Semidefinite programs simulate approximate message passing robustly

Misha Ivkov, Tselil Schramm
11/15/2023
cs.DScs.LGmath.ST

No confident code implementation found for this paper.

Abstract

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/\mathrm{polylog}(\mathrm{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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

A non-asymptotic distributional theory of approximate message passing for sparse and robust regression

79% match2024

On Universality of Non-Separable Approximate Message Passing Algorithms

79% match2025

Approximate Message Passing for the Matrix Tensor Product Model

78% match2023

Robust Distribution Learning with Local and Global Adversarial Corruptions

78% match2024

Unifying AMP Algorithms for Rotationally-Invariant Models

78% match2024

A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classification

78% match2024

Cite this paper

@article{ivkov2023semidefinite,
  title  = {Semidefinite programs simulate approximate message passing robustly},
  author = {Misha Ivkov and Tselil Schramm},
  year   = {2023},
  eprint = {2311.09017},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2311.09017v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2311.09017.svg)](https://codeofpaper.com/paper/2311.09017)

Discussion