Algorithmic pure states for the negative spherical perceptron

We consider the spherical perceptron with Gaussian disorder. This is the set S of points σ ∈ ℝN on the sphere of radius √N satisfying langle ga , σ rangle ≥ kappa√N, for all 1 ≤ a ≤ M, where (ga)a=1M are independent standard gaussian vectors and kappa ∈ ℝ 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 → ∞, M/N → α. 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 α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σ satisfying langle ga , hatσrangle ≥ kappa √N for all 1≤ a ≤ M and lying on a sphere of non-trivial radius √barq N, where barq ∈ (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 barq → 1 as α → αSAT(kappa), so that biglangle ga,hatσ/|hatσ|bigrangle ≥ (kappa-o(1))√N near criticality.