Free Energy Wells and Overlap Gap Property in Sparse PCA

on YouTube ↗34m

" summary

Analyzes sparse Principal Component Analysis (sparse PCA) in the sparse Rademacher spike model, examining how free energy wells and the Overlap Gap Property (OGP) relate to algorithmic hardness. Uses statistical physics concepts (free energy wells) and the OGP framework to identify regimes where polynomial-time algorithms fail versus succeed for recovering the sparse spike.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 2:45The Sparse PCA Model - Literature
3. 5:17The Sparse PCA Model - Sub-exponential time method
4. 8:05Stationary distributions: Gibbs measures
5. 11:22Free Energy Wells (FEW) from Statistical Physics
6. 14:03A deep FEW slows MCMC methods
7. 21:24Main Result on FEW
8. 23:24Proof Sketch
9. 26:12Summary/Future Work

" related talks

• 39mMemory Limited, Streaming PCAConstantine Caramanis · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 36mThe Overlap Gap Property For Inference: Power And LimitationsIlias Zadik · Rigorous Evidence for Information-Computation Trade-offs
• 28mRandomized Constrained Matrix DecompositionsBenjamin Erichson · Randomized Numerical Linear Algebra and Applications 2018
• 01h 06mTutorial: Methods from Statistical Physics IIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 29mAre Generative Models The New Sparsity?Bruno Loureiro · Rigorous Evidence for Information-Computation Trade-offs
• 24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin GlassesChris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi · ITCS 2023
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 49mRobust PCA via Non-convex Methods: Provable BoundsAnimashree Anandkumar · Semidefinite Optimization, Approximation and Applications 2014