Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
PreprintCited by 40Theoretical and Computational PhysicsConstraint Satisfaction and OptimizationRandom Matrices and Applications

The DOI matches its DataCite record.

The Overlap Gap Property and Approximate Message Passing Algorithms for $p$-spin models

Open access
Gamarnik, David, Jagannath, Aukosh·2019·arXiv
DOI 10.48550/arxiv.1911.06943arXiv 1911.06943
Open this paper in CoChat — free accountOpen PDF

Abstract

We consider the algorithmic problem of finding a near ground state (near optimal solution) of a $p$-spin model. We show that for a class of algorithms broadly defined as Approximate Message Passing (AMP), the presence of the Overlap Gap Property (OGP), appropriately defined, is a barrier. We conjecture that when $p\ge 4$ the model does indeed exhibits OGP (and prove it for the space of binary solutions). Assuming the validity of this conjecture, as an implication, the AMP fails to find near ground states in these models, per our result. We extend our result to the problem of finding pure states by means of Thouless, Anderson and Palmer (TAP) based iterations, which is yet another example of AMP type algorithms. We show that such iterations fail to find pure states approximately, subject to the conjecture that the space of pure states exhibits the OGP, appropriately stated, when $p\ge 4$.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1911.06943

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 40

  1. ACHLIOPTAS, D. and COJA-OGHLAN, A. (2008). Algorithmic barriers from phase transitions. In Founda- tions of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on 793-802. IEEE, New York.
  2. ACHLIOPTAS, D., COJA-OGHLAN, A. and RICCI-TERSENGHI, F. (2011). On the solution-space geometry of random constraint satisfaction problems. Random Structures Algorithms 38 251-268. MR2663730 https://doi.org/10.1002/rsa.20323 · DOI
  3. ADLER, R. J. and TAYLOR, J. E. (2007). Random Fields and Geometry. Springer Monographs in Mathe- matics. Springer, New York. MR2319516
  4. AUFFINGER, A. and CHEN, W.-K. (2015). On properties of Parisi measures. Probab. Theory Related Fields 161 817-850. MR3334282 https://doi.org/10.1007/s00440-014-0563-y · DOI
  5. AUFFINGER, A., CHEN, W.-K. and ZENG, Q. (2017). The SK model is full-step replica symmetry breaking at zero temperature. Preprint. Available at arXiv:1703.06872. · arXiv
  6. AUFFINGER, A. CHEN, W.-K. and ZENG, Q. (2020). The SK model is infinite step replica symmetry breaking at zero temperature. Comm. Pure Appl. Math. 73 921-943. https://doi.org/10.1002/cpa.21886 · DOI
  7. BAYATI, M., LELARGE, M. and MONTANARI, A. (2015). Universality in polytope phase transitions and message passing algorithms. Ann. Appl. Probab. 25 753-822. MR3313755 https://doi.org/10.1214/ 14-AAP1010 · DOI
  8. BAYATI, M. and MONTANARI, A. (2011). The dynamics of message passing on dense graphs, with appli- cations to compressed sensing. IEEE Trans. Inf. Theory 57 764-785. MR2810285 https://doi.org/10. 1109/TIT.2010.2094817 · DOI
  9. BEN AROUS, G., GHEISSARI, R. and JAGANNATH, A. (2020). Bounding flows for spherical spin glass dynamics. Comm. Math. Phys. 373 1011-1048. MR4061404 https://doi.org/10.1007/ s00220-019-03649-4 · DOI
  10. BEN AROUS, G. and JAGANNATH, A. (2018). Spectral gap estimates in mean field spin glasses. Comm. Math. Phys. 361 1-52. MR3825934 https://doi.org/10.1007/s00220-018-3152-6 · DOI
  11. BEN AROUS, G., GHEISSARI, R. and JAGANNATH, A. (2020). Algorithmic thresholds for tensor PCA. Ann. Probab. 48 2052-2087. https://doi.org/10.1214/19-AOP1415 · DOI
  12. BERTHIER, R., MONTANARI, A. and NGUYEN, P.-M. (2020). State evolution for approximate message passing with non-separable functions. Inf. Inference: A Journal of the IMA 9 33-79. MR4079177 https://doi.org/10.1093/imaiai/iay021 · DOI
  13. BOLTHAUSEN, E. (2014). An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model. Comm. Math. Phys. 325 333-366. MR3147441 https://doi.org/10. 1007/s00220-013-1862-3 · DOI
  14. CHEN, W.-K., GAMARNIK, D., PANCHENKO, D. and RAHMAN, M. (2019). Suboptimality of local algo- rithms for a class of max-cut problems. Ann. Probab. 47 1587-1618. MR3945754 https://doi.org/10. 1214/18-AOP1291 · DOI
  15. CHEN, W.-K., HANDSCHY, M. and LERMAN, G. (2018). On the energy landscape of the mixed even p-spin model. Probab. Theory Related Fields 171 53-95. MR3800830 https://doi.org/10.1007/ s00440-017-0773-1 · DOI
  16. COJA-OGHLAN, A. and EFTHYMIOU, C. (2011). On independent sets in random graphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms 136-144. SIAM, Philadel- phia, PA. MR2857116
  17. COJA-OGHLAN, A., HAQSHENAS, A. and HETTERICH, S. (2017). Walksat stalls well below satisfiability. SIAM J. Discrete Math. 31 1160-1173. MR3656499 https://doi.org/10.1137/16M1084158 · DOI
  18. DONOHO, D. L., MALEKI, A. and MONTANARI, A. (2009). Message-passing algorithms for compressed sensing. Proc. Natl. Acad. Sci. USA 106 18914-18919.
  19. EL ALAOUI, A., MONTANARI, A. and SELLKE, M. (2020). Optimization of mean-field spin glasses. Preprint. Available at arXiv:2001.00904. · arXiv
  20. GAMARNIK, D. and ILIAS, Z. (2017). High dimensional regression with binary coefficients. Estimating squared error and a phase transtition. In Conference on Learning Theory 948-953.
  21. GAMARNIK, D., JAGANNATH, A. and SEN, S. (2019). The overlap gap property in principal submatrix recovery. Preprint. Available at arXiv:1908.09959. · arXiv
  22. GAMARNIK, D., JAGANNATH, A. and WEIN, A. S. (2020). Low-degree hardness of random optimization problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). To appear.
  23. GAMARNIK, D. and KIZILDAG, E. (2018). Computing the partition function of the Sherrington-Kirkpatrick model is hard on average. Preprint. Available at arXiv:1810.05907. · arXiv
  24. GAMARNIK, D. and LI, Q. (2018). Finding a large submatrix of a Gaussian random matrix. Ann. Statist. 46 2511-2561. MR3851747 https://doi.org/10.1214/17-AOS1628 · DOI
  25. GAMARNIK, D. and SUDAN, M. (2017). Limits of local algorithms over sparse random graphs. Ann. Probab. 45 2353-2376. MR3693964 https://doi.org/10.1214/16-AOP1114 · DOI
  26. GAMARNIK, D. and SUDAN, M. (2017). Performance of sequential local algorithms for the random NAE- K-SAT problem. SIAM J. Comput. 46 590-619. MR3620150 https://doi.org/10.1137/140989728 · DOI
  27. JAGANNATH, A. and TOBASCO, I. (2016). A dynamic programming approach to the Parisi functional. Proc. Amer. Math. Soc. 144 3135-3150. MR3487243 https://doi.org/10.1090/proc/12968 · DOI
  28. JAGANNATH, A. and TOBASCO, I. (2017). Low temperature asymptotics of spherical mean field spin glasses. Comm. Math. Phys. 352 979-1017. MR3631397 https://doi.org/10.1007/s00220-017-2864-3 · DOI
  29. JAGANNATH, A. and TOBASCO, I. (2017). Some properties of the phase diagram for mixed p-spin glasses. Probab. Theory Related Fields 167 615-672. MR3627426 https://doi.org/10.1007/s00440-015-0691-z · DOI
  30. JAGANNATH, A. and TOBASCO, I. (2018). Bounds on the complexity of replica symmetry breaking for spherical spin glasses. Proc. Amer. Math. Soc. 146 3127-3142. MR3787372 https://doi.org/10.1090/ proc/13875 · DOI
  31. JAVANMARD, A. and MONTANARI, A. (2013). State evolution for general approximate message pass- ing algorithms, with applications to spatial coupling. Inf. Inference 2 115-144. MR3311445 https://doi.org/10.1093/imaiai/iat004 · DOI
  32. MÉZARD, M., MORA, T. and ZECCHINA, R. (2005). Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett. 94 197205. https://doi.org/10.1103/PhysRevLett.94.197205 · DOI
  33. MÉZARD, M., PARISI, G. and VIRASORO, M. A. (1987). Spin Glass Theory and Beyond. World Scientific Lecture Notes in Physics 9. World Scientific Co., Inc., Teaneck, NJ. MR1026102
  34. MONTANARI, A. (2019). Optimization of the Sherrington-Kirkpatrick Hamiltonian. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 1417-1433. IEEE, New York.
  35. PANCHENKO, D. (2013). The Sherrington-Kirkpatrick model. Springer Science & Business Media.
  36. RAHMAN, M. and VIRÁG, B. (2017). Local algorithms for independent sets are half-optimal. Ann. Probab. 45 1543-1577. MR3650409 https://doi.org/10.1214/16-AOP1094 · DOI
  37. SUBAG, E. (2017). The geometry of the Gibbs measure of pure spherical spin glasses. Invent. Math. 210 135-209. MR3698341 https://doi.org/10.1007/s00222-017-0726-4 · DOI
  38. TALAGRAND, M. (2006). Free energy of the spherical mean field model. Probab. Theory Related Fields 134 339-382. MR2226885 https://doi.org/10.1007/s00440-005-0433-8 · DOI
  39. TESCHL, G. (2012). Ordinary Differential Equations and Dynamical Systems. Graduate Studies in Mathe- matics 140. Amer. Math. Soc., Providence, RI. MR2961944 https://doi.org/10.1090/gsm/140 · DOI
  40. VERSHYNIN, R. (2018). High-Dimensional Probability. Cambridge Series in Statistical and Proba- bilistic Mathematics 47. Cambridge Univ. Press, Cambridge. MR3837109 https://doi.org/10.1017/ 9781108231596 · DOI

Cited by

See all 40

Metadata

Authors
Gamarnik, D., & Jagannath, A.
Affiliations
  • Massachusetts Institute of Technology (US)
  • University of Waterloo (CA)
ORCID
Gamarnik, David
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
49
Issue
1
Pages
180-205
ISSN
0091-1798 (ISSN-L)
DOI
10.48550/arxiv.1911.06943
arXiv
1911.06943
OpenAlex
W2987043130
Cited by
40
References
0
Citations by year
2026: 4 · 2025: 6 · 2024: 6 · 2023: 3 · 2022: 13 · 2021: 6 · 2020: 2
FWCI
2.94
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • The Annals of Probability (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Project Euclid (Cornell University) (submittedVersion)
  • DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1604232)
  • Natural Sciences and Engineering Research Council of Canada (dgecr-2020-00199, RGPIN 2020, rgpin-2020-04597, DGECR-2020)
  • Office of Naval Research (N00014-17-1-2790, N00014-17-1, N00014, N00014-17)
  • Office of International Science and Engineering
Topics
  • Physical Sciences › Physics and Astronomy › Condensed Matter Physics › Theoretical and Computational Physics
  • Physical Sciences › Computer Science › Artificial Intelligence › Constraint Satisfaction and Optimization
  • Physical Sciences › Mathematics › Statistics and Probability › Random Matrices and Applications
Keywords
overlap gap property, approximate message passing, p-spin model, spin glass, ground state search, pure states, binary solutions, combinatorial optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: The Overlap Gap Property and Approximate Message Passing Algorithms for $p$-spin models. https://app.cochat.ai/papers/10.48550/arxiv.1911.06943
The paper
Gamarnik, D., & Jagannath, A. (2019). The Overlap Gap Property and Approximate Message Passing Algorithms for $p$-spin models. arXiv. https://doi.org/10.48550/arxiv.1911.06943