PaperlayerView exact revision on arXiv

Source-linked AI summary

Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Rong Ge, Furong Huang, Chi Jin, Yang Yuan

arXiv:1503.02101v1cs.LGmath.OCstat.ML

TL;DR

Stochastic gradient descent lacks the usual convex guarantees when optimizing non-convex functions with many saddle points. The paper identifies the strict saddle property, proves efficient escape using stochastic gradients, and applies the framework to obtain an online orthogonal tensor decomposition algorithm with a global convergence guarantee.

  • Problem

    For non-convex functions with many saddle points, the paper asks which properties guarantee that stochastic gradient descent efficiently reaches a local minimum.

  • Method

    The paper identifies strict saddle functions and develops a stochastic-gradient analysis for escaping their saddle points in unconstrained and equality-constrained settings.

  • Results

    A strict-saddle objective for orthogonal tensor decomposition has local minima corresponding to valid decompositions, yielding the first online algorithm with a global convergence guarantee.

  • Takeaways & Limitations

    The strict saddle framework provides a route to analyzing stochastic gradient descent for non-convex problems with many local minima and saddle points.

  • Takeaways & Limitations

    The analysis covers equality constraints but leaves general inequality constraints for future work.

Abstract

from arXiv · show

We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allows for efficient optimization. Using this property we show that stochastic gradient descent converges to a local minimum in a polynomial number of iterations. To the best of our knowledge this is the first work that gives global convergence guarantees for stochastic gradient descent on non-convex functions with exponentially many local minima and saddle points. Our analysis can be applied to orthogonal tensor decomposition, which is widely used in learning a rich class of latent variable models. We propose a new optimization formulation for the tensor decomposition problem that has strict saddle property. As a result we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee.

1 Introduction

The paper studies why stochastic gradient methods can escape saddle points in non-convex optimization and identifies strict saddle functions as a tractable class. It applies this framework to orthogonal tensor decomposition, yielding an online algorithm with a global convergence guarantee.

  • 1 Introduction: Non-convex optimization can be difficult because functions may contain many local minima and saddle points, while no general polynomial-time guarantee for finding a local minimum is known.Saddle points have zero gradient without being local minima, making gradient-only methods particularly vulnerable.
  • 1 Introduction: Stochastic gradient methods remain attractive because Hessian-based methods increase memory requirements and per-iteration computation time.The paper therefore asks which properties of a non-convex function guarantee efficient convergence to a local minimum.
  • 1 Introduction: Orthogonal tensor decomposition has exponentially many local minima and saddle points because permutations of the true components yield equivalent solutions.The problem is central to learning latent variable models and has symmetric structure shared by other feature-learning problems.
  • 1 Introduction: Strict saddle functions have a negative Hessian eigenvalue at every saddle point, providing a structural basis for escaping saddles.Although deterministic gradient descent can remain fixed at a stationary point, stochastic-gradient randomness can escape unstable saddles.
  • 1 Introduction: For strict saddle functions, Noisy Gradient Descent outputs a point close to a local minimum in a polynomial number of steps.This is the paper’s main convergence result for stochastic-gradient optimization under the strict saddle property.
  • 1 Introduction: The paper designs a strict-saddle objective for orthogonal tensor decomposition whose local minima correspond to valid decompositions, enabling the first online algorithm with a global convergence guarantee.The objective is formulated as an expected loss over random samples.

2 Preliminaries

The preliminaries define stochastic-gradient optimization and its assumptions, then introduce fourth-order tensors and orthogonal decomposition as the paper’s application setting.

  • Stochastic Gradient Descent: Stochastic gradient descent optimizes a function through an unbiased, bounded-noise stochastic gradient oracle.The oracle satisfies E[SG(w)] = ∇f(w) and has deviation bounded by Q; updates use learning rate η.
  • Stochastic Gradient Descent: Traditional stochastic-gradient guarantees assume smoothness and strong convexity, whereas this paper studies smooth non-convex functions without strong convexity.In the strongly convex setting, prior work gives a 1/t convergence rate.
  • Stochastic Gradient Descent: The analysis also requires the Hessian to be ρ-Lipschitz, a third-order condition implied when bounded third derivatives exist.This controls how the Hessian changes between points.
  • Tensor Decomposition: A fourth-order tensor is a four-dimensional array, and tensor products and multilinear forms provide the notation for its contractions.For a fourth-order tensor, T(I,u,u,u) is a vector and T(I,I,u,u) is a matrix.
  • Tensor Decomposition: Orthogonal tensor decomposition represents a tensor using orthonormal component vectors, uniquely up to permutation and sign flips.Finding these components supports latent-variable models including HMMs, multi-view models, topic models, mixtures of Gaussians, and ICA.

3 Stochastic gradient descent for strict saddle function

This section defines strict-saddle structure and shows how noisy stochastic-gradient updates exploit it to reach and remain near local minima in polynomially many iterations.

  • Strict Saddle Property: Strict-saddle functions have positive-definite Hessians at local minima and a negative Hessian eigenvalue at every other stationary point.This excludes degenerate stationary points and identifies a direction of local decrease near saddles.
  • Strict Saddle Property: The robust strict-saddle condition partitions points into regions with large gradient, significant negative curvature, or proximity to a strongly convex local minimum.Near a local minimum, the function is α-strongly convex within a 2δ neighborhood.
  • Noisy Stochastic Gradient: Noisy stochastic gradient adds perturbations in every direction, allowing updates to explore neighborhoods around saddle points and escape along unstable directions.If the stochastic-gradient oracle already has non-negligible variance in every direction, additional noise is unnecessary.
  • Convergence Guarantee: The main theorem gives high-probability convergence near a local minimum in ˜O(η^-2 log(1/ζ)) iterations under boundedness, smoothness, Hessian-Lipschitzness, and oracle assumptions.The output is ˜O(√(η log(1/ηζ)))-close with probability at least 1 − ζ; hidden factors depend polynomially on other parameters.
  • Convergence Guarantee: The proof combines descent under large gradients, escape from saddles, and local retention near minima, then repeats the argument to obtain failure probability ζ.Expected function decrease and the bounded function range yield the polynomial iteration bound.
  • Constrained Problems: For constrained problems, the informal theorem applies projected noisy gradient descent under regularity and smoothness conditions.The constrained guarantee has the same ˜O(η^-2 log(1/ζ)) iteration dependence and local-minimum proximity form.

4 Online Tensor Decomposition

The paper formulates orthogonal tensor decomposition with a correlation-minimizing objective that satisfies the strict saddle property, then derives an online stochastic-gradient implementation. The formulation’s local minima recover the tensor components up to permutation and sign flips.

  • 4.1 Optimization problem for tensor decomposition: The authors introduce a tensor-decomposition formulation designed to satisfy the strict saddle property.
  • 4.1 Optimization problem for tensor decomposition: The objective minimizes correlations T(ui, ui, uj, uj) between distinct components.Its global minimum is 0 when component supports are disjoint in the orthogonal basis.
  • 4.1 Optimization problem for tensor decomposition: Unlike reconstruction-error optimization, the new formulation is presented as a single problem for finding all components.Prior approaches include iterative deflation and methods such as Alternating Least Squares or FastICA.
  • 4.1 Optimization problem for tensor decomposition: The optimization problem is (α, γ, ϵ, δ)-strict saddle with α = 1 and γ, ϵ, δ = 1/poly(d).All local minima have the form ui = κiaπ(i), with κi = ±1 and π a permutation.
  • Online stochastic-gradient implementation: In the ICA example, observed samples yield a tensor with an orthogonal decomposition, enabling stochastic gradients for the proposed objective.The setup uses an unknown orthonormal transformation and the fourth-order cumulant of the observed sample.
  • Online stochastic-gradient implementation: The stochastic gradient oracle estimates the objective from samples without constructing the fourth-order tensor.Its cost is O(d3) for one sample and O(d3 + d2k) for an average of k samples.

5 Experiments

Experiments test projected noisy gradient descent on orthogonal tensor decomposition using synthetic and ICA sampling schemes. The proposed objective is more stable than reconstruction error, and decreasing the learning rate drives ICA error to zero.

  • Experimental setup: The proposed algorithm converges efficiently from random initial points and outperforms the reconstruction-error formulation in the simulations.The experiments use dimension d = 10 and measure normalized reconstruction error.
  • Samples and stochastic gradients: The synthetic sanity check samples x as d4ai with probability 1/d, giving E[x⊗4] = T.
  • Samples and stochastic gradients: The ICA experiment uses mini-batches of size 100 because the stochastic gradient has large variance.
  • Comparison of objective functions: The new objective always converges within 10000 iterations, whereas reconstruction error sometimes fails to converge within that limit.The reconstruction-error method also exhibits long periods of small improvement, likely associated with saddle points lacking a significant negative eigenvalue.
  • Simple ICA example: In the ICA setting, constant learning rate leaves the error at a fixed small value, while decreasing the learning rate makes the error converge to 0.

6 Conclusion

The paper identifies strict saddle functions as a basis for analyzing stochastic-gradient escape from saddle points and applies the framework to online orthogonal tensor decomposition. It positions this as an initial step toward broader classes of non-convex functions with related symmetries.

  • Conclusion: Strict saddle analysis shows stochastic gradient descent can converge to a local minimum under the strict saddle assumption.
  • Conclusion: The framework yields a new online algorithm for orthogonal tensor decomposition with a global convergence guarantee.
  • Conclusion: The authors propose extending strict saddle analysis to more functions, especially those with similar symmetry properties.

A Detailed Analysis for Section 3 in Unconstrained Case

The unconstrained analysis decomposes noisy SGD’s behavior into large-gradient, strict-saddle, and local-minimum regimes, then combines them to establish high-probability convergence under strict-saddle assumptions.

  • Algorithm: The algorithm’s update combines stochastic-gradient noise with explicitly added random noise.This combined noise is used throughout the analysis of escaping saddle points.
  • Main conclusion: Combining the three regimes, noisy SGD reaches a point near a local minimum in ˜O(η^-2 log(1/ζ)) iterations with probability at least 1 − ζ.The high-probability guarantee repeats the saddle-escape argument and applies a union bound.
  • Assumptions: The analysis assumes a strict-saddle function and stochastic-gradient noise with zero mean, isotropic covariance, and bounded magnitude.The proof also uses boundedness, smoothness, and Lipschitz-Hessian conditions.
  • Large-gradient regime: When the gradient is large, the analysis treats the iterate as belonging to a separate descent regime.The corresponding lemma applies whenever the gradient norm exceeds the stated threshold.
  • Strict-saddle regime: When the gradient is small but the Hessian has sufficiently negative curvature, the iterate enters the target region within T_max = O((log d)/γη) steps.The bound is independent of the starting point w0.

B Detailed Analysis for Section 3 in Constrained Case

The constrained analysis extends noisy gradient descent to equality constraints by projecting updates onto the feasible set, yielding projected stochastic gradient descent under suitable geometric and noise conditions.

  • Constrained formulation: The equality-constrained problem uses a feasible set W defined by satisfying every constraint c_i(w) = 0.The algorithm projects each noisy update back onto W.
  • Algorithm: Projected Noisy Gradient Descent can be converted locally into projected stochastic gradient descent with an explicit projected update equation.The conversion combines artificial noise with stochastic-gradient noise.
  • Noise assumptions: The constrained analysis assumes independent noise with zero mean, isotropic covariance σ^2I, and an almost-sure norm bound Q.These conditions parallel the noise assumptions used in the unconstrained analysis.
  • Proof strategy: The proof handles the projection step through geometric tools for the constraint manifold before modifying the unconstrained analysis.The section introduces tangent and normal-space machinery and regularity conditions for the manifold.

B.1 Preliminaries

The constrained preliminaries replace ordinary gradients and Hessians with tangent-space quantities, while LICQ-based regularity controls multipliers, manifold curvature, and projection errors.

  • Constraint regularity: LICQ requires the constraint gradients {∇c_i(x)} to be linearly independent at a point.The paper strengthens this condition to α_c-RLICQ by requiring σ_min(C(w)) ≥ α_c.
  • Constrained derivatives: The constrained first- and second-order quantities χ(w) and M(w) play roles analogous to ∇f(w) and ∇^2f(w) in unconstrained optimization.χ(w) is the gradient component in the tangent space, and M(w) is tied to the Lagrangian Hessian.
  • Tangent and normal spaces: The tangent space contains vectors orthogonal to all constraint gradients, while the normal space is their span.The tangent and normal spaces have dimensions d − m and m, respectively, under α_c-RLICQ.
  • Derivative decomposition: The additional term N(w) need not be symmetric because χ(w) need not be the gradient of a scalar function.Nevertheless, N(w)v lies in the normal space for every vector v.
  • Optimality conditions: The constrained optimality conditions use KKT multipliers, with positive Lagrangian curvature on the tangent space sufficient for a strict local solution.The constrained quantities χ(w) and M(w) provide the corresponding local first- and second-order tests.
  • Manifold geometry: α_c-RLICQ together with constraint smoothness bounds the curvature of the constraint manifold and its radius of curvature.The radius parameter R serves as an upper bound on curvature and a lower bound on curvature radius.
  • Projection geometry: For sufficiently small steps, projecting an arbitrary update back to the feasible set is close to taking its tangent-space projection.The discrepancy is controlled by a second-order correction.

B.3 Main Theorem

The constrained main theorem transfers the strict-saddle escape analysis to projected SGD by approximating manifold dynamics with tangent-space dynamics and controlling projection corrections.

  • Strict-saddle structure: The constrained strict-saddle definition classifies points using tangent gradient size, tangent-space negative curvature, or local positive curvature near a minimum.These replace the corresponding unconstrained gradient and Hessian conditions.
  • Tangent-space approximation: Projected SGD is locally approximated by dynamics in the tangent space, with projection contributing a correction bounded by ˜O(η^2).This approximation follows from bounded manifold curvature and the projection lemmas.
  • Regularity conditions: α_c-RLICQ and smooth constraints provide the boundedness and smoothness properties needed for the Lagrangian-derived quantities.The analysis controls M(w), N(w), the Lagrangian Hessian, and the constraint Jacobian pseudoinverse.
  • Local-minimum regime: Near a constrained local minimum, the tangent-space Lagrangian curvature is locally strongly convex, enabling the local-stability argument.The proof then follows the unconstrained local-minimum analysis with the constrained quantities substituted.
  • Saddle-escape regime: At a constrained saddle with negative tangent curvature, the escape time is bounded by T_max = O((log(d − m))/γη).The bound depends on the tangent-space dimension d − m rather than the ambient dimension d.
  • Coupling argument: The tangent-space coupled sequence uses a local second-order approximation with noise projected onto the initial tangent space.The actual projected sequence is then shown to remain close to this coupled sequence.

C Detailed Proofs for Section 4

The section establishes that optimization problems (11) and (13) satisfy the (α, γ, ǫ, δ)-strict saddle property.

  • Optimization problems (11) and (13) satisfy the (α, γ, ǫ, δ)-strict saddle property.

C.1 Warm up: maximum eigenvalue formulation

For the maximum eigenvalue formulation, the proof characterizes local minima and shows that all other relevant points possess a direction of negative curvature, establishing strict-saddle structure.

  • The formulation satisfies the required smoothness conditions because its objective, constraints, and derivatives are bounded on the constrained domain.
  • Theorem 39 identifies ±ai (i ∈[d]) as the only local minima of optimization problem (11).
  • At points near saddle regions with at least two relatively large coordinates, a tangent direction has curvature at most −7/d.
  • When exactly one coordinate is relatively large, the point lies within δ of a local minimum whose nearby tangent-space curvature is at least 3.
  • The strict-saddle result follows by combining the saddle and local-minimum lemmas, while symmetry shows the minima are exactly ±ei in transformed coordinates.

C.2 New formulation

The new formulation has polynomially bounded derivatives, strict-saddle geometry, and exactly the permutation-and-sign variants of the component vectors as local minima.

  • The objective and its first three derivatives are bounded by poly(d), while each constraint’s first three derivatives are bounded by 2.
  • Theorem 43 states that optimization problem (13) has exactly 2d · d! local minima corresponding to permutations and sign flips of ai’s.
  • If two component vectors have overlapping relatively large coordinates, a tangent direction has curvature at most −γ.
  • If every pair of component vectors has disjoint relatively large-coordinate sets, the point lies within δ of a local minimum with nearby curvature at least 1.
  • The strict-saddle property follows from the two geometric lemmas, and the local-minimum count follows by the same symmetry argument as in Theorem 39.
Loading 1503.02101v1…