261 citations · 1.4k across the 45 of their papers we have counts for
5 papers · 1 filter
k-server via multiscale entropic regularization
Sebastien Bubeck, Michael B. Cohen, James R. Lee +2
We present an -competitive randomized algorithm for the -server problem on hierarchically separated trees (HSTs). This is the first -competitive randomized…
Sparsity, variance and curvature in multi-armed bandits
Sébastien Bubeck, Michael B. Cohen, Yuanzhi Li
In (online) learning theory the concepts of sparsity, variance and curvature are well-understood and are routinely used to obtain refined regret and generalization bounds. In this…
An homotopy method for regression provably beyond self-concordance and in input-sparsity time
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee +1
We consider the problem of linear regression where the norm loss (i.e., the usual least squares loss) is replaced by the norm. We show how to solve such probl…
Multi-scale Online Learning and its Applications to Online Auctions
Sébastien Bubeck, Nikhil R. Devanur, Zhiyi Huang +1
We consider revenue maximization in online auction/pricing problems. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted p…
Optimal algorithms for smooth and strongly convex distributed optimization in networks
Kevin Scaman, Francis Bach, Sébastien Bubeck +2
In this paper, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over…