Aaron Sidford

activity

20212026

most citedSharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

5 citations · 20 across the 29 of their papers we have counts for

collaborators

Showing 2023Show all

9 papers · 1 filter

cs.DS2023

Sparsifying generalized linear models

Arun Jambulapati, James R. Lee, Yang P. Liu +1

We consider the sparsification of sums $F : R^{n} \to R$ where $F (x) = f_{1} (⟨ a_{1}, x ⟩) + \dots + f_{m} (⟨ a_{m}, x ⟩)$ for vectors $a_1,\ldots,a_m \…

cs.DS2023

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

Yair Carmon, Arun Jambulapati, Yujia Jin +1

We design algorithms for minimizing $max_{i \in [n]} f_{i} (x)$ over a $d$ -dimensional Euclidean or simplex domain. When each $f_{i}$ is $1$ -Lipschitz and $1$ -smooth, our method computes…

cs.DS2023

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

Jan van den Brand, Li Chen, Rasmus Kyng +5

We provide an algorithm which, with high probability, maintains a $(1 - ε)$ -approximate maximum flow on an undirected graph undergoing $m$ -edge additions in amortized $m^{o(1)} ε^{-3…

cs.DS2023

Structured Semidefinite Programming for Recovering Structured Preconditioners

Arun Jambulapati, Jerry Li, Christopher Musco +3

We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental p…

cs.LG2023

Matrix Completion in Almost-Verification Time

Jonathan A. Kelner, Jerry Li, Allen Liu +2

We give a new framework for solving the fundamental problem of low-rank matrix completion, i.e., approximating a rank- $r$ matrix $M \in R^{m \times n}$ (where $m…

cs.DS2023★ 1 cited

Moments, Random Walks, and Limits for Spectrum Approximation

Yujia Jin, Christopher Musco, Aaron Sidford +1

We study lower bounds for the problem of approximating a one dimensional distribution given (noisy) measurements of its moments. We show that there are distributions on $[- 1, 1]$ th…

cs.DS2023★ 2 cited

Sparsifying sums of norms

Arun Jambulapati, James R. Lee, Yang P. Liu +1

For any norms $N_{1}, \dots, N_{m}$ on $R^{n}$ and $N (x) := N_{1} (x) + \dots + N_{m} (x)$ , we show there is a sparsified norm $N ~ (x) = w_{1} N_{1} (x) + \dots + w_{m} N_{m} (x)$ such that…

quant-ph2023★ 2 cited

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling

Adam Bouland, Yosheb Getachew, Yujia Jin +2

We give a quantum algorithm for computing an $ε$ -approximate Nash equilibrium of a zero-sum game in a $m \times n$ payoff matrix with bounded entries. Given a standard quantum orac…

math.OC2023

ReSQueing Parallel and Private Stochastic Convex Optimization

Yair Carmon, Arun Jambulapati, Yujia Jin +4

We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probab…