EVENT DETAILS AND ABSTRACT

Title: Algorithmic Thresholds for Spin Glass Optimization
Speaker: Mark Sellke
Speaker Info: Harvard University
Brief Description: Algorithmic Thresholds for Spin Glass Optimization
Special Note:
Abstract:

I will present recent progress on non-convex optimization problems with random objectives in high dimension, focusing on the spherical spin glass. This model has been studied in probability and mathematical physics for decades and is a prototypical example of a disordered system. We will see that a natural class of stable optimization algorithms gets stuck at an algorithmic threshold which is characterized by geometric properties of the landscape. The algorithmic threshold value is efficiently attained by second-order ascent method of Subag, and by Langevin dynamics in the special case of pure models. The geometric description generalizes to other disordered systems, and enables computation of the algorithmic threshold even in cases where the (algorithmically unachievable) asymptotic maximum value is unknown.