How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD

By Zeyuan Allen-Zhu. 2018

186 citations recorded by the source corpus.

Stochastic gradient descent (SGD) gives an optimal convergence rate when minimizing convex stochastic objectives $f(x)$. However, in terms of making the gradients small, the original SGD does not give an optimal rate, even when $f(x)$ is convex. If $f(x)$ is convex, to find a point with gradient norm $\varepsilon$, we design an algorithm SGD3 with a near-optimal rate $\tilde{O}(\varepsilon^{-2})$, improving the best known rate $O(\varepsilon^{-8/3})$. If $f(x)$ is nonconvex, to find its $\varepsilon$-approximate local minimum, we design an algorithm SGD5 with rate $\tilde{O}(\varepsilon^{-3.5})$, where previously SGD variants only achieve $\tilde{O}(\varepsilon^{-4})$. This is no slower than the best known stochastic version of Newton's method in all parameter regimes.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Federated Optimization in Heterogeneous Networks (2018, methodology): “The proximal term we introduce has also been explored in previous optimization literature with different purposes, such as Allen-Zhu (2018), to speed up (mini-batch) SGD training on a single machine, and in Li et al. (2014b) for efficient SGD training both in a single machine and distributed…”
The Complexity of Making the Gradient Small in Stochastic Convex Optimization (2019, methodology): “The analysis of this algorithm is detailed in Appendix A and carefully matches the original analysis of SGD3 (Allen-Zhu, 2018).”
Lower bounds for non-convex stochastic optimization (2019, background): “In the convex setting (where achieving approximate global optimality is possible and hence usually the goal) [2] proposes algorithms with rates for finding stationary points improving over SGD, and [27] give improvements on these bounds and establish their optimality.”
Accelerated Methods for Non-Convex Optimization (2016, methodology): “Then Nesterov [31, Theorem 2.2.2] shows that for k > 1 f(zk)− f(z∗) ≤ L1 ( 1− √ σ1/L1 )k−1 ‖z1 − z∗‖2 ≤ 2κ exp(−(k − 1)κ− 1 2 )∆f .”
Lower bounds for finding stationary points I (2017, background): “Nesterov [36] proposes lower bounds for finding stationary points under a box constraint, but his construction does not extend to the unconstrained case when f(x)−infx f(x) is bounded.”
Asymmetric Valleys: Beyond Sharp and Flat Local Minima (2019, background): “For example, it is shown that they could escape saddle points or sharp local minima under reasonable assumptions (Ge et al., 2015; Jin et al., 2017; 2018a;b; Xu et al., 2018; Allen-Zhu, 2018a;b; Allen-Zhu & Li, 2018; Kleinberg et al., 2018).”
Complexity of finding near-stationary points of convex functions stochastically (2018, methodology): “In the short note [12], Nesterov showed that performing two rounds of a fast-gradient method on a slightly regularized problem yields an ε-stationary point in Õ(ε−1/2) iterations.”
Understanding the acceleration phenomenon via high-resolution differential equations (2018, background): “An (L2/k4) lower bound has been established by [35] as the optimal convergence rate for minimizing ‖∇ f ‖2 with access to only first-order information.”
Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions (2018, background): “As a first attempt, one may follow the observation of Nesterov [15] for smooth minimization.”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “5 ) [5].”
Stochastic model-based minimization of weakly convex functions (2018, background): “As a first attempt, one may follow the observation of Nesterov [46] for smooth minimization.”
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions (2017, background): “If we assume f is convex, gradient descent satisfies the bound (2) after O( −1) gradient evaluations, and AGD improves this rate to O( −1/2 log 1 ) (Nesterov, 2012).”