Geometric Aspects of Optimization, Old and New

Mark Sellke – Stanford University


High-dimensional optimization plays a crucial role in modern statistics and machine learning. I will present recent progress on two problems in this area with connections to sequential decision making (part one), and optimization of random non-convex functions (part two).

The first part focuses on convex body chasing, which models convex optimization in a sequential and non-stationary setting. I will explain a solution to this problem based on the Steiner point from 19th century geometry. The resulting guarantee is exactly optimal in some sense and closes an exponential gap.

The second part concerns optimization of mean-field spin glass Hamiltonians, a family 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 “gets stuck” at an algorithmic threshold related to geometric properties of the landscape. This class of algorithms includes general gradient-based methods on dimension-free time scales. In particular, we determine when such algorithms can reach asymptotic optimality.

The most relevant papers are for the first part, and for the second part.