25 citations · 98 across the 29 of their papers we have counts for
31 papers
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…
Private Convex Optimization in General Norms
Sivakanth Gopi, Yin Tat Lee, Daogao Liu +2
We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm . Our algorithms are based on a regulariz…
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching
Arun Jambulapati, Yujia Jin, Aaron Sidford +1
Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [She17], optimal transport [JST19], and bipartite mat…
Semi-Random Sparse Recovery in Nearly-Linear Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
Sparse recovery is one of the most fundamental and well-studied inverse problems. Standard statistical formulations of the problem are provably solved by general convex programming…
Quadratic Speedups in Parallel Sampling from Determinantal Distributions
Nima Anari, Callum Burgess, Kevin Tian +1
We study the problem of parallelizing sampling from distributions related to determinants: symmetric, nonsymmetric, and partition-constrained determinantal point processes, as well…
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
Yujia Jin, Aaron Sidford, Kevin Tian
We design accelerated algorithms with improved rates for several fundamental classes of optimization problems. Our algorithms all build upon techniques related to the analysis of p…
Robust Regression Revisited: Acceleration and Improved Estimation Rates
Arun Jambulapati, Jerry Li, Tselil Schramm +1
We study fast algorithms for statistical regression problems under the strong contamination model, where the goal is to approximately optimize a generalized linear model (GLM) give…
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard +2
We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. Specifically, we are given a set of points in $\mathbb{R}^…
Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
Yin Tat Lee, Ruoqi Shen, Kevin Tian
We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte…
List-Decodable Mean Estimation in Nearly-PCA Time
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard +2
Traditionally, robust statistics has focused on designing estimators tolerant to a minority of contaminated data. Robust list-decodable learning focuses on the more challenging reg…
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
Michael B. Cohen, Aaron Sidford, Kevin Tian
We show that standard extragradient methods (i.e. mirror prox and dual extrapolation) recover optimal accelerated rates for first-order minimization of smooth convex functions. To…
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
Sepehr Assadi, Arun Jambulapati, Yujia Jin +2
We provide -pass semi-streaming algorithms for computing -approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods ar…
Structured Logconcave Sampling with a Restricted Gaussian Oracle
Yin Tat Lee, Ruoqi Shen, Kevin Tian
We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex opti…
Coordinate Methods for Matrix Games
Yair Carmon, Yujia Jin, Aaron Sidford +1
We develop primal-dual coordinate methods for solving bilinear saddle-point problems of the form which contain linear p…
Fast and Near-Optimal Diagonal Preconditioning
Arun Jambulapati, Jerry Li, Christopher Musco +2
The convergence rates of iterative methods for solving a linear system typically depend on the condition number of the matrix . Preconditioning is a…
Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing
Arun Jambulapati, Jerry Li, Kevin Tian
We develop two methods for the following fundamental statistical task: given an -corrupted set of samples from a -dimensional sub-Gaussian distribution, return an approxi…
Composite Logconcave Sampling with a Restricted Gaussian Oracle
Ruoqi Shen, Kevin Tian, Yin Tat Lee
We consider sampling from composite densities on of the form for well-conditioned and convex (but possibly non-smooth) ,…
Acceleration with a Ball Optimization Oracle
Yair Carmon, Arun Jambulapati, Qijia Jiang +4
Consider an oracle which takes a point and returns the minimizer of a convex function in an ball of radius around . It is straightforward to show that rough…