research
∙
09/08/2023
Parallel Submodular Function Minimization
We consider the parallel complexity of submodular function minimization ...
share
research
∙
08/07/2023
Matrix Completion in Almost-Verification Time
We give a new framework for solving the fundamental problem of low-rank ...
research
∙
08/03/2023
Quantum speedups for stochastic optimization
We consider the problem of minimizing a continuous function given quantu...
research
∙
07/02/2023
Moments, Random Walks, and Limits for Spectrum Approximation
We study lower bounds for the problem of approximating a one dimensional...
research
∙
06/26/2023
Towards Optimal Effective Resistance Estimation
We provide new algorithms and conditional hardness for the problem of es...
research
∙
06/20/2023
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
We study dynamic (1-ϵ)-approximate rounding of fractional matchings – a ...
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...
research
∙
01/31/2023
Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification
In this paper, we introduce a new, spectral notion of approximation betw...
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
∙
12/13/2022
Dynamic Maxflow via Dynamic Interior Point Methods
In this paper we provide an algorithm for maintaining a (1-ϵ)-approximat...
research
∙
10/13/2022
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
We provide an efficient unified plug-in approach for estimating symmetri...
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
∙
07/09/2022
Improved Lower Bounds for Submodular Function Minimization
We provide a generic technique for constructing families of submodular f...
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
∙
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
∙
04/08/2022
The Complexity of Infinite-Horizon General-Sum Stochastic Games
We study the complexity of computing stationary Nash equilibrium (NE) in...
research
∙
03/29/2022
Efficient Convex Optimization Requires Superlinear Memory
We show that any memory-constrained, first-order algorithm which minimiz...
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
∙
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
∙
10/29/2021
Computing Lewis Weights to High Precision
We present an algorithm for computing approximate ℓ_p Lewis weights to h...
research
∙
06/17/2021
Stochastic Bias-Reduced Gradient Methods
We develop a new primitive for stochastic optimization: a low-bias, low-...
research
∙
06/13/2021
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
We prove new upper and lower bounds for sample complexity of finding an ...
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
∙
01/14/2021
Minimum Cost Flows, MDPs, and ℓ_1-Regression in Nearly Linear Time for Dense Instances
In this paper we provide new randomized algorithms with improved runtime...
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
∙
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
∙
11/05/2020
Instance Based Approximations to Profile Maximum Likelihood
In this paper we provide a new efficient algorithm for approximately com...
research
∙
10/12/2020
Large-Scale Methods for Distributionally Robust Optimization
We propose and analyze algorithms for distributionally robust optimizati...
research
∙
09/17/2020
Coordinate Methods for Matrix Games
We develop primal-dual coordinate methods for solving bilinear saddle-po...
research
∙
09/03/2020
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...
research
∙
08/28/2020
Efficiently Solving MDPs with Stochastic Mirror Descent
We present a unified framework based on primal-dual stochastic mirror de...
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
∙
04/17/2020
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
research
∙
04/06/2020
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood
In this paper we consider the problem of computing the likelihood of the...
research
∙
03/19/2020
Faster Divergence Maximization for Faster Maximum Flow
In this paper we provide an algorithm which given any m-edge n-vertex di...
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
∙
03/02/2020
A General Framework for Symmetric Property Estimation
In this paper we provide a general framework for estimating symmetric pr...
research
∙
02/06/2020
Solving Tall Dense Linear Programs in Nearly Linear Time
In this paper we provide an Õ(nd+d^3) time randomized algorithm for solv...
research
∙
12/10/2019
High-precision Estimation of Random Walks in Small Space
In this paper, we provide a deterministic Õ(log N)-space algorithm for e...
research
∙
11/25/2019
Faster Matroid Intersection
In this paper we consider the classic matroid intersection problem: give...
research
∙
10/31/2019
Faster Energy Maximization for Faster Maximum Flow
In this paper we provide an algorithm which given any m-edge n-vertex di...
research
∙
10/17/2019
Solving Linear Programs with Sqrt(rank) Linear System Solves
We present an algorithm that given a linear program with n variables, m ...
research
∙
10/15/2019
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
Given a data matrix A∈R^n × d, principal component projection (PCP) and ...
research
∙
08/31/2019
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
In this paper we provide improved running times and oracle complexities ...
research
∙
08/29/2019