research
∙
07/02/2023
Moments, Random Walks, and Limits for Spectrum Approximation
We study lower bounds for the problem of approximating a one dimensional...
share
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
∙
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
∙
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/07/2021
A Unified Framework for Multi-distribution Density Ratio Estimation
Binary density ratio estimation (DRE), the problem of estimating the rat...
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
∙
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
∙
09/17/2020
Coordinate Methods for Matrix Games
We develop primal-dual coordinate methods for solving bilinear saddle-po...
research
∙
08/28/2020
Efficiently Solving MDPs with Stochastic Mirror Descent
We present a unified framework based on primal-dual stochastic mirror de...
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
∙
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
∙
07/03/2019
Variance Reduction for Matrix Games
We present a randomized primal-dual algorithm that solves the problem _x...
research
∙
09/13/2017