Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

How to Trap a Gradient Flow

April 24, 2020 @ 11:00 am - 12:00 pm

Sébastien Bubeck (Microsoft Research)


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
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.

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307