Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses
Brice Huang, Mark Sellke
Abstract
We study the problem of algorithmically optimizing the Hamiltonian of a spherical or Ising mean field spin glass. The maximum asymptotic value OPT of this random function is characterized by a variational principle known as the Parisi formula, proved first by Talagrand and in more generality by Panchenko. Recently developed approximate message passing algorithms efficiently optimize these functions up to a value ALG given by an extended Parisi formula, which minimizes over a larger space of functional order parameters. These two objectives are equal for spin glasses exhibiting a no overlap gap property. However, ALG can be strictly smaller than OPT, and no efficient algorithm producing a value exceeding ALG is known. We prove that when all interactions have even degree, no algorithm satisfying an overlap concentration property can produce an objective larger than ALG with non-negligible probability. This property holds for all algorithms with suitably Lipschitz dependence on the random disorder coefficients of the objective. It encompasses natural formulations of gradient descent, approximate message passing, and Langevin dynamics run for bounded time and in particular includes the algorithms achieving ALG mentioned above. To prove this result, we substantially generalize the overlap gap property framework introduced by Gamarnik and Sudan to arbitrary ultrametric forbidden structures of solutions.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
12 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster cites Frozen 1-RSB structure of the symmetric Ising perceptron
- Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster cites Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
- Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models cites Low-Degree Hardness of Random Optimization Problems
- Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization cites Low-Degree Hardness of Random Optimization Problems
- Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization cites The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
- Low-Degree Hardness of Random Optimization Problems cites The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
- The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials cites Low-Degree Hardness of Random Optimization Problems
- Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron cites Frozen 1-RSB structure of the symmetric Ising perceptron
- Algorithms and Barriers in the Symmetric Binary Perceptron Model cites Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
- Algorithms and Barriers in the Symmetric Binary Perceptron Model cites Frozen 1-RSB structure of the symmetric Ising perceptron
- Algorithms and Barriers in the Symmetric Binary Perceptron Model cites Low-Degree Hardness of Random Optimization Problems
- Algorithms and Barriers in the Symmetric Binary Perceptron Model cites Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
- Algorithms and Barriers in the Symmetric Binary Perceptron Model cites The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
- The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials cites Frozen 1-RSB structure of the symmetric Ising perceptron
- The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials cites Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
Cited by top-tier papers12
- Low-Degree Hardness of Random Optimization ProblemsDavid Gamarnik, Aukosh Jagannath, Alexander S. WeinFOCS 2020 · 48 citations
- The Algorithmic Phase Transition of Random k-SAT for Low Degree PolynomialsGuy Bresler, Brice HuangFOCS 2021 · 32 citations
- Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationAhmed El Alaoui, Andrea Montanari, Mark SellkeFOCS 2022 · 29 citations
- Algorithms and Barriers in the Symmetric Binary Perceptron ModelDavid Gamarnik, Eren C. Kizildag, Will Perkins, Changji XuFOCS 2022 · 26 citations
- Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass modelsJoao Basso, David Gamarnik, Song Mei, Leo ZhouFOCS 2022 · 25 citations
Builds on4
- Low-Degree Hardness of Random Optimization ProblemsDavid Gamarnik, Aukosh Jagannath, Alexander S. WeinFOCS 2020 · 48 citations
- Frozen 1-RSB structure of the symmetric Ising perceptronWill Perkins, Changji XuSTOC 2021 · 31 citations
- Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric PerceptronEmmanuel Abbe, Shuangping Li, Allan SlyFOCS 2021 · 27 citations
- Binary perceptron: efficient algorithms can find solutions in a rare well-connected clusterEmmanuel Abbe, Shuangping Li, Allan SlySTOC 2022 · 23 citations
Related papers
- Mean-field Underdamped Langevin Dynamics and its Spacetime DiscretizationQiang Fu, Ashia Camage WilsonICML 2024 · 5 citations
- On the hardness of finding balanced independent sets in random bipartite graphsWill Perkins, Yuzhou WangSODA 2024 · 2 citations
- Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gapLuca Pesce, Bruno Loureiro, Florent Krzakala, Lenka ZdeborováNeurIPS 2022 · 4 citations
- Symmetric Mean-field Langevin Dynamics for Distributional Minimax ProblemsJuno Kim, Kakei Yamamoto, Kazusato Oko, Zhuoran Yang et al.ICLR 2024 · 14 citations
- Optimal Algorithms for the Inhomogeneous Spiked Wigner ModelAleksandr Pak, Justin Ko, Florent KrzakalaNeurIPS 2023 · 17 citations
