diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | appeal.tex | 70 | ||||
| -rw-r--r-- | figs/24_detail_letter_legend.pdf | bin | 0 -> 5443 bytes | |||
| -rw-r--r-- | figs/24_phases_letter.pdf | bin | 0 -> 45067 bytes | |||
| -rw-r--r-- | figs/316_complexity_contour_1_letter.pdf | bin | 0 -> 742706 bytes | |||
| -rw-r--r-- | figs/316_detail_letter.pdf | bin | 0 -> 75758 bytes | |||
| -rw-r--r-- | figs/316_detail_letter_legend.pdf | bin | 0 -> 5477 bytes | |||
| -rw-r--r-- | frsb_kac-rice.bib | 101 | ||||
| -rw-r--r-- | frsb_kac-rice_letter.tex | 435 |
9 files changed, 569 insertions, 38 deletions
@@ -11,3 +11,4 @@ *.run.xml *.synctex(busy) *.toc +*Notes.bib diff --git a/appeal.tex b/appeal.tex new file mode 100644 index 0000000..7ae78f4 --- /dev/null +++ b/appeal.tex @@ -0,0 +1,70 @@ +\documentclass[a4paper]{letter} + +\usepackage[utf8]{inputenc} % why not type "Bézout" with unicode? +\usepackage[T1]{fontenc} % vector fonts plz +\usepackage{newtxtext,newtxmath} % Times for PR +\usepackage[ + colorlinks=true, + urlcolor=purple, + linkcolor=black, + citecolor=black, + filecolor=black +]{hyperref} % ref and cite links with pretty colors +\usepackage{xcolor} +\usepackage[style=phys]{biblatex} + +\addbibresource{bezout.bib} + +\signature{ + \vspace{-6\medskipamount} + \smallskip + Jaron Kent-Dobias \& Jorge Kurchan +} + +\address{ + Laboratoire de Physique\\ + Ecole Normale Sup\'erieure\\ + 24 rue Lhomond\\ + 75005 Paris +} + +\begin{document} +\begin{letter}{ + Editorial Office\\ + Physical Review Letters\\ + 1 Research Road\\ + Ridge, NY 11961 +} + +\opening{To the editors of Physical Review,} + +We wish to appeal the decision on our manuscript \emph{How to count in +hierarchical landscapes: A ‘full’ solution to mean-field complexity}, which was +rejected without being sent to referees. + +The problem of characterizing the geometry of complex energy and cost +landscapes is long-standing. Until this work, the correct calculation of the +complexity has only been made for a small minority of systems, those with +so-called replica symmetry. We show explicitly how such calculations can be +made for the vast majority of cases. + +Landscape complexity even for the simple models we consider is relevant to a +broad spectrum of physics disciplines. These models appear explicitly in modern +research of machine learning, like tensor denoising, and understanding how +complexity, dynamics, and equilibrium interplay in them provides powerful analogies +and insights into emergent phenomena in more complicated contexts, from +realistic machine learning models to the behavior of structural glasses. +Already in this work, we identify the surprising result that the purported +algorithmic threshold for optimization on mean-field cost functions lies +\emph{far above} the geometric threshold traditionally understood as the dynamic limit. + +We urge you to allow this paper to go to referees and allow it to +be judged by other scientists at the forefront of these fields. + +\closing{Sincerely,} + +\vspace{1em} + +\end{letter} + +\end{document} diff --git a/figs/24_detail_letter_legend.pdf b/figs/24_detail_letter_legend.pdf Binary files differnew file mode 100644 index 0000000..ca32ca0 --- /dev/null +++ b/figs/24_detail_letter_legend.pdf diff --git a/figs/24_phases_letter.pdf b/figs/24_phases_letter.pdf Binary files differnew file mode 100644 index 0000000..366f49e --- /dev/null +++ b/figs/24_phases_letter.pdf diff --git a/figs/316_complexity_contour_1_letter.pdf b/figs/316_complexity_contour_1_letter.pdf Binary files differnew file mode 100644 index 0000000..b5aa80d --- /dev/null +++ b/figs/316_complexity_contour_1_letter.pdf diff --git a/figs/316_detail_letter.pdf b/figs/316_detail_letter.pdf Binary files differnew file mode 100644 index 0000000..4c33457 --- /dev/null +++ b/figs/316_detail_letter.pdf diff --git a/figs/316_detail_letter_legend.pdf b/figs/316_detail_letter_legend.pdf Binary files differnew file mode 100644 index 0000000..756a2c7 --- /dev/null +++ b/figs/316_detail_letter_legend.pdf diff --git a/frsb_kac-rice.bib b/frsb_kac-rice.bib index 0374c8a..f8d4265 100644 --- a/frsb_kac-rice.bib +++ b/frsb_kac-rice.bib @@ -1,6 +1,6 @@ @article{Albert_2021_Searching, author = {Albert, Samuel and Biroli, Giulio and Ladieu, François and Tourbot, Roland and Urbani, Pierfrancesco}, - title = {Searching for the {Gardner} Transition in Glassy Glycerol}, + title = {Searching for the Gardner Transition in Glassy Glycerol}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {2021}, @@ -14,7 +14,7 @@ @article{Altieri_2021_Properties, author = {Altieri, Ada and Roy, Felix and Cammarota, Chiara and Biroli, Giulio}, - title = {Properties of Equilibria and Glassy Phases of the Random {Lotka}-{Volterra} Model with Demographic Noise}, + title = {Properties of Equilibria and Glassy Phases of the Random Lotka-Volterra Model with Demographic Noise}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {2021}, @@ -28,7 +28,7 @@ @article{Annibale_2003_Supersymmetric, author = {Annibale, Alessia and Cavagna, Andrea and Giardina, Irene and Parisi, Giorgio}, - title = {Supersymmetric complexity in the {Sherrington}-{Kirkpatrick} model}, + title = {Supersymmetric complexity in the Sherrington-Kirkpatrick model}, journal = {Physical Review E}, publisher = {American Physical Society (APS)}, year = {2003}, @@ -42,7 +42,7 @@ @article{Annibale_2003_The, author = {Annibale, Alessia and Cavagna, Andrea and Giardina, Irene and Parisi, Giorgio and Trevigne, Elisa}, - title = {The role of the {Becchi}--{Rouet}--{Stora}--{Tyutin} supersymmetry in the calculation of the complexity for the {Sherrington}--{Kirkpatrick} model}, + title = {The role of the Becchi--Rouet--Stora--Tyutin supersymmetry in the calculation of the complexity for the Sherrington--Kirkpatrick model}, journal = {Journal of Physics A: Mathematical and General}, publisher = {IOP Publishing}, year = {2003}, @@ -112,7 +112,7 @@ @article{Berthier_2019_Gardner, author = {Berthier, Ludovic and Biroli, Giulio and Charbonneau, Patrick and Corwin, Eric I. and Franz, Silvio and Zamponi, Francesco}, - title = {{Gardner} physics in amorphous solids and beyond}, + title = {Gardner physics in amorphous solids and beyond}, journal = {The Journal of Chemical Physics}, publisher = {AIP Publishing}, year = {2019}, @@ -140,7 +140,7 @@ @article{Biroli_2018_Liu-Nagel, author = {Biroli, Giulio and Urbani, Pierfrancesco}, - title = {{Liu}-{Nagel} phase diagrams in infinite dimension}, + title = {Liu-Nagel phase diagrams in infinite dimension}, journal = {SciPost Physics}, publisher = {Stichting SciPost}, year = {2018}, @@ -168,7 +168,7 @@ @article{Bray_2007_Statistics, author = {Bray, Alan J. and Dean, David S.}, - title = {Statistics of Critical Points of {Gaussian} Fields on Large-Dimensional Spaces}, + title = {Statistics of Critical Points of Gaussian Fields on Large-Dimensional Spaces}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {2007}, @@ -210,7 +210,7 @@ @article{Cavagna_1998_Stationary, author = {Cavagna, Andrea and Giardina, Irene and Parisi, Giorgio}, - title = {Stationary points of the {Thouless}-{Anderson}-{Palmer} free energy}, + title = {Stationary points of the Thouless-Anderson-Palmer free energy}, journal = {Physical Review B}, publisher = {American Physical Society (APS)}, year = {1998}, @@ -252,7 +252,7 @@ @article{Charbonneau_2015_Numerical, author = {Charbonneau, Patrick and Jin, Yuliang and Parisi, Giorgio and Rainone, Corrado and Seoane, Beatriz and Zamponi, Francesco}, - title = {Numerical detection of the {Gardner} transition in a mean-field glass former}, + title = {Numerical detection of the Gardner transition in a mean-field glass former}, journal = {Physical Review E}, publisher = {American Physical Society (APS)}, year = {2015}, @@ -294,7 +294,7 @@ @article{Crisanti_1995_Thouless-Anderson-Palmer, author = {Crisanti, A. and Sommers, H.-J.}, - title = {{Thouless}-{Anderson}-{Palmer} Approach to the Spherical {$p$}-Spin Spin Glass Model}, + title = {Thouless-Anderson-Palmer Approach to the Spherical $p$-Spin Spin Glass Model}, journal = {Journal de Physique I}, publisher = {EDP Sciences}, year = {1995}, @@ -308,7 +308,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}, @@ -322,7 +322,7 @@ @article{Crisanti_2006_Spherical, author = {Crisanti, A. and Leuzzi, L.}, - title = {Spherical {$2+p$} spin-glass model: An analytically solvable model with a glass-to-glass transition}, + title = {Spherical $2+p$ spin-glass model: An analytically solvable model with a glass-to-glass transition}, journal = {Physical Review B}, publisher = {American Physical Society (APS)}, year = {2006}, @@ -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, @@ -402,17 +404,19 @@ doi = {10.1214/21-aop1519} } -@article{ElAlaoui_2022_Sampling, +@unpublished{ElAlaoui_2022_Sampling, author = {El Alaoui, Ahmed and Montanari, Andrea and Sellke, Mark}, - title = {Sampling from the {Sherrington}-{Kirkpatrick} {Gibbs} measure via algorithmic + title = {Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization}, year = {2022}, month = {3}, url = {http://arxiv.org/abs/2203.05093v1}, + archiveprefix = {arXiv}, date = {2022-03-10T00:15:22Z}, eprint = {2203.05093v1}, eprintclass = {math.PR}, - eprinttype = {arxiv} + eprinttype = {arxiv}, + primaryclass = {cond-mat.stat-mech} } @article{Folena_2020_Rethinking, @@ -432,14 +436,14 @@ stochastic localization}, @phdthesis{Folena_2020_The, author = {Folena, Giampaolo}, - title = {The mixed {$p$}-spin model: selecting, following and losing states}, + title = {The mixed $p$-spin model: selecting, following and losing states}, year = {2020}, month = {3}, number = {2020UPASS060}, url = {https://tel.archives-ouvertes.fr/tel-02883385}, hal_id = {tel-02883385}, hal_version = {v1}, - school = {Université Paris-Saclay \& Università degli studi La Sapienza (Rome)}, + school = {Université Paris-Saclay & Università degli studi La Sapienza (Rome)}, type = {Theses} } @@ -459,7 +463,7 @@ stochastic localization}, @article{Gamarnik_2021_The, author = {Gamarnik, David and Jagannath, Aukosh}, - title = {The overlap gap property and approximate message passing algorithms for {$p$}-spin models}, + title = {The overlap gap property and approximate message passing algorithms for $p$-spin models}, journal = {The Annals of Probability}, publisher = {Institute of Mathematical Statistics}, year = {2021}, @@ -473,7 +477,7 @@ stochastic localization}, @article{Gardner_1985_Spin, author = {Gardner, E.}, - title = {Spin glasses with {$p$}-spin interactions}, + title = {Spin glasses with $p$-spin interactions}, journal = {Nuclear Physics B}, publisher = {Elsevier BV}, year = {1985}, @@ -486,8 +490,8 @@ stochastic localization}, @article{Geirhos_2018_Johari-Goldstein, author = {Geirhos, K. and Lunkenheimer, P. and Loidl, A.}, - title = {{Johari}-{Goldstein} Relaxation Far Below -{$T_g$}: Experimental Evidence for the {Gardner} Transition in Structural Glasses?}, + title = {Johari-Goldstein Relaxation Far Below +$T_g$: Experimental Evidence for the Gardner Transition in Structural Glasses?}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {2018}, @@ -508,14 +512,14 @@ stochastic localization}, pages = {204--209}, url = {https://doi.org/10.1142%2F9789812701558_0023}, doi = {10.1142/9789812701558_0023}, - booksubtitle = {Proceedings of the 31st Workshop of the International School of Solid State Physics, {Erice}, {Sicily}, {Italy}, 20 – 26 {July} 2004}, + booksubtitle = {Proceedings of the 31st Workshop of the International School of Solid State Physics, Erice, Sicily, Italy, 20 – 26 July 2004}, booktitle = {Complexity, Metastability and Nonextensivity}, editor = {Beck, C and Benedek, G and Rapisarda, A and Tsallis, C} } @article{Gross_1985_Mean-field, author = {Gross, D. J. and Kanter, I. and Sompolinsky, H.}, - title = {Mean-field theory of the {Potts} glass}, + title = {Mean-field theory of the Potts glass}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {1985}, @@ -543,7 +547,7 @@ stochastic localization}, @article{Hicks_2018_Gardner, author = {Hicks, C. L. and Wheatley, M. J. and Godfrey, M. J. and Moore, M. A.}, - title = {{Gardner} Transition in Physical Dimensions}, + title = {Gardner Transition in Physical Dimensions}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {2018}, @@ -555,16 +559,18 @@ stochastic localization}, doi = {10.1103/physrevlett.120.225501} } -@article{Huang_2021_Tight, +@unpublished{Huang_2021_Tight, author = {Huang, Brice and Sellke, Mark}, - title = {Tight {Lipschitz} Hardness for Optimizing Mean Field Spin Glasses}, + title = {Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses}, year = {2021}, month = {10}, url = {http://arxiv.org/abs/2110.07847v1}, + archiveprefix = {arXiv}, date = {2021-10-15T04:08:35Z}, eprint = {2110.07847v1}, eprintclass = {math.PR}, - eprinttype = {arxiv} + eprinttype = {arxiv}, + primaryclass = {cond-mat.stat-mech} } @article{Kac_1943_On, @@ -597,18 +603,37 @@ stochastic localization}, @article{Kent-Dobias_2022_Analytic, author = {Kent-Dobias, Jaron and Kurchan, Jorge}, title = {Analytic continuation over complex landscapes}, + journal = {Journal of Physics A: Mathematical and Theoretical}, + publisher = {IOP Publishing}, year = {2022}, - month = {4}, - url = {http://arxiv.org/abs/2204.06072v1}, - date = {2022-04-12T20:24:54Z}, - eprint = {2204.06072v1}, + month = {10}, + number = {43}, + volume = {55}, + pages = {434006}, + url = {https://doi.org/10.1088%2F1751-8121%2Fac9cc7}, + doi = {10.1088/1751-8121/ac9cc7}, + collection = {Random Landscapes and Dynamics in Evolution, Ecology and Beyond} +} + +@unpublished{Kent-Dobias_2022_How, + author = {Kent-Dobias, Jaron and Kurchan, Jorge}, + title = {How to count in hierarchical landscapes: a `full' solution to mean-field +complexity}, + year = {2022}, + month = {7}, + url = {http://arxiv.org/abs/2207.06161v2}, + archiveprefix = {arXiv}, + date = {2022-07-13T12:45:58Z}, + eprint = {2207.06161v2}, eprintclass = {cond-mat.stat-mech}, - eprinttype = {arxiv} + eprinttype = {arxiv}, + primaryclass = {cond-mat.stat-mech}, + urldate = {2022-10-05T20:12:41.619402Z} } @article{Li_2021_Determining, author = {Li, Huaping and Jin, Yuliang and Jiang, Ying and Chen, Jeff Z. Y.}, - title = {Determining the nonequilibrium criticality of a {Gardner} transition via a hybrid study of molecular simulations and machine learning}, + title = {Determining the nonequilibrium criticality of a Gardner transition via a hybrid study of molecular simulations and machine learning}, journal = {Proceedings of the National Academy of Sciences}, publisher = {Proceedings of the National Academy of Sciences}, year = {2021}, @@ -763,7 +788,7 @@ stochastic localization}, @article{Rieger_1992_The, author = {Rieger, H.}, - title = {The number of solutions of the {Thouless}-{Anderson}-{Palmer} equations for {$p$}-spin-interaction spin glasses}, + title = {The number of solutions of the Thouless-Anderson-Palmer equations for $p$-spin-interaction spin glasses}, journal = {Physical Review B}, publisher = {American Physical Society (APS)}, year = {1992}, @@ -819,7 +844,7 @@ stochastic localization}, @article{Seguin_2016_Experimental, author = {Seguin, A. and Dauchot, O.}, - title = {Experimental Evidence of the {Gardner} Phase in a Granular Glass}, + title = {Experimental Evidence of the Gardner Phase in a Granular Glass}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {2016}, @@ -847,7 +872,7 @@ stochastic localization}, @article{Xiao_2022_Probing, author = {Xiao, Hongyi and Liu, Andrea J. and Durian, Douglas J.}, - title = {Probing {Gardner} Physics in an Active Quasithermal Pressure-Controlled Granular System of Noncircular Particles}, + title = {Probing Gardner Physics in an Active Quasithermal Pressure-Controlled Granular System of Noncircular Particles}, journal = {Physical Review Letters}, publisher = {American Physical Society (APS)}, year = {2022}, diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex new file mode 100644 index 0000000..4fb22e7 --- /dev/null +++ b/frsb_kac-rice_letter.tex @@ -0,0 +1,435 @@ + +\documentclass[reprint,aps,prl,longbibliography,floatfix]{revtex4-2} + +\usepackage[utf8]{inputenc} % why not type "Bézout" with unicode? +\usepackage[T1]{fontenc} % vector fonts plz +\usepackage{amsmath,amssymb,latexsym,graphicx} +\usepackage{newtxtext,newtxmath} % Times for PR +\usepackage[dvipsnames]{xcolor} +\usepackage[ + colorlinks=true, + urlcolor=MidnightBlue, + citecolor=MidnightBlue, + filecolor=MidnightBlue, + linkcolor=MidnightBlue +]{hyperref} % ref and cite links with pretty colors +\usepackage{anyfontsize} + +\begin{document} + +\title{ + Unveiling the complexity of hierarchical energy landscapes +} + +\author{Jaron Kent-Dobias} +\author{Jorge Kurchan} +\affiliation{Laboratoire de Physique de l'Ecole Normale Supérieure, Paris, France} + +\begin{abstract} + Complexity is a measure of the number of stationary points in complex + landscapes. We derive a general solution for the complexity of mean-field + complex landscapes. It incorporates Parisi's solution for the ground state, + as it should. Using this solution, we count the stationary points of two + models: one with multi-step replica symmetry breaking, and one with full + replica symmetry breaking. These examples demonstrate the consistency of the + solution and reveal that the signature of replica symmetry breaking at high + energy densities is found in high-index saddles, not minima. +\end{abstract} + +\maketitle + +The functions used to describe the energies, costs, and fitnesses of disordered +systems in physics, computer science, and biology are typically \emph{complex}, +meaning that they have a number of minima that grows exponentially with the +size of the system \cite{Maillard_2020_Landscape, Ros_2019_Complex, +Altieri_2021_Properties}. Though they are often called `rough landscapes' to +evoke the intuitive image of many minima in something like a mountain range, +the metaphor to topographical landscapes is strained by the reality that these +complex landscapes also exist in very high dimensions: think of the dimensions +of phase space for $N$ particles, or the number of parameters in a neural +network. + +The \emph{complexity} of a function is the average of the logarithm of the +number of its minima, maxima, and saddle points (collectively stationary +points), under conditions fixing the value of the energy or the index of the +stationary point +\cite{Bray_1980_Metastable}. +Since in complex landscapes this +number grows exponentially with system size, their complexity is an extensive +quantity. Understanding the complexity offers an understanding about the +geometry and topology of the landscape, which can provide insight into +dynamical behavior. + +When complex systems are fully connected, i.e., each degree of freedom +interacts directly with every other, they are often described by a hierarchical +structure of the type first proposed by Parisi, the \emph{replica symmetry +breaking} (RSB) \cite{Parisi_1979_Infinite}. This family of structures is rich, spanning uniform +\emph{replica symmetry} (RS), an integer $k$ levels of hierarchical nested +structure ($k$RSB), a full continuum of nested structure (full RSB or FRSB), +and arbitrary combinations thereof. Though these rich structures are understood +in the equilibrium properties of fully connected models, the complexity has +only been computed in RS cases. + +In this paper and its longer companion, we share the first results for the +complexity with nontrivial hierarchy \cite{Kent-Dobias_2022_How}. Using a +general form for the solution detailed in a companion article, we describe the +structure of landscapes with a 1RSB complexity and a full RSB complexity +\footnote{The Thouless--Anderson--Palmer (TAP) complexity is the complexity of + a kind of mean-field free energy. Because of some deep thermodynamic + relationships 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.}. + +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 $N-1$ sphere +$S^{N-1}=\{\mathbf s\mid\|\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 complexity of the $p$-spin models has been extensively studied by +physicists and mathematicians. Among physicists, the bulk of work has been on + the so-called `TAP' complexity, +which counts minima in the mean-field Thouless--Anderson--Palmer () free energy \cite{Rieger_1992_The, +Crisanti_1995_Thouless-Anderson-Palmer, Cavagna_1997_An, +Cavagna_1997_Structure, Cavagna_1998_Stationary, Cavagna_2005_Cavity, +Giardina_2005_Supersymmetry}. The landscape complexity has been proven for pure +and mixed models without RSB \cite{Auffinger_2012_Random, +Auffinger_2013_Complexity, BenArous_2019_Geometry}. The mixed models been +treated without RSB \cite{Folena_2020_Rethinking}. And the methods of +complexity have been used to study many geometric properties of the pure +models, from the relative position of stationary points to one another to shape +and prevalence of instantons \cite{Ros_2019_Complexity, Ros_2021_Dynamical}. + +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}. In fact, defined this way the mixed spherical model encompasses all isotropic Gaussian fields on the sphere. + +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 +\cite{Kac_1943_On, Rice_1939_The}. The count is given by +\begin{equation} + \begin{aligned} + \mathcal N(E, \mu) + &=\int_{\mathbb R^N}d\boldsymbol\xi\,e^{-\frac12\|\boldsymbol\xi\|^2/\sigma^2}\int_{S^{N-1}}d\mathbf s\, \delta\big(\nabla H(\mathbf s)-\boldsymbol\xi\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 additional `noise' field $\boldsymbol\xi$ +helps regularize the $\delta$-functions for the energy and stability at finite +$N$, and will be convenient for defining the order parameter matrices later. The complexity is then +\begin{equation} \label{eq:complexity} + \Sigma(E,\mu)=\lim_{N\to\infty}\lim_{\sigma\to0}\frac1N\overline{\log\mathcal N(E, \mu}). +\end{equation} +Most of the difficulty of this calculation resides in the logarithm in this +formula. + +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_\mathrm m=\sqrt{4f''(1)}$ centered at $\mu$. When +$\mu>\mu_\mathrm m$, stationary points are minima whose sloppiest eigenvalue is +$\mu-\mu_\mathrm m$. When $\mu=\mu_\mathrm m$, the stationary points are marginal minima with +flat directions. When $\mu<\mu_\mathrm 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$ \cite{Cugliandolo_1993_Analytical}. 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_\mathrm 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' \cite{Cugliandolo_1993_Analytical} energy $E_\mathrm{th}$ corresponds to the +average energy at the dynamic transition temperature, and the asymptotic energy +reached by slow aging dynamics. + +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}. There is no longer a +sharp topological transition. + +In the pure models, $E_\mathrm{th}$ also corresponds to 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. + +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. The average of the factor +including the determinant and the factors involving $\delta$-functions can be +averaged over the disorder separately \cite{Bray_2007_Statistics}. The result +can be written +\begin{equation} + \Sigma(E,\mu)=\lim_{N\to\infty}\lim_{n\to0}\frac1N\frac{\partial}{\partial n} + \int_{\mathrm M_n(\mathbb R)} dQ\,dR\,dD\,e^{N\mathcal S(Q,R,D\mid E,\mu)}, +\end{equation} +where the effective action $\mathcal S$ is a function of three matrices indexed +by the $n$ replicas: +\begin{equation} + \begin{aligned} + &Q_{ab}=\frac{\mathbf s_a\cdot\mathbf s_b}N + \hspace{4em} + R_{ab}=\frac{\boldsymbol\xi_a\cdot\mathbf s_b}{N\sigma^2} + \\ + &D_{ab}=\frac1{N\sigma^4}\left(\sigma^2\delta_{ab}-\boldsymbol\xi_a\cdot\boldsymbol\xi_b\right). + \end{aligned} +\end{equation} +The matrix $Q$ is a clear analogue of the usual overlap matrix of the +equilibrium case. The matrices $R$ and $D$ have interpretations as response +functions: $R$ is related to the typical displacement of stationary points by +perturbations to the potential, and $D$ is related to the change in the +complexity caused by the same perturbations. The general expression for the +complexity as a function of these matrices is also found in +\cite{Folena_2020_Rethinking}. + +The complexity is found by the saddle point method, extremizing $\mathcal S$ +with respect to $Q$, $R$, and $D$ and replacing the integral with its integrand +evaluated at the extremum. We make the \emph{ansatz} that all three matrices have +a hierarchical structure, and moreover that they share the same hierarchical +structure. This means that the size of the blocks of equal value of each is the +same, though the values inside these blocks will vary from matrix to matrix. +This form can be shown to exactly reproduce the ground state energy predicted +by the equilibrium solution, a key consistency check. + +Along one line in the energy--stability plane the solution takes a simple form: +the matrices $R$ and $D$ corresponding to responses are diagonal, leaving +only the overlap matrix $Q$ with nontrivial off-diagonal entries. This +simplification makes the solution along this line analytically tractable even +for FRSB. The simplification is related to the presence of an approximate +supersymmetry in the Kac--Rice formula, studied in the past in the context of +the TAP free energy \cite{Annibale_2003_Supersymmetric, Annibale_2003_The, +Annibale_2004_Coexistence}. This line of `supersymmetric' solutions terminates +at the ground state, and describes the most numerous types of stable minima. + +Using this solution, one finds a correspondence between properties of the +overlap matrix $Q$ at the ground state energy, where the complexity vanishes, +and the overlap matrix in the equilibrium problem in the limit of zero +temperature. The saddle point parameters of the two problems are related +exactly. In the case where the vicinity of the equilibrium ground state is +described by a $k$RSB solution, the complexity at the ground state is +$(k-1)$RSB. This can be intuitively understood by considering the difference +between measuring overlaps between equilibrium \emph{states} and stationary +\emph{points}. For states, the finest level of the hierarchical description +gives the typical overlap between two points drawn from the same state, which +has some distribution about the ground state at nonzero temperature. For +points, this finest level does not exist. + +In general, solving the saddle-point equations for the parameters of the three +replica matrices is challenging. Unlike the equilibrium case, the solution is +not extremal, and so minimization methods cannot be used. However, the line of +simple `supersymmetric' solutions offers a convenient foothold: starting from +one of these solutions, the parameters $E$ and $\mu$ can be slowly varied to +find the complexity everywhere. This is how the data in what follows was produced. + +\begin{figure} + \centering + \hspace{-1em} + \includegraphics[width=\columnwidth]{figs/316_complexity_contour_1_letter.pdf} + \includegraphics[width=\columnwidth]{figs/316_detail_letter_legend.pdf} + + \caption{ + Complexity of the $3+16$ model in the energy $E$ and stability $\mu$ + plane. Solid lines show the prediction of 1RSB complexity, while dashed + lines show the prediction of RS complexity. Below the yellow marginal line + the complexity counts saddles of increasing index as $\mu$ decreases. Above + the yellow marginal line the complexity counts minima of increasing + stability as $\mu$ increases. + } \label{fig:2rsb.contour} +\end{figure} + +\begin{figure} + \centering + \includegraphics[width=\columnwidth]{figs/316_detail_letter.pdf} + \includegraphics[width=\columnwidth]{figs/316_detail_letter_legend.pdf} + + \caption{ + Detail of the `phases' of the $3+16$ model complexity as a function of + energy and stability. Solid lines show the prediction of 1RSB complexity, while dashed + lines show the prediction of RS complexity. Above the yellow marginal stability line the + complexity counts saddles of fixed index, while below that line it counts + minima of fixed stability. The shaded red region shows places where the + complexity is described by the 1RSB solution, while the shaded gray region + shows places where the complexity is described by the RS solution. In white + regions the complexity is zero. Several interesting energies are marked + with vertical black lines: the traditional `threshold' $E_\mathrm{th}$ + where minima become most numerous, the algorithmic threshold + $E_\mathrm{alg}$ that bounds the performance of smooth algorithms, and the + average energies at the $2$RSB and $1$RSB equilibrium transitions $\langle + E\rangle_2$ and $\langle E\rangle_1$, respectively. Though the figure is + suggestive, $E_\mathrm{alg}$ lies at slightly lower energy than the termination of the RS + -- 1RSB transition line. + } \label{fig:2rsb.phases} +\end{figure} + +For the first example, we study a model whose complexity has the simplest +replica symmetry breaking scheme, 1RSB. 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 the complexity. 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$. The typical equilibrium energies at these phase +transitions are listed in Table~\ref{tab:energies}. + +\begin{table} + \begin{tabular}{l|cc} + & $3+16$ & $2+4$ \\\hline\hline + $\langle E\rangle_\infty$ &---& $-0.531\,25\hphantom{1\,111\dots}$ \\ + $\hphantom{\langle}E_\mathrm{max}$ & $-0.886\,029\,051\dots$ & $-1.039\,701\,412\dots$\\ + $\langle E\rangle_1$ & $-0.906\,391\,055\dots$ & ---\\ + $\langle E\rangle_2$ & $-1.195\,531\,881\dots$ & ---\\ + $\hphantom{\langle}E_\mathrm{dom}$ & $-1.273\,886\,852\dots$ & $-1.056\,6\hphantom{11\,111\dots}$\\ + $\hphantom{\langle}E_\mathrm{alg}$ & $-1.275\,140\,128\dots$ & $-1.059\,384\,319\ldots$\\ + $\hphantom{\langle}E_\mathrm{th}$ & $-1.287\,575\,114\dots$ & $-1.059\,384\,319\ldots$\\ + $\hphantom{\langle}E_\mathrm{m}$ & $-1.287\,605\,527\ldots$ & $-1.059\,384\,319\ldots$ \\ + $\hphantom{\langle}E_0$ & $-1.287\,605\,530\ldots$ & $-1.059\,384\,319\ldots$\\\hline + \end{tabular} + \caption{ + Landmark energies of the equilibrium and complexity problems for the two + models studied. $\langle E\rangle_1$, $\langle E\rangle_2$ and $\langle + E\rangle_\infty$ are the average energies in equilibrium at the RS--1RSB, + 1RSB--2RSB, and RS--FRSB transitions, respectively. $E_\mathrm{max}$ is the + highest energy at which any stationary points are described by a RSB + complexity. $E_\mathrm{dom}$ is the energy at which dominant stationary + points have an RSB complexity. $E_\mathrm{alg}$ is the algorithmic + threshold below which smooth algorithms cannot go. $E_\mathrm{th}$ is the + traditional threshold energy, defined by the energy at which marginal + minima become most common. $E_\mathrm m$ is the lowest energy at which + saddles or marginal minima are found. $E_0$ is the ground state energy. + } \label{tab:energies} +\end{table} + +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, shown in Fig.~\ref{fig:2rsb.contour}. It predicts the same ground state as equilibrium and with a +ground state stability $\mu_0=6.480\,764\ldots>\mu_\mathrm m$. It predicts that +the complexity of marginal minima (and therefore all saddles) vanishes at +$E_\mathrm m$, which is very slightly greater than $E_0$. Saddles become +dominant over minima at a higher energy $E_\mathrm{th}$. The 1RSB complexity +transitions to a RS description for dominant stationary points at an energy +$E_\mathrm{dom}$. The highest energy for which the 1RSB description exists is +$E_\mathrm{max}$. The numeric values for all these energies are listed in +Table~\ref{tab:energies}. + +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_letter.pdf} + \includegraphics[width=\columnwidth]{figs/24_detail_letter_legend.pdf} + \caption{ + `Phases' of the complexity for the $2+4$ model in the energy $E$ and + stability $\mu$ plane. Solid lines show the prediction of 1RSB complexity, + while dashed lines show the prediction of RS complexity. The region shaded + gray shows where the RS solution is correct, while the region shaded red + shows that where the FRSB solution is correct. The white region shows where + the complexity is zero. + } \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 $E_0=E_\mathrm{alg}=E_\mathrm{th}=E_\mathrm m$. +In the equilibrium solution, the transition temperature from RS to FRSB is $\beta_\infty=1$, with corresponding average energy $\langle E\rangle_\infty$, also in Table~\ref{tab:energies}. + +Fig.~\ref{fig:frsb.phases} shows the regions of complexity for the $2+4$ model, +computed using finite-$k$ RSB approximations. Notably, the phase boundary +predicted by a perturbative expansion correctly predicts where 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. + +We have used our solution for mean-field complexity to explore how hierarchical +RSB in equilibrium corresponds to analogous hierarchical structure in the +energy landscape. In the examples we studied, a relative minority of energy +minima are distributed in a nontrivial way, corresponding to the lowest energy +densities. On the other hand, very high-index saddles begin exhibit RSB at much +higher energy densities, on the order of the energy densities associated with +RSB transitions in equilibrium. More wore is necessary to explore this +connection, as well as whether a purely \emph{geometric} explanation can be +made for the algorithmic threshold. Applying this method to the most realistic +RSB scenario for structural glasses, the so-called 1FRSB which has features of +both 1RSB and FRSB, might yield insights about signatures that should be +present in the landscape. + +\paragraph{Acknowledgements} +The authors would like to thank Valentina Ros for helpful discussions. + +\paragraph{Funding information} +JK-D and JK are supported by the Simons Foundation Grant No.~454943. + +\bibliography{frsb_kac-rice} + +\end{document} |