1.6k citations · 1.7k across the 22 of their papers we have counts for
5 papers · 1 filter
Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev
Yin Tat Lee, Santosh S. Vempala
Logarithmic Sobolev inequalities are a powerful way to estimate the rate of convergence of Markov chains and to derive concentration inequalities on distributions. We prove that th…
Leverage Score Sampling for Faster Accelerated Regression and ERM
Naman Agarwal, Sham Kakade, Rahul Kidambi +3
Given a matrix and a vector , we show how to compute an -approximate solution to the regression problem $ \min_{x\in\m…
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…
Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Yin Tat Lee, Santosh S. Vempala
We give the first rigorous proof of the convergence of Riemannian Hamiltonian Monte Carlo, a general (and practical) method for sampling Gibbs distributions. Our analysis shows tha…
Efficient Convex Optimization with Membership Oracles
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
We consider the problem of minimizing a convex function over a convex set given access only to an evaluation oracle for the function and a membership oracle for the set. We give a…