Aaron Sidford

activity

20212026

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

5 citations · 6 across the 18 of their papers we have counts for

collaborators

Showing cs.DSShow all

13 papers · 1 filter

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…

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…

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…

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ε^{-…

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 \…