Following the ground-states of full-RSB spherical spin glasses

Abstract

We focus on spherical spin glasses whose Parisi distribution has support of the form $[0,q]$. For such models we construct paths from the origin to the sphere which consistently remain close to the ground-state energy on the sphere of corresponding radius. The construction uses a greedy strategy, which always follows a direction corresponding to the most negative eigenvalues of the Hessian of the Hamiltonian. For finite mixtures $\nu (x)$ it provides an algorithm of time complexity $O(N^{\mathrm{deg}(\nu )})$ to find w.h.p. points with the ground-state energy, up to a small error. For the pure spherical models, the same algorithm reaches the energy $-E_{\infty }$, the conjectural terminal energy for gradient descent. Using the TAP formula for the free energy, for full-RSB models with support $[0,q]$, we are able to prove the correct lower bound on the free energy (namely, prove the lower bound from Parisi's formula), assuming the correctness of the Parisi formula only in the replica symmetric case.

References in corpus (8)

• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• Classical Particle in a Box with Random Potential: exploiting rotational symmetry of replicated Hamiltonian
• Low Temperature Asymptotics in Spherical Mean Field Spin Glasses
• Hessian spectrum at the global minimum of high-dimensional random landscapes
• On the Spectral Gap of Spherical Spin Glass Dynamics
• Aging and spin-glass dynamics
• Chaos in temperature in generic 2p-spin models
• Limiting dynamics for spherical models of spin glasses at high temperature

Cited by in corpus (8)

• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Algorithmic Thresholds in Mean Field Spin Glasses
• On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization
• The Overlap Gap Property in Principal Submatrix Recovery
• The Crisanti-Sommers Formula for Spherical Spin Glasses with Vector Spins
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• Breaking of 1RSB in random MAX-NAE-SAT
• On ${\ell }_p$-Gaussian-Grothendieck problem