Statistical Physics and Computation in High Dimension

on YouTube ↗01h 11m

" summary

Lecture contrasts exact limits and practical algorithms: replica and cavity methods give asymptotic mutual information and an information-theoretic recovery threshold (signal-to-noise ~ q log q), while polynomial algorithms stall at a higher threshold (empirically ~q^2). Concrete tools tested: Monte Carlo sampling (mixing too slow), Belief Propagation / AMP (works above q^2, tracked by state evolution), and a provable non-backtracking spectral algorithm whose leading eigenvector correlates with ground truth. Sum-of-squares, neural nets and quantum annealing also fail to beat the gap; planted-clique and tensor-spike examples show analogous barriers.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 5:33A simple example: Clustering
3. 7:35Stochastic Block Mode
4. 12:13Experiment: Monte-Carlo Markov Chai
5. 14:18Heuristic solution from statistical physic
6. 18:01Lineup of mathematical works
7. 20:59Asymptotic optimal overlap Information theoretic solution
8. 21:44Information Theoretic Transitio
9. 23:34Belief propagation
10. 26:41Yet sometimes, BP fails..
11. 27:54in fact, BP fails quite often!
12. 30:55Non-backtracking operator
13. 35:42Many attempts to beat the q? threshold
14. 37:44A bold conjecture
15. 38:51A variant: Planted Clique
16. 39:59"Balanced" Asymmetric Communiti
17. 46:49Intuition from physics
18. 52:18Scalings matter!
19. 55:33SPIKED TENSOR MODEL
20. 57:18IMPROVING ON BP/AMP ?

" related talks

• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 01h 10mLearning from Quantum ExperimentsRobert Huang · Quantum and Lattices Joint Reunion Workshop
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 01h 06mTutorial: Methods from Statistical Physics IIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022