research
∙
08/07/2023
Matrix Completion in Almost-Verification Time
We give a new framework for solving the fundamental problem of low-rank ...
share
research
∙
05/15/2023
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory
Discrepancy theory provides powerful tools for producing higher-quality ...
research
∙
02/28/2023
A CS guide to the quantum singular value transformation
We present a simplified exposition of some pieces of [Gilyén, Su, Low, a...
research
∙
02/13/2023
Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler
The development of efficient sampling algorithms catering to non-Euclide...
research
∙
01/10/2023
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
We give a quantum algorithm for computing an ϵ-approximate Nash equilibr...
research
∙
01/01/2023
ReSQueing Parallel and Private Stochastic Convex Optimization
We introduce a new tool for stochastic convex optimization (SCO): a Rewe...
research
∙
07/18/2022
Private Convex Optimization in General Norms
We propose a new framework for differentially private optimization of co...
research
∙
04/27/2022
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching
Box-simplex games are a family of bilinear minimax objectives which enca...
research
∙
03/21/2022
Improved Sampling-to-Counting Reductions in High-Dimensional Expanders and Faster Parallel Determinantal Sampling
We study parallel sampling algorithms for classes of distributions defin...
research
∙
03/08/2022
Semi-Random Sparse Recovery in Nearly-Linear Time
Sparse recovery is one of the most fundamental and well-studied inverse ...
research
∙
02/09/2022
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
We design accelerated algorithms with improved rates for several fundame...
research
∙
06/22/2021
Robust Regression Revisited: Acceleration and Improved Estimation Rates
We study fast algorithms for statistical regression problems under the s...
research
∙
06/16/2021
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation
We study the problem of list-decodable mean estimation, where an adversa...
research
∙
06/10/2021
Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
We give lower bounds on the performance of two of the most popular sampl...
research
∙
11/19/2020
List-Decodable Mean Estimation in Nearly-PCA Time
Traditionally, robust statistics has focused on designing estimators tol...
research
∙
11/12/2020
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
We show that standard extragradient methods (i.e. mirror prox and dual e...
research
∙
11/06/2020
Semi-Streaming Bipartite Matching in Fewer Passes and Less Space
We provide algorithms with improved pass and space complexities for appr...
research
∙
10/07/2020
Structured Logconcave Sampling with a Restricted Gaussian Oracle
We give algorithms for sampling several structured logconcave families t...
research
∙
09/17/2020
Coordinate Methods for Matrix Games
We develop primal-dual coordinate methods for solving bilinear saddle-po...
research
∙
08/04/2020
Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semi-Random Noise
Classical iterative algorithms for linear system solving and regression ...
research
∙
06/12/2020
Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
We develop two methods for the following fundamental statistical task: g...
research
∙
06/10/2020
Composite Logconcave Sampling with a Restricted Gaussian Oracle
We consider sampling from composite densities on ℝ^d of the form dπ(x) ∝...
research
∙
03/18/2020
Acceleration with a Ball Optimization Oracle
Consider an oracle which takes a point x and returns the minimizer of a ...
research
∙
02/12/2020
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
We give the first approximation algorithm for mixed packing and covering...
research
∙
02/10/2020
Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
We show that the gradient norm ∇ f(x) for x ∼(-f(x)), where f is strongl...
research
∙
07/03/2019
Variance Reduction for Matrix Games
We present a randomized primal-dual algorithm that solves the problem _x...
research
∙
06/03/2019
A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport
Optimal transportation, or computing the Wasserstein or “earth mover's” ...
research
∙
03/07/2019
A Rank-1 Sketch for Matrix Multiplicative Weights
We show that a simple randomized sketch of the matrix multiplicative wei...
research
∙
08/03/2018
Coordinate Methods for Accelerating ℓ_∞ Regression and Faster Approximate Maximum Flow
In this paper we provide faster algorithms for approximately solving ℓ_∞...
research
∙
02/21/2018