From 446304c5160e2d6aa2bf21f25fb8785670e3e677 Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Mon, 1 Jul 2024 15:08:49 +0200
Subject: Added small appendix to discuss relationship with Muller et al

---
 marginal.bib | 34 +++++++++++++++++++++++++++++++++-
 marginal.tex | 21 +++++++++++++++++++++
 2 files changed, 54 insertions(+), 1 deletion(-)

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}
 
-- 
cgit v1.2.3-70-g09d2