PaperlayerView exact revision on arXiv

Source-linked AI summary

Neon2: Finding Local Minima via First-Order Oracles

Zeyuan Allen-Zhu, Yuanzhi Li

arXiv:1711.06673v3cs.LGcs.DScs.NEmath.OCstat.ML

TL;DR

Stationary-point methods may not find approximate local minima, and Hessian-free methods rely on Hessian-vector products. Neon2 uses gradient-based updates for negative-curvature search and converts methods across stochastic and deterministic settings; the paper reports first-order conversions that retain the performance of Natasha2 and CDHS.

  • Problem

    The paper asks whether stationary-point-finding algorithms can be turned into local-minimum-finding ones.

    Source: §1 · p. 2

  • Method

    Neon2 uses gradient differences in perturbed updates to obtain negative-curvature information and support first-order conversions.

    Source: §1.1.1 · p. 3, §1.1.2 · p. 4, §3 · p. 8

  • Results

    Neon2 converts Natasha2 and CDHS into first-order methods without hurting their performance, with stochastic-gradient computations in the finite-sum setting.

    Source: §1.1.1 · p. 3, §1.1.2 · p. 4, §1.1.3 · p. 4

  • Takeaways & Limitations

    The conversions provide first-order routes to approximate local-minimum finding in the stochastic and deterministic settings.

    Source: §1.1.1 · p. 3, §1.1.2 · p. 4, §1.1.3 · p. 4

    Converting a stationary-point method with gradient complexity T yields local-minimum finding with complexity at least T.

    Source: §1.2 · p. 6

Abstract

from arXiv · show

We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algorithm's performance. As applications, our reduction turns Natasha2 into a first-order method without hurting its performance. It also converts SGD, GD, SCSG, and SVRG into algorithms finding approximate local minima, outperforming some best known results.

1 Introduction

The introduction asks how to turn stationary-point methods into local-minimum methods and Hessian-free methods into first-order ones. It presents Neon2 as a stable gradient-based negative-curvature search, then applies it across online, deterministic, and finite-sum settings.

1 Introduction

  • The motivating gap is that stationary-point methods may return points that are not approximate local minima, while Hessian-vector products can be less simple to implement than gradients.The introduction frames the challenge as converting stationary-point algorithms to local-minimum algorithms and Hessian-free methods to first-order ones.Source: §1 · p. 2

1.1 From Hessian-Vector Products to First-Order Methods

  • A polynomially small finite-difference step can replace Hessian-vector products when the algorithms are implemented stably, and Neon2 converts negative-curvature-search subroutines into first-order processes.The gradient difference approximates a Hessian-vector action; stability avoids requiring an inverse-exponentially small step.Source: §1.1 · p. 3

1.1.1 Online Setting

  • Neon2online solves negative-curvature search with eO(1/δ^2) stochastic gradients, matching Oja’s complexity and its stated information-theoretic optimality up to log factors.Plugging it into Natasha2 yields a stochastic first-order method finding approximate local minima without hurting Natasha2’s performance.Source: §1.1.1 · p. 3

1.1.2 Offline Deterministic Setting

  • Neon2det converts CDHS into a first-order method without hurting performance, retaining its approximate-local-minimum guarantee at the stated full-gradient complexity.The introduction contrasts this with the “convex until guilty” method, which has the same complexity but may not guarantee approximate local minima.Source: §1.1.2 · p. 4

1.1.3 Offline Finite-Sum Setting

  • Neon2finite converts finite-sum shift-and-invert and CDHS into first-order methods, with the latter retaining its performance for approximate local-minimum finding.The introduction specifies stochastic gradient computations for the converted CDHS method.Source: §1.1.3 · p. 4

1.2 From Stationary Points to Local Minima

  • Theorem 7a is described as removing the poly(d) factor, achieving T = eO(1/ε^4) whenever δ ≥ ε^(2/3), and providing a simpler analysis.For GD, the paper reports eO(1/ε^2) full gradients to find (ε, ε^(1/2))-approximate local minima.Source: §1.2 · p. 6
  • Neon2 converts GD into an approximate local-minimum-finding method, requiring eO(1/ε²) full gradients to find (ε, ε^1/2)-approximate local minima without hurting GD’s performance.For Neon2+SVRG, the result matches Reddi et al. [25] without Hessian-vector product computations.Source: §1.2 · p. 6
  • The conversion has gradient complexity at least T, the cost of the underlying algorithm for finding an ε-approximate stationary point.The combined method alternates stationary-point finding with escaping saddle points.Source: §1.2 · p. 6

2 Preliminaries

The preliminaries define the nonconvex minimization target and the smoothness and variance assumptions used to analyze it. They also establish notation for norms, random sampling, and positive-semidefinite matrix ordering.

2 Preliminaries

  • The notation uses the Euclidean norm, uniform random sampling from [n], and A ⪰ B to mean that A − B is positive semidefinite.For symmetric A, A ⪰−σI means every eigenvalue is at least −σ.Source: §2 · p. 6

2.1 Problem and Assumptions

  • The goal is to find an (ε, δ)-approximate local minimum x with ∥∇f(x)∥≤ε and ∇2f(x) ⪰−δI.Both f and each component fi may be nonconvex.Source: §2.1 · p. 7
  • Each fi is assumed L-smooth and L2-second-order smooth, and stochastic gradients have bounded variance V; the variance assumption is only needed for online algorithms.The paper notes that Neon2’s gradient complexity depends polynomially on f’s second-order smoothness, while time complexity depends logarithmically on each fi’s second-order smoothness.Source: §2.1 · p. 7

3 Neon2 in the Online Setting

Neon2online uses stochastic gradient differences to search for negative curvature without Hessian-vector products. Its output is either a certificate that the Hessian has no eigenvalue below −δ or a unit direction of sufficiently negative curvature; repeated trials can boost confidence.

3 Neon2 in the Online Setting

  • Neon2online repeatedly invokes its weaker search and verification procedure to boost success probability to 1 − p.The verification lemma uses m = Θ(L2 log(1/p)/δ2) samples when ∥v∥≤δ/(8L2).Source: §3 · pp. 7, 9
  • For every x0 ∈ Rd, δ ∈ (0, L], and p ∈ (0, 1), with probability at least 1 − p, if the output v ≠ ⊥, then ∥v∥2 = 1 and v⊤∇2f(x0)v ≤ −δ/2.Source: §3 · p. 8
  • The theorem states an O-bound on the total number of stochastic-gradient evaluations.The supplied theorem passage does not include the bound’s expression.Source: §3 · p. 8
  • Neon2online updates from a random perturbation using stochastic gradient differences and stops at its iteration limit or when displacement from x0 exceeds r.While iterates remain within distance r, the gradient difference approximates the Hessian-vector product up to O(r2) error.Source: §3 · p. 8

4 Neon2 in the Deterministic Setting

Neon2det approximates Hessian-vector products with gradient differences and uses a Chebyshev-polynomial procedure to find negative curvature. Under the stated smoothness assumptions, it returns either a Hessian lower-bound certificate or a negative-curvature direction, with a bound on full-gradient evaluations.

4 Neon2 in the Deterministic Setting

  • With probability at least 1 − p, Neon2det’s output v satisfies that if v ≠ ⊥, then ∥v∥2 = 1 and v⊤∇2f(x0)v ≤ −δ/2.Source: §4 · p. 9
  • The theorem states an O-bound on the total number of full-gradient evaluations.The supplied theorem passage does not include the bound’s expression.Source: §4 · p. 9
  • The Chebyshev polynomial keeps values bounded on [−1, 1] while growing on larger arguments, enabling faster amplification of eigenvalues above the threshold than the power-method approach.The method seeks to compute x0 + Tt(M)ξ.Source: §4 · p. 10
  • Neon2det replaces Hessian-vector products with gradient differences to approximate the matrix-vector operations needed by its Chebyshev-polynomial search.The theorem assumes f is L-smooth and L2-second-order smooth.Source: §4 · pp. 9–10
  • Because Chebyshev coefficients can be as large as 2^O(t), the method uses backward recurrence to keep the computed result sufficiently close to the exact polynomial value.The passage identifies this as the stability theory of computing Chebyshev polynomials.Source: §4 · p. 10

5 Neon2 in the Finite-Sum Setting

The finite-sum setting uses shift-and-invert to find negative curvature, with matrix inversion reduced to a convex optimization problem. Neon2finite approximates the required Hessian-vector products using gradient differences; the section states a high-probability curvature guarantee and a stochastic-gradient evaluation bound.

5 Neon2 in the Finite-Sum Setting

  • The finite-sum shift-and-invert approach expresses the matrix as a finite sum and uses convex optimization to compute the required inverse-vector product.The section frames computing By as minimizing a convex quadratic function.Source: §5 · p. 11
  • Neon2finite approximates each Hessian-vector product with a gradient difference, enabling a stochastic first-order method to compute the shift-and-invert update.For a stochastic gradient at z, it uses ∇fi(x0 + z) − ∇fi(x0) to approximate ∇2fi(x0)·z.Source: §5 · p. 11
  • The authors state that their noise-stability proof is omitted because its detailed theoretical analysis would complicate the paper.They say performance should be unaffected as long as the norm of z is bounded.Source: §5 · p. 11
  • If Neon2finite returns v ≠ ⊥, v is unit length and satisfies v⊤∇2f(x0)v ≤ −δ/2.The guarantee is stated with probability at least 1 − p under the section's smoothness assumptions.Source: §5 · p. 11
  • The section states a stochastic-gradient evaluation bound whose eO notation hides logarithmic factors in d, 1/p, and L/δ.The supplied bound does not include its leading expression.Source: §5 · p. 11

6 Applications of Neon2

The applications section adapts Neon2 to existing optimization methods, with individual analyses for SGD, GD, Natasha2, CDHS, SCSG, and SVRG. The authors note that they do not have a generic statement for applying the reduction to any algorithm.

6 Applications of Neon2

  • The paper applies Neon2 to SGD, GD, SCSG, SVRG, Natasha2, and CDHS, but gives no generic guarantee for applying it to any algorithm.The authors say the applications must therefore be proved individually.Source: §6 · pp. 11–12

6.1 Applying Neon2 to SGD and GD

  • Neon2+SGD tests for negative curvature when SGD finds a point with small gradient, while Neon2+GD substitutes full gradient descent and Neon2det.The results state that both algorithms output an (ε, δ)-approximate local minimum with probability at least 1 − p.Source: §6.1 · pp. 12–13

6.2 Applying Neon2 to Natasha2 and CDHS

  • Neon2online replaces Oja’s algorithm in Natasha2, and Neon2det or Neon2finite replaces Lanczos in CDHS, with performance stated to be unharmed.The section describes the resulting methods as first-order; Natasha2 uses stochastic gradients, while CDHS can use full or stochastic gradients.Source: §6.2 · p. 13

6.3 Applying Neon2 to SCSG and SVRG

  • Neon2+SCSG tests whether the endpoint of an epoch is a local minimum, because its descent guarantee concerns the expected gradient at that endpoint.This differs from the SGD approach, which tests the current point; the section says the altered test requires a different proof.Source: §6.3 · p. 14
  • For SCSG, mini-batch size one is not necessarily optimal, and the authors identify a batch-size tradeoff in their parameter choice.When the chosen batch size exceeds B, the analysis instead runs Neon2+SGD to simplify the proof.Source: §6.3 · p. 14
  • The section gives probability 2/3 guarantees that Neon2+SCSG and Neon2+SVRG output approximate local minima, with confidence boosting noted for SCSG.Their stated complexity expressions are incomplete in the supplied passages.Source: §6.3 · p. 15

A.1 Auxiliary Lemmas

  • The auxiliary lemmas include a concentration result for a nonnegative recurrence and a matrix inequality for bounded random symmetric matrices.The recurrence condition includes a lower bound on the conditional expectation of its coefficient; the matrix lemma assumes E[B] = −A.Source: §A.1 · p. 16

A.2 Revisiting Oja’s Method

This appendix restates a prior theorem on products of random matrices for the paper’s analysis. It describes a change of variables used to meet the prior theorem’s assumptions, without changing the algorithm.

A.2 Revisiting Oja’s Method

  • The appendix credits [7] with the underlying theorem and says its restatement uses simple mathematical manipulations without improving the constants.The proof applies a change of variables for analysis only, without requiring an algorithm change.Source: §A.2 · p. 17
  • The restated theorem assumes i.i.d. random matrices bounded in norm with expectation −A, where A has a nonnegative maximum eigenvalue.The displayed theorem statement also introduces a Gaussian vector and learning-rate parameters, but their full conditions are not present in the supplied passages.Source: §A.2 · p. 17
  • To apply the prior theorem, the proof shifts and rescales the matrices so the transformed matrices lie between zero and the identity.The text explicitly characterizes this change of variables as an analysis device rather than an algorithmic modification.Source: §A.2 · p. 17

A.3 Proof of Lemma 3.1

The proof analyzes Neon2online’s perturbed stochastic-gradient trajectory and its termination rule. It uses norm-growth and negative-curvature arguments to show that the returned direction has the required curvature when the procedure terminates.

A.3 Proof of Lemma 3.1

  • Neon2online starts with a Gaussian perturbation and updates using stochastic gradient differences relative to the starting point.The proof tracks the resulting iterates and their relation to the perturbation.Source: §A.3 · p. 19
  • The proof establishes that the weak procedure does not terminate before T0 and terminates by T1 with high probability, using a norm-growth argument.The passages state that the iterate remains within radius r up to T0 and reaches the termination condition by T1.Source: §A.3 · pp. 20–21
  • At termination, the proof combines the negative-curvature property with an error bound to establish curvature for the returned normalized displacement.The returned vector is the normalized difference between the terminating iterate and the starting point; otherwise the procedure outputs ⊥.Source: §A.3 · pp. 19, 22

A.4 Proof of Lemma 3.2

The Lemma 3.2 proof uses bounded i.i.d. random variables, while the appendix describes an inexact backward recurrence for stable Chebyshev computation and its error analysis.

A.4 Proof of Lemma 3.2

  • The proof defines i.i.d. variables bounded by L∥v∥² and concludes by applying the assumptions on ∥v∥² and the chosen sample size m.Source: §A.4 · p. 22

B.1 Stable Computation of Chebyshev Polynomials

  • Inexact backward recurrence approximates the Chebyshev computation using an approximate matrix-vector algorithm, and its output equals the exact recurrence output when ε = 0.Source: §B.1 · p. 23
  • The stable Chebyshev-sum theorem gives an error analysis under eigenvalue and parameter conditions, with ε constrained by 1/(4NCU).Source: §B.1 · p. 23

B.2 Proof of Theorem 3

The proof uses a Chebyshev-polynomial construction to find a negative-curvature direction without Hessian-vector products, and establishes a high-probability curvature guarantee. It also includes auxiliary claims for estimating the gradient norm and analyzing perturbations.

B.2 Proof of Theorem 3

  • The method approximates M-vector products using gradient differences, enabling iterative approximation of x0 + Tt(M)ξ without Hessian-vector products.The recurrence sets y0 = 0, y1 = ξ, and yt = 2M(yt−1) − yt−2; the resulting iterate approximates the Chebyshev-polynomial update.Source: §B.2 · pp. 23–24
  • With probability at least 1 − p, when λmin(∇²f(x0)) ≤ −δ, the proof obtains a unit vector v with vᵀ∇²f(x0)v ≤ −1.Source: §B.2 · pp. 24–25
  • The proof argues termination by bounding the iterate displacement to reach at least r by iteration T1 ≤ T.Source: §B.2 · p. 24

C.1 Auxiliary Claims

  • A median of gradient estimates is compared with 3ε/4 to distinguish a gradient norm at most ε from one at least ε.Source: §C.1 · p. 25

C.2 Proof of Theorem 7a

Theorem 7a’s proof establishes that any returned iterate meets the approximate stationarity and curvature conditions, then bounds the algorithm’s gradient-computation cost.

C.2 Proof of Theorem 7a

  • Whenever the algorithm outputs xt, it satisfies ∥∇f(xt)∥ ≤ ε and ∇²f(xt) ⪰ −δI.Source: §C.2 · p. 26
  • When the ordinary update is reached, the proof establishes expected objective decrease of at least Ω(ε²/L); the negative-curvature branch instead has vᵀ∇²f(y0)v ≤ −δ.Source: §C.2 · p. 26
  • Each iteration is dominated by eO(B) stochastic-gradient computations for the update and gradient-norm estimate.Source: §C.2 · p. 26

C.3 Proof of Theorem 7b

Theorem 7b’s proof uses a counting argument to show Neon2+SCSG returns an iterate with the required stationarity and curvature properties with probability at least 2/3. It also bounds the per-iteration gradient-computation cost.

C.3 Proof of Theorem 7b

  • The termination argument compares N1, the number of Neon2online invocations, with N2, the number of negative-curvature updates, and concludes when N1 > N2.Source: §C.3 · p. 27
  • A negative-curvature update yields an expected objective decrease of at least δ³/(12L²), which bounds the expected number of such updates.Source: §C.3 · p. 27
  • With probability at least 2/3, the algorithm outputs an iterate satisfying ∥∇f(xt+1/2)∥ ≤ ε and ∇²f(xt+1/2) ⪰ −δI.Source: §C.3 · pp. 26–27
  • Each iteration uses eO(B) stochastic-gradient computations for SCSG and gradient-norm estimation, plus eO(L²/δ²) for Neon2online.Source: §C.3 · p. 27
Loading 1711.06673v3…