Algorithmic pure states for the negative spherical perceptron

Abstract

We consider the spherical perceptron with Gaussian disorder. This is the set $S$ of points $\sigma \in {\mathbb{R}}^N$ on the sphere of radius $\sqrt{N}$ satisfying $⟨g_a,\sigma ⟩\ge \kappa \sqrt{N}$ for all $1\le a\le M$, where $(g_a{)}_{a=1}^M$ are independent standard gaussian vectors and $\kappa \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 \alpha$. The case $\kappa <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 ${\alpha }_{\text{SAT}}(\kappa )$, 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 $\kappa <0$ and outputs a vector $\hat{\sigma }$ satisfying $⟨g_a,\hat{\sigma }⟩\ge \kappa \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{\sigma }$ to be approximately the barycenter of a pure state of the spherical perceptron. Moreover we expect that $\bar{q}\to 1$ as $\alpha \to {\alpha }_{\text{SAT}}(\kappa )$, so that $⟨g_a,\hat{\sigma }/|\hat{\sigma }|⟩\ge (\kappa -o(1))\sqrt{N}$ near criticality.

34 pages