diff options
Diffstat (limited to 'marginal.tex')
| -rw-r--r-- | marginal.tex | 63 |
1 files changed, 44 insertions, 19 deletions
diff --git a/marginal.tex b/marginal.tex index 3a94ca0..26a88fe 100644 --- a/marginal.tex +++ b/marginal.tex @@ -55,31 +55,38 @@ 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. -In some simple models of rugged landscapes, it was recently found that marginal -minima are significant as the attractors of gradient descent dynamics -\cite{Folena_2020_Rethinking, Folena_2023_On}. This extends to more novel -algorithms, like approximate message passing -\cite{Kent-Dobias_2024_Algorithm-independent}. While it is still not known how -to predict which marginal minima will be attractors, this ubiquity of behavior -suggests that understanding the distribution of marginal minima is a useful -step in bounding out-of-equilibrium dynamical behavior. +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}, 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}. +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 +\cite{Kent-Dobias_2023_How}. Though it is still not known how to predict the +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 +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 marginal minima at the energy level at which they are the -majority of stationary points, commonly known as the threshold energy -\cite{Monasson_1995_Structural}. It is now understood that out-of-equilibrium -dynamics typically goes to marginal minima at other energy levels -\cite{Folena_2023_On}. +results in only the threshold energy and cannot characterize marginal minima at +energies where they are a minority \cite{Monasson_1995_Structural}. -The alternative approach, used to great success in the spherical models, is to +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 points. Then, one can condition the analysis on whatever properties of the Hessian are necessary to lead to marginal minima. This strategy is so -successful in the spherical models because it is straightforward to implement. +successful in the spherical spin glasses because it is straightforward to implement. First, the shape of the Hessian's spectrum is independent of energy and even whether one sits at a stationary point or not. This is a property of models whose energy is a Gaussian random variable \cite{Bray_2007_Statistics}. @@ -87,7 +94,7 @@ Furthermore, a natural parameter in the analysis of these models linearly shifts the spectrum of the Hessian. Therefore, tuning this parameter to a specific constant value allows one to require that the Hessian spectrum have a pseudogap, and therefore that the associated minima be marginal. Unfortunately -this strategy is less straightforward to generalize. Many models of interest, +this strategy is less straightforward to generalize to other models. Many models of interest, especially in inference problems, have Hessian statistics that are poorly understood. This is especially true for the statistics of the Hessian conditioned to lie at stationary points, which is necessary to understand in @@ -101,10 +108,23 @@ the smallest eigenvalue of the Hessian at stationary points be zero, and further looking for a sign that the zero eigenvalue lies at the edge of a continuous spectrum, we enforce the condition that the spectrum has a pseudogap, and is therefore marginal. We demonstrate the method on the -spherical models, where it is unnecessary but instructive, and on extensions of +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}. + +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 +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. +Finally, Section \ref{sec:conclusion} summarizes this work and suggests +necessary extensions. \section{Conditioning on the smallest eigenvalue} +\label{sec:eigenvalue} In this section, we introduce a general method for conditioning a measure on the smallest eigenvalue of some matrix that depends on it. In Section @@ -124,7 +144,9 @@ expressed as {\int d\mathbf s'\,\delta(N-\|\mathbf s'\|^2)e^{-\beta\mathbf s'^TA\mathbf s'}} g\left(\frac{\mathbf s^TA\mathbf s}N\right) \end{equation} -Assuming +In the limit of large $\beta$, each integral concentrates among vectors +$\mathbf s$ in the eigenspace of $A$ corresponding to the smallest eigenvalue +of $A$. This produces \begin{equation} \begin{aligned} &\lim_{\beta\to\infty}\int\frac{ @@ -143,7 +165,7 @@ Assuming \end{equation} The first relation extends a technique first introduced in \cite{Ikeda_2023_Bose-Einstein-like} and used in -\cite{Kent-Dobias_2024_Arrangement}. A Boltzmann distribution is introduced +\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$ @@ -390,6 +412,7 @@ that $\hat\lambda=0$. \section{Marginal complexity in random landscapes} +\label{sec:marginal.complexity} The methods of the previous section can be used in diverse settings. However, we are interested in applying them to study stationary points in random @@ -631,6 +654,7 @@ course the complexity of the underlying problem is not banished: near the end of the calculation, terms involving the superspace must be expanded. \section{Examples} +\label{sec:examples} In this section we present analysis of marginal complexity in three random landscapes. In Section \ref{sec:ex.spherical} we apply the methods described @@ -1356,6 +1380,7 @@ taking the zero-temperature limit, we find \end{figure} \section{Conclusions} +\label{sec:conclusion} We have introduced a method for conditioning complexity on the marginality of stationary points. This method is in principal completely general, and permits |