937 citations · 3.8k across the 80 of their papers we have counts for
4 papers · 2 filters
Lower Bounds for Non-Convex Stochastic Optimization
Yossi Arjevani, Yair Carmon, John C. Duchi +3
We lower bound the complexity of finding -stationary points (with gradient norm at most ) using stochastic first-order methods. In a well-studied model where algorithms acces…
Geometry, Computation, and Optimality in Stochastic Optimization
Chen Cheng, Daniel Levy, John C. Duchi
We study computational and statistical consequences of problem geometry in stochastic and online optimization. By focusing on constraint set and gradient geometry, we characterize…
The importance of better models in stochastic optimization
Hilal Asi, John C. Duchi
Standard stochastic optimization methods are brittle, sensitive to stepsize choices and other algorithmic parameters, and they exhibit instability outside of well-behaved families…
Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs
Yu Bai, John Duchi, Song Mei
We study a family of (potentially non-convex) constrained optimization problems with convex composite structure. Through a novel analysis of non-smooth geometry, we show that proxi…