Source-linked AI summary
Precise Convergence Speed of Clipped SGD
David A. R. Robin
TL;DR
The paper tightens convergence analysis for clipped SGD on (L0, L1)-smooth functions, a relaxation introduced to model the observed decrease in Hessian spectral norm during training. By simplifying the projection-based bias proof, it establishes an average-gradient criterion and extends the valid step-size range to ηβ̄ < 1.
Problem
For clipped SGD on (L0, L1)-smooth functions, prior analysis used a minimal-gradient convergence criterion, while this smoothness relaxation models Hessian spectral-norm decrease during training.
Source: pp. 1–2Method
The analysis refactors case disjunctions to expose how ℓ2-projection properties control clipping bias, and uses this in the Clip-SGD descent analysis.
Source: pp. 1–2Results
The strengthened descent condition yields an average-L1 criterion, and the valid step-size range is ηβ̄ < 1, with β̄ = L0 + cL1.
Source: pp. 2–3Takeaways & Limitations
The precise non-asymptotic rate permits hyperparameter selection to minimize its upper bound using quantities such as training time and variance.
Source: p. 2The authors conjecture that the constants 2 before ζ and in min(σ²/c, σ) are not tight.
Source: p. 2
Abstract
from arXiv · showhide
We present a tightened convergence analysis of clipped gradient descent on $(L_0, L_1)$-smooth functions, with quantitative constants. Building on the ideas of Koloskova et al (2023), we refactor several case disjunctions to reveal the central role of a control of the bias derived from fundamental properties of $\ell_2$-projection, simplifying proofs. We also extend the domain of validity from $\eta \leq 1 / (9 \beta)$ to $\eta < 1 /\beta$ where $\beta = L_0 + c L_1$ for clipping constant $c$, which matches the more traditional analysis of smooth functions. We strengthen the convergence criterion from $\left( \min_{t < T} \mathbb{E}[\lVert \nabla f(x_t) \rVert_2] \right)$ to $\left( \frac{1}{T} \sum_{t < T} \mathbb{E}[\lVert \nabla f(x_t) \rVert_2] \right)$ with matching speed, and lower the final achievable loss from $\mathcal{O}(\min(\sigma^2/c, \sigma))$ to the more precise $6 \min(\sigma^2 /c, 3 \sigma)$.
A Appendix : Proofs omitted from main text
The appendix bounds the bias introduced by clipping a random gradient, using properties of ℓ2 projection and case analysis based on the mean norm, clipping threshold, and noise scale.
Bias bounds
- For ∥µ∥ ≥ ε0, the squared bias is at most min(∥µ∥², c²)/4; for ∥µ∥ ≤ ε0, the bias is bounded using Lemma A.2.These bounds cover the large- and small-mean regimes, respectively.Source: A Appendix : Proofs omitted from main… · p. 4
Projection properties
- The proof targets a 1/4 bias constant by using three ℓ2-projection properties that control bias according to ∥µ∥.It splits cases by whether ∥µ∥ is above or below c, then whether min(∥µ∥, c) is above or below σ.Source: A Appendix : Proofs omitted from main… · p. 4
Bias bounds
- The bias ∥Pcµ − E[PcX]∥ is bounded by ε0/2, with separate cases for clipping thresholds above or below 4σ.Here ε0 = 4 min(σ, σ²/c); the proof then defines κ = ε0 min(ε0/8, 2c) for its subsequent bounds.Source: A Appendix : Proofs omitted from main… · p. 4
Projection properties
- A correlation argument bounds µ · E[PcX] using the identity E[µ · PcX] = E[X · PcX] − E[(X − µ) · PcX].For ∥µ∥ ≥ c, the proof substitutes Pcµ = (c/∥µ∥)µ into the resulting inequality.Source: A Appendix : Proofs omitted from main… · p. 5
- Firm non-expansiveness of projection bounds the squared distance between projected points by their original squared distance, supporting the bias estimates.The proof applies this property to Pcµ and PcX, then uses Jensen’s inequality and the variance bound.Source: A Appendix : Proofs omitted from main… · p. 5
- The proof uses the clipping residual ∥v − Pcv∥ = (∥v∥ − c)+ and a lower bound on that residual to handle the case ∥µ∥ < c.In this regime Pcµ = µ, and the argument combines the residual bounds with Jensen’s inequality.Source: A Appendix : Proofs omitted from main… · p. 5