From 1c6dd13cd759855ab7d49bc2b7758993cef2bafd Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Sat, 17 Jun 2023 10:36:44 +0200 Subject: A few fixes and many citations. --- when_annealed.bib | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ when_annealed.tex | 20 +++++----- 2 files changed, 123 insertions(+), 9 deletions(-) diff --git a/when_annealed.bib b/when_annealed.bib index d13ddf8..7c311fa 100644 --- a/when_annealed.bib +++ b/when_annealed.bib @@ -1,3 +1,17 @@ +@article{Altieri_2021_Properties, + author = {Altieri, Ada and Roy, Felix and Cammarota, Chiara and Biroli, Giulio}, + title = {Properties of Equilibria and Glassy Phases of the Random {Lotka}-{Volterra} Model with Demographic Noise}, + journal = {Physical Review Letters}, + publisher = {American Physical Society (APS)}, + year = {2021}, + month = {6}, + number = {25}, + volume = {126}, + pages = {258301}, + url = {https://doi.org/10.1103%2Fphysrevlett.126.258301}, + doi = {10.1103/physrevlett.126.258301} +} + @article{Auffinger_2022_The, author = {Auffinger, Antonio and Zhou, Yuxin}, title = {The Spherical {$p+s$} Spin Glass At Zero Temperature}, @@ -24,6 +38,34 @@ doi = {10.1002/cpa.21875} } +@article{Bray_2007_Statistics, + author = {Bray, Alan J. and Dean, David S.}, + title = {Statistics of Critical Points of {Gaussian} Fields on Large-Dimensional Spaces}, + journal = {Physical Review Letters}, + publisher = {American Physical Society (APS)}, + year = {2007}, + month = {4}, + number = {15}, + volume = {98}, + pages = {150201}, + url = {https://doi.org/10.1103%2Fphysrevlett.98.150201}, + doi = {10.1103/physrevlett.98.150201} +} + +@article{Cavagna_1998_Stationary, + author = {Cavagna, Andrea and Giardina, Irene and Parisi, Giorgio}, + title = {Stationary points of the {Thouless}-{Anderson}-{Palmer} free energy}, + journal = {Physical Review B}, + publisher = {American Physical Society (APS)}, + year = {1998}, + month = {5}, + number = {18}, + volume = {57}, + pages = {11251--11257}, + url = {https://doi.org/10.1103%2Fphysrevb.57.11251}, + doi = {10.1103/physrevb.57.11251} +} + @article{Crisanti_2004_Spherical, author = {Crisanti, A. and Leuzzi, L.}, title = {Spherical $2+p$ Spin-Glass Model: An Exactly Solvable Model for Glass to Spin-Glass Transition}, @@ -121,6 +163,20 @@ doi = {10.1103/physrevlett.92.240601} } +@article{Fyodorov_2007_Density, + author = {Fyodorov, Y. V. and Sommers, H.-J. and Williams, I.}, + title = {Density of stationary points in a high dimensional random energy landscape and the onset of glassy behavior}, + journal = {JETP Letters}, + publisher = {Pleiades Publishing Ltd}, + year = {2007}, + month = {5}, + number = {5}, + volume = {85}, + pages = {261--266}, + url = {https://doi.org/10.1134%2Fs0021364007050098}, + doi = {10.1134/s0021364007050098} +} + @article{Fyodorov_2012_Critical, author = {Fyodorov, Yan V. and Nadal, Celine}, title = {Critical Behavior of the Number of Minima of a Random Landscape at the Glass Transition Point and the Tracy-Widom Distribution}, @@ -149,6 +205,20 @@ doi = {10.1103/physrevlett.130.237103} } +@article{Kent-Dobias_2021_Complex, + author = {Kent-Dobias, Jaron and Kurchan, Jorge}, + title = {Complex complex landscapes}, + journal = {Physical Review Research}, + publisher = {American Physical Society (APS)}, + year = {2021}, + month = {4}, + number = {2}, + volume = {3}, + pages = {023064}, + url = {https://doi.org/10.1103%2Fphysrevresearch.3.023064}, + doi = {10.1103/physrevresearch.3.023064} +} + @article{Kent-Dobias_2023_How, author = {Kent-Dobias, Jaron and Kurchan, Jorge}, title = {How to count in hierarchical landscapes: a full solution to mean-field complexity}, @@ -163,6 +233,20 @@ doi = {10.1103/PhysRevE.107.064111} } +@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{Muller_2006_Marginal, author = {Müller, Markus and Leuzzi, Luca and Crisanti, Andrea}, title = {Marginal states in mean-field glasses}, @@ -230,6 +314,20 @@ interactions: the typical number of equilibria}, eprinttype = {arxiv} } +@article{Stein_1995_Broken, + author = {Stein, D. L. and Newman, C. M.}, + title = {Broken ergodicity and the geometry of rugged landscapes}, + journal = {Physical Review E}, + publisher = {American Physical Society (APS)}, + year = {1995}, + month = {6}, + number = {6}, + volume = {51}, + pages = {5228--5238}, + url = {https://doi.org/10.1103%2Fphysreve.51.5228}, + doi = {10.1103/physreve.51.5228} +} + @article{Wainrib_2013_Topological, author = {Wainrib, Gilles and Touboul, Jonathan}, title = {Topological and Dynamical Complexity of Random Neural Networks}, @@ -244,3 +342,17 @@ interactions: the typical number of equilibria}, doi = {10.1103/physrevlett.110.118101} } +@article{Yang_2023_Stochastic, + author = {Yang, Ning and Tang, Chao and Tu, Yuhai}, + title = {Stochastic Gradient Descent Introduces an Effective Landscape-Dependent Regularization Favoring Flat Solutions}, + journal = {Physical Review Letters}, + publisher = {American Physical Society (APS)}, + year = {2023}, + month = {6}, + number = {23}, + volume = {130}, + pages = {237101}, + url = {https://doi.org/10.1103%2Fphysrevlett.130.237101}, + doi = {10.1103/physrevlett.130.237101} +} + diff --git a/when_annealed.tex b/when_annealed.tex index dd57ec2..469fd6e 100644 --- a/when_annealed.tex +++ b/when_annealed.tex @@ -56,12 +56,14 @@ Random high-dimensional energies, cost functions, and interaction networks are important in many fields. The energy landscape of glasses, the likelihood landscape of machine learning and inference, and the interactions between -organisms in an ecosystem are just a few examples. A traditional tool for +organisms in an ecosystem are just a few examples \cite{Stein_1995_Broken, Krzakala_2007_Landscape, Altieri_2021_Properties, Yang_2023_Stochastic}. A traditional tool for making sense of their behavior is to analyze the statistics of points where -their dynamics are stationary. For energy or cost landscapes, these correspond -to the minima, maxima, and saddles, while for ecosystems and other non-gradient -dynamical systems these correspond to equilibria of the dynamics. When many -stationary points are present, the system is considered complex. +their dynamics are stationary \cite{Cavagna_1998_Stationary, +Fyodorov_2004_Complexity, Fyodorov_2007_Density, Bray_2007_Statistics}. For +energy or cost landscapes, these correspond to the minima, maxima, and saddles, +while for ecosystems and other non-gradient dynamical systems these correspond +to equilibria of the dynamics. When many stationary points are present, the +system is considered complex. Despite the importance of stationary point statistics for understanding complex behavior, they are often calculated using an uncontrolled approximation. @@ -69,12 +71,12 @@ Because their number is so large, it cannot be reliably averaged. The annealed approximation takes this average anyway, risking a systematic bias by rare and atypical samples. The annealed approximation is known to be exact for certain models and in certain circumstances, but it is used outside those circumstances -without much reflection \cite{Wainrib_2013_Topological, +without much reflection \cite{Wainrib_2013_Topological, Kent-Dobias_2021_Complex, Gershenzon_2023_On-Site}. In a few cases researches have made instead the better-controlled quenched average, which averages the logarithm of the number of stationary points, and find deviations from the annealed approximation with important implications for the system's behavior \cite{Muller_2006_Marginal, -Ros_2019_Complexity, Kent-Dobias_2023_How, Ros_2023_Quenched}. Generically, +Ros_2019_Complex, Kent-Dobias_2023_How, Ros_2023_Quenched}. Generically, the annealed approximation to the complexity is wrong when a nonvanishing fraction of pairs of stationary points have nontrivial correlations in their mutual position. @@ -386,8 +388,8 @@ proportional to -2(f''-f')u_fw_f -2\log^2\frac{f''}{f'}f'^2f''v_f \end{equation} -If $G_f>0$, then the bifurcating solutions exist, and there is someplace where -the annealed solution is corrected by a {\oldstylenums1\textsc{rsb}} solution. +If $G_f>0$, then the bifurcating solutions exist, and there are some saddles whose +complexity is corrected by a {\oldstylenums1\textsc{rsb}} solution. Therefore, $G_f>0$ is a condition to see {\oldstylenums1}\textsc{rsb} in the complexity. If $G_f<0$, then there is nowhere along the extremal line where saddles can be described by such a complexity. The range of $3+s$ models where -- cgit v1.2.3-70-g09d2