Started adding discussion of the algorithmic threshold.

2 files changed, 76 insertions, 3 deletions

diff --git a/frsb_kac-rice.bib b/frsb_kac-rice.bib
index ecd2fed..2c12f3b 100644
--- a/frsb_kac-rice.bib
+++ b/frsb_kac-rice.bib
@@ -209,7 +209,7 @@
 
 @article{Crisanti_2004_Spherical,
  author = {Crisanti, A. and Leuzzi, L.},
- title = {Spherical $2+p$ Spin-Glass Model: An Exactly Solvable Model for Glass to Spin-Glass Transition},
+ title = {Spherical {$2+p$} Spin-Glass Model: An Exactly Solvable Model for Glass to Spin-Glass Transition},
  journal = {Physical Review Letters},
  publisher = {American Physical Society (APS)},
  year = {2004},
@@ -235,6 +235,20 @@
  doi = {10.1103/physrevb.73.014412}
 }
 
+@article{Crisanti_2011_Statistical,
+ author = {Crisanti, A. and Leuzzi, L. and Paoluzzi, M.},
+ title = {Statistical mechanical approach to secondary processes and structural relaxation in glasses and glass formers},
+ journal = {The European Physical Journal E},
+ publisher = {Springer Science and Business Media LLC},
+ year = {2011},
+ month = {9},
+ number = {9},
+ volume = {34},
+ pages = {98},
+ url = {https://doi.org/10.1140%2Fepje%2Fi2011-11098-3},
+ doi = {10.1140/epje/i2011-11098-3}
+}
+
 @article{Cugliandolo_1993_Analytical,
  author = {Cugliandolo, L. F. and Kurchan, J.},
  title = {Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model},
@@ -263,6 +277,33 @@
  doi = {10.1103/physrevlett.124.078002}
 }
 
+@article{ElAlaoui_2020_Algorithmic,
+ author = {El Alaoui, Ahmed and Montanari, Andrea},
+ title = {Algorithmic Thresholds in Mean Field Spin Glasses},
+ year = {2020},
+ month = {9},
+ url = {http://arxiv.org/abs/2009.11481v1},
+ date = {2020-09-24T04:22:42Z},
+ eprint = {2009.11481v1},
+ eprintclass = {cond-mat.stat-mech},
+ eprinttype = {arxiv},
+ urldate = {2022-07-08T16:19:15.304072Z}
+}
+
+@article{ElAlaoui_2021_Optimization,
+ author = {El Alaoui, Ahmed and Montanari, Andrea and Sellke, Mark},
+ title = {Optimization of mean-field spin glasses},
+ journal = {The Annals of Probability},
+ publisher = {Institute of Mathematical Statistics},
+ year = {2021},
+ month = {11},
+ number = {6},
+ volume = {49},
+ pages = {2922--2960},
+ url = {https://doi.org/10.1214%2F21-aop1519},
+ doi = {10.1214/21-aop1519}
+}
+
 @article{ElAlaoui_2022_Sampling,
  author = {El Alaoui, Ahmed and Montanari, Andrea and Sellke, Mark},
  title = {Sampling from the {Sherrington}-{Kirkpatrick} {Gibbs} measure via algorithmic
diff --git a/frsb_kac-rice.tex b/frsb_kac-rice.tex
index dda10f2..51c72bf 100644
--- a/frsb_kac-rice.tex
+++ b/frsb_kac-rice.tex
@@ -655,6 +655,18 @@ complexity in the ground state are
   d_d=\hat\beta r_d
 \end{align}
 
+The supersymmetric solution produces the correct complexity for the ground
+state and for a class of minima. Moreover, it produces the correct parameters
+for the fields $C$, $R$, and $D$ at those points. This is an important foothold
+in the problem of computing the general complexity. The full saddle point
+equations at $k$-RSB are not very numerically stable, and a `good' saddle point
+has a typically small radius of convergence under methods like Newton's
+algorithm. With the supersymmetric solution in hand, it is possible to take
+small steps in the parameter space to find non-supersymmetric numeric
+solutions, each time ensuring the initial conditions for the solver are
+sufficiently close to the correct answer. This is the strategy we use in
+\S\ref{sec:examples}.
+
 \section{Full replica symmetry breaking}
 
 This reasoning applies equally well to FRSB systems.
@@ -810,6 +822,7 @@ that this is the line of stability for the replica symmetric saddle.
 
 
 \section{General solution: examples}
+\label{sec:examples}
 
 \subsection{1RSB complexity}
 
@@ -819,8 +832,27 @@ to 1RSB in Kac--Rice. For this example, we take
 \begin{equation}
   f(q)=\frac12\left(q^3+\frac1{16}q^{16}\right)
 \end{equation}
-With this covariance, the model sees a RS to 1RSB transition at
-$\beta_1=1.70615\ldots$ and a 1RSB to 2RSB transition at $\beta_2=6.02198\ldots$. At these points, the average energies are $\langle E\rangle_1=-0.906391\ldots$ and $\langle E\rangle_2=-1.19553\ldots$, and the ground state energy is $E_0=-1.2876055305\ldots$.
+established to have a 2RSB ground state \cite{Crisanti_2011_Statistical}.
+With this covariance, the model sees a replica symmetric to 1RSB transition at
+$\beta_1=1.70615\ldots$ and a 1RSB to 2RSB transition at
+$\beta_2=6.02198\ldots$. At these transitions, the average energies are
+$\langle E\rangle_1=-0.906391\ldots$ and $\langle E\rangle_2=-1.19553\ldots$,
+respectively, and the ground state energy is $E_0=-1.2876055305\ldots$.
+Besides these typical equilibrium energies, an energy of special interest for
+looking at the landscape topology is the \emph{algorithmic threshold}
+$E_\mathrm{alg}$, defined by the lowest energy reached by local algorithms like
+approximate message passing \cite{ElAlaoui_2020_Algorithmic,
+ElAlaoui_2021_Optimization}. In the spherical models, this has been proven to
+be
+\begin{equation}
+  E_{\mathrm{alg}}=-\int_0^1dq\,\sqrt{f''(q)}
+\end{equation}
+For full RSB systems, $E_\mathrm{alg}=E_0$ and the algorithm can reach the
+ground state energy. For the pure $p$-spin models,
+$E_\mathrm{alg}=E_\mathrm{th}$, where $E_\mathrm{th}$ is the energy at which
+marginal minima are the most common stationary points. Something about the
+topology of the energy function is relevant to where this algorithmic threshold
+lies. For the $3+16$ model at hand, $E_\mathrm{alg}=1.275140128\ldots$.
 
 In this model, the RS complexity gives an inconsistent answer for the
 complexity of the ground state, predicting that the complexity of minima