PaperlayerView exact revision on arXiv

Source-linked AI summary

First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time

Yi Xu, Rong Jin, Tianbao Yang

arXiv:1711.01944v3math.OCstat.ML

TL;DR

Existing analyses of first-order noise-based saddle-escape methods obscure how the noise works. The paper analyzes NEON procedures that use noise to extract negative curvature, then combines them with stochastic first-order algorithms; it reports almost-linear dependence on dimensionality for finding second-order stationary points.

  • Problem

    Existing first-order noise-based saddle-escape analyses are involved and do not make the mechanism of the added noise explicit, while first- and second-order approaches have developed largely separately.

    Source: §1 · p. 3

  • Method

    The paper analyzes NEON procedures that treat noise added to first-order information as a tool for extracting negative curvature, and combines them with existing stochastic first-order algorithms.

    Source: §1 · p. 3

  • Results

    The developed stochastic first-order algorithms are claimed to be the first with almost-linear dimensionality dependence for finding a second-order stationary point, with epsilon dependence competitive with or better than standard SGD and noisy variants.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The paper presents NEON as a way to promote first-order stochastic algorithms to second-order convergence guarantees and reports several such algorithms.

    Source: §6 · p. 14

    A rigorous analysis of algorithms using noisy finite-difference Hessian-vector products remains unresolved, and heuristic approaches may have numerical issues.

    Source: §1 · p. 3

Abstract

from arXiv · show

Two classes of methods have been proposed for escaping from saddle points with one using the second-order information carried by the Hessian and the other adding the noise into the first-order information. The existing analysis for algorithms using noise in the first-order information is quite involved and hides the essence of added noise, which hinder further improvements of these algorithms. In this paper, we present a novel perspective of noise-adding technique, i.e., adding the noise into the first-order information can help extract the negative curvature from the Hessian matrix, and provide a formal reasoning of this perspective by analyzing a simple first-order procedure. More importantly, the proposed procedure enables one to design purely first-order stochastic algorithms for escaping from non-degenerate saddle points with a much better time complexity (almost linear time in terms of the problem's dimensionality). In particular, we develop a {\bf first-order stochastic algorithm} based on our new technique and an existing algorithm that only converges to a first-order stationary point to enjoy a time complexity of {$\widetilde O(d/\epsilon^{3.5})$ for finding a nearly second-order stationary point $\bf{x}$ such that $\|\nabla F(bf{x})\|\leq \epsilon$ and $\nabla^2 F(bf{x})\geq -\sqrt{\epsilon}I$ (in high probability), where $F(\cdot)$ denotes the objective function and $d$ is the dimensionality of the problem. To the best of our knowledge, this is the best theoretical result of first-order algorithms for stochastic non-convex optimization, which is even competitive with if not better than existing stochastic algorithms hinging on the second-order information.

1. Introduction

The introduction frames saddle escape as a gap between first-order noise-based methods and Hessian-based methods. It presents NEON procedures for extracting negative curvature and combines them with stochastic first-order algorithms to seek nearly second-order stationary points.

1. Introduction

  • Mini-batch SGD and its variants need not escape non-degenerate saddle points, while noisy-SGD and SGLD analyses cover isotropic noise injected into the stochastic gradient.The cited noisy variants use sphere-sampled or Gaussian noise and have polynomial complexity with at least a fourth-power dependence on dimensionality.Source: §1 · p. 2
  • Hessian-based saddle-escape methods can have almost-linear dimensionality dependence when Hessian-vector products are computable in linear time.This provides a contrasting route to the dimensionality cost of noise-based first-order methods.Source: §1 · p. 2
  • Adding noise to first-order information is presented as a way to extract negative curvature from the Hessian, connecting two previously disconnected approaches to saddle escape.The paper formally analyzes simple procedures based on gradient descent and accelerated gradient descent for extracting a negative-curvature direction.Source: §1 · p. 3
  • The proposed framework combines NEON curvature extraction with existing stochastic first-order algorithms that target first-order critical points, to find points with gradient norm at most epsilon and minimum Hessian eigenvalue at least negative gamma.The paper denotes such a point a nearly (epsilon, gamma)-second-order stationary point.Source: §1 · p. 3
  • The proposed stochastic first-order algorithms are the first claimed to achieve almost-linear dimensionality dependence for finding a second-order stationary point, with epsilon dependence competitive with or better than standard SGD and noisy variants.The authors also describe their dependence on epsilon as competitive with existing second-order stochastic algorithms.Source: §1 · p. 3

2. Other Related Work

Prior stochastic first-order methods are described as targeting first-order stationary points, while some later approaches add second-order machinery for saddle escape. The paper positions NEON as a way to supply negative-curvature directions and discusses its connection to noisy power methods.

2. Other Related Work

  • NEON can strengthen first-order stochastic algorithms with first-order convergence guarantees by adding a procedure for escaping saddle points.The paper proposes combining NEON with SGD, stochastic momentum, mini-batch SGD, and SCSG.Source: §2 · p. 4
  • The related stochastic methods SCSG and Natasha1.5 are described as having iteration complexity O(1/epsilon^(10/3)) for finding a first-order stationary point in expectation.The cited passage states that Natasha1.5 has the same convergence and complexity as SCSG.Source: §2 · p. 4
  • Earlier stochastic algorithms used second-order information to compute negative curvature, which the authors say can be replaced by NEON procedures.The paper notes that one generic framework's requirements exclude algorithms such as SGD, stochastic momentum, and SCSG.Source: §2 · p. 4
  • NEON is viewed as a noisy power method on the Hessian or an augmented matrix, with Hessian-vector products estimated by finite differences using first-order information.Existing noisy-power-method analyses do not directly apply because their complexity or noise requirements are unsuitable for NEON; the authors instead adapt an analysis route related to the perturbed gradient method.Source: §2 · p. 4

3. Preliminaries

The section states smoothness and stochastic-noise assumptions, then reviews second-order methods for finding negative curvature and escaping non-degenerate saddle points.

3. Preliminaries

  • The stochastic objectives have Lipschitz-continuous gradients and Hessians, with bounds L1 and L2, respectively.The assumptions also bound the initial objective gap by Δ.Source: §3 · p. 5
  • Optional noise assumptions bound gradient deviations either through an exponential moment or a second moment; the latter supports expectation-based analysis.The text identifies the first two assumptions as standard for second-order convergence, the third as needed for high-probability analysis, and the last for expectation-based analysis.Source: §3 · p. 5
  • A unit negative-curvature direction supports an update that decreases the objective enough to escape a non-degenerate saddle point.When the gradient is unavailable, the update uses a Rademacher random variable.Source: §3 · pp. 5–6
  • The Power method iterates with I − η∇²f(x) to find a negative-curvature direction when the minimum Hessian eigenvalue is at most −γ.The text also describes Lanczos as finding such a vector with fewer Hessian-vector products.Source: §3 · p. 6
  • Hessian-vector products can be approximated using gradients, but the heuristic may be unstable for very small h.Convergence guarantees for Power and Lanczos with noise in the Hessian-vector approximation are described as underexplored.Source: §3 · p. 6

4. Extracting NC From Noise

NEON uses noise-initialized first-order updates to extract negative-curvature directions, with an accelerated variant and a minibatch extension. The section analyzes their guarantees and reports simulations comparing them with power and Lanczos methods.

4. Extracting NC From Noise

  • NEON starts from random noise and uses first-order gradient updates whose recurrence approximates the Power method, making its iterates close to a negative-curvature direction.The section presents gradient descent and accelerated-gradient procedures for extracting such a direction from a Hessian with an eigenvalue below −γ.Source: §4 · pp. 6–7
  • When NEON returns a nonzero vector, it certifies negative curvature; when it returns 0, the minimum Hessian eigenvalue is at least −γ with high probability.The guarantee applies at points whose Hessian has a negative eigenvalue, including non-degenerate saddle points.Source: §4 · pp. 7–8

4.1. Finding NC by Accelerated Gradient Method

  • NEON+ matches the Lanczos iteration complexity of O(1/√γ) for extracting negative curvature, improving on NEON’s O(1/γ) complexity.The theorem gives a high-probability curvature guarantee when NEON+ returns a nonzero vector and a corresponding minimum-eigenvalue bound when it returns 0.Source: §4.1 · pp. 8, 10
  • NCFind searches the history of iterates for a negative-curvature direction satisfying the paper’s target condition, rather than the modified-objective decrease targeted by NCE.Its condition check can detect cases where the history already contains such a direction.Source: §4.1 · p. 9

4.2. Stochastic Approach for Extracting NC

  • With sufficiently large minibatches, NEON applied to the sampled objective finds an approximate negative-curvature direction for the full objective, with IFO complexity eO(1/γ^3) for Algorithm 1 or eO(1/γ^2.5) for Algorithm 2.If the procedure returns 0, the minimum eigenvalue of the full Hessian is at least −2γ with high probability.Source: §4.2 · p. 10
  • In simulations, stochastic NEON variants found good directions faster by IFO calls than their full versions and were competitive with Lanczos; NEON+ converged faster than NEON.NEON and the Power method had overlapping curves; the stochastic comparison used a sample size of 100.Source: Figure 1 · p. 11, §4.2 · p. 11

5. First-order Algorithms for Stochastic Non-Convex Optimization

The section combines NEON saddle-point escape procedures with first-order stochastic algorithms to obtain high-probability second-order guarantees. It analyzes a general framework and gives instances for stochastic momentum, mini-batch SGD, and SCSG.

5. First-order Algorithms for Stochastic Non-Convex Optimization

  • If λ_min(∇²F(y_j))≤−γ, the escape component ensures E[F(x_{j+1})−F(y_j)]≤−Cγ³ for some C>0.The framework combines this decrease property with a first-order stochastic algorithm and a mini-batch condition check.Source: §5 · p. 12
  • With high probability, NEON-A returns y_j with ∥∇F(y_j)∥≤O(ε) and λ_min(∇²F(y_j))≥−2γ, with logarithmic factors hidden in the complexity bound.The guarantee follows under the stated properties of the first-order algorithm, escape step, and first-order-condition check.Source: §5 · pp. 12–13
  • NEON-SM finds an (ε,γ)-second-order stationary point with high probability under the stated bounded-gradient-moment condition and γ≥ε^(2/3).For γ=ε^(1/2), the stated IFO complexity is eO(1/ε⁴).Source: §5 · p. 13
  • For mini-batch SGD, the authors note that no γ≥ε^(2/3) requirement is needed because MSGD guarantees E[F(y_j)−F(x_j)]≤0.The corollary states that NEON-MSGD finds an (ε,γ)-SPP with high probability.Source: §5 · pp. 13–14
  • Under the conditions γ ≥ ε^(4/9) and b = 1, NEON-SCSG has an expected IFO complexity of eO(1/ε^3.33), according to the cited passage.Source: §5 · p. 14

6. Conclusions

The conclusion presents noise-initiated first-order procedures for extracting negative curvature and a framework for strengthening first-order stochastic algorithms. The appendices provide supporting descent, concentration, and sampled-Hessian arguments.

6. Conclusions

  • The paper proposes first-order procedures that use a noise-initiated sequence to extract negative curvature, alongside a framework for giving first-order stochastic algorithms second-order convergence guarantees.The authors describe the resulting algorithms as having state-of-the-art second-order convergence guarantees.Source: §6 · p. 14

Appendix A. Proof of Lemma 1

  • Moving along the extracted unit direction v decreases the objective when vᵀ∇²f(x)v≤−cγ, using a step size based on the directional gradient.The proof invokes the Hessian's L2-Lipschitz continuity.Source: Appendix A · pp. 16–17

Appendix B. Concentration inequalities

  • The concentration appendix gives probability bounds for sampled gradient and Hessian estimates and explains that iteration-level high-probability bounds extend to the final result by a union bound.The Hessian bound uses a sample-size condition involving log(2d/δ)/ε².Source: Appendix B · p. 17

Appendix C. Proof of Lemma 2

  • When the true Hessian has minimum eigenvalue at most −γ, the sampled Hessian retains a negative eigenvalue with high probability, allowing NEON or NEON+ to generate a negative-curvature vector.The proof also bounds the true minimum eigenvalue when the procedure returns zero.Source: Appendix C · p. 18

Appendix D. Proof of Theorem 4

The proof analyzes termination of NEON-A by tracking first- and second-order conditions and objective progress. It uses concentration bounds to relate sampled conditions to the true objective and derivatives.

Appendix D. Proof of Theorem 4

  • At termination, the proof uses sampled conditions at y_j and x_j, then concentration inequalities to obtain ∥∇F(y_j)∥≤O(ε) and λ_min(∇²F(y_j))≥−2γ with high probability.Before termination, it separates iterations according to whether the true gradient norm at y_j is at least ε.Source: Appendix D · p. 18
  • The analysis tracks whether a favorable case C3 has occurred and bounds the probability that it has not occurred by successive objective-progress arguments.The proof bounds expected objective decrease on iterations outside C3 by −θ times the probability of remaining outside it.Source: Appendix D · pp. 19–20
  • After eO(log(1/ζ)/θ) steps, the proof bounds the probability of encountering C3 at least once by 1−ζ/2, yielding a high-probability termination argument.The resulting IFO complexity is stated as eO(max(T_n+T_a+T_c)).Source: Appendix D · p. 20

Appendix E. Proof of Corollary 5

The proof of Corollary 5 applies stochastic-momentum bounds to the framework's first-order component. It uses a step-size condition and a restriction on γ to establish the needed expected objective-change bound.

Appendix E. Proof of Corollary 5

  • For stochastic momentum, the proof assumes η≤(1−β)/(2L1) when applying the cited convergence analysis.It also uses σ² as an upper bound on E[∥∇f(x;ξ)∥²].Source: Appendix E · p. 21
  • When ∥∇F(y_j)∥≤ε, the proof bounds E[F(y_j)−F(x_j)]≤ε² and uses γ≥ε^(2/3) to satisfy the two required inequalities.The bound follows from the stated ε(ε,α)=C′ε² relation.Source: Appendix E · p. 21

Appendix F. Proof of Corollary 6

The corollary proofs check that the NEON-MSGD and NEON-SCSG updates satisfy the conditions needed for the stated guarantees. The SCSG proof also records sample-size and per-epoch IFO requirements.

Appendix F. Proof of Corollary 6

  • NEON-MSGD has y_j = x_j, which establishes the second inequality of condition (15) in the Corollary 6 proof.The proof then considers the first inequality when the gradient norm is at least ε.Source: Appendix F · pp. 21–22

Appendix G. Proof of Corollary 7

  • The NEON-SCSG proof uses z_j = y_j and the per-epoch SCSG guarantee to verify condition (15).The proof identifies the required sample-size bound and states that each SCSG-Epoch has the same expected IFO complexity regardless of b.Source: Appendix G · pp. 22–23
  • The Corollary 7 proof requires |S1| ≥ eO(max(1/ε^2, 1/(γ^(9/2)b^(1/2)))) and gives expected IFO complexity 2|S1| for each SCSG-Epoch.The latter bound is stated to hold regardless of b because N in SCSG-Epoch has a geometric distribution.Source: Appendix G · p. 23

Appendix H. Proof of Theorem 2

The proof of Theorem 2 establishes that NEON detects negative curvature with high probability when the Hessian has an eigenvalue at most −γ. It bounds the iterates and compares trajectories initialized with a displacement along the minimum-eigenvalue direction.

Appendix H. Proof of Theorem 2

  • When λ_min(∇²f(x)) ≤ −γ, Lemma 5 states that NEON finds a qualifying iterate within t steps with probability at least 1 − δ.If NEON returns 0, the proof concludes that λ_min(∇²f(x)) ≥ −γ with high probability.Source: Appendix H · pp. 23, 25

H.1. Proof of Lemma 6

  • Lemma 6 bounds the iterates generated from an initial point of norm at most 2r, provided η ≤ c_max/L1.Under its stated conditions, the iterates remain within 2ĉP through the considered horizon.Source: Appendix H · p. 24

H.2. Proof of Lemma 7

  • Lemma 7 compares a trajectory initialized at u0 with one displaced by μre1, where e1 is the minimum-eigenvalue direction, to establish bounded-time potential decrease.The proof bounds both trajectories and uses their separation along e1 to show one reaches the decrease threshold.Source: Appendix H · p. 24, §H.2 · pp. 26–27

Appendix H. Proof of Theorem 2

  • For a bounded iterate, the proof uses Hessian Lipschitz continuity to convert the decrease in the local potential into a decrease in the objective.The comparison yields a quadratic-form decrease of at least 2F within the stated radius.Source: Appendix H · p. 25

Appendix I. Proof of Theorem 3

Theorem 3’s proof treats both termination by NCFind and the case where it does not terminate. In the latter case, it uses boundedness and a perturbed trajectory to establish negative-curvature detection with high probability.

I.2. Proof of Lemma 8

  • When inequality (32) does not hold, if λmin(∇²f(x)) ≤ −γ and ∥u0∥ ≤ 2r, then any η ≤ cmax/L1 yields ∥uτ∥ ≤ 6ĉP for all τ < T.Source: Appendix I · p. 30

I.3. Proof of Lemma 9

  • Lemma 9 analyzes a second trajectory initialized by displacing u0 along e, and bounds its time to reach the potential-decrease threshold.The proof states that, under its conditions, the horizon is less than ĉJ.Source: Appendix I · p. 30, §I.1 · p. 31

I.1. Continuing the Proof of Theorem 3

  • If NCFind does not terminate, Lemmas 8 and 9 are used to prove that NEON+ finds negative curvature with high probability.If NEON+ returns 0, the proof says λ_min(∇²f(x)) ≥ −γ holds with high probability.Source: §I.1 · pp. 31–32

Appendix J. Additional simulation results

Appendix K. Analysis of eigen-gap

The eigen-gap analysis studies the update matrix associated with accelerated gradient dynamics. Under the stated eigenvalue and step-size conditions, it establishes a lower bound on the gap between the top-k eigenspace and the remaining spectrum.

Appendix K. Analysis of eigen-gap

  • For λ1 ≤ … ≤ λk ≤ −γ < 0 ≤ λk+1 ≤ … ≤ λd and sufficiently small η ≤ 1/L1, Lemma 10 lower-bounds the top-k eigen-space gap by √(ηγ).The proof analyzes roots of a quadratic associated with the update matrix.Source: Appendix K · pp. 38–39
  • For Hessian eigenvalues λi ≤ 0, the discriminant is nonnegative, so the roots are real; evaluating h at 0, 1, and (1+ζ)(1−ηλi) places one root in (0,1) and another in (1,∞).Source: Appendix K · p. 39
  • The gap bound uses the choice ζ = 1 − √(ηγ/2) for the accelerated update.The analysis states the resulting gap is at least √(ηγ).Source: Appendix K · p. 40

Related papers

Loading 1711.01944v3…