Escaping Saddles with Stochastic Gradients

Hadi Daneshmand; Jonas Kohler; Aurelien Lucchi; Thomas Hofmann

Source-linked AI summary

Escaping Saddles with Stochastic Gradients

Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, Thomas Hofmann

arXiv:1803.05999v2Mar 15, 2018cs.LGmath.OCstat.ML

TL;DR

SGD’s stochastic gradients may align with negative-curvature directions rather than behaving like dimension-diluted isotropic noise. The paper introduces the CNC assumption and analyzes perturbed GD and vanilla SGD, obtaining dimension-independent second-order convergence results under that condition.

Problem
Isotropic-noise analyses can produce convergence rates dependent on parameter dimension, motivating evidence about stochastic-gradient variance along negative-curvature directions.
Method
The paper introduces the CNC assumption and analyzes GD perturbed by stochastic gradients and vanilla SGD for non-convex optimization.
Results
Under CNC, vanilla SGD reaches an (ϵ, ϵ)-second-order stationary point in ˜O(ϵ−10) iterations with high probability, while stochastic-gradient variance increases with negative-eigenvalue magnitude.
Takeaways & Limitations
Under CNC, explicit isotropic perturbations can be replaced by intrinsic SGD noise, with convergence rates independent of parameter dimension.
Takeaways & Limitations
The CNC-PGD rate is unknown to be optimal, remains worse than the best known perturbed-SGD rate in second-order optimality, and relies on an initialization assumption.

Abstract

from arXiv · show

We analyze the variance of stochastic gradients along negative curvature directions in certain non-convex machine learning models and show that stochastic gradients exhibit a strong component along these directions. Furthermore, we show that - contrary to the case of isotropic noise - this variance is proportional to the magnitude of the corresponding eigenvalues and not decreasing in the dimensionality. Based upon this observation we propose a new assumption under which we show that the injection of explicit, isotropic noise usually applied to make gradient descent escape saddle points can successfully be replaced by a simple SGD step. Additionally - and under the same condition - we derive the first convergence rate for plain SGD to a second-order stationary point in a number of iterations that is independent of the problem dimension.

1. Introduction

The paper studies whether SGD’s intrinsic sampling variance can replace explicit isotropic perturbations for escaping saddles in non-convex optimization. It introduces CNC, requiring variance along most-negative-curvature directions, and reports convergence and empirical results under this condition.

SGD is attractive for its simplicity and dataset-size-independent convergence, but its sampling noise must usually be controlled through conservative stepsizes or variance reduction.
Non-convex optimization is complicated by saddle points and suboptimal local minima, making second-order stationarity a practical target instead of global minimization.
Existing methods reach second-order stationary points by explicitly injecting isotropic noise, which introduces input-dimension dependence and leaves vanilla SGD’s intrinsic noise unresolved.
The CNC assumption requires the stochastic gradient’s projected second moment to remain uniformly bounded away from zero along the Hessian’s minimum-eigenvalue direction.
Under CNC, the paper analyzes GD perturbed by SGD steps and vanilla SGD, while also proving CNC for half-spaces and providing empirical evidence for neural-network training.
Stochastic-gradient variance along the most negative-curvature direction remains significant independently of network width and depth, unlike uniform noise whose variance decreases as O(1/d).

2. Background & Related work

Prior work established first- and second-order convergence results using explicit noise, curvature methods, or Hessian approximations. These approaches involve iteration, dimensionality, or computational trade-offs that motivate the paper’s noise-free SGD analysis.

For smooth non-convex functions, GD reaches a first-order stationary point in O(ϵ^-2) iterations, while SGD requires O(ϵ^-4).
Existing second-order first-order methods rely on explicitly added isotropic noise to escape saddle points, with prior analyses reporting dimension-dependent iteration complexity.
Prior work had not demonstrated convergence of SGD without explicitly added noise, leaving the role of vanilla SGD’s intrinsic noise unresolved.
Second-order methods exploit negative curvature but can lack global convergence guarantees or require costly Hessian computation and inversion.
Trust-region and cubic-regularization methods provide second-order guarantees, while Hessian-vector products and matrix-free methods reduce curvature-computation costs.

3. GD Perturbed by Stochastic Gradients

CNC-PGD replaces explicit isotropic perturbations with intrinsic stochastic-gradient noise under the CNC condition, using a GD/SGD combination to escape saddle points. The analysis establishes polynomial-time convergence through separate large-gradient, sharp-negative-curvature, and moderate-curvature regimes, while noting dimension independence and rate limitations.

CNC-PGD uses intrinsic SGD noise instead of isotropic perturbations, under the CNC assumption and standard smoothness conditions.The objective has Lipschitz gradients and Hessians, and stochastic gradients are assumed bounded.
Convergence result: Under CNC, CNC-PGD converges polynomially to a second-order stationary point without requiring isotropic noise.The result is dimension-independent, but the authors state that its second-order rate is worse than the isotropic-noise comparison by an ϵ^-0.1 factor and may not be optimal.
Proof regimes: The proof analyzes large gradients, sharp negative curvature, and small gradients with moderate negative curvature separately before combining their expected decreases.Large gradients invoke standard GD descent; sharp negative curvature yields expected decrease from CNC noise; moderate curvature bounds subsequent function-value increases.
Scope: The dimension-independent conclusion does not conflict with a dimensional lower bound because that lower bound makes no initialization assumption, unlike CNC.The distinction is explicitly attributed to the initialization condition in Assumption 1.
Joint analysis: The combined analysis shows that visited iterates reach second-order stationary points in a finite number of steps, with a high-probability return guarantee.The argument first establishes expected function-value decrease and then converts repeated visits into a high-probability statement.
Limitation: The analysis cannot guarantee that PGD remains near every second-order stationary point because degenerate saddles may satisfy the second-order condition without being local minima.A strict-saddle assumption could exclude such degenerate saddles.

4. SGD without Perturbation

CNC-SGD uses stochastic gradients without explicit perturbations and, under the CNC assumption, converges to a second-order stationary point with dimension-independent guarantees.

4. SGD without Perturbation: CNC-SGD uses periodic step-size increases to amplify stochastic-gradient variance along directions of negative curvature.The method requires no additional perturbation.
4. SGD without Perturbation: The CNC-SGD parameter table specifies constants c1, c2, and c3 independent of γ, δ, ϵ, ρ, and L.These constants are part of the parameter choices used by Algorithm 2.
4. SGD without Perturbation: Theorem 2 establishes convergence of CNC-SGD under the CNC and smoothness assumptions.The supplied theorem statement omits the numerical guarantee and iteration expression.
4. SGD without Perturbation: Vanilla SGD converges without perturbations under CNC, with a second-order guarantee requiring ˜O(ϵ−4) stochastic-gradient steps.This improves the dimensional dependence of isotropic-noise approaches, while its first-order rate is worse and its second-order rate remains behind the best perturbed-SGD result.

5. Learning Half-spaces with Correlated

For learning half-spaces, stochastic gradients have nontrivial projections onto negative-curvature directions, establishing the CNC condition under stated structural assumptions.

5. Learning Half-spaces with Correlated: The analysis targets learning half-spaces, where stochastic gradients are unbiased and the objective may be non-convex with saddle points.Samples are drawn from the data distribution P.
5. Learning Half-spaces with Correlated: A lower bound on projected stochastic-gradient second moments establishes significant variance along eigenvectors associated with negative Hessian eigenvalues.The bound requires a structural condition relating the magnitude of the loss's second derivative to its first derivative.
5. Learning Half-spaces with Correlated: The CNC condition holds for stochastic gradients on learning half-spaces, including eigenvectors corresponding to the minimum Hessian eigenvalue.This yields polynomial-time second-order convergence for both mixed SGD-GD steps and vanilla SGD.
5. Learning Half-spaces with Correlated: The resulting convergence guarantees are dimension free.The supplied discussion attributes this to replacing isotropic-noise requirements with CNC.
5. Learning Half-spaces with Correlated: The variance of stochastic gradients along negative-curvature eigenvectors scales proportionally to the magnitude of their negative eigenvalues.This contrasts with isotropic noise, whose variance is uniformly distributed across Hessian eigenvectors.

6. Experiments

Experiments examine saddle escape in learning half-spaces and projected stochastic-gradient variance across neural-network widths and depths, with stochastic methods escaping saddles quickly.

6. Experiments: Stochastic methods quickly find negative-curvature directions and escape a saddle in the learning-halfspaces experiment.The comparison averaged suboptimality over 10 runs; the result is presented as a proof of concept rather than an encompassing benchmark.
6. Experiments: The neural-network experiments estimate projected stochastic-gradient second moments over 30 random parameter settings on MNIST.Networks vary in width and depth, and the estimates are compared with normalized isotropic-noise vectors.
6. Experiments: Stochastic gradients maintain significant variance along most-negative-curvature directions independently of network width and depth.The comparison reports that isotropic-noise variance along λmin decreases as O(1/d).
6. Experiments: Projected stochastic-gradient variance increases with the magnitude of the associated eigenvalues in networks with 8, 16, and 32 hidden layers.Figure 3 displays a scatterplot with a fitted linear model and 95% confidence interval.

7. Conclusion

The paper concludes that CNC provides a weaker alternative to isotropic noise for analyzing SGD and PGD in non-convex optimization, with evidence from half-spaces and neural networks.

7. Conclusion: CNC requires stochastic noise to have sufficient variance along directions of most negative curvature.The paper presents this as less restrictive than isotropic-noise assumptions.
7. Conclusion: The paper reports that stochastic gradients satisfy CNC for learning half-spaces and that their variance is proportional to negative-eigenvalue magnitude.Neural-network experiments provide empirical evidence suggesting validity beyond half-spaces.
7. Conclusion: The paper identifies proving the neural-network observation theoretically and studying optimization and generalization implications as future work.The conclusion does not claim that these extensions have been established.
7. Conclusion: The analysis includes smoothness, Hessian-Lipschitzness, bounded-gradient, and stochastic-gradient-Lipschitz assumptions.These assumptions support the stochastic-step analysis and parameterized algorithms.
7. Conclusion: A stochastic-gradient step decreases the objective function in expectation under unbiased gradients and bounded stochastic gradients.This result follows from smoothness.

B.2. Sharp negative curvature regime

The sharp-curvature analysis shows that stochastic perturbations correlated with the minimum-eigenvalue direction grow through Hessian power iterations, forcing sufficient iterate movement and function decrease under the CNC condition.

Sharp-curvature setup: The proof assumes a small gradient and a sufficiently large negative Hessian eigenvalue, then argues by contradiction from insufficient function decrease.The analysis first bounds iterate distance and then uses a stale Taylor approximation around the initial parameter.
Distance contradiction: The proof combines an upper bound on iterate distance from limited function decrease with a lower bound from exponential power-iteration growth.Bounds on ut, δt, and the distance lower bound are combined to obtain the contradiction.
Sharp-curvature setup: The iterate decomposition separates Hessian power iterations, stale Taylor-approximation errors, and terms depending on the initial gradient.The power-iteration term is ut, while δt captures Taylor errors and dt depends on the initial gradient.
Exponential growth: Under the CNC assumption, the expected squared norm of the power-iteration term grows exponentially with the number of steps.The growth follows from the component of stochastic-gradient noise along the minimum-curvature eigenvector.
Distance contradiction: Choosing parameters using λ ≥ √ρϵ2/5 makes the lower bound positive and yields exponential distance growth until the sufficient function decrease occurs.The resulting contradiction establishes the claimed behavior of perturbed gradient steps in the sharp-curvature regime.

C.2. Proof of the Main Theorem

The main-theorem proof analyzes CNC-SGD across large-gradient, sharp-curvature, and moderate-curvature regimes, controlling function changes to obtain a high-probability second-order stationarity guarantee.

Conclusion: The combined bounds yield an (ϵ, √ρϵ)-second-order stationary point with probability at least 1−δ after the stated number of SGD steps.The conclusion follows by bounding the average probability of the unfavorable events over the iteration blocks.
Proof structure: CNC-SGD decomposes each stochastic update into a deterministic gradient step and a zero-mean stochastic noise term.The CNC condition is exploited specifically during large-step updates, unlike perturbed SGD with isotropic noise at every step.
Large-gradient regime: When the gradient norm is large, one SGD step guarantees the desired function decrease under the selected step-size condition.The regime is defined by the large-gradient inequality in Eq. (64).
Sharp-curvature regime: For sharp negative curvature, a large-step SGD update supplies variance that smaller-step updates exploit to decrease the function value in expectation.This is the negative-curvature exploration mechanism formalized by Lemma 16.
Moderate-curvature regime: In the moderate-curvature and small-gradient regime, the proof controls the function increase caused by stochastic-gradient variance.The resulting bounds are combined with the large-gradient and sharp-curvature cases through a probabilistic argument.

C.3. Proof of the main Lemma 16

The proof of Lemma 16 extends the sharp-curvature argument to SGD by bounding distance, approximation errors, and stochastic terms before deriving exponential escape from a saddle region.

Proof ingredients: The proof repeatedly invokes martingale and auxiliary bounds to control stochastic-gradient noise and Taylor-approximation errors.The stochastic process lemma provides the needed conditional zero-mean relation.
Lemma 16 conclusion: The small-negative-eigenvalue case gives an expected function decrease after tthres iterations with the smaller step size η.The proof assumes insufficient decrease, bounds the distance to the pivot, and then derives the contradiction.
Iterate decomposition: The SGD expansion includes stale Taylor errors, stochastic noise, and initial-gradient terms in the displacement from the pivot point.The combined perturbation is denoted Ωt = δt + ζt + dt.
Escape argument: The argument chooses parameters so the lower bound on iterate distance is positive and grows exponentially under negative curvature.This contradicts the upper distance bound if insufficient function decrease persists for sufficiently many iterations.
Distance control: A distance bound follows from a lower bound on expected function decrease and the zero-mean property of the stochastic noise.The proof relates telescoping iterate differences to visited stochastic gradients.

D. Analysis of Learning Half-spaces

For learning half-spaces, the analysis relates negative Hessian curvature to the stochastic-gradient projection along its corresponding eigenvector using the model’s Hessian structure.

Setting: The half-space result assumes the data support lies on the unit sphere and considers a unit eigenvector v with negative eigenvalue λ.The result is stated for the half-space learning problem under Assumption 3.
Hessian connection: The Hessian representation ∇2f(w)v = λv and ∇2f(w) = ϕ′′(w⊤z)zz⊤ connects curvature to the data-dependent direction z.This identity is the starting point for the stochastic-gradient projection analysis.
Bound: Applying the resulting relation together with Jensen’s inequality yields the desired half-space bound, with the final inequality using λ < 0.The proof explicitly attributes the last step to the negative eigenvalue condition.

E. Additional experimental results

Additional experiments examine learning halfspaces and neural networks, comparing optimization trajectories and covariance or correlation patterns across stochastic gradients and isotropic noise.

Learning halfspaces: In the halfspace experiment, samples come from two multivariate Gaussian distributions in R4 with labels assigned by distribution.The experiment uses n/2 = 20 samples from each distribution.
Experimental setup: The experiments compare Gradient Descent, Stochastic Gradient Descent, PGD, and PGD-CNC using specified perturbation and step-size settings.All methods use α = 1/4; stochastic steps use batch size 1, and perturbed methods trigger when ∇f(w) < 0.01.
Learning halfspaces: All methods move from a saddle toward the flat end of the sigmoid, but Gradient Descent is much slower to find significant negative curvature.The comparison uses gradient norms and minimum and maximum eigenvalues along optimization trajectories.
Neural networks: Neural-network experiments vary width and depth while examining covariances between stochastic gradients or isotropic noise and eigenvectors across the negative eigenspectrum.The figures include increasing width and depth, correlations with eigenvectors of different eigenvalue magnitudes, and fitted linear models across 8, 16, and 32 hidden layers.
Neural networks: Correlation between eigenvectors and stochastic gradients increases with the magnitude of the associated eigenvalues, unlike randomly drawn unit-sphere noise.The correlations also decrease as dimension increases.