diff options
| -rw-r--r-- | marginal.tex | 103 |
1 files changed, 70 insertions, 33 deletions
diff --git a/marginal.tex b/marginal.tex index fc89c5a..59b92e0 100644 --- a/marginal.tex +++ b/marginal.tex @@ -557,7 +557,7 @@ value of the minimum eigenvalue $\lambda^*$, or \end{equation} The marginal complexity follows by evaluating the complexity conditioned on $\lambda_{\text{min}}=0$ at the marginal stability $\mu=\mu_\text{m}(E)$, -\begin{equation} +\begin{equation} \label{eq:marginal.complexity} \Sigma_\text{m}(E) =\Sigma_0(E,\mu_\text m(E)) \end{equation} @@ -1267,7 +1267,7 @@ limit should continue to hold at small nonzero coupling, and perhaps reveal something about the inherent properties of marginal minima that do not tend to be found by algorithms. -\subsection{Random nonlinear least squares} +\subsection{Random sums of squares} \label{sec:least.squares} In this subsection we consider perhaps the simplest example of a non-Gaussian @@ -1426,12 +1426,12 @@ Given these simplifying forms of the ansatz, taking the superdeterminant in \begin{aligned} \log\det\left\{ \left[ - f'(C)\odot D-\hat\beta I+\left(R^{\circ2}-G^{\circ2}+I\sum_{\alpha\gamma}2(\delta^{\alpha1}\hat\lambda+\beta)(\delta^{\gamma1}\hat\lambda+\beta)Q_{\alpha\gamma}^2\right)\odot f''(C) + f'(C)\odot D-\hat\beta I+\left(R^{\circ2}-G^{\circ2}+I\sum_{\alpha\gamma}2(\delta^{\alpha1}\hat\lambda+\beta)(\delta^{\gamma1}\hat\lambda+\beta)(Q^{\alpha\gamma})^2\right)\odot f''(C) \right]f(C) +(I-R\odot f'(C))^2 \right\} \\ - +n\log\det_{\alpha\gamma}(\delta_{\alpha\gamma}-2(\delta_{\alpha1}\hat\lambda+\beta)Q_{\alpha\gamma}) - -2\log\det(I+G\odot f'(C)) + +n\log\det_{\alpha\gamma}(\delta_{\alpha\gamma}-2(\delta_{\alpha1}\hat\lambda+\beta)Q^{\alpha\gamma}) + -2\log\det\big[I+G\odot f'(C)\big] \end{aligned} \end{equation} \end{widetext} @@ -1454,22 +1454,34 @@ typical pairs of stationary points have no overlap. This requires that $f(0)=0$, We further take a planted replica symmetric structure for the matrix $Q$, identical to that in \eqref{eq:Q.structure}. The resulting effective action is the same as if we had made an annealed calculation in the complexity, though -the previous expressions are general. +the previous expressions are general. We find an expression of the form +\begin{equation} + \begin{aligned} + &\Sigma_{\lambda^*}(E,\mu) + =\frac1N\lim_{n\to0}\frac\partial{\partial n} + \int d\hat\beta\,d\hat\lambda\,dr\,dd\,dg\,dq_0\,d\tilde q_0\,\\ + &\hspace{8em}\times e^{nN\mathcal S_\mathrm{RSS}(\hat\beta,\hat\lambda,r,d,g,q_0,\tilde q_0\mid\lambda^*,E,\mu,\beta)} + \end{aligned} +\end{equation} +for the effective action \begin{widetext} \begin{equation} \begin{aligned} - \mathcal S_\beta - =\hat\beta E-\mu(r+g) - +\frac12\log\frac{d+r^2}{g^2}\frac{1-2q_0+\tilde q_0^2}{(1-q_0)^2} - -\frac\alpha2\log\left(\frac{1-f'(1)(2\beta(1-q_0)+\hat\lambda-(1-2q_0+\tilde q_0^2)\beta(\beta+\hat\lambda)f'(1))}{(1-(1-q_0)\beta f'(1))^2}\right) - \\ - -\frac12\mu\hat\lambda+\hat\lambda\lambda^*-\frac\alpha2\log\left[ + &\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\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) \\ + &\quad-\frac\alpha2\log\bigg( + \frac{1-4f'(1)\big[\beta(1-q_0)+\frac12\hat\lambda-\beta(\beta+\hat\lambda)(1-2q_0+\tilde q_0^2)f'(1)\big]} + {\big[1-2(1-q_0)\beta f'(1)\big]^2} \\ + &\qquad\qquad\qquad\times \frac{ - \big[f'(1)d-\hat\beta-f''(1)(r^2-g^2+q_0^2\beta^2-\tilde q_0^2\beta(\beta+\hat\lambda)+\beta\hat\lambda+\frac12\hat\lambda^2)\big]f(1)+(1-rf'(1))^2 + f(1)\big[f'(1)d-\hat\beta-f''(1)\big(r^2-g^2+4q_0^2\beta^2-4\tilde q_0^2\beta(\beta+\hat\lambda)+4\beta\hat\lambda+2\hat\lambda^2\big)\big]+(1-rf'(1))^2 }{ - (1+gf'(1))^2 + \big[1+gf'(1)\big]^2 } - \right] + \bigg) \end{aligned} \end{equation} We expect as before the limits of $q_0$ and $\tilde q_0$ as $\beta$ goes to @@ -1478,28 +1490,32 @@ infinity to approach one, defining their asymptotic expansion as in taking the zero-temperature limit, we find \begin{equation} \begin{aligned} - \mathcal S_\infty - =\hat\beta E-\mu(r+g) - +\frac12\log\frac{d+r^2}{g^2}\frac{y_0^2-\Delta z}{y_0^2} - -\frac\alpha2\log\left( - \frac{ - 1-(2y_0+\hat\lambda)f'(1)+(y_0^2-\Delta z)f'(1)^2 - }{(1-y_0f'(1))^2} - \right) + &\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\lambda\lambda^* + +\frac12\log\left(\frac{d+r^2}{g^2}\times\frac{y^2-2\Delta z}{y^2}\right) \\ - -\frac12\mu\hat\lambda+\hat\lambda\lambda^*-\frac\alpha2\log\left[ + &-\frac\alpha2\log\left( + \frac{ + 1-2(2y+\hat\lambda)f'(1)+4(y^2-2\Delta z)f'(1)^2 + }{\big[1-2yf'(1)\big]^2} + \times \frac{ - \big[f'(1)d-\hat\beta-f''(1)(r^2-g^2+2y_0\hat\lambda+\Delta z+\frac12\hat\lambda^2)\big]f(1)+\big[1-rf'(1)\big]^2 + f(1)\big[f'(1)d-\hat\beta-f''(1)(r^2-g^2+8(y\hat\lambda+\Delta z)+2\hat\lambda^2)\big]+\big[1-rf'(1)\big]^2 }{ - (1+gf'(1))^2 + \big[1+gf'(1)\big]^2 } - \right] + \right) \end{aligned} \end{equation} \end{widetext} We can finally write the complexity with fixed minimum eigenvalue $\lambda^*$ as -\begin{equation} - \Sigma_{\lambda^*}(E,\mu)=\operatorname{extremum}_{\hat\beta,r,d,g,y_0,\Delta z,\hat\lambda}\mathcal S_\infty +\begin{equation} \label{eq:rss.complexity} + \begin{aligned} + &\Sigma_{\lambda^*}(E,\mu) \\ + &=\underset{\hat\beta,\hat\lambda,r,d,g,y,\Delta z}{\operatorname{extremum}} + \mathcal S_\textrm{RSS}(\hat\beta,\hat\lambda,r,d,g,y,\Delta z\mid\lambda^*,E,\mu,\infty) + \end{aligned} \end{equation} Note that unlike the previous two examples, the effective action in this case does not split into two largely independent pieces, one relating to the @@ -1521,6 +1537,7 @@ introduced in this paper becomes necessary. } \label{fig:ls.complexity} \end{figure} +The marginal complexity can be derived from \eqref{eq:rss.complexity} using the \eqref{eq:marginal.stability} to fix $\mu$ to the marginal stability $\mu_\textrm m(E)$ and then by evaluating the complexity at that stability as in \eqref{eq:marginal.complexity}. Fig.~\ref{fig:ls.complexity} shows the marginal complexity in a sum-of-squares model with $\alpha=\frac32$ and $f(q)=q^2+q^3$. Also shown is the dominant complexity computed in Appendix~\ref{sec:dominant.complexity}. As the figure @@ -1550,10 +1567,21 @@ with the marginal stability only at the threshold energy. In our companion paper, we explore the relationship between the marginal complexity and the performance of two generic algorithms on this model: gradient descent and approximate message passing -\cite{Kent-Dobias_2024_Algorithm-independent}. - -\cite{Urbani_2023_A, Kamali_2023_Dynamical, Kamali_2023_Stochastic, Urbani_2024_Statistical} -\cite{Montanari_2023_Solving, Montanari_2024_On} +\cite{Kent-Dobias_2024_Algorithm-independent}. We show that the range of +energies where the marginal complexity is positive does effectively bound the +performance of these algorithms. At the moment the comparison is restricted to +models with small polynomial powers appearing in $f(q)$ and with small $\alpha$ +for computational reasons. However, with some of the \textsc{dmft} results +already found on these models it should be possible to make comparisons in a +wider family of models \cite{Kamali_2023_Dynamical, Kamali_2023_Stochastic}. + +The results on the marginal complexity are complimentary to rigorous results on +the performance of algorithms in the least squares case, which focus on bounds +for the parameters of $f$ necessary for zero-energy solutions to exist and be +found by algorithms \cite{Montanari_2023_Solving, Montanari_2024_On}. With more +work to evaluate the marginal complexity in the full \textsc{rsb} case, it will +be interesting to compare the bounds implied by the distribution of marginal +minima with those made by other means. \section{Conclusions} \label{sec:conclusion} @@ -1582,6 +1610,15 @@ inconvenient measure. It's possible that a variational approach can be preserved by treating the direction toward and the directions orthogonal to the signal differently. This problem merits further research. +Finally, the problem of predicting which marginal minima are able to attract +some dynamics and which cannot attract any dynamics looms large over this work. +As we discussed briefly at the end of Section~\ref{sec:multispherical}, in some +simple contexts it is easy to see why certain marginal minima are not viable, +but at the moment we do not know how to generalize this. Ideas related to the +stability of minima with respect to perturbations of the landscape have +recently been suggested as a route to understanding this problem, but this is +still in its infancy \cite{Urbani_2024_Statistical}. + \begin{acknowledgements} JK-D is supported by a \textsc{DynSysMath} Specific Initiative of the INFN. \end{acknowledgements} |