Incremental Approximate Message Passing
summary
A practical incremental AMP algorithm queries a gradient oracle O(poly(n,1/ε)) times (iterations about O(ε⁻²)), uses orthogonal updates and an Onsager reaction term to force independence, and its finite-iterate behavior follows state evolution. Design reduces to a stochastic control problem whose dual equals the Parisi functional (stochastic control / Parisi duality), so the AMP class provably attains the best achievable AMP energy; on the 3‑spin test it reaches ≈0.800 (better than Glauber ≈0.78) and is implemented and numerically validated.
AI-written summary · about
chapters (8)
- 0:00Start
- 7:54The Ising mixed p-spin Hamiltonian
- 11:14Convex relaxations
- 18:12Asymptotic value: Zero temperature Parisi formula
- 22:30Ultrametric structure
- 26:46Main result
- 42:01Choice of the non-linearities?
- 55:31Main message
related talks
49mApproximate Message Passing Algorithms For Orthogonally Invariant Models
58mUniversality of Approximate Message Passing on Semi-random Matrices
01h 08mTutorial: Methods from Statistical Physics III
27mThe Estimation Error of General First Order Methods
49mAnalysis of Algorithms on Dense Matrices using Approximate Message Passing
26mTight Algorithmic Thresholds for Spin Glass Hamiltonians
32mLocal Convexity Of The Tap Free Energy And Amp Convergence For Z2-Synchronization
01h 07mOptimization Crash Course (continued)