Tight Algorithmic Thresholds for Spin Glass Hamiltonians
summary
Provides a tight characterization of the algorithmic threshold ALG for optimizing mean-field spin glass Hamiltonians (Ising and spherical, even-degree models only): any overlap-concentrated algorithm (AMP, gradient descent with constant iterations, etc.) cannot exceed ALG up to an exponentially small 1/n probability, and ALG arises from relaxing the Parisi variational problem to nonmonotone trial functions. Proof builds a branching overlap gap property using ultrametric trees, shows AMP can produce matching ultrametric outputs, and proves large full-binary subtrees are necessary to reach below ALG.
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:13Mean Field Spin Glass Hamiltonians
- 2:16Motivations for the Model
- 3:17The Parisi Formula
- 4:29A Look at the Landscape
- 5:09AMP Algorithms Succeed under No Overlap Gap
- 6:46Algorithmic Hardness from the Overlap Gap Property
- 7:39Overlap Gap Property for Spin Glasses: A Cartoon
- 8:22New Result: An Algorithmic Threshold
- 9:39Ultrametric Spaces and Trees
- 10:37Algorithms and Ultrametrics
- 11:37Branching OGP
- 13:31Overlap Concentrated Algorithms
- 15:25Ultrametric Transformations from Overlap Concentration
- 16:36Ruling Out a Complicated Ultrametric
- 22:29Conclusion
related talks
24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
33mOptimization of Full-RSB Spherical Spin Glasses
01h 31mIncremental Approximate Message Passing
01h 01mA Polynomial-time Algorithm for Finding Ground States of Gapped Local Hamiltonians in 1D
01h 18mStatistical Physics and Computation in High Dimension
43mApproximating 2-State Spin Systems
58mUniversality of Approximate Message Passing on Semi-random Matrices
38mSome Easy Optimization Problems Have the Overlap-Gap Property