PaperlayerView exact revision on arXiv

Source-linked AI summary

Natasha 2: Faster Non-Convex Optimization Than SGD

Zeyuan Allen-Zhu

arXiv:1708.08694v4math.OCcs.DScs.LGcs.NEstat.ML

TL;DR

The paper addresses the gap between SGD's slower provable rate and the need to find approximate local minima rather than merely stationary points in smooth nonconvex optimization. It combines Oja's negative-curvature procedure with Natasha1.5 to construct Natasha2. The resulting method achieves eO(ε^-3.25) for (ε, ε^1/4)-approximate local minima, with a second guarantee of eO(ε^-3.5) for (ε, ε^1/2)-approximate local minima.

  • Problem

    The paper seeks a provably faster online stochastic method for finding approximate local minima, since stationary points may be saddle points and SGD has rate essentially O(ε^-4).

  • Method

    Natasha2 combines Natasha1.5 with Oja's algorithm, which uses stochastic Hessian-vector products to identify negative-curvature directions.

  • Results

    T = eO(ε^-3.25) finds (ε, ε^1/4)-approximate local minima, while T = eO(ε^-3.5) finds (ε, ε^1/2)-approximate local minima.

  • Takeaways & Limitations

    The paper provides faster online stochastic rates for approximate local minima of smooth nonconvex objectives using curvature information and stochastic first-order computations.

  • Takeaways & Limitations

    The intuitive saddle-point process requires a stationary point to lie inside a safe zone, and using a weaker version worsens the convergence rate.

Abstract

from arXiv · show

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.

1 Introduction

The paper targets faster online stochastic optimization for approximate local minima, motivated by neural-network training and the need to avoid saddle points. Natasha2 combines negative-curvature detection with stochastic first-order methods to improve on SGD's rate.

  • Motivation: Deep neural-network training still relies primarily on SGD and heuristic variants, motivating provably faster training algorithms.
  • Problem Setting: The goal is to find approximate local minima of an online stochastic nonconvex objective, with complexity independent of the dataset size n.This online setting also covers n being infinite.
  • Motivation: Approximate local minima are sought because stationary points may be saddle points, whereas experiments suggest local-minimum convergence may suffice for neural-network training.
  • Method: Negative-curvature directions provide a Hessian-informed alternative to blind random perturbations for escaping saddle points.The negative eigenvector of the Hessian identifies a direction for decreasing the objective near a saddle point.
  • Method: Oja's algorithm approximates power iteration online using stochastic Hessian-vector products, whose computation is described as comparable in cost to stochastic gradients.For neural networks, both gradient and Hessian-vector-product computations can be implemented with one backpropagation, though the latter may be roughly twice as expensive in practice.

2 Preliminaries

The preliminaries define the paper's norm, matrix-order, curvature, convexity, smoothness, and gradient-mapping notation. These definitions specify the assumptions and stationarity concepts used later.

  • Notation: The paper uses the Euclidean norm, spectral norm, minimum and maximum eigenvalues, and PSD ordering for symmetric matrices.A ⪰ −σI means every eigenvalue is at least −σ.
  • Function Classes: σ-bounded nonconvexity requires a lower quadratic-model bound with a −σ term, while σ-strong convexity uses a positive quadratic term.
  • Function Classes: L-smoothness bounds gradient variation, and L2-second-order smoothness bounds Hessian variation in spectral norm.
  • Stationarity: For F(x) = ψ(x) + f(x), the gradient mapping is defined with parameter η; when ψ is identically zero, it equals ∇f(x).

3 Natasha 1.5: Finding Approximate Stationary Points

Natasha 1.5 develops an online extension of variance-reduced methods for finding ε-approximate stationary points while exploiting bounded nonconvexity. Its analysis uses sub-epochs, stabilization, and concentration to obtain a complexity improvement over prior online methods.

  • Motivation: Before this work, online first-order methods did not exploit the σ-bounded nonconvexity parameter, while offline methods such as repeatSVRG and Natasha1 did.σ-nonconvexity measures how negative the Hessian eigenvalues can be, with larger σ indicating greater nonconvexity.
  • Our Theorem: Natasha 1.5 extends Natasha1 to the online setting under assumptions (A1), (A2), and (A3), achieving better complexity than SCSG.The method uses stochastic gradient computations and hides dependencies on variance and initial objective gap in simplified big-O notation.
  • Our Theorem: E[∥∇f(x_out)∥] ≤ ε is achieved using O(T) stochastic-gradient computations, and the numerator's σ^1/3 factor is key for the later local-minimum algorithm.When ε ≤ σ/L is not satisfied, σ can be replaced by εL; Natasha1.5 is preferable to Natasha1 only when σ ≤ εL.
  • Our Algorithm: The algorithm replaces full snapshot gradients with minibatch estimates, shortening epochs from n iterations to B iterations when B ≪ n.This converts offline SVRG- and Natasha1-style procedures into online methods.
  • Our Intuition: Natasha1 stabilizes variance-reduced updates by adding 2σ(x_t−b_x), equivalently minimizing f(x)+σ∥x−b_x∥^2 within each sub-epoch.The retraction enables mirror-descent-type analysis that can use bounded nonconvexity.

4 Natasha 2: Finding Approximate Local Minima

Natasha2 targets approximate local minima online by alternating stationary-point finding with negative-curvature detection. Under smoothness assumptions, it achieves improved rates for two approximate-local-minimum criteria.

  • Prior work: Before Natasha2, SGD required T = O(poly(d)ε−4) gradient computations, while several variance-reduction methods could remain stuck at saddle points.The comparison concerns online approximate-local-minimum guarantees.
  • Method: Natasha2 alternates stationary-point finding with Oja’s algorithm to detect negative curvature and move along an approximate minimum-eigenvalue direction.Its gradient complexity counts stochastic gradients plus Hessian-vector products.
  • Guarantee: Under (A1), (A2), and (A4), Natasha2 outputs xout with probability at least 2/3 satisfying ∥∇f(xout)∥≤ε and ∇2f(xout) ⪰−δI.The guarantee applies for ε ∈ (0,1) and δ ∈ (0, ε1/4).
  • Goal: ε-approximate local minima require both small gradient and Hessian eigenvalues bounded below by −δ.The paper distinguishes these from approximate stationary points, which may be saddle points.
  • Rates: T = eO(ε−3.25) finds (ε, ε1/4)-approximate local minima, improving on SGD’s ε−4 factor.For the stronger criterion with δ = ε1/2, the rate is eO(ε−3.5).
  • Technical ingredient: The analysis addresses leaving the safe zone by showing that such movement produces objective decrease proportional to the squared travel distance.This property handles a case in which the stationary-point routine does not terminate inside the safe zone.

5 Auxiliary Lemmas

The auxiliary results establish online eigenvector estimation, a first-order stopping criterion, and convex-SGD guarantees used to analyze Natasha1.5 and Natasha2.

  • Section scope: The auxiliary section supplies results for Oja’s algorithm, stationary-point finding, and SGD on convex functions.These results support the later proofs of Natasha1.5full and Natasha2full.
  • Oja’s algorithm: Oja’s algorithm estimates eigenvectors online using stochastic matrix-vector products, which correspond here to stochastic Hessian-vector products.Its total number of Hessian-vector products is at most O(T log(1/p)).
  • First-order stopping criterion: Adding a convex regularizer makes g(x) σ-strongly convex, allowing convex optimization to minimize G(x).The construction applies when ψ is proper convex and f is σ-nonconvex but L-smooth.
  • First-order stopping criterion: An approximate stationary point of G transfers to an approximate stationary point of F, with additive error O(σ2∥bx −x∗∥2).The transfer result quantifies the dependence on the regularized problem’s minimizer.
  • Convex SGD: SGD3sc reaches ∥GF,η(x)∥≤ε using eO(ε−2) stochastic gradient computations, whereas naive SGD requires eO(σ−1ε−2).The improved rate is used to tighten the final complexities of Natasha1.5 and Natasha2.

6 Natasha 1.5: Finding Stationary Points

Natasha1.5 is an online stochastic method for finding approximate stationary points, combining snapshot minibatches, regularized SVRG-style sub-epochs, and mirror-descent analysis to handle estimator bias. Its pruning variant achieves an ε-accurate output under stated smoothness, variance, and parameter conditions.

  • Algorithm: Natasha1.5full partitions each full epoch into p sub-epochs of length m = B/p and applies a regularized SVRG-style update within each sub-epoch.Each epoch begins with a minibatch gradient at the current snapshot, while each sub-epoch starts from a randomly selected point from the preceding sub-epoch.
  • Algorithm: The gradient estimator combines the snapshot minibatch gradient, a stochastic-gradient difference, and a regularization term centered at the sub-epoch start.The estimator is analyzed as biased because the snapshot minibatch gradient is not the full gradient.
  • Outputs: Natasha1.5full outputs a randomly selected point by for small gradient and the final point y+ for objective decrease.The analysis informally bounds the gradient at by using the initial and final objective values, while y+ is retained to ensure objective decrease.
  • Analysis: The main one-epoch lemma uses mirror descent to handle the biased estimator, unlike the gradient-descent analysis used for SCSG.The authors identify this proof technique as key to the Natasha1.5full result.
  • Analysis: Under the stated step-size conditions, telescoping the one-sub-epoch bound yields an entire-epoch guarantee used by the pruning algorithm.The conditions include α ≤ 1/(2L+4σ), α ≥ 8/(σm), and α ≤ σ/(4p^2L^2).
  • Pruning: Natasha1.5prune runs Natasha1.5full, defines G(x) = F(x) + σ∥x − by∥^2, and then applies SGD to this strongly convex regularized objective.The additional SGD stage starts from by and produces the final output xout.
  • Guarantee: Theorem 1 states that Natasha1.5prune outputs xout with E[∥GF,η(xout)∥] ≤ ε in the stated gradient complexity under its assumptions.The result assumes a starting vector, an upper bound ΔF on the initial objective gap, and parameter constraints relating L, σ, and ε.
  • Guarantee: With L, ΔF, and V treated as constants, Corollary 6.6 gives the resulting asymptotic gradient-complexity bound.The supplied corollary passage states the bound but does not preserve its exponent in the extracted text.

7 Natasha 2: Finding Local Minima

Natasha2 alternates first-order optimization with second-order saddle detection and random perturbations, then uses convexification and SGD to obtain approximate local minima under smoothness and variance assumptions.

  • Assumptions: Natasha2full assumes each fi is L-smooth, while f is second-order smooth and stochastic gradients have bounded variance.These assumptions match the setting used by prior online SGD analyses, with the variance bound needed for online methods.
  • Algorithm: Each iteration uses Oja’s algorithm to detect either a sufficiently negative Hessian direction or certify that ∇2f(yk) ⪰−δI.The algorithm then performs a second-order step or proceeds with a first-order step.
  • Algorithm: When negative curvature is detected, Natasha2 randomly moves by ±δ/L2 along the detected direction; otherwise it applies a first-order step to a penalized function.The penalized function is designed to be 5L-smooth and 3δ-nonconvex, with additional parameter choices handling boundary cases.
  • Algorithm: After N1 first-order steps, the method randomly selects an iterate, prunes it using convex SGD, and outputs the resulting point.The final objective adds a strong-convexity penalty around the selected iterate and pruning output.
  • Guarantee: With probability at least 2/3, the output satisfies ∥∇f(xout)∥≤ε and ∇2f(xout) ⪰−3δI.Thus the output meets the paper’s gradient and approximate-local-minimum conditions.
  • Complexity: Assuming L, L2, ∆f, and V are constants, Natasha2full achieves its stated complexity for every δ ∈(0, ε1/4], with larger δ replaceable by ε1/4.The total complexity combines Oja’s procedures, first-order steps, and the final SGD call.

B Convergence of GD and SGD for Nonconvex Functions

For smooth nonconvex functions, gradient descent and SGD guarantee approximate stationary points, but the stochastic-gradient complexity retains an ε−4 dependence that acceleration does not remove.

  • Gradient descent: For L-smooth nonconvex functions, gradient descent guarantees an iterate with small gradient after sufficiently many updates.Each full gradient requires computing all n individual sample gradients, producing an n-dependent total complexity.
  • Stochastic gradient descent: SGD similarly guarantees a randomly selected iterate with E[∥∇f(xt)∥2]≤ε2 when its iteration count is sufficiently large.The guarantee concerns an approximate stationary point rather than an approximate local minimum.
  • Stochastic gradient descent: The resulting SGD convergence rate is T ∝ 1/ε4, and acceleration improves only the lower-order ε−2 term.The ε−4 term remains unchanged in the cited discussion.

C.1 Proof of Lemma 5.3

The proof of Lemma 5.3 establishes that online Oja’s algorithm can identify a sufficiently low-curvature direction or certify an approximate lower bound on the Hessian spectrum.

  • Single-run guarantee: A single Oja run produces a unit vector with probability at least 4/5 under the lemma’s stated iteration and step-size conditions.The vector approximates the relevant extremal eigen-direction through stochastic matrix samples.
  • Amplification: Repeating Oja’s algorithm O(log(1/p)) times raises the success probability to at least 1−p.The total Hessian-vector-product count is at most O(T log(1/p)).
  • Proof structure: The proof combines a high-probability stochastic estimate, Markov’s bound, and independent repetitions to obtain the spectral guarantee.The resulting bound controls the minimum-eigenvalue test used by Natasha2.

C.2 Proof of Lemma 5.5

The proof of Lemma 5.5 uses Fenchel-dual properties and gradient-mapping inequalities to relate approximate optimization of a strongly convex regularized objective to the relevant distance and gradient bounds.

  • Fenchel duality: The proof introduces Fenchel duality for a proper convex function and uses ∇h∗(β)=arg maxy{y⊤β−h(y)}.Strong convexity of h makes its dual smooth, enabling the subsequent inequality.
  • Setup: Lemma 5.5 considers the unique minimizer x∗ of G and an arbitrary feasible vector x under the specified step-size range.The argument applies to the regularized objective used by the method.
  • Proof strategy: The proof applies a gradient-mapping inequality, bounds the inner product with Young’s inequality, and combines the resulting relations.The cited derivation also uses non-negativity of the gradient-mapping norm.
  • Conditions: The required convexity and smoothness conditions follow because the regularized function is convex and (L+2σ)-smooth.This observation justifies applying the cited gradient-mapping lemma.

D.1 Proof of Lemma 6.1

Lemma 6.1 is justified by standard identities for centered random vectors, a norm-sum inequality, and the L-smoothness of each fi(·).

  • D.1 Proof of Lemma 6.1: Lemma 6.1 establishes the stated result using several elementary expectation and smoothness inequalities.The proof invokes centered-vector variance identities, a bound on sums of p vectors, and the L-smoothness of each fi(·).
  • D.1 Proof of Lemma 6.1: E[∥a + b∥2] = E[∥a∥2] + ∥b∥2 when a is centered and b is nonrandom.The condition is E[a] = 0.
  • D.1 Proof of Lemma 6.1: For any random vector ζ, E∥ζ − Eζ∥2 = E∥ζ∥2 − ∥Eζ∥2.This identity supplies one of the proof’s intermediate inequalities.
  • D.1 Proof of Lemma 6.1: For p vectors, ∥a1 + · · · + ap∥2 ≤ p∥a1∥2 + · · · + p∥ap∥2.The proof also uses bx0 = ex in deriving this bound.

D.2 Proof of Lemma 6.4

The proof of Lemma 6.4 combines proximal optimality, convexity, smoothness, expectation, and telescoping arguments under a step-size restriction.

  • D.2 Proof of Lemma 6.4: The proof invokes the regret inequality for proximal mirror descent as a classical intermediate result.The passage identifies both the inequality and its proof as classical.
  • D.2 Proof of Lemma 6.4: The proximal subproblem yields a subgradient g ∈ ∂ψ(xt+1) satisfying α(xt+1 − xt) + w + g = 0.Convexity of ψ then supplies the inequality used to rearrange the update relation.
  • D.2 Proof of Lemma 6.4: Lemma 6.4 considers xs* = arg minx{F(x) + σ∥x − bxs∥2} when α ≤ 1/(2L + 4σ).The proof first computes properties of this regularized minimizer.
  • D.2 Proof of Lemma 6.4: The analysis uses that t and u do not depend on the randomness and that bxs+1 is sampled uniformly from {xs0, . . . , xsm−1}.Uniform sampling and σ-strong convexity of Fs(·) are used in the expectation argument.
  • D.2 Proof of Lemma 6.4: Taking expectation and applying the stated inequalities leads to a telescoping bound over t = 0, 1, . . . , m − 1.The argument uses Fact D.1, Young’s inequality, and the choice u = xs*.
  • D.2 Proof of Lemma 6.4: The step-size condition α ≤ 1/(2L + 4σ) also implies 1/(2σα) ≥ 1, enabling the final division and rearrangement.The proof additionally uses bxs0 = bxs.

D.3 Proof of Lemma 6.5

Lemma 6.5 follows by telescoping Lemma 6.4 across all p subepochs and applying the listed step-size conditions, noise bound, and strong convexity.

  • D.3 Proof of Lemma 6.5: Lemma 6.5 assumes α ≤ 1/(2L + 4σ), α ≥ 8/(σm), and α ≤ σ/(4p^2L^2).These three restrictions are stated together as the lemma’s conditions.
  • D.3 Proof of Lemma 6.5: Telescoping Lemma 6.4 over subepochs s = 0, 1, . . . , p − 1 produces the main intermediate bound.The resulting expression includes terms involving ∥bxs − bxs+1∥2 and Fs(bxs) − Fs(xs*).
  • D.3 Proof of Lemma 6.5: The proof uses 4αp^2L^2 ≤ σ and the definition Fs(y) = F(y) + σ∥y − bxs∥2.These substitutions simplify the intermediate inequality.
  • D.3 Proof of Lemma 6.5: The stochastic error term is controlled using E[∥e∥2] ≤ VB from Claim 6.2.This bound is applied before rearranging the inequality.
  • D.3 Proof of Lemma 6.5: Applying σ-strong convexity of Fs(·) yields the desired inequality after the final rearrangement.The proof concludes immediately after this strong-convexity step.
Loading 1708.08694v4…