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

35 papers

math.OC2026

Fast, Parallel, Query-Efficient Binary Classification

Ishani Karmarkar, Liam O'Carroll, Aaron Sidford

We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size $n$ with normalized $d$ -dimensional features. Letting $Φ\i…

cs.DS2026

Computing Lewis weights to high precision using local relative smoothness

Sander Gribling, Aaron Sidford, Chenyi Zhang

We provide algorithms that compute $ε$ -estimates of the $ℓ_{p}$ -Lewis weights of a matrix $A \in R^{m \times n}$ for $p \geq 4$ using $O (p^{2} lo g (m / ε))$ rounds of leverag…

math.OC2026

Solving Matrix Games with Near-Optimal Matvec Complexity

Ishani Karmarkar, Liam O'Carroll, Aaron Sidford

We study the problem of computing an $ε$ -approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix $A \in R^{m \times n}$ , when the players'…

math.OC2025

Balancing Gradient and Hessian Queries in Non-Convex Optimization

Deeksha Adil, Brian Bullins, Aaron Sidford +1

We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function. We…

math.OC2025

Isotropic Noise in Stochastic and Quantum Convex Optimization

Annie Marsden, Liam O'Carroll, Aaron Sidford +1

We consider the problem of minimizing a $d$ -dimensional Lipschitz convex function using a stochastic gradient oracle. We introduce and motivate a setting where the noise of the sto…

cs.DS2025

Reusing Samples in Variance Reduction

Yujia Jin, Ishani Karmarkar, Aaron Sidford +1

We provide a general framework to improve trade-offs between the number of full batch and sample queries used to solve structured optimization problems. Our results apply to a broa…

math.OC2025

Solving Zero-Sum Games with Fewer Matrix-Vector Products

Ishani Karmarkar, Liam O'Carroll, Aaron Sidford

In this paper we consider the problem of computing an $ε$ -approximate Nash Equilibrium of a zero-sum game in a payoff matrix $A \in R^{m \times n}$ with $O (1)$ -bounded ent…

cs.DS2025

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

Michał Dereziński, Aaron Sidford

We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for $k$ large singular values. For solving su…

math.OC2024

Extracting Dual Solutions via Primal Optimizers

Yair Carmon, Arun Jambulapati, Liam O'Carroll +1

We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associa…

math.OC2024

Convex optimization with $p$ -norm oracles

Deeksha Adil, Brian Bullins, Arun Jambulapati +1

In recent years, there have been significant advances in efficiently solving $ℓ_{s}$ -regression using linear system solvers and $ℓ_{2}$ -regression [Adil-Kyng-Peng-Sachdeva, J. AC…

cs.DS2024

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm

Yujia Jin, Ishani Karmarkar, Christopher Musco +2

We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $n$ -node undirected graph. We provide a randomized algorithm that, with $O(nε^{-…

math.OC2024

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

Arun Jambulapati, Aaron Sidford, Kevin Tian

We develop a new parallel algorithm for minimizing Lipschitz, convex functions with a stochastic subgradient oracle. The total number of queries made and the query depth, i.e., the…

cs.LG2024

Truncated Variance Reduced Value Iteration

Yujia Jin, Ishani Karmarkar, Aaron Sidford +1

We provide faster randomized algorithms for computing an $ε$ -optimal policy in a discounted Markov decision process with $A_{tot}$ -state-action pairs, bounded rewards, and d…

cs.DS2024

On computing approximate Lewis weights

Simon Apers, Sander Gribling, Aaron Sidford

In this note we provide and analyze a simple method that given an $n \times d$ matrix, outputs approximate $ℓ_{p}$ -Lewis weights, a natural measure of the importance of the rows w…

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…

cs.DS2022

Dynamic Maxflow via Dynamic Interior Point Methods

Jan van den Brand, Yang P. Liu, Aaron Sidford

In this paper we provide an algorithm for maintaining a $(1 - ε)$ -approximate maximum flow in a dynamic, capacitated graph undergoing edge additions. Over a sequence of $m$ -additions…

Fast, Parallel, Query-Efficient Binary Classification

Computing Lewis weights to high precision using local relative smoothness

Solving Matrix Games with Near-Optimal Matvec Complexity

Balancing Gradient and Hessian Queries in Non-Convex Optimization

Isotropic Noise in Stochastic and Quantum Convex Optimization

Reusing Samples in Variance Reduction

Solving Zero-Sum Games with Fewer Matrix-Vector Products

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

Extracting Dual Solutions via Primal Optimizers

Convex optimization with p-norm oracles

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

Truncated Variance Reduced Value Iteration

On computing approximate Lewis weights

Sparsifying generalized linear models

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

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

Structured Semidefinite Programming for Recovering Structured Preconditioners

Matrix Completion in Almost-Verification Time

Moments, Random Walks, and Limits for Spectrum Approximation

Sparsifying sums of norms

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

ReSQueing Parallel and Private Stochastic Convex Optimization

Dynamic Maxflow via Dynamic Interior Point Methods

Convex optimization with $p$ -norm oracles