4
[2311.09017] Semidefinite programs simulate approximate message passing robustly
source link: https://arxiv.org/abs/2311.09017
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 15 Nov 2023]
Semidefinite programs simulate approximate message passing robustly
Approximate message passing (AMP) is a family of iterative algorithms that generalize matrix power iteration. AMP algorithms are known to optimally solve many average-case optimization problems. In this paper, we show that a large class of AMP algorithms can be simulated in polynomial time by \emph{local statistics hierarchy} semidefinite programs (SDPs), even when an unknown principal minor of measure 1/polylog(dimension) is adversarially corrupted. Ours are the first robust guarantees for many of these problems. Further, our results offer an interesting counterpoint to strong lower bounds against less constrained SDP relaxations for average-case max-cut-gain (a.k.a. "optimizing the Sherrington-Kirkpatrick Hamiltonian") and other problems.
| Comments: | 50 pages |
| Subjects: | Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML) |
| Cite as: | arXiv:2311.09017 [cs.DS] |
| (or arXiv:2311.09017v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2311.09017 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK