To Be (Hard) or Not Be:...

on YouTube ↗36m

" summary

Defines the spiked matrix-tensor model (rank‑one vector, noisy matrix plus p=3 tensor), computes the Bayes-optimal MMSE from the limiting free energy and matches it to a single-parameter order parameter, and shows approximate message passing attains that limit up to a sharp threshold via state-evolution. Empirical and analytic work with Langevin dynamics and gradient flow shows Langevin is much slower (likely superlinear or exponential) and gradient descent gets trapped until spurious minima turn into saddles; landscape analysis uses Kac-Rice count and replica symmetry–breaking intuition. Spectral initialization or ignoring the tensor first removes the practical hardness.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 2:18GENERIC QUESTIONS
3. 4:20SPIKED MATRIX-TENSOR PROBLE
4. 7:11OPTIMAL LEARNING
5. 11:16APPROXIMATE MESSAGE PASSIN AN ITERATIVE THRESHOLDING ALGORITHM
6. 11:52THE HARD PHASE OF AME
7. 14:13WHAT ABOUT PRACTICAL OFF-THE-SHELVES ALGORITHMS
8. 15:10LANGEVIN ALGORITHM
9. 17:36AMP SAMPLNG VS LANGEVIN SAMPLING
10. 17:50LANGEVIN STATE EVOLUTION (NUMERICAL SOLUTION)
11. 18:55A LANGEVIN PHASE TRANSITION
12. 20:05A PARISI-FRANZ VISION BEWARE: THIS SLIDE IS FOR REPLICA GEEKS
13. 22:14MLE AND MINIMIZATION
14. 22:33LANGEVIN STATE EVOLUTION ZERO TEMPERATURE LIMIT: GRADIENT FLOW
15. 23:03ANALYTICAL SOLUTION (LONG TIME EXTRAPOLATION)
16. 23:13ENERGY LANDSCAPE
17. 23:38LANDSCAPE & MINIMAS
18. 24:33LANDSCAPE ANALYSIS
19. 29:39ANALYTICAL SOLUTION (LANDCSAPE ANALYSIS)
20. 30:05CONCLUSIONS...
21. 30:39PERSPECTIVES?

" related talks

• 01h 06mTutorial: Methods from Statistical Physics IIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 45mTAP Free Energy, Spin Glasses, and Variational InferenceZhou Fan · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 35mThresholds of Descending Algorithms in Inference ProblemsStefano Sarao Mannelli · Computational Phase Transitions (Simons Institute, 2020)
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 25mFast Approximations of the Pattern Maximum Likelihood EstimatePascal Vontobel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 39mPhase Retrieval in High Dimensions: Statistical and Computational Phase TransitionsFlorent Krzakala · Computational Phase Transitions (Simons Institute, 2020)