PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Descent Can Take Exponential Time to Escape Saddle Points

Simon S. Du, Chi Jin, Jason D. Lee, Michael I. Jordan, Barnabas Poczos, Aarti Singh

arXiv:1705.10412v2math.OCcs.LGstat.ML

TL;DR

The paper investigates whether randomly initialized GD can reach local minima in polynomial time on general non-convex smooth functions. It constructs functions with natural initialization where GD takes exponential time to escape successive saddle points, whereas perturbed GD reaches local minima in polynomial time. The authors conclude that perturbations are necessary for efficient non-convex optimization within this setting.

  • Problem

    For general non-convex problems, it was unclear whether randomly initialized GD could escape saddle points and reach local minima with explicit polynomial-time guarantees.

  • Method

    The paper constructs smooth, non-pathological functions under natural random initialization schemes and compares GD with perturbed GD.

  • Results

    GD can take exponentially long to escape d saddle points, while perturbed GD escapes them in polynomial time under uniform initialization over a unit cube.

  • Takeaways & Limitations

    The results support adding perturbations to GD for efficient non-convex optimization.

  • Takeaways & Limitations

    The paper leaves open whether GD remains inherently slow when the local optimum lies inside the initialization region used in its main constructions.

Abstract

from arXiv · show

Although gradient descent (GD) almost always escapes saddle points asymptotically [Lee et al., 2016], this paper shows that even with fairly natural random initialization schemes and non-pathological functions, GD can be significantly slowed down by saddle points, taking exponential time to escape. On the other hand, gradient descent with perturbations [Ge et al., 2015, Jin et al., 2017] is not slowed down by saddle points - it can find an approximate local minimizer in polynomial time. This result implies that GD is inherently slower than perturbed GD, and justifies the importance of adding perturbations for efficient non-convex optimization. While our focus is theoretical, we also present experiments that illustrate our theoretical findings.

1 Introduction

The paper asks whether randomly initialized gradient descent can escape saddle points in polynomial time for general non-convex problems. It presents a smooth-function construction where GD takes exponential time, while perturbed GD escapes in polynomial time.

  • Motivation: For general non-convex problems, GD is known to find a stationary point in polynomial time, but stationary points may be minima, saddles, or maxima.The convergence-rate behavior beyond stationary-point finding is less understood.
  • Prior work: Perturbations incorporated at every step or episodically allow GD variants to escape strict saddle points in polynomial time.The episodic-perturbation result also gives a bound on the number of escape iterations.
  • Contribution: The paper shows that natural random initialization and smooth, non-pathological functions do not prevent GD from taking exponentially long to escape saddle points.The result contrasts with perturbed GD, which reaches local minima in polynomial time.
  • Contribution: A smooth function in R^d makes GD visit d saddle-point neighborhoods, with later escapes taking increasingly longer and producing e^Omega(d) total steps.Perturbed GD takes a constant amount of time per saddle point in the construction.
  • Prior work: Existing results show that randomly initialized GD converges to minimizers almost surely, but provide asymptotic rather than explicit convergence-rate guarantees.This leaves open whether polynomial-time convergence to minimizers is possible.

2 Preliminaries

The paper formalizes strict saddles, second-order stationary points, and smoothness assumptions, then compares ordinary and perturbed gradient descent. Ordinary GD converges almost surely to second-order stationary points under convergence assumptions, while perturbed GD reaches approximate second-order stationary points in polynomial time.

  • Assumptions: The analysis assumes bounded function values, ℓ-gradient Lipschitzness, and ρ-Hessian Lipschitzness, which constrain function, gradient, and Hessian variation.These are presented as standard or commonly used assumptions for optimization and saddle-point analysis.
  • Definitions: A strict saddle has a zero gradient and a Hessian direction with a strictly negative eigenvalue, enabling escape; many machine-learning saddle points are strict.When all saddle points are strict, second-order stationary points are exactly local minima.
  • Definitions: An ϵ-second-order stationary point has gradient norm at most ϵ and a Hessian whose smallest eigenvalue is nonnegative up to the stated approximation.Exact second-order stationarity requires vanishing gradient and a positive-semidefinite Hessian.
  • Gradient-descent guarantees: With η < 1/ℓ, convergent GD from an absolutely continuous random initialization reaches a second-order stationary point almost surely.The result specifies limiting behavior but not a convergence rate.
  • Perturbed gradient descent: With suitable hyperparameters, perturbed GD finds an ϵ-second-order stationary point with probability at least 1 − δ in polynomially many iterations.The algorithm injects a uniform random perturbation when the gradient is small and sufficient time has passed since the previous perturbation.

3 Warmup: Examples with “Un-natural" Initialization

Two warmup constructions show that GD can require exponentially many steps to escape a strict saddle under unusual initialization schemes. One uses an exponentially thin band near the saddle, while the other uses initialization far away that funnels into that band.

  • Warmup examples: GD with random initialization can require exponentially many steps to escape strict saddles in simple counterexamples, although the constructions are described as unnatural or pathological.The examples motivate studying whether exponential slowdown persists under more natural settings.
  • Thin-band initialization: For the locally quadratic saddle f(x1, x2) = x1^2 − x2^2 in U = [−1, 1]^2 with η = 1/4, an exponentially thin initialization band causes slow escape.The band has width 2 · (3/2)^−exp(1/ϵ), making the initialization scheme unlikely in practice.
  • Far-away initialization: A second construction adds a long slope so a relatively large initialization region converges into the exponentially thin band near the saddle.The function is defined on [−∞, 1] × [−1, 1] and smoothly connects the distant region to the local quadratic region.
  • Far-away initialization: Uniform initialization in [−R−1, −R+1] × [−1, 1] is used to analyze the far-away construction, with Figure 1b illustrating the setup.The construction is designed so distant initialization funnels toward the slow-escape region.
  • Thin-band initialization: The thin-band construction requires initialization at an exponentially large distance R when R ≈ exp(1/ϵ), so GD takes exponential time to leave the saddle neighborhood.The neighborhood is U = [−1, 1] × [−1, 1] around (0, 0).

4 Main Result

The paper constructs smooth, non-pathological functions under natural random initialization where GD requires exponential time to escape saddle points, while perturbed GD reaches local minima in polynomial time.

  • Under uniform initialization in [−1, 1]^d, a smooth function with B, ℓ, and ρ at most poly(d) makes GD remain Ω(1) from every local minimum for T ≤ e^Ω(d).
  • With probability 1 − e^−d, perturbed GD finds an ε-close point to a local minimum in poly(d, 1/ε) time.
  • The construction has 2^d symmetric local minima, and both algorithms traverse d saddle-point neighborhoods before reaching one.
  • The example also rules out efficient GD approximation of ε-second-order stationary points for ε = 1/poly(d), whereas PGD achieves such points in polynomial time.
  • The result extends beyond uniform initialization: any distribution concentrated in an ℓ∞ ball inherits the conclusion with high probability, including Gaussian initialization.
  • GD’s escape time grows multiplicatively across saddle points, with t_i+1 ≥ (L+γ)/γ · t_i, yielding t_d ≥ ((L+γ)/γ)^d.

5 Experiments

Experiments with the constructed objective confirm that PGD converges faster than GD, while GD’s saddle-escape time grows multiplicatively and PGD’s remains approximately constant.

  • PGD converges faster than GD in all experiments, matching the theoretical predictions.The experiments vary L at fixed dimensions d = 5 and d = 10.
  • GD’s iterations to escape a saddle point grow at a fixed multiplicative rate involving L and γ.The figures verify that increasing γ increases the growth rate of GD’s escape iterations.
  • PGD requires an approximately constant number of iterations to escape, approximately ∼ 1/(ηγ).

6 Conclusion

The paper constructs smooth non-convex functions where GD can take exponential time to reach a local minimum, while perturbed GD converges in polynomial time. It also identifies stochastic extensions, initialization questions, and special structures as important scope boundaries.

  • GD can require exponential time to converge to a local minimum under a natural initialization scheme, whereas perturbed GD converges in polynomial time.
  • With random initialization, the authors expect analogous worst-case exponential saddle-escape behavior for general stochastic gradient descent.They expect polynomial time when perturbations are added per iteration or noise covariance is lower bounded in every direction.
  • Whether GD remains inherently slow when the local optimum lies inside the initialization region is left as an open problem.The authors also suggest using the counterexample toward oracle-model computational lower bounds.
  • The results do not rule out efficient GD on non-convex functions with special structures.The matrix square-root problem is given as an example where reasonable random initialization keeps gradient updates away from saddle points.

A Proofs for Results in Section 4

This section provides the proofs for Theorem 4.1 and Corollary 4.3, while omitting Corollary 4.2 because it follows from the same construction.

  • The section proves Theorem 4.1 and Corollary 4.3 claim by claim.
  • The proof of Corollary 4.2 is omitted because it follows easily from the construction used for Theorem 4.1.

A.1 Proof for Claim 1 of Theorem 4.1

The proof constructs a smooth function and domain that guide GD through a sequence of saddle neighborhoods, then extends and mirrors the construction to cover natural initializations in R^d.

  • Step 1: The tube: Spline polynomials connect quadratic regimes, making the function C2 and extending it across transition regions without introducing stationary points there.The spline degrees are bounded by five, and the gradients in the connection regions are bounded away from zero.
  • Step 1: The tube: The construction begins with a tube-shaped domain and a function whose GD dynamics remain near saddle points for exponential time from [0,1]^d initialization.The initial construction fixes L = e, γ = 1, τ = e and defines a closed subset D0.
  • Step 1: The tube: GD requires exponential time to reach xd ≥ 2τ, with the proof tracking escape times from successive saddle neighborhoods.The analysis defines Tk and Tτk for the first escape time and time spent inside each neighborhood.
  • Step 1: The tube: The escape-time analysis uses coordinate-wise GD dynamics: progress through a saddle region takes at least 1/(2ηγ) iterations, while earlier coordinates contribute additional delay.The proof also shows that iterates remain inside D0 throughout the relevant trajectory.
  • Step 3: From the octopus to R^d: Whitney’s extension theorem extends the function from the closed octopus domain to R^d while preserving agreement on the domain and polynomial derivative bounds.The extension may add stationary points, but GD never leaves the original domain.

A.2 Proof for Claim 2 of Theorem 4.1

The proof shows that perturbed gradient descent remains inside the designated region D after noise is added and throughout the subsequent noiseless iterations, completing the argument for Claim 2.

  • Keeping iterates in D: Perturbations are selected so that no noise is added when a coordinate lies between τ and 2τ.The proof uses polynomially small ϵ to ensure gthres ≤ γτ^10 and r ≤ τ^20.
  • Keeping iterates in D: After noise is added, the iterate lies in a region with an initial block of coordinates at least 2τ and remaining coordinates at most τ.The argument assumes, without loss of generality, that the post-noise iterate is nonnegative and satisfies the stated coordinate bounds.
  • Keeping iterates in D: The coordinate-wise gradient-descent dynamics preserve the relevant region between consecutive noise injections.The proof separately handles coordinates near the τ-to-2τ boundary and invokes Lemma B.2 for the needed bounds.
  • Conclusion: The resulting iterate satisfies k ≤ 1/(2ηγ), implying x(t) remains in D0 and completing the proof.This is the final bound obtained after combining the coordinate-wise estimates.

A.3 Proof for Corollary 4.3

The corollary transfers the analysis between a scaled function and the original function, showing that gradient descent with a rescaled stepsize has the corresponding behavior with high probability.

  • Rescaling argument: Gradient descent with stepsize η on g is equivalent to gradient descent on f with stepsize ηR^2.The equivalence follows from the auxiliary sequence y_t = h(x_t).
  • Rescaling argument: With probability 1 − δ, the initial point x(0) lies in B∞(z, R), enabling application of Theorem 4.1.The first corollary conclusion follows by combining this initialization event with the theorem.
  • Rescaling argument: The second conclusion follows by applying Theorem 2.7 in the same way as in the proof of Theorem 4.1.The passage identifies the theorem used to obtain the corresponding approximate-local-minimum guarantee.

B Auxiliary Theorems

The auxiliary results provide spline constructions and a continuous extension theorem used to build smooth connection functions satisfying prescribed boundary conditions and regularity bounds.

  • Spline constructions: Cubic Hermite interpolation constructs a polynomial matching endpoint values and derivatives under specified sign conditions.The interpolant matches f(y0), f(y1), f′(y0), and f′(y1).
  • Spline constructions: The connection function g(xi, xi+1) is built from polynomial functions g1 and g2 to satisfy boundary conditions for the constructed pieces.The construction introduces ν = −g1(2τ) + 4Lτ^2 and verifies the required conditions at xi = τ and xi = 2τ.
  • Spline constructions: At the boundaries xi = τ and xi = 2τ, the connection function's first and second derivatives are zero, so it does not affect neighboring boundary conditions.This property allows the bivariate and univariate constructions to satisfy the lemma's requirements.
  • Continuous extension: The continuous extension theorem extends a function defined on a closed subset E of R^d to a Cm function on R^d.The extension preserves the function on E and has operator norm at most Cd^(5m/2), with C depending only on m.
Loading 1705.10412v2…