67 citations · 172 across the 19 of their papers we have counts for
11 papers · 1 filter
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…
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…
Large-Scale Methods for Distributionally Robust Optimization
Daniel Levy, Yair Carmon, John C. Duchi +1
We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and divergence uncertainty sets. We prove th…
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…
Variance Reduction for Matrix Games
Yair Carmon, Yujia Jin, Aaron Sidford +1
We present a randomized primal-dual algorithm that solves the problem to additive error in time , fo…