diff options
Diffstat (limited to 'marginal.tex')
-rw-r--r-- | marginal.tex | 20 |
1 files changed, 19 insertions, 1 deletions
diff --git a/marginal.tex b/marginal.tex index 3a59487..1d2d1d6 100644 --- a/marginal.tex +++ b/marginal.tex @@ -1478,10 +1478,20 @@ taking the zero-temperature limit, we find \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 \end{equation} -\end{widetext} +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 +eigenvalue problem and one relating to the ordinary complexity. Instead, the +order parameters related to the eigenvalue problem are mixed throughout the +effective action with those of the ordinary complexity. This is a signal of the +fact that the sum of squares problem is not Gaussian, while the previous two +examples are. In all non-Gaussian problems, conditioning on properties of the +Hessian cannot be done independently from the complexity, and the method +introduced in this paper becomes necessary. \begin{figure} \includegraphics{figs/most_squares_complexity.pdf} @@ -1493,6 +1503,14 @@ taking the zero-temperature limit, we find } \label{fig:ls.complexity} \end{figure} +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 +demonstrates, the range of energies at which marginal minima are found can +differ significantly from those implied by the dominant complexity, with the +lowest energy significantly higher than the ground state and the highest energy +significantly higher than the threshold. + \cite{Urbani_2023_A, Kamali_2023_Dynamical, Kamali_2023_Stochastic, Urbani_2024_Statistical} \cite{Montanari_2023_Solving, Montanari_2024_On} |