From 96b88b3959482ba740bf275588b9d63ec1b49c84 Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Fri, 8 Jul 2022 18:28:20 +0200
Subject: Started adding discussion of the algorithmic threshold.

---
 frsb_kac-rice.tex | 36 ++++++++++++++++++++++++++++++++++--
 1 file changed, 34 insertions(+), 2 deletions(-)

(limited to 'frsb_kac-rice.tex')

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
-- 
cgit v1.2.3-70-g09d2