Sébastien Bubeck

Portrait 
Senior Researcher

Machine Learning and Optimization, Microsoft Research, Redmond

Contact

Building 99, 3920

Redmond, WA 98052

sebubeck AT microsoft DOT com

Associate Editor for Mathematics of Operations Research.

Associate Editor for Mathematical Statistics and Learning (publisher: European Mathematical Society)

I was on the program committee for NIPS 2012, NIPS 2014, NIPS 2016, NIPS 2017, NeurIPS 2019 (senior area chair), COLT 2013 (PC and local organizer), COLT 2014 (PC and local organizer), COLT 2015, COLT 2016, COLT 2017, COLT 2018 (co-chair), COLT 2019, ICML 2015, ICML 2016, ICML 2017, SODA 2017, STOC 2020, Random 2017, ALT 2013, ALT 2014.

Steering committee member (elected) for COLT from 2014 to 2017.

I am interested in a variety of topics in theoretical computer science and machine learning.

My best works have been around online decision making, with a couple of solutions to long-standing problems (minimax rate for multi-armed bandits and linear bandits at COLT 2009/COLT 2012/ALT 2018, best of both worlds for multi-armed bandits at COLT 2011, bandit convex optimization at COLT 2016/STOC 2017, progress on k-server and metrical task systems at STOC 2017/SODA 2018, chasing convex bodies at STOC 2019, multiplayer multi-armed bandit currently under submission).

I also did a couple of works in convex optimization (entropic barrier at COLT 2015, geometric view on acceleration in 2015, optimal distributed rates at ICML 2017/NIPS 2018) and in network analysis (influence of the seed in preferential attachment graphs, and dimension estimation in random geometric graphs, work done in 2013/2014, appeared in Random Structures and Algorithms). Some other fun side projects included Langevin diffusion (NIPS 2015), entropic CLT (International Mathematics Research Notices 2016), and smoothed analysis of local search (STOC 2017).

NEW: Multiplayer multi-armed bandit

The non-stochastic version of cooperative multiplayer multi-armed bandit (with collisions) turns out to be a surprisingly challenging problem. In this first paper we obtain an optimal algorithm for the model with announced collisions. The model where collisions are not announced remains wide open (both from upper and lower bounds perspective).

Chasing convex bodies competitively

With an extremely fun team of co-authors (Yin Tat Lee, Yuanzhi Li, Mark Sellke) we finally managed to obtain a competitive algorithm for chasing convex bodies (after a couple of years of infructuous attempts), see also this youtube video. We also obtained a rather complete picture of the nested version of the problem. The latter approach was then used to obtain the optimal competitive ratio in this paper by Mark Sellke (see also this paper with very similar results).

A regularization approach for k-server and metrical task systems with the multiscale entropy

With a fantastic team of co-authors (Michael Cohen, James R. Lee, Yin Tat Lee, Aleksander Madry) we improved the state of the art competitive ratio for k-server and metrical task systems by using the mirror descent algorithm. To learn more about it I recommend to first take a look at this [youtube video], then these 3 blog posts ([part 1], [part 2], [part 3]) and finally [the k-server paper] itself. The [MTS paper] is finally online too, and it is a great start to get into this line of work.

Polynomial-time algorithm for bandit convex optimization

From July 2014 to July 2016 with various co-authors at MSR we dedicated a lot of energy to bandit convex optimization. The end product is a new efficient algorithm. To learn more about it I recommend to first take a look at this [youtube video], then these 3 blog posts ([part 1], [part 2], [part 3]), and finally [the paper] itself.

Research Interests

  • machine learning

  • theoretical computer science

  • convex optimization

  • multi-armed bandits

  • online algorithms (in particular metrical task systems and k-server)

  • statistical network analysis, random graphs and random matrices

  • applications of information theory to learning, optimization, and probability