937 citations · 3.8k across the 80 of their papers we have counts for
4 papers · 2 filters
Lower Bounds for Finding Stationary Points II: First-Order Methods
Yair Carmon, John C. Duchi, Oliver Hinder +1
We establish lower bounds on the complexity of finding -stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic…
Lower Bounds for Finding Stationary Points I
Yair Carmon, John C. Duchi, Oliver Hinder +1
We prove lower bounds on the complexity of finding -stationary points (points such that ) of smooth, high-dimensional, and potentially non-convex func…
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
Yair Carmon, Oliver Hinder, John C. Duchi +1
We develop and analyze a variant of Nesterov's accelerated gradient descent (AGD) for minimization of smooth non-convex functions. We prove that one of two cases occurs: either our…
Stochastic Methods for Composite and Weakly Convex Optimization Problems
John Duchi, Feng Ruan
We consider minimization of stochastic functionals that are compositions of a (potentially) non-smooth convex function and smooth function and, more generally, stochastic w…