Natasha 2: Faster Non-Convex Optimization Than SGD

By Zeyuan Allen-Zhu. 2017

259 citations recorded by the source corpus.

We design a stochastic algorithm to train any smooth neural network to $\varepsilon$-approximate local minima, using $O(\varepsilon^{-3.25})$ backpropagations. The best result was essentially $O(\varepsilon^{-4})$ by SGD. More broadly, it finds $\varepsilon$-approximate local minima of any smooth nonconvex function in rate $O(\varepsilon^{-3.25})$, with only oracle access to stochastic gradients.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “Under these conditions, constant step-size SGD has a better convergence rate than algorithms which have recently been proposed to improve on SGD [2, 4].”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, methodology): “GD after SGD) O " 2 1 = 2 (see Theorem 1) SGD3 sc (SGD + recursive regularization) O " 2 log 3 (see Theorem 3) online nonconvex ( -nonconvex) SGD (naive) O " 4 (folklore, see e.g. [3, 17]) SCSG O " 10 = 3 (see [21]) SGD4 O " 2 + " 4 (see Theorem 4) Natasha1 :5 O &quot”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, background): “hitz smoothness assumption. Perhaps surprisingly, without using momentum, one can already improve this rate to T = O(" 3:5) (using SGD) [4], T= O(" 3:333) [34], or even to T= O(" 3:25) [2] if second-order Lipschitz smoothness is added. It is unclear whether such rates can be improved ”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Another set of conditions that are special cases of the PL condition was referred to as “one-point convexity” in [ 1].”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “…all local minima are global, then perturbed (stochastic) gradient descent [Ge et al., 2015, Jin et al., 2017, Levy, 2016] or methods with second order information [Nesterov and Polyak, 2006, Curtis et al., 2014, Carmon et al., 2016, Allen-Zhu, 2017] can ﬁnd a global minimum in polynomial time.”
On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms (2019, unknown): “This is different from classic nonconvex results where, for instance, Natasha 2 [Allen-Zhu, 2018], finds an -FOSP using O(1/ 3.25) samples.”
Energy Efficient Federated Learning Over Wireless Communication Networks (2019, methodology): “Due to the non-convexity of function Fk(w), we respectively replace Fk(w) and F (w) with their regularized versions [37]”
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).”
Escaping Saddles with Stochastic Gradients (2018, methodology): “This is applied e.g. using matrix-free Lanczos iterations (Curtis & Robinson, 2017; Reddi et al., 2017) or online variants such as Oja’s algorithm (Allen-Zhu, 2017).”
One-Bit Over-the-Air Aggregation for Communication-Efficient Federated Edge Learning: Design and Convergence Analysis (2020, background): “Assumptions 2 and 3 below, on the Lipschitz smoothness and bounded variance, respectively, are standard in the stochastic optimization literature [34].”
Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization (2019, background): “Other researchers have also made signiﬁcant progress in this direction, including [2, 3, 4, 8, 12, 16, 17, 18, 22, 27, 30].”
Stochastic model-based minimization of weakly convex functions (2018, result): “The results in this paper are orthogonal to the recent line of work on accelerated rates of convergence for smooth nonconvex ﬁnite sum minimization problems, e.g., [3, 4,38,53].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “There are also several other algorithms that provably work well in the presence of stochastic/incremental first-order and/or second-order oracles [179]–[181].”