To Clip or not to Clip: the Dynamics of SGD with Gradient Clipping in High-Dimensions
Authors: Noah Marshall
Ke Liang Xiao
Atish Agarwala
Elliot Paquette
Venue: ICLR 2025 Poster (2025)
Keywords: gradient clipping
high-dimensional probability
stochastic optimization
deep learning theory
Primary area: optimization

Abstract: The success of modern machine learning is due in part to the adaptive optimization methods that have been developed to deal with the difficulties of training large models over complex datasets. One such method is gradient clipping: a practical procedure with limited theoretical underpinnings. In this work, we study clipping in a least squares problem under streaming SGD. We develop a theoretical analysis of the learning dynamics in the limit of large intrinsic dimension—a model and dataset dependent notion of dimensionality. In this limit we find a deterministic equation that describes the evolution of the loss and demonstrate that this equation predicts the path of clipped SGD on synthetic, CIFAR10, and Wikitext2 data. We show that with Gaussian noise clipping cannot improve SGD performance. Yet, in other noisy settings, clipping can provide benefits with tuning of the clipping threshold. We propose a simple heuristic for near optimal scheduling of the clipping threshold which requires the tuning of only one hyperparameter. We conclude with a discussion about the links between high-dimensional clipping and neural network training.

Published as a conference paper at ICLR 2025
To CLIP OR NOT TO CLIP: THE DYNAMICS OF SGD WITH GRADIENT CLIPPING IN HIGH-DIMENSIONS
Noah Marshall, Ke Liang Xiao & Elliot Paquette McGill University
Atish Agarwala Google Deepmind
(noah. mww.ha 1 12, kel ang. xi ai @mai megill_ elliot. wwtptapauueeteteeceee ca
thet inetishhe seeissh@googo sh@google.com
ABSTRACT
The success of modern machine learning is due in part to the adaptive optimiza- tion methods that have heen developed to deal with the difficulties of training large models over complex datasets. One such method is gradient clipping: a practical procedure with limited theoretical underpinnings. In this work, we study clipping least squares problem under streaming SGD. We develop a theoretical anal- ysis of the learning dynamics in the limit of large intrinsic dimension a model this limit we find determin-
and dataset dependent notion of dimensionality, istic equation that describes the evolution of the loss and demonstrate that this equation predicts the path of clipped SGD on synthetic, CIFAR1O, 10, and Wikitex12 data. We show that with Gaussian noise clipping cannot improve SGD perfor- mance. Yet, in other noisy settings, clipping can provide benefits with tuning the clipping threshold. We propose simple heuristic for near optimal scheduling the clipping threshold which requires the tuning of only one hyperparameter. We conclude with discussion about the links between nigh-dimensional clipping and neural network training.
INTRODUCTION
Stochastic gradient descent (SGD) methods the standard for nearly all large scale modern op- timization tasks. Even with the ever growing complexities of neural nets, with sufficient hyper- parameter tuning, SGD often outperforms other more complex methods. To deal with the difficulties of training large models over complex datasets, adaptive SGD methods have been developed. One of the simplest such methods is gradient clipping (Mikolov, 2012; Pascanu al., 2013). Gradient clip- ping replaces any stochastic gradient Vefe(x) with clipped gradient (Vefe for some threshold e, where
clip,(z) min (1.
|
While gradient clipping was first introduced to address the problem of exploding gradients in recur- rent neural networks, it has become an integral part of training models for NLP gpt3. It has also found use in other domains such as differential privacy (Abadi et al., 2016; Pichapati et al., 2019) and computer vision (Tolstikhin al., 2021; Dosovitskiy et al., 2021).
Despite widespread use, the reasons behind the effectiveness of clipping remain somewhat mys- tery. For instance, it is unclear exactly how the gradient distribution affects training, or for which distributions clipping can offer benefits. is hypothesized that the distribution of the gradient norms plays a large role (Zhang et al., 2020b). Also, it is unknown how one should adjust the clipping threshold as the problem scales. There has been growing interest in how models and their optimal parammeasssstrss scale with dimension (Kaplan et al., 2020). Understanding this behaviour would allow one perform hyperparameter tuning on smaller, more efficient models before scaling potentially very large final architecture.
In this work develop theory of clipped SGD in dighnssinsss under the mean mean-squared error loss (MSE) over a class random least-squares problems. After formally introducing the class of considered problems (Sec. 2), show the following:

---

Published as a conference paper at ICLR 2025
In high-dimensions the dynamics of clipped SGD (C-SGD) well described by SDE, clipped homogenized SGD (C-HSGD). We provide a non asymptoti bound on the difference the risk curves between C-SGD and C-HSGD. Under C-HSGD the risk evolution can be described by system of ODEs (Sec. 3) which we demonstrate predict the training dynamics under real-world data.
Using C-HSGD, we show that the differences between clipped and unclipped SGD be de- scribed by two unitless reduction factors I and which encode the effect of clipping (Sec. 3).
The reduction factors control the stability of the algorithm. They describe the precise clipping- learning rate combinations which are convergent. Moreover, identify some clipping schedules that improve stability (Sec. 4).
We find a general criterion for when clipping can speed up optimization, described by a different ratio of the reduction factors. We then identify a problem setup where clipping never helps well as one where clipping improves performance. (Sec. 5).
Using these insights, we propose a simple, heuristic clipping and learning rate schedule. This schedule is shown closely follow an optimal schedule which prove will never underperform SGD.
We conclude with a discussion about the links between our analysis and quantities measurable in real neural networks.
Related work: The distribution of noise in stochastic gradients and its effect on training was studied by (Zhang et al., 2020b). They argue that this noise is well approximated by Gaussian for ResNets (He et al., 2015) trained on Imagenet (Deng et al., 2009), while a heavy-tailed distribution more appropriate with BERT (Devlin al., 2019) on an NLP dataset. They show that for heavy- tailed noise unclipped SGD diverges while clipped SGD can converge. Other theoretical analyses on clipping often focus on imposing smoothness conditions on the loss function, and then performing analysis for fixed learning rates (Koloskova et al., 2023; Zhang et al., 2020a; Chen et al., 2020). These works have shown that fixed rate clipped SGD can outperform unclipped SGD under certain conditions. Other works have also studied SGD through the lens of SDEs (Li et al., 2017; Mandt et al., 2016; Barrett Dherin, 2021). More recently, partly spurred by the sheer size of modern models as well as the apparent regularity at which they scale (Kaplan al., 2020), there has been an interest in studying stochastic optimization correspondence between the dynamics of learning-relevant quantities like the loss and the trajectory of an equivalent SDE. These relationships have been worked out for SGD the streaming setup over variety of losses (Collins-Woodfin Woodfin al., 2023; Paquette al., 2022), and the resulting analyses lead to quantities which can be useful for understanding learning dynamics in practical models (Agarwala et al., 2023).
nigh-dimension. with SDEs. There is a formal
PROBLEM SETUP
In this work, we consider linear regression using the mean-squared loss
[(O, x, y) (xx 0) wll2/2. /2/
in the streaming or one-pass scenario, where data is not reused. Clipped SGD (C-SGD), without mini-batching. is described by the iteration
0x+1 = 0₂- - 77k clip,, (VeL Xk+1. Mk+1)),
(3)
where VoL(Ok, X Mk+1) ((x441, 0x) yk++ |x++1 with initialization 0g E R. We assume that the samples {(**) F1s) J220 consisting data x and targets yks satisfy the following:
Assumption 1. The data x E .Rd are Gaussian with covariance K. The targets y are generated by y (x, 0¹) c. where e represents noise and 0" the ground
The noise is centered and subgaussiag (see Vershynin (2018) for more details) with subgaussian norm ||ell S and variance Eie?] x² for some 9, 2 0.
We formulate general version of results for non-Gaussian data in Appendix A.
2

---

Published as a conference paper at ICLR 2025
Definition 1. Define the population risk and the noiseless risk:
P(0) Exx.e) [[(x, 0 -0) -)) and R(0) 1xx
0²)
-x,0-
/2,
(4)
as well as the distance to optimality
( 0 0-1
Our theory is phrased in terms of the intrinsic dimension, statistical notion of dimensionality which occasionally much smaller than the ambient dimension d. There are interesting settings where these dimensions effectively interchangeable, and such, the reader may wish to, first glance, consider the results to be phrased in terms of the ambient dimension.
Definition 2 (Intrinsic Dimension). Let the data x E R have covariance matrix K. Define the intrinsic dimension of the data to be
d d=
(5)
where K refers to the operator norm. Note that d S 8. We will refer to as the ambient dimension. Assumption 2. The covariance matrix K is normalized such that || 1. Note that this assump- tion may always be satisfied by rescaling the problem.
The definition of can be extended to and measured in real neural networks trained on real datasets; Appendix C.3 for more details.
We allow for the scheduling of both the clipping threshold and the learning rate. Specifically,
Assumption 3. There are continuous bounded functions 1j Et + R- and c R+ + RR such that
6 = cck/ddVd
7k = wk/dd//d.
(6)
We note that while it is reasonable for c(t) = (which is to say that clipping occurs), for technical reasons, we shall not allow this in our main theorem.
3 CLIPPED HOMOGENIZED SGD
Our main result shows that the risk of C-SGD is well-approximated by the solution to an SDE which call clipped homogenized SGD (C-HSGD):
Definition 3 (Clipped Homogenized SGD). Denote the stochastic gradient as tax, where to (x, 0 0-) - e. Define the descent reduction factor and the variance reduction factor
(0) = ||B[clip.(oo)
ve(0) = E|clip.
and
||
E
Then C-HSGD is defined to be the solution to
2vetey (O)) dB.,
de, = -0000 + n(O)
(8)
d
where initialization taken to be the same as SGD and B, is a standard Brownian motion.
reformulate the above by redefin- ing (0) ((cl and changing the coefficient on the Brownian motion term to / ( K/d. d. This comes from noticing that B[6]] 2P(0) and [(clip2((o) < in the heavy-tailed case due to the effects of clipping. This yields the immediate observation that clipping improves SGD under heavy-tailes noise since clipped SGD converges while SGD does not.
Remark: If the noise is heavy-tailed (o = oo),
C-HSGD has similar structure to an SDE previously established for unclipped SGD (Paquette et al., 2022), with the addition of reduction factors f.e and that capture the effects of clipping. In essence, the homogenized SGD suggests that, clipped SGD is still driven by a drift term in the direction of -oR but clipping provides bias against the gradient which shrinks the descent term (hereafter
3

---

Published as a conference paper at ICLR 2025
the negative term in (8)). Meanwhile, the diffusion term is shrunk by vo( due to the reduction of variance of the clipped gradients. These terms imply a tradeoff: clipping should aim to reduce variance (decrease Ve) more than it shrinks the descent term (decrease pc). We investigate this trade-off in detail in Section 5.
We compute Me and Ve for select data and noise distributions (Appendix D). For Gaussian data, Stein's Lemma gives us a form for Ae which can be interpreted as the probability of not clipping:
Ue (c( P(| S c).
For non Gaussian data the exact form of μe is challenging to compute due to its dependence x; however, Equation (9) can give a good approximation in many high-dimensional settings due to Central Limit Theorem effects. As example, risk curves for linear models trained CIFARIO (Figure (c)) and Wikitext2 (Figure 1 (d)) are well-captured by the dynamics of C-HSGD with Aee computed using the Gaussian form from Equation 9. See the experiment details in Appendix H.
This form can also be used to tractably compute fe in the non-linear setting using information already computed during C-SGD. See Appendix C.2 for full description of the extension of μa. and Pe to this setting, as well as a demonstration of the technique during training of ResNet18 and ViT on CIFARIO. This allows us cheaply estimate jec and V/ for many values of through training.
There exist a set of tractable lower and upper bounds for μ4 and ve which can be expressed in terms of the risk. In Appendix E, we show that for all noise distributions with well-behaved densities that are positive near 0, there exist positive constants and Ny such that
Kg min
1,
(0c(0) S Keg min
(10a)
V (2((0) + 02
V (2 + 0Z
Ky min
1, 22(()) + 02
(0) S Ku min
1, 22(()) + 0
(10b)
This simple form can be used to derive simple clipping schedules for MSE loss, which we explore in Section 5.3.
We now state our main theorem, which formalizes how C-HSGD is a good description of C-SGD: Theorem 1. Suppose that Assumptions 1, 2 and 3 hold. Suppose that θ and O2 are independent realizationn of C-HSGD and C-SGD with equal, deterministic initial conditions. Let sup, c(t) and π sup, (t). There is a constant C = C(v, (n/d), e. T7, 110 112), stochastic process E, and a constant m = m(f) so that for any S u S md and any n
R(O,)) D(O))
Rk/aa)) [D(O)
sup osk
S (C(nn/duulog(ddd
(11)
with probability 1- - and provided the right hand side is less than 1. The stochastic process is given by
Cn(s)odds E(t) exp (1, VR(O.) + R(0 [ed)
for absolute constant C >> 0. The constant C can be bounded by
C///n// ((1 + |10g 0 11))) + x² /n/d) exp (C max (T,
Informally, this theorem says that
[R(0)) [ (((O)aa]]1 ((0)))
D(()/a)) | (log(d)d
sup ogksn
In particular, as d grows, the risk curves of C-SGD and C-HSGD look closer to another for longer time windows and with higher probability. Under additional assumptions," ? the C-HSGD curve converges to dimension-indeeendenn deterministic limit and thus does clipped SGD, We discuss how to find this deterministic limit in the following section.
The complete proof is detailed in Appendix B along with the theorem statement and proof for non- Gaussian data.
'oode to reproduce the results is available at https//gihab..om/marzzllll "hhe spectrum of K converges and the initialization A 0' converges
4

---

Published as a conference paper at ICLR 2025
Extracting deterministic dynamies: For any twice differentiable function q, the C-HSGD dy- namics can be expressed as follows:
+ n11)2 d (oc)(O.)P()) (KV + d.M.
dg(()) = = (0.10)))o00..)00(000
(12)
where M₁ is martingale term that vanishes d co. This is an example of the concentration of measure phenomenon observed in high-dimensional probability. As a result, we obtain a good deterministic approximation for the evolution of ( by setting M, 0.
Using this idea, we introduce deterministic equivalents, RG and D., for the risk terms R(O;) and D(@)), respectively. Solving for RS and D. involves forming and solving coupled system of ordinary differential equations. Additionally, Theorem 1 implies that these risks under clipped stochastic gradient descent converge their deterministic equivalents. The complete details and derivation of this system of ODEs along with the statement and proof of C-SGD's 's convergence to the deterministic equivalents are available Appendix G.
A numerical comparison of C-SGD, C-HSGD, and the ODEs is provided in Figure 1. In this figure, we demonstrate that these dynamics describe the risk of clipped SGD with both Cauchy and Gaus- sian distributed noise, despite the fact that unclipped SGD does not converge under Cauchy noise. In the same figure we show that these deterministic equivalents describe the dynamics of real-world data.
A simple example of the above theory can be had when the covariance of the data is the identity matrix.
Example 1 (Isotropic data). When the data is isotropic Gaussian, the risk Rg solves the autonomous ODE:
R₂ = (2(()) RR + Ven)) (Re + 02/2),
(13)
where Ro = R(O)).
Since the data is Gaussian, it is possible to express Me and Ve as functions of the risk. As slight abuse of notation we shall also write (R()) or (e() for Ho(0) or (0) respectively. We will suppress the dependence on 0 where appropriate, as we have in Example 1.
4 STABILITY ANALYSIS
In this section we establish stability conditions for streaming SGD with clipping. Stability thresholds from convex models are useful for understanding dynamics in deep learning (Cohen et al., 2021; Agarwala et al., 2023). Additionally, a larger range of stable learning rates can prevent failures in costly training runs. We show that the largest stable learning rate is structurally similar to that of the unclipped SGD case, but with the introduction of the reduction factors and ve which account for the effects of clipping.
From Equation (12), we observe that for either the risk R. or the distance to optimality D, the instantaneous time derivative is quadratic in the learning rate rtt). This implies that can com- pute stability threshold for the learning rate, determining whether, in high-dimensions, these mea- sures of suboptimality increase or decrease. We find the critical values o (t) and (t) such that E[dR(())) = 0 and E[dD(O,)) = O. In particular,
d VP(())) Pe(t) ()))
R(O,) Mc(t) (0:)
mie (t)
Tr(K2) Me(e) (9,) and Tb
(14)
P(O,) Ve(s) (O,)
This implies that clipping increases instantaneous stability (for both R and D) relative to unclipped SGD when
Me(t) (,,)
Ve(e) ( > 1.
(CSC)
We refer to this as the clipped-stability-crieeii (CSC). This can be interpreted as a relative to-iull---noii--raae the fraction of clipped gradients μ reduces the signal, while clipping reduces the noise through the reduction factor Stability is increased when the relative signal-to-noise, ratio is greater than 1. Clipping significantly enhances stability when a small fraction of samples contribute disproportionately to the gradient norm.
5

---

Published as a conference paper at ICLR 2025
0.18
C-HSGD C-SGD
0.18
C-HSGD
C-SGD
0.16
0.16
ODE
Unclipped ODE
0.14
Risk
Risk
0.12
0.12
0.10
0.10
0.08
0.0
2.5
5.0
7.5 Iterations
10.0
12.5
15.0
0.0
2.5
5.0
7.5
10.0
12.5
15.0
lterations
(a) Synthetic data, Gaussian noise
Synthetic data, Cauchy noise
Risk
Risk
10-1
C-SGD
C-SGD 80% CI
ODE
Clipped ODE
10"
101
10a
10a
10
0
10"
10'
10
10a
10
Iterations
Iterations
(c) CIFARIO data, assumed Gaussian noise
(d) Wikitext2 data, assumed GMM noise
Figure 1: Comparison of C-SGD, C-HSGD and their deterministic equivalent (ODE) with Gaussian or Cauchy noise, from the Student-t family. The solution to the unclipped ODE for reference in the Gaussian case. Unclipped SGD does not converge under Cauchy noise. We also compare clipped SGD with CIFARIO as well as Wikitext2 data. In all cases, the deterministic equivalent ODE closely match the actual path of clipped SGD. Experiment details available in Appendix H.
Clipping will increase the stability of SGD with a small enough choice of c:
Theorem 2. For data x K) one may always choose the clipping schedule small enough to satisfy the (CSC).
The proof of this theorem follows from an application of L'Hôpital's rule and is available in Ap- pendix F. We provide plots of the (CSC) in Figure 2 under various settings. We conjecture that this result extends beyond Gaussian data, but the current intractability of μ for general data makes precise claims difficult.
Counterintuitively, clipping can also decrease stability in some cases, when the bias towards VeR (j)) is reduced more than the overall gradient norms (V). This shows that some must be taken to avoid clipping being detrimental. The proof of the following theorem straightforwardly uses the definitions of pe and Ne and can be found in Appendix F.
Theorem 3. Consider x ~ N(, K) and noise with the distribution given by
= p/2,
P(e = 0) = 1--p.
P(c=A)=
(15)
for p E (0. 1) and X 0. Then, there is constant depending X that when R₁ S there always exists c(t) such that the (CSC) is less than 1. Therefore, clipped SGD can be less stable than unclipped SGD)

---

Published as a conference paper at ICLR 2025
5 WHEN DOES CLIPPED SGD OUTPERFORM UNCLIPPED SGD?
We now ask: under what settings can clipping improve the performance of SGD? Specifically, with the optimal learning rate schedule for unclipped SGD, does there exist a clipping-learning rate com- bination such that clipping achieves a lower loss at time T"?
We will use Equation (12) to answer this question. We first present detailed calculations in the isotropic case to find an exact condition on the gradient distribution where clipping improves train- ing. We then show that this condition still applies under anisotropic data. We provide examples and plots of this condition to develop intuition on when clipping helps to improve training. Finally, we propose a new, heuristic clipping schedule which very closely matches an optimal clipping schedule which we prove never underperforms unclipped SGD.
5.1 ISOTROPIC DATA
Consider the case of isotropic data where x ~ I). Define Ri to be the deterministic equivalent of RR(4)), where yp is C-HSGD with c(t) co (which is to say unclipped HSGD). Example shows that RG and R solve the following ODEs,
dR, 2n(()) R2 + Ve(o (2R, + o²), dt
(t)) 2
d dt
R2 + 7 2
(2 + o²)-
(16)
These results enable comparison between clipped and unclipped SGD. Since these ODEs are quadratic in (4), it is straightforward to greedily maximize their instantaneous rate of descent, resulting in the globally optimal learning rate schedule. Optimizing each ODE over ()( yields
dR, dt
R.
dR
(R
(17)
0² 2/2
Ve(e)
dt
R + 02/2
When R2 R2,0 see that the rate of descent is faster and thus clipping improves SGD exactly when there exists a c(t) such that
Po(c Rd)
Vo(() R2)) >1 1.
(CCC)
We call this inequality the clipping-comparison--rrieee exactly understand when clipping is helpful to training. Informally, the improvement criterion tells us that clipping is effective when it can reduce the variance of the gradient norms, via Ve(e) more than it reduces the squared reduction to the descent term (2(1))- This is consistent with previous observa- tions that, in practice, clipping is effective when the distribution of the gradient norms is heavy-tailed Zhang al. (2020b), but gives quantitative rule for comparison. To give some intuition, we provide some plots of these thresholds over various types of noise distributions in Figure 2. In Appendix C. we provide similar plots involving the Student-t family of distributions. This family has a degrees of freedom parameter that allows the family to vary between Cauchy (df = 1) and Gaussian (as df goes to infinity). These plots provide an illustration of the effect that heavy-tailedness can have on the (CSC) and the (CCC).
(CCC). Therefore, in our setting we can
5.2 ANISOTROPIC DATA
The previous results show that with isotropic data, the optimal clipping schedule can be found by maximizing the (CCC) at each time point. Inspired by this observation, we describe procedure which, given learning rate schedule for unclipped SGD, gives us a learning rate-clipping schedule pair which performs at least as well as unclipped SGD. We then provide a simple heuristic of this procedure, which experimentally achieves the same performance.
Consider a learning rate schedule rtt,, used to train unclipped SGD. We define the max-(CCC) clipping threshold schedule as follows: At step we first set the clipping threshold to
(R,)
c² (t) argmax.
(18)
no (Re)

---

Published as a conference paper at ICLR 2025
10P
Gau
2.5
Gau
Rad
Rad
Uni
2.0
Uni
Exp
Exp
CSC
10
CCC
1.5
1.0
10P
0.5
10
20
7.5
10.0
12.5
15.0
6
(a) The (CSC)
(b) The (CCC)
Figure 2: The (CSC) and (CCC) across various noise distributions: Gaussian (Gau), Rademacher- like (Rad), uniform [-M, .M] (Uni), and symmetrized exponential (Exp) noise. The (CSC) is computed with Rt = 3, o 9, 0.7; the (CCC) figure uses R = 3, = 5, 0.2 (where is parameter for Rademacher-like noise). Parameters chosen to illustrate different behaviours.
Given a clipping threshold c, we define compensated learning rate for clipped SGD by
ā((, c) mn(t)/He(B)).
(19)
Effectively, this learning rate compensates for the fact that clipping biases SGD against the gradient such that clipped SGD now has the instantaneous descent term unclipped SGD. We now choose 17* (t) = (t, e² (t)) as our learning rate. In Appendix C.I we provide plots of Equation (18) for various distributions.
This schedule will never underperform unclipped SGD. If the (CCC) is never satisfied we have (t) oo and 17" (t) rt),, recovering the original, unclipped SGD. However, if the (CCC) is satisfied at any time the max-(CCC) schedule will take advantage of this and provide improvements to optimization.
order to show this, we first have to solve for RG under anisotropic data. this setting, the risk is the sum of two parts: gradient flow term and an integrated correction term. The gradient flow term associated with the infinitesimal learning rate limit SGD. It decreases the risk and comes from solving the underlying problem. The correction term arises because the actual learning rate is not infinitesimal. encodes the errors made by SGD and increases the risk. Gradient flow is defined to be,
of = V ( dt,
(20)
with / = 0g. Then the gradient flow term is R( In Appendix G, we show R₂ with any learning rate (1) and clipping schedule c(l) solves
ā 1. ((())EC))) Tr(K2 -KT - oz 02/ddss
R₁ = R
(21)
where = (c(s) ds is the clipped integrated learning rate. The integral term in Equation (21) is the finite learning rate correction. The risk of unclipped SGD can be computed using c(t) oc:
R = R( + 2 % 2 - + +
(22)
where r, = S0 n(s)ds. This gives us the following theorem:
Theorem 4. Given SGD with learning rate schedule nt() and clipped SGD with learning and clip- ping schedules 17" (t) and c² (t), then Ry < RT. If there exists a t E [0,T] such that the (CCC) holds then Ry < RT. Conversely, pº (R)/ve(R) < 1 for all R > and 0, then for any learning and clipping schedules 17(t) and c(t), SGD with the compensated learning rate schedule ((()eet)) has R Rr.
8

---

Published as a conference paper at ICLR 2025
Proof. With these choices, the clipped risk (21) solves
RT = R( + d /
" r²(s)
Tr(K' (K( - + /2/dss.. Pd(s)
Vals)
(23)
Note that the gradient flow term is identical to that of unclipped SGD. Since the (CCC) is satisfied, the integrated correction term is larger than unclipped SGD and thus Rr Rg. If the (CCC)
occurs at some f, then in fact Ry < RT. For the converse, one substitutes the learning rate schedule into (22) and it smaller than (21).
We note that this result holds for any choice of the unclipped learning rate, even the optimal one. Therefore, if the (CCC) holds at some point along the optimal unclipped SGD trajectory then the benefits of gradient clipping cannot be matched by unclipped SGD.
Gau
Rad
Uni
Exp
Max CCC
10
100
0
10
Risk
Figure 3: The maximum over of the (CCC) for various values of the risk. Notice that the maximum value of the (CCC) for both uniform and Gaussian noise is 1, corresponding unclipped SGD. Plots are computed with a = 7, p = 0.5 where is parameter in the Rademacher-lik noise.
The following theorems give concrete examples of our results and apply in both the isotropic and anisotropic setting. We show that the (CCC) cannot be satisfied when the data are Gaussian. Then, we show that, as before, broadly distributed gradients can benefit from clipping (even with all finite moments). Both proofs straightforwardly apply the definitions of and Ve (Appendix F).
Theorem 5. Ifx (0, K) and o then (R))/vv < for all R, c 0.
Hence, in this case clipped SGD never improves over unclipped SGD (in the sense of Theorem 4). Theorem 6. Consider x NO, K) and the Rademacher-tike noise as described Theorem 3. Then, there is an r > 0 depending on and X so that when R, S there always exists c(t) such that the (CCC) is satisfied.
It is interesting to note that the (CSC) is automatically satisfied if the (CCC) is, implying that when gradient clipping improves SGD's performance, also enhances stability. This dual benefit suggests that in some settings clipping can be used to achieve both efficient and stable training.
5.3 A HEBUIISII FOR THE OPTIMAL CLIPPING SCHEDULE
When we consider the max- max-(ccc) clipping schedule light of our simplifications of μr and Ve (Equation (10a)) we arrive at simple heuristic for the max-(CCC) optimal clipping schedule itself. Using Equation (10a), we see that
2
12
R V. (Re)
(24)
K
KI
This suggests that the upper bound might be attained by using the clipping schedule where c(t) is proportional /2R, R2, o² along with the approximate compensated learning rate
e 22 o²
(t, 17(t) max (1, 1/k),
(25)

---

Published as a conference paper at ICLR 2025
where RR+ is single scalar which can be tuned. In Figure 4, we compare: unclipped SGD, clipped SGD using the max-(CCC) schedule and compensated learning rate, clipped SGD the heuris- tic schedules from Equation (25). To obtain the max-(cCC) schedule numerically optimize at each step in solving the ODE equation. In contrast, we tune only to obtain our heuristic schedules.
As expected, we see improvement by clipping for Gaussian noise (Figure 4a). In contrast, with Rademacher-like noise, clipping allows SGD to learn faster and reach a lower value of the risk (Figure 4b). Remarkably, the heuristic schedule obtains essentially identical performance as the op- timal schedule. We show that this heuristic is effective on Wikitex12 data for next-token prediction and explore stability to nyper-parameter changes Appendix C.4. This heuristic shows promising potential to improve the training of clipped SGD with minimal tuning effort, however, comprehen- sive evaluation left for future work as warrants a dedicated study to assess its effectiveness and generalizabiltty.
C-SGD Opt 80.0%
0.20-
C-SGD Opt 80.0% CI
0.200
C-SGD Ap. Opt.
C-SGD Ap. Opt. 80.0% CI
ee-SGD 80.0% CI
oc-SGD 80.0%
0.175
Opt ODE
0.15
Opt ODE
Ap. Opt. ODE
Ap. Opt. ODE
Risk
0.150
Unclpped ODE
Risk
Unclipped ODE
0.10
0.125
0.100
0.05
0.075
0.0
2.5
5.0
7.5 Iterations
10.0
12.5
15.0
0.00
0.0
2.5
5.0
7.5
10.0
12.5
15.0
Iterations
(a) Gaussian noise
(b) Rademacher-like noise
Figure 4: Results of clipped versus unclipped SGD under the setting of Theorem 4. We com- pare the optimal max-(CCC) to the heuristic schedule in Equation (25). Notice that clipping cannot improve SGD in the setting with Gaussian noise while noticeably improves performance with Rademacher-like noise. Moreover, the heuristic schedule and the optimal schedule perform very similarly. The unclipped learning rate constantly 7) 0.4 while a 0.8. We compare Gaussian and Rademacher-like like noise with 0.2. SGD is presented with 80% confidence intervals over 100 runs.
CONCLUSION
Our analysis of high-dimensional streaming settings shows that the effectiveness of clipping hinges on two key quantities: descent and variance reduction factors f4, and Ve. The structure of the noise, model, and data then determine the dynamics of pe. and v. for a given clipping threshold. This allows us to compare clipped SGD to unclipped SGD with learning rate and clipping schedules. Clipping can be beneficial in the setting of non-Gaussian noise; in certain noisy regimes, clipping helps filter noisy datapoints more than non-noisy ones. The key is that the gradient norm becomes a grrong-enoupe proxy for the "quality" of a datapoint, and can be used to effectively filter each point.
The local stability of clipped SGD depends on the ratio of Me to Ve, the (CSC). The maximum stable learning rate can be increased by clipping if clipping reduces the average square gradient norm more than the probability of clipping. This can be achieved for broad distributions of gradients. Similarly, clipping improves optimization if the ratio of 2r2 to V. exceeds the (CCC). This quantity informs when the tradeoff between biasing training against the gradient and reducing the variance pays off.
One future direction is to consider more complex models and losses. Exact risk curves have been derived in the unclipped SGD setting on more general losses (Collins-Woodfi et al., 2023); some of these results are likely adaptable to the clipped SGD setting. Additionally, important quantities from the analysis of high- -igheninnnii linear models can be measured in real networks (via linearization) and can be used to analyze learning dynamics (A (Agarwala & Pennington, 2024). We believe that the generalized versions of pe and v. will be interesting study in real networks.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We thank Lechao Xiao for his feedback on the clarity and accuracy of our work, which significantly improved the manuscript. We also extend our gratitude to Courtney Paquette for her proofreading and assistance in shaping the final draft.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016.
Atish Agarwala and Jeffrey Pennington. High dimensional analysis reveals conservative sharpening and a stochastic edge of stability. arXiv preprint arXiv:2404.19661, April 2024. doi: 10.48550/ ar04v.2404. 19261.
Atish Agarwala, Fabian Pedregosa, and Jeffrey Pennington. Second-order regression models exhibit progressive sharpening to the edge of stability. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 169-195, PMLR, 2023. URL https::tt//pptcc.tt htt.pp:://proceediggg. mlr press/v202/ agarwa a23b. html.
David Barrett and Benoit Dherin. Implicit gradient regularization. In International Conference on Learning Representations, 2021.
Xiangyi Chen, Steven Z. Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. In Advances Neural Information Processing Systems, 2020.
Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs the edge of stability. In International Conference on Learning Representations, 2021. URL https: //wpp///pppee.eee//////e/ee/eeee net/ forum? i d= faahhhhhrttteeeee
Elizabeth Collins-Woddfin and Elliot Paquette. High-dimensional limit of one-pass sgd on least squares. arXiv preprint arXiv:2304.068477 2023.
Elizabeth Collins- Woodfin, Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the High- Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index models. arXiv e-prints, art. arXiv:2308.088 08977, August 2023. doi: (0.48550/aXXi.23008.00m 08977.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255 2009. doi: 10. 109/CV/R.2009.5000000
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Associ- ationfor Computational Linguistics, 2019. URL https://p////.c.ctt /api. wwwanticschooeee.e...... .arr.orgg /org/ Corpus 52967399,
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1929, 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2015. URL https: /api......// semanti htt.oooo.....oooooooooooo//00//.

---

Published as a conference paper at ICLR 2025
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recogni- tion, pp. 770-778, 2016.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In Proceedings of the 40th International Con- ference on Machine Leurning, 2023.
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradi- ent algorithms. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2101-2110. 10. PMLR, 2017.
Stephan Mandt, Matthew D. Hoffman, and David M. Blei. A variational analysis of stochastic gradient algorithms, 2016.
Tomávs Mikolov. Statistical Language Models based on Neural Networks. PhD thesis, Brno Uni-
versity of Technology, 2012.
Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. of sgd in high-dimensions: Exact dynamics and generalization properties. arXiv preprint 0rXiv:2205.07066 2022.
Homogenization
Razvan Pascanu, Tomávs Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on Machine Learning, 2013.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2011.
Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, and Sanjiv Ku- mar. Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv: 190.::998.006600 2019.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy. Mip-mixer: An all-mip architecture for vision. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 24261-24272, 2021.
Roman Vershynin. high--Diensional Probability: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. In Advances in Neural Information Processing Systems, 2020a
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Pro- cessing Systems, volume 33, pp. 15383-15393. Curran Associates, Inc., 2020b.
12

---

Published as a conference paper at ICLR 2025
A FULL FORMULATION OF THEOREM WITH NON-GAUSSIAN DATA
To state the more general version Theorem 1, we require some additional technical assumptions. Along with all of the assumptions described in Section we will further assume:
Assumption 4. For some constant and any fixed 0 with ||0|| S. 1, we have 1x"Ollvs S and the data satisfy a Hanson- Hanson-Wrighe Wright inequality: for all 2 0 and any fixed matrix B,
BIKVKBB PIIKBBKK]] }): (26)
6
P( Bx Bx
Exx T Bx 2 1) S 2xxp
-iin
where K is the covariance of the data. Assumption 5. μ and v satisfy the following Lipschitz-like bounds for some constants Cy and Cv.
lm(x) m((v)l S C₁. IR(x) - R(()]
(27)
min, R(=)
((x))(t) s Cu 1+
[R(x) - R(y)
(28)
(R(x) + R(y)
where R is the risk.
We may now state our more general version of Theorem 1. Here we use .max c(t) and rj max, st)).
Theorem 7. There is constant C = =C(v (1+ and constant c = c(v) so that
for any S S cd
TR(O.) D(@x))
[R(O k/a) D(Oafa)
m/d
Cono (
sup OSkkn
< C
Cexp
ulog(d)dd-/2, (29)
with probability at least e- and provided the right hand side is less than 1. The coefficient can be bounded by
C C ((1 [[]]13) Vn/d)eexp exp (C (1 CL) max
for absolute conslant C > 0.
We note that when o = 0 (so there is no noise) we arrive at the simpler conclusion that
(R(O.) D(0))) - [ s/a) D(O
- (/2
sup O5k5n
We note also that if r)(s) 1), the risk will be bounded below by constant that depends only n, a with high probability (and provided there is no warm start), and hence again this coefficient can be bounded with high probability in similar way to C. Moreover, for any desired d-independent risk threshold Rg. if one makes sufficiently large, then with very high probability, two risk curves will agree up the point they cross below this risk threshold.
13

---

Published as a conference paper at ICLR 2025
B PROOF OF MAIN THEOREMS
In this section we prove both Theorem and Theorem 7.
B.1 PROOF OF THEOREM 1
In order to prove the version of our Theorem with Gaussian data, it suffices to check that Gaussians satisfy both Assumption 4 and
It is standard fact that the Hanson- Hanson-Wright inequality is satisfied for Gaussians Vershynin (2018).
Let standard Gaussian then recall from (9),
Pe ( IP( (xx 0 00) (c) 1 20) - S c).
(30)
(31)
With a slight abuse of notation, we condition on and use (e - C, + c) to express
I
I
(mo(01) - (o((2)]
2 E
2
(32)
(2)(01)
22 (0z)
c+c
c ++ E / ((()2)
S
P
6
(33)
(R(01))
+ P
2
C
c)
P
2
(34)
(R(O))
VR(02)
Without loss of generality, we assume c/R(02) S c e/R(O,), then the former term may be bounded by
c+c
P 2 C+C
IP 2
(35)
(R(O,)
/R(0z)
+ cl
(
VR(O,) (((22)
<
(36)
2 π
(R(0.)R(02))
Maximizing te -P/RR(0) t yields
IP 2
c+6
- (R(02)
PP 25
c+
8)
RR(0)) - -((22))((0))
(37)
(R(00))
2 2TTR(02) ( (R(02))
RR(01) - R(02)
(38)
min (0),0))) R2))
By applying the same argument the latter term of (34), we see that
(R(0,) R(02) (p())) m((2)l < Cp min (0,.00.)) R(2)'
(39)
desired.
14

---

Published as a conference paper at ICLR 2025
To show (28), let us first first define (() E clipp (Ez (62--e] [
Upon conditioning on e,
follows that (())(()) - (v2R(z). c).
Differentiating with respect to &, we see that
i (() E
(40)
(ote)/E
(5= - -e)ze 12 dz
(41)
V2T
(-cte)/E
==(ctc//E
-2
(f= c)e -/2 c)e-=112
+ 2EP (15= s(ce
(42)
V2T
x=(-ote)/E
-2
(c- + E)E -(0-0) + (c - (ote))
(43)
2t
+ 2 (IEz el S c)
(44)
12te 25
Upon noting that { absolute value of 2 c( by
< &C, for some absolute constant C may bound the
5V2T
f(. c) & 4CC + 2/c/.
(45)
ag
Hence, without loss of generality, if we assume that (2)(01) S (2)(02) and conditioning on e, we obtain
/22(
f(S, c) dg
(46)
(2R(01)
a
2c ((( R(02) + 2B|e| V (2R(0)) - 2R(00))
(47)
which completes the proof of (28).
B.2 PROOF OF THEOREM 7
We now prove the general version of our main result.
We simplify notation by studying the iterations U₁ 02 0- We shall also write n nkk/d) so that rn/d = Before proving theorem 7 we first show series of lemmas following closely the proof techniques of Collins-Woodfin & Paquette (2023).
Notation 1. It is helpful to formulate some results in terms of tensor products. We use x & to refer the tensor product of x and y..
Notation 2. We use C' refer to generic constant which may change from line to line.
With a slight abuse of notation, extend {rx J220 to be indexed by continuous time E R by ve uly-- Let q be quadratic. Via its Taylor expansion, may write the updates of by
ij Va(u)) clipeva((4xx+t)) + g(vu+1) - ((v)) = -d
nh (V2g, (clip (cip) (48)
2d
This update can be decomposed into errors, martingale parts and predictable parts
g(vx+1) - -((x)= = Th d ((u)) V Kv + (r( @
The (( (K
(49)
AM AMguad AFr-
Where we have martingale and error increments being contributed from both the linear and quadratic terms. The specific form of these terms may be seen in section B.3. We will relate these quadratics to
15

---

Published as a conference paper at ICLR 2025
manifold of functions which will close under the gradient and Hessian operations above. Choose this family functions to be
= R V2 E
(50)
where Ω is a circle of radius 2 and thus enclosing the eigenvalues of K. We further define the stopping time r for a parameter M.
== inf ( ||16|| 2 M) U (id: [V 2 M)
T
(51)
and the stopped processes,
UKAT
V = Ven(r/a)-
(52)
We will first prove Theorem 7 for the stopped process {ug h220 and (V7)220 and then bound the probability that T S n.
Lemma 1. There is an absolute constant C > O so that
sup oSeSn/d
1d(v%a)) 5
sup Osign/d
(IMTd + LM
Etaa + (MM
(53)
+ fmia
(Cmaxin n + CurR(s)(m, + + +2Cnn
sup gEQ
(q(v q(V])) ds, (54)
m,
where m, is sum of risks m, 1000-VR((00 + R(OO..))
Proof. When context is clear, we will write R(2; K) = R(=). We begin by noting that for all E Q
since for eigenvalues and eigenvectors (A,, wi) of K.
V Ku
Σ (A:-2) (u, wi)
$ (0,, (K, 222).
The same bound holds for the gradient term, and we conclude that for all g E Q
VV(c) Kel S +0))+
Given a E Q, by (49), we obtain
(00)=g((m %-' (?(s)
" / (s())) v(UT)P(u)) Tr(KV ((C)P()))T((V'')))) g)ds (55)
de
+ Mi Kn + +M MM.quad + E7.
Similarly, by Itô's lemma
((V7) = 9V(V) - ((V))(V))V)((V)) TKV
(56)
+ 1% (2(())
d U(VT) Tr(V29))d g)ds + M..SDE
where
( (s>))
MR SDD
VI(VT)T (2Ku(V))P(V) JdB.
(57)
Vd
First, will show that for any g E Q and any 32 Rd
16

---

Published as a conference paper at ICLR 2025
(g(21) Vi((22) (Kr)) I 4 sup (9(x1) - g(z2)l.
(58)
sEQ
The statement is obvious if g(x) = g(x). If g()) Va(r)" R(2) then Vg(x) = v2q1((z0x +
R(z)Vq( and using Cauchy's integral formula we see,
Vg(x)*<x = x" R(2) Vq(z))
(59)
1 Vq(x)"((2)xd)
2 p yo T ((z))
Vq(x)" R(2)xdz + [Vq(x) "oo(x)"R)) R(2).
2Ti jQ
Tg
(60)
For any on S2 we have that [|((2))lop V 1. Furthermore, the arc-length of Q is St. Therefore, we have
f 2x Jo
dy
(61)
s sup (g((1)) g(>2)), gEQ
(62)
and
- of
[2(x1) - T2(x2)
(63)
2T In
s sup (g(2)) g(x2)) gEQ
(64)
If g((()) x- R())V2 then using the identity R(=)K = I+ =R(=)).
Vo(x) xf R(y) zx" R(y)V 222) yx² R()))r)
(65)
By the same methods above,
[Vg(z))"Kz - Vg(x2)" Kx2l S 24 sup (g(x1) - g(x2))-
(66)
gEQ
It is simple to account for the presence of the functions y and v. Using Assumptions 5
((VT)) S sup (g(vTa) - s(V7)) C (m, + o)
(67)
gEQ
As for p. adding and subtracting (VVTa)9 (VH)) using μ and g(V,)) < (R(O),)
Iu(o(al(ooaa) - - (VTT))(V)) sup (g(v(a) - s(VT)) (1+ min (Rin
C,2
(68)
geQ
Note could have also added and subtracted y (v) and so picking whichever is better, arrive at
(u(oia)((tla) (VVV))(VV)1 S sup (g(()))) (VV +20,).
sEQ
This completes the claim.
17

---

Published as a conference paper at ICLR 2025
Lemma 2. There is an absolute constant C 0 so that for any quadratic q with ||q||c I 1 any
n S dT with T 2 1, any 1 S u S d,
sup l0sksn
My
1 SCVTT(( 2
(69)
MT-quad OSkSn
sup
< <CVTT, 1/2u,
(70)
sup E OSkknn
C + M)
(71)
sup ogiSn/d
M. M..DDE
(72)
with probability at least 1 1-
The proof of lemma 2 is deferred appendix B.3.
Lemma 3. There is an absolute constant C >> O so that for any m >> O, there exists Q S Q with [Q] S Cdsmm such that for all q E Q, there is some q E Q that satisfies ||q gllc= I d 2m
Proof. With assumption 2, the length of Ω is fixed independent of d. Thus, may construct Q by restricting Q to minimal d-2m-nnet of Ω
The proof of Theorem 7 now follows easily from these results. By Lemmas and 2, there is an absolute constant C' so that for any u 2
(Q(v(a) ((V7) CVTTO' () (2+ + +["²
C. max la(v%a) - g(V(") dss, neQ
(73)
event of probability least 1 - e and where have set
E, = (Cmax(m. (7 Cun + + +2C,m)
m
Then, from Lemma 3 with m 1 and increasing the absolute constant so that for all f S T
sup (4((()))) s 2 (2+ + + TEQ except event of probability C An application of Gronwall's 's incquality gives
//'
L. max -V REQ
(74)
sup sup (q(v(a)) q(V(7) CVT (2+ VVT exp Sh (ddss) (75) vEQ O
Now note that by contour integration, both the risk (K, 022) and suboptimality v ||0||2 both can be estimated by
max{|l107 1 - O,a 221121.21R(005 R( S sup (q(vTa) ((V,)),,
gEQ
proving our claim for the stopped processes. Now, will be shown that with overwhelming does not occur for < dT'. It suffices to show that following lemma.
Lemma 4. There is an absolute constant C > 0 so that for all r 2 0 and all T 2 0 with probability
at least - 2c - for all () < s $<> T,
V2
-C 3s " 1T/
e max +o
(76)
Vol
18

---

Published as a conference paper at ICLR 2025
Proof. Consider (VV) log(1 + [[v]ll)) Then,
(((e)) VP(V)) V,dt+ P(((I)(V))(( Tr(K) dt
di((V) 2n(t); 1+ |V
1+ 11V d
(77)
21, (V)(()) (V, 8 V., dt+ + (n(() 2 (VVV)()V) vd(1+ [IV
(V., VdB,
d(1 + []]
Note that, Tr(K)/d | so the drift terms are all bounded above and below by absolute constants multiplied by max T Meanwhile, the quadratic variation is bounded by
(p(V))) f 8 (s)
vVV.)P(V.) (V. V. K)
13 ds
(78)
2 8C " d t
(79)
for C' an absolute constant.
And so, for all 0, setting f(t) be the integrated drift terms from (77)
PP max ISST (vV) f(4) > CtNTT/Vrr) < 2exp(-r?
(80)
This implies the claim immediately as f(t) S C m. T/ }t for all t.
We can now conclude the main theorem, noting that if for some fixed T, we pick M that
(2 + M)² = max C(1 C(1++ (161)) exp (f(c& Css
(2+ (2+2)2
then with probability at least 1- e-d - ||Vill remains below M up time T. As single steps of clipped SGD cannot increase the norm of U3 by more than factor of 2 (with probability at least e e-od), we conclude that if < Td, using (75)
exp (f, Eads) ((s))s))
2 = 110-11² < 4(77 + 4CVTToOP
Provided 2 and provided that
ACVTT702 (fu+ exp (f" Egde) (gll)) d 1/1/2 8
(81)
we have
M < 4(M²2² A12
hence we conclude that
M V8M
So if we pick M larger than V8M (which is larger than 2 by how M was picked) we conclude that
т Td.
B.3 BOUNDING MARTINGALES AND ERRORS
Lemma 5. Martingale Bernstein inequality For {M& martingale, we define
Tk.p inf(l> 0: Elexp(|Ms M 23.
(82)
then there exists absolute constant C O such that for all > 0
min ['maxonn '' oz , })
12
JM - E(Moll >t) < 2exp ISKSN
sup
(83)
19

---

Published as a conference paper at ICLR 2025
This section is dedicated to bounding the martingale and error terms present in Equations (55) and (56). These terms are
AM Vg(u))² dip.aallexex/ + The Vg(vE) E/clip aalleaa
(84)
i =- Volot)" clipeva((xxat1)
f Vg(uT) KoZu(oT) AE
(85)
d
and
T.M-uudd k+1
(v ((xx)e++))))))
02
(V²q,
E.
cclioova )21)
(86)
2d²
2d
1
(V q, clip (xxx++))) 122)
7 d
K,
v(U (P AF
(87)
2d
where we recall 4 (x*+1, ) c++1. The error increment has contributions from both the linear-in 7i- and quadratic terms. More precisely,
A A AF A A
A
(88)
where
AE
1ik (g(OT) "/ Xk+1 c4x)
and
AE AET-QuE ququa
E
(V
q.
22 le Wesdd - (V K)) E ( makise)))
2d
B.4 MARTINGALE FOR THE LINEAR TERMS
We'll llll begin the proof for the linear terms in the increments. First, note that using the ||glic norm we can bound
[Vq(=)] ||| [Vv( < |lllcc=1 ||=|])-
(89)
Thus,
(r(u))"K'p((r)) < (1 M).
(90)
From Equation (134) in the following section, for an absolute constant C > 0
A Fr.lin < C(2 + 7
(91)
Meanwhile, we can get subexponential bounds for the former terms of (85),
t " c(ipaa((4x6441==-- (a(o)))xxx1ee Xx+1 Ev Iexxe
nh
Va(U))
(92)
d
d
cì
(x30+1 [1 b Dova
(93)
So, by Assumptions I and 4, as well as Equation (89), we have
Va(uE) Tx- Xx- pexeeee
< Vg(oo) xi+ 1x411x1le
(94)
< Vg(07) )² "xc+1 llve 1
(95)
(1 + M)e (2 + M).
(96)
20

---

Published as a conference paper at ICLR 2025
Likewise,
lovavoloi 6xx0+1 |1xx0+1l|
s V eex++1 11x
(97)
S
(98)
(2 M)
(99)
Thus, for some absolute constant C' 0
2 (I++))
T = inf (t> 0: Elexp( (i /1
(100)
for all k. Hence once vd may further bound away this additional fraction incurring further loss of a factor of We may apply Lemma 5 to see that for all > 1, and some absolute constant
0
sup
IM BIM > 17(2 + ( s 2xp (-en min {L,t)).
(101)
IskSn
In the case that n S df', this implies that there is an absolute constant so that for any 1 S u S d
M S CTi(2 + M) VT
sup 15k5
(102)
Vd
with probability at least exp(-u).
B.5 MARTINGALE FOR THE QUADRATIC TERMS
We write
T.quad k+1
=
2n
(
clip cl.pceee((4xxx-1) 02)
2d
ink
<v²g, E (211)))
(103)
= Ti + T2,
(104)
where
Ti =
7
V x.22 221)
E2 ae 1ox.k11?see 1135020 -E -E
TJk
(
82 x
(105)
2d
2d
Notice that
(v x21) 1 all Sodd
S gll
(106)
so that
[Ti S e
(107)
As for T2.
To
c
V2g.
Xb+1
621
1 1P2od
2d
|
(108)
E
?
V2g
X6+1
|e Fr.
2d
|
Similarly,
c2
2d
42g.
[
Xk+1
5
702
2d
(109)
So that overall,
21702
AM I.quad b+1
AM
<
(110)
d
21

---

Published as a conference paper at ICLR 2025
for all k. Then, by Lemma 5 we have for t 2 1
sup Isksn |M [MT-quad - EMMM
MMM--ddd 277c - 2ex (-cn min (i,
(111)
Hence we conclude that for some absolute constant and all 1 S Sd
VT
sup 15k
M
I CTc
Vd u
(112)
with probability at least - exp(-u))
B.6
MARTINGALE FOR THE SDE
Recall equation (57)
TT(8) 2VVVV VKdB..
M SDE
(113)
vd
We may compute the quadratic variation of M,
MR.SDE as
(M [ "(""V:))00"""""""((("
(114)
using (89) we see that
(MTSDE)) - (1+
(115)
so that
sup 0SET
(MT.SDE), - Cird (1
(116)
then using the sub- Gaussians tail bound for continuous martingales with bounded quadratic variation gives for
IP
sup
M
t
SDE
CT7(1 + M) M)VVVu/VV 2exp (-u²)
(117)
OS$ST
so that increasing the absolute constant C 0 as needed, for all
Cn((1 M)² VT
M SDE
sup
Vd"
(118)
021ST
with probability at least exp(-u).
B.7 BOUNDING THE ERROR TERMS
The remaining technical difficulty is in bounding the error terms. We will first focus the linear error term.
B.7.1
LINEAR ERROR TERMS
A Er.lin
7h
Bleie (xk+11()) xx+1 (f&)
(119)
d
7
(E [X++ I xx+1 le (
(120)
c Vd
X4+1 sgn((x)
X4+1 sgn(Ex)
Vq(uk) (Q(U))=E TE
L TrKK)
(121)
|xx++|||
TTi(K)
The B[Da].
(122)
22

---

Published as a conference paper at ICLR 2025
For clarity, we will write Vg(uE) as Vgk. We see that
0,
x 2 S ed and Tr() S edd
oV 1
VgL. Xx+1
x 12 1 e'd and l Tr(K) d'd.
(r()))T(K))
D₂
OV evava 11
Vqk. Xx+11xl
L +| 2 ed and l Tr(K) s dd.
and
(123)
ovdVg |
oV xxiia 1h4
+ e²d and l Tr(K) > ddd.
Tr())
Now, considering each case, we see that:
When fg x 2 c²d and lg Tr(K) > cdd, we have
cvd
D& = V4l Xx+ 1c
1
(124)
Ne (T(K)
1 ||x++al|
Volk X Eal
(125)
(Tr(K)
When G11x+111 cdd and & Tr(K) S ddd, we have
cvd
Da = V X6tl
(126)
[4 X
||*++|||
I Vo x6+1
(127)
/Tr(K)
When (1|x++1 > e'd and lz Tr(K) edd
D&l x
cvd [6 |x++1|
1
(128)
VTr(K)
||xx+1l| Il VTr(K)
Vg
(129)
Now using the numerical inequality 1 1- >/2/// > 11 11-29 22 > max (2),
(1
||x++1|| || (T((K)
| || TrK
P
>1) S
max
(130)
Since, by assumption Tr(K) d, and using Assumption 4 we see that, setting = max (2)
|xx++|| Ill (T(
>1) < ([Tr(K) - ||x++ 11
ds)
(131)
d=
ds
1):
< 2
min
(132)
| K 1
02 |
Since K| d, we conclude that for all u >
|x
IP
> ou
< 2exp (-du?)
(133)
Tr(K)
23

---

Published as a conference paper at ICLR 2025
The term X fx] has second moment bounded by (compare with (96))
EJ V x - C(2 + M)
for absolute constant C > 0, and hence conclude for absolute constant C > 0
A Iin
- C22 + md
(134)
Thus, taking dT steps, we get
E S CTTT0" (2 M/2 ugkgn
max
(135)
B.7.2 QUADRATIC ERROR TERMS
This follows similar path as the linear terms. We again express
A
AErquad
AE
ii
[E
( V2 q,
x k+1/
Le
(Vig, K) E [ macksced))
(136)
2d
Ī/ 2
(24g q. x 82
(V K)
k++1/
1 11xxx_11 120od
P(t > 2d) (137)
2d
|| |xt+1| 1|
KrK
ni
[DD]] 2d
(138)
with
1/ (V q, x x+11
(V K) f2 mrksaad
(139)
(V'g. 9.
X 82
1P dd (''q, K)
+ 2d
x+1/
1 mikssed
(140)
| 1
Tr(K)
4 ((V2g q. x x22 - (V22 K))
( 2 < edd and & Tr(K) S edd,
l c²d (V',.)
(V'g, q. x 02
f1|xa+112 edd and & Tr(K) > dd.
k+1
Ti(K)
(141)
od
9
2 q, K)
lg
6||x++112 > and and & (K) s ddd
|x111||
Ed (F21x221)
82
(v2gkK) Tr(K)
111L XL41
11|x++112 > odd and e (r) > ddd.
Consider the function by cases. On Eg Xx+1 ||2 S cdd and TT(K) > o²d we have
V q, x 02 E 2d (v),
(142)
Tr(K)
4 (VV q, x 02 (V'g. K + (V 9)KK ( Tr(K) )
(143)
4
s ( q 221) - (V K) + (v K)
[T((K) - ||1x+111 12
(144)
2dd
Similarly, if x 2| > od d and Tr(K) ed
2d V q, 32
x+11 - <V²g,K) 4
(145)
|x 11
2d
2d
|xx+1|12 1 ((V2 x - (V2 K)) + (VV2g, K)
[Tx++1|
2
(146)
4
(v²s 4, x 02 - k) + (V2 k)
[T(KK- - ||xx+ 1|21
(147)
cd
24

---

Published as a conference paper at ICLR 2025
and finally when x 1|? > cdd and and l
Tr(K)
c²d we have
(V2g, (V2,,x271 x
(V K)
2d
S < 22 <V)..))
(148)
|
Tr(K)
+(V2g, K) ed Tr(K) | de ((K)s (149)
So overall,
4 c²d
DI S S V
( (V K)
(T(K) - |xx+1||1| le Tr(K)sead (150)
Now, we may use the Hanson-Wright inequality (Assumption 4) along with the inequality
||VV2 TvKK2<vKj' K S TT(K)|VV') Tr(K) = d
(151)
see that for all 20
min {12 12
P q (
- K) > w²) S 2exp
d.11)
(152)
We also recall from (132) that
P [1] to²) exp (-min {
t2
(7.1)
Hence overall, we conclude that for some absolute constant C'> >
+1
So that overall
A k
quad
< Croo 2/2
(153)
and summing over & S n S Td,
max 0Sksn
gr.quad
k
<
(154)
This completes the proof of Lemma 2.
C ADDITIONAL EXPERIMENTS AND SUPPLEMENTARY FIGURES
C.1 STUDENT-T DISTRIBUTED NOISE
Here, we examine the influence of heavy-tailed noise on the (CSC) and (CCC) using the Student-t family of distributions.
The Student-t distribution, characterized by its degrees of freedom (df) parameter, allows us to explore continuum of tail behaviors. As the degrees of freedom decrease, the distribution becomes more heavy-tailed, ranging from the Cauchy distribution (df 1) to the Gaussian distribution as df approaches infinity.
To better understand how varying tail behaviors affect the dynamics of clipped SGD, we generate plots of these thresholds the degrees of freedom parameter changes. These results are in Figure 5.
As df increases, so to do values of the (CSC) and (CCC) ratios. This is unsurprising as the distribution becomes more heavy-tailed.
25

---

Published as a conference paper at ICLR 2025
d150
d150
3.0
df10
df10
d15
d15
2.5
d
df2.5
d12.1
d12.1
CSC
10
CCO
2.0
1.5
1.0
10P
0.0
2.5
5.0
7.5
10.0
15.0
5.0
7.5
10.0
12.5
15.0
Figure 5: The CSC and CCC where the noise is Student-t distributed. We hold the variance fixed and vary the offrreesof--rredom (DOF) parameter. Notice how for high DOF, the thresolds resemble Gaussian behaviour (compare to Figure 2 in the main paper). Meanwhile for small DOF, see that both the CSC and CCC are high, suggesting clipping particularly effective. This reflects the heavy-tailed behaviour of the small DOF Student-t distribution.
C.2 MEASURING μr AND REAL NETWORKS
We can estimate μ and v in the non-linear setting as well. Even though C-HSGD does not fully capture the dynamics in this regime, computing estimates of μ and may give useful information about how to apply clipping schedules. Given a loss function L(0) induced by some non-linear model (0), the generalization of Equation is given by
|E[clip (VoC)ll E Voll
( Ell|clip, (VoC))
(0
and
(155)
Vo
Here the averages across sampled minibatches. These forms be derived from the original calculation by making the substitution x + J, where is the Jacobian 80
dx
The numerator and denominator be estimated online using running average (e.g. exponential moving average) updated after every C-SGD step. This does not require any additional backprop-
agation steps, but does require keeping 2 extra running averages in the shape of 0 to compute pe- However, we use the form of He from Equation 9, adapted as
(o( V s c]
(156)
(that is, the probability of unelipped gradients), no additional memory computation is efficient.
incurred and the
We used this estimator compute yu and for ResNet18 and VIT S/16 trained on CIFARIO (Figure 6, left column). The models were trained without clipping, and μ and y were computed using different clipping values c. With larger clipping threshold of c 10, gradients are rarely clipped and putt) 2 vt) z 1; there is non-trivial dynamics for smaller clipping strength. We also computed the (CSC) and (CCC) for the different thresholds (Figure 6, right column). For ResNet18, the (CCC) is above for the smaller thresholds; if the theory holds, then clipping is beneficial here. In contrast, for ViT remains or below and clipping would not help.
Further investigation is needed to understand the utility of using μ and in the non-linear setting; the two main obstacles are the fidelity of the H-CSGD approximation and, relatedly, the question of whether or not the max-(CCC) is strictly better than the unclipped schedule in the non-linear setting. Non-convex optimization can often have more effects which depend on the whole training trajectory; the form of the H-CSGD dynamics in the linear setting allowed to largely ignore these with the appropriate choice of μ and v. We leave the exploration and development of practical applications of yu and to set joint learning rate and clipping schedules future work.
26

---

Published as a conference paper at ICLR 2025
ResNet18
ResNet18
1.0
1.0
0.8-
0.8
0.5-
0.6
1.00
CSC
10.00
0.4
CCC
0.2
Mmm
0.10
<= 1.00
0.0
0.0
0
50
100
150
200
0
50
100
150
200
Epochs
Epochs
VIT S/16
VIT S/16
0.8
0.8
0.4
CSC
0.4
10.00
c- 1.00
e- 10.00
0.0
50
100
150
200
100
150
200
Epochs
Epochs
Figure 6: Jr, v, CSC and CCC for the realistic models of Appendix C (ResNet18 and ViT) trained on CIFARIO. μ and were computed using Equations 155 and the additional approximation from Equation 156. μ and y computed for three log-spaced clipping thresholds. Our theory suggests that ResNet may benefit from clipping, but ViT this setting does not.
C.3 MEASURING THE INTRINSIC DIMENSION IN REAL NETWORKS
Recall that the intrinsic dimension is defined in terms of the spectrum of K:
== Tr(K) |
We can extend the definition of the intrinsic dimension to the non-linear setting by considering a linearization of the dynamics. Given loss function C(z) and model z(0) on parameters 0, the Gauss Newton matrix G of the loss is defined by:
G == Voz V.LV
(157)
Here Voz is the model Jacobian, and V2.C is the Hessian of the loss with respect the model outputs. G encodes the second derivative the loss with respect to a linearized model ž = z(0,) + (ez(0-0m))
For linear model on MSE loss (as we studied in the main text), we have K = G. If we took non-linear model during training, and locally linearized the model and loss, we would measure the intrinsic dimension with G as well. Therefore, on non-linear models, we will define
d,i = TrGG)/I|
(158)
as the non-linear intrinsic dimension.
With this definition, we can measure the intrinsic dimension on neural network models during train- ing. We measured d on ResNet18 He al. (2016) and ViT S/16 Dosovitskiy et al. (2020) for networks trained on CIFARIO using MSE loss (Figure 7). We see that for ResNet18, d increases from 100 to 10², while for VIT d stays steady at 300. In both cases d, large, but it is very model dependent.
This suggests that real neural network models are in the effectively digensinnn regime; leave to future work the question which concepts from the basic theory generalize to the non- linear setting.
27

---

Published as a conference paper at ICLR 2025
Intrinsic Dimension
10*
10F
ResNet18 ViT S/16
100
150
Epochs
Figure 7: Non-linear intrinsic dimension dny for models trained on MSE loss. For ResNet18 (blue), d,y increases by factor of 10 over training, while for VIT S/16 (orange) d remains relatively constant.
C.4 FURTHER EXPERIMENTS WITH THE HBURISTIC CLIPPING SCHEDULE
In this section we showcase some preliminary results investigating the proposed heuristic optimal clipping schedule given in Section 5.3. Note that full investigation of the heuristic optimal clipping schedule across many datasets and in differing models is beyond the scope this paper.
C.4.1 HEURISTIC CLIPPING SCHEDULE, ON REAL DATA
In this section we showcase some results on applying the heuristically optimal learning rate schedule for real datasets, namely the Wikitext2 dataset for next-token prediction. For experimental details on how the dataset was embedded and key quantities were estimated see Appendix H. full inves- tigation into the efficacy of this heuristic schedule will require extensive experimentation which is beyond the scope this work. Here we simply provide evidence that the schedule and heuristics are effective even in real world conditions.
1.00
CCC (for WikiText GMM)
0.95
0.90
0.85
Risk
0.80
10
0.75
oc- xGD 80.0% CI
C-SGD Ap. Opt. 80.0% Cl
0.70
Ap. Opt. ODE
Unclipped ODE
0.65
10
15
10 Iterations
102
10a
Figure 8: We train linear model using the heuristic optimal clipping and learning rate schedules given in Section 5.3. The (CCC) is given in the left hand figure. Note that the optimal clipping in this scenario is not clip. This captured by the heuristic optimal. fact, heuristic optimal actually performs slightly better due to imperfectly compensating the learning rate.
C.4.2 INSENSITIVITY TO THE TUNED CONSTANT
Here we investigate the sensitivity of the heuristic clipping schedule to the tuned parammeer In Figure we first find the optimal through simple grid search. To investigate the sensitivity, we then run clipped SGD with the heuristic schedule with both 1.5k and x/2. Despite the relatively large change in the syper-parameter observe relatively small stray from the behaviour under
28

---

Published as a conference paper at ICLR 2025
0.20
Unclioped ODE
0.20
Unclppped ODE
Opt ODE
Opt ODE
Ap. Opt. ODE
Ap. Opt ODE
Sensiliity range
0.15
Senstiitty range
Risk
Risk
0.10
0.05
0.08
0.0
7.5
10.0
12.5
15.0
0.0
5.0
7.5
10.0
12.5
15.0
Iterations
Iterations
Figure 9: Sensitivity experiment the heuristic clipping schedule (Equation (25) to changes optimal Here the sensitivity range gives the values when with 1.5x and k/2.
D SOME EXAMPLES OF μ AND V
In this section we give some examples of f and defined in equation (7) under various common distributions. First, we will describe how to define and Ve functions of the risk.
Notice that, with Gaussian data, to law /2R(0) c where & standard Gaussian. Thus we can define jı and 50 such that
2 e)x|l
(O e)] ()O)) E[(v/R((,){ - -c)2
7 (
(159)
[ 2 x)x]l
and (de (..) ()( and (O,) (),)))) In what follows R((0) for some O In the following examples, we will simplify notation and simply let R(O,) = r.
D.1 GAUSSIAN DATA AND GAUSSIAN NOISE
Consider a ~ (O, K) and 6 ~ N(O, o²). First define
F(z) erf
2
V
2
2212
(160)
Then, have
me(r) = erf
(Vi(r+ 02
(161)
(2r (2r + ( = Fr
2 + cafe arfe
(162)
A[r + 12/22)
D.2 GAUSSIAN DATA AND RADEMACHER-LIKE NOISE
with probability 4/2
0
with probability 1 1-
(163)
with probability 4/2
Note that o² Var(e) = 22g. For some standard Gaussian random variable 2, μ and y may be computed
29

---

Published as a conference paper at ICLR 2025
c
c
Me(r) = qpp
1z A -
+ (1 - q)
|z| 2r
(164)
2r
c A
c 1
erf
+ erf
+ - q) erf
(165)
2
4r
vrr
4r
(2r - - = 2r 2
F
c A
+ F
c+
+ + q)
c
(166)
22
22r
22
91
(c+ X)2
(c- [c- 1)2
exp
exp
(167)
VT
2r
2r
c+A A V4r
erf
erf
(168)
Vrr
qe
erfe
c
+
erfe
(c+ A
(1
q)P
c
(169)
V2r
/2r
22
D.3 GAUSSIAN DATA AND UNIFORM NOISE
For N(0, K) and uniform noise supported on [-M, M] we have 0² = M2/3 and
1
4r (e (e=- -11
(e(r) 2M
(170)
1
2 (M-c)erfe
(c- M 4rr
(c+ + M) erfc
(c+M
(171)
2M
/4r
-1
M3² 4r
4r (-c² + cM - M - 4r + cc cM + M² M2 + 4r)
(2r + d²))((r)=
6M
(172)
cc-M)
1
c (C+M
M
(c3
M3
erl 66Mr) erf
+
(c3 + M3 + +6Mr erf
6M
44r
6M
V4r
(173)
E
(etar12
(e=
-1)
ok
202
(174)
2M
(c-M
M-MM
(c+ M
(M-
erfe
+ (c+ M) erfe
(175)
2M
4rr
44r
D.4 GAUSSIAN DATA AND SYMMETRIC EXPONENTIAL NOISE
For a N(0, K) and symmetric exponential noise, also known Laplacian, with density
f(x) de -1=12 /2
(176)
then we have
(e(r) 2erl
(177)
V2222
(222022011/2 erf ((o->r²) 2ed erf (le+
1)/2
(178)
V2r²
30

---

Published as a conference paper at ICLR 2025
Then, if Tx(r) satisfies
(8 (8+4222)TG) = 26 2ed + c22)) - 2e 20+ 222 + 2cd + +22)
(179)
- के X2 /2r2 + +222 +2A
C
1)
(180)
V2p²
+ + erf
c
(181)
V2
22 2cd + +x2 erf
c- C-
(182)
V2r²2
c c Ar²
20-12044--3/2222 - - c2 erf
(183)
22
have
ve(r) + (((()))))(o))))
(184)
E SIMPLIFICATION OF AND V
Theorem 8. Let X N(0, K) and let the noise be are for a fixed random variable and a > O.
Assume that the characteristic function of e, :p(() = RB]ett]] is integrable. This assumption implies that has continuous density gly). We will additionally assume that g(0) > 0.
Then, there exist absolute constants K4, Ku depending on the distribution of the noise (but not σ) such that,
Kit min (1. + d2 S (c(R) K. min (1, /2R + 0e
(185)
Proof. We first complete the upper bound. Let N(0, 1). Notice that to /2R(0)g Thus,
(0 P((co < <).
(186)
Going forward, we omit the dependence on for clarity. Let f be the density of f. Then, by the Fourier inversion theorem
/ c izt RR²
f(x)
p(ot)dt
2T
(187)
| { RI?
< 2m
(o(ot)ld
where sp(t) is the characteristic function of Now consider cases: when 2R 2 o²,
1
f(x) <
lp(t)
2Ta
(188)
< π -1/2 1/2
V2R + 0
Meanwhile, o < 2R
31

---

Published as a conference paper at ICLR 2025
2TT / E-Ri -Rii (s(())dt I J (p(t)ddt
_
f(x) -
(189)
22T
Va² 2R
By assumption, / (t) < oo and while depends on the noise distribution does not depend on the variance/scale parameter a. Since,
Me = S f(z)dz,
(190)
putting the two cases together completes the bound.
We now proceed with the lower bound. Let A 2 and again consider cases. First, let Ac and /2R Ac for some A. Then,
Pe = P(lée) I c)
PP(V2Rg + oel c)
(191)
2 P([g) 5 1//2A)/((e| & 1/2A) KA 0.
Where KA bounded away from by assumption. And so,
(1, V02 2R
Me 2 KA min
(192)
Now for the remaining cases. We can express by integrating over the density of to Let L represent the law of ac. Then,
E (x+u)) ( /aR (LCd))))) dæ.
dC(y)
(193)
ATR. -C
Consider the case where V2R Ac and /2R > o. Then,
1
1/A
(x+400))//00 /4RR (y)
Me 2
V -1/A
(194)
4me- 1//84
2 min
1,
V2R+ 12R+0*
AV
where we may lower bound the integrand since ((x + // < 1/2A over the rectangle (zz y) [-c,c] x 1-1/A, 1/A]. Similarly, consider the /2R and Ac. Then,
V2Ry
Pe 2
dy dz
2
2T
-1/A
1/A
(195)
4me 4me-1/24 1/2A3
min
1,
1, /2R
Av2n 2m
Choosing K4 min (KA,
41/0a Av
completes the proof.
Corollary 1. In the same setting as Theorem
(1, 1122R-0 +
à²
S ( & Kr min (1, 22 + oz
à
Ki min
(196)
32

---

Published as a conference paper at ICLR 2025
Proof. is trivially less than or equal to 1. Recall the definition,
1
Ve(R)=
(E [ [elssa] + +1 - -mo))
2R + o² 2R o²
(197)
c²
which gives the upper bound with coefficient Now for the lower bound. We can write,
1
(L p(G2 tolse t) c² no)
V6
2R 02
1
P(C 2 ()dd+ 21 2 mo)
(198)
2R 6²
2
2(1
2R + 0²
So now use the Me bound derived above to obtain the desired bound for
F PROOF OF STABILITY AND EFFECTIVENESS THEOREMS
F.1 PROOF OF THEOREM 2
To see there exists c > such that (CSC) holds, it is simpler to work with the inverse of the ratio.
We remark that
1115 + e (11p))
Ve = lim
lim c+ Pe
(199)
c->0+
P([e| c)
P([| c) J
(dP+ c3 P(C S c))
lim -+0+
(200)
P(Ie Sc)
lim c-0+ P(L) S c) JA C d
à
(201)
P(L <c)
Therefore, it suffices to show that (201) is less than 1. Indeed, the former term converges to 0 by the Lebesgue-Differrnttttin Differentiation Theorem. For the latter, let us assume that ~ x for some probability- measure Given that x NO0, K), let denote to be the (Gaussian) density of (x, 0 0*). It follows that
P[[e] S = PP-c+ (x, 5c)
(202)
1 /e cte
f(x) dx dT
(203)
-tc
Differentiating with respect to yields,
de (oafe c+e
d
f(x) dr do = f(c+t)+
(204)
By L'Hôpital's rule, the latter term of (201) becomes
2c
lim c P([
lim +
(205)
< <))
J3 f(c c) f(-c+
2c
lim
(206)
+
Jp 2f(e) di((e)
0.
(207)
33

---

Published as a conference paper at ICLR 2025
F.2 PROOF OF THEOREM 3
First, notice that o² = =q².. In the limit as [Rel + 0 we have,
((Re) P([d S c)
(208)
[1 c
(209)
[1 - x>c
Asc
v(()) 12122 o>y
(210)
thus
14 R2) 1
A<c
(211)
v (Re)
((Rs)
> 1
c< ((1-g) -
(212)
v (Re))
1 (R,)
$
V(I- (1-9)A_cs)
(213)
v (R))
thus c may always be chosen such that the (CSC) is less than 1.
F.3 PROOF OF THEOREM 5
With and v given by equations (161) and (162) we have that
(Re) <1
lim c+0 vRR))
(214)
Meanwhile, it can be seen that for all R. 0 /2 (R)) uel (R.) is increasing and continuous in Since,
(Ra)
lim
1
(215)
c00 v(Re)
we are done.
F.4 PROOF OF THEOREM 6
In light of Section F.2 above, we see that
(c(
A<c
(216)
(Re)
Me (R,)2
>
c< c<(1-9)
(217)
(Re)
Me (Ra)²
51
(1 -
(218)
ve(
thus may always be chosen such that the (CCC) holds.
34

---

Published as a conference paper at ICLR 2025
G THE RISK UNDER ANISOTROPIC DATA
In this section, we describe how to use equation (12) to solve for the risk. First, define
(z z R(z; K)z/2,
(219)
where R(2; K) (K -=1)=1 the resolvent of K. Using Itö's Lemma and the resolvent identity (K( =2) I.
(q,()r) = -- ntt) (Io,, 1- + +2gg. Ma(t) (R(O)))dt
(t)
(220)
+ d Tr( (R( + dM,.
We shall let (+(() be the deterministic equivalent of this equation, that is
(t) (t) (D. 2x)2 (c(s) (t())
(221)
where (recalling Ω is the circle of radius 2)
of (x(t)dz and R, = 2Ti Jn =Q= (t)d2.
/
D. = 2τi Jn
These are analogues of the same formulas that hold exactly for D(O,) and R(O,) when replacing Q₂ by qa( (O.).
Now possible to precisely compare the solution of these ODEs to SGD, as the same machin- ery developed for Theorem applies. In particular, Lemma 1 bounds the supremum difference supsen (9,) - Qt)l (although now with M 0). Hence, we conclude the following:
Theorem 9. Suppose that Assumptions 1, 2 and 3 hold. Suppose that {0x] is C-SGD, Ler sup, c(t) and = sup, (t).. There is constant C C(v, (n/d), 1100 0" 112), stochastic process E, and a constant m m(v) so that for any S S md.
R((02) D(O+)
Rxja DKja
sup oSkgn
S log(d))))
(222)
with probability e and provided the right hand side is less than 1. The stochastic process & is given by
E(t) exp (J, Cnls)
VR(O.) R.
for an absolute constant C > 0. The constant C can be bounded by
C C ((1 110. 0' & Vn/d) exp (C max 7 (n/d))
for absolute conslant C > 0.
We note that further details in this direction are shown in Collins-Woodfnn et al. (2023).
G.1 GETTING A SYSTEM OF ODES
We may use Equation (221) to get an equivalent coupled system of ODEs which can solve for R.- First, we may diagonalize,
J. Σ
K = Σ Mmmmyy
R(2; K)
wwws
(223)
1=1
Where (1:111 and {wi) the eigenvalues and eigenvectors of K respectively. Therefore,
35

---

Published as a conference paper at ICLR 2025
1
Q+
( 0", w²,=
(224)
A
Define vi(1) = (e, 0" ,,,00",,,, wex² /2. Then, R2 = E (i(()) and Dr = Ex= 20; 20;(1). Now, we can find a system of ODEs which describes the evolution of (w))
Choose S2 to be a complex curve enclosing only the i-th eigenvalue of K. Integrating over both sides of equation (221) and using Cauchy's ' integral formula, we see that
du -22((t) (Ra) + T(t) dt
d (B) + + e
(225)
This final system of ODEs is used in all experiments to solve for RG-
G.2 GETTING INTEGRAL. EQUATION
Using Equation (221) and an integrating factor we see that
L ((s)) (Ra) Tr( -)000(0()22)00) 2=(00 (R))) + 02/2)ds (226)
Qs(t) (0) (:00))-2ss2 2=12
+
d
2=00 - Die - Mclt) (et))(Re)
where 22 = fo (7))) () (R,) (R))ds the integrated clipped learning rate. Now, multiplying by 2, integrating both sides around 52 and multiplying by 11/2Ti, we get
R₂ = R( + S (s)e,, (0T-)) + o² oz2/2)ds
(227)
where the first term identified with gradient flow as in Paquette et al. (2022).
H EXPERIMENTAL DETAILS
H.1 CLIPPED SGD AND HOMOGENIZED CLIPPED SGD
The code to reproduce these results is available at https//giitub.oommmmaa//llz
H.1.1
FIGURE
The experiments creating Figure 1 were carried out on an MI Macbook Air. Homogenized clipped SGD is solved via standard Euler-Maruyama algorithm. The procedure for solving for the risk is described in Appendix G.
The synthetic data was generated with ambient dimension o' 500 while the intrinsic dimension is d = 180. For both experiments, = 0.9, 0.7. We plot the 80% confidence interval across 100 runs.
The CIFAR10 data was used to perform binary classification by regressing to +1 labels. The data split into classes and where class contains: birds, cats, and dogs. Class 2 contains: trucks, ships, and planes. The data matrix D is first passed through random features model so that
D,, tanh DA
(228)
where is a random features matrix independent standard Gaussians. order to estimate the regression problem was first solved using Sci-kit leam (Pedregosa et al., 201 1) and the resulting
36

---

Published as a conference paper at ICLR 2025
solution taken to be 0" The differences {y, (0" (0"),,)} for all X; E Dry then assumed to be the noise. A histogram of this noise is available in Figure 10a. The noise was then fitted to a Gaussian. Finally, 0.1 and 0.5 and the C-SGD plot represents the 80% confidence interval over 50 runs.
The Wikitext2 data first processed for eexttooken-predictie The data tokenized and split into context lengths of at most 512. The data was then embedded using the Huggingface imple- mentation of GPT-2 (Radford et al., 2019) and passed through the same random features model as with CIFARIO. We again used Sci-kit learn to estimate 0" and the noise terms whose histogram is available in Figure 10b. The noise resembled mixture of 3- Gaussians and we therefore fit the noise to Gaussian mixture model. In this case 0.4 and 0.5 and the C-SGD plot represents the 80% confidence interval over runs.
1.0
Estimated PDF
Estimated PDF Empirical density
Empirical density
0.8
0.4
Density
Density
0.3
0.4-
0.2
0.1
0.2
0.0
-3
-1
-2
2
(a) CIFARIO noise
(b) Wikitext2 noise
Figure 10: Histograms of the estimated noise distributions for the CIFARIO and Wikitext2 datasets.
H.1.2 FIGURE 4
The experiments creating were again carried out on an MI Macbook Air. Numerical optimization of the max-(CCC) clipping schedule (Equation (18)) was done via the Nelder-Mead algorithm using standard python libraries.
H.2 INTRINSIC DIMENSION EXPERIMENTS
The experiments in Appendix C.3 were carried out on 8 P100 GPUs trained in parallel with batch size 128. This allowed for efficient computation of the full batch Gauss-Newton operator power iteration. Both networks were trained for 200 epochs. ResNet18 was trained with cosine learning rate decay (base learning rate 0.05), while ViT was trained with linear warmup for 2 epochs followed by cosine learning rate decay (base learning rate 0.00625). Both networks used GELU activation function.
via
37


Reviews:
[{"review_id": "0JynZXB0jk", "reviewer": "Reviewer_cyxq", "summary": "This paper analyzes SGD with gradient clipping by constructing an analogous Stochastic Differential Equation (SDE) and studying its solution. The SDE developed by the authors follows the development in [1] with the addition of two factors $\\mu_c$ and $\\nu_c$ that capture the effect of gradient clipping. The authors show that their SDE is close to the SGD trajectory and also conduct a stability analysis to obtain a criterion for when clipped SGD is more or less stable than its unclipped version (and allows for larger learning rates). The authors study different noise conditions (Gaussian and Rademacher-type) noise and show that the clipping threshold can be set to obtain larger learning rates. Finally this paper explores the conditions under which clipped SGD can achieve lower risk values than unclipped SGD.\n\n[1] Paquette, C., Paquette, E., Adlam, B., & Pennington, J. (2022). Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties. arXiv preprint arXiv:2205.07069.", "questions": "1. The role of CSC is still unclear to me. Can the authors provide a demonstration of how clipped SGD allows for larger learning rates. None of the figures seem to illustrate how clipped SGD converges faster than unclipped SGD. In case I have missed this please direct me to where I can find this.\n\n2. While there is a figure demonstrating the correspondence of clipped SGD and the SDE with heavy tailed Cauchy noise, there are no experiments comparing unclipped and clipped SGD in that condition. Does clipped SGD converge faster in that situation? Can this be demonstrated in an experiment?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis seems strong and the authors provide extensive technical proofs for their theoretical results. While I did not go through all the proofs to verify their correctness, the analysis seems correct. The authors go beyond just showing a correspondence between clipped SGD and the C-HSGD stochastic differential equation to provide some applications of their result to stability analysis and to study when clipping helps in SGD.", "weaknesses": "1. The theoretical analysis seems to mostly be an application of previous results obtained in [1]. The new machinery that is used here is Stein's lemma to obtain bounds on the quantities $\\mu_c$ and $\\nu_c$ that characterize the effects of clipping SGD. This only allows the authors to characterize $\\mu_c, \\nu_c$ for gaussian data, even though they are able to show the correspondence of the SDE to clipped SGD with non-gaussian data. The technical contribution is arguably only incremental.\n\n2. The condition for testing whether clipped SGD reaches lower risk values (CCC) seems to be hard to evaluate. It involves estimating whether $\\mu_c^2 / \\nu_c > 1$ anywhere along the trajectory of the SDE. This seems to require solving the SDE to estimate whether clipped SGD is beneficial, as well as estimating the threshold $c$ at which to clip the gradients. This may be harder than simply solving the original least squares optimization problem.\n\n3. While the authors explore how their results extend to the setting of training deep networks, the arguments are made in the regime where deep networks can be approximated well by linear models (the NTK regime). NTK models do not perform as well as deep networks that learn features and that cannot be approximated as linear models.\n\n[1] Paquette, C., Paquette, E., Adlam, B., & Pennington, J. (2022). Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties. arXiv preprint arXiv:2205.07069.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "InsTeNc1DZ", "reviewer": "Reviewer_dT4j", "summary": "The paper studies the properties of clipped SGD for linear regression with mean squared error loss under specific data and noise distributions. The authors compare the parameters learned from clipped SGD (C-SGD) to the solution of a stochastic differential equation (C-HSGD), demonstrating their close alignment in terms of risk and optimality gap. They also derive an ODE to describe risk evolution. Additionally, learning stability (CSC) and instantaneous risk descent (CCC) are analyzed through descent and variance reduction factors. The authors show that under Gaussian noise, clipped SGD is inferior to unclipped SGD, but under other noise distributions, it improves both performance and stability. Theoretical results are supported by experiments.", "questions": "* In the conclusion, the authors suggest extending the analysis to more complex losses. What are the bottlenecks for such an analysis?\n* The heuristic presented in the paper appears to be limited to normally distributed data due to the validity of Eqs. (10a) and (10b). Is it possible to extend this approach to a more general setting, such as sub-Gaussian distributions?\n* While the authors used real-world data to validate the C-HSGD approximation, they did not evaluate the heuristics on real-world data (though the setup for Figure 4 is somewhat unclear, please correct me if I am mistaken). Could the authors clarify why this aspect was not explored?\n\nMinor: \n* In Theorem 1, the subscript for $\\theta_{sd}$  in the denominator of the definition of $\\mathcal{E}$ should include a ceiling (or floor).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is very well-written, and the problem it addresses is important for large-scale learning settings.  Particularly, gradient clipping is an important  technique that proves useful in deep learning, which makes it crucial to understand its effects. This paper provides a rigorous characterization of clipped SGD in linear regression, focusing on the descent and variance reduction factors. The authors also propose a learning rate schedule that ensures clipped SGD performs at least as well as standard SGD, offering practical insights for optimization.", "weaknesses": "* The problem setting is restricted to linear regression with mean squared loss  and the proposed heuristic seems to be meaningful only when the features follow a Gaussian distribution.\n\n* Calculating the descent and variance reduction factors in more general settings appears challenging, since it involves numerical optimization at every step, which limits the practical applicability of the proposed learning rate scheduling and criteria.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E9Xs8wQkLd", "reviewer": "Reviewer_g87A", "summary": "The paper studies the widely used gradient clipping technique in SGD under quadratic settings. Under specific assumptions, the paper develops a theoretical analysis of the training dynamics by proposing an SDE C-HSGD and proving its connection to clipped SGD. Based on this, the paper shows that when clipping can help convergence and stability, providing insights into understanding the clipping technique.", "questions": "1. More intuitive explanations for the connection between C-SGD and S-HSGD are welcomed.\n\n2. As also noted in the weakness part, I think possibly the authors can discuss how the analysis in the Gaussian quadratic settings may have impacts on broader machine learning applications.\n\n3. Do you also take stability into consideration when comparing C-SGD and SGD in Section 5?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. To my knowledge, this is a novel perspective looking into clipping, which is interesting and aligns with the common belief that clipping helps when noise is heavy-tailed.\n\n2. The theory seems to be clear and complete.", "weaknesses": "1. Although the theory looks promising, I think it's still restrictive due to the settings it applies: \n    - As the author also mentioned in the paper, one of the key benefits of clipping is that it helps SGD converge in generalized smooth settings, which cannot be reflected by quadratics.\n    - The theory typically requires the data $x$ to be Gaussian, or close to Gaussian as in Appendix A. This is still a restrictive assumption. \n\n2. I kindly suggest the authors gather more notation definitions in Section 2, as there are still new notations in the following sections, which may make it inconvenient to follow and refer to when reading.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4I0CgkBfbP", "reviewer": "Reviewer_2Wzk", "summary": "This paper provides a theoretical investigation into the effects of gradient clipping in high-dimensional settings. Specifically, the authors analyze how clipping impacts SGD in terms of stability, convergence, and optimization dynamics. They derive a deterministic equivalent for clipped SGD, named Clipped Homogenized SGD, which approximates the risk evolution via a system of Ordinary Differential Equations (ODEs) under high-dimensional assumptions. Key findings indicate that while clipping does not improve performance with Gaussian noise, it can enhance stability and convergence under other noisy conditions. The paper also proposes a heuristic clipping schedule for near-optimal performance with minimal hyperparameter tuning.", "questions": "1. Can the authors provide more insights into how sensitive the results are to the hyperparameter choice in the proposed clipping heuristic? Would small variations in the threshold significantly affect the stability or convergence?\n\n2. Could the authors discuss the potential for extending their theoretical findings beyond linear regression to other models, such as generalized linear models? Are there specific challenges or limitations in applying their stability analysis to non-linear models or more complex loss functions?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The study provides a new theoretical perspective on gradient clipping, a widely used technique in training deep learning models, by framing it in high-dimensional analysis. This theoretical foundation is novel and helps bridge a gap in understanding the dynamics of SGD under clipping.\n\n2. The paper is well-organized, with a clear presentation of problem setup, definitions, and theoretical results. The analysis is rigorous, covering a range of noise distributions and demonstrating the proposed model’s effectiveness across synthetic and real-world datasets", "weaknesses": "1. The analysis is specific to linear regression, which may limit the generalizability of the findings to other types of models. Insights into extending these results or experiments with more complex models, such as neural networks, could enhance the broader relevance of the work.\n\n2. The descent and variance reduction factors play a central role in understanding the stability and effectiveness of clipping. However, the paper lacks a practical interpretation or intuition for these factors, which might make it challenging for practitioners to apply these insights beyond the linear regression context. Further discussion on the role of these factors in practical scenarios, perhaps with illustrative examples, would enhance accessibility and the broader applicability of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)