Optimization of random polynomials on the sphere in the full-RSB regime

Optimization of random polynomials on the sphere in the full-RSB regime

-
Eliran Subag, Courant
Fine Hall 214

The talk will focus on optimization on the high-dimensional sphere when the objective function is a polynomial with independent Gaussian coefficients. Such random processes are called spherical spin glasses in physics, and have been extensively studied since the 80s. I will describe certain geometric properties of spherical spin glasses unique to the full-RSB case, and explain how they can be exploited to design a polynomial time algorithm that finds points within vanishing error from the global minimum.