Source-linked AI summary
Efficient approaches for escaping higher order saddle points in non-convex optimization
Anima Anandkumar, Rong Ge
TL;DR
High-dimensional nonconvex optimization can stall at degenerate saddle points that first- and second-order information cannot distinguish from local minima. The paper uses higher-order derivatives to construct an algorithm guaranteed to converge to a third-order local minimum, while establishing NP-hardness for finding fourth-order local minima.
Problem
Degenerate saddle points can resemble local minima to first- and second-order methods, while saddle points can delay progress toward a local optimum.
Source: §1 · pp. 1, 3Method
The algorithm alternates cubic-regularized second-order steps with third-order searches in a competitive subspace.
Source: §1.1 · p. 3Results
The algorithm is guaranteed to converge to a third-order local minimum, while finding a fourth-order local minimum is NP-hard even for a well-behaved function.
Source: §1.1 · p. 3Takeaways & Limitations
The paper provides a third-order method for addressing some problems caused by degenerate saddle points, but the same ideas cannot be generalized to higher orders.
Source: §7 · p. 15Algorithm 2 may escape a point that is already a local minimum when its third derivatives are large relative to its Hessian.
Source: §5 · p. 13
Abstract
from arXiv · showhide
Local search heuristics for non-convex optimizations are popular in applied machine learning. However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points such that the first and second order derivatives cannot distinguish them with local optima. In this paper we use higher order derivatives to escape these saddle points: we design the first efficient algorithm guaranteed to converge to a third order local optimum (while existing techniques are at most second order). We also show that it is NP-hard to extend this further to finding fourth order local optima.
1 Introduction
High-dimensional nonconvex optimization can leave algorithms stalled at saddle points, and first- and second-order tests can mistake degenerate saddles for minima. The paper develops third-order optimality methods, guarantees convergence to a third-order local minimum, and shows that finding fourth-order local minima is NP-hard.
1 Introduction
- In high dimensions, saddle points are widespread, and reaching even a local optimum is computationally hard in the worst case.The passage notes that ordinary gradient descent may remain at a saddle for an arbitrarily long time.Source: §1 · p. 1
1.2 Related Work
- Prior second-order and noisy-gradient methods require a strictly negative Hessian eigenvalue at a saddle, so degenerate saddles can evade them.When the Hessian is singular and positive semidefinite, higher-order derivatives may be needed to distinguish a saddle from a local optimum.Source: §1 · p. 2, §1.2 · p. 4
1 Introduction
- Degenerate critical points arise in overspecified neural networks and other models, as well as through symmetries such as neuron permutations.Examples discussed include Gaussian mixtures, radial basis function networks, ARMA models, and student-teacher networks.Source: §1 · p. 2
1.1 Summary of Results
- The proposed algorithm always converges to a third-order local minimum and finds a similar point in polynomial time.“Similar” means approximately satisfying the necessary and sufficient condition for a third-order local minimum.Source: §1.1 · p. 3
- The algorithm alternates cubic-regularized second-order steps with third-order steps that search a competitive subspace.The competitive subspace identifies where third-order derivatives are large relative to second-order information.Source: §1.1 · p. 3
- Finding a fourth-order local minimum is NP-hard, even for a well-behaved function.The hardness result is stated for functions with bounded derivatives and local minimizers within the unit ℓ2 ball.Source: §1.1 · p. 3
2 Preliminaries
The preliminaries classify critical points by their Hessians and explain why degenerate saddle points resist second-order methods. They also introduce matrix and tensor notation used for higher-order derivatives.
2.1 Critical Points
- A critical point is defined by a zero gradient, and Hessian eigenvalues distinguish local minima, local maxima, strict saddles, and degenerate points.Degenerate points have zero Hessian eigenvalues, with the remaining eigenvalues either nonnegative or nonpositive.Source: §2.1 · p. 5
- Second-order algorithms cannot handle degenerate saddle points, where the Hessian has zero eigenvalues and may be positive semidefinite.For a positive-semidefinite Hessian, the point satisfies the second-order local-minimum condition, which can leave higher-order behavior unresolved.Source: §2.1 · p. 5
2.2 Matrix and Tensor Notations
- The section introduces third-order derivative tensors and multilinear notation, including projection of a tensor onto a subspace.For vectors u, v, w, T(u, v, w) is a scalar; projecting T onto P applies the original tensor to projected vectors.Source: §2.2 · p. 6
- The tensor spectral norm is defined through unit-vector evaluations, and computing it is NP-hard, including for symmetric tensors.For symmetric tensors, the norm can be expressed as the maximum of T(u, u, u) over unit vectors u.Source: §2.2 · p. 6
3 Overview of Nestorov’s Cubic Regularization
This section reviews cubic regularization as a second-order optimization method and establishes its convergence guarantees. The method optimizes a local quadratic model with a cubic regularizer under a Lipschitz-Hessian assumption.
3 Overview of Nestorov’s Cubic Regularization
- Each step optimizes a degree-two Taylor approximation of the objective with a cubic regularizer, generating the next iterate.The cubic-regularized optimization problem can be solved in polynomial time.Source: §3 · pp. 6–7
- A cubic-regularization step moves at least μ(z) and decreases the objective by at least R∥z − x∥^3/12.Here z is the step output from x; the guarantee supports convergence analysis of the iterate sequence.Source: §3 · p. 7
- When the objective is bounded below, the sequence has iterates that increasingly satisfy the second-order optimality condition, with μ(x(i)) tending to zero.Small μ corresponds to a small gradient and no Hessian eigenvalue with large negative magnitude.Source: §3 · p. 7
- With a bounded initial level set, cubic regularization has a nonempty connected limit set whose points are all second-order local minima.The algorithm's guarantees are stated under the Lipschitz-Hessian smoothness assumption.Source: §3 · pp. 6–8
4 Third Order Necessary Condition
Under the paper’s smoothness assumption, this section gives a necessary and sufficient condition for third-order local optimality. It also states that the condition can be checked in polynomial time given the first three derivatives.
4 Third Order Necessary Condition
- The condition characterizes third-order local minima for a class of smooth functions, with proofs deferred to Appendix A.1.The section presents the condition under its stated third-order smoothness assumption.Source: §4 · p. 8
- The third-order condition can be verified in polynomial time given the gradient, Hessian, and third derivative.The verification computes the subspace where the Hessian quadratic form is zero, using SVD.Source: §4 · p. 8
- For functions satisfying Assumption 2, a point is third-order optimal if and only if it satisfies the paper’s third-order necessary condition.The condition includes requiring the third derivative to vanish along vectors in the zero-curvature subspace of the Hessian.Source: §4 · pp. 8–9
- The proof uses a Taylor expansion whose fourth-order remainder is bounded, allowing the local analysis to focus on terms through order three.The main challenge is balancing the positive part of the Hessian against the third derivatives.Source: §4 · p. 9
5 Algorithm for Finding Third Order Optimal Points
The algorithm alternates cubic regularization with a third-order step to make progress in competitive subspaces. Its progress measures vanish, and under a compact-level-set condition every limit point satisfies third-order necessary conditions.
5 Algorithm for Finding Third Order Optimal Points
- A competitive subspace has small Hessian eigenvalues but large third-derivative norm, so third-order information can offer progress there.The algorithm selects an eigensubspace where third-order contribution can exceed second-order contribution.Source: §5 · pp. 9–10
- Each iteration combines cubic regularization with a third-order step that seeks function improvement in a competitive subspace.The section assumes Assumptions 1 and 2.Source: §5 · pp. 9–10
- The tensor approximation step has expected iteration count at most 2 and returns a unit vector meeting its guarantee with Q = Bn^1.5.The guarantee compares the third-order tensor along the vector with the projected tensor’s Frobenius norm divided by Q.Source: §5 · p. 10
- Both the first- and second-order progress measure and the third-order progress measure go to zero as iterations increase.The first measure tracks first- and second-order progress; CQ(z) measures third-order progress.Source: §5 · pp. 11–12
- With a compact level set, every limit point of the iterates satisfies the third-order necessary conditions.The function values converge, and the theorem guarantees nonempty limit points under compactness.Source: §5 · p. 12
- Not every third-order local minimum can be a limit point: the algorithm may escape one when third derivatives are large relative to the Hessian.For f(x) = x^2 − 100x^3 + x^4, x = 0 is a local minimum that the algorithm may escape.Source: §5 · p. 13
- In the general case, a convergence rate is hard to obtain when the function may have higher-order local minima.Polynomial convergence rates are possible when the function has additional nice properties.Source: §5 · p. 13
- Under strict third-order-saddle conditions, sufficiently many polynomially many iterations place an iterate near a local minimum.The corollary’s iteration bound depends on n, L, R, Q, the initial objective gap, and the condition parameters.Source: §5 · pp. 13–14
6 Hardness for Finding a fourth order Local Minimum
Finding a fourth-order local minimum is NP-hard even for well-behaved functions. The proof reduces quartic nonnegativity to fourth-order local-minimum finding using a degree-6 regularizer.
6 Hardness for Finding a fourth order Local Minimum
- Well-behaved functions are infinitely differentiable and have local minimizers within the unit ℓ2 ball, where derivatives are bounded.The passage states that algorithms from previous sections can find a local minimum up to order 3, but not order 4.Source: §6 · p. 14
- Finding a fourth-order local minimum is NP-hard even when the function is guaranteed to be well-behaved.Well-behaved functions have all local minimizers inside the unit ℓ2 ball and are smooth with bounded derivatives there.Source: §6 · p. 14
- The reduction adds a degree-6 regularizer ||x||^6 to a degree-4 polynomial.If the polynomial is nonnegative, 0 is the only fourth-order local minimum; if it has negative directions, every fourth-order local minimum has negative function value.Source: §6 · p. 15
7 Conclusion
The paper presents an algorithm guaranteed to find a third-order local minimum to address degenerate saddle points, while showing that the approach does not extend to higher orders. It leaves open the existence of strict third-order saddle classes and algorithms for constrained optimization.
7 Conclusion
- The paper gives the first algorithm guaranteed to find a third-order local minimum, but shows the same ideas cannot be generalized to higher orders.The paper describes the algorithm as addressing some problems caused by degenerate saddle points.Source: §7 · p. 15
- Complicated saddle-point structures remain a major problem for optimization algorithms.The conclusion identifies degenerate saddle points as a continuing research direction.Source: §7 · p. 15
- Open questions include whether interesting function classes satisfy the strict third-order saddle property and whether a third-order algorithm can handle constrained optimization.The authors hope further work will produce efficient algorithms whose performance does not suffer from degenerate saddle points.Source: §7 · p. 15
A.1 Omitted Proofs in Section 4
The appendix states an equivalence between third-order local optimality and Condition 4, and outlines Taylor-based arguments for the criterion and its necessary conditions.
A.1 Omitted Proofs in Section 4
- The Taylor argument bounds the third-order expansion error using a Lipschitz condition on the third derivative.The proof passage says the bound follows by repeated integration from x to y.Source: §A.1 · p. 18
- Under Assumption 2, a point is third-order optimal if and only if it satisfies Condition 4.The supplied passages do not state the condition itself.Source: §A.1 · p. 18
- The Hessian range and nullspace organize the cubic derivative into components whose competition is bounded using the smallest nonzero eigenvalue and tensor norms.The argument separates the third derivative into projected tensors and bounds the terms involving range and nullspace directions.Source: §A.1 · p. 19
- A nonzero gradient, negative Hessian curvature, or nonzero cubic derivative along a Hessian-null direction rules out third-order local minimality.The proof considers these three cases as violations of a necessary condition.Source: §A.1 · pp. 19–20
A.2 Algorithm for Competitive Subspace, Proof of Theorem 7
The competitive-subspace procedure uses the Hessian and third derivative to seek a direction with a strong cubic signal. Its randomized approximation returns a direction with a cubic value bounded relative to the projected tensor norm.
A.2 Algorithm for Competitive Subspace, Proof of Theorem 7
- Algorithm 4 takes the function, point z, Hessian, third derivative, approximation ratio, and Lipschitz bound, and returns a competitive subspace and CQ(z).The supplied algorithm excerpt gives these as its required inputs and outputs.Source: §A.2 · p. 20
- At most 2 expected iterations suffice, and the output u satisfies T(u, u, u) ≥ ||Proj_S T||F/Q for Q = Bn^1.5.Theorem 13 states that B is a universal constant.Source: §A.2 · p. 20
- The proof uses Gaussian anti-concentration to obtain a direction whose cubic value is at least ε/(8n^1.5) times the projected tensor Frobenius norm with probability at least 1/2.It also uses a high-probability bound that the Gaussian vector's norm is at most 2√n.Source: §A.2 · pp. 20–21
A.3 Proof of Theorem 10
The proof reduces degree-4 polynomial nonnegativity to finding a fourth-order local minimum of a well-behaved function. It establishes the reduction using g(x)=f(x)+||x||^6 and characterizes its fourth-order local minima according to whether f is nonnegative or has a negative direction.
A.3 Proof of Theorem 10
- NP-hardness follows by reducing degree-4 polynomial nonnegativity to finding a fourth-order local minimum of the well-behaved function g(x)=f(x)+||x||^6.The theorem states that finding such a minimum remains NP-hard even when the function is guaranteed to be well-behaved.Source: §A.3 · p. 21
- The constructed g is well-behaved because it is a bounded-coefficient polynomial and its global minimizer lies within the unit ℓ2 ball.The proof also states that g(tx) is increasing for t≥1 when ||x||=1.Source: §A.3 · p. 21
- When f is nonnegative, 0 is the unique fourth-order local minimizer of g.Along any nonzero ray, the proof finds that only t=0 is a first-order local minimizer of g(tu).Source: §A.3 · p. 21
- If f has a negative direction, every local minimizer of g has negative value under f.For a nonzero fourth-order local minimizer, the proof's ray argument requires f(x)<0; if f(z)<0 for a unit direction, 0 is not a fourth-order local minimum.Source: §A.3 · p. 21