论文标题
负球体感知的算法纯状态
Algorithmic pure states for the negative spherical perceptron
论文作者
论文摘要
我们认为具有高斯疾病的球形感知。这是\ in \ mathbb {r}^n $的集合$ s $ s $ s $ $（g_a）_ {a = 1}^m $是独立的标准高斯矢量，而$κ\ in \ mathbb {r} $是固定的。 $ s $的各种特征，例如其表面度量和其非空的最大$ m $，在渐近制度$ n \ to \ infty $，$ m/n \ toα$的统计物理学中按统计物理进行了启发。 The case $κ<0$ is of special interest as $S$ is conjectured to exhibit a hierarchical tree-like geometry known as "full replica-symmetry breaking" (FRSB) close to the satisfiability threshold $α_{\text{SAT}}(κ)$, and whose characteristics are captured by a Parisi variational principle akin to the one appearing in the Sherrington-Kirkpatrick模型。在本文中，我们设计了一种有效的算法，该算法在鉴于对巴黎变量原理的解决方案的访问权限，将这种猜想的FRSB结构利用为$κ<0 $，并输出一个vector $ \hatσ$满足$ \ langle g_a，\ hatt pecrange g_a，\hatσ\ hatten \ gebeκ\κ\ be $κ$ and $ and $ and $ and $ n}非平凡半径$ \ sqrt {\ bar {q} n} $的球体，其中$ \ bar {q} \ in（0,1）$是支持相关Parisi度量的右端。我们预计$ \hatσ$大约是球形感知纯状态的重中心。此外，我们期望$ \ bar {q} \ to 1 $ as $α\ toα_ {\ text {sat}}（κ）$，因此$ \ big \ big \ big \ langle g_a，\hatσ/| \hatσ| \ big big big big big big \ big \ rangle \ geq（geq（κ-crigite）
We consider the spherical perceptron with Gaussian disorder. This is the set $S$ of points $σ\in \mathbb{R}^N$ on the sphere of radius $\sqrt{N}$ satisfying $\langle g_a , σ\rangle \ge κ\sqrt{N}\,$ for all $1 \le a \le M$, where $(g_a)_{a=1}^M$ are independent standard gaussian vectors and $κ\in \mathbb{R}$ is fixed. Various characteristics of $S$ such as its surface measure and the largest $M$ for which it is non-empty, were computed heuristically in statistical physics in the asymptotic regime $N \to \infty$, $M/N \to α$. The case $κ<0$ is of special interest as $S$ is conjectured to exhibit a hierarchical tree-like geometry known as "full replica-symmetry breaking" (FRSB) close to the satisfiability threshold $α_{\text{SAT}}(κ)$, and whose characteristics are captured by a Parisi variational principle akin to the one appearing in the Sherrington-Kirkpatrick model. In this paper we design an efficient algorithm which, given oracle access to the solution of the Parisi variational principle, exploits this conjectured FRSB structure for $κ<0$ and outputs a vector $\hatσ$ satisfying $\langle g_a , \hatσ\rangle \ge κ\sqrt{N}$ for all $1\le a \le M$ and lying on a sphere of non-trivial radius $\sqrt{\bar{q} N}$, where $\bar{q} \in (0,1)$ is the right-end of the support of the associated Parisi measure. We expect $\hatσ$ to be approximately the barycenter of a pure state of the spherical perceptron. Moreover we expect that $\bar{q} \to 1$ as $α\to α_{\text{SAT}}(κ)$, so that $\big\langle g_a,\hatσ/|\hatσ|\big\rangle \geq (κ-o(1))\sqrt{N}$ near criticality.
