How to Trap a Gradient Flow

Abstract:

In 1993, Stephen A. Vavasis proved that in any finite dimension, there exists a faster method than gradient descent to find stationary points of smooth non-convex functions. In dimension 2 he proved that 1/eps gradient queries are enough, and that 1/sqrt(eps) queries are necessary. We close this gap by providing an algorithm based on a new local-to-global phenomenon for smooth non-convex functions. Some higher dimensional results will also be discussed. I will also present an extension of the 1/sqrt(eps) lower bound to randomized algorithms, mainly as an excuse to discuss some beautiful topics such as Aldous’ 1983 paper on local minimization on the cube, and Benjamini-Pemantle-Peres’ 1998 construction of unpredictable walks.

Joint work with Dan Mikulincer

–

Bio:

Sébastien Bubeck is a Sr. Principal Research at Microsoft Research, Redmond. He has published two monographs, on the multi-armed bandit problem and on convex optimization. His papers on these topics have won awards at COLT, ALT, and NeurIPS. He is also interested in classical competitive analysis of online algorithms, information inequalities and their use in statistics/probability, and in the emerging field of adversarial examples.