Merge branch 'master' into apsaps.v2

1 files changed, 119 insertions, 48 deletions

diff --git a/marginal.tex b/marginal.tex
index de44583..1ede776 100644
--- a/marginal.tex
+++ b/marginal.tex
@@ -61,7 +61,10 @@ 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. 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.
+minima}, or minima whose Hessian matrix have a continuous spectral density over
+all sufficiently small positive eigenvalues. In most circumstances the spectrum
+is \emph{pseudogapped}, which means that the spectral density smoothly
+approaches zero as zero eigenvalue is approached from above.
 
 However, recent work found that the threshold energy is not important even for
 simple gradient descent dynamics \cite{Folena_2020_Rethinking, Folena_2023_On, ElAlaoui_2020_Algorithmic}.
@@ -116,7 +119,7 @@ continuous spectrum, we enforce the condition that the spectrum has a
 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 where the technique is more useful.
-In a companion paper, we compare the marginal complexity with the performance
+In a related work, we compare the marginal complexity with the performance
 of gradient descent and approximate message passing algorithms \cite{Kent-Dobias_2024_Algorithm-independent}.
 
 An outline of this paper follows. In Section \ref{sec:eigenvalue} we introduce the technique for conditioning on
@@ -141,7 +144,7 @@ at the bottom on the spectrum.
 
 \subsection{The general method}
 
-Consider an $N\times N$ real matrix $A$. An arbitrary function $g$ of the
+Consider an $N\times N$ real symmetric 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}
@@ -466,8 +469,9 @@ extremizing the Lagrangian
   L(\mathbf x,\pmb\omega)=H(\mathbf x)+\sum_{i=1}^r\omega_ig_i(\mathbf x)
 \end{equation}
 with respect to $\mathbf x$ and the Lagrange multipliers
-$\pmb\omega=\{\omega_1,\ldots,\omega_r\}$. The corresponding gradient and
-Hessian of the energy associated with this constrained extremal problem are
+$\pmb\omega=\{\omega_1,\ldots,\omega_r\}$. To write the gradient and Hessian of the energy, which are necessary to count stationary points, care must be taken to ensure they are constrained to the tangent space of the configuration manifold. For our purposes, the Lagrangian formalism offers a solution: the gradient $\nabla H:\mathbb R^N\times\mathbb R^r\to\mathbb R^N$ and
+Hessian $\operatorname{Hess} H:\mathbb R^N\times\mathbb R^r\to\mathbb R^{N\times N}$ of the energy $H$ can be written as the simple vector derivatives of
+the Lagrangian $L$, with
 \begin{align}
   &\nabla H(\mathbf x,\pmb\omega)
   =\partial L(\mathbf x,\pmb\omega)
@@ -480,7 +484,13 @@ Hessian of the energy associated with this constrained extremal problem are
   \end{aligned}
 \end{align}
 where $\partial=\frac\partial{\partial\mathbf x}$ will always represent the
-derivative with respect to the vector argument $\mathbf x$.
+derivative with respect to the vector argument $\mathbf x$. Note that unlike
+the energy, which is a function of the configuration $\mathbf x$ alone, the
+gradient and Hessian depend also on the Lagrange multipliers $\pmb\omega$. In situations
+with an extensive number of constraints, it is important to take seriously
+contributions of the form $\frac{\partial^2L}{\partial\mathbf
+x\partial\pmb\omega}$ to the Hessian \cite{Kent-Dobias_2024_On}. However, the cases we study here have
+$N^0$ constraints and these contributions appear as finite-$N$ corrections.
 
 The number of
 stationary points in a landscape for a particular function $H$ is found by
@@ -631,20 +641,35 @@ treat the determinant keeping the absolute value signs, as in previous works
 \cite{Folena_2020_Rethinking, Kent-Dobias_2023_How}. However, other of
 our examples are for models where the same techniques are impossible.
 
-For the cases studied here, fixing the trace results in a relationship
-between $\mu$ and the Lagrange multipliers enforcing the constraints. This is
-because the trace of $\partial\partial H$ is typically an order of $N$ smaller
-than the trace of $\partial\partial g_i$. The result is that
+Finally, the $\delta$-function fixing the trace of the Hessian to $\mu$ in
+\eqref{eq:kac-rice.measure.2} must be addressed. One could treat it using a
+Fourier representation as in (\ref{eq:delta.grad}--\ref{eq:delta.eigen}), but
+this is inconvenient because a term of the form
+$\operatorname{Tr}\partial\partial H(\mathbf x)$ in the exponential integrand
+cannot be neatly captured in superspace representation introduced in the next
+section. However, in the cases we study in this paper a simplification can be made: the trace of $\partial\partial H$ can be separated into two pieces, one
+that is spatially independent and one that is typically small, or
+\begin{equation} \label{eq:mu.star}
+  \operatorname{Tr}\partial\partial H(\mathbf x)=N\mu^*_H+\Delta_H(\mathbf x)
+\end{equation}
+where $\overline{\mu^*_H}=\mu^*$ and $\overline{\Delta_H(\mathbf x)}=O(N^0)$.
+Then fixing the trace of the Hessian to $\mu$ implies that
 \begin{equation}
-  \mu
-  =\frac1N\operatorname{Tr}\operatorname{Hess}H(\mathbf x)
-  =\frac1N\sum_{i=1}^r\omega_i\operatorname{Tr}\partial\partial g_i(\mathbf x)
-  +O(N^{-1})
+  \begin{aligned}
+    \mu
+    &=\frac1N\operatorname{Tr}\operatorname{Hess}H(\mathbf x)
+    =\frac1N\left(\partial\partial H(\mathbf x)+
+    \sum_{i=1}^r\omega_i\operatorname{Tr}\partial\partial g_i(\mathbf x)\right)
+    \\
+    &=\mu^*+\frac1N\sum_{i=1}^r\omega_i\operatorname{Tr}\partial\partial g_i(\mathbf x)
+    +O(N^{-1})
+  \end{aligned}
 \end{equation}
+for typical samples $H$.
 In particular, here we study only cases with quadratic $g_i$, which results in
 a linear expression relating $\mu$ and the $\omega_i$ that is independent of $\mathbf
 x$. Since $H$ contains the disorder of the problem, this simplification means
-that the effect of fixing the trace is independent of the disorder and only
+that the effect of fixing the trace is largely independent of the disorder and mostly
 depends on properties of the constraint manifold.
 
 \subsection{Superspace representation}
@@ -710,7 +735,7 @@ functions and the determinant made. The new measures
   \delta\big((\mathbf s_a^\alpha)^T\partial\mathbf g(\mathbf x_a)\big)
   \\
   d\pmb\omega&=\bigg(\prod_{i=1}^rd\omega_i\bigg)
-  \,\delta\bigg(N\mu-\sum_i^r\omega_i\operatorname{Tr}\partial\partial g_i\bigg)
+  \,\delta\bigg(N\mu-\mu^*-\sum_i^r\omega_i\operatorname{Tr}\partial\partial g_i\bigg)
 \end{align}
 collect the individual measures of the various fields embedded in the superfield, along with their constraints.
 \end{widetext}
@@ -755,7 +780,8 @@ unit normal distribution \cite{Crisanti_1993_The}. We focus on marginal minima
 in models with $f'(0)=0$, which corresponds to models without a random external
 field. Such a random field would correspond in each individual sample $H$ to a
 signal, and therefore complicate the analysis by correlating the positions of
-stationary points and the eigenvectors of their Hessians.
+stationary points and the eigenvectors of their Hessians. Here, $\mu^*$ of
+\eqref{eq:mu.star} is zero.
 
 The marginal optima of these models can be studied without the methods
 introduced in this paper, and have been in the past \cite{Folena_2020_Rethinking,
@@ -930,9 +956,9 @@ the contributions from the marginal pieces of the calculation, and is given by
 \end{equation}
 \end{widetext}
 The fact that the complexity can be split into two relatively independent
-pieces in this way is a characteristic of the Gaussian nature of the spherical
+pieces in this way is a characteristic of the isotropic and Gaussian nature of the spherical
 spin glass. In Section \ref{sec:least.squares} we will study a model whose
-energy is not Gaussian and where such a decomposition is impossible.
+energy is isotropic but not Gaussian and where such a decomposition is impossible.
 
 There are some dramatic simplifications that emerge from the structure of this
 particular problem. First, notice that the dependence on the parameters $X$ and $\hat X$ are purely quadratic.
@@ -1020,7 +1046,7 @@ for $\mathbf x,\mathbf x'\in\mathbb R^N$ by
   \overline{H_i(\mathbf x)H_j(\mathbf x')}
   =N\delta_{ij}f_i\left(\frac{\mathbf x\cdot\mathbf x'}N\right)
 \end{equation}
-with the functions $f_1$ and $f_2$ not necessarily the same.
+with the functions $f_1$ and $f_2$ not necessarily the same. As for the spherical spin glasses, $\mu^*$ of \eqref{eq:mu.star} is zero.
 
 In this problem, there is an energetic competition between the independent spin
 glass energies on each sphere and their tendency to align or anti-align through
@@ -1219,7 +1245,7 @@ asymptotic behavior of the overlaps. These take the form
 $q^{ij}_0=q^{ij}_d-y^{ij}_0\beta^{-1}-z^{ij}_0\beta^{-2}$. Notice that in this case, the asymptotic behavior of the
 off-diagonal elements is to approach the value of the diagonal rather than to approach one.
 We also require $\tilde q^{ij}_d=q^{ij}_d-\tilde y^{ij}_d\beta^{-1}-\tilde
-z^{ij}_d\beta^{-2}$, i.e., that the tilde diagonal terms also approache the
+z^{ij}_d\beta^{-2}$, i.e., that the tilde diagonal terms also approach the
 same diagonal value as the untilde terms, but with potentially different rates.
 
 As before, in order for the logarithmic term to stay finite, there are necessary
@@ -1288,8 +1314,8 @@ $\epsilon$ is increased, the most common type of marginal minimum drifts toward
 points with $\omega_1>\omega_2$.
 
 Multispherical spin glasses may be an interesting platform for testing ideas
-about which among the possible marginal minima can dynamics,
-and cannot. In the limit where $\epsilon=0$ and the configurations of the
+about which among the possible marginal minima can attract dynamics
+and which cannot. In the limit where $\epsilon=0$ and the configurations of the
 two spheres are independent, the minima found dynamically should be marginal on both
 subspaces. Just because technically on the expanded configuration space
 the Cartesian product of a deep stable minimum on one sphere and a marginal minimum on the other is
@@ -1364,9 +1390,12 @@ As in the previous sections, we used the method of Lagrange multipliers to analy
     -V_k(\mathbf x)\partial\partial V_k(\mathbf x)\right]+\omega I
   \end{aligned}
 \end{align}
-As in the spherical and multispherical spin glasses, fixing the trace of the Hessian
-is equivalent to constraining the value of the Lagrange
-multiplier $\omega=\mu$.
+Unlike in the spherical and multispherical spin glasses, the value $\mu^*$
+defined in \eqref{eq:mu.star} giving the typical value of
+$\frac1N\operatorname{Tr}\partial\partial H$ is not always zero. Instead
+$\mu^*=-f'(0)$, nonzero where there is a linear term in $V$. Fixing the trace
+of the Hessian is therefore equivalent to constraining the value of the Lagrange multiplier $\omega=\mu+f'(0)$.
+
 
 The derivation of the marginal complexity for this model is complicated, but
 can be made schematically like that of the derivation of the equilibrium free
@@ -1379,10 +1408,11 @@ $\lambda^*$ is given by
   \begin{aligned}
     \mathcal N(E,\mu,\lambda^*)^n
     &=\int d\hat\beta\,d\hat\lambda\prod_{a=1}^n\lim_{m_a\to0}\prod_{\alpha=1}^{m_a}d\pmb\phi_a^\alpha
-    \exp\left\{
+    \\
+    &\qquad\times\exp\left\{
       \delta^{\alpha1}N(\hat\beta E+\hat\lambda\lambda^*)
       -\frac12\int d1\,d2\,\left[B^\alpha(1,2)\sum_{k=1}^MV_k(\pmb\phi_a^\alpha(1,2))^2
-      -\mu\|\pmb\phi_a^\alpha(1,2)\|^2\right]
+      -\big(\mu+f'(0)\big)\|\pmb\phi_a^\alpha(1,2)\|^2\right]
     \right\}
   \end{aligned}
 \end{equation}
@@ -1499,7 +1529,7 @@ with an effective action
 \begin{equation}
   \begin{aligned}
     &\mathcal S_\mathrm{RSS}(\hat\beta,\hat\lambda,r,d,g,q_0,\tilde q_0\mid\lambda^*,E,\mu,\beta)
-    =\hat\beta E-\mu(r+g+\hat\lambda)
+    =\hat\beta E-\big(\mu+f'(0)\big)(r+g+\hat\lambda)
     +\hat\lambda\lambda^*
     +\frac12\log\left(\frac{d+r^2}{g^2}
     \times\frac{1-2q_0+\tilde q_0^2}{(1-q_0)^2}\right) \\
@@ -1522,7 +1552,7 @@ taking the zero-temperature limit, we find
 \begin{equation}
   \begin{aligned}
     &\mathcal S_\mathrm{RSS}(\hat\beta,\hat\lambda,r,d,g,y,\Delta z\mid\lambda^*,E,\mu,\infty)
-    =\hat\beta E-\mu(r+g+\hat\lambda)
+    =\hat\beta E-\big(\mu+f'(0)\big)(r+g+\hat\lambda)
     +\hat\lambda\lambda^*
     +\frac12\log\left(\frac{d+r^2}{g^2}\times\frac{y^2-2\Delta z}{y^2}\right)
     \\
@@ -1622,7 +1652,7 @@ to determine the marginal stability continue to hold even in non-Gaussian cases
 where the complexity and the condition to fix the minimum eigenvalue are
 tangled together.
 
-In our companion paper, we use a sum of squared random functions model to explore the relationship between the marginal
+In a related paper, we use a sum of squared random functions model to explore the relationship between the marginal
 complexity and the performance of two generic algorithms:
 gradient descent and approximate message passing
 \cite{Kent-Dobias_2024_Algorithm-independent}. We show that the range of
@@ -1648,8 +1678,7 @@ We have introduced a method for conditioning complexity on the marginality of
 stationary points. This method is general, and permits
 conditioning without first needing to understand the statistics of the Hessian at stationary points. We used our approach to study marginal complexity in three
 different models of random landscapes, showing that the method works and can be
-applied to models whose marginal complexity was not previously known. In our
-companion paper, we further show that marginal complexity in the third
+applied to models whose marginal complexity was not previously known. In related work, we further show that marginal complexity in the third
 model of sums of squared random functions can be used to effectively bound
 algorithmic performance \cite{Kent-Dobias_2024_Algorithm-independent}.
 
@@ -1675,6 +1704,25 @@ self-similarity and stochastic stability of minima have
 recently been suggested as a route to understanding this problem, but this approach is
 still in its infancy \cite{Urbani_2024_Statistical}.
 
+The title of our paper and that of \citeauthor{Muller_2006_Marginal} suggest
+they address the same topic, but this is not the case
+\cite{Muller_2006_Marginal}. That work differs in three important and
+fundamental ways. First, it describes minima of the TAP free energy and
+involves peculiarities specific to the TAP. Second, it describes dominant
+minima which happen to be marginal, not a condition for finding subdominant marginal minima. Finally, it
+focuses on minima with a single soft direction (which are the typical minima of
+the low temperature Sherrington--Kirkpatrick TAP free energy), while we aim to
+avoid such minima in favor of ones that have a pseudogap (which we argue are relevant
+to out-of-equilibrium dynamics). The fact that the typical minima studied by
+\citeauthor{Muller_2006_Marginal} are not marginal in this latter sense may
+provide an intuitive explanation for the seeming discrepancy between the proof
+that the low-energy Sherrington--Kirkpatrick model cannot be sampled
+\cite{ElAlaoui_2022_Sampling} and the proof that a message passing algorithm
+can find near-ground states \cite{Montanari_2021_Optimization}: the algorithm
+finds the atypical low-lying states that are marginal in the sense considered
+here but cannot find the typical ones considered by
+\citeauthor{Muller_2006_Marginal}.
+
 \begin{acknowledgements}
   JK-D is supported by a \textsc{DynSysMath} Specific Initiative of the INFN.
 \end{acknowledgements}
@@ -1759,7 +1807,7 @@ like the super vector $\pmb\phi$ is made up of a linear combination of $N\times
 N$ regular or Grassmann matrices indexed by every nonvanishing combination of
 the Grassmann indices $\bar\theta_1,\theta_1,\bar\theta_2,\theta_2$. Such a supermatrix acts on supervectors by ordinary matrix multiplication and convolution in the Grassmann indices, i.e.,
 \begin{equation}
-  (M\pmb\phi)(1)=\int d1\,M(1,2)\pmb\phi(2)
+  (M\pmb\phi)(1)=\int d2\,M(1,2)\pmb\phi(2)
 \end{equation}
 The identity supermatrix is given by
 \begin{equation}
@@ -1772,19 +1820,28 @@ Integrals involving superfields contracted into such operators result in schemat
 \end{equation}
 where the usual role of the determinant is replaced by the superdeterminant.
 The superdeterminant can be defined using the ordinary determinant by writing a
-block version of the matrix $M$: if $\mathbf e(1)=\{1,\bar\theta_1\theta_1\}$ is
+block version of the matrix $M$. If $\mathbf e(1)=\{1,\bar\theta_1\theta_1\}$ is
 the basis vector of the even subspace of the superspace and $\mathbf
-f(1)=\{\bar\theta_1,\theta_1\}$ is that of the odd subspace, then we can form a
+f(1)=\{\bar\theta_1,\theta_1\}$ is that of the odd subspace, dual bases $\mathbf e^\dagger(1)=\{\bar\theta_1\theta_1,1\}$ and $\mathbf f^\dagger(1)=\{-\theta_1,\bar\theta_1\}$ can be defined by the requirement that
+\begin{align}
+  &\int d1\,e_i^\dagger(1)e_j(1)=\delta_{ij}
+  &&
+  \int d1\,f_i^\dagger(1)f_j(1)=\delta_{ij} \\
+  &\int d1\,e_i^\dagger(1)f_j(1)=0
+  &&
+  \int d1\,f_i^\dagger(1)e_j(1)=0
+\end{align}
+With such bases and dual bases defined, we can form a
 block representation of $M$ in analogy to the matrix form of an operator in quantum mechanics by
 \begin{equation}
   \int d1\,d2\,\begin{bmatrix}
-    \mathbf e(1)M(1,2)\mathbf e(2)^T
+    \mathbf e^\dagger(1)M(1,2)\mathbf e(2)
     &
-    \mathbf e(1)M(1,2)\mathbf f(2)^T
+    \mathbf e^\dagger(1)M(1,2)\mathbf f(2)
     \\
-    \mathbf f(1)M(1,2)\mathbf e(2)^T
+    \mathbf f^\dagger(1)M(1,2)\mathbf e(2)
     &
-    \mathbf f(1)M(1,2)\mathbf f(2)^T
+    \mathbf f^\dagger(1)M(1,2)\mathbf f(2)
   \end{bmatrix}
   =\begin{bmatrix}
     A & B \\ C & D
@@ -1802,7 +1859,21 @@ save for the inverse of $\det D$. Likewise, the supertrace of $M$ is is given by
 \end{equation}
 The same method can be used to calculate the
 superdeterminant and supertrace in arbitrary superspaces, where for $\mathbb R^{N|2D}$ each
-basis has $2^{2D-1}$ elements. For instance, for $\mathbb R^{N|4}$ we have $\mathbf e(1,2)=\{1,\bar\theta_1\theta_1,\bar\theta_2\theta_2,\bar\theta_1\theta_2,\bar\theta_2\theta_1,\bar\theta_1\bar\theta_2,\theta_1\theta_2,\bar\theta_1\theta_1\bar\theta_2\theta_2\}$ and $\mathbf f(1,2)=\{\bar\theta_1,\theta_1,\bar\theta_2,\theta_2,\bar\theta_1\theta_1\bar\theta_2,\bar\theta_2\theta_2\theta_1,\bar\theta_1\theta_1\theta_2,\bar\theta_2\theta_2\theta_1\}$.
+basis has $2^{2D-1}$ elements. For instance, for $\mathbb R^{N|4}$ we have
+\begin{align}
+  &\mathbf e(1,2)=\{
+    1,\bar\theta_1\theta_1,\bar\theta_2\theta_2,
+    \bar\theta_1\theta_2,\bar\theta_2\theta_1,
+    \bar\theta_1\bar\theta_2,\theta_1\theta_2,
+    \bar\theta_1\theta_1\bar\theta_2\theta_2
+  \}\notag \\
+  &\mathbf f(1,2)=\{
+    \bar\theta_1,\theta_1,\bar\theta_2,\theta_2,
+    \bar\theta_1\theta_1\bar\theta_2,\bar\theta_2\theta_2\theta_1,
+    \bar\theta_1\theta_1\theta_2,\bar\theta_2\theta_2\theta_1
+  \}
+\end{align}
+with the dual bases defined analogously to those above.
 
 \section{BRST symmetry}
 \label{sec:brst}
@@ -1988,9 +2059,9 @@ the replicated count of stationary points can be written
     =\int d\hat\beta\prod_{a=1}^n\,d\pmb\phi_a\,
     \exp\bigg[
       N\hat\beta E \\
-    &\qquad-\frac12\int d1\,\left(
+    &-\frac12\int d1\,\left(
         B(1)\sum_{k=1}^MV_k(\pmb\phi_a(1))^2
-        -\mu\|\pmb\phi_a(1)\|^2
+        -\big(\mu+f'(0)\big)\|\pmb\phi_a(1)\|^2
       \right)
     \bigg]
   \end{aligned}
@@ -2033,9 +2104,9 @@ Making the $M$ independent Gaussian integrals, we find
 \begin{equation}
   \begin{aligned}
     &\mathcal N(E,\mu)^n
-    =\int d\hat\beta\left(\prod_{a=1}^nd\pmb\phi_a\right)
-    \exp\bigg[
-      nN\hat\beta E+\frac\mu2\sum_a^n\int d1\,\|\pmb\phi_a\|^2 \\
+    =\int d\hat\beta\left(\prod_{a=1}^nd\pmb\phi_a\right) \\
+    &\times\exp\bigg[
+      nN\hat\beta E+\frac{\mu+f'(0)}2\sum_a^n\int d1\,\|\pmb\phi_a\|^2 \\
     &\quad-\frac M2\log\operatorname{sdet}\left(
         \delta_{ab}\delta(1,2)+B(1)f\left(\frac{\pmb\phi_a(1)\cdot\pmb\phi_b(2)}N\right)
       \right)
@@ -2056,7 +2127,7 @@ We therefore have
     &\mathcal N(E,\mu)^n
     =\int d\hat\beta\,d\mathbb Q\,
     \exp\bigg\{
-      nN\hat\beta E+N\frac\mu2\operatorname{sTr}\mathbb Q
+      nN\hat\beta E+N\frac{\mu+f'(0)}2\operatorname{sTr}\mathbb Q
     +\frac N2\log\operatorname{sdet}\mathbb Q
     -\frac M2\log\operatorname{sdet}\left[
       \delta_{ab}\delta(1,2)+B(1)f(\mathbb Q_{ab}(1,2))
@@ -2086,7 +2157,7 @@ where the effective action is given by
 \begin{equation}
   \begin{aligned}
     \mathcal S_\mathrm{KR}(\hat\beta,C,R,D,G)
-    &=\hat\beta E+\lim_{n\to0}\frac1n\Bigg(-\mu\operatorname{Tr}(G+R)
+    &=\hat\beta E+\lim_{n\to0}\frac1n\Bigg(-\big(\mu+f'(0)\big)\operatorname{Tr}(G+R)
     +\frac12\log\det\big[G^{-2}(CD+R^2)\big]
     +\alpha\log\det\big[I+G\odot f'(C)\big]
     \\