25 citations · 98 across the 29 of their papers we have counts for
7 papers · 1 filter
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…
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- matrix (where $m…
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory
Arun Jambulapati, Victor Reis, Kevin Tian
Discrepancy theory provides powerful tools for producing higher-quality objects which "beat the union bound" in fundamental settings throughout combinatorics and computer science.…
Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations
Arun Jambulapati, Kevin Tian
We investigate different aspects of area convexity [Sherman '17], a mysterious tool introduced to tackle optimization problems under the challenging geometry. We deve…
Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler
Sivakanth Gopi, Yin Tat Lee, Daogao Liu +2
The development of efficient sampling algorithms catering to non-Euclidean geometries has been a challenging endeavor, as discretization techniques which succeed in the Euclidean s…
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 payoff matrix with bounded entries. Given a standard quantum orac…
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…