All-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix Estimation

on YouTube ↗38m

" summary

Shows that rank‑1 sparse spiked matrix estimation exhibits sharp all‑or‑nothing phase transitions as sparsity rho→0 and SNR λ→∞: the information‑theoretic threshold occurs at λ scaling like (−log rho)/rho (proved when rho≫N^(−β)), while the computational threshold for recovery by approximate message passing sits at much larger λ (roughly ∝1/rho^2 when rho≫(log N)^(−α)), producing a diverging gap; proves the stat limit via adaptive interpolation and IMMSE and the algorithmic limit by finite‑sample state‑evolution concentration, with simulations matching the predicted MMSE jumps from 0 to 1.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:29Motivation
3. 3:17Sparse spiked Wigner matrix model
4. 5:03Related work
5. 11:01Statistical Limits and Phase Transitions
6. 12:37Computational Limits and Phase Transitions
7. 13:48Observed phase transitions
8. 17:23Regimes with phase transitions
9. 18:19All-or-nothing for the mutual information
10. 20:06All-or-nothing for the MMSE
11. 21:08All-or-nothing for the MSE of AMP
12. 22:07Computational-to-statistical gap
13. 25:52Methods for information theoretic results
14. 27:18Methods for computational results

" related talks

• 45mPhase Transitions in Low-Rank Matrix EstimationFlorent Krzakala · Random Instances and Phase Transitions (Simons Institute, 2016)
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 35mThresholds of Descending Algorithms in Inference ProblemsStefano Sarao Mannelli · Computational Phase Transitions (Simons Institute, 2020)
• 39mPhase Retrieval in High Dimensions: Statistical and Computational Phase TransitionsFlorent Krzakala · Computational Phase Transitions (Simons Institute, 2020)
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 46mSolvable Model of Unsupervised Feature LearningLenka Zdeborova · Random Instances and Phase Transitions (Simons Institute, 2016)