25 citations · 98 across the 29 of their papers we have counts for
6 papers · 1 filter
Matrix Completion in Almost-Verification Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
We give a new framework for solving the fundamental problem of low-rank matrix completion, i.e., approximating a rank- matrix (where $m…
Private Convex Optimization in General Norms
Sivakanth Gopi, Yin Tat Lee, Daogao Liu +2
We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm . Our algorithms are based on a regulariz…
Composite Logconcave Sampling with a Restricted Gaussian Oracle
Ruoqi Shen, Kevin Tian, Yin Tat Lee
We consider sampling from composite densities on of the form for well-conditioned and convex (but possibly non-smooth) ,…
Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
Yin Tat Lee, Ruoqi Shen, Kevin Tian
We show that the gradient norm for , where is strongly convex and smooth, concentrates tightly around its mean. This removes a barrier in…
A Rank-1 Sketch for Matrix Multiplicative Weights
Yair Carmon, John C. Duchi, Aaron Sidford +1
We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor. Unlik…
Learning Populations of Parameters
Kevin Tian, Weihao Kong, Gregory Valiant
Consider the following estimation problem: there are entities, each with an unknown parameter , and we observe independent random variables, …