SUDAKOV-FERNIQUE POST-AMP, AND A NEW PROOF OF THE LOCAL CONVEXITY OF THE TAP FREE ENERGY

• 成果类型: Article
• 署名作者: Elentano, Michael
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/23-AOP1675
• 发表日期: 2024
• 页码: 923-954
• 关键词: state evolution

摘要

We develop an approach for studying the local convexity of a certain class of random objectives around the iterates of an AMP algorithm. Our approach involves applying the Sudakov-Fernique inequality conditionally on a long sequence of AMP iterates, and our main contribution is to demonstrate the way in which the resulting objective can be simplified and analyzed. As a consequence, we provide a new, and arguably simpler, proof of some of the results of Celentano, Fan and Mei ( Ann. Statist. 51 (2023) 519-546), which establishes that the so-called TAP free energy in the Z 2 -synchronization problem is locally convex in the region to which AMP converges. We further prove a conjecture of Alaoui, Montanari and Sellke (In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science-FOCS 2022 (2022) 323-334 IEEE Computer Soc.) involving the local convexity of a related but distinct TAP free energy, which as a consequence, confirms that their algorithm efficiently samples from the Sherrington-Kirkpatrick Gibbs measure throughout the easy regime.