THE OVERLAP GAP PROPERTY AND APPROXIMATE MESSAGE PASSING ALGORITHMS FOR p-SPIN MODELS

• 成果类型: Article
• 署名作者: Gamarnik, David; Jagannath, Aukosh
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Waterloo
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/20-AOP1448
• 发表日期: 2021
• 页码: 180-205
• 关键词: local algorithms; state evolution

摘要

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 >= 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 >= 4.