Seminar by Mark Sellke

Please Note: This seminar will be given in person.

Algorithmic Thresholds for Spherical Spin Glasses

This talk focuses on optimizing the random and non-convex Hamiltonians of spherical spin glasses, a family of high-dimensional *random* non-convex functions. These functions have been studied in probability and physics for decades, and are closely related to modern problems such as spiked tensor estimation. We investigate the power of "stable" optimization algorithms to solve this problem, a class which includes general gradient-based methods on dimension-free time scales. Our results identify the optimal performance of such algorithms based on a geometric property of the landscape called the branching overlap gap property. Time permitting, I will discuss algorithmic thresholds for an extended family of problems where the true optimal objective value is not known in general. Based on joint work with Brice Huang.