Optimization of mean-field spin glass Hamiltonians

Abstract: We consider the question of computing an approximate ground state configuration of an Ising (mixed) p-spin Hamiltonian H_N from a bounded number of gradient evaluations.

I will present an efficient algorithm which exploits the ultrametric structure of the superlevel sets of H_N in order to achieve an energy E_* characterized via an extended Parisi variational principle. This energy E_* is optimal when the model satisfies a `no overlap gap’ condition. At the heart of this algorithmic approach is a stochastic control problem, whose dual turns out to be the Parisi formula, thereby shedding new light on the nature of the latter.

This is joint work with Andrea Montanari and Mark Sellke.

optimization and controlstatistics theory

Audience: researchers in the topic

MAD+

Series comments: Description: Research seminar on data science

See here for Zoom links to individual seminars, links to recordings, and to subscribe to calendar or mailing list.