Timezone: »
Poster
Finite-Time Analysis of Projected Langevin Monte Carlo
Sebastien Bubeck · Ronen Eldan · Joseph Lehec
We analyze the projected Langevin Monte Carlo (LMC) algorithm, a close cousin of projected Stochastic Gradient Descent (SGD). We show that LMC allows to sample in polynomial time from a posterior distribution restricted to a convex body and with concave log-likelihood. This gives the first Markov chain to sample from a log-concave distribution with a first-order oracle, as the existing chains with provable guarantees (lattice walk, ball walk and hit-and-run) require a zeroth-order oracle. Our proof uses elementary concepts from stochastic calculus which could be useful more generally to understand SGD and its variants.
Author Information
Sebastien Bubeck (MSR)
Ronen Eldan (Weizmann)
Joseph Lehec
More from the Same Authors
-
2020 Poster: Network size and size of the weights in memorization with two-layers neural networks »
Sebastien Bubeck · Ronen Eldan · Yin Tat Lee · Dan Mikulincer -
2015 Poster: Bandit Smooth Convex Optimization: Improving the Bias-Variance Tradeoff »
Ofer Dekel · Ronen Eldan · Tomer Koren -
2015 Spotlight: Bandit Smooth Convex Optimization: Improving the Bias-Variance Tradeoff »
Ofer Dekel · Ronen Eldan · Tomer Koren -
2013 Workshop: Learning Faster From Easy Data »
Peter Grünwald · Wouter M Koolen · Sasha Rakhlin · Nati Srebro · Alekh Agarwal · Karthik Sridharan · Tim van Erven · Sebastien Bubeck -
2013 Workshop: Bayesian Optimization in Theory and Practice »
Matthew Hoffman · Jasper Snoek · Nando de Freitas · Michael A Osborne · Ryan Adams · Sebastien Bubeck · Philipp Hennig · Remi Munos · Andreas Krause -
2013 Poster: Prior-free and prior-dependent regret bounds for Thompson Sampling »
Sebastien Bubeck · Che-Yu Liu -
2012 Session: Oral Session 2 »
Sebastien Bubeck -
2011 Poster: Multi-Bandit Best Arm Identification »
Victor Gabillon · Mohammad Ghavamzadeh · Alessandro Lazaric · Sebastien Bubeck -
2008 Poster: Online Optimization in X-Armed Bandits »
Sebastien Bubeck · Remi Munos · Gilles Stoltz · Csaba Szepesvari -
2007 Spotlight: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann -
2007 Poster: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann