Sébastien Bubeck – Publications by Topics
Lecture Notes, Survey, PhD Thesis
M. Racz and S. Bubeck, Basic models and questions in statistical network analysis. Statist. Surv. 11 (2017), 1–47. [arxiv]
S. Bubeck, Convex Optimization: Algorithms and Complexity. In Foundations and Trends in Machine Learning, Vol. 8: No. 34, pp 231357, 2015 [pdf]
S. Bubeck, The complexities of optimization. Lecture notes, 2013. Available on my blog.
S. Bubeck and N. CesaBianchi, Regret Analysis of Stochastic and Nonstochastic Multiarmed Bandit Problems. In Foundations and Trends in Machine Learning, Vol 5: No 1, 1122, 2012. [pdf]
S. Bubeck, Introduction to Online Optimization. Lecture Notes, 2011. [draft]
S. Bubeck, Bandits Games and Clustering Foundations. PhD dissertation, Université Lille 1, 2010 (Jacques Neveu prize 2010, runnerup for the french AI prize 2011, runnerup for the Gilles Kahn prize 2010). [pdf] [slides of the defense] [slides of my jobtalk] [slides for the Gilles Kahn prize]
Various math topics (combinatorics, geometric probability, information theory)
O. Angel, S. Bubeck, Y. Peres and F. Wei, Local maxcut in smoothed polynomial time. STOC 2017. [arxiv]
S. Bubeck, K. Edwards, H. Mania and C. Supko, On paths, stars and wyes in trees. Draft, 2016. [arxiv]
S. Bubeck and S. Ganguly, Entropic CLT and phase transition in highdimensional Wishart matrices. To appear in International Mathematics Research Notices, 2015. [arxiv]
S. Bubeck and E. Gwynne, Asymptotic behavior of the Eden model with positively homogeneous edge weights. Draft, 2015. [arxiv]
S. Bubeck and N. Linial, On the local profiles of trees. Journal of Graph Theory, 2015. [draft]
Adversarial examples in machine learning
H. Salman, G. Yang, J. Li, P. Zhang, H. Zhang, I. Razenshteyn, S. Bubeck, Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. In submission. [arxiv]
S. Bubeck, Y.T. Lee, E. Price, I. Razenshteyn, Adversarial Examples from Cryptographic PseudoRandom Generators. (merged with paper below) [arxiv]
S. Bubeck, E. Price, I. Razenshteyn, Adversarial examples from computational constraints. ICML 2019 [arxiv]
Competitive analysis in online algorithms
S. Bubeck and Y. Rabani, Parametrized Metrical Task Systems. In submission. [arxiv]
S. Bubeck, B. Klartag, Y.T. Lee, Y. Li, M. Sellke, Chasing Nested Convex Bodies Nearly Optimally. In submission. [arxiv]
S. Bubeck, Y.T. Lee, Y. Li, M. Sellke, Competitively Chasing Convex Bodies. STOC 2019. [arxiv]
S. Bubeck, M. B. Cohen, J. R. Lee, Y.T. Lee, Metrical task systems on trees via mirror descent and unfair gluing. SODA 2019. [arxiv]
C.J. Argue, S. Bubeck, M. B. Cohen, A. Gupta, Y.T. Lee, Nearly linear competitive ratio for chasing nested convex bodies. SODA 2019. [arxiv]
S. Bubeck, M. B. Cohen, J. R. Lee, Y.T. Lee, A. Madry, kserver via multiscale entropic regularization. STOC 2018. [arxiv]
Convex optimization
S. Bubeck, Q. Jiang, Y.T. Lee, Y. Li, A. Sidford, Complexity of Highly Parallel NonSmooth Convex Optimization. In submission. [arxiv]
S. Bubeck, Q. Jiang, Y.T. Lee, Y. Li, A. Sidford, Nearoptimal method for highly smooth convex optimization. COLT 2019. [arxiv]
K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, L. Massoulié, Optimal Algorithms for NonSmooth Distributed Optimization in Networks. NeurIPS 2018 (Best Paper Award) [arxiv]
S. Bubeck, M. B. Cohen, Y.T. Lee, Y. Li, An homotopy method for ell_p regression provably beyond selfconcordance and in inputsparsity time. STOC 2018. [arxiv]
K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, L. Massoulié, Optimal algorithms for smooth and strongly convex distributed optimization in networks. ICML 2017 [arxiv]
S. Bubeck, R. Eldan and Y. T. Lee, Kernelbased methods for bandit convex optimization. Extended abstract in STOC 2017. [arxiv]
S. Bubeck and R. Eldan, Multiscale exploration of convex functions and bandit convex optimization. Extended abstract in COLT 2016 (Best Paper Award), long version to appear in Mathematical Statistics and Learning. [arxiv]
S. Bubeck and Y. T. Lee, Blackbox optimization with a politician. ICML 2016. [arxiv]
S. Bubeck, Y.T. Lee, and M. Singh, A geometric alternative to Nesterov's accelerated gradient descent. Draft, 2015. [draft]
S. Bubeck, J. Lehec, and R. Eldan, Sampling from a logconcave distribution with Projected Langevin Monte Carlo. Extended abstract in NIPS 2015, long version to appear in Discrete & Computational Geometry. [arxiv]
S. Bubeck, O. Dekel, T. Koren and Y. Peres, Bandit Convex Optimization: sqrt{T} Regret in One Dimension. COLT 2015. [arxiv]
S. Bubeck and R. Eldan, The entropic barrier: a simple and optimal universal selfconcordant barrier. Extended abstract in COLT 2015, long version to appear in Mathematics of Operations Research. [arxiv]
Multiarmed bandit
S. Bubeck, Y. Li, Y. Peres, M. Sellke, NonStochastic MultiPlayer MultiArmed Bandits: Optimal Rate With Collision Information, Sublinear Without. In submission. [arxiv]
S. Bubeck and M. Sellke, FirstOrder Regret Analysis of Thompson Sampling. In submission. [arxiv]
S. Bubeck, Y. Li, H. Luo, C.Y. Wei, Improved Pathlength Regret Bounds for Bandits. COLT 2019. [arxiv]
Z. AllenZhu, S. Bubeck, and Y. Li, Make the Minority Great Again: FirstOrder Regret Bound for Contextual Bandits. NeurIPS 2018. [arxiv]
S. Bubeck, M. B. Cohen, Y. Li, Sparsity, variance and curvature in multiarmed bandits . ALT 2018 (Best Student Paper Award). [arxiv]
S. Bubeck, N. R. Devanur, Z. Huang, R. Niazadeh, Online Auctions and Multiscale Online Learning. EC 2017 [arxiv]
S. Bubeck and C.Y. Liu, Priorfree and priordependent regret bounds for Thompson Sampling . NIPS 2013. [pdf] [Supp. material]
S. Bubeck, V. Perchet and P. Rigollet, Bounded regret in stochastic multiarmed bandits. COLT 2013. [pdf] [Video]
(Note: The proof of Theorem 8 is not correct. We do not know if the theorem holds true.)
S. Bubeck, N. CesaBianchi and G. Lugosi, Bandits with heavy tail. IEEE Transactions on Information Theory 59, 77117717, 2013. [pdf]
S. Bubeck and A. Slivkins, The best of both worlds: stochastic and adversarial bandits. COLT 2012. [pdf]
J.Y. Audibert and S. Bubeck, Regret Bounds and Minimax Policies under Partial Monitoring. Journal of Machine Learning Research (JMLR) 11, 26352686, 2010. [pdf]
J.Y. Audibert and S. Bubeck, Minimax Policies for Adversarial and Stochastic Bandits. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT), 2009 (Best Student Paper Award). [pdf] [slides]
Combinatorial statistics/statistical network analysis
S. Bubeck, J. Ding, R. Eldan and M. Racz, Testing for highdimensional geometry in random graphs. To appear in Random Structures and Algorithms, 2015. [draft]
S. Bubeck, L. Devroye and G. Lugosi, Finding Adam in random growing trees. To appear in Random Structures and Algorithms, 2015. [draft]
L. AddarioBerry, S. Bhamidi, S. Bubeck, L. Devroye, G. Lugosi, and R. Imbuzeiro Oliveira, Exceptional rotations of random graphs: a VC theory. Journal of Machine Learning Research (JMLR), 2015. [arxiv]
E. AriasCastro, S. Bubeck, G. Lugosi and N. Verzelen,
Detecting Markov Random Fields Hidden in White Noise. To appear in Bernoulli, 2015. [arxiv]
S. Bubeck, R. Eldan, E. Mossel and M. Racz, From trees to seeds: on the inference of the seed from large trees in the uniform attachment model. To appear in Bernoulli, 2014. [draft]
S. Bubeck, E. Mossel and M. Racz, On the influence of the seed graph in the preferential attachment model. IEEE Transactions on Network Science and Engineering 1, 3039, 2015. [arxiv]
E. AriasCastro, S. Bubeck and G. Lugosi, Detecting Positive Correlations in a Multivariate Sample. Bernoulli 21, 209241, 2015. [draft]
E. AriasCastro, S. Bubeck and G. Lugosi, Detection of correlations. Annals of Statistics 40, 412435, 2012. [pdf]
Linear bandit, Continuouslyarmed bandit
J.Y. Audibert, S. Bubeck and G. Lugosi, Regret in Online Combinatorial Optimization. Mathematics of Operations Research, 39, 3145, 2014. [pdf]
S. Bubeck, N. CesaBianchi and S. M. Kakade, Towards Minimax Policies for Online Linear Optimization with Bandit Feedback. COLT 2012. [pdf] [slides] [Video]
S. Bubeck, G. Stoltz and J. Y. Yu, Lipschitz Bandits without the Lipschitz Constant. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory (ALT), 2011. [pdf]
J.Y. Audibert, S. Bubeck and G. Lugosi, Minimax Policies for Combinatorial Prediction Games. COLT 2011. [pdf] [slides] [Video]
S. Bubeck, R. Munos, G. Stoltz and C. Szepesvari, XArmed Bandits. Journal of Machine Learning Research (JMLR) 12, 15871627, 2011. [pdf] [slides] [Video]
S. Bubeck and R. Munos, OpenLoop Optimistic Planning. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), 2010. [pdf] [slides]
S. Bubeck, R. Munos, G. Stoltz and C. Szepesvari, Online Optimization in XArmed Bandits. In Advances in Neural Information Processing Systems (NIPS) 22, 2009. [pdf] [Supp. material] [poster]
Stochastic optimization
C.Y. Liu and S. Bubeck, Most Correlated Arms Identification. COLT 2014. [draft]
K. Jamieson, M. Malloy, S. Bubeck and R. Nowak, lil’ UCB: An Optimal Exploration Algorithm for MultiArmed Bandits. COLT 2014. [draft]
K. Jamieson, M. Malloy, S. Bubeck and R. Nowak, On Finding the Largest Mean Among Many. Asilomar, 2013. [draft]
S. Bubeck, D. Ernst and A. Garivier, Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality. Journal of Machine Learning Research (JMLR), 14, 601623, 2013. [pdf]
S. Bubeck, T. Wang and N. Viswanathan, Multiple Identifications in MultiArmed Bandits. ICML 2013. [pdf]
S. Bubeck, D. Ernst and A. Garivier, Optimal discovery with probabilistic expert advice. 51st IEEE Conference on Decision and Control (CDC), 2012. [pdf] [Extended version]
V. Gabillon. M. Ghavamzadeh, A. Lazaric and S. Bubeck, MultiBandit Best Arm Identification. NIPS 2011. [pdf] [Tech. reportl]
J.Y. Audibert, S. Bubeck and R. Munos, Best Arm Identification in MultiArmed Bandits. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), 2010. [pdf] [slides]
J.Y. Audibert, S. Bubeck and R. Munos, Bandit View on Noisy Optimization. Chapter to appear in the book Optimization for Machine Learning, MIT press, 2010. [pdf]
S. Bubeck, R. Munos and G. Stoltz, Pure Exploration in FinitelyArmed and ContinuouslyArmed Bandits. Theoretical Computer Science 412, 18321852, 2011. [pdf]
S. Bubeck, R. Munos and G. Stoltz, Pure Exploration in MultiArmed Bandit Problems. In Proceedings of the 20th International Conference on Algorithmic Learning Theory (ALT), 2009. [pdf] [slides]
Clustering
S. Bubeck, M. Meila and U. von Luxburg, How the Initialization Affects the Stability of the kmeans Algorithm. ESAIM: Probability and Statistics 16, 436452, 2012. [pdf]
S. Bubeck and U. von Luxburg, Nearest Neighbor Clustering: A Baseline Method for Consistent Clustering with Arbitrary Objective Functions. Journal of Machine Learning Research (JMLR) 10, 657698, 2009. [pdf]
U. von Luxburg, S. Bubeck, S. Jegelka and M. Kaufmann, Consistent Minimization of Clustering Objective Functions. In Advances in Neural Information Processing Systems (NIPS) 21, 2008. [pdf] [Supp. material] [poster]
