More work on the letter version.

2 files changed, 184 insertions, 3 deletions

diff --git a/frsb_kac-rice.bib b/frsb_kac-rice.bib
index 0374c8a..0412ab7 100644
--- a/frsb_kac-rice.bib
+++ b/frsb_kac-rice.bib
@@ -376,16 +376,18 @@
  doi = {10.1103/physrevlett.124.078002}
 }
 
-@article{ElAlaoui_2020_Algorithmic,
+@unpublished{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},
+ archiveprefix = {arXiv},
  date = {2020-09-24T04:22:42Z},
  eprint = {2009.11481v1},
  eprintclass = {cond-mat.stat-mech},
- eprinttype = {arxiv}
+ eprinttype = {arxiv},
+ primaryclass = {cond-mat.stat-mech}
 }
 
 @article{ElAlaoui_2021_Optimization,
diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex
index ba54e06..d3369ac 100644
--- a/frsb_kac-rice_letter.tex
+++ b/frsb_kac-rice_letter.tex
@@ -73,7 +73,86 @@ between the TAP complexity and the equilibrium free energy, the TAP complexity
 can be computed with extensions of the equilibrium method. As a result, the TAP
 complexity has been previously computed for nontrivial hierarchical structure.
 
-\cite{Albert_2021_Searching}
+We study the mixed $p$-spin spherical models, with Hamiltonian
+\begin{equation} \label{eq:hamiltonian}
+  H(\mathbf s)=-\sum_p\frac1{p!}\sum_{i_1\cdots i_p}^NJ^{(p)}_{i_1\cdots i_p}s_{i_1}\cdots s_{i_p}
+\end{equation}
+is defined for vectors $\mathbf s\in\mathbb R^N$ confined to the sphere
+$\|\mathbf s\|^2=N$.  The coupling coefficients $J$ are taken at random, with
+zero mean and variance $\overline{(J^{(p)})^2}=a_pp!/2N^{p-1}$ chosen so that
+the energy is typically extensive. The overbar will always denote an average
+over the coefficients $J$. The factors $a_p$ in the variances are freely chosen
+constants that define the particular model. For instance, the so-called `pure'
+models have $a_p=1$ for some $p$ and all others zero.
+
+The variance of the couplings implies that the covariance of the energy with
+itself depends on only the dot product (or overlap) between two configurations.
+In particular, one finds
+\begin{equation} \label{eq:covariance}
+  \overline{H(\mathbf s_1)H(\mathbf s_2)}=Nf\left(\frac{\mathbf s_1\cdot\mathbf s_2}N\right)
+\end{equation}
+where $f$ is defined by the series
+\begin{equation}
+  f(q)=\frac12\sum_pa_pq^p
+\end{equation}
+One needn't start with a Hamiltonian like
+\eqref{eq:hamiltonian}, defined as a series: instead, the covariance rule
+\eqref{eq:covariance} can be specified for arbitrary, non-polynomial $f$, as in
+the `toy model' of M\'ezard and Parisi \cite{Mezard_1992_Manifolds}.
+
+The family of spherical models thus defined is quite rich, and by varying the
+covariance $f$ nearly any hierarchical structure can be found in
+equilibrium. Because of a correspondence between the ground state complexity
+and the entropy at zero temperature, any hierarchical structure in the
+equilibrium should be reflected in the complexity.
+
+The complexity is calculated using the Kac--Rice formula, which counts the
+stationary points using a $\delta$-function weighted by a Jacobian. The count
+is given by
+\begin{equation}
+  \begin{aligned}
+    \mathcal N(E, \mu)
+    &=\int_{S^{N-1}}d\mathbf s\, \delta\big(\nabla H(\mathbf s)\big)\,\big|\det\operatorname{Hess}H(\mathbf s)\big| \\
+    &\hspace{2pc}\times\delta\big(NE-H(\mathbf s)\big)\delta\big(N\mu-\operatorname{Tr}\operatorname{Hess}H(\mathbf s)\big)
+  \end{aligned}
+\end{equation}
+with two additional $\delta$-functions inserted to fix the energy density $E$
+and the stability $\mu$. The complexity is then
+\begin{equation} \label{eq:complexity}
+  \Sigma(E,\mu)=\lim_{N\to\infty}\frac1N\overline{\log\mathcal N(E, \mu})
+\end{equation}
+
+The stability $\mu$, sometimes called the radial reaction, determines the depth
+of minima or the index of saddles. At large $N$ the Hessian can be shown to
+consist of the sum of a GOE matrix with variance $f''(1)/N$ shifted by a
+constant diagonal matrix of value $\mu$. Therefore, the spectrum of the Hessian
+is a Wigner semicircle of radius $\mu_m=\sqrt{4f''(1)}$ centered at $\mu$. When
+$\mu>\mu_m$, stationary points are minima whose sloppiest eigenvalue is
+$\mu-\mu_m$. When $\mu=\mu_m$, the stationary points are marginal minima with
+flat directions. When $\mu<\mu_m$, the stationary points are saddles with
+indexed fixed to within order one (fixed macroscopic index).
+
+It's worth reviewing the complexity for the best-studied case of the pure model
+for $p\geq3$. Here, because the covariance is a homogeneous polynomial, $E$ and
+$\mu$ cannot be fixed separately, and one implies the other: $\mu=pE$.
+Therefore at each energy there is only one kind of stationary point. When the
+energy reaches $E_\mathrm{th}=\mu_m/p$, the population of stationary points
+suddenly shifts from all saddles to all minima, and there is an abrupt
+percolation transition in the topology of constant-energy slices of the
+landscape. This behavior of the complexity can be used to explain a rich
+variety of phenomena in the equilibrium and dynamics of the pure models: the
+threshold energy $E_\mathrm{th}$ corresponds to the average energy at the
+dynamic transition temperature, and the asymptotic energy reached by slow aging
+dynamics, and to the algorithmic limit $E_\mathrm{alg}$.
+
+Things become much less clear in even the simplest mixed models. For instance,
+one mixed model known to have a replica symmetric complexity was shown to
+nonetheless not have a clear relationship between features of the complexity
+and the asymptotic dynamics \cite{Folena_2020_Rethinking}.
+
+To compute the complexity in the generic case, we use the replica method to
+treat the logarithm inside the average of \eqref{eq:complexity}, and the
+$\delta$-functions are written in a Fourier basis.
 
 \begin{figure}
   \centering
@@ -97,6 +176,71 @@ complexity has been previously computed for nontrivial hierarchical structure.
   } \label{fig:2rsb.phases}
 \end{figure}
 
+It is known that by choosing a covariance $f$ as the sum of polynomials with
+well-separated powers, one develops 2RSB in equilibrium. This should correspond
+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}
+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 in equilibrium 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.287\,605\,530\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 might be relevant to where this algorithmic threshold
+lies. For the $3+16$ model at hand, $E_\mathrm{alg}=-1.275\,140\,128\ldots$.
+
+In this model, the RS complexity gives an inconsistent answer for the
+complexity of the ground state, predicting that the complexity of minima
+vanishes at a higher energy than the complexity of saddles, with both at a
+lower energy than the equilibrium ground state. The 1RSB complexity resolves
+these problems, predicting the same ground state as equilibrium and with a ground state stability $\mu_0=6.480\,764\ldots>\mu_m$. It predicts that the
+complexity of marginal minima (and therefore all saddles) vanishes at
+$E_m=-1.287\,605\,527\ldots$, which is very slightly greater than $E_0$. Saddles
+become dominant over minima at a higher energy $E_\mathrm{th}=-1.287\,575\,114\ldots$.
+The 1RSB complexity transitions to a RS description for dominant stationary
+points at an energy $E_1=-1.273\,886\,852\ldots$. The highest energy for which
+the 1RSB description exists is $E_\mathrm{max}=-0.886\,029\,051\ldots$
+
+For minima, the complexity does
+not inherit a 1RSB description until the energy is with in a close vicinity of
+the ground state. On the other hand, for high-index saddles the complexity
+becomes described by 1RSB at quite high energies. This suggests that when
+sampling a landscape at high energies, high index saddles may show a sign of
+replica symmetry breaking when minima or inherent states do not.
+
+Fig.~\ref{fig:2rsb.phases} shows a different detail of the complexity in the
+vicinity of the ground state, now as functions of the energy difference and
+stability difference from the ground state. Several of the landmark energies
+described above are plotted, alongside the boundaries between the `phases.'
+Though $E_\mathrm{alg}$ looks quite close to the energy at which dominant
+saddles transition from 1RSB to RS, they differ by roughly $10^{-3}$, as
+evidenced by the numbers cited above. Likewise, though $\langle E\rangle_1$
+looks very close to $E_\mathrm{max}$, where the 1RSB transition line
+terminates, they too differ. The fact that $E_\mathrm{alg}$ is very slightly
+below the place where most saddle transition to 1RSB is suggestive; we
+speculate that an analysis of the typical minima connected to these saddles by
+downward trajectories will coincide with the algorithmic limit. An analysis of
+the typical nearby minima or the typical downward trajectories from these
+saddles at 1RSB is warranted \cite{Ros_2019_Complex, Ros_2021_Dynamical}. Also
+notable is that $E_\mathrm{alg}$ is at a significantly higher energy than
+$E_\mathrm{th}$; according to the theory, optimal smooth algorithms in this
+model stall in a place where minima are exponentially subdominant.
+
 \begin{figure}
   \centering
   \includegraphics[width=\columnwidth]{figs/24_phases.pdf}
@@ -108,6 +252,41 @@ complexity has been previously computed for nontrivial hierarchical structure.
   } \label{fig:frsb.phases}
 \end{figure}
 
+If the covariance $f$ is chosen to be concave, then one develops FRSB in equilibrium. To this purpose, we choose
+\begin{equation}
+  f(q)=\frac12\left(q^2+\frac1{16}q^4\right)
+\end{equation}
+also studied before in equilibrium \cite{Crisanti_2004_Spherical, Crisanti_2006_Spherical}. Because the ground state is FRSB, for this model
+\begin{equation}
+  E_0=E_\mathrm{alg}=E_\mathrm{th}=-\int_0^1dq\,\sqrt{f''(q)}=-1.059\,384\,319\ldots
+\end{equation}
+In the equilibrium solution, the transition temperature from RS to FRSB is $\beta_\infty=1$, with corresponding average energy $\langle E\rangle_\infty=-0.53125\ldots$.
+
+Along the supersymmetric line, the FRSB solution can be found in full, exact
+functional form.  To treat the FRSB away from this line numerically, we resort to
+finite $k$RSB approximations.  Since we are not trying to find the actual
+$k$RSB solution, but approximate the FRSB one, we drop the extremal condition
+\eqref{eq:cond.x} for $x_1,\ldots,x_k$ and instead set
+\begin{equation}
+  x_i=\left(\frac i{k+1}\right)x_\textrm{max}
+\end{equation}
+and extremize over $x_\textrm{max}$ alone. This dramatically simplifies the
+equations that must be solved to find solutions. In the results that follow, a
+20RSB approximation is used to trace the dominant saddles and marginal minima, while
+a 5RSB approximation is used to trace the (much longer) boundaries of the
+complexity.
+
+Fig.~\ref{fig:frsb.complexity} shows the complexity for this model as a
+function of energy difference from the ground state for several notable
+trajectories in the energy and stability plane. Fig.~\ref{fig:frsb.phases}
+shows these trajectories, along with the phase boundaries of the complexity in
+this plane. Notably, the phase boundary predicted by \eqref{eq:mu.transition}
+correctly predicts where all of the finite $k$RSB approximations terminate.
+Like the 1RSB model in the previous subsection, this phase boundary is oriented
+such that very few, low energy, minima are described by a FRSB solution, while
+relatively high energy saddles of high index are also. Again, this suggests
+that studying the mutual distribution of high-index saddle points might give
+insight into lower-energy symmetry breaking in more general contexts.
 
 \paragraph{Acknowledgements}
 The authors would like to thank Valentina Ros for helpful discussions.