Precise Convergence Speed of Clipped SGD

David A. R. Robin

In the authors' words

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 $ℓ_{2}$ -projection, simplifying proofs. We also extend the domain of validity from $η \leq 1/ (9 β)$ to $η < 1/ β$ where $β = L_{0} + c L_{1}$ for clipping constant $c$ , which matches the more traditional analysis of smooth functions. We strengthen the convergence criterion from $(min_{t < T} E [∥ \nabla f (x_{t}) ∥_{2}])$ to $(\frac{1}{T} \sum_{t < T} E [∥ \nabla f (x_{t}) ∥_{2}])$ with matching speed, and lower the final achievable loss from $O (min (σ^{2} / c, σ))$ to the more precise $6 min (σ^{2} / c, 3 σ)$ .

Main resultThe abstract does not state a limitation.

Precise Convergence Speed of Clipped SGD

In the authors' words

More on Learning theory & optimization that day

Transformers as Cross-Task Learners: Shared Structure Drives Sample Efficiency in In-Context Learning

Nuclear Norm-Regularized Bayesian Matrix Completion

Human-AI-Powered Hypothesis Testing: Cost-Aware Selective AI Scoring and Sequential Human Escalation

Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs

Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity