20 citations · 48 across the 10 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…