From 96b88b3959482ba740bf275588b9d63ec1b49c84 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 8 Jul 2022 18:28:20 +0200 Subject: Started adding discussion of the algorithmic threshold. --- frsb_kac-rice.bib | 43 ++++++++++++++++++++++++++++++++++++++++++- frsb_kac-rice.tex | 36 ++++++++++++++++++++++++++++++++++-- 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 -- cgit v1.2.3-70-g09d2