206 citations · 808 across the 40 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
math.OC2017
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…
math.OC2017
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…
math.OC2017★ 33 cited
"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…