arXiv Machine Learning

High-Probability Convergence of Clipped SGD under Heavy-Tailed Noise and $(L_0,L_1)$-Smoothness

arXiv Machine Learning
Sep 14

Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise

The paper proves that stochastic gradient descent with gradient clipping and additive Gaussian noise (SGD‑CN) converges almost surely under smoothness and bounded noise assumptions, given standard decaying step sizes. The analysis extends to momentum variants such as the stochastic heavy ball and Nesterov's accelerated gradient, showing that careful energy constructions yield similar guarantees. These results provide stronger theoretical foundations for understanding the pathwise behaviour of clipped stochastic gradient methods in both convex and nonconvex regimes.

By Amartya Mukherjee, Jun Liu
arXiv Machine Learning
Oct 16

On the Last-Iterate Convergence of Clipped Gradient Methods

The paper establishes the first optimal last‑iterate convergence rates, in high probability, for Clipped‑SGD when the gradient noise is heavy‑tailed. It addresses the gap left by earlier results that required strong noise assumptions, such as exponentially decaying tails. By proving these rates, the authors provide theoretical support for the practical effectiveness of gradient clipping in stochastic convex optimization.

By Zijian Liu
arXiv Machine Learning
1d ago

Bias-Optimal Bounds for Stochastic Gradient Descent

The paper presents a non‑asymptotic analysis of Stochastic Gradient Descent (SGD) that focuses on the bias component of its convergence bounds. Under assumptions of convexity or strong convexity and smoothness, the authors derive new bias‑optimal bounds for all constant step‑sizes <gamma L> in (0,2), covering critical and large step‑size regimes that were previously unexplored without extra variance assumptions. For critical step‑sizes, the paper shows that while an optimal bias term cannot be achieved, it can be approximated arbitrarily closely, and applies these results to obtain new complexity bounds for the Stochastic Proximal algorithm without requiring regularity assumptions.

By Daniel Cortild, Lucas Ketels, Juan Peypouquet, Guillaume Garrigos