5 citations · 20 across the 29 of their papers we have counts for
13 papers · 1 filter
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 with normalized -dimensional features. Letting $Φ\i…
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 , when the players'…
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…
Isotropic Noise in Stochastic and Quantum Convex Optimization
Annie Marsden, Liam O'Carroll, Aaron Sidford +1
We consider the problem of minimizing a -dimensional Lipschitz convex function using a stochastic gradient oracle. We introduce and motivate a setting where the noise of the sto…
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 with -bounded ent…
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…
Convex optimization with -norm oracles
Deeksha Adil, Brian Bullins, Arun Jambulapati +1
In recent years, there have been significant advances in efficiently solving -regression using linear system solvers and -regression [Adil-Kyng-Peng-Sachdeva, J. AC…
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…
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…
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
Yair Carmon, Arun Jambulapati, Yujia Jin +1
The accelerated proximal point algorithm (APPA), also known as "Catalyst", is a well-established reduction from convex optimization to approximate proximal point computation (i.e.,…
Optimal and Adaptive Monteiro-Svaiter Acceleration
Yair Carmon, Danielle Hausler, Arun Jambulapati +2
We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Consequently, for any $p\…
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…
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
Jonathan Kelner, Annie Marsden, Vatsal Sharan +3
We provide new gradient-based methods for efficiently solving a broad class of ill-conditioned optimization problems. We consider the problem of minimizing a function $f : \mathbb{…