diff options
| -rw-r--r-- | marginal.bib | 42 | ||||
| -rw-r--r-- | marginal.tex | 105 |
2 files changed, 98 insertions, 49 deletions
diff --git a/marginal.bib b/marginal.bib index 45d26ae..9d7afbb 100644 --- a/marginal.bib +++ b/marginal.bib @@ -42,6 +42,21 @@ issn = {1083-6489} } +@article{Biroli_2013_Perspective, + author = {Biroli, Giulio and Garrahan, Juan P.}, + title = {Perspective: The glass transition}, + journal = {The Journal of Chemical Physics}, + publisher = {AIP Publishing}, + year = {2013}, + month = {March}, + number = {12}, + volume = {138}, + pages = {12A301}, + url = {http://dx.doi.org/10.1063/1.4795539}, + doi = {10.1063/1.4795539}, + issn = {1089-7690} +} + @article{Bray_2007_Statistics, author = {Bray, Alan J. and Dean, David S.}, title = {Statistics of Critical Points of {Gaussian} Fields on Large-Dimensional Spaces}, @@ -339,6 +354,20 @@ title = {Conditioning the complexity of random landscapes on marginal optima} } +@article{Krzakala_2007_Landscape, + author = {Krzakala, Florent and Kurchan, Jorge}, + title = {Landscape analysis of constraint satisfaction problems}, + journal = {Physical Review E}, + publisher = {American Physical Society (APS)}, + year = {2007}, + month = {8}, + number = {2}, + volume = {76}, + pages = {021122}, + url = {https://doi.org/10.1103%2Fphysreve.76.021122}, + doi = {10.1103/physreve.76.021122} +} + @article{Kurchan_1992_Supersymmetry, author = {Kurchan, J.}, title = {Supersymmetry in spin glass dynamics}, @@ -419,6 +448,19 @@ doi = {10.1103/physrevx.9.011003} } +@inbook{Ros_2023_High-dimensional, + author = {Ros, Valentina and Fyodorov, Yan V.}, + title = {The High-dimensional Landscape Paradigm: Spin-Glasses, and Beyond}, + publisher = {World Scientific}, + year = {2023}, + month = {August}, + pages = {95--114}, + url = {http://dx.doi.org/10.1142/9789811273926_0006}, + doi = {10.1142/9789811273926_0006}, + booktitle = {Spin Glass Theory and Far Beyond}, + isbn = {9789811273926} +} + @article{Subag_2020_Following, author = {Subag, Eliran}, title = {Following the Ground States of Full-{RSB} Spherical Spin Glasses}, diff --git a/marginal.tex b/marginal.tex index 59b92e0..c1b5a82 100644 --- a/marginal.tex +++ b/marginal.tex @@ -35,9 +35,9 @@ conditioning the statistics of stationary points in random landscapes on their marginality, and apply it in three isotropic settings with qualitatively different structure: in the spherical spin-glasses, where the - energy is Gaussian and its Hessian is GOE; in a multispherical spin glasses, - which are Gaussian but non-GOE; and in spherical random nonlinear sum of - squares, which is non-Gaussian. In these problems we are able to fully + energy is Gaussian and its Hessian is GOE; in multispherical spin glasses, + which are Gaussian but non-GOE; and in sums of squared spherical random + functions, which are non-Gaussian. In these problems we are able to fully characterize the distribution of marginal optima in the landscape, including when they are in the minority. \end{abstract} @@ -47,23 +47,23 @@ \section{Introduction} Systems with rugged landscapes are important across many disciplines, from the -physics to glasses and spin-glasses to statistical inference problems. The +physics to glasses and spin-glasses to statistical inference problems \cite{Ros_2023_High-dimensional}. The behavior of these systems is best understood when equilibrium or optimal solutions are studied and weighted averages can be taken statically over all possible configurations. However, such systems are also infamous for their tendency to defy equilibrium and optimal expectations in practice, due to the presence of dynamic transitions or crossovers that leave physical or -algorithmic dynamics stuck exploring only a subset of configurations. +algorithmic dynamics stuck exploring only a subset of configurations \cite{Biroli_2013_Perspective, Krzakala_2007_Landscape}. In mean-field settings, it was long thought that physical and many algorithmic dynamics would get stuck at a specific energy level, called the threshold energy. The threshold energy is the energy level at which level sets of the landscape transition from containing mostly saddle points to containing mostly -minima. At this threshold, the level set contains mostly \emph{marginal +minima. The level set associated with this threshold energy contains mostly \emph{marginal minima}, or minima that have a pseudogap in the spectrum of their Hessian. However, recent work found that the threshold energy is not important even for -simple gradient descent dynamics \cite{Folena_2020_Rethinking, Folena_2023_On}. +simple gradient descent dynamics \cite{Folena_2020_Rethinking, Folena_2023_On, ElAlaoui_2020_Algorithmic}. Depending on the initial condition of the system and the nature of the dynamics, the energy reached can be above or below the threshold energy, while in some models the threshold energy is completely inaccessible to any dynamics @@ -71,16 +71,16 @@ in some models the threshold energy is completely inaccessible to any dynamics energy level that many simple algorithms will reach, the results all share one commonality: the minima found are still marginal, despite being in the minority compared to stiff minima or saddle points. This ubiquity of behavior suggests -that the distribution of marginal minima can bound out-of-equilibrium dynamical +that the distribution of marginal minima can be used to bound out-of-equilibrium dynamical behavior. It is not straightforward to condition on the marginality of minima using the traditional methods for analyzing the distribution of minima in rugged landscapes. Using the method of a Legendre transformation of the Parisi parameter corresponding to a set of real replicas, one can force the result to -correspond with marginal minima by tuning the value of that parameter, but this -results in only the threshold energy and cannot characterize marginal minima at -energies where they are a minority \cite{Monasson_1995_Structural}. +correspond with marginal minima by tuning the value of that parameter \cite{Monasson_1995_Structural}. However, this +results in only a characterization of the threshold energy and cannot characterize marginal minima at +other energies where they are a minority. The alternative approach, used to great success in the spherical spin glasses, is to start by making a detailed understanding of the Hessian matrix at stationary @@ -111,12 +111,12 @@ pseudogap, and is therefore marginal. We demonstrate the method on the spherical spin glasses, where it is unnecessary but instructive, and on extensions of the spherical models with non-GOE Hessians where the technique is more useful. In a companion paper, we compare the marginal complexity with the performance -of gradient descent and approximate message passing \cite{Kent-Dobias_2024_Algorithm-independent}. +of gradient descent and approximate message passing algorithms \cite{Kent-Dobias_2024_Algorithm-independent}. -In Section \ref{sec:eigenvalue} we introduce the technique for conditioning on +An outline of this paper follows. In Section \ref{sec:eigenvalue} we introduce the technique for conditioning on the smallest eigenvalue and how to extend it to further condition on the presence of a pseudogap. We provide a simple but illustrative example using a -shifted GOE matrix. In Section \ref{sec:marginal.complexity} we apply this +GOE matrix with a shifted diagonal. In Section \ref{sec:marginal.complexity} we apply this technique to the problem of characterizing marginal minima in random landscapes. The following Section \ref{sec:examples} gives several examples of the marginal complexity applied to specific models of increasing difficulty. @@ -135,8 +135,9 @@ at the bottom on the spectrum. \subsection{The general method} -An arbitrary function $g$ of the minimum eigenvalue of a matrix $A$ can be -expressed as +Consider an $N\times N$ real matrix $A$. An arbitrary function $g$ of the +minimum eigenvalue of $A$ can be expressed using integrals over $\mathbf +s\in\mathbb R^N$ as \begin{equation} \label{eq:λmin} g(\lambda_\textrm{min}(A)) =\lim_{\beta\to\infty}\int @@ -163,15 +164,16 @@ of $A$. This produces &=g(\lambda_\mathrm{min}(A)) \end{aligned} \end{equation} +as desired. The first relation extends a technique first introduced in -\cite{Ikeda_2023_Bose-Einstein-like} and used in +\cite{Ikeda_2023_Bose-Einstein-like} and later used in \cite{Kent-Dobias_2024_Arrangement} in the context of random landscapes. A Boltzmann distribution is introduced over a spherical model whose Hamiltonian is quadratic with interaction matrix given by $A$. In the limit of zero temperature, the measure will concentrate on the ground states of the model, which correspond with the eigenspace of $A$ associated with its minimum eigenvalue $\lambda_\mathrm{min}$. The second -relation uses the fact that, once restricted to the sphere $\mathbf s^T\mathbf -s=N$ and the minimum eigenspace, $\mathbf s^TA\mathbf s=N\lambda_\mathrm{min}(A)$. +relation uses the fact that, once restricted to the sphere $\|\mathbf +s\|^2=N$ and the minimum eigenspace, $\mathbf s^TA\mathbf s=\mathbf s^T\mathbf s\lambda_\mathrm{min}(A)=N\lambda_\mathrm{min}(A)$. The relationship is formal, but we can make use of the fact that the integral expression with a Gibbs distribution can be manipulated with replica @@ -196,11 +198,12 @@ while for $\mu>2\sigma$ the minimum eigenvalue would need to be a large deviation from the typical spectrum and its likelihood will be exponentially suppressed with $N$. For $\mu<2\sigma$, the bulk of the typical spectrum contains zero and therefore a larger $N^2$ deviation, moving an extensive number of -eigenvalues, would be necessary. This final case cannot be quantified by this +eigenvalues, would be necessary \cite{Dean_2006_Large}. This final case cannot be quantified by this method, but instead the nonexistence of a large deviation linear in $N$ appears -as the emergence of an imaginary part in the function. +as the emergence of an imaginary part in the large deviation function. -As an example, we compute +To compute this large deviation function, we will employ the method outlined in +the previous subsection to calculate \begin{equation} \label{eq:large.dev} \begin{aligned} e^{NG_{\lambda^*}(\mu)} @@ -235,7 +238,8 @@ find \begin{aligned} &e^{NG_{\lambda^*}(\mu)} =\lim_{\beta\to\infty}\lim_{m\to0}\int d\hat\lambda\prod_{\alpha=1}^m\left[d\mathbf s^\alpha\,\delta(N-\|\mathbf s^\alpha\|^2)\right] \\ - &\hspace{10em}\exp\left\{N\left[\hat\lambda(\lambda^*-\mu)-m\beta\mu\right]+\frac{\sigma^2}{N}\left[\beta^2\sum_{\alpha\gamma}^m(\mathbf s^\alpha\cdot\mathbf s^\gamma)^2 + &\hspace{10em} + \times\exp\left\{N\left[\hat\lambda(\lambda^*-\mu)-m\beta\mu\right]+\frac{\sigma^2}{N}\left[\beta^2\sum_{\alpha\gamma}^m(\mathbf s^\alpha\cdot\mathbf s^\gamma)^2 +2\beta\hat\lambda\sum_\alpha^m(\mathbf s^\alpha\cdot\mathbf s^1)^2 +\hat\lambda^2N^2 \right]\right\} @@ -243,26 +247,26 @@ find \end{equation} \end{widetext} We make the Hubbard--Stratonovich transformation to the matrix field -$Q^{\alpha\beta}=\frac1N\mathbf s^\alpha\cdot\mathbf s^\beta$. This gives +$Q^{\alpha\beta}=\frac1N\mathbf s^\alpha\cdot\mathbf s^\beta$. This produces an integral expression of the form \begin{equation} e^{NG_{\lambda^*}(\mu)} =\lim_{\beta\to\infty}\lim_{m\to0}\int d\hat\lambda\,dQ\, e^{N\mathcal U_\mathrm{GOE}(\hat\lambda,Q\mid\beta,\lambda^*,\mu)} \end{equation} -where the effective action is given by +where the effective action $\mathcal U_\mathrm{GOE}$ is given by \begin{equation} \label{eq:goe.action} \begin{aligned} &\mathcal U_\textrm{GOE}(\hat\lambda, Q\mid\beta,\lambda^*,\mu) - =\hat\lambda(\lambda^*-\mu)-m\beta\mu \\ + =\hat\lambda(\lambda^*-\mu)+\lim_{m\to0}\bigg\{-m\beta\mu \\ &+\sigma^2\left[\beta^2\sum_{\alpha\gamma}^m(Q^{\alpha\gamma})^2 +2\beta\hat\lambda\sum_\alpha^m(Q^{1\alpha})^2 +\hat\lambda^2 - \right]+\frac12\log\det Q + \right]+\frac12\log\det Q\bigg\} \end{aligned} \end{equation} and $Q^{\alpha\alpha}=1$ because of the spherical constraint. We can evaluate this integral using the saddle point method. We make a replica symmetric ansatz for -$Q$, because this is a 2-spin model, but with the first row singled out because +$Q$, because this is a 2-spin spherical model, but with the first row singled out because of its unique coupling with $\hat\lambda$. The resulting matrix has the form \begin{equation} \label{eq:Q.structure} Q=\begin{bmatrix} @@ -273,11 +277,15 @@ of its unique coupling with $\hat\lambda$. The resulting matrix has the form \tilde q_0&q_0&q_0&\cdots&1 \end{bmatrix} \end{equation} -The relevant expressions in the effective action produce $\sum_{\alpha\beta}(Q^{\alpha\beta})^2=m+2(m-1)\tilde q_0^2+(m-1)(m-2)q_0^2$, $\sum_\alpha(Q^{1\alpha})^2=1+(m-1)\tilde q_0^2$, -and -\begin{equation} - \log\det Q=(m-2)\log(1-q_0)+\log(1+(m-2)q_0-(m-1)\tilde q_0^2) -\end{equation} +The relevant expressions in the effective action produce +\begin{align} + &\sum_{\alpha\beta}(Q^{\alpha\beta})^2=m+2(m-1)\tilde q_0^2+(m-1)(m-2)q_0^2 \\ + &\sum_\alpha(Q^{1\alpha})^2=1+(m-1)\tilde q_0^2 \\ + &\begin{aligned} + &\log\det Q=(m-2)\log(1-q_0) \\ + &\hspace{6em}+\log\big[1+(m-2)q_0-(m-1)\tilde q_0^2\big] + \end{aligned} +\end{align} Inserting these expressions into the effective action and taking the limit of $m$ to zero, we arrive at \begin{equation} @@ -285,7 +293,7 @@ $m$ to zero, we arrive at =\lim_{\beta\to\infty}\int d\hat\lambda\,dq_0\,d\tilde q_0\, e^{N\mathcal U_\textrm{GOE}(\hat\lambda,q_0,\tilde q_0\mid\beta,\lambda^*,\mu)} \end{equation} -with the effective action +with the new effective action \begin{equation} \begin{aligned} &\mathcal U_\mathrm{GOE}(\hat\lambda,q_0,\tilde q_0\mid\beta,\lambda^*,\mu) \\ @@ -316,7 +324,7 @@ action that diverges with $\beta$. To cure this, we must take $\tilde y=y$. The +\frac12\log\left(1-\frac{2\Delta z}{y^2}\right) \end{aligned} \end{equation} -Extremizing this action over the new parameters $y$, $\Delta z$, and $\hat\lambda$, we have +Extremizing this action over the new parameters $y$, $\Delta z$, and $\hat\lambda$, we find \begin{align} \hat\lambda&=\frac1\sigma\sqrt{\left(\frac{\mu-\lambda^*}{2\sigma}\right)^2-1} \\ @@ -329,7 +337,7 @@ Extremizing this action over the new parameters $y$, $\Delta z$, and $\hat\lambd -\frac{\mu-\lambda^*}{2\sigma}\sqrt{\left(\frac{\mu-\lambda^*}{2\sigma}\right)^2-1} \right] \end{align} -Inserting this solution into the effective action we find +Inserting this solution into the effective action we arrive at \begin{equation} \label{eq:goe.large.dev} \begin{aligned} &G_{\lambda^*}(\mu) @@ -341,15 +349,15 @@ Inserting this solution into the effective action we find \right] \end{aligned} \end{equation} -This function is plotted in Fig.~\ref{fig:large.dev} for $\lambda^*=0$. For $\mu<2\sigma$ $G_{0}(\mu)$ has an -imaginary part. This indicates that the existence of a minimally zero eigenvalue when $\mu<2\sigma$ corresponds with a large deviation that grows faster than $N$, +This function is plotted in Fig.~\ref{fig:large.dev} for $\lambda^*=0$. For $\mu<2\sigma$, $G_{0}(\mu)$ has an +imaginary part. This indicates that the existence of a zero minimum eigenvalue when $\mu<2\sigma$ corresponds with a large deviation that grows faster than $N$, rather like $N^2$, since in this regime the bulk of the typical spectrum is over zero and therefore extensively many eigenvalues have to have large -deviations in order for the smallest eigenvalue to be zero. For +deviations in order for the smallest eigenvalue to be zero \cite{Dean_2006_Large}. For $\mu\geq2\sigma$ this function gives the large deviation function for the probability of seeing a zero eigenvalue given the shift $\mu$. $\mu=2\sigma$ is the maximum of the function with a real value, and -corresponds to the intersection of the average spectrum with zero, i.e., a +corresponds to the intersection of the typical bulk spectrum with zero, i.e., a pseudogap. \begin{figure} @@ -377,11 +385,9 @@ pseudogap. } \label{fig:large.dev} \end{figure} -Marginal spectra with a pseudogap and those with simple isolated eigenvalues -are qualitatively different, and more attention may be focused on the former. Here, we see what appears to be a general heuristic for identifying the saddle parameters for which the spectrum is pseudogapped: the equivalent of this -large-deviation functions will lie on the singular boundary between a purely +large-deviation function will lie on the singular boundary between a purely real and complex value. \subsection{Conditioning on a pseudogap} @@ -389,7 +395,7 @@ real and complex value. We have seen that this method effectively conditions a random matrix ensemble on its lowest eigenvalue being zero. However, this does not correspond on its -own to marginal minima. In the previous example, most values of $\mu$ where +own to marginality. In the previous example, most values of $\mu$ where the calculation was valid correspond to matrices with a single isolated eigenvalue. However, the marginal minima we are concerned with have pseudogapped spectra, where the continuous part of the spectral density has a @@ -398,7 +404,7 @@ lower bound at zero. Fortunately, our calculation can be modified to ensure that we consider only pseudogapped spectra. First, we insert a shift $\mu$ by hand into the `natural' spectrum of the problem at hand, conditioning the trace to have a specific -value $\mu=\operatorname{Tr}A$. Then, we choose this artificial shift so that +value $\mu=\frac1N\operatorname{Tr}A$. Then, we choose this artificial shift so that the resulting conditioned spectra are pseudogapped. As seen the previous subsection, this can be done by starting from a sufficiently large $\mu$ and decreasing it until the calculation develops an imaginary part, signaling the @@ -406,9 +412,10 @@ breakdown of the large-deviation principle at order $N$. In isotropic or zero-signal landscapes, there is another way to condition on a pseudogap. In such landscapes, the typical spectrum does not have an isolated -eigenvalue. Therefore, the condition associated with the bulk of the spectrum -touching zero, i.e., the pseudogap, will always correspond to the most common -configuration. We can therefore choose $\mu=\mu_\textrm m$ such that +eigenvalue. Therefore, for a given $\mu$ the bottom of the spectrum can be located by looking for the value $\lambda^*$ that maximizes the (real) large deviation function. +Inverting this reasoning, we can find the value $\mu=\mu_\textrm m$ +corresponding to a marginal spectrum by requiring that the large deviation +function has a maximum in $\lambda^*$ at $\lambda^*=0$, or \begin{equation} 0=\frac\partial{\partial\lambda^*}G_{\lambda^*}(\mu_\mathrm m)\bigg|_{\lambda^*=0} \end{equation} @@ -1629,7 +1636,7 @@ still in its infancy \cite{Urbani_2024_Statistical}. \label{sec:superspace} The superspace $\mathbb R^{N|2D}$ is a vector space with $N$ real indices and -$2D$ Grassmann indices $\bar\theta_1,\theta_1,\ldots,\bar\theta_D,\theta_D$. +$2D$ Grassmann indices $\bar\theta_1,\theta_1,\ldots,\bar\theta_D,\theta_D$ \cite{DeWitt_1992_Supermanifolds}. The Grassmann indices anticommute like fermions. Their integration is defined by \begin{equation} \int d\theta\,\theta=1 |