论文标题
对称感知的关键窗口
Critical Window of The Symmetric Perceptron
论文作者
论文摘要
我们研究对称二进制感知的临界窗口，或同等的组合差异。考虑找到满足$ \ |aσ\ | _ \ infty \ le k $的二进制矢量$σ$的问题，其中$ a $是$αn\ times n $矩阵，带有iid高斯条目。对于固定的$ k $，在哪种密度$α$的情况下，这种约束满意度问题（CSP）令人满意？珀金斯和徐，李，李和狡猾的敏锐的门槛最近建立了一个第一阶。也就是说，对于每种$ k $，都存在一个明确的关键密度$α_c$，因此对于任何固定的$ε> 0 $，具有较高的概率，CSP对于$αn<（α_c -ε）n $可满足，对于$ age n>（α_c +ε）n $。这对应于关键窗口大小的$ O（n）$的界面。 我们显着提高了这些结果，并提供指数式的尾巴界限。我们的主要结果是，也许令人惊讶的是，关键窗口实际上最多是$ o（\ log n）$。更确切地说，对于$αn<α_cn -o（\ log n）$，CSP可满足CSP的满足，并且对于任何$αN>α_cn +ω（1）$而言，CSP可满足。这意味着对称感知器几乎具有“最尖锐的过渡”，将其添加到CSP的简短列表中，严格众所周知，临界窗口宽度为接近恒定的宽度。
We study the critical window of the symmetric binary perceptron, or equivalently, combinatorial discrepancy. Consider the problem of finding a binary vector $σ$ satisfying $\|Aσ\|_\infty \le K$, where $A$ is an $αn \times n$ matrix with iid Gaussian entries. For fixed $K$, at which densities $α$ is this constraint satisfaction problem (CSP) satisfiable? A sharp threshold was recently established by Perkins and Xu, and Abbe, Li, and Sly , answering this to first order. Namely, for each $K$ there exists an explicit critical density $α_c$ so that for any fixed $ε> 0$, with high probability the CSP is satisfiable for $αn < (α_c - ε) n$ and unsatisfiable for $αn > (α_c + ε) n$. This corresponds to a bound of $o(n)$ on the size of the critical window. We sharpen these results significantly, as well as provide exponential tail bounds. Our main result is that, perhaps surprisingly, the critical window is actually at most $O(\log n)$. More precisely, with high probability the CSP is satisfiable for $αn < α_c n -O(\log n)$ and unsatisfiable for any $αn > α_c n + ω(1)$. This implies the symmetric perceptron has nearly the "sharpest possible transition," adding it to a short list of CSP for which the critical window is rigorously known to be of near-constant width.
