Potential Hessian Ascent: The Sherrington-Kirkpatrick Model

David Jekel, Juspreet Singh Sandhu, Jonathan Shi

We present the first iterative spectral algorithm to find near-optimal solutions for a random quadratic objective over the discrete hypercube, resolving a conjecture of Subag [Suba…