The Overlap Gap Property in Principal Submatrix Recovery

on YouTube ↗39m

" summary

Model: n×n Gaussian matrix with an nρ×nρ planted submatrix of mean λ/n. Information-theoretic boundary shows approximate recovery threshold at λ about 2√(1/ρ · log(1/ρ)), while a naive spectral method needs λ ≳ 1/ρ. A Parisi‑style variational limit for a restricted likelihood reveals a non‑monotonic overlap curve (an overlap gap property) for intermediate λ ≈ ρ^{-1/2+α}, and that local Markov chains started near random overlap take exponential time to reach good overlap.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 0:52Premise
3. 1:44Structural Evidence
4. 7:03The Problem
5. 10:12Restricted likelihood
6. 25:20Local Markov chains
7. 27:10Scaling regimes
8. 29:10Random optimization

" related talks

• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 27mOptimal Spectral Recovery Of A Planted Vector In A SubspaceAlexander S Wein · Rigorous Evidence for Information-Computation Trade-offs
• 38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix EstimationCynthia Rush · Rigorous Evidence for Information-Computation Trade-offs
• 36mThe Overlap Gap Property For Inference: Power And LimitationsIlias Zadik · Rigorous Evidence for Information-Computation Trade-offs
• 23mHow Large is the Norm of a Random Matrix?Ramon van Handel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 39mMemory Limited, Streaming PCAConstantine Caramanis · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 31mPlanted Geometric Matching ProblemsDmitriy (Tim) Kunisky · Rigorous Evidence for Information-Computation Trade-offs
• 01h 31mUnsupervised LearningSantosh Vempala · The Brain and Computation Boot Camp