Algorithmic Thresholds for Mean-Field Spin Glasses

Zuvor findet vor dem Uhrturmhörsaal um 16.45 Uhr ein get-togehter statt.

Dr. Mark Sellke, Princeton/Amazon

High-dimensional optimization plays a crucial role in modern statistics and machine learning. I will present recent progress on optimization of mean-field spin glass Hamiltonians, a natural class of random non-convex functions. These functions have been studied in probability and physics for decades, and their optimization is related to problems such as clustering and spiked tensor estimation. We will see that a natural class of optimization algorithms, which includes general gradient-based methods on dimension-free time scales, "gets stuck" at an algorithmic threshold related to geometric properties of the landscape. In particular, we characterize when such algorithms can reach the true optimal objective value. Based on joint works with Ahmed El Alaoui, Brice Huang, and Andrea Montanari.