PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding Approximate Local Minima Faster than Gradient Descent

Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, Tengyu Ma

arXiv:1611.01146v4math.OCcs.DScs.NEstat.ML

TL;DR

Global optimization of non-convex objectives is NP-hard, motivating efficient methods for finding approximate local minima. The paper presents FastCubic, a second-order algorithm for smooth non-convex optimization, including neural-network training. It reports a provable linear-time bound and faster running time than known critical-point methods over a range of parameters.

  • Problem

    Global minimization of non-convex objectives is NP-hard, motivating the search for efficient algorithms that find approximate local minima.

    Source: §1 · p. 2

  • Method

    FastCubic uses cubic regularization and approximate cubic minimization to find an approximate local minimum for smooth non-convex functions.

    Source: §1 · p. 2, §1.2 · p. 4

  • Results

    FastCubic has a provable linear-time bound for approximate local minima and is faster than known critical-point methods for a wide range of parameters.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The algorithm applies to a general machine-learning optimization setting that includes training deep neural networks.

    Source: §1 · p. 2

    The paper does not attempt to improve the constant dependency in its simplest result.

    Source: §4 · p. 7

Abstract

from arXiv · show

We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and the number of training examples. The time complexity of our algorithm to find an approximate local minimum is even faster than that of gradient descent to find a critical point. Our algorithm applies to a general class of optimization problems including training a neural network and other non-convex objectives arising in machine learning.

1 Introduction

Because global optimization of non-convex objectives is NP-hard, the paper targets approximate local minima and presents FastCubic, a provable linear-time algorithm for smooth non-convex optimization. It applies to machine-learning objectives, including neural-network training, and its running-time bound is also faster than known critical-point methods for a range of parameters.

1 Introduction

  • FastCubic finds approximate local minima in provable linear time for a general machine-learning optimization setting that includes deep neural-network training.Its bound is also the fastest known for finding a critical point over a wide range of parameters.Source: §1 · p. 2
  • Global minimization of non-convex objectives is NP-hard, so the paper focuses on approximate local optimality rather than global optima.Experiments cited in the paper suggest that fast convergence to a local minimum is sufficient for neural-network training, whereas convergence to a critical point may not be.Source: §1 · p. 2

1.1 Related work

  • Prior local-minimum methods include noise-injected SGD with a large polynomial running time, while gradient descent's local-minimum convergence rates and required step sizes were unknown.A concurrent accelerated-gradient method was reported to attain the same running time as this paper by a different technique.Source: §1.1 · p. 4

2 Preliminaries and Main Theorem

This section sets the smoothness and access assumptions for the optimization problem, then states the main results for the finite-sum setting. It also relates approximate local minima to true local minima under a strict-saddle condition.

2 Preliminaries and Main Theorem

  • The analysis assumes Lipschitz continuity of the gradient and Hessian and defines complexity parameters for gradient and Hessian-vector access.Source: §2 · p. 5
  • The finite-sum setting assumes f is an average of component functions with bounded Hessians and includes supervised learning such as neural networks and generalized linear models.Source: §2 · p. 5, §2.1 · p. 6
  • For an (α, β, γ)-strict-saddle function and ε < min{α, β^2}, an ε-approximate local minimum is γ-close to a local minimum.Source: §2 · p. 5

2.1 Main Results

  • Theorem 1 states the FastCubic output guarantee for the finite-sum setting, with logarithmic factors hidden in its running-time bound.Source: §2.1 · p. 6
  • The running-time framework invokes approximate matrix inversion and PCA subroutines, with accelerated SVRG specified for the finite-sum case.Source: §2.1 · p. 6

3 Our Fast Cubic Regularization Algorithm

FastCubic repeatedly approximately minimizes a cubic model to construct an update. FastCubicMin supplies candidate steps and is analyzed through model-approximation, termination, and running-time guarantees.

3 Our Fast Cubic Regularization Algorithm

  • FastCubicMin returns candidate vectors, and the algorithm selects between v and λvmin/(2L) by choosing the one with the smaller cubic-model value.Source: §3 · p. 7
  • FastCubicMin either obtains a 1/3000 multiplicative approximation to the model minimum or meets its stopping condition, with additional guarantees on the output vector and gradient.Source: §3 · p. 7
  • FastCubic iteratively calls FastCubicMin and stops when the model value exceeds the stated negative threshold.Source: §3 · p. 7
  • The paper’s roadmap assigns FastCubicMin’s sufficient conditions and running-time analysis to later sections.Source: §3 · p. 7

4 Theorem 2 implies Theorem 1

The section derives Theorem 1 from FastCubicMin’s guarantees. At termination, the output satisfies the stated approximate local-minimum conditions; the paper notes that its constant dependencies are not optimized.

4 Theorem 2 implies Theorem 1

  • The authors state that they did not try to improve the constant dependency in the paper.Source: §4 · p. 7
  • At termination, FastCubic’s output has gradient norm at most ε and minimum Hessian eigenvalue at least the stated negative tolerance.Source: §4 · p. 8
  • The running-time argument bounds the number of non-final iterations and combines that bound with Theorem 2-c.Source: §4 · p. 8

5 Characterization Lemma of the Minimizer h∗

The section characterizes a minimizer of the cubic model through a scalar shift of the Hessian and a corresponding linear system. It also establishes uniqueness of the shift and gives an upper-bound argument for it.

5 Characterization Lemma of the Minimizer h∗

  • A vector h* minimizes m(h) exactly when some λ* ≥ 0 makes H + λ*I positive semidefinite, satisfies (H + λ*I)h* = −g, and obeys ∥h*∥ = 2λ*.Source: §5 · p. 8
  • The scalar λ* in the minimizer characterization is unique.Source: §5 · p. 8
  • The proof bounds λ* using the gradient, the Hessian shift, and a lower bound on the shifted Hessian’s minimum eigenvalue.Source: §5 · p. 8

6 Sufficient Conditions for Theorem 2-a and 2-b

The section gives sufficient conditions under which the outputs of the cubic-minimization procedure support Theorems 2-a and 2-b. It distinguishes a direct approximate-minimizer case from a harder case that also uses an approximate lowest-eigenvector.

6 Sufficient Conditions for Theorem 2-a and 2-b

  • Case 1 requires v to approximate −(H + λI)−1g and its norm to be approximately 2λ/L.The section relates this case to the characterization of the minimizer of m(h).Source: §6 · p. 9
  • Case 2 combines an approximate inverse-Hessian vector with a bound on L∥v∥ and an approximate lowest-eigenvector condition.The section says either v or λvmin/(2L) will be an approximate minimizer when the stated conditions hold.Source: §6 · p. 9
  • Under Case 1, the approximate solution has m(v) ≤ m(h∗) + 1/(250κ^3L^2).The section extends the exact characterization to nonzero approximation error ˜ε.Source: §6 · p. 9
  • The two Case 2 claims yield a choice among candidate vectors with a bound on m(h∗) relative to m(h′) or a negative-threshold alternative.The supplied passage states the alternatives but does not fully specify the candidate set.Source: §6 · p. 9

7 Main Algorithms for Theorem 2

FastCubicMin adjusts a regularization parameter and uses approximate linear solves, binary search, or an approximate eigenvector to produce outputs meeting sufficient conditions for the main lemmas. The appendix also sketches why Hessian-vector products can be computed in linear time for relevant circuit-based objectives.

7 Main Algorithms for Theorem 2

  • The algorithm starts at λ0 = 2B, then decreases λ and uses approximate inverse-Hessian vectors to choose among termination, binary search, and eigenvector computation.The three branches correspond to whether L∥v∥ is approximately equal to, larger than, or smaller than 2λi.Source: §7 · p. 10
  • FastCubicMin returns λ, v, and vmin satisfying one of Main Lemma 1’s sufficient conditions.Main Lemma 3 also gives a running-time guarantee, though its expression is not present in the supplied passage.Source: §7 · p. 10

7.1 Correctness Half of Main Lemma 3

  • The correctness proof checks that the algorithm’s output satisfies Main Lemma 1, which in turn supplies the assumptions used to derive Theorem 2’s parts.The proof identifies Theorem 2-a, 2-b, and 2-c with Main Lemmas 1, 2, and 3, respectively.Source: §7.1 · p. 12

A Computing Hessian-Vector Product in Linear Time

  • For differentiable circuits of size N, back-propagation computes the gradient in O(N + d) time; applying it to g(x) = ⟨∇f(x), v⟩ gives a linear-time Hessian-vector product under the stated circuit assumptions.The appendix assumes twice-differentiable circuits for the Hessian-vector argument.Source: A Computing Hessian-Vector Product in… · p. 13

B Proof of Lemma B.1 and Corollary 4.1

This appendix proves Lemma B.1 and Corollary 4.1 by controlling first- and second-order conditions near xt. The proof uses Hessian Lipschitz continuity to relate derivatives at nearby points.

B Proof of Lemma B.1 and Corollary 4.1

  • The proof first establishes a first-order condition for the point xt + h′.The supplied passage identifies this as the first part of the proof of Lemma B.1.Source: B Proof of Lemma B.1 and Corollary 4.1 · p. 13
  • Hessian Lipschitz continuity is used to control the gradient at xt + h′ and establish the lemma’s first conclusion.The cited passage states that this bound proves the first conclusion, but the bound itself is not included.Source: B Proof of Lemma B.1 and Corollary 4.1 · pp. 13–14
  • For the second-order condition, the proof bounds Hessian change by L∥h′∥ and then considers cases based on the minimum eigenvalue at xt.The supplied excerpt does not preserve the resulting curvature bound.Source: B Proof of Lemma B.1 and Corollary 4.1 · p. 14

C Proof of Lemma 5.1 and Corollary 5.2

The appendix characterizes minimizers of the cubic model through a system involving a regularization parameter and a shifted linear system. It establishes uniqueness properties of that parameter and supplies bounds used in the proofs of Claims 6.1–6.3.

C Proof of Lemma 5.1 and Corollary 5.2

  • The system’s λ′ is unique and satisfies λ′ ≥ −λmin(H); when λ′ is strictly larger, its corresponding h′ is unique and equals −(H + λ′I)−1g.At the boundary λ′ = −λmin(H), the solution may instead include a component in the lowest eigenspace, provided g is orthogonal to that eigenspace.Source: C Proof of Lemma 5.1 and Corollary 5.2 · p. 15
  • A minimizer h∗ of m(h) is characterized by λ∗ ≥ 0, H + λ∗I ⪰ 0, (H + λ∗I)h∗ = −g, and ∥h∗∥ = 2λ∗.The appendix proves both directions of this characterization.Source: C Proof of Lemma 5.1 and Corollary 5.2 · pp. 16–17

D.1 Proof of Claim 6.1

  • Claim 6.1 bounds m(v) above by m(h∗) + 1/(250κ^3L^2) under its Case 1 and approximation-error conditions.The following proof subsections also derive bounds for Claims 6.2 and 6.3; the excerpt gives an intermediate lower bound y ≥ 2m(v) − 1/16κ^3L^2.Source: §D.1 · p. 18, §D.2 · p. 21

E Proof of Main Lemma 2

Under the stated premise on m(h*), Main Lemma 2 proves conditions on the output vector by treating two cases. The proof bounds the output’s norm and gradient using approximate linear solves and case-specific assumptions.

E Proof of Main Lemma 2

  • The proof divides the analysis into Case 1 and Case 2 to establish the output-vector bounds.The case-specific arguments use the assumptions of each case and bounds involving λ* and the approximate-solve error.Source: E Proof of Main Lemma 2 · pp. 21–22
  • The output vector’s norm is bounded in terms of ∥h*∥ and a term involving κ and L.The supplied bound is ∥v∥ ≤ ∥h*∥ + 1/(20κL).Source: E Proof of Main Lemma 2 · p. 21
  • The proof bounds ∥∇m(v)∥ using the approximate-solve error and the output-vector norm.The derivation uses ∥H + λI∥ ≤ L² + 2B and a bound on ∥v∥; its displayed final expression is incomplete in the passages.Source: E Proof of Main Lemma 2 · pp. 21–22

F Proof of Lemma 7.2

Lemma 7.2 establishes iteration invariants for FastCubicMin by induction, including bounds on the shift and a termination condition. Its proof uses approximate inverse-vector computations to relate successive shifts.

F Proof of Lemma 7.2

  • Lemma 7.2 maintains shift bounds across iterations and gives a termination condition for FastCubicMin.The displayed invariants include λ_i + λ_min(H) ≥ 3/(10κ) and, at termination, λ_i + λ_min(H) ≤ 1/κ.Source: F Proof of Lemma 7.2 · p. 22
  • The invariants are proved by induction, with the base case using the definitions of B and L² and the initial shift λ₀.The proof propagates the upper bound using λ_i ≤ λ_{i−1}.Source: F Proof of Lemma 7.2 · p. 22
  • The proof relates the approximate vector computation to the largest eigenvalue of (H + λ_i I)⁻¹.It uses the displayed bounds on w̃⊤w and the inverse’s largest eigenvalue to derive implications for the next shift.Source: F Proof of Lemma 7.2 · pp. 22–23
  • The update and stopping conditions imply the successive-shift invariants asserted in Lemma 7.2.When the specified condition occurs, the algorithm outputs at Line 20; otherwise the update yields the stated relation between shifts.Source: F Proof of Lemma 7.2 · p. 23

G Proof of Main Lemma 3: Running Time Half

The running-time proof bounds FastCubicMin’s iterations and the cost of its inverse, power-method, and lowest-eigenvector computations. Together these bounds express its total time through the cost of approximate inverse-system solves.

G Proof of Main Lemma 3: Running Time Half

  • FastCubicMin uses at most O(log(Bκ)) outer loops because the shifted minimum eigenvalue decreases geometrically until termination.The proof bounds the starting quantity by 3B and keeps it above 3/(10κ) during iteration.Source: G Proof of Main Lemma 3: Running Time… · p. 23

G.1 Matrix Inverse

  • Every required inverse-vector computation has a bounded condition measure, at most 10κL².This bound applies during FastCubicMin and BinarySearch.Source: §G.1 · pp. 23–24
  • The matrix-inverse steps run in time Õ(T_inverse(κL², ε̃)).The proof relates approximate solve accuracy to the norm of the right-hand vector and invokes Theorem 2.4.Source: §G.1 · p. 24

G.2 Power Method

  • The power-method step obtains an approximate leading eigenvector of (H + λ_i I)⁻¹ using inexact matrix-vector products.The passage says sufficiently accurate products retain a constant-multiplicative approximation and cites [3, Appendix A].Source: §G.2 · p. 24

G.3 Lowest Eigenvector

  • The lowest-eigenvector step uses Shift and Invert to compute an approximate lowest eigenvector of H.The proof converts the task to finding a leading eigenvector of a positive semidefinite matrix and bounds the resulting Rayleigh quotient.Source: §G.3 · p. 24

G.4 Putting It All Together

  • Combining the iteration and subroutine bounds gives total FastCubicMin time Õ(T_inverse(κL², ε̃)).The stated Õ hides factors polylogarithmic in κ, L, L², B, and d.Source: §G.4 · pp. 24–25

H Proof of Lemma G.1

  • BinarySearch maintains a bracket for its shift and stops once the bracket width is at most ε̂.The proof relates each midpoint test to the approximate solution of a shifted linear system; the supplied passages do not preserve the complete iteration bound.Source: H Proof of Lemma G.1 · p. 25
Loading 1611.01146v4…