Sébastien Bubeck – Old NewsMy best works have been around online decision making, with a couple of solutions to longstanding problems (minimax rate for multiarmed bandits and linear bandits at COLT 2009/COLT 2012/ALT 2018, best of both worlds for multiarmed bandits at COLT 2011, bandit convex optimization at COLT 2016/STOC 2017, progress on kserver and metrical task systems at STOC 2017/SODA 2018/STOC 2023, chasing convex bodies at STOC 2019, multiplayer multiarmed bandit at COLT 2020/COLT 2021, layered graph traversal in 2022). 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/NeurIPS 2019/ICML 2020) 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), smoothed analysis of local search (STOC 2017), and finding critical points on nonconvex functions in low dimensions (COLT 2020, ALT 2023). In 201920202021 I spent a lot of time thinking about adversarial examples in ML (computational complexity of adversarial examples at ICML 2019, more efficient randomized smoothing at NeurIPS 2019, construction of compact and smooth twolayer neural networks at NeurIPS 2020, law of robustness at COLT 2021 and NeurIPS 2021). In 2022 I started thinking more seriously about feature learning in neural networks. Shortest path without a map, but with an entropic regularizerIn shortest path without a map, a searcher tries to find a shortest path between a source and a target while the environment is revealed sequentially. Specifically, in layered graph traversal, the underlying graph is revealed layer by layer. The optimal randomized competitive ratio for this problem remained open since the original paper by Papadimitriou and Yannakakis in 1989. With Christian Coester and Yuval Rabani we resolved the problem using mirror descent, with the twist that the mirror map is evolving as the geometry of the space is being revealed, see the paper here. A law of robustness for neural networksWe proved with Mark Sellke that very large overparametrization is necessary for memorization of highdimensional data with a Lipschitz neural network, see the paper here and a more popular account of the result on Quanta magazine here. This work is a followup on a conjecture we had with Yuanzhi Li and Dheeraj Nagaraj for a more specific scenario (twolayer neural network and Gaussian data). The conjecture remains open in the sense that the result with Mark assumes nonexponential size weights, while for twolayer nets this assumption might be superfluous. Multiplayer multiarmed banditThe nonstochastic version of cooperative multiplayer multiarmed 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). In the stochastic case we proved that in fact one can get optimal regret without ANY collisions (see here for the multiarmed version). Chasing convex bodies competitivelyWith an extremely fun team of coauthors (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 kserver and metrical task systems with the multiscale entropyWith a fantastic team of coauthors (Michael Cohen, James R. Lee, Yin Tat Lee, Aleksander Madry) we improved the state of the art competitive ratio for kserver 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 kserver paper] itself. The [MTS paper] is finally online too, and it is a great start to get into this line of work. Polynomialtime algorithm for bandit convex optimizationFrom July 2014 to July 2016 with various coauthors 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
