The Overlap Gap Property For Inference: Power And Limitations
summary
Claim: the overlap gap property (OGP) for inference predicts where efficient algorithms fail by testing monotonicity of a restricted optimization curve (overlap vs best loss) and is equivalent to a spectral monotonicity condition. Tools: a mix of first and second moment methods plus concentration and spectral arguments. Results: sparse regression shows a sharp algorithmic vs information-theoretic split (proven non‑monotonicity implies hardness); planted clique forces over-parameterization and reveals an unexpected n^{2/3} transition; OGP rules out many MCMC-style approaches but leaves open extensions to stable algorithms and constructive no‑OGP methods.
AI-written summary · about
chapters (10)
- 0:00Start
- 0:45Introduction
- 3:17OGP for random optimization
- 7:04This talk: a short survey
- 11:54The OGP for Inference - part 2
- 15:50The Sparse Regression Model
- 16:37Computational Statistical Gap
- 18:28The OGP for Regression - Phase Transition
- 20:55The Planted Clique Model - Brief Literature Review
- 24:05The Planted Clique Model - First moment OGP diagram
related talks
38mSome Easy Optimization Problems Have the Overlap-Gap Property
34mFree Energy Wells and Overlap Gap Property in Sparse PCA
33mA Few Connections Between Optimization and Probability
39mThe Overlap Gap Property in Principal Submatrix Recovery
01h 01mRobustness, Stochastics, Uncertainty 2
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
58mContinuous Methods 2
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms