25 citations · 98 across the 29 of their papers we have counts for
11 papers · 1 filter
List-Decodable Mean Estimation in Nearly-PCA Time
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard +2
Traditionally, robust statistics has focused on designing estimators tolerant to a minority of contaminated data. Robust list-decodable learning focuses on the more challenging reg…
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
Michael B. Cohen, Aaron Sidford, Kevin Tian
We show that standard extragradient methods (i.e. mirror prox and dual extrapolation) recover optimal accelerated rates for first-order minimization of smooth convex functions. To…
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
Sepehr Assadi, Arun Jambulapati, Yujia Jin +2
We provide -pass semi-streaming algorithms for computing -approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods ar…
Structured Logconcave Sampling with a Restricted Gaussian Oracle
Yin Tat Lee, Ruoqi Shen, Kevin Tian
We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex opti…
Coordinate Methods for Matrix Games
Yair Carmon, Yujia Jin, Aaron Sidford +1
We develop primal-dual coordinate methods for solving bilinear saddle-point problems of the form which contain linear p…
Fast and Near-Optimal Diagonal Preconditioning
Arun Jambulapati, Jerry Li, Christopher Musco +2
The convergence rates of iterative methods for solving a linear system typically depend on the condition number of the matrix . Preconditioning is a…
Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
Arun Jambulapati, Jerry Li, Kevin Tian
We develop two methods for the following fundamental statistical task: given an -corrupted set of samples from a -dimensional sub-Gaussian distribution, return an approxi…
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) ,…
Acceleration with a Ball Optimization Oracle
Yair Carmon, Arun Jambulapati, Qijia Jiang +4
Consider an oracle which takes a point and returns the minimizer of a convex function in an ball of radius around . It is straightforward to show that rough…
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li +2
We give the first approximation algorithm for mixed packing and covering semidefinite programs (SDPs) with polylogarithmic dependence on width. Mixed packing and covering SDPs cons…
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…