Thresholds of Descending Algorithms in Inference Problems

on YouTube ↗35m

" summary

Shows explicit calculation of the critical signal-to-noise value where simple descent methods stop recovering planted structure, giving closed-form thresholds for models like the spiked tensor model and low-rank matrices. Uses random matrix theory and the replica/energy-landscape picture to derive a gap between the information-theoretic limit and the gradient descent threshold, constructs synthetic Gaussian instances, runs numerical experiments over system sizes up to a few thousand, and demonstrates descent iterates get trapped before the analytic threshold — matching theory and simulations.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 11:56Phase diagram AMP
3. 14:20Phase diagram Langevin algorithm
4. 17:44Phase diagram gradient flow

" related talks

• 38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix EstimationCynthia Rush · Rigorous Evidence for Information-Computation Trade-offs
• 45mPhase Transitions in Low-Rank Matrix EstimationFlorent Krzakala · 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)
• 36mTo Be (Hard) or Not Be:...Florent Krzakala · Rigorous Evidence for Information-Computation Trade-offs
• 01h 20mThe elusive generalization: classical bounds to double descent to grokkingMisha Belkin · Modern Paradigms in Generalization Boot Camp 2024
• 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
• 15mExploring the math of thresholdsEmmanuel Bakare · Conf42 Platform Engineering 2025