The overlap gap property and approximate message passing algorithms for $p$-spin models
The Annals of Probability · 01.01.2021 · 49 (1) · 180-205
DOI: 10.1214/20-aop1448 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Annals of Probability, erschienen am 01.01.2021. Verfasst von David Gamarnik und 1 weiteren Autor:innen. Die Arbeit wurde bisher 41-mal zitiert (Crossref) und nennt 44 Literaturangaben.
Abstract (Originalsprache)
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 exhibit 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$.
Zitieren
APA
Gamarnik, D., & Jagannath, A. (2021). The overlap gap property and approximate message passing algorithms for $p$-spin models. The Annals of Probability, 49(1), 180-205. https://doi.org/10.1214/20-aop1448
Vancouver
Gamarnik D, Jagannath A. The overlap gap property and approximate message passing algorithms for $p$-spin models. The Annals of Probability. 2021;49(1):180-205. doi:10.1214/20-aop1448
BibTeX
@article{Gamarnik2021,
author = {Gamarnik, David and Jagannath, Aukosh},
title = {The overlap gap property and approximate message passing algorithms for $p$-spin models},
journal = {The Annals of Probability},
year = {2021},
volume = {49},
number = {1},
pages = {180--205},
doi = {10.1214/20-aop1448}
}
EUVIMED