research
∙
05/15/2023
Sparsifying Sums of Norms
For any norms N_1,…,N_m on ℝ^n and N(x) := N_1(x)+⋯+N_m(x), we show ther...
share
research
∙
05/15/2023
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory
Discrepancy theory provides powerful tools for producing higher-quality ...
research
∙
03/14/2023
Testing Causality for High Dimensional Data
Determining causal relationship between high dimensional observations ar...
research
∙
01/01/2023
ReSQueing Parallel and Private Stochastic Convex Optimization
We introduce a new tool for stochastic convex optimization (SCO): a Rewe...
research
∙
09/21/2022
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
We present an algorithm that given any n-vertex, m-edge, rank r hypergra...
research
∙
08/24/2022
A Slightly Improved Bound for the KLS Constant
We refine the recent breakthrough technique of Klartag and Lehec to obta...
research
∙
06/17/2022
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
The accelerated proximal point algorithm (APPA), also known as "Catalyst...
research
∙
05/30/2022
Optimal and Adaptive Monteiro-Svaiter Acceleration
We develop a variant of the Monteiro-Svaiter (MS) acceleration framework...
research
∙
05/12/2022
Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities
In this work, we present new simple and optimal algorithms for solving t...
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
∙
12/01/2021
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
We make several advances broadly related to the maintenance of electrica...
research
∙
11/02/2021
Improved Iteration Complexities for Overconstrained p-Norm Regression
In this paper we obtain improved iteration complexities for solving ℓ_p ...
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/17/2021
Stochastic Bias-Reduced Gradient Methods
We develop a new primitive for stochastic optimization: a low-bias, low-...
research
∙
05/04/2021
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
We characterize the complexity of minimizing max_i∈[N] f_i(x) for convex...
research
∙
11/17/2020
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
In this paper we provide an O(m (loglog n)^O(1)log(1/ϵ))-expected time a...
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
∙
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
∙
06/03/2019
A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport
Optimal transportation, or computing the Wasserstein or “earth mover's” ...
research
∙
05/21/2019
Parallel Reachability in Almost Linear Work and Square Root Depth
In this paper we provide a parallel algorithm that given any n-node m-ed...
research
∙
12/15/2018
Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices
In this paper we show how to recover a spectral approximations to broad ...
research
∙
10/17/2018
Towards Optimal Running Times for Optimal Transport
In this work, we provide faster algorithms for approximating the optimal...
research
∙
10/04/2018
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
In this paper we provide nearly linear time algorithms for several probl...
research
∙
11/02/2017