Convergence of Clipped SGD on Convex ( L 0 , L 1 ) (L_{0},L_{1}) -Smooth Functions

Ofir Gaash, Kfir Yehuda Levy, Yair Carmon · 2025

Read Convergence of Clipped SGD on Convex ( L 0 , L 1 ) (L_{0},L_{1}) -Smooth Functions by Ofir Gaash, Kfir Yehuda Levy, Yair Carmon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16492.txt.

Introduction

Ofir Gaash, Kfir Levy, and Yair Carmon analyzed clipped gradient descent under a broader smoothness notion in a 2025 paper. Real loss surfaces are not uniformly smooth: their steepness grows with the gradient itself, captured by a two-parameter smoothness class that has recently attracted attention. Plain stochastic gradient descent can misbehave there, while clipping each gradient step to a capped length is the standard practical fix, now given a rigorous footing.

For convex problems in this class, clipped descent reaches the same high-probability convergence rate as the classic smooth case, up to logarithmic factors and additive terms. An adaptive clipped variant matches the guarantee without hand-tuned step sizes. Experiments check the theory's predictions on algorithmic choices.

Catalog record

CREATOROfir Gaash, Kfir Yehuda Levy, Yair Carmon
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-16492

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Convergence of Clipped SGD on Convex ( L 0 , L 1 ) (L_{0},L_{1}) -Smooth Functions Ofir Gaash, Kfir Yehuda Levy, Yair Carmon Abstract We study stochastic gradient descent (SGD) with gradient clipping on convex functions under a generalized smoothness assumption called ( L 0 , L 1 ) (L_{0},L_{1}) -smoothness. Using gradient clipping, we establish a high probability convergence rate that matches the SGD rate in the L L smooth case up to polylogarithmic factors and additive terms. We also propose a variation of adaptive SGD with gradient clipping, which achieves the same guarantee. We perform empirical experiments to examine our theory and algorithmic choices. 1 Introduction Gradient clipping is a common method for stabilizing neural network training. Despite its wide use, little thought is given to the choice of the clipping threshold , with many works fixing it at 1 without attempting to tune it [ 3 , 5 , 34 , 35 , 2 , 20 , 21 ] . In pursuit of a theory-driven threshold choice, recent research tries to better understand the benefits of gradient clipping. Experiments suggest that clipping is effective in situations where small changes in input can lead to significant variations in gradient norms [ 43 , 42 ] . This observation has led Zhang et al. [43] to formally define this behavior as the following “relaxed” smoothness property. Definition 1 . A twice-differentiable function f:\mathbb{R}^{d}\to\mathbb{R} is (L_{0},L_{1}) -smooth if for every x\in\mathbb{R}^{d} it holds that \|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\| . In words, (L_{0},L_{1}) -smoothness allows the Hessian norm to increase linearly in the gradient norm. This is opposed to the traditional smoothness property, which says that the Hessian norm is bounded by a constant, coinciding with the new definition for L_{1}=0 . Building on this definition, Zhang et al. [43] show instances where clipped SGD outperforms standard SGD. Specifically, they denote M=\sup\left\{\|\nabla f(x)\|\;|\;f(x)<f(x_{0})\right\} , and show that the complexity of SGD with a fixed stepsize is larger than the complexity of SGD with gradient clipping by a factor of L_{1}M (assuming both algorithms are initialized at x_{0} ). This factor can be very large: in particular, it may be exponential in L_{1}R_{0} , where R_{0} is the initial distance from the optimum (see Appendix G ). The connection between (L_{0},L_{1}) -smoothness and gradient clipping has led researchers to attempt to characterize the complexity of (L_{0},L_{1}) -smooth optimization, mainly in terms of the dependence on L_{1} . The non-convex setting is well understood: the state-of-the-art rate of gradient norm convergence comprises of the rate for L_{0} -smooth functions and additional low-order terms that depend on L_{1} . This holds for both clipped GD [ 38 ] and clipped SGD [ 37 ] (see Section 2 for details). Motivation for studying the convex setting. Despite being originally motivated by the behavior of (non-convex) neural networks, generalized smoothness is also compelling to study in the convex setting. There are several instances where convex analysis closely aligns with empirical behavior; among them are AdaGrad-based algorithms and the momentum technique, in which theory preceded practice [ 29 , 7 , 32 ] . Furthermore, a body of work show that neural networks have convex-like behavior [ 14 , 45 , 22 ] . From a theoretical perspective, it allows to examine whether the pattern observed for gradient norm convergence—an L_{0} -smooth rate with low-order L_{1} -dependent terms—also holds for optimality gap convergence. These considerations have motivated recent work to study the convex, (L_{0},L_{1}) -smooth setting [ 15 , 18 , 11 , 38 , 37 , 24 ] . For clipped GD, [ 11 , 38 , 37 , 24 ] prove an optimality gap convergence rate following the aforementioned pattern. However, prior work does not provide a corresponding result in the stochastic setting (we discuss a concurrent work by Lobanov and Gasnikov [23] in Section 2 ). The difficulty of the stochastic, convex regime stems from the fact that clipping biases stochastic gradients. Bias is arguably more challenging in the convex setting than in the non-convex setting: the former intimately relies on stochastic gradients being unbiased, while for the latter it suffices to average enough stochastic gradient such that the noise drops below the required degree of stationarity [ 15 ] . This is potentially the reason previous studies of the convex setting [ 18 , 15 ] proved convergence only in the deterministic regime. Our contribution. In this work, we analyze gradient clipping in the convex, stochastic, (L_{0},L_{1}) -smooth setting with light-tailed noise. Our contributions are as follows. • We show that the pattern of an L_{0} -smooth convergence rate with L_{1} -dependent low-order terms extends to the stochastic convex setting. For clipped SGD with \sigma -sub-Gaussian gradient noise, we prove a sub-optimality bound of O\left(\frac{\log\left({T}/{\delta}\right)L_{0}R_{0}^{2}}{T}+\frac{\log^{2}\left({T}/{\delta}\right)\sigma R_{0}}{\sqrt{T}}\right) that holds with probability at least 1-\delta for T=\Omega(\log\left(\frac{T}{\delta}\right)L_{1}^{2}R_{0}^{2}) . That is, we bound the stochastic gradient query complexity of achieving optimality gap \epsilon with probability at least 1-\delta by \widetilde{O}\left(\frac{L_{0}R^{2}}{\epsilon}+\frac{\sigma^{2}R_{0}^{2}}{\epsilon^{2}}+(L_{1}R_{0})^{2}\right) , where \widetilde{O}(\cdot) hides factors poly-logarithmic in \frac{1}{\delta\epsilon} . This matches the best known bounds for (fixed step-size) SGD in the L_{0} -smooth case, which are \Omega\left(\frac{L_{0}R^{2}}{\epsilon}+\frac{\sigma^{2}R_{0}^{2}}{\epsilon^{2}}\right) [ 16 ] . Our bound depends on L_{1} only through an additive term, with no implicit dependence on \exp\left(L_{1}R_{0}\right) . • We show the same complexity bound for two variations of SGD: adaptive SGD [ 25 ] with clipping, and SGD with a variable stepsize which we refer to as “implicit clipping.” • We show that, to achieve the bounds above, precise knowledge of the parameter L_{1} is not required: simply replacing L_{1} by the conservative choice \widetilde{O}(T^{1/2}/R_{0}) suffices. This result does not appear in papers studying the deterministic regime. • We perform numerical experiments that demonstrate the benefits of gradient clipping for SGD on convex, (L_{0},L_{1}) -smooth functions, and assess the empirical effect of some of our algorithmic choices. For technical reasons, we employ a double sampling technique that uses two independent stochastic gradient samples in each update: one to estimate the direction of the update, and another to estimate its magnitude. This technique is necessary in order to apply some of the probabilistic tools we use, which assume sequences of unbiased random variables, but our empirical analysis suggests it might not be helpful in practice. We elaborate on this technique in the analysis as well as in the experiments. The paper organization is as follows. In Section 2 we survey related work. In Section 3 we outline our algorithmic framework and prove our theoretic results. In Section 4 we describe our experiments and discuss their results. In Section 5 we provide a short conclusion. 2 Related work Generalized smoothness definitions. Zhang et al. [43] first introduced the concept of (L_{0},L_{1}) -smoothness as in Definition 1 . Zhang et al. [42] , Gorbunov et al. [11] , Vankov et al. [38] provide useful equivalent definitions. Li et al. [18] introduce an even more general notion of smoothness: given a non-decreasing continuous function \ell , they define \ell -smoothness as the property \|\nabla^{2}f(x)\|\leq\ell(\|\nabla f(x)\|) . In this work, we focus on (L_{0},L_{1}) -smoothness. Algorithms for (L_{0},L_{1}) -smooth optimization. Most prior work [ 43 , 42 , 30 , 15 , 11 , 38 , 24 , 37 ] consider

Read the complete text