Analysis of Algorithms on Dense Matrices using Approximate Message Passing

on YouTube ↗49m

" summary

A specific algorithmic claim: iterating a centered, rescaled dense random matrix with a component-wise nonlinearity plus an explicit Onsager reaction term yields vectors whose coordinates converge to an IID Gaussian law described by a scalar state evolution. Rigorous proofs cover Gaussian matrices and polynomial nonlinearities; the reaction term exactly cancels reversing paths (leaving non-reversing trees), enabling CLT-style moments. Works empirically beyond polynomials and separability; proofs currently hold for any fixed number of iterations (breakdown expected near log N).

AI-written summary · about

" chapters (13)

1. 0:00Introduction and motivation
2. 1:03Sparse graph algorithms
3. 2:22Planted subgraph example
4. 6:08Belief propagation
5. 9:25Independent subtree analysis
6. 12:13Approximate message passing
7. 16:57Formalizing the AMP iteration
8. 21:00Gaussian convergence theorem
9. 24:21Conditioning technique
10. 28:57Complexity and stability
11. 32:36Proof for linear functions
12. 37:47Generalization to polynomials
13. 44:12Applications and open problems

" related talks

• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 49mApproximate Message Passing Algorithms For Orthogonally Invariant ModelsZhou Fan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 34mMatrix Martingales in Randomized Numerical Linear AlgebraRasmus Kyng · Randomized Numerical Linear Algebra and Applications 2018
• 29mImplementing Randomized Matrix Algorithms in Parallel and Distributed EnvironmentsMichael Mahoney · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 06mTutorial: Methods from Statistical Physics IIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 01h 31mPast, Present and Future of Randomized Numerical Linear Algebra IIMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013