The Estimation Error of General First Order Methods

on YouTube ↗27m

" summary

Claims a concrete lower bound: for fixed T and n,p →∞ any general first‑order method (matrix multiplies + coordinatewise nonlinearities) reduces any first‑order method to AMP and its asymptotic error is bounded below by the Bayes risk of a scalar Gaussian model whose noise variance comes from AMP state evolution. The proof maps regression instances to an infinite computation tree and compares AMP to belief propagation, exposing gaps (e.g. sparse phase retrieval needs substantially more samples than the information‑theoretic threshold).

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:51High-dimensional regression with initialization
3. 1:56Approximate message passing
4. 4:39First-order methods
5. 5:35General first order methods (GFOMs)
6. 6:54The GFOM lower bound
7. 9:14A comparison of two models
8. 12:30It suffices to consider only AMP algorithms
9. 13:41Description of asymptotic error (state evolution)
10. 15:42A statistical model
11. 18:572: Message passing algorithms
12. 20:094: Local Bayes risk Message passing algorithm is local
13. 22:14High dimensional regression and the computation tree
14. 22:52An example: sparse phase retrieval
15. 23:49Join us for hiking!

" related talks

• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022
• 01h 31mIncremental Approximate Message PassingAhmed El Alaoui · Computational Phase Transitions (Simons Institute, 2020)
• 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
• 48mExact Minimax Estimation for Phase SynchronizationChao Gao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 46mSolvable Model of Unsupervised Feature LearningLenka Zdeborova · Random Instances and Phase Transitions (Simons Institute, 2016)
• 37mEfficient Algorithms for Reliable Machine LearningAdam R. Klivans · The Role of TCS in Modern Machine Learning