Optimization of Full-RSB Spherical Spin Glasses
summary
Proves an explicit polynomial-time algorithm (time ~n^p up to ε-dependent constants) that, under the concave mixture condition equivalent to Parisi support = [0,1], constructs a path of radius-increasing vectors and reaches energy within ε of the maximum with high probability. The algorithm repeatedly takes orthogonal iterative Hessian steps: at each small step choose a unit direction orthogonal to the current point (and gradient) that maximizes the Hessian quadratic form on the tangent, then advance. Requires nonzero C2 and uses uniform spectral control of the restricted Hessian.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:36Basic examples: pure p-spin
- 4:41Mixed p-spin models
- 6:00Optimization of full-RSB mixtures
- 10:01Negative results
- 11:05The ultrametric tree at zero temp.
- 16:10One path from the tree in full-RSB
- 17:47Constructing a good path
- 19:27Algorithm
- 25:35Proof sketch
related talks
24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
26mTight Algorithmic Thresholds for Spin Glass Hamiltonians
59mOptimizing Noncommutative Polynomials: The SYK Model
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
01h 18mStatistical Physics and Computation in High Dimension
29mApproximating Spherical Gaussian Mixtures
01h 11mOptimization and Sampling Under Symmetry: Part 1 -- Examples
01h 10mOptimization II