Sébastien Bubeck – Publications

Lecture Notes, Survey, PhD Thesis

  • S. Bubeck, The complexities of optimization. Lecture notes, 2013. Available on my blog.

  • S. Bubeck and N. Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. In Foundations and Trends in Machine Learning, Vol 5: No 1, 1-122, 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, runner-up for the french AI prize 2011, runner-up for the Gilles Kahn prize 2010). [pdf] [slides of the defense] [slides of my jobtalk] [slides for the Gilles Kahn prize]

Preprints

  • S. Bubeck and R. Eldan, The entropic barrier: a simple and optimal universal self-concordant barrier. Preprint, 2014. [draft]

  • S. Bubeck, J. Ding, R. Eldan and M. Racz, Testing for high-dimensional geometry in random graphs. Submitted, 2014. [draft]

  • S. Bubeck, L. Devroye and G. Lugosi, Finding Adam in random growing trees. Submitted, 2014. [draft]

  • 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. Submitted, 2014. [draft]

  • S. Bubeck, Theory of Convex Optimization for Machine Learning. Submitted, 2014. [pdf]

  • S. Bubeck, E. Mossel and M. Racz, On the influence of the seed graph in the preferential attachment model. Submitted, 2014. [draft]

Journal Papers

  • S. Bubeck and N. Linial, On the local profiles of trees. Journal of Graph Theory (to appear), 2013. [draft]

  • E. Arias-Castro, S. Bubeck and G. Lugosi, Detecting Positive Correlations in a Multivariate Sample. To appear in Bernoulli, 2013. [pdf]

  • J.Y. Audibert, S. Bubeck and G. Lugosi, Regret in Online Combinatorial Optimization. Mathematics of Operations Research, 39, 31-45, 2014. [draft]

  • S. Bubeck, N. Cesa-Bianchi and G. Lugosi, Bandits with heavy tail. IEEE Transactions on Information Theory 59, 7711-7717, 2013. [pdf]

  • 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, 601-623, 2013. [pdf]

  • E. Arias-Castro, S. Bubeck and G. Lugosi, Detection of correlations. Annals of Statistics 40, 412-435, 2012. [pdf]

  • S. Bubeck, R. Munos, G. Stoltz and C. Szepesvari, X-Armed Bandits. Journal of Machine Learning Research (JMLR) 12, 1587-1627, 2011. [pdf] [slides] [Video]

  • J.Y. Audibert and S. Bubeck, Regret Bounds and Minimax Policies under Partial Monitoring. Journal of Machine Learning Research (JMLR) 11, 2635-2686, 2010. [pdf]

  • S. Bubeck, R. Munos and G. Stoltz, Pure Exploration in Finitely-Armed and Continuously-Armed Bandits. Theoretical Computer Science 412, 1832-1852, 2011. [pdf]

  • S. Bubeck, M. Meila and U. von Luxburg, How the Initialization Affects the Stability of the k-means Algorithm. ESAIM: Probability and Statistics 16, 436-452, 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, 657-698, 2009. [pdf]

Conference Papers

  • 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 Multi-Armed Bandits. COLT 2014. [draft]

  • S. Bubeck and C.Y. Liu, Prior-free and prior-dependent regret bounds for Thompson Sampling. NIPS 2013. [pdf] [Supp. material]

  • S. Bubeck, V. Perchet and P. Rigollet, Bounded regret in stochastic multi-armed 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, T. Wang and N. Viswanathan, Multiple Identifications in Multi-Armed Bandits. ICML 2013. [pdf]

  • S. Bubeck, N. Cesa-Bianchi and S. M. Kakade, Towards Minimax Policies for Online Linear Optimization with Bandit Feedback. COLT 2012. [pdf] [slides] [Video]

  • S. Bubeck and A. Slivkins, The best of both worlds: stochastic and adversarial bandits. COLT 2012. [pdf]

  • V. Gabillon. M. Ghavamzadeh, A. Lazaric and S. Bubeck, Multi-Bandit Best Arm Identification. NIPS 2011. [pdf] [Tech. reportl]

  • 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]

  • J.Y. Audibert, S. Bubeck and R. Munos, Best Arm Identification in Multi-Armed Bandits. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), 2010. [pdf] [slides]

  • S. Bubeck and R. Munos, Open-Loop Optimistic Planning. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), 2010. [pdf] [slides]

  • S. Bubeck, R. Munos and G. Stoltz, Pure Exploration in Multi-Armed Bandit Problems. In Proceedings of the 20th International Conference on Algorithmic Learning Theory (ALT), 2009. [pdf] [slides]

  • 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]

  • S. Bubeck, R. Munos, G. Stoltz and C. Szepesvari, Online Optimization in X-Armed Bandits. In Advances in Neural Information Processing Systems (NIPS) 22, 2009. [pdf] [Supp. material] [poster]

  • 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]

Misc.

  • 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. 51st IEEE Conference on Decision and Control (CDC), 2012. [pdf] [Extended version]

  • J.Y. Audibert, S. Bubeck and R. Munos, Bandit View on Noisy Optimization. In Optimization for Machine Learning, MIT press, 2011. [pdf]