Potential Hessian Ascent: The Sherrington-Kirkpatrick Model

Abstract: We provide the first iterative spectral algorithm to find near-optima of a random quadratic objective over the discrete hypercube. The algorithm is a randomized Hessian ascent in the solid cube, where we modify the objective by subtracting a specific instance-independent potential function [Chen et al., Communications on Pure and Applied Mathematics, 76(7), 2023]. This extends Subag's algorithmic program of Hessian ascent from the sphere [Subag, Communications on Pure and Applied Mathematics, 74(5), 2021] to the more complex geometry of the cube. Utilizing tools from free probability theory, we construct an approximate projector into the top-eigenspaces of the Hessian with well-behaved diagonal entries, and use it as the covariance matrix for the random increments. With high probability, the empirical distribution of the iterates approximates the solution to the primal version of the Auffinger-Chen SDE [Auffinger et al., Communications in Mathematical Physics, 335, 2015]. We then bound the change to the modified objective function for every iterate via a Taylor expansion whose derivatives are controlled using various Gaussian concentration bounds and smoothness properties of (a semiconcave regularization of) the Fenchel-Legendre dual to the solution of the Parisi PDE. These results lay the groundwork for demonstrating the (possible) existence of low-degree sum-of-squares certificates over high-entropy step distributions for a relaxed version of the Parisi formula [Open Question 1.8, arXiv:2401.14383].