PaperlayerView exact revision on arXiv

Source-linked AI summary

Handbook of Convergence Theorems for (Stochastic) Gradient Methods

Guillaume Garrigos, Robert M. Gower

arXiv:2301.11235v3math.OC

TL;DR

The handbook addresses how to prove convergence and complexity rates for gradient, stochastic, and proximal methods under standard function assumptions. It organizes simple proofs for independent consultation, including less-common SGD variants; the cited results include linear convergence for strongly convex smooth settings and Fejér monotonicity for stochastic Polyak stepsizes. Its scope is bounded by strong global assumptions such as the PL property and by incompatibilities among some assumptions.

  • Problem

    Existing convergence analyses span many gradient-type methods and function classes, creating a need for simple, easy-to-reference proofs across these settings.

  • Method

    The handbook collects and presents simple proofs for gradient descent, stochastic variants, minibatching, momentum, subgradient, proximal-gradient, and related methods.

  • Results

    The collection includes a linear convergence rate of 1 − µ/L for strongly convex smooth gradient descent and establishes Fejér monotonicity for stochastic Polyak stepsizes.

  • Takeaways & Limitations

    The notes provide an independently consultable reference for global convergence and complexity arguments across smooth, convex, strongly convex, PL, and nonsmooth settings.

  • Takeaways & Limitations

    The PL property is a strong global condition, and strongly convex functions cannot also be Lipschitz continuous under the cited assumptions.

Abstract

from arXiv · show

This is a handbook of simple proofs of the convergence of gradient and stochastic gradient descent type methods. We consider functions that are Lipschitz, smooth, convex, strongly convex, and/or Polyak-Łojasiewicz functions. Our focus is on ``good proofs'' that are also simple. Each section can be consulted separately. We start with proofs of gradient descent, then on stochastic variants, including minibatching and momentum. Then move on to nonsmooth problems with the subgradient method, the proximal gradient descent and their stochastic variants. Our focus is on global convergence rates and complexity rates. Some slightly less common proofs found here include that of SGD (Stochastic gradient descent) with a proximal step, with momentum, and with mini-batching without replacement.

1 Introduction

The handbook collects simple, reusable convergence proofs for gradient and stochastic gradient methods across common function classes. It is organized as a reference rather than a linear literature review or textbook.

  • The notes collect convergence proofs for gradient and stochastic gradient based methods, emphasizing simple proofs that achieve the best rate for each setting.The collection includes known proofs as well as the authors’ preferred presentations.
  • The handbook is intended as an easy-to-reference collection, not a proper review of the literature.Readers are asked to cite the original sources alongside the handbook.
  • Sections can be consulted independently, with assumptions and properties linked backward from convergence results.The table of contents and Table 1a are recommended entry points.
  • The notes are not designed to be read linearly because doing so would be unnecessarily tedious.

2 Theory : Smooth functions and convexity

This section develops foundational definitions and characterizations for smoothness, convexity, strong convexity, and the Polyak–Łojasiewicz property. It connects these assumptions to Hessian conditions, least-squares examples, and convergence-relevant inequalities.

  • 2.1.1 Notations: The Jacobian maps derivatives of F: R^d → R^p into a matrix in R^p×d, while the gradient is the transpose differential of a scalar function.The Hessian of a twice-differentiable scalar function is a d × d matrix and is symmetric.
  • 2.1 Smoothness: An L-Lipschitz differentiable map has uniformly bounded differential, and the converse follows through the mean-value inequality.For scalar functions, L-smoothness means the gradient is L-Lipschitz.
  • 2.2 Convexity: Convex differentiable functions lie above every tangent plane, while twice-differentiable convex functions have nonnegative Hessian eigenvalues.These first- and second-order characterizations are used throughout the convergence proofs.
  • 2.3 Strong convexity: Strong convexity is equivalent to adding µ/2∥x∥2 to a convex function, and its Hessian eigenvalues are at least µ when twice differentiable.A continuous strongly convex function has a unique minimizer; least-squares is strongly convex exactly when Φ is injective.
  • 2.4 Polyak- Lojasiewicz: The Polyak–Łojasiewicz property is weaker than strong convexity and can hold without convexity, while ensuring critical points are global minimizers.For least-squares, the PL constant is the smallest nonzero eigenvalue of Φ⊤Φ; the property is global and relatively strong, with local variants discussed.
  • Smooth and convex functions: Smooth convex functions satisfy the co-coercivity inequality, a stronger joint consequence than simply combining smoothness and convexity.

3 Gradient Descent

This section presents simple convergence proofs for gradient descent under convex, strongly convex, and Polyak–Łojasiewicz assumptions, with corresponding complexity guarantees.

  • Setup: Gradient descent minimizes a well-posed differentiable function using iterates determined by an initial point and positive stepsize.Stepsizes are also called learning rates in machine learning.
  • Convex and smooth functions: Convex and L-smooth objectives achieve sublinear convergence under a stepsize satisfying 0 < γ ≤ 1/L.The section provides both Lyapunov-energy and direct proofs.
  • Convex and smooth functions: The Lyapunov proof combines function suboptimality and squared distance to a minimizer into a decreasing energy.The proof establishes descent of both quantities and concludes by dividing the resulting bound by t.
  • Convex and smooth functions: Convex smooth gradient descent has O(1/t) complexity for reaching ε accuracy when γ = 1/L.The direct proof specializes to γ = 1/L.
  • Strongly convex and smooth functions: For μ-strongly convex and L-smooth objectives, gradient descent has linear convergence with rate 1 − μ/L and O(log(1/ε)) complexity when γ = 1/L.Two proofs use first-order inequalities or Hessian eigenvalues bounded between μ and L.
  • Polyak–Łojasiewicz functions: Under the Polyak–Łojasiewicz condition and smoothness, gradient descent also obtains logarithmic complexity, while local minima and critical points are global minima.The section describes this setting as recovering bounds similar to the strongly convex case.

4 Theory : Sum of functions

This section develops smoothness, interpolation, and noise tools for objectives written as sums of functions, connecting component assumptions to aggregate convergence analysis.

  • Problem and assumptions: The section studies minimizing a well-posed objective represented as a sum of component functions that are bounded below.It considers componentwise convexity and componentwise smoothness assumptions.
  • Smoothness: If each component f_i is L_i-smooth, then the aggregate objective is L_avg-smooth.The result follows from the component smoothness assumptions.
  • Expected smoothness: Under component convexity and smoothness, the aggregate objective satisfies L_max-smoothness in expectation and an analogous expected cocoercivity inequality.The bounds use the largest component smoothness constant L_max.
  • Interpolation: Interpolation means that one point simultaneously minimizes every component function and therefore also minimizes their sum.For learning problems, this corresponds to perfectly fitting every data point.
  • Interpolation examples: For least-squares models, interpolation is equivalent to attaining inf f = 0; in linear models it corresponds to y lying in the range of Φ.Overparameterized regimes can generically satisfy this condition when d > n.
  • Noise measures: Gradient noise and function noise quantify departure from interpolation, and interpolation implies zero gradient noise, with equivalence under component convexity.Function noise is also zero exactly when interpolation holds for least-squares objectives.

5 Stochastic Gradient Descent

This section analyzes stochastic gradient descent for sums of functions, emphasizing stepsize choices, interpolation-dependent behavior, and convergence under convex, strongly convex, and Polyak–Łojasiewicz assumptions.

  • General SGD analysis: SGD follows a sampled component gradient, which is an unbiased estimator of the full gradient, and its behavior depends strongly on the stepsize sequence.The general analysis assumes stepsizes 0 < γ_t ≤ 1/(4L_max).
  • Stepsize selection: The stepsize analysis balances a bias term, requiring divergent cumulative stepsizes, against a variance term controlled by the stepsize squares.Constant stepsizes remove the bias term but require separate treatment of persistent variance.
  • Convex smooth SGD: With interpolation, gradient variance is zero and constant-step-size SGD achieves a 1/t expected convergence rate, matching deterministic gradient descent.The section describes interpolation as making the stochastic problem sufficiently easy for this behavior.
  • Convex smooth SGD: Without interpolation, constant-step-size SGD does not converge because its variance term remains O(1); decreasing stepsizes require a trade-off, with α = 1/2 identified as the best compromise for the stated bound.The discussion contrasts slowly decreasing stepsizes, which enlarge the denominator, with rapidly vanishing stepsizes, which reduce the numerator.
  • Convex smooth SGD: For convex smooth objectives, constant-step-size SGD provides an O(1/ε^2) complexity guarantee, while vanishing-step-size SGD uses weighted averages of past iterates.The constant stepsize is bounded by 1/(4L_max).
  • Strongly convex SGD: For strongly convex objectives, constant-step-size SGD yields a geometric convergence bound and a Õ(1/ε) complexity guarantee for squared distance to the minimizer.The stepsize satisfies 0 < γ < 1/(2L_max).
  • Polyak–Łojasiewicz SGD: For smooth Polyak–Łojasiewicz objectives, constant-step-size SGD obtains a geometric recursion and Õ(1/ε) complexity under a stepsize bounded by μ/(L_f L_max).The proof uses variance transfer together with the Polyak–Łojasiewicz property.
  • Nonconvex SGD: Without the Polyak–Łojasiewicz condition in the nonconvex setting, the analysis establishes stationarity bounds rather than global optimality results.The section attributes global optimality results to the Polyak–Łojasiewicz setting.

6 Minibatch SGD

MiniSGD replaces single-sample gradients with uniformly sampled batches, preserving unbiasedness while interpolating between SGD and GD. Under convex smoothness assumptions, the handbook derives convergence and complexity guarantees for constant, horizon-dependent, and diminishing stepsizes.

  • Minibatch construction: MiniSGD samples each batch uniformly among subsets of size b and updates iterates using the resulting minibatch gradient.The batch size satisfies b ∈ {1, ..., n}.
  • Minibatch construction: The expected minibatch gradient equals the full gradient ∇f(x), so minibatching preserves unbiased gradient estimation.This expectation is taken under the uniform batch-sampling law.
  • Analysis tools: Mini-batching improves parallel resource use and can improve SGD complexity through gradient-noise and expected-smoothness analyses.The analysis uses gradient noise, expected smoothness, and variance transfer as central tools.
  • Interpolation between SGD and GD: For b = 1, MiniSGD reduces to SGD with L_b = Lmax, whereas b = n recovers GD with L_b = L and zero variance.Thus minibatching connects the stochastic and deterministic endpoint behaviors.

7 Stochastic Momentum

The momentum section presents equivalent stochastic momentum formulations and proves convex smooth convergence using an iterate-moving-average viewpoint. Its parameterized result yields an O(1/ε^2) complexity guarantee for the iterates themselves, improving on the available SGD guarantee for averaged iterates.

  • Momentum formulations: Momentum is motivated by its widespread use in machine learning and is formulated with stochastic gradients, stepsizes, and momentum parameters.The algorithm initializes m_{-1} = 0 and generates the sequence (x_t).
  • Complexity: The resulting momentum method has O(1/ε^2) complexity for the iterates, whereas the cited SGD result provides complexity only for averaged iterates.The comparison is stated within the convex setting.
  • Momentum formulations: The momentum and heavy-ball formulations are equivalent after setting ˆγ_t = γ_t and ˆβ_t = γ_tβ_t.The equivalence is established directly for the generated iterates.
  • Momentum formulations: Momentum also admits an iterate-moving-average formulation that introduces auxiliary variables z_t and rewrites x_{t+1} as a weighted combination of x_t and z_t.This IMA viewpoint is used in the convergence proof.
  • Convergence: For convex smooth objectives, parameters γ_t = 2η/(t + 3) and β_t = t/(t + 2), with η ≤ 1/(4Lmax), yield convergence of the iterates.The proof analyzes the squared distance of the auxiliary sequence and uses telescoping.

8 Theory : Nonsmooth functions

The nonsmooth-functions section develops subgradients and proximal operators as tools for optimization beyond differentiability. It establishes their key convex-analytic properties, including optimality characterization and proximal non-expansiveness.

  • Sources of nonsmoothness: Nonsmoothness arises from nondifferentiable functions such as the L1 norm and ReLU, or from functions defined only on a restricted domain.Indicator functions encode constrained minimization through composite objectives.
  • Subgradients: A subgradient η at x satisfies f(y) ≥ f(x) + ⟨η, y − x⟩ for every y, and the subdifferential collects all such subgradients.For differentiable convex functions, the subdifferential reduces to the singleton {∇f(x)}.
  • Subgradients: Convex Lipschitz continuity is equivalent to uniformly bounded subgradients, extending the gradient characterization to nondifferentiable functions.The common bound is the Lipschitz constant G.
  • Subgradients: For convex functions, a point minimizes f exactly when 0 belongs to its subdifferential.This is the nonsmooth analogue of the zero-gradient optimality condition.
  • Proximal operators: The proximal operator minimizes g(u) plus a quadratic penalty and is characterized by a subdifferential inclusion.For indicator functions of closed convex sets, it coincides with projection.
  • Proximal operators: Under proper lower-semicontinuous convexity, the proximal operator is 1-Lipschitz, or non-expansive, and can characterize composite minimizers through fixed points.These properties are presented as tools for subsequent nonsmooth optimization proofs.

9 Stochastic Subgradient Descent

Stochastic subgradient descent minimizes expected convex stochastic functions using unbiased sampled subgradients. Under convexity and Lipschitz assumptions, averaged iterates achieve sublinear convergence, while projected variants improve complexity under bounded-solution assumptions.

  • Problem and assumptions: The stochastic objective is an expectation of convex, G-Lipschitz functions, with measurable sampled subgradients available through an oracle.These assumptions imply that the expected objective is convex and G-Lipschitz, and sampled subgradients are bounded.
  • Algorithm: SSD extends stochastic gradient descent by updating with a sampled subgradient of the sampled function.The sampled subgradient is an unbiased estimator of a subgradient of the expected objective.
  • Convergence rates: With constant stepsizes, averaged SSD iterates obtain a finite-horizon sublinear bound, and choosing γ = 1/√T yields the associated rate.The theorem and corollary specialize the general stepsize estimate to fixed horizons and give an ε-complexity guarantee.
  • Convergence rates: A decreasing stepsize γ_t = γ_0/√(t+1) gives a convergence bound involving logarithmic dependence on the horizon.The handbook contrasts this schedule with the constant-stepsize finite-horizon choice.
  • Projected SSD: Projected SSD adds projection onto a ball containing a solution and uses decreasing stepsizes to remove the logarithmic term from the convergence rate.The localization assumption requires a solution x* with ∥x*∥ ≤ B, and the projection keeps iterates within that ball.
  • Scope boundary: Strong convexity is incompatible with the global G-Lipschitz assumption imposed on the stochastic component functions.The handbook states this impossibility as a lemma and supports it by showing that strong convexity eventually requires unbounded subgradients.

10 Stochastic Polyak Stepsizes

Stochastic Polyak Stepsizes adapt SSD using sampled function-value gaps and require knowledge of optimal sampled values. Their defining choice minimizes an upper bound on Lyapunov-energy decrease and yields almost-sure Fejér monotonicity.

  • Definition and motivation: SPS is SSD with a stepsize based on the positive part of the sampled function-value gap relative to f_ξ(x*).The required optimal sampled values are especially accessible under interpolation, where they equal inf f_ξ.
  • Definition and motivation: Among nonnegative stepsizes, SPS minimizes the upper bound on the discrete decrease of the Lyapunov energy ∥x_t − x*∥^2.This optimality criterion motivates the adaptive stepsize definition.
  • Monotonicity: SPS iterates are Fejér monotonic almost surely, so their distance to any fixed solution does not increase.The zero-subgradient and nonzero-subgradient cases both establish the same monotonicity inequality.
  • Local assumptions: Fejér monotonicity bounds the iterates in advance, allowing assumptions on subgradient boundedness to be imposed only on a solution-centered ball.The resulting local assumption replaces global bounded-subgradient requirements for the SPS analysis.
  • Convergence results: Under convexity and locally bounded subgradients, SPS admits a convergence theorem for averaged iterates, while strong convexity yields a stronger rate result.Both results use the initial distance D = ∥x_0 − x*∥ and local boundedness on the corresponding solution ball.

11 Proximal Gradient Descent

Proximal gradient descent handles composite objectives by combining a gradient step for the smooth term with a proximal step for the nonsmooth term. Convexity gives sublinear convergence, while strong convexity gives linear convergence and logarithmic complexity.

  • Problem and algorithm: PGD minimizes F = f + g by alternating a gradient step on differentiable f with a proximal step on proper lower-semicontinuous g.The composite problem is assumed well-posed, and the convex convergence theorem requires both terms to be convex with f L-smooth.
  • Convex convergence: For convex f and g with γL ≤ 1, PGD produces decreasing function values and a decreasing Lyapunov energy.The proof combines proximal optimality, smoothness, and convexity inequalities.
  • Convex convergence: With γ = 1/L, the convex method reaches ε accuracy with O(1/ε) complexity.The complexity result follows from the convex convergence bound.
  • Strongly convex convergence: If f is μ-strongly convex and L-smooth while g is convex, PGD contracts squared distance to a minimizer by the factor 1 − γμ.The handbook gives both a first-order proof and a proof based on Lipschitzness of the gradient and proximal operator.
  • Strongly convex convergence: For γ = 1/L in the strongly convex setting, PGD has O(log(1/ε)) complexity.This is stated as the corresponding strongly convex corollary.

12 Proximal Stochastic Gradient Descent

Proximal stochastic gradient descent extends PGD to composite sums with stochastic smooth components. Under convexity, it provides convergence and ε-complexity bounds governed by gradient noise; strong convexity gives a faster complexity result.

  • Problem and algorithm: PSGD minimizes a composite sum with differentiable component functions and a proper lower-semicontinuous regularizer using sampled gradients followed by a proximal step.The analysis assumes convexity and component smoothness bounded by L_max.
  • Convex convergence: The convex PSGD theorem controls averaged-iterate error using the composite gradient-noise parameter σ*_F and a nonincreasing stepsize sequence.The stepsize is constrained by γ_0 ≤ 1/(8L_max).
  • Convex convergence: Constant stepsizes yield an O(ε^-2) complexity guarantee for convex composite stochastic optimization.The bound uses the initial distance and initial objective gap through C_0.
  • Convex convergence: Vanishing stepsizes γ_t = γ_0/√(t+1) provide an alternative convex convergence bound with logarithmic terms.The schedule is required to satisfy γ_0 ≤ 1/(8L_max).
  • Strongly convex convergence: When f is strongly convex, PSGD admits a stronger convergence theorem and a corresponding ˜O(1/ε) complexity result.The strongly convex result uses constant stepsizes bounded by 1/(2L_max).

13 Stochastic Proximal Point

The stochastic proximal point method minimizes an expected convex stochastic function by applying proximal steps to sampled functions. The section derives general and specialized convergence bounds, including constant and vanishing step sizes.

  • Method: The stochastic proximal point method applies a proximal step to a sampled function fξ at every iteration while minimizing f(x) = E_D[fξ(x)].The iterates are generated from step sizes γt > 0 under an expectation-of-convexity assumption.
  • Constant step sizes: The constant-step-size bound matches the corresponding stochastic subgradient descent bound down to the constant.The section then specializes the result to constant step sizes and derives a complexity guarantee.
  • General step sizes: Theorem 13.2 gives a convergence bound for the stochastic proximal point method with arbitrary positive step sizes and averaged iterates.Its proof compares successive distances to an optimizer, uses proximal optimality and convexity, then telescopes the resulting inequality.
  • Constant step sizes: Choosing γ = 1/√T for a fixed horizon yields the stated averaged-iterate convergence rate and its associated ε-complexity bound.The result is obtained by substituting the horizon-dependent step size into the constant-step-size theorem.
  • Vanishing step sizes: A vanishing step size γt = γ0/√(t+1) yields the section’s convergence-rate result for decreasing step sizes.The proof uses integral bounds to control the step-size sums before applying the general theorem.
  • Related work: The proof of the general stochastic proximal point bound is adapted from Theorem 4.4 in reference [9].

A.1 Converting Rates into Complexity

This appendix collects tools for converting convergence recurrences into complexity bounds and verifies properties of selected functions and algorithms. It includes a nonconvex Polyak–Łojasiewicz example, convexity checks, and auxiliary sum estimates.

  • Converting rates into complexity: Lemma A.2 analyzes a geometrically contracting positive sequence and provides an ε-dependent guarantee for when αk becomes at most ε.The proof rearranges the recurrence and applies logarithms, with a separate trivial case when ρ = 0.
  • Converting rates into complexity: Lemma A.3 derives sufficient step-size conditions for controlling a recurrence with constants µ, A, and C and ensuring αt ≤ ε.The proof first controls the second term, restricts γ, and then bounds the contraction term logarithmically.
  • A nonconvex PL function: f(t) = t^2 + 3 sin(t)^2 is nonconvex but satisfies the Polyak–Łojasiewicz condition with µ = 0.025 = 1/40.Nonconvexity follows because f''(π/2) = −4, while the PL inequality is verified by analyzing the sine curve.
  • Stochastic Polyak Stepsize: The Stochastic Polyak Stepsize minimizes the right-hand side of the relevant one-step bound, selecting the positive unconstrained minimizer or zero.When the sampled subgradient is zero, the optimal step is γ = 0; otherwise the constrained solution is (γ̂)+.
  • Convexity verification: The convexity appendix proves convexity on an open region using positive-semidefinite Hessians and extends it to the full domain by the definition of convexity.At the boundary, the generalized Hessian is a set of positive-semidefinite matrices, and separate cases complete the domain argument.
  • Auxiliary bounds: The sum-integral bounds provide logarithmic estimates, including 1/t ≤ 2 log(T + 1) and related upper bounds used in rate conversions.The bounds follow from standard comparisons for decreasing positive functions.
Loading 2301.11235v3…