PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, Volkan Cevher

arXiv:2006.11144v1math.OCcs.LGmath.PRstat.ML

TL;DR

The paper asks how SGD behaves in non-convex problems, where trajectory convergence, saddle avoidance, and step-size-dependent rates are central questions. It analyzes SGD through stochastic-approximation and gradient-dynamics connections, establishing probability-one convergence and strict-saddle avoidance alongside a last-iterate rate for regular minimizers. These guarantees provide a theoretical basis for studying vanishing step sizes.

  • Problem

    The paper asks whether SGD converges in non-convex problems, avoids spurious critical regions, and how quickly it reaches local minima as a function of step size.

    Source: §1 · p. 1

  • Method

    The analysis uses a trajectory-based stochastic-approximation approach connecting SGD with continuous-time gradient dynamics.

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

  • Results

    With probability 1, SGD iterates converge and avoid strict saddle manifolds, and Θ(1/n^p) step sizes yield an O(1/n^p) last-iterate rate to Hurwicz-regular minimizers.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results identify vanishing step sizes as having theoretical benefits for convergence, saddle avoidance, and stabilization to local minimizers.

    Source: §1 · p. 2

    Earlier stochastic saddle-avoidance results require hyperbolicity, excluding non-isolated saddles and center manifolds common in deep-net training.

    Source: §4.3 · p. 7

Abstract

from arXiv · show

This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm's convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with probability $1$ under a very broad range of step-size schedules. Subsequently, going beyond existing positive probability guarantees, we show that SGD avoids strict saddle points/manifolds with probability $1$ for the entire spectrum of step-size policies considered. Finally, we prove that the algorithm's rate of convergence to Hurwicz minimizers is $\mathcal{O}(1/n^{p})$ if the method is employed with a $\Theta(1/n^p)$ step-size schedule. This provides an important guideline for tuning the algorithm's step-size as it suggests that a cool-down phase with a vanishing step-size could lead to faster convergence; we demonstrate this heuristic using ResNet architectures on CIFAR.

1. Introduction

The paper examines whether SGD converges, avoids spurious critical regions, and how its convergence rate depends on step size in non-convex problems. It answers with probability-one trajectory guarantees and a last-iterate rate for regular local minimizers.

1. Introduction

  • With probability 1, SGD iterates converge under mild objective conditions and step sizes Θ(1/n^p), p ∈ (0, 1]; this is trajectory convergence, not an average guarantee.The result applies to any instantiation of the algorithm.Source: §1 · p. 2
  • With probability 1, SGD avoids strict saddle manifolds, including connected sets of non-isolated saddle points found in overparameterized neural-network loss landscapes [27].This extends SGD guarantees previously stated with high probability or in expectation.Source: §1 · p. 2
  • For step sizes Θ(1/n^p), p ∈ (0, 1], SGD reaches Hurwicz-regular local minimizers at an O(1/n^p) last-iterate rate.The guarantee concerns the last generated point, not an ergodic or mean-squared-gradient-norm rate.Source: §1 · p. 2
  • The analysis combines the ODE method of stochastic approximation with dynamical-systems techniques and martingale limit theory.The ODE method is attributed to Benveniste et al., Kushner and Yin, Ljung, and Benaïm; martingale tools to Pemantle and Brandière and Duflo.Source: §1 · p. 2

2. Problem setup and assumptions

The setup studies a differentiable non-convex objective under regularity and boundedness assumptions, with gradients accessed through a stochastic first-order oracle. SGD updates iterates using oracle signals and a step-size sequence.

2.1. Problem setup.

  • The objective is differentiable, G-Lipschitz, and L-smooth, with bounded function sublevels and bounded near-critical gradient sublevels.These assumptions imply that the critical set is nonempty.Source: §2.1 · p. 3

2.2. Assumptions on the oracle.

  • The stochastic first-order oracle supplies stochastic gradient information; its error has finite q-th moment for q ≥ 2, with bounded noise allowed as q = ∞.Allowing q above 2 provides more flexibility in choosing step-size policies.Source: §2.2 · p. 4

2.3. Stochastic gradient descent.

  • SGD updates X_(n+1) = X_n − γ_n V_n, where V_n is an oracle gradient signal and γ_n is the step size.The gradient error is denoted Z_n, and the oracle randomness is not measurable with respect to the natural filtration of the iterates.Source: §2.3 · p. 4

3. Stochastic approximation

The analysis connects SGD to continuous-time gradient dynamics by viewing its iterates as an approximation to the dynamics’ flow. Under suitable step-size and moment conditions, that approximation supports probability-one convergence conclusions.

3. Stochastic approximation

  • SGD can be rewritten as a Robbins–Monro discretization of continuous-time gradient dynamics, with the gradient error acting as the stochastic component.The paper motivates this comparison because the objective is a strict Lyapunov function for gradient dynamics, whose orbits converge to the critical set.Source: §3 · p. 4
  • An asymptotic pseudotrajectory tracks the gradient-dynamics flow with arbitrary accuracy over windows of arbitrary length as time tends to infinity.The paper interpolates the iterates across elapsed step-size time to compare the discrete sequence with the continuous flow.Source: §3 · pp. 4–5
  • With probability 1, SGD iterates form an asymptotic pseudotrajectory under the stated step-size and moment conditions, including schedules Θ(1/n^p) for p ∈ (2/(q + 2), 1].This comparison delineates step-size policies for which the discrete system is well approximated by gradient dynamics.Source: §3 · p. 5

4. Convergence analysis

The analysis uses SGD-induced approximations of gradient descent to establish boundedness and almost-sure convergence, then examines strict-saddle avoidance and local convergence rates.

4.1. Boundedness and stability of the approximation.

  • Under Assumptions 1–4 and γn ∝ 1/n^p, p ∈ (2/(q + 2), 1], SGD-induced gradient-descent approximations remain bounded almost surely.This certifies trajectory boundedness rather than assuming it in advance.Source: §4.1 · pp. 5–6

4.2. Almost sure convergence.

  • Under Assumptions 1–4 and γn = Θ(1/n^p), p ∈ (2/(q + 2), 1], SGD converges almost surely to a connected component of the critical set where f is constant.Almost surely, f(Xn) also converges to a critical value, and every limit point of Xn is critical.Source: §4.2 · p. 6

4.3. Avoidance analysis.

  • For γn ∝ 1/n^p, p ∈ (0, 1], SGD has zero probability of converging to any strict saddle manifold, from any initial condition.A strict saddle manifold consists of critical points with at least one negative Hessian eigenvalue.Source: §4.3 · p. 9

4.4. Rate of convergence.

  • The local rate analysis tracks squared distance to a regular minimizer and considers γn = γ/(n + m)^p, with p ∈ (2/(q + 2), 1] and sufficiently large m and γ > 0.The analysis concerns last iterates, not an ergodic average or best iterate.Source: §4.4 · p. 9

5. Numerical experiments

The experiments compare step-size schedules on a Shekel benchmark and test a constant-step-size training phase followed by a vanishing-step-size cooldown on CIFAR10.

Shekel benchmark

  • In the reported comparison, the 1/n policy converges 2 to 4 orders of magnitude faster than the constant and 1/√n policies; the constant schedule initially performs better, then quickly saturates.Source: §5 · p. 10

ResNet18 on CIFAR10

  • On ResNet18 training over CIFAR10, the cooldown phase with step-size 1/n improves training loss, and the reported results favor using a vanishing step-size for the final training epochs.The experiment uses 100 initial epochs at a constant step-size, then launches cooldowns from checkpoints.Source: §5 · p. 10

6. Concluding remarks

The paper presents a trajectory-based analysis of SGD under minimal assumptions, establishing stationary limit points, almost-sure avoidance of strict saddle manifolds, and an O(1/n) rate to regular minimizers.

Concluding remarks

  • The analysis establishes stationary limit points, almost-sure avoidance of strict saddle manifolds, and an O(1/n) convergence rate to regular minimizers under minimal assumptions.The paper identifies constrained or composite problems and adaptive gradient methods as directions for future work.Source: §6 · p. 10

Appendix A. Convergence in continuous time

Under Assumptions 1 and 2, every gradient-flow solution converges to the critical set. The proof uses bounded sublevel sets and the decrease of the objective along flow lines.

Appendix A. Convergence in continuous time

  • Every solution of (GD) converges to the critical set X* under Assumptions 1 and 2.The proof first shows convergence to a compact invariant set, then rules out non-critical limit points.Source: Appendix A · p. 11
  • Bounded sublevel sets and the non-increasing objective place each flow trajectory in a compact invariant set.Global solution existence and uniqueness follow from Picard–Lindelöf and Assumption 1.Source: Appendix A · p. 11
  • A non-critical limit point would force a fixed decrease in f over repeated short time intervals, contradicting boundedness below on the trajectory.The argument uses continuity of the gradient near the proposed limit point and boundedness of the gradient.Source: Appendix A · p. 11

B.1. Discrepancies between flows and APTs.

The example separates the long-run behavior of gradient-flow solutions from that of an asymptotic pseudotrajectory. A curve can satisfy the APT condition while remaining at a height that no flow solution approaches.

B.1. Discrepancies between flows and APTs.

  • The example uses a pseudo-gradient flow of f(x1, x2) = x2^2/2 − x1.Its solution from initial condition (0, b) is used to construct the comparison with the constant-height curve.Source: §B.1 · p. 12
  • Over any fixed horizon T, the constant-height curve's maximum deviation from the corresponding flow tends to zero as the starting time grows.The bound is T/(1 + t0), which can be made at most ε by choosing t0 sufficiently large.Source: §B.1 · p. 12
  • All solutions of the depicted flow have x2(t) tending to 0, but the curve X(t) = (t, 1) is an APT with x2(t) tending to 1.The discrepancy is illustrated in Figure 3.Source: §B.1 · p. 12, Figure 3 · p. 12
  • The flow trajectories intersect x2 = 1 at a vanishing angle as time tends to infinity, explaining how the constant-height curve can be an APT.The passage notes that the needed estimate at t0 then holds for all later starting times by monotonicity.Source: §B.1 · p. 12

B.2. Boundedness of APTs.

For the stated step-size and noise-moment conditions, SGD-induced asymptotic pseudotrajectories are bounded almost surely. The proof establishes recurrent proximity to the critical set, then uses uniform objective decrease to bound the trajectories.

B.2. Boundedness of APTs.

  • For γn ∝ 1/n^p with p ∈ (2/(q + 2), 1], every SGD-induced APT is bounded almost surely under Assumptions 1–4.The theorem concerns the affine interpolation of the SGD iterates.Source: §B.2 · p. 13
  • The proof first shows that the SGD interpolation is an APT of (GD) with probability 1 under the stated step-size and moment condition.It then combines this property with almost-sure entry into a neighborhood of the critical set.Source: §B.2 · pp. 13, 16
  • Under the theorem's assumptions, the iterates have a subsequence whose distance to the critical set tends to zero almost surely.This supplies a trajectory point near the critical set from which the boundedness argument proceeds.Source: §B.2 · p. 13
  • Away from a neighborhood of the critical set, the gradient norm is bounded below by a positive constant.This uses the assumption that gradient sublevel sets are bounded.Source: §B.2 · p. 13
  • For a fixed time interval, the flow either decreases f by a uniform amount or enters a neighborhood of the critical set.The APT approximation transfers this decrease-or-entry property to the SGD interpolation, which remains in bounded sublevel sets.Source: §B.2 · pp. 15–17

Appendix C. Avoidance analysis

The avoidance analysis combines probabilistic criteria that prevent a process from converging to zero with a Lyapunov construction for unstable directions near strict saddle manifolds.

Appendix C. Avoidance analysis

  • Theorem 3's proof combines probabilistic estimates for processes avoiding zero with an average Lyapunov function that grows exponentially along unstable directions of a strict saddle manifold.The Lyapunov construction relies on center manifold theory.Source: Appendix C · p. 17, §C.1 · p. 17

C.1. Probabilistic estimates.

  • For p ∈ (0, 1/2], condition (C.1) alone ensures that the process En does not converge to zero with positive probability.The passage states P(lim En = 0) = 0.Source: §C.1 · p. 17
  • For p ∈ (1/2, 1], the same non-convergence conclusion requires bounded increments and a conditional drift condition above a threshold.Under those additional conditions, P(lim En = 0) = 0.Source: §C.1 · p. 17

C.2. Center manifold theory and geometric constructions.

The appendix constructs a center-stable manifold and an energy function that captures repulsion from strict saddle manifolds. It uses this local growth to establish almost-sure avoidance under the stated step-size and assumption conditions.

C.2. Center manifold theory and geometric constructions.

  • Near a strict saddle manifold, central directions are tangent to the center-stable manifold, stable directions converge along it, and unstable directions are transverse and may escape.Source: §C.2 · p. 18
  • The projector maps nearby points onto the center-stable manifold along unstable directions, enabling an energy function that vanishes exactly on the manifold locally.Source: §C.2 · pp. 19–20
  • The constructed energy grows locally at a geometric rate for stochastic iterates near the saddle manifold, so they cannot remain nearby for long periods.The additive noise is non-antagonistic in expectation.Source: §C.2 · p. 21

C.3. Avoidance of saddle-point manifolds.

  • Under Assumptions 1–5, SGD with γn ∝ 1/n^p for p ∈ (0, 1] converges to a strict saddle manifold with probability zero.Source: §C.3 · p. 21

Appendix D. Rates of convergence

The appendix develops a high-probability local analysis for SGD near regular minima. It controls accumulated error and uses that control to show iterates remain close to the minimum under a diminishing step-size schedule.

Appendix D. Rates of convergence

  • The analysis targets convergence rates to regular Hurwicz minima, where the Hessian at the minimizer is positive definite.Source: Appendix D · p. 23
  • The theorem considers γn = γ/(n + m)^p for p ∈ (2/(q + 2), 1], with sufficiently large m and γ.Source: Appendix D · p. 23
  • The proof controls aggregated error terms and conditions on staying near the minimizer before applying a recursive estimate.Source: Appendix D · p. 25
  • With sufficiently large m, SGD initialized near a regular minimizer remains close to it with probability at least 1 − δ.Source: Appendix D · pp. 23, 29

Appendix E. Numerical experiments

The appendix evaluates cooldown training for ResNet18 on CIFAR10, reporting a benefit in test accuracy and loss when decay is used in the final portion of training.

Appendix E. Numerical experiments

  • The experiments used torchvision ResNet18 and CIFAR10 with the standard 50,000/10,000 training/test split and batches of 120.Source: Appendix E · p. 30
  • Cooldown with a 1/n step-size policy in the final part of training showed a clear benefit, especially in test accuracy and loss.Source: Appendix E · p. 30
  • Training began with constant-step-size SGD selected by grid search, then applied cooldown from checkpoints using a 1/n schedule whose counter restarted at cooldown.Source: Appendix E · p. 30

Related papers

Loading 2006.11144v1…