Statistical Physics and Computation in High Dimension

on YouTube ↗01h 04m

" summary

Covers the generalized linear model with five concrete cases: perceptron storage capacity (spherical capacity = 2, binary perceptron conjectured threshold ≈ 0.833), compressed sensing and sparse phase retrieval (AMP fails until ≈50% more measurements in some regimes), teacher–student classification (perfect recovery at α≈1.24 in theory), and random-feature/hidden-manifold models. Uses the replica method, replica formula proven rigorously only in Bayes‑optimal and convex ERM cases, derives state evolution for approximate message passing, and highlights a persistent hard phase where algorithms lag information-theoretic limits.

AI-written summary · about

" chapters (29)

1. 0:00Start
2. 0:30GRAPHICAL MODEL
3. 2:22PERCEPTRON STORAGE CAPACITY
4. 5:13COMPRESSED SENSING
5. 7:05TEACHER-STUDENT NEURAL NETWORK
6. 8:40GENERATIVE PRIORS
7. 10:31RANDOM FEATURE LEARNING
8. 12:04HIDDEN MANIFOLD MODEL
9. 14:38SPHERICAL PERCEPTRON
10. 18:13SYMMETRIC BINARY PERCEPTRONS
11. 20:06CAN SOLUTIONS BE FOUND EFFICIENTLY?
12. 23:27Are perceptrons with random labels relevant for learning with neural networks?
13. 24:33RADEMACHER COMPLEXITY
14. 26:41WHEN CAN A NEURAL NETWORK LEARN A TEACHER-NEURAL NETWORK
15. 27:29TEACHER STUDENT PERCEPTRON
16. 28:21Solved using the replica method in the high-dimensional limit
17. 29:26STATE-OR-THE-ART
18. 30:27BAYES-OPTIMAL GENERALIZATION
19. 32:18REPLICA METHOD SOLUTION
20. 33:30PROOF IDEA
21. 36:58APPROXIMATE MESSAGE PASSING
22. 39:33STATE EVOLUTION
23. 40:11SELECTED RELATED WORK
24. 40:43BOTTOM LINE
25. 43:39BAYES VS RISK MINIMISATION
26. 49:02SYMMETRIC-DOOR PERCEPTRON
27. 50:22PHASE DIAGRAM OF (NOISELESS) SPARSE LINEAR ESTIMATION
28. 51:19COMPRESSED PHASE RETRIEVAL
29. 54:16SOTA FOR PROOFS

" related talks

• 39mPhase Retrieval in High Dimensions: Statistical and Computational Phase TransitionsFlorent Krzakala · Computational Phase Transitions (Simons Institute, 2020)
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 01h 07mTheory of Computation IIChristos Papadimitriou · The Brain and Computation Boot Camp
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 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
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 48mLearning by Local Entropy MaximizationRiccardo Zecchina · Random Instances and Phase Transitions (Simons Institute, 2016)