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

arXiv:2505.20817v3 Announce Type: replace-cross Abstract: Gradient clipping is widely used in language-model training to control heavy-tailed gradient noise and can improve convergence guarantees over stochastic gradient descent (SGD) under (L_0,L_1)-smoothness. Under these joint conditions, a central challenge is to obtain high-probability guarantees without exponential dependence on L_1R_0, where R_0 bounds the initial distance to a minimizer. We resolve this challenge for convex objectives, establishing, to the best of our knowledge, the first such guarantees for standard Clip-SGD. We assume unbiased stochastic gradients with bounded central alpha-th moment, alphain(1,2]. Our bounds have only polylogarithmic dependence on the inverse failure probability and recover known deterministic generalized-smoothness rates when the noise vanishes, as well as the standard high-probability rate under heavy-tailed noise in the classical L-smooth setting. The convex rate is attained by a computable output that averages iterates whose sampled stochastic gradients are not clipped, requiring neither function values nor extra oracle calls. We establish a lower bound for Clip-SGD with any fixed stepsize and clipping level, showing that, under the stated iteration conditions, our convex stochastic rate is optimal up to logarithmic factors in the iteration budget. Our upper-bound analysis uses a directional clipping-bias bound to absorb part of the bias into the progress generated by the clipped population gradient, avoiding an exponentially large local smoothness constant. We also obtain nonconvex high-probability guarantees that recover the noiseless rate, match the classical-smooth stochastic iteration rate when L_1=0, and have no explicit L_1 dependence in the asymptotically dominant stochastic term.

Source: arXiv cs.LG | 2026-09-30

Related