11 citations · 58 across the 33 of their papers we have counts for
12 papers · 1 filter
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…
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…
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 Methods for Higher-Order Smooth Monotone Variational Inequalities
Deeksha Adil, Brian Bullins, Arun Jambulapati +1
In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for -order smooth, monotone operators -- a problem that gener…
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\…
Stochastic Bias-Reduced Gradient Methods
Hilal Asi, Yair Carmon, Arun Jambulapati +2
We develop a new primitive for stochastic optimization: a low-bias, low-cost estimator of the minimizer of any Lipschitz strongly-convex function. In particular, we use a…
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
Yair Carmon, Arun Jambulapati, Yujia Jin +1
We characterize the complexity of minimizing for convex, Lipschitz functions . For non-smooth functions, existing methods require $O(Nε^{-2…
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…
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…