From 5cdb3e644a0526c3a38f1f20df14bbf54a06afa0 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Wed, 14 Sep 2022 16:28:39 +0200 Subject: Added draft appeal letter. --- appeal.tex | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) create mode 100644 appeal.tex diff --git a/appeal.tex b/appeal.tex new file mode 100644 index 0000000..dce7fee --- /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, no correct calculation had been +made for the complexity of systems without a so-called replica symmetric +solution, which represent an small minority of systems. 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} -- cgit v1.2.3-70-g09d2 From 33d89f6ec26a545df9db276914904cacfd64c3fc Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Thu, 15 Sep 2022 13:59:20 +0200 Subject: Edited appeal letter. --- appeal.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/appeal.tex b/appeal.tex index dce7fee..7ae78f4 100644 --- a/appeal.tex +++ b/appeal.tex @@ -43,10 +43,10 @@ hierarchical landscapes: A ‘full’ solution to mean-field complexity}, which rejected without being sent to referees. The problem of characterizing the geometry of complex energy and cost -landscapes is long-standing. Until this work, no correct calculation had been -made for the complexity of systems without a so-called replica symmetric -solution, which represent an small minority of systems. We show explicitly how -such calculations can be made for the vast majority of cases. +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 -- cgit v1.2.3-70-g09d2 From 07dbb34e714ace184f32cb62c5c484daf053bd48 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Tue, 27 Sep 2022 13:22:48 +0200 Subject: Start of letter version. --- frsb_kac-rice_letter.tex | 120 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 120 insertions(+) create mode 100644 frsb_kac-rice_letter.tex diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex new file mode 100644 index 0000000..ba54e06 --- /dev/null +++ b/frsb_kac-rice_letter.tex @@ -0,0 +1,120 @@ + +\documentclass[reprint,aps,prl,longbibliography]{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{ + Unvieling the complexity of heirarchical energy landscapes +} + +\author{Jaron Kent-Dobias} +\author{Jorge Kurchan} +\affiliation{Laboratoire de Physique de l'Ecole Normale Supérieure, Paris, France} + +\begin{abstract} + We derive the general solution for counting the stationary points 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. +\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. 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 logarithm of the average number of +its minima, maxima, and saddle points (collectively stationary points), under +conditions like the value of the energy or the index of the stationary point. +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). 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 we share the first results for the complexity with nontrivial +hierarchy. Using a general form for the solution, we detail the structure of +landscapes with a 1RSB complexity and a full RSB complexity. + +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. + +\cite{Albert_2021_Searching} + +\begin{figure} + \centering + \includegraphics[width=\columnwidth]{figs/316_detail.pdf} + + \caption{ + Detail of the `phases' of the $3+16$ model complexity as a function of + energy and stability. 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} + +\begin{figure} + \centering + \includegraphics[width=\columnwidth]{figs/24_phases.pdf} + \caption{ + `Phases' of the complexity for the $2+4$ model in the energy $E$ and + stability $\mu^*$ plane. 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} + + +\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} -- cgit v1.2.3-70-g09d2 From d451019c13e19218fffe0605ca82f77e9b63aeb3 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Tue, 27 Sep 2022 13:23:30 +0200 Subject: Updated .gitignore. --- .gitignore | 1 + 1 file changed, 1 insertion(+) diff --git a/.gitignore b/.gitignore index faacc6a..9a36fc7 100644 --- a/.gitignore +++ b/.gitignore @@ -11,3 +11,4 @@ *.run.xml *.synctex(busy) *.toc +*Notes.bib -- cgit v1.2.3-70-g09d2 From f3144b0bc033de918785b40e083f48c8451d4a7d Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Tue, 27 Sep 2022 16:54:54 +0200 Subject: More work on the letter version. --- frsb_kac-rice.bib | 6 +- frsb_kac-rice_letter.tex | 181 ++++++++++++++++++++++++++++++++++++++++++++++- 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. -- cgit v1.2.3-70-g09d2 From 6dbe5a229823612fa77fd54f15f505a82cf3c12e Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Tue, 27 Sep 2022 17:02:14 +0200 Subject: Changed rest of arxiv papers to be compatible with revtex. --- frsb_kac-rice.bib | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) diff --git a/frsb_kac-rice.bib b/frsb_kac-rice.bib index 0412ab7..d8927bc 100644 --- a/frsb_kac-rice.bib +++ b/frsb_kac-rice.bib @@ -404,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 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, @@ -557,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}, 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, @@ -596,16 +600,18 @@ stochastic localization}, doi = {10.1103/physrevresearch.3.023064} } -@article{Kent-Dobias_2022_Analytic, +@unpublished{Kent-Dobias_2022_Analytic, author = {Kent-Dobias, Jaron and Kurchan, Jorge}, title = {Analytic continuation over complex landscapes}, year = {2022}, month = {4}, url = {http://arxiv.org/abs/2204.06072v1}, + archiveprefix = {arXiv}, date = {2022-04-12T20:24:54Z}, eprint = {2204.06072v1}, eprintclass = {cond-mat.stat-mech}, - eprinttype = {arxiv} + eprinttype = {arxiv}, + primaryclass = {cond-mat.stat-mech} } @article{Li_2021_Determining, -- cgit v1.2.3-70-g09d2 From 36947d8407c36560e991d4243001d08cddbee829 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Thu, 20 Oct 2022 13:59:49 +0200 Subject: Lots of writing. --- frsb_kac-rice_letter.tex | 76 ++++++++++++++++++++++++++++++++++-------------- 1 file changed, 54 insertions(+), 22 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index d3369ac..801dc8e 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -45,13 +45,13 @@ 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 logarithm of the average number of -its minima, maxima, and saddle points (collectively stationary points), under -conditions like the value of the energy or the index of the stationary point. -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. +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 like the value of the energy or the index of the +stationary point. 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 @@ -65,20 +65,20 @@ only been computed in RS cases. In this paper we share the first results for the complexity with nontrivial hierarchy. Using a general form for the solution, we detail the structure of -landscapes with a 1RSB complexity and a full RSB complexity. - -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. +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 sphere -$\|\mathbf s\|^2=N$. The coupling coefficients $J$ are taken at random, with +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 @@ -136,7 +136,7 @@ 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 +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 @@ -148,11 +148,42 @@ 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}. +and the asymptotic dynamics \cite{Folena_2020_Rethinking}. There is no longer a +sharp topological transition. 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. +$\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 as a function of three matrices indexed by the replicas: one +which is a clear analogue of the usual overlap matrix of the equilibrium case, +and two which can be related to the response of stationary points to +perturbations of the potential. The general expression for the complexity as a +function of these matrices is also found in \cite{Folena_2020_Rethinking}. + +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 two hierarchical matrices corresponding to responses are diagonal, leaving +only the overlap matrix 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. This line of `supersymmetric' solutions terminates at the +ground state, and describes the most numerous types of stable minima. + +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 @@ -176,9 +207,10 @@ $\delta$-functions are written in a Fourier basis. } \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 +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. For this example, we take \begin{equation} f(q)=\frac12\left(q^3+\frac1{16}q^{16}\right) \end{equation} -- cgit v1.2.3-70-g09d2 From 7fc64027fba299f53ac8d037588391c13263f95c Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Thu, 20 Oct 2022 16:20:40 +0200 Subject: Work on letter writing, and addition of new figures sized for the letter. --- figs/24_phases_letter.pdf | Bin 0 -> 45067 bytes figs/316_complexity_contour_1_letter.pdf | Bin 0 -> 742706 bytes figs/316_detail_letter.pdf | Bin 0 -> 75758 bytes figs/316_detail_letter_legend.pdf | Bin 0 -> 5477 bytes frsb_kac-rice_letter.tex | 41 +++++++++++++++---------------- 5 files changed, 20 insertions(+), 21 deletions(-) create mode 100644 figs/24_phases_letter.pdf create mode 100644 figs/316_complexity_contour_1_letter.pdf create mode 100644 figs/316_detail_letter.pdf create mode 100644 figs/316_detail_letter_legend.pdf diff --git a/figs/24_phases_letter.pdf b/figs/24_phases_letter.pdf new file mode 100644 index 0000000..366f49e Binary files /dev/null and b/figs/24_phases_letter.pdf differ diff --git a/figs/316_complexity_contour_1_letter.pdf b/figs/316_complexity_contour_1_letter.pdf new file mode 100644 index 0000000..b5aa80d Binary files /dev/null and b/figs/316_complexity_contour_1_letter.pdf differ diff --git a/figs/316_detail_letter.pdf b/figs/316_detail_letter.pdf new file mode 100644 index 0000000..4c33457 Binary files /dev/null and b/figs/316_detail_letter.pdf differ diff --git a/figs/316_detail_letter_legend.pdf b/figs/316_detail_letter_legend.pdf new file mode 100644 index 0000000..756a2c7 Binary files /dev/null and b/figs/316_detail_letter_legend.pdf differ diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 801dc8e..5917167 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -1,5 +1,5 @@ -\documentclass[reprint,aps,prl,longbibliography]{revtex4-2} +\documentclass[reprint,aps,prl,longbibliography,floatfix]{revtex4-2} \usepackage[utf8]{inputenc} % why not type "Bézout" with unicode? \usepackage[T1]{fontenc} % vector fonts plz @@ -187,7 +187,22 @@ find the complexity everywhere. This is how the data in what follows was produce \begin{figure} \centering - \includegraphics[width=\columnwidth]{figs/316_detail.pdf} + \hspace{-1em} + \includegraphics[width=\columnwidth]{figs/316_complexity_contour_1_letter.pdf} + + \caption{ + Complexity of the $3+16$ model in the energy $E$ and stability $\mu^*$ + plane. The right shows a detail of the left. 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 @@ -275,7 +290,7 @@ model stall in a place where minima are exponentially subdominant. \begin{figure} \centering - \includegraphics[width=\columnwidth]{figs/24_phases.pdf} + \includegraphics[width=\columnwidth]{figs/24_phases_letter.pdf} \caption{ `Phases' of the complexity for the $2+4$ model in the energy $E$ and stability $\mu^*$ plane. The region shaded gray shows where the RS solution @@ -294,25 +309,9 @@ also studied before in equilibrium \cite{Crisanti_2004_Spherical, Crisanti_2006_ \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} +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} +this plane. Notably, the phase boundary predicted by a perturbative expansion 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 -- cgit v1.2.3-70-g09d2 From 85b28e181dee40cf0940a322e6f9edbff13f401e Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Thu, 20 Oct 2022 16:46:00 +0200 Subject: Spelling in title. --- frsb_kac-rice_letter.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 5917167..ebbadf3 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -18,7 +18,7 @@ \begin{document} \title{ - Unvieling the complexity of heirarchical energy landscapes + Unveiling the complexity of hierarchical energy landscapes } \author{Jaron Kent-Dobias} -- cgit v1.2.3-70-g09d2 From 87510f78bef9224f38f4588eccecd0d0247aa73d Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 15:32:48 +0200 Subject: Added a table for interesting energy values. --- frsb_kac-rice_letter.tex | 45 +++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 43 insertions(+), 2 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index ebbadf3..1d8785c 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -119,8 +119,10 @@ is given by 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}) + \Sigma(E,\mu)=\lim_{N\to\infty}\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 @@ -178,6 +180,19 @@ supersymmetry in the Kac--Rice formula, studied in the past in the context of the TAP free energy. 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 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 @@ -225,7 +240,7 @@ find the complexity everywhere. This is how the data in what follows was produce 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. For this example, we take +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} @@ -251,6 +266,32 @@ 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$. +\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_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_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 -- cgit v1.2.3-70-g09d2 From a242819dab57a8fbfda184e0f6e448b6e6375717 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 15:47:42 +0200 Subject: Rearranged some exposition about the algorithmic threshold. --- frsb_kac-rice_letter.tex | 37 ++++++++++++++++++------------------- 1 file changed, 18 insertions(+), 19 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 1d8785c..c3628f9 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -145,7 +145,22 @@ 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}$. +dynamics. + +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. 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 @@ -247,24 +262,8 @@ This should correspond to 1RSB in the complexity. We take 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$. +$\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} -- cgit v1.2.3-70-g09d2 From 0e641b3cf916deefef4752d87a860104ef783816 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 15:55:07 +0200 Subject: More rearrangement. --- frsb_kac-rice_letter.tex | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index c3628f9..b4ba867 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -147,6 +147,12 @@ threshold 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, @@ -162,12 +168,6 @@ 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. -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. - 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 -- cgit v1.2.3-70-g09d2 From d28e08b7e4637b5a44434f2909f6213818a3834b Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 15:55:17 +0200 Subject: No mu^* in this version. --- frsb_kac-rice_letter.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index b4ba867..f216171 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -221,11 +221,11 @@ find the complexity everywhere. This is how the data in what follows was produce \includegraphics[width=\columnwidth]{figs/316_complexity_contour_1_letter.pdf} \caption{ - Complexity of the $3+16$ model in the energy $E$ and stability $\mu^*$ + Complexity of the $3+16$ model in the energy $E$ and stability $\mu$ plane. The right shows a detail of the left. Below the yellow marginal line - the complexity counts saddles of increasing index as $\mu^*$ decreases. + 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. + stability as $\mu$ increases. } \label{fig:2rsb.contour} \end{figure} @@ -333,7 +333,7 @@ model stall in a place where minima are exponentially subdominant. \includegraphics[width=\columnwidth]{figs/24_phases_letter.pdf} \caption{ `Phases' of the complexity for the $2+4$ model in the energy $E$ and - stability $\mu^*$ plane. The region shaded gray shows where the RS solution + stability $\mu$ plane. 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} -- cgit v1.2.3-70-g09d2 From 780f33ccb345052b938551776c4965fc0615fc2d Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 16:40:26 +0200 Subject: More writing. --- frsb_kac-rice.bib | 70 +++++++++++++++++++++++++++++------------------- frsb_kac-rice_letter.tex | 69 ++++++++++++++++++++++++++++++----------------- 2 files changed, 87 insertions(+), 52 deletions(-) diff --git a/frsb_kac-rice.bib b/frsb_kac-rice.bib index d8927bc..3e8acb7 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}, @@ -406,7 +406,7 @@ @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}, @@ -436,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} } @@ -463,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}, @@ -477,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}, @@ -490,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}, @@ -512,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}, @@ -547,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}, @@ -561,7 +561,7 @@ stochastic localization}, @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}, @@ -614,9 +614,25 @@ stochastic localization}, primaryclass = {cond-mat.stat-mech} } +@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}, + 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}, @@ -771,7 +787,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}, @@ -827,7 +843,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}, @@ -855,7 +871,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 index f216171..f539fbc 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -26,11 +26,14 @@ \affiliation{Laboratoire de Physique de l'Ecole Normale Supérieure, Paris, France} \begin{abstract} - We derive the general solution for counting the stationary points 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. + 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 @@ -64,14 +67,14 @@ in the equilibrium properties of fully connected models, the complexity has only been computed in RS cases. In this paper we share the first results for the complexity with nontrivial -hierarchy. Using a general form for the solution, we detail 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.}. +hierarchy. 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.} \cite{Kent-Dobias_2022_How}. We study the mixed $p$-spin spherical models, with Hamiltonian \begin{equation} \label{eq:hamiltonian} @@ -275,6 +278,7 @@ transitions are listed in Table~\ref{tab:energies}. $\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{ @@ -287,7 +291,8 @@ transitions are listed in Table~\ref{tab:energies}. 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_0$ is the ground state energy. + 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} @@ -295,13 +300,15 @@ 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$ +these problems, predicting 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 @@ -349,16 +356,28 @@ also studied before in equilibrium \cite{Crisanti_2004_Spherical, Crisanti_2006_ \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$. -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 a perturbative expansion -correctly predicts where all of the finite $k$RSB approximations terminate. +Fig.~\ref{fig:frsb.phases} shows the regions of complexity for the $2+4$ model. +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. -- cgit v1.2.3-70-g09d2 From 40f81655eaaa4264b6feba819f6d904ec6ea0b9f Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 17:00:32 +0200 Subject: Some writing and lots of references. --- frsb_kac-rice_letter.tex | 56 ++++++++++++++++++++++++++++++++---------------- 1 file changed, 37 insertions(+), 19 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index f539fbc..b3c288a 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -41,9 +41,10 @@ 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. 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 +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. @@ -51,43 +52,60 @@ 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 like the value of the energy or the index of the -stationary point. 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. +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). This family of structures is rich, spanning uniform +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 we share the first results for the complexity with nontrivial -hierarchy. 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.} \cite{Kent-Dobias_2022_How}. +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 +$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 Thouless--Anderson--Palmer (TAP) complexity for the pure models, +which counts minima in a kind of mean-field 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 in specific cases, again without RSB \cite{Folena_2020_Rethinking, +Ros_2019_Complex}. 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 @@ -101,7 +119,7 @@ where $f$ is defined by the series 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 `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 -- cgit v1.2.3-70-g09d2 From 738d0a77ae244cce8e5f9b6faaba14a277bda330 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 17:03:57 +0200 Subject: More citations. --- frsb_kac-rice_letter.tex | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index b3c288a..21807cb 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -128,8 +128,8 @@ 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 +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) @@ -156,17 +156,17 @@ 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. +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_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. 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 -- cgit v1.2.3-70-g09d2 From e9332328dd3f154d985cf7bd153d9fdd2c9a4d69 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 21 Oct 2022 17:32:09 +0200 Subject: Added legend and some small changes. --- figs/24_detail_letter_legend.pdf | Bin 0 -> 5443 bytes frsb_kac-rice_letter.tex | 75 ++++++++++++++++++++------------------- 2 files changed, 39 insertions(+), 36 deletions(-) create mode 100644 figs/24_detail_letter_legend.pdf diff --git a/figs/24_detail_letter_legend.pdf b/figs/24_detail_letter_legend.pdf new file mode 100644 index 0000000..ca32ca0 Binary files /dev/null and b/figs/24_detail_letter_legend.pdf differ diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 21807cb..7fc71a9 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -51,7 +51,7 @@ 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 like the value of the energy or the index of the +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 @@ -100,21 +100,20 @@ 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 in specific cases, again without RSB \cite{Folena_2020_Rethinking, -Ros_2019_Complex}. 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}. +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) + \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 + 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 @@ -149,17 +148,17 @@ 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 +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_m/p$, the +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 @@ -240,12 +239,14 @@ find the complexity everywhere. This is how the data in what follows was produce \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. The right shows a detail of the left. 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 + 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} @@ -257,7 +258,8 @@ find the complexity everywhere. This is how the data in what follows was produce \caption{ Detail of the `phases' of the $3+16$ model complexity as a function of - energy and stability. Above the yellow marginal stability line the + 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 @@ -318,7 +320,7 @@ 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 +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 @@ -356,32 +358,33 @@ 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. 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. + 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 -\begin{equation} - E_0=E_\mathrm{alg}=E_\mathrm{th}=-\int_0^1dq\,\sqrt{f''(q)}=-1.059\,384\,319\ldots + f(q)=\frac12\left(q^2+\frac1{16}q^4\right), \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$. - -Fig.~\ref{fig:frsb.phases} shows the regions of complexity for the $2+4$ model. -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. +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 -- cgit v1.2.3-70-g09d2 From b834440d905adf50d405c1203195d543ef7225d6 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Sat, 22 Oct 2022 15:06:00 +0200 Subject: Downgraded revtex for overleaf. --- frsb_kac-rice_letter.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 7fc71a9..f7906ee 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -1,5 +1,5 @@ -\documentclass[reprint,aps,prl,longbibliography,floatfix]{revtex4-2} +\documentclass[reprint,aps,prl,longbibliography,floatfix]{revtex4-1} \usepackage[utf8]{inputenc} % why not type "Bézout" with unicode? \usepackage[T1]{fontenc} % vector fonts plz -- cgit v1.2.3-70-g09d2 From 2a249b308db46cb9da2d19e9edbd80508a6eaebf Mon Sep 17 00:00:00 2001 From: "kurchan.jorge" Date: Sat, 22 Oct 2022 12:53:10 +0000 Subject: Update on Overleaf. --- frsb_kac-rice_letter.tex | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 7fc71a9..84d708d 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -52,7 +52,9 @@ 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 +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 -- cgit v1.2.3-70-g09d2 From 71001ad320a4241f552b866a7effa482108077bd Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Sat, 22 Oct 2022 13:09:19 +0000 Subject: Update on Overleaf. --- frsb_kac-rice_letter.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 115d94c..84d708d 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -1,5 +1,5 @@ -\documentclass[reprint,aps,prl,longbibliography,floatfix]{revtex4-1} +\documentclass[reprint,aps,prl,longbibliography,floatfix]{revtex4-2} \usepackage[utf8]{inputenc} % why not type "Bézout" with unicode? \usepackage[T1]{fontenc} % vector fonts plz -- cgit v1.2.3-70-g09d2 From 8d06423bf6291ccd11696b9012bc054c5eee963f Mon Sep 17 00:00:00 2001 From: "kurchan.jorge" Date: Mon, 24 Oct 2022 10:27:52 +0000 Subject: Update on Overleaf. --- frsb_kac-rice_letter.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 84d708d..63b7811 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -27,7 +27,7 @@ \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 + landscapes. We {\color{red} solve the long-standing problem of detremining the...} 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 @@ -95,8 +95,8 @@ 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 Thouless--Anderson--Palmer (TAP) complexity for the pure models, -which counts minima in a kind of mean-field free energy \cite{Rieger_1992_The, + 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 @@ -165,7 +165,7 @@ 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 +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. -- cgit v1.2.3-70-g09d2 From 6c0cd5488bc630a0fcf6a14629fd5f91f2706483 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Mon, 7 Nov 2022 14:22:31 +0100 Subject: Finishing up the letter. --- frsb_kac-rice.bib | 19 +++++++------- frsb_kac-rice_letter.tex | 65 ++++++++++++++++++++++++++++++++---------------- 2 files changed, 54 insertions(+), 30 deletions(-) diff --git a/frsb_kac-rice.bib b/frsb_kac-rice.bib index 3e8acb7..f8d4265 100644 --- a/frsb_kac-rice.bib +++ b/frsb_kac-rice.bib @@ -600,18 +600,19 @@ $T_g$: Experimental Evidence for the Gardner Transition in Structural Glasses?}, doi = {10.1103/physrevresearch.3.023064} } -@unpublished{Kent-Dobias_2022_Analytic, +@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}, - archiveprefix = {arXiv}, - date = {2022-04-12T20:24:54Z}, - eprint = {2204.06072v1}, - eprintclass = {cond-mat.stat-mech}, - eprinttype = {arxiv}, - primaryclass = {cond-mat.stat-mech} + 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, diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 63b7811..4fb22e7 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -27,7 +27,7 @@ \begin{abstract} Complexity is a measure of the number of stationary points in complex - landscapes. We {\color{red} solve the long-standing problem of detremining the...} derive a general solution for the complexity of mean-field + 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 @@ -134,14 +134,16 @@ stationary points using a $\delta$-function weighted by a Jacobian \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| \\ + &=\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 complexity is then +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}\frac1N\overline{\log\mathcal N(E, \mu}). + \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. @@ -195,30 +197,51 @@ 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 as a function of three matrices indexed by the replicas: one -which is a clear analogue of the usual overlap matrix of the equilibrium case, -and two which can be related to the response of stationary points to -perturbations of the potential. The general expression for the complexity as a -function of these matrices is also found in \cite{Folena_2020_Rethinking}. - -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. +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 two hierarchical matrices corresponding to responses are diagonal, leaving -only the overlap matrix with nontrivial off-diagonal entries. This +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. This line of `supersymmetric' solutions terminates at the -ground state, and describes the most numerous types of stable minima. +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 at the ground state energy, where the complexity vanishes, +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 -- cgit v1.2.3-70-g09d2