Sébastien Bubeck – Publications by Year

2016

  • O. Angel, S. Bubeck, Y. Peres and F. Wei, Local max-cut in smoothed polynomial time. See arxiv for draft.

  • S. Bubeck, R. Eldan and Y. T. Lee, Kernel-based methods for bandit convex optimization. Draft, 2016. [arxiv]

  • M. Racz and S. Bubeck, Basic models and questions in statistical network analysis. Lecture notes, 2016. [arxiv]

  • S. Bubeck, K. Edwards, H. Mania and C. Supko, On paths, stars and wyes in trees. Submitted, 2016. [arxiv]

  • S. Bubeck and R. Eldan, Multi-scale exploration of convex functions and bandit convex optimization. COLT 2016 (Best Paper Award). [arxiv]

  • S. Bubeck and Y.-T. Lee, Black-box optimization with a politician. ICML 2016. [arxiv]

  • S. Bubeck and S. Ganguly, Entropic CLT and phase transition in high-dimensional Wishart matrices. To appear in International Mathematics Research Notices, 2015. [arxiv]

2015

  • S. Bubeck, Convex Optimization: Algorithms and Complexity. In Foundations and Trends in Machine Learning, Vol. 8: No. 3-4, pp 231-357, 2015 [pdf]

  • S. Bubeck and E. Gwynne, Asymptotic behavior of the Eden model with positively homogeneous edge weights. Submitted, 2015. [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 log-concave distribution with Projected Langevin Monte Carlo. NIPS 2015. [draft]

  • L. Addario-Berry, 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]

  • S. Bubeck, J. Ding, R. Eldan and M. Racz, Testing for high-dimensional 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]

  • 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 self-concordant barrier. COLT 2015. [arxiv]

  • 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, 30-39, 2015. [arxiv]

  • E. Arias-Castro, S. Bubeck and G. Lugosi, Detecting Positive Correlations in a Multivariate Sample. Bernoulli 21, 209-241, 2015. [draft]

  • S. Bubeck and N. Linial, On the local profiles of trees. Journal of Graph Theory, 2015. [draft]

2014

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

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

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

2013

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

  • K. Jamieson, M. Malloy, S. Bubeck and R. Nowak, On Finding the Largest Mean Among Many. Asilomar, 2013. [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, The complexities of optimization. Lecture notes, 2013. Available on my blog.

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

  • S. Bubeck, T. Wang and N. Viswanathan, Multiple Identifications in Multi-Armed Bandits. ICML 2013. [pdf]

2012

  • 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, D. Ernst and A. Garivier, Optimal discovery with probabilistic expert advice. 51st IEEE Conference on Decision and Control (CDC), 2012. [pdf] [Extended version]

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

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

2011

  • S. Bubeck, Introduction to Online Optimization. Lecture notes, 2011. [draft]

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

  • 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, S. Bubeck and G. Lugosi, Minimax Policies for Combinatorial Prediction Games. COLT 2011. [pdf] [slides] [Video]

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

2010

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

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

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

2009

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

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

2008

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