261 citations · 1.4k across the 45 of their papers we have counts for
6 papers · 1 filter
Entropic CLT and phase transition in high-dimensional Wishart matrices
Sébastien Bubeck, Shirshendu Ganguly
We consider high dimensional Wishart matrices where the entries of are i.i.d. from a log-concave distribut…
Multi-scale exploration of convex functions and bandit convex optimization
Sébastien Bubeck, Ronen Eldan
We construct a new map from a convex function to a distribution on its domain, with the property that this distribution is a multi-scale exploration of the function. We use this ma…
Sampling from a log-concave distribution with Projected Langevin Monte Carlo
Sébastien Bubeck, Ronen Eldan, Joseph Lehec
We extend the Langevin Monte Carlo (LMC) algorithm to compactly supported measures via a projection step, akin to projected Stochastic Gradient Descent (SGD). We show that (project…
A geometric alternative to Nesterov's accelerated gradient descent
Sébastien Bubeck, Yin Tat Lee, Mohit Singh
We propose a new method for unconstrained optimization of a smooth and strongly convex function, which attains the optimal rate of convergence of Nesterov's accelerated gradient de…
Exceptional rotations of random graphs: a VC theory
Louigi Addario-Berry, Shankar Bhamidi, Sébastien Bubeck +3
In this paper we explore maximal deviations of large random structures from their typical behavior. We introduce a model for a high-dimensional random graph process and ask analogo…
Bandit Convex Optimization: sqrt{T} Regret in One Dimension
Sébastien Bubeck, Ofer Dekel, Tomer Koren +1
We analyze the minimax regret of the adversarial bandit convex optimization problem. Focusing on the one-dimensional case, we prove that the minimax regret is $\widetildeΘ(\sqrt{T}…