Tutorial: Methods from Statistical Physics III

on YouTube ↗01h 08m

" summary

Derives the AMP memory term by converting pairwise message passing on the complete graph into a bulk update, tracking backtracking loops and using A_ij ~ N(0,1/N) so state evolution yields Gaussian marginals; shows the Onsager term appears from two-step backtracks. Analyzes the symmetric perceptron (|·| version), counts solutions by first/second moment and identifies alpha_sat = -log 2 / log P(kappa); proves most solutions are isolated solutions with linear Hamming distance yet efficient heuristics like multi-scale majority and discrepancy methods locate rare clusters of many solutions, and proposes a local-entropy criterion for algorithmic hardness.

AI-written summary · about

" chapters (13)

1. 0:00Start
2. 2:00State Evolution
3. 3:12Message Passing
4. 14:35First Order Taylor Expansion of F
5. 22:36Perceptron Problem
6. 26:01The Satisfiability Threshold
7. 26:28Symmetric Perceptron
8. 27:49Moment Method
9. 32:25Count the Number of Solutions
10. 35:57Pity Segment Inequality
11. 37:26Second Moment
12. 49:10Majority Multi-Scale Majority Algorithm
13. 50:50Local Entropy

" related talks

• 01h 31mIncremental Approximate Message PassingAhmed El Alaoui · Computational Phase Transitions (Simons Institute, 2020)
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 49mApproximate Message Passing Algorithms For Orthogonally Invariant ModelsZhou Fan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 48mLearning by Local Entropy MaximizationRiccardo Zecchina · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013