Algorithmic Thresholds in Mean-Field Spin Glasses

Mark Sellke – Stanford University

Abstract

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 such problems 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 asymptotic optimality.

Additionally, I will briefly mention some of my other works in online decision making, adversarial robustness, and mixing/sampling.

The most relevant papers are https://arxiv.org/abs/1905.11968, https://arxiv.org/abs/2001.00904, and https://arxiv.org/abs/2110.07847