Source-linked AI summary
Convergence rates for the stochastic gradient descent method for non-convex objective functions
Benjamin Fehrman, Benjamin Gess, Arnulf Jentzen
TL;DR
Rates for SGD have been established mainly under global contraction or convexity, assumptions often unmet by machine-learning objectives. This paper proves local convergence and rate estimates without those global conditions, with complexity settings that depend on accuracy and confidence.
Problem
Prior convergence-rate estimates for SGD relied on global contraction or convexity, assumptions often not satisfied by machine-learning objectives with rich sets of minima.
Source: §1 · p. 2Method
The paper proves local convergence of SGD to minima and estimates its convergence rate without requiring global convexity or contraction.
Source: §1 · p. 2Results
The stated settings are n(ε) = c1ε^-2/ρ, M(ε) = c2ε^-4/ρ+4, M(ε, η) = c3ε^-2η^-1 |log(η)|, and K(η) = c4 |log(η)|.
Source: §1 · p. 5Takeaways & Limitations
The approach addresses objectives whose minima may form non-isolated, possibly non-compact manifolds, unlike settings where contraction implies a unique minimum.
Source: §1 · p. 2The stated result assumes ρ ∈ (2/3, 1); the range extends to (0, 1) when M ∩ U is compact.
Source: §1 · p. 4, §5 · p. 30
Abstract
from arXiv · showhide
We prove the local convergence to minima and estimates on the rate of convergence for the stochastic gradient descent method in the case of not necessarily globally convex nor contracting objective functions. In particular, the results are applicable to simple objective functions arising in machine learning.
1 Introduction
This paper analyzes local convergence of SGD near sets of minima and convergence-rate estimates without requiring global convexity or contraction, accounting for the geometry of non-isolated minima. It also considers sharper estimates and improved computational efficiency for compact minimum sets, and applicability to simple machine-learning losses, including neural-network objectives.
1 Introduction
- The paper proves local convergence of SGD to the set of global minima, with rate estimates that avoid global convexity or contraction assumptions.The motivation is that neural-network objectives may have non-isolated minima and saddle points, unlike settings where contraction ensures a unique minimum.Source: §1 · p. 2
- The analysis assumes f is locally C3 in a neighborhood of M ∩ U and that its Hessian is maximally nondegenerate on M ∩ U.The restriction ρ ∈ (2/3, 1) extends to ρ ∈ (0, 1) when M ∩ U is a compact subset of R^d.Source: §1 · pp. 3–4
1.2 Structure of the work
- The analysis handles escape from attraction basins and non-isolated minima by estimating excursions separately in normal and tangential directions.The paper notes that mini-batches help control iterates lost in non-attracted regions.Source: §1 · pp. 6–7, §1.2 · pp. 8–9
1.1 Literature
- The literature distinguishes convergence of the gradient to zero from convergence of loss values to the global minimum; the former does not rule out saddle-point convergence.Prior non-convex gradient results include Lei, Hu, Li, & Tang, while linear SGD rates under the PL inequality are discussed by Karimi, Nutini, & Schmidt; the paper notes PL excludes local minima that are not global.Source: §1.1 · pp. 7–8
1.2 Structure of the work
- The deterministic continuous- and discrete-time gradient descent analyses establish exponential convergence near the minima manifold, while SGD converges algebraically in expectation when it stays in its attraction basin.These deterministic sections illustrate the geometric assumptions and arguments; the paper notes their computational impracticality when f and ∇f cannot be efficiently computed.Source: §1 · p. 7, §1.2 · p. 8
- When M ∩ U is compact, the paper previews improved convergence estimates and computational efficiency because SGD cannot escape tangentially within a basin of attraction, allowing a smaller mini-batch gradient approximation.The estimates also apply when the objective has a unique minimum.Source: §1.2 · p. 9
- The paper shows that Theorem 1.1’s assumptions hold for simple machine-learning objectives built from measurable loss functions and jointly measurable artificial neural networks.Source: §1.2 · p. 9
- For the Section 7.1 and 7.2 objectives, the data variables are i.i.d. with distribution μ, and global minima form non-unique, locally smooth, non-compact manifolds with maximally nondegenerate Hessians.Source: §1.2 · p. 9
2 Geometric preliminaries
The section develops local geometric tools around the manifold of minima, including a smooth local projection, a tangent-normal decomposition, and estimates that support later convergence analysis.
2 Geometric preliminaries
- The projection onto M∩U is well-defined and smooth in local neighborhoods, enabling analysis near the manifold.The projection is not asserted to be globally defined.Source: §2 · p. 9
- At points on M∩U, the Hessian’s null space characterizes tangent directions, while it is positive definite on normal directions.Source: §2 · p. 10
- The squared-distance gradient equals twice the displacement from a point to its local projection onto M∩U.Source: §2 · pp. 11–12
- The local neighborhoods use R and δ to measure tangential and normal distance from the manifold, respectively.Source: §2 · p. 12
- Near the manifold, the gradient splits into approximately normal and tangential components; the normal part supports a convergence rate, while the tangential part requires error control.Source: §2 · pp. 14–15
- These local geometric estimates are used to quantify discrete gradient descent’s convergence to M∩U.Source: §2 · pp. 15–16
3 Continuous deterministic gradient descent
The section analyzes continuous-time deterministic gradient descent near a manifold of minima. It establishes local convergence and shows that trajectories starting in a sufficiently small neighborhood remain in a local region.
3 Continuous deterministic gradient descent
- Continuous-time gradient descent converges to the local manifold of minima when initialized in a sufficiently small neighborhood.Source: §3 · p. 17
- The distance to the manifold satisfies a local upper bound of -λ times the distance plus a quadratic error term.The displayed differential inequality is d/dt d(θt, M∩U) ≤ -λd(θt, M∩U) + c1d(θt, M∩U)^2.Source: §3 · p. 18
- For suitable local initial data, trajectories stay within the chosen neighborhood for all time.Source: §3 · pp. 17–18
4 Discrete deterministic gradient descent
The section proves local basin invariance for discrete deterministic gradient descent under smoothness and Hessian-rank assumptions. Its proof controls convergence in directions normal to the manifold of minima while keeping the iterates within the basin.
4 Discrete deterministic gradient descent
- The discrete learning rate must be sufficiently small because an oversized step can overshoot the local minimum manifold and leave its attraction basin.The proof highlights this step-size issue as a distinction from the continuous-time argument.Source: §4 · p. 19
- The proof establishes convergence along normal directions while controlling tangential motion so the trajectory does not leave a suitably reduced basin.Normal convergence is shown provided the solution remains in the basin; the tangential component is then bounded after choosing a potentially smaller basin.Source: §4 · p. 19
- For a non-empty d-dimensional C1-submanifold M∩U with rank((Hess f)(θ)) = d − d at every θ, initialization θ0 ∈ VR/2,δ(x0) keeps θn in VR,δ(x0) for every n.Source: §4 · pp. 19, 21
- The local result extends to learning rate ρ = 1, with a logarithmic term appearing in estimate (4.18).The remainder of the proof is stated to follow by the same techniques, with an additional finiteness observation.Source: §4 · p. 21
5 Stochastic gradient descent
This section studies local convergence and probability estimates for mini-batch SGD near and reaching manifolds of minima, including behavior within a basin, independent runs, and objective minimization. It also presents a local result and parameter scalings for computational efficiency.
Proposition 5.3
- On the event that SGD does not escape its basin of attraction, it converges in expectation to the manifold of minima in normal directions.The result holds locally for initial points in a neighborhood of a point on the manifold.Source: §5 · p. 23
Proposition 5.4
- Proposition 5.4 estimates SGD’s maximal excursion on the event that its dynamics remain in the basin of attraction.The section identifies sufficiently large mini-batch size as necessary for establishing that SGD remains in the basin for large times.Source: §5 · p. 27
Remark 5.5
- The restriction ρ ∈ (2/3, 1) is needed only for boundedness of a sum that cannot be controlled by mini-batch size; with compact M ∩ U, Section 6 applies for ρ ∈ (0, 1).The remaining arguments apply without change for ρ ∈ (0, 1).Source: §5 · p. 30
Lemmas 5.6 and Proposition 5.7
- A basin point lies in V_R,δ(x0) when its distance to the manifold is less than δ and its distance to x0 is at most R − δ.The section combines normal-direction convergence with tangential-excursion estimates inductively to lower-bound the probability of remaining in the basin.Source: §5 · pp. 30–31
Theorem 5.8
- Theorem 5.8 estimates the probability that SGD is within distance ε of the local-minimum manifold at time n, under the stated initialization and regularity assumptions.The initial condition is uniformly distributed on a bounded open set intersecting the manifold.Source: §5 · pp. 36–37
Corollary 5.9
- Corollary 5.9 estimates the probability that K independent SGD runs fail to come within distance ε of the local-minimum manifold by time n.The corollary follows from Theorem 5.8 and independence of the runs.Source: §5 · pp. 39–40
Corollary 5.10
- Corollary 5.10 translates convergence of the independent SGD runs to the local-minimum manifold into a statement about minimizing the objective function.The translation uses Corollary 5.9 and the objective function's local regularity.Source: §5 · pp. 40–41
Lemma 5.11
- Lemma 5.11 establishes a measurable selection that minimizes a mini-batch approximation, addressing the computational difficulty of obtaining the converged random variable directly.The section then states that the minimum in (5.134) can be efficiently computed using mini-batch averages.Source: §5 · p. 41
Theorem 5.12
- For every x0 ∈ M ∩ U ∩ A, positive R0, δ0, r, and c exist such that for all R ∈ (0,R0], δ ∈ (0,δ0], r ∈ (0,r], n, M, M, K ∈ N, and ε ∈ (0,1], a condition is asserted.Source: §5 · p. 42
Corollary 5.13
- The computational-cost constant depends on computing F and ∇θF and initializing X₁,₁, but not on runtime n, sampling size K, or mini-batch sizes M and M.This independence is stated for the algorithm proposed in Theorem 5.12.Source: §5 · p. 45
- n(ε)=c1ε^-2/ρ, M(ε)=c2ε^(-4/ρ+4), M(ε,η)=c3ε^-2η^-1|log(η)|, and K(η)=c4|log(η)| give the parameter scalings in Corollary 5.13.The corollary states these scalings for ε, η ∈ (0,1].Source: §5 · p. 45
6 Stochastic gradient descent - The compact case
In the compact case, SGD converges toward the manifold of local minima, and compactness improves the estimates by preventing escape from the basin along directions tangent to that manifold.
6 Stochastic gradient descent - The compact case
- The section analyzes convergence to the manifold in directions normal to it under the additional assumption that the manifold of local minima is compact.The compactness assumption also underlies the probability estimates for SGD convergence and the improved efficiency result.Source: §6 · pp. 47, 50, 51
- Compactness improves the convergence estimate because SGD cannot leave the basin of attraction along directions tangent to the manifold of minima.The compact-case analysis allows the radius parameter to grow without bound and extends the stated range of ρ to (0, 1).Source: §6 · pp. 47–48
- n(ε)=c1ε−2/ρ, M(ε)=c2ε−2/ρ+2, M(ε,η)=c3ε−2η−1 |log(η)|, and K=c4 |log(η)| give the compact-case parameter choices in Corollary 6.5.The result concerns the computation efficiency of the SGD algorithm analyzed in Theorem 6.4.Source: §6 · p. 51
7 Applications
The paper verifies its convergence theorem for two simple neural-network objectives. Their global minima form non-isolated manifolds, a setting where results requiring locally unique minima do not apply.
7 Applications
- The two network examples have global-minimum sets of codimensions 2 and 1, so their minima are not locally unique and results requiring that property do not apply.The examples are a four-parameter affine-linear network with linear activation and a two-parameter network with ReLU activation.Source: §7 · p. 52
7.1 A four-parameter network with a linear activation function
- The conditions of Theorem 1.1 hold for a four-parameter affine-linear network with linear activation, whose local minimum set is a non-empty two-dimensional submanifold of R4.The proof establishes the minimum-set characterization and verifies the nondegeneracy assumption.Source: §7.1 · pp. 52, 54
7.2 A two parameter network with the ReLU activation function
- The conditions of Theorem 1.1 also hold for a two-parameter affine-linear network with ReLU activation, whose local minimum set is a non-empty one-dimensional submanifold of R2.The proof also establishes the nondegeneracy assumption for this example.Source: §7.2 · pp. 54, 56