diff options
| -rw-r--r-- | marginal.bib | 34 | ||||
| -rw-r--r-- | marginal.tex | 21 |
2 files changed, 54 insertions, 1 deletions
diff --git a/marginal.bib b/marginal.bib index 4398380..5f4dbfc 100644 --- a/marginal.bib +++ b/marginal.bib @@ -236,6 +236,19 @@ doi = {10.1214/21-aop1519} } +@inproceedings{ElAlaoui_2022_Sampling, + author = {El Alaoui, Ahmed and Montanari, Andrea and Sellke, Mark}, + title = {Sampling from the {Sherrington}-{Kirkpatrick} Gibbs measure via algorithmic stochastic localization}, + publisher = {IEEE}, + year = {2022}, + month = {10}, + pages = {323--334}, + url = {https://doi.org/10.1109%2Ffocs54457.2022.00038}, + doi = {10.1109/focs54457.2022.00038}, + address = {Denver, CO, USA}, + booktitle = {2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)} +} + @article{Foini_2012_On, author = {Foini, Laura and Krzakala, Florent and Zamponi, Francesco}, title = {On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory}, @@ -521,6 +534,12 @@ title = {Conditioning the complexity of random landscapes on marginal optima} } +@misc{Kent-Dobias_2024_least-squares, + author = {Kent-Dobias, Jaron}, + url = {https://github.com/kentdobias/least_squares/releases/tag/marginal_paper}, + howpublished = {\url{https://github.com/kentdobias/least_squares/releases/tag/marginal_paper}} +} + @article{Krzakala_2007_Landscape, author = {Krzakala, Florent and Kurchan, Jorge}, title = {Landscape analysis of constraint satisfaction problems}, @@ -590,6 +609,19 @@ doi = {10.1103/physrevlett.75.2847} } +@article{Montanari_2021_Optimization, + author = {Montanari, Andrea}, + title = {Optimization of the {Sherrington}--{Kirkpatrick} {Hamiltonian}}, + journal = {SIAM Journal on Computing}, + publisher = {Society for Industrial & Applied Mathematics (SIAM)}, + year = {2021}, + month = {January}, + pages = {FOCS19--38}, + url = {http://dx.doi.org/10.1137/20M132016X}, + doi = {10.1137/20m132016x}, + issn = {1095-7111} +} + @unpublished{Montanari_2023_Solving, author = {Montanari, Andrea and Subag, Eliran}, title = {Solving overparametrized systems of random equations: I. Model and algorithms for approximate solutions}, @@ -716,7 +748,7 @@ @article{Tange_2011_GNU, author = {Tange, Ole}, - title = {GNU Parallel: The Command-Line Power Tool}, + title = {{GNU} Parallel: The Command-Line Power Tool}, journal = {;login: The USENIX Magazine}, year = {2011}, month = {2}, diff --git a/marginal.tex b/marginal.tex index 4ac383d..0db0e10 100644 --- a/marginal.tex +++ b/marginal.tex @@ -1662,6 +1662,27 @@ still in its infancy \cite{Urbani_2024_Statistical}. \appendix +\section{Relationship with previous work} + +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, 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 not the typical ones that are marginal in the sense of +\citeauthor{Muller_2006_Marginal}. + \section{A primer on superspace} \label{sec:superspace} |