To Clip or not to Clip: the Dynamics of SGD with Gradient Clipping in High-Dimensions

## Abstract

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.

## 1 Introduction

Stochastic gradient descent (SGD) methods are the standard for nearly all large scale modern optimization 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, ; Pascanu et al., ). Gradient clipping replaces any stochastic gradient $\nabla_{\bm{\theta}}f_{\bm{\theta}}(\mathbf{x})$ with a clipped gradient $\operatorname{clip}_{c}(\nabla_{\bm{\theta}}f_{\bm{\theta}}(\mathbf{x}))$, for some threshold $c$, where

$$ $\operatorname{clip}_{c}(\mathbf{z})=\min\left(1,\frac{c}{\|\mathbf{z}\|}\right )\mathbf{z}.$ (1) $$

While gradient clipping was first introduced to address the problem of exploding gradients in recurrent 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., ; Pichapati et al., ) and computer vision (Tolstikhin et al., ; Dosovitskiy et al., ).

Despite widespread use, the reasons behind the effectiveness of clipping remain somewhat a mystery. For instance, it is unclear
exactly how the gradient distribution affects training, or for
which distributions clipping can offer benefits. It is hypothesized that the distribution of the gradient norms plays a
large role (Zhang et al., ). 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 hyper-parameters scale with
dimension (Kaplan et al., ). Understanding this behaviour would allow one to perform hyperparameter tuning on
smaller, more efficient models before scaling to a potentially very large final architecture.

In this work we develop a theory of clipped SGD in high-dimensions under the mean-squared error loss (MSE) over a class
of random least-squares problems.
After formally introducing the class of considered problems (Sec. 2),
we show the following:

- •
In high-dimensions the dynamics of clipped SGD (C-SGD) are well described by an SDE, clipped homogenized SGD (C-HSGD). We provide a *non-asymptotic* bound on the difference of the risk curves between C-SGD and C-HSGD. Under C-HSGD the risk evolution can be described by a 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 can be
described by two unitless *reduction factors* $\mu$ and $\nu$ 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, we 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 as 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 to closely follow an optimal schedule which we 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., ). They argue that this noise is well approximated by a Gaussian for ResNets (He et al., ) trained on Imagenet (Deng et al., ), while a heavy-tailed distribution is more appropriate with BERT (Devlin et al., ) 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., ; Zhang et al., ; Chen et al., ). 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., ; Mandt et al., ; Barrett & Dherin, ). More recently, partly spurred by the sheer size of modern models as well as the apparent regularity at which they scale (Kaplan et al., ), there has been an interest in studying stochastic optimization in high-dimensions with SDEs. There is a formal 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 in the streaming setup over a variety of losses (Collins-Woodfin et al., ; Paquette et al., ), and the resulting analyses lead to quantities which can be useful for understanding learning dynamics in practical models (Agarwala et al., ).

## 2 Problem setup

In this work, we consider linear regression using the mean-squared loss

$$ $\mathcal{L}(\bm{\theta},\mathbf{x},y)=\|\left\langle\mathbf{x},\bm{\theta} \right\rangle-y\|^{2}/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

$$ $\displaystyle\bm{\theta}_{k+1}$ $\displaystyle=\bm{\theta}_{k}-\eta_{k}\operatorname{clip}_{c_{k}}\left(\nabla_ {\bm{\theta}}\mathcal{L}(\bm{\theta}_{k},\mathbf{x}_{k+1},y_{k+1})\right),$ (3) $$

where $\nabla_{\bm{\theta}}\mathcal{L}(\bm{\theta}_{k},\mathbf{x}_{k+1},y_{k+1})=(
\left\langle\mathbf{x}_{k+1},\bm{\theta}_{k}\right\rangle-y_{k+1})\mathbf{x}_{
k+1}$ with initialization $\bm{\theta}_{0}\in\mathbb{R}{d}$. We assume that the samples $\{(\mathbf{x}_{k},y_{k})\}_{k\geq 0}$, consisting of data $\mathbf{x}_{k}$ and targets $y_{k}$, satisfy the following:

###### Assumption 1 .

The data $\mathbf{x}\in\mathbb{R}{d}$ are Gaussian with covariance $\mathbf{K}$. The targets $y$ are generated by $y=\left\langle\mathbf{x},{\bm{\theta}^{*}}\right\rangle+\epsilon$, where $\epsilon$ represents noise and ${\bm{\theta}^{*}}$ is the ground-truth.

The noise is centered and subgaussian (see Vershynin () for more details) with subgaussian norm $\|\epsilon\|_{\psi_{2}}\leq\dutchcal{v}$ and variance $\mathbb{E}[\epsilon^{2}]=\sigma^{2}$ for some $\dutchcal{v},\sigma\geq 0$.

We formulate a more general version of our results for non-Gaussian data
in Appendix A.

###### Definition 1 .

Define the population risk and the noiseless risk:

$$ $\displaystyle\mathcal{P}(\bm{\theta})=\mathbb{E}_{(\mathbf{x},\epsilon)}\left[ (\left\langle\mathbf{x},\bm{\theta}-{\bm{\theta}^{*}}\right\rangle-\epsilon)^{ 2}\right]/2\quad\text{and}\quad\mathcal{R}(\bm{\theta})=\mathbb{E}_{\mathbf{x} }\left[\left\langle\mathbf{x},\bm{\theta}-{\bm{\theta}^{*}}\right\rangle^{2} \right]/2,$ (4) $$

as well as the distance to optimality

$$ $\mathcal{D}(\bm{\theta})=\|\bm{\theta}-{\bm{\theta}^{*}}\|^{2}.$ $$

Our theory is phrased in terms of the intrinsic dimension, a statistical notion of dimensionality which is occasionally much
smaller than the ambient dimension $\dutchcal{d}$. There are interesting settings where these dimensions are effectively interchangeable, and as such, the reader may wish to, at first glance, consider the results to be phrased in terms of the ambient dimension.

###### Definition 2 (Intrinsic Dimension) .

Let the data $\mathbf{x}\in\mathbb{R}^{\dutchcal{d}}$ have covariance matrix $\mathbf{K}$. Define the intrinsic dimension of the data to be

$$ $d=\operatorname{Tr}(\mathbf{K})/\|\mathbf{K}\|,$ (5) $$

where $\|\mathbf{K}\|$ refers to the operator norm. Note that $d\leq\dutchcal{d}$. We will refer to $\dutchcal{d}$ as the ambient dimension.

###### Assumption 2 .

The covariance matrix $\mathbf{K}$ is normalized such that $\|\mathbf{K}\|=1$. Note that this assumption may always be satisfied by rescaling the problem.

The definition of $d$ can be extended to and measured in real neural networks trained on real
datasets; see 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 $\eta:\mathbb{R}^{+}\to\mathbb{R}^{+}$ and $c:\mathbb{R}^{+}\to\mathbb{R}^{+}$ such that

$$ $\displaystyle c_{k}=c(k/d)\sqrt{d}$ $\displaystyle\eta_{k}=\eta(k/d)/d.$ (6) $$

We note that while it is reasonable for $c(t)=\infty$ (which is to say that no clipping occurs), for technical reasons, we shall not allow this in our main theorem.

###### Assumption 1 .

###### Definition 1 .

###### Definition 2 (Intrinsic Dimension) .

###### Assumption 2 .

###### Assumption 3 .

## 3 Clipped homogenized SGD

Our main result shows that the risk of C-SGD is well-approximated by the solution to an SDE which we call *clipped homogenized SGD* (C-HSGD):

###### Definition 3 (Clipped Homogenized SGD) .

Denote the stochastic gradient as $\ell_{\bm{\theta}}\mathbf{x}$, where $\ell_{\bm{\theta}}=\left\langle\mathbf{x},\bm{\theta}-{\bm{\theta}^{*}}\right
\rangle-\epsilon$. Define the descent reduction factor and the variance reduction factor

$$ $\displaystyle\mu_{c}(\bm{\theta})=\frac{\|\mathbb{E}[\operatorname{clip}_{c}( \ell_{\bm{\theta}})\mathbf{x}]\|}{\|\mathbb{E}[\ell_{\bm{\theta}}\mathbf{x}]\| }\qquad\text{and}\qquad\nu_{c}(\bm{\theta})=\frac{\mathbb{E}[\operatorname{ clip}^{2}_{c}(\ell_{\bm{\theta}})]}{\mathbb{E}[\ell_{\bm{\theta}}^{2}]}.$ (7) $$

Then C-HSGD is defined to be the solution to

$$ $\mathrm{d}\bm{\Theta}_{t}=-\eta(t)\mu_{c(t)}(\bm{\Theta}_{t})\nabla\mathcal{P} (\bm{\Theta}_{t})\mathrm{d}t+\eta(t)\sqrt{\frac{2\nu_{c(t)}(\bm{\Theta}_{t}) \mathcal{P}(\bm{\Theta}_{t})\mathbf{K}}{d}}\mathrm{d}\mathbf{B}_{t},$ (8) $$

where initialization is taken to be the same as SGD and $B_{t}$ is a standard Brownian motion.

###### Definition 3 (Clipped Homogenized SGD) .

##### Remark:

If the noise is heavy-tailed ($\sigma=\infty$), we can reformulate the above by redefining $\nu_{c}(\bm{\theta})=\mathbb{E}[\operatorname{clip}^{2}_{c}(\ell_{\bm{\theta}})]$ and changing the coefficient on the Brownian motion term to $\eta(t)\sqrt{\nu_{c(t)}(\bm{\Theta}_{t})\mathbf{K}/d}$. This comes from noticing that $\mathbb{E}[\ell_{\bm{\theta}}^{2}]=2\mathcal{P}(\bm{\theta})$ and $\mathbb{E}[\operatorname{clip}^{2}_{c}(\ell_{\bm{\theta}})]<\infty$ even in the heavy-tailed case due to the effects of clipping. This yields the immediate observation that clipping improves SGD under heavy-tailed noise since clipped SGD converges while SGD does not.

C-HSGD has similar structure to an SDE previously established for unclipped SGD (Paquette et al., ), with the addition of reduction factors $\mu_{c}$ and $\nu_{c}$ 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 $-\nabla_{\bm{\theta}}\mathcal{R}$—but clipping provides a bias *against* the gradient which shrinks the descent term (hereafter the negative term in (8)).
Meanwhile, the diffusion term is shrunk by $\nu_{c}(\theta)$ due to the reduction of variance of the clipped gradients. These terms imply a tradeoff: clipping should aim to reduce variance (decrease $\nu_{c}$) more than it shrinks the descent term (decrease $\mu_{c}$). We investigate this trade-off in detail in Section 5.

We compute $\mu_{c}$ and $\nu_{c}$ for select data and noise distributions (Appendix D).
For Gaussian data, Stein’s Lemma gives us a form for $\mu_{c}$ which can be interpreted as the probability of *not* clipping:

$$ $\displaystyle\mu_{c}(\bm{\theta})=\mathbb{P}(|\ell_{\bm{\theta}}|\leq c).$ (9) $$

For non-Gaussian data the exact form of $\mu_{c}$ is challenging to compute due to its dependence on $\mathbf{x}$;
however, Equation (9) can give a good approximation
in many high-dimensional settings due to Central Limit Theorem effects. As an example, risk curves for linear models trained on
CIFAR10 (Figure 1 (c)) and Wikitext2 (Figure 1 (d)) are well-captured by the dynamics of C-HSGD
with $\mu_{c}$ computed using the Gaussian form from Equation 9. (^1^11Code to reproduce the results is available at [Github](https://github.com/nmarzz/clip).) See the experiment details in Appendix H.

This form can also be used to tractably compute $\mu_{c}$ in the non-linear setting using information already computed
during C-SGD. See Appendix C.2 for a full description of the extension of $\mu_{c}$ and $\nu_{c}$ to this setting, as well as a demonstration of the technique during training of ResNet18 and ViT
on CIFAR10.

There exist a set of tractable lower and upper bounds for $\mu_{c}$ and $\nu_{c}$ 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 0, there exist
positive constants $\kappa_{l}$ and $\kappa_{u}$ such that

$$ $\displaystyle\kappa_{l}\min\left(1,\frac{c}{\sqrt{2\mathcal{R}(\bm{\theta})+ \sigma^{2}}}\right)\leq$ $\displaystyle\mu_{c}(\bm{\theta})\leq\kappa_{u}\min\left(1,\frac{c}{\sqrt{2 \mathcal{R}(\bm{\theta})+\sigma^{2}}}\right)$ (10a) $\displaystyle\kappa_{l}\min\left(1,\frac{c^{2}}{2\mathcal{R}(\bm{\theta})+ \sigma^{2}}\right)\leq$ $\displaystyle\nu_{c}(\bm{\theta})\leq\kappa_{u}\min\left(1,\frac{c^{2}}{2 \mathcal{R}(\bm{\theta})+\sigma^{2}}\right).$ (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 $\bm{\Theta}_{t}$ and $\bm{\theta}_{k}$ are independent realizations of C-HSGD and C-SGD with equal, deterministic initial conditions.
Let $\overline{c}=\sup_{t}c(t)$ and ${\overline{\eta}}=\sup_{t}{\eta}(t)$.
There is a constant $\mathcal{C}=\mathcal{C}(\dutchcal{v},(n/d),\overline{c},\overline{\eta},\|\bm{
\theta}_{0}-{\bm{\theta}^{*}}\|^{2})$, a stochastic process $\mathcal{E}$, and a constant $m=m(\dutchcal{v})$ so that for any $1\leq u\leq md$ and any $n$

$$ $\sup_{0\leq k\leq n}\left\|\begin{bmatrix}\mathcal{R}(\bm{\theta}_{k})\\ \mathcal{D}(\bm{\theta}_{k})\end{bmatrix}-\begin{bmatrix}\mathcal{R}(\bm{ \Theta}_{k/d})\\ \mathcal{D}(\bm{\Theta}_{k/d})\end{bmatrix}\right\|\leq\mathcal{C}\mathcal{E}( n/d)u\log(d)d^{-1/2},$ (11) $$

with probability $1-e^{-u}$ and provided the right hand side is less than $1$.
The stochastic process $\mathcal{E}$ is given by

$$ $\mathcal{E}(t)=\exp\left(\int_{0}^{t}\frac{C{\eta}(s)^{2}\sigma\,\mathrm{d}s}{ \sqrt{\mathcal{R}(\bm{\Theta}_{s})+\mathcal{R}(\bm{\theta}_{sd})}}\right)$ $$

for an absolute constant $C>0$.
The constant $\mathcal{C}$ can be bounded by

$$ $\mathcal{C}\leq C\sqrt{n/d}\,\overline{\eta}\dutchcal{v}^{2}\cdot((1+\|\bm{ \theta}_{0}-{\bm{\theta}^{*}}\|^{2})\dutchcal{v}^{2}+\overline{c}^{2}\sqrt{n/d })\cdot\exp\left(C\max\{\overline{\eta},\overline{\eta}^{2}\}(n/d)\right).$ $$

Informally, this theorem says that

$$ $\sup_{0\leq k\leq n}\left\|\begin{bmatrix}\mathcal{R}(\bm{\theta}_{k})\\ \mathcal{D}(\bm{\theta}_{k})\end{bmatrix}-\begin{bmatrix}\mathcal{R}(\bm{ \Theta}_{k/d})\\ \mathcal{D}(\bm{\Theta}_{k/d})\end{bmatrix}\right\|=\mathcal{O}(\log(d)d^{-1/2 }).$ $$

In particular, as $d$ grows, the risk curves of C-SGD and C-HSGD look closer to one another for longer time windows and with higher probability. Under additional assumptions,(^2^22The spectrum of $\mathbf{K}$ converges and the initialization $\bm{\theta}_{0}-{\bm{\theta}^{*}}$ converges) the C-HSGD curve converges to a dimension-independent deterministic limit and thus so 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.

###### Theorem 1 .

##### Extracting deterministic dynamics:

For any twice differentiable function $q$, the C-HSGD dynamics can be expressed as follows:

$$ $\mathrm{d}q(\bm{\Theta}_{t})=-\eta(t)\mu_{c(t)}(\bm{\Theta}_{t})\nabla\mathcal {P}(\bm{\Theta}_{t})^{T}\nabla q(\bm{\Theta}_{t})\mathrm{d}t+\frac{\eta(t)^{2} }{d}\nu_{c(t)}(\bm{\Theta}_{t})\mathcal{P}(\bm{\Theta}_{t})\operatorname{Tr}( \mathbf{K}\nabla^{2}q)\mathrm{d}t+\mathrm{d}\mathcal{M}_{t},$ (12) $$

where $\mathcal{M}_{t}$ is a martingale term that vanishes as $d\to\infty$. 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 $q(\bm{\Theta}_{t})$ by setting $\mathcal{M}_{t}\equiv 0$.

Using this idea, we introduce deterministic equivalents, $R_{t}$ and $D_{t}$, for the risk terms $\mathcal{R}(\bm{\Theta}_{t})$ and $\mathcal{D}(\bm{\Theta}_{t})$, respectively. Solving for $R_{t}$ and $D_{t}$ involves forming and solving a coupled system of $d$ ordinary differential equations. Additionally, Theorem 1 implies that these risks under clipped stochastic gradient descent converge to their deterministic equivalents. The complete details and derivation of this system of ODEs along with the statement and proof of C-SGD’s convergence to the deterministic equivalents are available in 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 Gaussian 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
$R_{t}$ solves the autonomous ODE:

$$ $\dot{R}_{t}=-2\eta(t)\mu_{c(t)}R_{t}+\eta(t)^{2}\nu_{c(t)}(R_{t}+\sigma^{2}/2),$ (13) $$

where $R_{0}=\mathcal{R}(\bm{\Theta}_{0})$.

Since the data is Gaussian, it is possible to express $\mu_{c}$ and $\nu_{c}$ as functions of the risk. As a slight abuse of notation we shall also write $\mu_{c}(\mathcal{R}(\bm{\theta}))$ or $\nu_{c}(\mathcal{R}(\bm{\theta}))$ for $\mu_{c}(\bm{\theta})$ or $\nu_{c}(\bm{\theta})$ respectively. We will suppress the dependence on $\bm{\theta}$ where appropriate, as we have in Example 1.

Figure: (a) Synthetic data, Gaussian noise
Refer to caption: x1.png

###### Example 1 (Isotropic data) .

## 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., ; Agarwala et al., ).
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 $\mu_{c}$ and $\nu_{c}$ which account for the effects of clipping.

From Equation (12), we observe that for either the risk $\mathcal{R}$ or the distance to optimality $\mathcal{D}$, the instantaneous time derivative is quadratic in the learning rate $\eta({t})$. This implies that we can compute a stability threshold for the learning rate, determining whether, in high-dimensions, these measures of suboptimality increase or decrease. We find the critical values $\eta^{*}_{\mathcal{R}}({t})$ and $\eta^{*}_{\mathcal{D}}({t})$ such that
$\mathbb{E}[\mathrm{d}\mathcal{R}(\Theta_{t})]=0$
and
$\mathbb{E}[\mathrm{d}\mathcal{D}(\Theta_{t})]=0$
. In particular,

$$ $\eta^{*}_{\mathcal{R}}({t})=\frac{d\|\nabla\mathcal{P}(\bm{\Theta}_{t})\|^{2}} {\operatorname{Tr}(\mathbf{K}^{2})\mathcal{P}(\bm{\Theta}_{t})}\frac{\mu_{c(t) }(\bm{\Theta}_{t})}{\nu_{c(t)}(\bm{\Theta}_{t})}\quad\text{and}\quad\eta^{*}_{ \mathcal{D}}({t})=\frac{\mathcal{R}(\bm{\Theta}_{t})}{\mathcal{P}(\bm{\Theta}_ {t})}\frac{\mu_{c(t)}(\bm{\Theta}_{t})}{\nu_{c(t)}(\bm{\Theta}_{t})}.$ (14) $$

This implies that clipping increases instantaneous stability (for both $\mathcal{R}$ and $\mathcal{D}$) relative to unclipped SGD when

$$ $\frac{\mu_{c(t)}(\bm{\Theta}_{t})}{\nu_{c(t)}(\bm{\Theta}_{t})}>1.$ ( CSC ) $$

We refer to this as the clipped-stability-criterion (CSC). This can be interpreted as
as a relative signal-to-noise-ratio; the fraction of clipped gradients $\mu$ reduces the signal,
while clipping reduces the noise through the reduction factor $\nu$. 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.

Clipping will increase the stability of SGD with a small enough choice of $c$:

###### Theorem 2 .

For data $\mathbf{x}\sim N(0,\mathbf{K})$ one may always choose the clipping schedule $c$ 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 Appendix 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 $\mu$ for general data makes precise
claims difficult.

Counterintuitively, clipping can also *decrease* stability in some cases, when the bias towards $\nabla_{\bm{\theta}}\mathcal{R}$ ($\mu$) is reduced more than
the overall gradient norms ($\nu$). This shows that some care must be taken to avoid clipping being detrimental. The proof of the following theorem straightforwardly uses the definitions of $\mu_{c}$ and $\nu_{c}$ and can be found in Appendix F.

###### Theorem 3 .

Consider $\mathbf{x}\sim N(0,\mathbf{K})$ and noise with the distribution given by

$$ $\displaystyle\mathbb{P}(\epsilon=-\lambda)=p/2,$ $\displaystyle\mathbb{P}(\epsilon=0)=1-p,$ $\displaystyle\mathbb{P}(\epsilon=\lambda)=p/2,$ (15) $$

for $p\in(0,1)$ and $\lambda>0$. Then, there is a constant $r$ depending on $p,\lambda$ so that when $R_{t}\leq r$ there always exists $c(t)$ such that the (CSC) is less than $1$. Therefore, clipped SGD can be less stable than unclipped SGD.

###### Theorem 2 .

###### Theorem 3 .

## 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 combination 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 training. 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 $\mathbf{x}\sim N(0,\mathbf{I})$.
Define $R^{\infty}_{t}$ to be the deterministic equivalent of $\mathcal{R}(\bm{\varphi}_{t})$, where $\bm{\varphi}_{t}$ is C-HSGD with $c(t)\equiv\infty$ (which is to say unclipped HSGD). Example 1 shows that $R_{t}$ and $R^{\infty}_{t}$ solve the following ODEs,

$$ $\displaystyle\frac{\mathrm{d}R_{t}}{\mathrm{d}t}=-2\eta(t)\mu_{c(t)}R_{t}+ \frac{\eta^{2}(t)}{2}\nu_{c(t)}(2R_{t}+\sigma^{2}),$ $\displaystyle\frac{\mathrm{d}R^{\infty}_{t}}{\mathrm{d}t}=-2\eta(t)R^{\infty}_ {t}+\frac{\eta^{2}(t)}{2}(2R^{\infty}_{t}+\sigma^{2}).$ (16) $$

These results enable a comparison between clipped and unclipped SGD. Since these ODEs are quadratic in $\eta(t)$, it is straightforward to greedily maximize their instantaneous rate of descent, resulting in the globally optimal learning rate schedule. Optimizing each ODE over $\eta(t)$ yields

$$ $\displaystyle\frac{\mathrm{d}R_{t}}{\mathrm{d}t}=-\frac{R_{t}^{2}}{R_{t}+ \sigma^{2}/2}\frac{\mu_{c(t)}^{2}}{\nu_{c(t)}}$ $\displaystyle\frac{\mathrm{d}R^{\infty}_{t}}{\mathrm{d}t}=-\frac{\left({R^{ \infty}_{t}}\right)^{2}}{R^{\infty}_{t}+\sigma^{2}/2}.$ (17) $$

When $R_{t}=R^{\infty}_{t}$, we see that the rate of descent is faster and thus clipping improves SGD exactly when there exists a $c(t)$ such that

$$ $\displaystyle\frac{\mu^{2}_{c(t)}(R_{t})}{\nu_{c(t)}(R_{t})}>1.$ ( CCC ) $$

We call this inequality the clipping-comparison-criterion (CCC). Therefore, in our setting we can 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 $\nu_{c(t)}$ more than it reduces the squared reduction to the descent term $\mu^{2}_{c(t)}$. This is consistent with previous
observations that, in practice, clipping is effective when the distribution of the gradient
norms is heavy-tailed Zhang et al. (), but gives a 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.1 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).

Figure: (a) The (CSC)
Refer to caption: x5.png

### 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 a procedure which, given a 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 $\eta({t})$, used to train unclipped SGD. We define the max-(CCC) clipping threshold schedule as follows: At step $t$, we first set the clipping threshold to

$$ $c^{*}(t)=\operatorname{argmax}_{c}\frac{\mu^{2}_{c}(R_{t})}{\nu_{c}(R_{t})}.$ (18) $$

Given a clipping threshold $c$, we define a *compensated* learning rate for clipped SGD by

$$ $\tilde{\eta}(t,c)=\eta(t)/\mu_{c}(R_{t}).$ (19) $$

Effectively, this learning rate compensates for the fact that clipping biases SGD against the gradient such that clipped SGD now has the same instantaneous descent term as unclipped SGD. We now choose $\eta^{*}(t)=\tilde{\eta}(t,c^{*}({t}))$ as our learning rate. In Appendix C.1 we provide plots of Equation (18) for various distributions.

This schedule will never underperform unclipped SGD. If the (CCC)
is never satisfied we have $c^{*}({t})\equiv\infty$ and $\eta^{*}(t)=\eta({t})$, 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. In order to show this, we first have to solve for $R_{t}$ under anisotropic data. In this setting, the risk is the sum of two
parts: a gradient flow term and an integrated correction term. The gradient flow term is associated with the infinitesimal learning rate limit of SGD. It *decreases* the risk and comes from solving the
underlying problem. The correction term arises because the actual learning rate is not infinitesimal. It encodes the errors made by SGD and *increases* the risk. Gradient flow is defined to be,

$$ $\mathrm{d}\bm{\Phi}^{\mathrm{gf}}_{t}=-\nabla\mathcal{R}(\bm{\Phi}^{\mathrm{gf }}_{t})\,\mathrm{d}t,$ (20) $$

with $\bm{\Phi}^{\mathrm{gf}}_{0}=\bm{\theta}_{0}$. Then the gradient flow term is $\mathcal{R}(\bm{\Phi}^{\mathrm{gf}}_{t})$. In Appendix G, we show $R_{t}$ with any learning rate $\eta(t)$ and clipping schedule $c(t)$ solves

$$ $R_{t}=\mathcal{R}(\bm{\Phi}^{\mathrm{gf}}_{\Gamma_{T}^{c}})+\frac{1}{d}\int_{0 }^{t}{\eta}^{2}(s)\nu_{c(s)}\operatorname{Tr}(\mathbf{K}^{2}e^{-2\mathbf{K}( \Gamma_{t}^{c}-\Gamma_{s}^{c})})(R_{s}+\sigma^{2}/2)\mathrm{d}s,$ (21) $$

where $\Gamma_{t}^{c}=\int_{0}^{t}\eta(s)\mu_{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)\equiv\infty$:

$$ $R^{\infty}_{t}=\mathcal{R}(\bm{\Phi}^{\mathrm{gf}}_{\Gamma_{T}})+\frac{1}{d} \int_{0}^{t}{\eta}^{2}(s)\operatorname{Tr}(\mathbf{K}^{2}e^{-2\mathbf{K}( \Gamma_{t}-\Gamma_{s})})(R^{\infty}_{s}+\sigma^{2}/2)\mathrm{d}s.$ (22) $$

where $\Gamma_{t}=\int_{0}^{t}\eta(s)\mathrm{d}s$. This gives us the following theorem:

###### Theorem 4 .

Given SGD with learning rate schedule $\eta({t})$
and clipped SGD with learning and clipping schedules $\eta^{*}({t})$ and $c^{*}({t})$, then $R_{T}\leq R^{\infty}_{T}$.
If there exists a $t\in[0,T]$ such that the (CCC) holds then $R_{T}<R^{\infty}_{T}$.
Conversely, if $\mu_{c}^{2}(R)/\nu_{c}(R)\leq 1$ for all $R>0$ and $c>0$, then for any learning and clipping schedules $\eta({t})$ and $c({t})$, SGD with the compensated learning rate schedule $\eta(t)\mu_{c(t)}$ has $R^{\infty}_{T}\leq R_{T}$.

###### Proof.

With these choices, the clipped risk (21) solves

$$ $R_{T}=\mathcal{R}(\bm{\Phi}^{\mathrm{gf}}_{\Gamma_{T}})+\frac{1}{d}\int_{0}^{T }\eta^{2}(s)\frac{\nu_{c(s)}}{\mu^{2}_{c(s)}}\operatorname{Tr}(\mathbf{K}^{2}e ^{-2\mathbf{K}(\Gamma_{T}-\Gamma_{s})})(R_{s}+\sigma^{2}/2)\mathrm{d}s.$ (23) $$

Note that the gradient flow term is identical to that of unclipped SGD. Since the (CCC) is satisfied, the integrated correction term is no larger than unclipped SGD and thus $R_{T}\leq R^{\infty}_{T}$. If the (CCC) occurs at some $t$, then in fact $R_{T}<R^{\infty}_{T}$. For the converse, one substitutes the learning rate schedule into (22) and sees it is
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.

Figure: Figure 3: The maximum over $c$ of the (CCC) for various values of the risk. Notice that the maximum value of the $\eqref{eq:clip_comparison_criterion}$ for both uniform and Gaussian noise is $1$, corresponding to unclipped SGD. Plots are computed with $\sigma=7,\ p=0.5$ where $p$ is a parameter in the Rademacher-like noise.
Refer to caption: x7.png

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 $\mu_{c}$ and $\nu_{c}$ (Appendix F).

###### Theorem 5 .

If $\mathbf{x}\sim N(0,\mathbf{K})$ and $\epsilon\sim N(0,\sigma^{2})$ then $\mu_{c}^{2}(R)/\nu_{c}(R)\leq 1$ 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 $\mathbf{x}\sim N(0,\mathbf{K})$ and the Rademacher-like noise as described in Theorem 3. Then, there is an $r>0$ depending on $p$ and $\lambda$ so that when $R_{t}\leq r$ 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, it also enhances its stability. This dual benefit suggests that in some settings clipping can be used to achieve both efficient and stable training.

###### Theorem 4 .

###### Proof.

###### Theorem 5 .

###### Theorem 6 .

### 5.3 A heuristic for the optimal clipping schedule

When we consider the max-(CCC) clipping schedule in light of our simplifications of $\mu_{c}$ and $\nu_{c}$ (Equation (10a)) we can arrive at a simple heuristic for the max-(CCC) optimal clipping schedule itself. Using Equation (10a), we see that

$$ $\displaystyle\frac{\kappa_{l}^{2}}{\kappa_{u}}\leq\frac{\mu_{c}^{2}(R_{t})}{ \nu_{c}(R_{t})}\leq\frac{\kappa_{u}^{2}}{\kappa_{l}}.$ (24) $$

This suggests that the upper bound might be attained by using the clipping schedule where $c(t)$ is proportional to $\sqrt{2R_{t}+\sigma^{2}}$ along with the approximate compensated learning rate

$$ $\displaystyle c^{a}(t)=\kappa\sqrt{2R_{t}+\sigma^{2}}$ $\displaystyle\eta^{a}(t,c)=\eta(t)\max\left(1,1/\kappa\right),$ (25) $$

where $\kappa\in\mathbb{R}^{+}$ is a *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 heuristic schedules from Equation (25). To obtain the max-(CCC) schedule we numerically optimize at each step in solving the ODE equation. In contrast, we tune only $\kappa$ to obtain our heuristic schedules.

As expected, we see no 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 optimal schedule. This heuristic shows promising potential to improve the training of clipped SGD with minimal tuning effort, but its thorough exploration and validation is left for future work.

Figure: (a) Gaussian noise
Refer to caption: x8.png

## 6 Conclusion

Our analysis of high-dimensional streaming settings shows that the effectiveness of clipping hinges on two key quantities: descent and variance reduction factors $\mu_{c}$ and $\nu_{c}$. The structure of the noise, model, and data then determine the dynamics of $\mu_{c}$ and $\nu_{c}$ 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 strong-enough 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 $\mu_{c}$ to $\nu_{c}$, 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 $\mu_{c}^{2}$ to $\nu_{c}$ exceeds $1$, 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-Woodfin et al., ); some of these results are likely adaptable to the clipped SGD setting. Additionally, important quantities from the analysis of
high-dimensional linear models can be measured in real networks (via linearization)
and can be used to analyze learning dynamics (Agarwala & Pennington, ).
We believe that the generalized versions of $\mu_{c}$ and $\nu_{c}$ will be interesting to study in real networks.

## Acknowledgements

We thank Lechao Xiao for his insightful feedback on the clarity and accuracy of our presentation, which significantly improved the manuscript. We also extend our gratitude to Courtney Paquette for her meticulous proofreading and assistance in shaping the final draft.

## Appendix A Full formulation of Theorem 1 with non-Gaussian data

To state the more general version of Theorem 1, we require some additional technical assumptions. Along with all of the assumptions described in Section 2 we will further assume:

###### Assumption 4 .

For some constant $\dutchcal{v}\geq 1$ and any fixed $\bm{\theta}$ with $\|\bm{\theta}\|\leq 1$, we have $\|\mathbf{x}^{T}\bm{\theta}\|_{\psi_{2}}\leq\dutchcal{v}$ and the data satisfy a Hanson-Wright inequality: for all $t\geq 0$ and any fixed matrix $\bm{B}$,

$$ $\mathbb{P}(|\mathbf{x}^{T}\bm{B}\mathbf{x}-\mathbb{E}[\mathbf{x}^{T}\bm{B} \mathbf{x}]|\geq t)\leq 2\exp\left(-\min\left\{\frac{t^{2}}{\dutchcal{v}^{4}\| \sqrt{\mathbf{K}}\bm{B}\sqrt{\mathbf{K}}\|^{2}_{F}},\frac{t}{\dutchcal{v}^{2} \|\sqrt{\mathbf{K}}\bm{B}\sqrt{\mathbf{K}}\|}\right\}\right),$ (26) $$

where $\mathbf{K}$ is the covariance of the data.

###### Assumption 5 .

$\mu$ and $\nu$ satisfy the following Lipschitz-like bounds for some constants $C_{\mu}$ and $C_{\nu}$.

$$ $|\mu(x)-\mu(y)|\leq C_{\mu}\frac{|\mathcal{R}(x)-\mathcal{R}(y)|}{\min_{z\in\{ x,y\}}\mathcal{R}(z)}$ (27) $$

$$ $|\nu(x)\mathcal{P}(x)-\nu(y)\mathcal{P}(y)|\leq C_{\nu}\left(1+\frac{\sigma}{ \sqrt{\mathcal{R}(x)+\mathcal{R}(y)}}\right)|\mathcal{R}(x)-\mathcal{R}(y)|$ (28) $$

where $\mathcal{R}$ is the risk.

We may now state our more general version of Theorem 1.
Here we use $\overline{c}=\max_{t}c(t)$ and $\overline{\eta}=\max_{t}\eta(t)$.

###### Theorem 7 .

There is a constant $\mathcal{C}=\mathcal{C}(\dutchcal{v},(n/d),c,\eta,(1+\|V_{0}\|^{2}))$ and a constant $c=c(\dutchcal{v})$ so that for any $1\leq u\leq cd$

$$ $\sup_{0\leq k\leq n}\left\|\begin{bmatrix}\mathcal{R}(\bm{\theta}_{k})\\ \mathcal{D}(\bm{\theta}_{k})\end{bmatrix}-\begin{bmatrix}\mathcal{R}(\bm{ \Theta}_{k/d})\\ \mathcal{D}(\bm{\Theta}_{k/d})\end{bmatrix}\right\|\leq\mathcal{C}\exp\left( \int_{0}^{n/d}\frac{C_{\nu}\eta^{2}(s)\sigma\,\mathrm{d}s}{\sqrt{\mathcal{R}( \bm{\Theta}_{s})+\mathcal{R}(\bm{\theta}_{sd})}}\right)u\log(d)d^{-1/2},$ (29) $$

with probability at least $1-e^{-u}$ and provided the right hand side is less than $1$. The coefficient $\mathcal{C}$ can be bounded by

$$ $\mathcal{C}\leq C\sqrt{n/d}\overline{\eta}\dutchcal{v}^{2}((1+\|V_{0}\|^{2}) \dutchcal{v}^{2}+c^{2}\sqrt{n/d})\exp\left(C\times(1+C_{\mu})\max\{\overline{ \eta},\overline{\eta}^{2}\}(n/d)\right)$ $$

for an absolute constant $C>0.$

We note that when $\sigma=0$ (so there is no noise) we arrive at the simpler conclusion that

$$ $\sup_{0\leq k\leq n}\left\|\begin{bmatrix}\mathcal{R}(\bm{\theta}_{k})\\ \mathcal{D}(\bm{\theta}_{k})\end{bmatrix}-\begin{bmatrix}\mathcal{R}(\bm{ \Theta}_{k/d})\\ \mathcal{D}(\bm{\Theta}_{k/d})\end{bmatrix}\right\|=\mathcal{O}(d^{-1/2}).$ $$

We note also that if $\eta(s)\equiv\eta$, the risk will be bounded below by a constant that depends only on $\eta,c,\sigma$ with high probability (and provided there is no warm start), and hence again this coefficient can be bounded with high probability in a similar way to $\mathcal{C}$. Moreover, for any desired $d$-independent risk threshold $R_{0}$, if one makes $d$ sufficiently large, then with very high probability, two risk curves will agree up to the point they cross below this risk threshold.

###### Assumption 4 .

###### Assumption 5 .

###### Theorem 7 .

## Appendix B Proof of main theorems

In this section we prove both Theorem 1 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 5.

It is a standard fact that the Hanson-Wright inequality is satisfied for Gaussians Vershynin ().

Let $z$ be standard Gaussian then recall from (9),

$$ $\displaystyle\mu_{c}(\bm{\theta})$ $\displaystyle=\mathbb{P}(|\left\langle\mathbf{x},\bm{\theta}-{\bm{\theta}^{*}} \right\rangle|\leq c)$ (30) $\displaystyle=\mathbb{P}(|\sqrt{2\mathcal{R}(\bm{\theta})}z-\epsilon|\leq c).$ (31) $$

With a slight abuse of notation, we condition on $\epsilon$ and use $I=(\epsilon-c,\epsilon+c)$ to express

$$ $\displaystyle|\mu_{c}(\bm{\theta}_{1})-\mu_{c}(\bm{\theta}_{2})|$ $\displaystyle=\left|\mathbb{P}\left(z\in\frac{I}{\sqrt{2\mathcal{R}(\bm{\theta }_{1})}}\bigg{|}\,\epsilon\right)-\mathbb{P}\left(z\in\frac{I}{\sqrt{2\mathcal {R}(\bm{\theta}_{2})}}\bigg{|}\,\epsilon\right)\right|$ (32) $\displaystyle\leq\left|\mathbb{P}\left(z\leq\frac{c+\epsilon}{\sqrt{\mathcal{R }(\bm{\theta}_{1})}}\bigg{|}\,\epsilon\right)-\mathbb{P}\left(z\leq\frac{c+ \epsilon}{\sqrt{\mathcal{R}(\bm{\theta}_{2})}}\bigg{|}\,\epsilon\right)\right|$ (33) $\displaystyle\quad+\left|\mathbb{P}\left(z\leq\frac{c-\epsilon}{\sqrt{\mathcal {R}(\bm{\theta}_{1})}}\bigg{|}\,\epsilon\right)-\mathbb{P}\left(z\leq\frac{c- \epsilon}{\sqrt{\mathcal{R}(\bm{\theta}_{2})}}\bigg{|}\,\epsilon\right)\right|.$ (34) $$

Without loss of generality, we assume $c+\epsilon/\mathcal{R}(\bm{\theta}_{2})\leq c+\epsilon/\mathcal{R}(\bm{\theta}
_{1})$, then the former term may be bounded by

$$ $\displaystyle\left|\mathbb{P}\left(z\leq\frac{c+\epsilon}{\sqrt{\mathcal{R}( \bm{\theta}_{1})}}\bigg{|}\,\epsilon\right)-\mathbb{P}\left(z\leq\frac{c+ \epsilon}{\sqrt{\mathcal{R}(\bm{\theta}_{2})}}\bigg{|}\,\epsilon\right)\right|$ (35) $\displaystyle\leq\frac{|c+\epsilon|}{2\sqrt{\pi}}e^{-\frac{(c+\epsilon)^{2}}{4 \mathcal{R}(\bm{\theta}_{1})}}\left|\frac{\sqrt{\mathcal{R}(\bm{\theta}_{1})}- \sqrt{\mathcal{R}(\bm{\theta}_{2})}}{\sqrt{\mathcal{R}(\bm{\theta}_{1}) \mathcal{R}(\bm{\theta}_{2})}}\right|.$ (36) $$

Maximizing $te^{-t^{2}/4\mathcal{R}(\bm{\theta}_{1})}$ in $t$ yields

$$ $\displaystyle\left|\mathbb{P}\left(z\leq\frac{c+\epsilon}{\sqrt{\mathcal{R}( \bm{\theta}_{1})}}\bigg{|}\,\epsilon\right)-\mathbb{P}\left(z\leq\frac{c+ \epsilon}{\sqrt{\mathcal{R}(\bm{\theta}_{2})}}\bigg{|}\,\epsilon\right)\right|$ $\displaystyle\leq\frac{|\mathcal{R}(\bm{\theta}_{1})-\mathcal{R}(\bm{\theta}_{ 2})|}{\sqrt{2\pi\mathcal{R}(\bm{\theta}_{2})}(\sqrt{\mathcal{R}(\bm{\theta}_{1 })}+\sqrt{\mathcal{R}(\bm{\theta}_{2})})}$ (37) $\displaystyle\leq C_{\mu}\frac{|\mathcal{R}(\bm{\theta}_{1})-\mathcal{R}(\bm{ \theta}_{2})|}{\min_{z\in\{\bm{\theta}_{1},\bm{\theta}_{2}\}}\mathcal{R}(z)}.$ (38) $$

By applying the same argument to the latter term of (34), we see that

$$ $|\mu(\bm{\theta}_{1})-\mu(\bm{\theta}_{2})|\leq C_{\mu}\frac{|\mathcal{R}(\bm{ \theta}_{1})-\mathcal{R}(\bm{\theta}_{2})|}{\min_{z\in\{\bm{\theta}_{1},\bm{ \theta}_{2}\}}\mathcal{R}(z)},$ (39) $$

as desired.

To show (28), let us first first define $f(\xi,\epsilon)=\mathbb{E}\left[\operatorname{clip}_{c}^{2}\left(\xi z-
\epsilon\right)\bigg{|}\,\epsilon\right]]$. Upon conditioning on $\epsilon$, it follows that $\nu(\bm{\theta})\mathcal{P}(\bm{\theta})=f\left(\sqrt{2\mathcal{R}(x)},
\epsilon\right)$. Differentiating with respect to $\xi$, we see that

$$ $\displaystyle\frac{\partial}{\partial\xi}f(\xi)$ $\displaystyle=\mathbb{E}\left[2z\operatorname{clip}_{c}(\xi z-\epsilon) \mathbbm{1}_{|\xi z-\epsilon|\leq c}\right]$ (40) $\displaystyle=\frac{2}{\sqrt{2\pi}}\int_{(-c+\epsilon)/\xi}^{(c+\epsilon)/\xi} (\xi z-\epsilon)ze^{-z^{2}/2}\,dz$ (41) $\displaystyle=\frac{-2}{\sqrt{2\pi}}\left[(\xi z-\epsilon)e^{-z^{2}/2}\bigg{|} _{z=(-c+\epsilon)/\xi}^{z=(c+\epsilon)/\xi}\right]+2\xi\mathbb{P}\left(|\xi z- \epsilon|\leq c|\,\epsilon\right)$ (42) $\displaystyle=\frac{-2}{\sqrt{2\pi}}\left[(c-\epsilon+\epsilon)e^{-(c-\epsilon )^{2}/2\xi^{2}}+(c+\epsilon-\epsilon)e^{-(c+\epsilon)^{2}/2\xi^{2}}\right]$ (43) $\displaystyle\quad+2\xi\mathbb{P}\left(|\xi z-\epsilon|\leq c|\,\epsilon\right).$ (44) $$

Upon noting that
$\xi\left(\frac{c+\epsilon}{\xi\sqrt{2\pi}}e^{-\frac{(c+\epsilon)^{2}}{2\xi^{2}
}}\right)\leq\xi C$, for some absolute constant $C>0$ we may bound the absolute value of $\frac{\partial}{\partial\xi}f(\xi,\epsilon)$ by

$$ $\left|\frac{\partial}{\partial\xi}f(\xi,\epsilon)\right|\leq 4C\xi+2|\epsilon|.$ (45) $$

Hence, without loss of generality, if we assume that $\sqrt{2\mathcal{R}(\bm{\theta}_{1})}\leq\sqrt{2\mathcal{R}(\bm{\theta}_{2})}$ and conditioning on $\epsilon$, we obtain

$$ $\displaystyle|\nu(\bm{\theta}_{1})\mathcal{P}(\bm{\theta}_{1})-\nu(\bm{\theta} _{2})\mathcal{P}(\bm{\theta}_{2})|$ $\displaystyle\leq\int_{\sqrt{2\mathcal{R}(\bm{\theta}_{1})}}^{\sqrt{2\mathcal{ R}(x_{2})}}\left|\frac{\partial}{\partial\xi}f(\xi,\epsilon)\right|\,d\xi$ (46) $\displaystyle\leq 2c\left|\mathcal{R}(\bm{\theta}_{1})-\mathcal{R}(\bm{\theta} _{2})\right|+2\mathbb{E}|\epsilon|\left|\sqrt{2\mathcal{R}(\bm{\theta}_{1})}- \sqrt{2\mathcal{R}(\bm{\theta}_{2})}\right|,$ (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 $v_{k}=\bm{\theta}_{k}-{\bm{\theta}^{*}}$. We shall also write $\tilde{\eta}_{k}=\eta(k/d)$ so that $\tilde{\eta}_{k}/d=\eta_{k}$. Before proving theorem 7 we first show a series of lemmas following closely the proof techniques of Collins-Woodfin & Paquette ().

###### Notation 1 .

It is helpful to formulate some results in terms of tensor products. We use $x\otimes y$ to refer the tensor product of $x$ and $y$.

###### Notation 2 .

We use $C$ to refer to a generic constant which may change from line to line.

With a slight abuse of notation, extend $\{v_{k}\}_{k\geq 0}$ to be indexed by continuous time $t\in\mathbb{R}^{+}$ by $v_{t}=v_{\lfloor t\rfloor}$. Let $q$ be a quadratic. Via its Taylor expansion, we may write the updates of $q$ by

$$ $q(v_{k+1})-q(v_{k})=-\frac{\tilde{\eta}_{k}}{d}\nabla q(v_{k})^{T} \operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})+\frac{\tilde{\eta}_{ k}^{2}}{2d^{2}}\left\langle\nabla^{2}q,(\operatorname{clip}_{c\sqrt{d}}(\ell_{ k}\mathbf{x}_{k+1}))^{\otimes 2}\right\rangle.$ (48) $$

This update can be decomposed into errors, martingale parts and predictable parts

$$ $\displaystyle q(v_{k+1})-q(v_{k})$ $\displaystyle=-\frac{\tilde{\eta}_{k}}{d}\mu(v_{k})\nabla q(v_{k})^{T}\mathbf{ K}v_{k}+\frac{\tilde{\eta}_{k}^{2}}{d^{2}}\nu(v_{k})\mathcal{P}(v_{k}) \operatorname{Tr}(\nabla^{2}q\mathbf{K})$ (49) $\displaystyle+\Delta\mathcal{M}_{k}^{lin}+\Delta\mathcal{M}_{k}^{quad}+\Delta E _{k}.$ $$

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 a manifold of functions which will close under the gradient and Hessian operations above. Choose this family of functions to be

$$ $Q=\{v\mapsto v^{T}R(z;\mathbf{K})v,\quad\forall z\in\Omega\}$ (50) $$

where $\Omega$ is a circle of radius $2$ and thus enclosing the eigenvalues of $\mathbf{K}$. We further define the stopping time $\tau$ for a parameter $M$.

$$ $\tau=\inf\{k:\|v_{k}\|\geq M\}\cup\{td:\|V_{t}\|\geq M\},$ (51) $$

and the stopped processes,

$$ $\displaystyle v_{k}^{\tau}=v_{k\wedge\tau}$ $\displaystyle V_{t}^{\tau}=V_{t\wedge(\tau/d)}.$ (52) $$

We will first prove Theorem 7 for the stopped process $\{v_{k}^{\tau}\}_{k\geq 0}$ and $\{V_{t}^{\tau}\}_{t\geq 0}$ and then bound the probability that $\tau\leq n$.

###### Lemma 1 .

There is an absolute constant $C>0$ so that

$$ $\displaystyle\sup_{0\leq t\leq n/d}$ $\displaystyle\left|q(v_{td}^{\tau})-q(V_{t}^{\tau})\right|\leq\sup_{0\leq t \leq n/d}\left(|\mathcal{M}_{td}^{\tau,lin}|+|\mathcal{M}_{td}^{\tau,quad}|+|E _{td}^{\tau}|+|\mathcal{M}_{t}^{\tau,SDE}|\right)$ (53) $\displaystyle+\int_{0}^{n/d}\left(C\max\{\overline{\eta},\overline{\eta}^{2}\} +\frac{C_{\nu}{\eta}^{2}(s)(\mathfrak{m}_{s}+\sigma)}{\mathfrak{m}_{s}}+2{C_{ \mu}}\overline{\eta}\right)\sup_{q\in Q}\left|q(v_{sd}^{\tau})-q(V_{s}^{\tau}) \right|\mathrm{d}s,$ (54) $$

where $\mathfrak{m}_{s}$ is sum of risks
$\mathfrak{m}_{s}=\sqrt{\mathcal{R}(\bm{\theta}_{sd}^{\tau})+\mathcal{R}(\bm{
\Theta}_{sd}^{\tau})}.$

###### Proof.

When context is clear, we will write $R(z;\mathbf{K})=R(z)$.
We begin by noting that for all $q\in Q$
since for eigenvalues and eigenvectors $(\lambda_{i},\omega_{i})$ of $\mathbf{K}$,

$$ $\left|\nabla q(v)^{T}\mathbf{K}v\right|=\left|\sum_{i}\frac{\lambda_{i}}{( \lambda_{i}-z)}\langle v,\omega_{i}\rangle^{2}\right|\leq\sum_{i}{\lambda_{i}} \langle v,\omega_{i}\rangle^{2}=\langle\mathbf{K},v^{\otimes 2}\rangle.$ $$

The same bound holds for the gradient term, and we conclude that for all $q\in Q$

$$ $|\nabla q(v)^{T}\mathbf{K}v|\leq 2\mathcal{R}(v+{\bm{\theta}^{*}}).$ $$

Given a $g\in Q$, by (49), we obtain

$$ $\displaystyle g(v_{t}^{\tau})$ $\displaystyle=g(v_{0}^{\tau})-\int_{0}^{t}\frac{\eta(s)}{d}\mu(v_{s}^{\tau}) \nabla g(v_{s}^{\tau})^{T}\mathbf{K}v_{s}^{\tau}\mathrm{d}s+\int_{0}^{t}\frac{ \eta^{2}(s)}{d^{2}}\nu(v_{s}^{\tau})\mathcal{P}(v_{s}^{\tau})\operatorname{Tr} (\mathbf{K}\nabla^{2}g)\mathrm{d}s$ (55) $\displaystyle\quad+\mathcal{M}_{t}^{\tau,lin}+\mathcal{M}_{t}^{\tau,quad}+E_{t }^{\tau}.$ $$

Similarly, by Itô’s lemma

$$ $\displaystyle g(V_{t}^{\tau})=g(V_{0}^{\tau})$ $\displaystyle-\int_{0}^{t}\eta(s)\mu(V_{s}^{\tau})\nabla g(V_{s}^{\tau})^{T} \mathbf{K}V_{s}^{\tau}\mathrm{d}s$ (56) $\displaystyle+\int_{0}^{t}\frac{\eta^{2}(s)}{d^{2}}\nu(V_{s}^{\tau})\mathcal{P }(V_{s}^{\tau})\operatorname{Tr}(\mathbf{K}\nabla^{2}g)\mathrm{d}s+\mathcal{M} _{t}^{\tau,SDE},$ $$

where

$$ $\mathcal{M}_{t}^{\tau,SDE}=\int_{0}^{t}\frac{\eta(s)}{\sqrt{d}}\nabla g(V_{s}^ {\tau})^{T}\sqrt{2\mathbf{K}\nu(V_{s}^{\tau})\mathcal{P}(V_{s}^{\tau})}dB_{s}.$ (57) $$

First, we will show that for any $g\in Q$ and any $x_{1},x_{2}\in\mathbb{R}{d}$

$$ $|\nabla g(x_{1})^{T}\mathbf{K}x_{1}-\nabla g(x_{2})^{T}\mathbf{K}x_{2}|\leq 4 \sup_{g\in Q}|g(x_{1})-g(x_{2})|.$ (58) $$

The statement is obvious if $g(x)=q(x)$. If $g(x)=\nabla q(x)^{T}R(z)x$ then $\nabla g(x)=\nabla^{2}qR(z)x+R(z)\nabla q(x)$ and using Cauchy’s integral formula we can see,

$$ $\displaystyle\nabla g(x)^{T}\mathbf{K}x$ $\displaystyle=x^{T}R(z)\nabla^{2}q\mathbf{K}x+\nabla q(x)^{T}R(z)\mathbf{K}x$ (59) $\displaystyle=-\underbrace{\frac{1}{2\pi i}\oint_{\Omega}yx^{T}R(z)\nabla^{2} qR(y)xdy}_{T_{1}}-\underbrace{\frac{1}{2\pi i}\oint_{\Omega}\nabla q(x)^{T}R(z )xdz}_{T_{2}}+\underbrace{z\nabla q(x)^{T}R(z)x}_{T_{3}}.$ (60) $$

For any $z$ on $\Omega$ we have that $\|R(z)\|_{op}\leq 1$. Furthermore, the arc-length of $\Omega$ is $8\pi$.
Therefore, we have

$$ $\displaystyle|T_{1}(x_{1})-T_{1}(x_{2})|$ $\displaystyle\leq\frac{1}{2\pi}\oint_{\Omega}|y|\left|x_{1}^{T}R(z)\nabla^{2} qR(y)x_{1}-x_{2}^{T}R(z)\nabla^{2}qR(y)x_{2}\right|dy$ (61) $\displaystyle\leq 8\sup_{g\in Q}|g(x_{1})-g(x_{2})|,$ (62) $$

and

$$ $\displaystyle|T_{2}(x_{1})-T_{2}(x_{2})|$ $\displaystyle\leq\frac{1}{2\pi}\oint_{\Omega}|\nabla q(x_{1})^{T}R(z)x_{1}- \nabla q(x_{2})^{T}R(z)x_{2}|dz$ (63) $\displaystyle\leq 4\sup_{g\in Q}|g(x_{1})-g(x_{2})|.$ (64) $$

If $g(x)=x^{T}R(z)\nabla^{2}qR(y)x$, then using the identity $R(z)\mathbf{K}=\mathbf{I}+zR(z)$,

$$ $\displaystyle\nabla g(x)^{T}\mathbf{K}x$ $\displaystyle=x^{T}R(y)\nabla^{2}qx+zx^{T}R(y)\nabla^{2}qR(z)x+x^{T}R(z)\nabla ^{2}qx+yx^{T}R(z)\nabla^{2}qR(y)x.$ (65) $$

By the same methods as above, we see

$$ $\displaystyle|\nabla g(x_{1})^{T}\mathbf{K}x_{1}-\nabla g(x_{2})^{T}\mathbf{K} x_{2}|$ $\displaystyle\leq 24\sup_{g\in Q}|g(x_{1})-g(x_{2})|.$ (66) $$

It is simple to account for the presence of the functions $\mu$ and $\nu$.
Using Assumptions 5

$$ $\displaystyle\left|\nu(v_{td}^{\tau})\mathcal{P}(v_{td}^{\tau})-\nu(V_{t}^{ \tau})\mathcal{P}(V_{td}^{\tau})\right|\leq\sup_{g\in Q}|g(v_{td}^{\tau})-g(V_ {t}^{\tau})|\frac{C_{\nu}(\mathfrak{m}_{t}+\sigma)}{\mathfrak{m}_{t}}.$ (67) $$

As for $\mu$, adding and subtracting $\mu(v_{td}^{\tau})g(V_{td}^{\tau})$, using $\mu\leq 1$ and $g(V_{td}^{\tau})\leq 2\mathcal{R}(\bm{\Theta}_{td}^{\tau})$

$$ $|\mu(v_{td}^{\tau})g(v_{td}^{\tau})-\mu(V_{t}^{\tau})g(V_{t}^{\tau})|\leq\sup_ {g\in Q}|g(v_{td}^{\tau})-g(V_{t}^{\tau})|\left(1+\frac{C_{\mu}2\mathcal{R}( \bm{\Theta}_{td}^{\tau})}{\min\{\mathcal{R}(\bm{\theta}_{td}^{\tau}),\mathcal{ R}(\bm{\Theta}_{td}^{\tau})\}}\right).$ (68) $$

Note we could have also added and subtracted $\mu(V_{td}^{\tau})g(v_{td}^{\tau})$, and so picking whichever is better, we arrive at

$$ $|\mu(v_{td}^{\tau})g(v_{td}^{\tau})-\mu(V_{t}^{\tau})g(V_{t}^{\tau})|\leq\sup_ {g\in Q}|g(v_{td}^{\tau})-g(V_{t}^{\tau})|\left(1+2C_{\mu}\right).$ $$

This completes the claim.

∎

###### Lemma 2 .

There is an absolute constant $C>0$
so that
for any quadratic $q$ with $\|q\|_{C^{2}}\leq 1$
any $n\leq dT$ with $T\geq 1$,
any $1\leq u\leq d$,

$$ $\displaystyle\left|\sup_{0\leq k\leq n}\mathcal{M}_{k}^{\tau,lin}\right|$ $\displaystyle\leq C\sqrt{T}\overline{\eta}(2+M)^{2}\dutchcal{v}^{2}d^{-1/2}u,$ (69) $\displaystyle\left|\sup_{0\leq k\leq n}\mathcal{M}_{t}^{\tau,quad}\right|$ $\displaystyle\leq C\sqrt{T}\overline{\eta}c^{2}\dutchcal{v}^{2}d^{-1/2}u,$ (70) $\displaystyle\left|\sup_{0\leq k\leq n}E_{t}^{\tau}\right|$ $\displaystyle\leq CT\overline{\eta}(2+M)^{2}\dutchcal{v}^{4}d^{-1/2},$ (71) $\displaystyle\left|\sup_{0\leq t\leq n/d}\mathcal{M}_{t}^{\tau,SDE}\right|$ $\displaystyle\leq C\sqrt{T}\overline{\eta}(2+M)^{2}\dutchcal{v}^{2}d^{-1/2}u.$ (72) $$

with probability at least $1-e^{-u}.$

The proof of lemma 2 is deferred to appendix B.3.

###### Lemma 3 .

There is an absolute constant $C>0$ so that for any $m>0$, there exists a $\bar{Q}\subseteq Q$ with $|\bar{Q}|\leq Cd^{2m}$ such that for all $q\in Q$, there is some $\bar{q}\in\bar{Q}$ that satisfies $\|\bar{q}-q\|_{C^{2}}\leq d^{-2m}$.

###### Proof.

With assumption 2, the arc length of $\Omega$ is fixed independent of $d$. Thus, we may construct $\bar{Q}$ by restricting $Q$ to a minimal $d^{-2m}$-net of $\Omega$.
∎

The proof of Theorem 7 now follows easily from these results. By Lemmas 1 and 2,
there is an absolute constant $C$ so that for any $u\geq 1$

$$ $|\bar{q}(v_{td}^{\tau})-\bar{q}(V_{t}^{\tau})|\leq C\sqrt{T}\overline{\eta} \dutchcal{v}^{2}d^{-1/2}\left((2+M)^{2}\dutchcal{v}^{2}u+c^{2}\sqrt{T}\right)+ \int_{0}^{t}\mathfrak{L}_{s}\max_{q\in\bar{Q}}|q(v_{sd}^{\tau})-q(V_{s}^{\tau} )|\mathrm{d}s,$ (73) $$

on an event of probability at least $1-e^{-u}$, and where we have set

$$ $\mathfrak{L}_{s}\coloneqq\left(C\max\{\overline{\eta},\overline{\eta}^{2}\}+ \frac{C_{\nu}{\eta}^{2}(s)(\mathfrak{m}_{s}+\sigma)}{\mathfrak{m}_{s}}+2{C_{ \mu}}\overline{\eta}\right).$ $$

Then, from Lemma 3 with $m=1$
and increasing the absolute constant $C>0$
so that for all $t\leq T$

$$ $\sup_{q\in Q}|q(v_{td}^{\tau})-q(V_{t}^{\tau})|\leq C\sqrt{T}\overline{\eta} \dutchcal{v}^{2}d^{-1/2}\left((2+M)^{2}\dutchcal{v}^{2}u+c^{2}\sqrt{T}\right)+ \int_{0}^{t}\mathfrak{L}_{s}\max_{q\in\bar{Q}}|q(v_{sd}^{\tau})-q(V_{s}^{\tau} )|\mathrm{d}s,$ (74) $$

except on an event of probability $Cd^{8}e^{-u}.$

An application of Gronwall’s inequality gives

$$ $\sup_{q\in Q}\sup_{0\leq t\leq T}|q(v_{td}^{\tau})-q(V_{t}^{\tau})|\leq C\sqrt {T}\overline{\eta}\dutchcal{v}^{2}d^{-1/2}\left((2+M)^{2}\dutchcal{v}^{2}u+c^{ 2}\sqrt{T}\right)\exp\left(\int_{0}^{T}\mathfrak{L}_{s}\mathrm{d}s\right).$ (75) $$

Now we note that by contour integration, both the risk $v\mapsto\langle\mathbf{K},v^{\otimes 2}\rangle$ and suboptimality $v\mapsto\|v\|^{2}$ both can be estimated by

$$ $\max\{\left|\|\bm{\theta}_{td}^{\tau}-{\bm{\theta}^{*}}\|^{2}-\|\bm{\Theta}_{ td}^{\tau}-{\bm{\theta}^{*}}\|^{2}\right|,2\left|\mathcal{R}(\bm{\theta}_{td}^ {\tau})-\mathcal{R}(\bm{\Theta}_{td}^{\tau})\right|\}\leq 4\sup_{q\in Q}|q(v_{ td}^{\tau})-q(V_{t}^{\tau})|,$ $$

proving our claim for the stopped processes. Now, it will be shown that with overwhelming $\tau$ does not occur for $n\leq dT$. It suffices to show that following lemma.

###### Lemma 4 .

There is an absolute constant $C>0$ so that for all $r\geq 0$
and all $T\geq 0$
with probability at least $1-2e^{-r^{2}/2}$
for all $0\leq s\leq T$,

$$ $e^{-C\max\{\overline{\eta},\overline{\eta}^{2}\}s-C\overline{\eta}\sqrt{T}d^{- 1/2}r}\leq\frac{\|V_{s}\|^{2}}{\|V_{0}\|^{2}}\leq e^{C\max\{\overline{\eta}, \overline{\eta}^{2}\}s+C\overline{\eta}\sqrt{T}d^{-1/2}r}.$ (76) $$

###### Proof.

Consider $\varphi(V_{t})=\log(1+\|V_{t}\|^{2})$. Then,

$$ $\displaystyle\mathrm{d}\varphi(V_{t})=$ $\displaystyle-2\eta(t)\frac{\mu(X_{t})}{1+\|V_{t}\|^{2}}\nabla\mathcal{P}(V_{t })^{T}V_{t}\mathrm{d}t+\frac{\eta^{2}(t)2\nu(V_{t})\mathcal{P}(V_{t})}{1+\|V_{ t}\|^{2}}\frac{\operatorname{Tr}(\mathbf{K})}{d}\mathrm{d}t$ (77) $\displaystyle-\frac{2\eta^{2}(t)\nu(V_{t})\mathcal{P}(V_{t})}{d(1+\|V_{t}\|^{2 })^{2}}\left\langle V_{t}\otimes V_{t},\mathbf{K}\right\rangle\mathrm{d}t+ \frac{2\eta(t)\sqrt{2\nu(V_{t})\mathcal{P}(V_{t})}}{\sqrt{d}(1+\|V_{t}\|^{2})} \left\langle V_{t},\sqrt{\mathbf{K}}\mathrm{d}B_{t}\right\rangle.$ $$

Note that, $\operatorname{Tr}(\mathbf{K})/d=\|\mathbf{K}\|=1$ so the drift terms are all bounded above and below by absolute constants multiplied by $\max\{\overline{\eta},\overline{\eta}^{2}\}$. Meanwhile, the quadratic variation is bounded by

$$ $\displaystyle\langle\varphi(V)\rangle_{t}$ $\displaystyle=\int_{0}^{t}\frac{8\eta^{2}(s)}{d}\nu(V_{s})\mathcal{P}(V_{s}) \frac{\left\langle V_{s}\otimes V_{s},\mathbf{K}\right\rangle}{(1+\|V_{s}\|^{2 })^{2}}\mathrm{d}s$ (78) $\displaystyle\leq 8C\frac{\overline{\eta}^{2}}{d}t,$ (79) $$

for $C$ an absolute constant.

And so, for all $r\geq 0$ , setting $f(t)$ to be the integrated drift terms from (77)

$$ $\mathbb{P}(\max_{1\leq t\leq T}|\varphi(V_{t})-f(t)|\geq C\overline{\eta}\sqrt {T}/\sqrt{d}r)\leq 2\exp(-r^{2}/2).$ (80) $$

This implies the claim immediately as $|f(t)|\leq C\max\{\overline{\eta},\overline{\eta}^{2}\}t$ for all $t.$
∎

We can now conclude the main theorem, noting that if for some fixed $T$, if we pick $\tilde{M}$ so that

$$ $(2+\tilde{M})^{2}=\max\left\{C(1+\|V_{0}\|^{2})\exp\left(\int_{0}^{T}Cs\right) ,(2+2)^{2}\right\}$ $$

then with probability at least $1-e^{-d}$, $\|V_{t}\|$ remains below $\tilde{M}$ up time $T$. As single steps of clipped SGD cannot increase the norm of $v_{k}$ by more than a factor of $2$ (with probability at least $1-e^{-cd}$), we conclude that if $\tau\leq Td$, using
(75)

$$ $M^{2}=\|v_{\tau}\|^{2}\leq 4(\tilde{M})^{2}+4C\sqrt{T}\overline{\eta}\dutchcal {v}^{2}d^{-1/2}\left((2+M)^{2}\dutchcal{v}^{2}u+c^{2}\sqrt{T}\right)\exp\left( \int_{0}^{T}\mathfrak{L}_{s}\mathrm{d}s\right).$ $$

Provided $M\geq 2$ and provided that

$$ $4C\sqrt{T}\overline{\eta}\dutchcal{v}^{2}\left(\dutchcal{v}^{2}u+c^{2}\sqrt{T} \right)\exp\left(\int_{0}^{T}\mathfrak{L}_{s}\mathrm{d}s\right)d^{-1/2}\leq \frac{1}{8},$ (81) $$

we have

$$ $M^{2}\leq 4(\tilde{M})^{2}+\frac{1}{2}M^{2},$ $$

hence we conclude that

$$ $M\leq\sqrt{8}\tilde{M}.$ $$

So if we pick $M$ larger than $\sqrt{8}\tilde{M}$ (which is larger than $2$ by how $\tilde{M}$ was picked) we conclude that $\tau>Td$.

###### Notation 1 .

###### Notation 2 .

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

### B.3 Bounding martingales and errors

###### Lemma 5 .

Martingale Bernstein inequality
For $\{M_{k}\}_{k=0}^{N}$ a martingale, we define

$$ $\sigma_{k,p}=\inf\{t>0:\mathbb{E}[\exp(|M_{k}-M_{k-1}|^{p}/t^{p})|\mathscr{F}_ {k-1}]\leq 2\},$ (82) $$

then there exists an absolute constant $C>0$ such that for all $t>0$

$$ $\mathbb{P}\left(\sup_{1\leq k\leq N}|M_{k}-\mathbb{E}[M_{0}]|>t\right)\leq 2 \exp\left(-\min\left\{\frac{t}{C\max\sigma_{k,1}},\frac{t^{2}}{C\sum_{i=1}^{N} \sigma_{i,1}^{2}}\right\}\right).$ (83) $$

This section is dedicated to bounding the martingale and error terms present in Equations (55) and (56). These terms are

$$ $\displaystyle\Delta\mathcal{M}_{k+1}^{\tau,lin}$ $\displaystyle:=-\frac{\tilde{\eta}_{k}}{d}\nabla q(v_{k}^{\tau})^{T} \operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})+\frac{\tilde{\eta}_{ k}}{d}\nabla q(v_{k}^{\tau})^{T}\mathbb{E}[\operatorname{clip}_{c\sqrt{d}}( \ell_{k}\mathbf{x}_{k+1})|\mathscr{F}_{k}]$ (84) $\displaystyle=-\frac{\tilde{\eta}_{k}}{d}\nabla q(v_{k}^{\tau})^{T} \operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})+\frac{\tilde{\eta}_{ k}}{d}\nabla q(v_{k}^{\tau})^{T}\mathbf{K}v_{k}^{\tau}\mu(v_{k}^{\tau})-\Delta E _{k}^{\tau,lin},$ (85) $$

and

$$ $\displaystyle\Delta\mathcal{M}_{k+1}^{\tau,quad}$ $\displaystyle:=\frac{\tilde{\eta}_{k}}{2d^{2}}\left\langle\nabla^{2}q, \operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})^{\otimes 2}\right \rangle-\frac{\tilde{\eta}_{k}}{2d^{2}}\left\langle\nabla^{2}q,\mathbb{E}\left [\operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})^{\otimes 2}\right]\right\rangle$ (86) $\displaystyle=\frac{\tilde{\eta}_{k}}{2d^{2}}\left\langle\nabla^{2}q, \operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})^{\otimes 2}\right \rangle-\frac{\tilde{\eta}_{k}}{d^{2}}\left\langle\mathbf{K},\nabla^{2}q\right \rangle\nu(v_{k})\mathcal{P}(v_{k})-\Delta E_{k}^{\tau,quad},$ (87) $$

where we recall $\ell_{k}=\left\langle\mathbf{x}_{k+1},v_{k}^{\tau}\right\rangle-\epsilon_{k+1}$. The error increment has contributions from both the linear—in $\tilde{\eta}_{k}$—and quadratic terms. More precisely,

$$ $\Delta E_{k}^{\tau}=\Delta E_{k}^{\tau,lin}+\Delta E_{k}^{\tau,quad},$ (88) $$

where

$$ $\Delta E_{k}^{\tau,lin}=-\frac{\tilde{\eta}_{k}}{d}\nabla q(\bm{\theta}_{k}^{ \tau})^{T}\mathbb{E}[\operatorname{clip}_{c\sqrt{d}}(\mathbf{x}_{k+1}\ell_{k}) -\mathbf{x}_{k+1}\operatorname{clip}_{c}(\ell_{k})]$ $$

and

$$ $\Delta E_{k}^{\tau,quad}=\frac{\tilde{\eta}_{k}}{2d^{2}}\left(\mathbb{E}\left[ \left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle\ell_{k}^{2} \mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1}\|^{2}\leq c^{2}d}\right]-\left\langle \nabla^{2}q,\mathbf{K}\right\rangle\mathbb{E}\left[\ell_{k}^{2}\mathbbm{1}_{ \ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^{2}d}\right]\right).$ $$

###### Lemma 5 .

### B.4 Martingale for the linear terms

We’ll begin the proof for the linear terms in the increments. First, note that using the $\|q\|_{C^{2}}$ norm we can bound

$$ $\|\nabla q(x)\|\leq\|\nabla^{2}q\|\|x\|+\|\nabla q(0)\|\leq\|q\|_{C^{2}}(1+\|x \|).$ (89) $$

Thus,

$$ $|\nabla q(v_{k}^{\tau})^{T}\mathbf{K}v_{k}^{\tau}\mu(v_{k}^{\tau})|\leq(1+M).$ (90) $$

From Equation (134) in the following section, for an absolute constant $C>0$

$$ $|\Delta E_{k}^{\tau,lin}|\leq C(2+M)^{2}\overline{\eta}d^{-3/2}\dutchcal{v}^{3}.$ (91) $$

Meanwhile, we can get subexponential bounds for the former terms of (85),

$$ $\displaystyle-\frac{\tilde{\eta}_{k}}{d}\nabla q(v_{k}^{\tau})^{T} \operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})=$ $\displaystyle-\frac{\tilde{\eta}_{k}}{d}\nabla q(v_{k}^{\tau})^{T}\mathbf{x}_{ k+1}\ell_{k}\mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1}\|\leq c\sqrt{d}}$ (92) $\displaystyle-\frac{c\tilde{\eta}_{k}}{\sqrt{d}}\nabla q(v_{k}^{\tau})^{T} \frac{\ell_{k}\mathbf{x}_{k+1}}{\|\ell_{k}\mathbf{x}_{k+1}\|}\mathbbm{1}_{\| \ell_{k}\mathbf{x}_{k+1}\|>c\sqrt{d}}.$ (93) $$

So, by Assumptions 1 and 4, as well as Equation (89), we have

$$ $\displaystyle\left\|\nabla q(v_{k}^{\tau})^{T}\mathbf{x}_{k+1}\ell_{k}\mathbbm {1}_{\|\ell_{k}\mathbf{x}_{k+1}\|<c\sqrt{d}}\right\|_{\psi_{1}}$ $\displaystyle\leq\|\nabla q(v_{t}^{\tau})^{T}\mathbf{x}_{k+1}\ell_{k}\|_{\psi_ {1}}$ (94) $\displaystyle\leq\|\nabla q(v_{t}^{\tau})^{T}\mathbf{x}_{k+1}\|_{\psi_{2}}\| \ell_{k}\|_{\psi_{2}}$ (95) $\displaystyle\leq(1+M)\dutchcal{v}\times(2+M)\dutchcal{v}.$ (96) $$

Likewise,

$$ $\displaystyle\left\|c\sqrt{d}\nabla q(v_{k}^{\tau})^{T}\frac{\ell_{k}\mathbf{x }_{k+1}}{\|\ell_{k}\mathbf{x}_{k+1}\|}\mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1} \|>c\sqrt{d}}\right\|_{\psi_{1}}$ $\displaystyle\leq\left\|\nabla q(v_{k}^{\tau})^{T}\ell_{k}\mathbf{x}_{k+1} \mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1}\|>c\sqrt{d}}\right\|_{\psi_{1}}$ (97) $\displaystyle\leq\left\|\nabla q(v_{k}^{\tau})^{T}\ell_{k}\mathbf{x}_{k+1} \right\|_{\psi_{1}}$ (98) $\displaystyle\leq(2+M)^{2}\dutchcal{v}^{2}.$ (99) $$

Thus, for some absolute constant $C>0$

$$ $\sigma_{k,1}=\inf\{t>0:\mathbb{E}[\exp(|\Delta\mathcal{M}_{k}^{\tau,lin}|/t)| \mathscr{F}_{k-1}]\leq 2\}\leq C\frac{\overline{\eta}}{d}(2+M)^{2}\dutchcal{v} ^{2}\left(1+\frac{\dutchcal{v}}{\sqrt{d}}\right).$ (100) $$

for all $k$.
Hence once $\sqrt{d}\geq\dutchcal{v}$ we may further bound away this additional fraction incurring a further loss of a factor of $2$.
We may apply Lemma 5 to see that for all $t>1$, and some absolute constant $c>0$

$$ $\mathbb{P}\left(\sup_{1\leq k\leq n}|\mathcal{M}_{k}^{\tau,lin}-\mathbb{E}[ \mathcal{M}_{0}^{\tau,lin}]|>\overline{\eta}(2+M)^{2}\dutchcal{v}^{2}(n/d)t \right)\leq 2\exp\left(-cn\min\left\{t^{2},t\right\}\right).$ (101) $$

In the case that $n\leq dT$, this implies that there is an absolute constant so that for any $1\leq u\leq d$

$$ $\sup_{1\leq k\leq n}|\mathcal{M}_{k}^{\tau,lin}|\leq C\overline{\eta}(2+M)^{2} \dutchcal{v}^{2}\frac{\sqrt{T}}{\sqrt{d}}u$ (102) $$

with probability at least $1-\exp(-u)$.

### B.5 Martingale for the quadratic terms

We write

$$ $\displaystyle\Delta\mathcal{M}_{k+1}^{\tau,quad}$ $\displaystyle=\frac{\tilde{\eta}_{k}}{2d^{2}}\left\langle\nabla^{2}q, \operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})^{\otimes 2}\right \rangle-\frac{\tilde{\eta}_{k}}{2d^{2}}\left\langle\nabla^{2}q,\mathbb{E}\left [\operatorname{clip}_{c\sqrt{d}}(\ell_{k}\mathbf{x}_{k+1})^{\otimes 2}| \mathscr{F}_{k}\right]\right\rangle$ (103) $\displaystyle=T_{1}+T_{2},$ (104) $$

where

$$ $T_{1}=\frac{\tilde{\eta}_{k}}{2d^{2}}\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^ {\otimes 2}\right\rangle\ell_{k}^{2}\mathbbm{1}_{\ell_{k}^{2}\|\mathbf{x}_{k+1 }\|^{2}\leq c^{2}d}-\mathbb{E}\left[\frac{\tilde{\eta}_{k}}{2d^{2}}\left \langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle\ell_{k}^{2} \mathbbm{1}_{\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2}d}|\mathscr{F}_{k} \right].$ (105) $$

Notice that

$$ $\left|\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle\ell_{k }^{2}\mathbbm{1}_{\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2}d}\right|\leq \|\nabla^{2}q\|c^{2}d,$ (106) $$

so that

$$ $|T_{1}|\leq c^{2}\overline{\eta}^{2}d^{-1}.$ (107) $$

As for $T_{2}$,

$$ $\displaystyle T_{2}=$ $\displaystyle\frac{\tilde{\eta}_{k}c^{2}}{2d}\left\langle\nabla^{2}q,\left( \frac{\mathbf{x}_{k+1}}{\|\mathbf{x}_{k+1}\|}\right)^{\otimes 2}\right\rangle \mathbbm{1}_{\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\geq c^{2}d}$ (108) $\displaystyle-\mathbb{E}\left[\frac{\tilde{\eta}_{k}c^{2}}{2d}\left\langle \nabla^{2}q,\left(\frac{\mathbf{x}_{k+1}}{\|\mathbf{x}_{k+1}\|}\right)^{ \otimes 2}\right\rangle\mathbbm{1}_{\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\geq c ^{2}d}\middle|\mathscr{F}_{k}\right].$ $$

Similarly,

$$ $\left|\frac{\tilde{\eta}_{k}c^{2}}{2d}\left\langle\nabla^{2}q,\left(\frac{ \mathbf{x}_{k+1}}{\|\mathbf{x}_{k+1}\|}\right)^{\otimes 2}\right\rangle \mathbbm{1}_{\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\geq c^{2}d}\right|\leq\frac{ \overline{\eta}c^{2}}{2d}.$ (109) $$

So that overall,

$$ $|\Delta\mathcal{M}_{k+1}^{\tau,quad}|\leq\frac{2\overline{\eta}c^{2}}{d}$ (110) $$

for all $k$. Then, by Lemma 5 we have for $t\geq 1$

$$ $\mathbb{P}\left(\sup_{1\leq k\leq n}|M_{k}^{\tau,quad}-\mathbb{E}[M_{0}^{\tau, quad}]|>{2\overline{\eta}c^{2}}({n}/{d})t\right)\leq 2\exp\left(-cn\min\left\{ t,t^{2}\right\}\right).$ (111) $$

Hence we conclude that for some absolute constant $C$ and all $1\leq u\leq d$

$$ $\sup_{1\leq k\leq n}|M_{k}^{\tau,quad}|\leq C\overline{\eta}c^{2}\frac{\sqrt{T }}{\sqrt{d}}u$ (112) $$

with probability at least $1-\exp(-u)$.

### B.6 Martingale for the SDE

Recall equation (57)

$$ $\mathcal{M}_{t}^{\tau,SDE}=\int_{0}^{t}\frac{\eta(s)}{\sqrt{d}}\sqrt{2\nu(V_{s }^{\tau})\mathcal{P}(V_{s}^{\tau})}\nabla g(V_{s}^{\tau})^{T}\sqrt{\mathbf{K}} dB_{s}.$ (113) $$

We may compute the quadratic variation of $\mathcal{M}_{t}^{\tau,SDE}$ as

$$ $\left\langle\mathcal{M}^{\tau,SDE}\right\rangle_{t}=\int_{0}^{t}2\frac{\eta^{2 }(s)}{d}\nu(V_{s}^{\tau})\mathcal{P}(V_{s}^{\tau})\nabla g(V_{s}^{\tau})^{T} \mathbf{K}\nabla g(V_{s}^{\tau})\mathrm{d}s$ (114) $$

using (89) we see that

$$ $\left\langle\mathcal{M}^{\tau,SDE}\right\rangle_{t}\leq C\overline{\eta}^{2}d^ {-1}(1+M)^{4}t$ (115) $$

so that

$$ $\sup_{0\leq t\leq T}\left\langle\mathcal{M}^{\tau,SDE}\right\rangle_{t}\leq C \overline{\eta}^{2}d^{-1}(1+M)^{4}T$ (116) $$

then using the sub-Gaussian tail bound for continuous martingales with bounded quadratic variation gives for $u\geq 1$

$$ $\mathbb{P}\left(\sup_{0\leq s\leq T}\left|\mathcal{M}_{t}^{\tau,SDE}\right|>C \overline{\eta}(1+M)^{2}\sqrt{T}u/\sqrt{d}\right)\leq 2\exp\left(-u^{2}\right)$ (117) $$

so that increasing the absolute constant $C>0$ as needed, for all $u\geq 1$

$$ $\sup_{0\leq t\leq T}\left|\mathcal{M}_{t}^{\tau,SDE}\right|\leq C\overline{ \eta}(1+M)^{2}\frac{\sqrt{T}}{\sqrt{d}}u$ (118) $$

with probability at least $1-\exp(-u)$.

### B.7 Bounding the error terms

The remaining technical difficulty is in bounding the error terms. We will first focus on the linear error term.

#### B.7.1 Linear error terms

$$ $\displaystyle\Delta E_{k}^{\tau,lin}$ $\displaystyle=-\frac{\tilde{\eta}_{k}}{d}\nabla q(v_{k}^{\tau})^{T}\mathbb{E}[ \operatorname{clip}_{c\sqrt{d}}(\mathbf{x}_{k+1}\ell_{k})-\mathbf{x}_{k+1} \operatorname{clip}_{c}(\ell_{k})]$ (119) $\displaystyle=-\frac{\tilde{\eta}_{k}}{d}\nabla q(v_{k}^{\tau})^{T}\left( \mathbb{E}\left[\mathbf{x}_{k+1}\ell_{k}\mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1 }\|^{2}\leq c^{2}d}-\mathbf{x}_{k+1}\ell_{k}\mathbbm{1}_{\ell_{k}\operatorname {Tr}(\mathbf{K})\leq c^{2}d}\right]\right)$ (120) $\displaystyle-\frac{\tilde{\eta}_{k}c}{\sqrt{d}}\nabla q(v_{k}^{\tau})^{T} \mathbb{E}\left[\frac{\mathbf{x}_{k+1}\operatorname{sgn}(\ell_{k})}{\|\mathbf{ x}_{k+1}\|}\mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1}\|^{2}>c^{2}d}-\frac{\mathbf {x}_{k+1}\operatorname{sgn}(\ell_{k})}{\sqrt{\operatorname{Tr}(\mathbf{K})}} \mathbbm{1}_{\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d}\right]$ (121) $\displaystyle\eqqcolon-\frac{\tilde{\eta}_{k}}{d}\mathbb{E}[D_{k}].$ (122) $$

For clarity, we will write $\nabla q(v_{k}^{\tau})$ as $\nabla q_{k}$. We see that

$$ $\displaystyle D_{k}=\begin{cases}0,&\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c ^{2}d\text{ and }\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^{2}d,\\ \nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}-\frac{c\sqrt{d}\nabla q_{k}^{T} \mathbf{x}_{k+1}\ell_{k}}{|\ell_{k}|\sqrt{\operatorname{Tr}(\mathbf{K})}},& \ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2}d\text{ and }\ell_{k}^{2} \operatorname{Tr}(\mathbf{K})>c^{2}d,\\ \frac{c\sqrt{d}\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}}{|\ell_{k}|\|\mathbf{x }_{k+1}\|}-\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k},&\ell_{k}^{2}\|\mathbf{x}_ {k+1}\|^{2}>c^{2}d\text{ and }\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^ {2}d,\\ \frac{c\sqrt{d}\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}}{|\ell_{k}|\|\mathbf{x }_{k+1}\|}-\frac{c\sqrt{d}\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}}{|\ell_{k}| \sqrt{\operatorname{Tr}(\mathbf{K})}},&\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}>c^ {2}d\text{ and }\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d.\end{cases}$ (123) $$

Now, considering each case, we see that:

When $\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2}d$ and $\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d$, we have

$$ $\displaystyle|D_{k}|$ $\displaystyle=|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|\left|1-\frac{c\sqrt{d }}{|\ell_{k}|\sqrt{\operatorname{Tr}(\mathbf{K})}}\right|$ (124) $\displaystyle\leq|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|\left|1-\frac{\| \mathbf{x}_{k+1}\|}{\sqrt{\operatorname{Tr}(\mathbf{K})}}\right|.$ (125) $$

When $\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}>c^{2}d$ and $\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^{2}d$, we have

$$ $\displaystyle|D_{k}|$ $\displaystyle=|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|\left|\frac{c\sqrt{d}} {|\ell_{k}|\|\mathbf{x}_{k+1}\|}-1\right|$ (126) $\displaystyle\leq|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|\left|1-\frac{\| \mathbf{x}_{k+1}\|}{\sqrt{\operatorname{Tr}(\mathbf{K})}}\right|.$ (127) $$

When $\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}>c^{2}d$ and $\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d$,

$$ $\displaystyle|D_{k}|$ $\displaystyle=|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|\left|c\sqrt{d}\frac{1 }{|\ell_{k}|}\right|\left|\frac{1}{\|\mathbf{x}_{k+1}\|}-\frac{1}{\sqrt{ \operatorname{Tr}(\mathbf{K})}}\right|$ (128) $\displaystyle\leq|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|\left|1-\frac{\| \mathbf{x}_{k+1}\|}{\sqrt{\operatorname{Tr}(\mathbf{K})}}\right|.$ (129) $$

Now using the numerical inequality $|1-z|>t\implies|1-z^{2}|>\max\{t,t^{2}\}$,

$$ $\mathbb{P}\left(\left|1-\frac{\|\mathbf{x}_{k+1}\|}{\sqrt{\operatorname{Tr}( \mathbf{K})}}\right|>t\right)\leq\mathbb{P}\left(\left|1-\frac{\|\mathbf{x}_{k +1}\|^{2}}{\operatorname{Tr}(\mathbf{K})}\right|>\max\{t,t^{2}\}\right).$ (130) $$

Since, by assumption $\operatorname{Tr}(\mathbf{K})=d$, and using Assumption 4 we see that, setting $s=\max\{t,t^{2}\}$

$$ $\displaystyle\mathbb{P}\left(\left|1-\frac{\|\mathbf{x}_{k+1}\|}{\sqrt{ \operatorname{Tr}(\mathbf{K})}}\right|>t\right)$ $\displaystyle\leq\mathbb{P}\left(\left|\operatorname{Tr}(\mathbf{K})-\|\mathbf {x}_{k+1}\|^{2}\right|>\mathrm{d}s\right)$ (131) $\displaystyle\leq 2\exp\left(-\min\left\{\frac{d^{2}s^{2}}{\dutchcal{v}^{4}\| \mathbf{K}\|_{F}^{2}},\frac{\mathrm{d}s}{\dutchcal{v}^{2}\|\mathbf{K}\|}\right \}\right).$ (132) $$

Since $d^{2}/\|\mathbf{K}\|_{F}^{2}\geq d$, we conclude that for all $u\geq 1$

$$ $\mathbb{P}\left(\left|1-\frac{\|\mathbf{x}_{k+1}\|}{\sqrt{\operatorname{Tr}( \mathbf{K})}}\right|>\dutchcal{v}u\right)\leq 2\exp\left(-du^{2}\right).$ (133) $$

The term $|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|$ has a second moment bounded by (compare with (96))

$$ $\mathbb{E}|\nabla q_{k}^{T}\mathbf{x}_{k+1}\ell_{k}|\leq C(2+M)^{2}\dutchcal{v }^{2}$ $$

for an absolute constant $C>0$, and hence we conclude for an absolute constant $C>0$

$$ $|\Delta E_{k}^{\tau,lin}|\leq C(2+M)^{2}\overline{\eta}d^{-3/2}\dutchcal{v}^{3}.$ (134) $$

Thus, taking $n\leq dT$ steps, we get

$$ $\max_{0\leq k\leq n}|E_{k}^{\tau,lin}|\leq CT\overline{\eta}\dutchcal{v}^{3}(2 +M)^{2}d^{-1/2}.$ (135) $$

#### B.7.2 Quadratic error terms

This follows a similar path as the linear terms.
We again express

$$ $\displaystyle\Delta E_{k}^{\tau,quad}$ $\displaystyle=\frac{\tilde{\eta}_{k}}{2d^{2}}\left(\mathbb{E}\left[\left \langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle\ell_{k}^{2} \mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1}\|^{2}\leq c^{2}d}\right]-\left\langle \nabla^{2}q,\mathbf{K}\right\rangle\mathbb{E}\left[\ell_{k}^{2}\mathbbm{1}_{ \ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^{2}d}\right]\right)$ (136) $\displaystyle+\frac{\tilde{\eta}_{k}c^{2}}{2d}\left(\mathbb{E}\left[\frac{ \left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle}{\|\mathbf{x }_{k+1}\|^{2}}\mathbbm{1}_{\|\ell_{k}\mathbf{x}_{k+1}\|^{2}>c^{2}d}\right]- \frac{\left\langle\nabla^{2}q,\mathbf{K}\right\rangle}{\operatorname{Tr} \mathbf{K}}\mathbb{P}\left(\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d \right)\right)$ (137) $\displaystyle\coloneqq\frac{\tilde{\eta}_{k}}{2d^{2}}\mathbb{E}[D_{k}^{\prime}]$ (138) $$

with

$$ $\displaystyle D_{k}^{\prime}$ $\displaystyle=\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right \rangle\ell_{k}^{2}\mathbbm{1}_{\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2} d}-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\ell_{k}^{2}\mathbbm{1}_{ \ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^{2}d}$ (139) $\displaystyle\phantom{=}+c^{2}d\frac{\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^ {\otimes 2}\right\rangle}{\|\mathbf{x}_{k+1}\|^{2}}\mathbbm{1}_{\ell_{k}^{2}\| \mathbf{x}_{k+1}\|^{2}>c^{2}d}-c^{2}d\frac{\left\langle\nabla^{2}q,\mathbf{K} \right\rangle}{\operatorname{Tr}(\mathbf{K})}\mathbbm{1}_{\ell_{k}^{2} \operatorname{Tr}(\mathbf{K})>c^{2}d}$ (140) $\displaystyle=\begin{cases}\ell_{k}^{2}\left(\left\langle\nabla^{2}q,\mathbf{x }_{k+1}^{\otimes 2}\right\rangle-\left\langle\nabla^{2}q,\mathbf{K}\right \rangle\right),&\text{$\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2}d$ and $ \ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^{2}d$},\[10.0pt] \left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle\ell_{k}^{2}- c^{2}d\frac{\left\langle\nabla^{2}q,\mathbf{K}\right\rangle}{\operatorname{Tr} (\mathbf{K})},&\text{$\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2}d$ and $ \ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d$},\[10.0pt] c^{2}d\frac{\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle} {\|\mathbf{x}_{k+1}\|^{2}}-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\ell _{k}^{2},&\text{$\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}>c^{2}d$ and $\ell_{k}^{2 }\operatorname{Tr}(\mathbf{K})\leq c^{2}d$},\[10.0pt] c^{2}d\left(\frac{\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right \rangle}{\|\mathbf{x}_{k+1}\|^{2}}-\frac{\left\langle\nabla^{2}q,\mathbf{K} \right\rangle}{\operatorname{Tr}(\mathbf{K})}\right),&\text{$\ell_{k}^{2}\| \mathbf{x}_{k+1}\|^{2}>c^{2}d$ and $\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})> c^{2}d$}.\end{cases}$ (141) $$

Consider the function by cases. On $\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}\leq c^{2}d$ and $\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d$ we have

$$ $\displaystyle\left|\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right \rangle\ell_{k}^{2}-c^{2}d\frac{\left\langle\nabla^{2}q,\mathbf{K}\right \rangle}{\operatorname{Tr}(\mathbf{K})}\right|$ (142) $\displaystyle=\left|\ell_{k}^{2}\left(\left\langle\nabla^{2}q,\mathbf{x}_{k+1} ^{\otimes 2}\right\rangle-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle \right)+\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\left(\ell_{k}^{2}- \frac{c^{2}d}{\operatorname{Tr}(\mathbf{K})}\right)\right|$ (143) $\displaystyle\leq\ell_{k}^{2}\left|\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{ \otimes 2}\right\rangle-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\right| +\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\frac{\ell_{k}^{4}}{c^{2}d} \left|\operatorname{Tr}(\mathbf{K})-\|\mathbf{x}_{k+1}\|^{2}\right|.$ (144) $$

Similarly, if $\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}>c^{2}d$ and $\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})\leq c^{2}d$

$$ $\displaystyle\left|c^{2}d\frac{\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{ \otimes 2}\right\rangle}{\|\mathbf{x}_{k+1}\|^{2}}-\left\langle\nabla^{2}q, \mathbf{K}\right\rangle\ell_{k}^{2}\right|$ (145) $\displaystyle=\left|\frac{c^{2}d}{\|\mathbf{x}_{k+1}\|^{2}}\left(\left\langle \nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2}\right\rangle-\left\langle\nabla^{2}q, \mathbf{K}\right\rangle\right)+\left\langle\nabla^{2}q,\mathbf{K}\right\rangle \left(\frac{c^{2}d}{\|\mathbf{x}_{k+1}\|^{2}}-w^{2}\right)\right|$ (146) $\displaystyle\leq\ell_{k}^{2}\left|\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{ \otimes 2}\right\rangle-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\right| +\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\frac{\ell_{k}^{4}}{c^{2}d} \left|\operatorname{Tr}(\mathbf{K})-\|\mathbf{x}_{k+1}\|^{2}\right|.$ (147) $$

and finally when $\ell_{k}^{2}\|\mathbf{x}_{k+1}\|^{2}>c^{2}d$ and $\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d$ we have

$$ $\displaystyle\left|c^{2}d\left(\frac{\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^ {\otimes 2}\right\rangle}{\|\mathbf{x}_{k+1}\|^{2}}-\frac{\left\langle\nabla^{ 2}q,\mathbf{K}\right\rangle}{\operatorname{Tr}(\mathbf{K})}\right)\right|$ $\displaystyle\leq\ell_{k}^{2}\left|\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{ \otimes 2}\right\rangle-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\right|$ (148) $\displaystyle+\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\frac{\ell_{k}^{4 }}{c^{2}d}\left|\operatorname{Tr}(\mathbf{K})-\|\mathbf{x}_{k+1}\|^{2}\right| \mathbbm{1}_{\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d}.$ (149) $$

So overall,

$$ $|D^{\prime}_{k}|\leq\ell_{k}^{2}\left|\left\langle\nabla^{2}q,\mathbf{x}_{k+1} ^{\otimes 2}\right\rangle-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle \right|+\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\frac{\ell_{k}^{4}}{c^{ 2}d}\left|\operatorname{Tr}(\mathbf{K})-\|\mathbf{x}_{k+1}\|^{2}\right| \mathbbm{1}_{\ell_{k}^{2}\operatorname{Tr}(\mathbf{K})>c^{2}d}.$ (150) $$

Now, we may use the Hanson-Wright inequality (Assumption 4) along with the inequality

$$ $\|\sqrt{\mathbf{K}}\nabla^{2}q\sqrt{\mathbf{K}}\|_{F}^{2}\leq\operatorname{Tr} (\mathbf{K})\|\nabla^{2}q\|^{2}\leq\operatorname{Tr}(\mathbf{K})=d$ (151) $$

to see that for all $t\geq 0$

$$ $\mathbb{P}\left(\left|\left\langle\nabla^{2}q,\mathbf{x}_{k+1}^{\otimes 2} \right\rangle-\left\langle\nabla^{2}q,\mathbf{K}\right\rangle\right|>t \dutchcal{v}^{2}\right)\leq 2\exp\left(-\min\left\{\frac{t^{2}}{d},t\right\} \right).$ (152) $$

We also recall from (132) that

$$ $\mathbb{P}\left(|\|\mathbf{x}_{k+1}\|^{2}-\operatorname{Tr}(\mathbf{K})|>t \dutchcal{v}^{2}\right)\leq 2\exp\left(-\min\left\{\frac{t^{2}}{d},t\right\} \right).$ $$

Hence overall, we conclude that for some absolute constant $C>0$

$$ $|\mathbb{E}D_{k}^{\prime}|\leq C\dutchcal{v}^{4}(1+M)^{2}\sqrt{d}.$ $$

So that overall

$$ $\displaystyle\left|\Delta E_{k}^{\tau,quad}\right|$ $\displaystyle\leq C\overline{\eta}\dutchcal{v}^{4}(1+M)^{2}d^{-3/2}.$ (153) $$

and summing over $k\leq n\leq Td,$

$$ $\displaystyle\max_{0\leq k\leq n}\left|E_{k}^{\tau,quad}\right|$ $\displaystyle\leq CT\overline{\eta}\dutchcal{v}^{4}(1+M)^{2}d^{-1/2}.$ (154) $$

This completes the proof of Lemma 2.

## Appendix 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 a 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 as 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.

Figure: Figure 5: The CSC and CCC where the noise is Student-t distributed. We hold the variance fixed and vary over the degrees-of-freedom (DOF) parameter. Notice how for high DOF, the thresolds resemble Gaussian behaviour (compare to Figure 2 in the main paper). Meanwhile for small DOF, we see that both the CSC and CCC are high, suggesting clipping is particularly effective. This reflects the heavy-tailed behaviour of the small DOF Student-t distribution.
Refer to caption: x10.png

### C.2 Measuring μ 𝜇 \mu italic_μ and ν 𝜈 \nu italic_ν in real networks

Figure: Figure 6: $\mu$, $\nu$, CSC and CCC for the realistic models of Appendix C (ResNet18 and ViT) trained on CIFAR10. $\mu$ and $\nu$ were computed using the results from the Gaussian model: $\mu$ was defined as the fraction of unclipped gradients, and $\nu$ is the ratio of clipped gradient squared norms to the unclipped gradient squared norms. $\mu$ and $\nu$ are computed for three log-spaced clipping thresholds. Our theory suggests that ResNet may benefit from clipping, but ViT in this setting does not.
Refer to caption: x12.png

We can estimate $\mu$ and $\nu$ in the non-linear setting as well. Even though C-HSGD does not fully capture the dynamics in
this regime, computing estimates of $\mu$ and $\nu$ may give useful information about how to apply clipping schedules. Given a loss function $\mathcal{L}(\bm{\theta})$
induced by some non-linear model $\mathbf{z}(\bm{\theta})$,
the generalization of Equation 7 is given by

$$ $\displaystyle\mu_{c}(\bm{\theta})=\frac{\|\mathbb{E}[\operatorname{clip}_{c}( \nabla_{\bm{\theta}}\mathcal{L})]\|}{\|\mathbb{E}[\nabla_{\bm{\theta}}\mathcal {L}]\|}\qquad\text{and}\qquad\nu_{c}(\bm{\theta})=\frac{\mathbb{E}[|| \operatorname{clip}_{c}(\nabla_{\bm{\theta}}\mathcal{L})||^{2}]}{\mathbb{E}[|| \nabla_{\bm{\theta}}\mathcal{L}||^{2}]}.$ (155) $$

Here the averages are across sampled minibatches. These forms can be derived from the original calculation by making the substitution
$\mathbf{x}\to\mathbf{J}$, where $\mathbf{J}$ is the Jacobian $\frac{\partial\mathbf{z}}{\partial\bm{\theta}}$.

The numerator and denominator can be estimated online using a running average (e.g. exponential moving average)
updated after every C-SGD step. This does not require any additional
backpropagation steps, but does require keeping 2 extra running averages
in the shape of $\bm{\theta}$ to compute $\mu_{c}$. However, if we use the form of $\mu_{c}$ from Equation 9, adapted as

$$ $\mu_{c}(\bm{\theta})=\mathbb{P}[||\nabla_{\bm{\theta}}\mathcal{L}||\leq c]$ (156) $$

(that is, the probability of unclipped gradients),
no additional memory costs are
incurred and the computation is efficient.

Figure: Figure 7: $\mu$, $\nu$, CSC and CCC for the realistic models of Appendix C (ResNet18 and ViT) trained on CIFAR10. $\mu$ and $\nu$ were computed using Equations 155 and the additional approximation from Equation 156. $\mu$ and $\nu$ are computed for three log-spaced clipping thresholds. Our theory suggests that ResNet may benefit from clipping, but ViT in this setting does not.
Refer to caption: x16.png

We used this estimator to compute $\mu$ and $\nu$ for ResNet18 and ViT S/16 trained on CIFAR10
(Figure 7, left column). The models were trained without clipping, and $\mu$ and $\nu$ were computed using different
clipping values $c$. With a larger clipping threshold of $c=10$, gradients are rarely clipped and $\mu(t)\approx\nu(t)\approx 1$; there is non-trivial
dynamics for smaller clipping strength. We also computed the (CSC) and (CCC) for the different thresholds
(Figure 7, right column). For ResNet18, the (CCC) is above $1$ for the smaller
thresholds; if the theory holds, then clipping is beneficial here.
In contrast, for ViT it remains at or below $1$ and clipping would not help.

Further investigation is needed to understand the utility of using $\mu$ and $\nu$ 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 us to largely ignore these with the appropriate
choice of $\mu$ and $\nu$. We leave the exploration and development of practical applications of $\mu$ and $\nu$ to set joint learning rate and clipping
schedules to future work.

### C.3 Measuring the intrinsic dimension in real networks

Recall that the intrinsic dimension $d$ is defined in terms of the spectrum of $\mathbf{K}$:

$$ $d:=\operatorname{Tr}(\mathbf{K})/\|\mathbf{K}\|.$ $$

We can extend the definition of the intrinsic dimension to the
non-linear setting by considering a linearization of the dynamics. Given a loss function $\mathcal{L}(\mathbf{z})$ and a model
$\mathbf{z}(\bm{\theta})$ on parameters $\bm{\theta}$, the Gauss Newton matrix $\mathbf{G}$ of the loss is defined by:

$$ $\mathbf{G}:=\nabla_{\bm{\theta}}\mathbf{z}^{\top}\nabla_{\mathbf{z}}^{2} \mathcal{L}\nabla_{\bm{\theta}}\mathbf{z}.$ (157) $$

Here $\nabla_{\bm{\theta}}\mathbf{z}$ is the model Jacobian, and
$\nabla_{\mathbf{z}}^{2}\mathcal{L}$ is the Hessian
of the loss with respect to the model outputs. $\mathbf{G}$ encodes the second derivative of the loss with respect to a linearized
model $\tilde{\mathbf{z}}=\mathbf{z}(\bm{\theta}_{0})+\nabla_{\bm{\theta}}\mathbf{z}(
\bm{\theta}-\bm{\theta}_{0})$.

For a linear model on MSE loss (as we studied in the main text), we have $\mathbf{K}=\mathbf{G}$. If we took a
non-linear model during training, and locally linearized the model and loss, we would measure the intrinsic dimension with
$\mathbf{G}$ as well.
Therefore, on non-linear models, we will define

$$ $d_{nl}:=\operatorname{Tr}(\mathbf{G})/\|\mathbf{G}\|$ (158) $$

as the *non-linear intrinsic dimension*.

With this definition, we can measure the intrinsic dimension on neural network models during training.
We measured $d_{nl}$ on ResNet18 He et al. () and ViT S/16 Dosovitskiy et al. () for networks trained on CIFAR10 using
MSE loss (Figure 8). We see that for
ResNet18, $d_{nl}$ increases from $\sim 100$ to $10^{3}$, while for
ViT $d_{nl}$ stays steady at $\sim 300$. In both cases $d_{nl}$ is large, but it is very model
dependent.

This suggests that real neural network models are in the effectively high-dimensional regime; we leave
to future work the question of which concepts from the basic theory
generalize to the non-linear setting.

Figure: Figure 8: Non-linear intrinsic dimension $d_{nl}$ for models trained on MSE loss. For ResNet18 (blue), $d_{nl}$ increases by a factor of $10$ over training, while for ViT S/16 (orange) $d_{nl}$ remains relatively constant.
Refer to caption: x20.png

## Appendix D Some examples of μ 𝜇 \mu italic_μ and ν 𝜈 \nu italic_ν

In this section we give some examples of $\mu$ and $\nu$ as defined in equation (7) under various common distributions. First, we will describe how to define $\mu_{c}$ and $\nu_{c}$ as functions of the risk.

Notice that, with Gaussian data, $\ell_{\bm{\theta}}\overset{\operatorname{law}}{=}\sqrt{2\mathcal{R}(\bm{\theta
})}\xi-\epsilon$ where $\xi$ is a standard Gaussian. Thus we can define $\tilde{\mu}$ and $\tilde{\nu}$ such that

$$ $\displaystyle\tilde{\mu}(\bm{\Theta}_{t})=\frac{\|\mathbb{E}[\operatorname{ clip}_{c}(\sqrt{2\mathcal{R}(\bm{\Theta}_{t})}\xi-\epsilon)\mathbf{x}]\|}{\| \mathbb{E}[(\sqrt{2\mathcal{R}(\bm{\Theta}_{t})}\xi-\epsilon)\mathbf{x}]\|}$ $\displaystyle\tilde{\nu}(\bm{\Theta}_{t})=\frac{\mathbb{E}[\operatorname{clip} ^{2}_{c}(\sqrt{2\mathcal{R}(\bm{\Theta}_{t})}\xi-\epsilon)]}{\mathbb{E}[(\sqrt {2\mathcal{R}(\bm{\Theta}_{t})}\xi-\epsilon)^{2}]}$ (159) $$

and $\mu_{c}(\bm{\Theta}_{t})=\tilde{\mu}_{c}(\mathcal{R}(\bm{\Theta}_{t}))$ and $\nu_{c}(\bm{\Theta}_{t})=\tilde{\nu}_{c}(\mathcal{R}(\bm{\Theta}_{t}))$. In what follows $r=\mathcal{R}(\bm{\theta})$ for some $\bm{\Theta}_{t}$. In the following examples, we will simplify notation and simply let $\mathcal{R}(\bm{\Theta}_{t})=r$.

### D.1 Gaussian data and Gaussian noise

Consider $a\sim N(0,\mathbf{K})$ and $\epsilon\sim N(0,\sigma^{2})$. First define

$$ $F(z)=\operatorname{erf}\left(\frac{z}{\sqrt{2}}\right)-\sqrt{\frac{2}{\pi}}ze^ {-z^{2}/2}$ (160) $$

Then, we have

$$ $\mu_{c}(r)=\operatorname{erf}\left(\frac{c}{\sqrt{4(r+\sigma^{2}/2)}}\right)$ (161) $$

$$ $(2r+\sigma^{2})\nu_{c}(r)=2rF\left(\frac{c}{\sqrt{2(r+\eta^{2}/2)}}\right)+c^{ 2}\operatorname{erfc}\left(\frac{c}{\sqrt{4(r+\eta^{2}/2)}}\right)$ (162) $$

### D.2 Gaussian data and Rademacher-like noise

$$ $\epsilon_{k}=\begin{cases}-\lambda&\text{with probability }q/2\\ 0&\text{with probability }1-q\\ \lambda&\text{with probability }q/2\end{cases}$ (163) $$

Note that $\sigma^{2}=\operatorname{Var}(\epsilon)=\lambda^{2}q$. For some standard Gaussian random variable $z$, $\mu$ and $\nu$ may be computed as

$$ $\displaystyle\mu_{c}(r)$ $\displaystyle=q\mathbb{P}\left(|z-\lambda|\leq\frac{c}{\sqrt{2r}}\right)+(1-q) \mathbb{P}\left(|z|\leq\frac{c}{\sqrt{2r}}\right)$ (164) $\displaystyle=\frac{q}{2}\left(\operatorname{erf}\left(\frac{c-\lambda}{\sqrt{ 4r}}\right)+\operatorname{erf}\left(\frac{c+\lambda}{\sqrt{4r}}\right)\right)+ (1-q)\operatorname{erf}\left(\frac{c}{\sqrt{4r}}\right)$ (165) $$

$$ $\displaystyle(2r+\sigma^{2})\nu_{c}(r)$ $\displaystyle=2r\frac{q}{2}\left(F\left(\frac{c-\lambda}{\sqrt{2r}}\right)+F \left(\frac{c+\lambda}{\sqrt{2r}}\right)\right)+2r(1-q)F\left(\frac{c}{\sqrt{2 r}}\right)$ (166) $\displaystyle+\frac{q\lambda}{\sqrt{\pi r}}\left(\exp\left(-\frac{(c+\lambda)^ {2}}{2r}\right)-\exp\left(-\frac{(c-\lambda)^{2}}{2r}\right)\right)$ (167) $\displaystyle+\frac{q\lambda^{2}}{2}\left(\operatorname{erf}\left(\frac{c- \lambda}{\sqrt{4r}}\right)+\operatorname{erf}\left(\frac{c+\lambda}{\sqrt{4r}} \right)\right)$ (168) $\displaystyle+\frac{qc^{2}}{2}\left(\operatorname{erfc}\left(\frac{c-\lambda}{ \sqrt{2r}}\right)+\operatorname{erfc}\left(\frac{c+\lambda}{\sqrt{2r}}\right)+ (1-q)\mathbb{P}\left(|z|>\frac{c}{\sqrt{2r}}\right)\right)$ (169) $$

### D.3 Gaussian data and uniform noise

For $a\sim N(0,\mathbf{K})$ and uniform noise supported on $[-M,M]$ we have $\sigma^{2}=M^{2}/3$ and

$$ $\displaystyle\mu_{c}(r)$ $\displaystyle=1-\frac{1}{2M}c^{2}\left(e^{-\frac{(c+M)^{2}}{4r}}(e^{\frac{cM}{ r}}-1)\sqrt{\frac{4r}{\pi}}\right)$ (170) $\displaystyle-\frac{1}{2M}c^{2}\left((M-c)\operatorname{erfc}\left(\frac{c-M}{ \sqrt{4r}}\right)+(c+M)\operatorname{erfc}\left(\frac{c+M}{\sqrt{4r}}\right)\right)$ (171) $$

$$ $\displaystyle(2r+\sigma^{2})\nu_{c}(r)$ $\displaystyle=\frac{-1}{6M}e^{-\frac{(c+M)^{2}}{4r}}\sqrt{\frac{4r}{\pi}}\left (-c^{2}+cM-M^{2}-4r+e^{cM/r}(c^{2}+cM+M^{2}+4r)\right)$ (172) $\displaystyle-\frac{1}{6M}(c^{3}-M^{3}-6Mr)\operatorname{erf}\left(\frac{c-M}{ \sqrt{4r}}\right)+\frac{1}{6M}(c^{3}+M^{3}+6Mr)\operatorname{erf}\left(\frac{c +M}{\sqrt{4r}}\right)$ (173) $\displaystyle+\frac{1}{2M}c^{2}\left(e^{-\frac{(c+M)^{2}}{4r}}(e^{\frac{cM}{r} }-1)\sqrt{\frac{2\sigma^{2}}{\pi}}\right)$ (174) $\displaystyle+\frac{1}{2M}c^{2}\left((M-c)\operatorname{erfc}\left(\frac{c-M}{ \sqrt{4r}}\right)+(c+M)\operatorname{erfc}\left(\frac{c+M}{\sqrt{4r}}\right)\right)$ (175) $$

### D.4 Gaussian data and symmetric exponential noise

For $a\sim N(0,\mathbf{K})$ and symmetric exponential noise, also known as Laplacian, with density

$$ $f(x)=\lambda e^{-|x|\lambda}/2$ (176) $$

then we have

$$ $\displaystyle\mu_{c}(r)$ $\displaystyle=2\operatorname{erf}\left(\frac{c}{\sqrt{2r^{2}}}\right)$ (177) $\displaystyle+e^{\lambda(-2c+\lambda r^{2})/2}(e^{2c\lambda}-\operatorname{erf }\left(\frac{(c-\lambda r^{2})}{\sqrt{2r^{2}}}\right)-e^{2c\lambda} \operatorname{erf}\left(\frac{(c+\lambda r^{2})}{\sqrt{2r^{2}}}\right)-1)/2$ (178) $$

Then, if $T_{c}(r)$ satisfies

$$ $\displaystyle(8+4\lambda^{2}r^{2})T(r)$ $\displaystyle=2e^{\lambda(2c+\lambda r^{2})/2}(2-2c\lambda+c^{2}\lambda^{2})-2 e^{\lambda(-2c+\lambda r^{2})/2}(2+2c\lambda+c^{2}\lambda^{2})$ (179) $\displaystyle-4ce^{\frac{-c^{2}}{2r^{2}}}\lambda^{2}\sqrt{2r^{2}/\pi}+2\lambda ^{2}r^{2}+2\lambda^{2}r^{2}(\operatorname{erf}\left(\frac{c}{\sqrt{2r^{2}}} \right)-1)$ (180) $\displaystyle+(4+2\lambda^{2}r^{2}+8)\operatorname{erf}\left(\frac{c}{\sqrt{2r ^{2}}}\right)$ (181) $\displaystyle-2e^{\lambda(-2c+\lambda r^{2})/2}(2+2c\lambda+c^{2}\lambda^{2}) \operatorname{erf}\left(\frac{c-\lambda r^{2}}{\sqrt{2r^{2}}}\right)$ (182) $\displaystyle-2e^{\lambda(2c+\lambda r^{2})/2}(2-2c\lambda+c^{2}\lambda^{2}) \operatorname{erf}\left(\frac{c+\lambda r^{2}}{\sqrt{2r^{2}}}\right)$ (183) $$

we have

$$ $\nu_{c}(r)=T_{c}(r)+c^{2}(1-\mu_{c}(r))/(2r+\sigma^{2})$ (184) $$

## Appendix E Simplification of μ 𝜇 \mu italic_μ and ν 𝜈 \nu italic_ν

###### Theorem 8 .

Let $\mathbf{x}\sim N(0,\mathbf{K})$ and let the noise be $\sigma\epsilon$ for a fixed random variable $\epsilon$ and $\sigma>0$. Assume that the characteristic function of $\epsilon$, $\varphi(t)=\mathbb{E}[e^{it\epsilon}]$ is integrable. This assumption implies that $\epsilon$ has a continuous density $g(y)$. We will additionally assume that $g(0)>0$.

Then, there exist absolute constants $\kappa_{l},\kappa_{u}$ depending on the distribution of the noise (but not $\sigma$) such that,

$$ $\kappa_{l}\min\left(1,\frac{c}{\sqrt{2R+\sigma^{2}}}\right)\leq\mu_{c}(R)\leq \kappa_{u}\min\left(1,\frac{c}{\sqrt{2R+\sigma^{2}}}\right)$ (185) $$

###### Proof.

We first complete the upper bound. Let $g\sim N(0,1)$. Notice that $\ell_{\bm{\theta}}\overset{\operatorname{law}}{=}\sqrt{2\mathcal{R}(\bm{\theta
})}g-\sigma\epsilon$. Thus,

$$ $\mu_{c}(\bm{\theta})=\mathbb{P}(|\ell_{\bm{\theta}}|\leq c).$ (186) $$

Going forward, we omit the dependence on $\bm{\theta}$ for clarity. Let $f$ be the density of $\ell$. Then, by the Fourier inversion theorem

$$ $\displaystyle f(x)$ $\displaystyle=\frac{1}{2\pi}\int e^{-ixt}e^{-\mathcal{R}t^{2}}\varphi(\sigma t )\mathrm{d}t$ (187) $\displaystyle\leq\frac{1}{2\pi}\int e^{-\mathcal{R}t^{2}}|\varphi(\sigma t)| \mathrm{d}t,$ $$

where $\varphi(t)$ is the characteristic function of $\epsilon$. Now consider cases: when $2\mathcal{R}\geq\sigma^{2}$,

$$ $\displaystyle f(x)$ $\displaystyle\leq\frac{1}{2\pi\sigma}\int e^{-\mathcal{R}t^{2}/\sigma^{2}}| \varphi(t)|dt$ (188) $\displaystyle\leq\pi^{-1/2}\frac{1}{\sqrt{2\mathcal{R}+\sigma^{2}}}$ $$

Meanwhile, if $\sigma^{2}<2\mathcal{R}$

$$ $\displaystyle f(x)$ $\displaystyle\leq\frac{1}{2\pi\sigma}\int e^{-\mathcal{R}t^{2}/\sigma^{2}}| \varphi(t)|dt$ (189) $\displaystyle\leq\frac{\int|\varphi(t)|dt}{\sqrt{2}\pi}\frac{1}{\sqrt{\sigma^{ 2}+2\mathcal{R}}}$ $$

By assumption, $\int|\varphi(t)|dt<\infty$ and while it depends on the noise distribution it does not depend on the variance/scale parameter $\sigma$. Since,

$$ $\mu_{c}=\int_{-c}^{c}f(x)dx,$ (190) $$

putting the two cases together completes the bound.

We now proceed with the lower bound. Let $A\geq 1$ and again consider cases. First, let $\sigma<Ac$ and $\sqrt{2R}<Ac$ for some $A$. Then,

$$ $\displaystyle\mu_{c}$ $\displaystyle=\mathbb{P}(|\ell_{\bm{\theta}}|\leq c)$ (191) $\displaystyle=\mathbb{P}(|\sqrt{2R}g+\sigma\epsilon|\leq c)$ $\displaystyle\geq\mathbb{P}(|g|\leq 1/2A)\mathbb{P}(|\epsilon|\leq 1/2A)$ $\displaystyle=\kappa_{A}>0.$ $$

Where $\kappa_{A}$ is bounded away from 0 0 by assumption. And so,

$$ $\mu_{c}\geq\kappa_{A}\min\left(1,\frac{c}{\sqrt{\sigma^{2}+2R}}\right).$ (192) $$

Now for the remaining cases. We can express $\mu_{c}$ by integrating over the density of $\ell_{\bm{\theta}}$. Let $\mathcal{L}$ represent the law of $\sigma\epsilon$. Then,

$$ $\mu_{c}=\frac{1}{\sqrt{4\pi R}}\int_{-c}^{c}\int_{\mathbb{R}}e^{-(x+y)^{2}/4R} \mathrm{d}\mathcal{L}(y)\,\mathrm{d}x.$ (193) $$

Consider the case where $\sqrt{2R}>Ac$ and $\sqrt{2R}>\sigma$. Then,

$$ $\displaystyle\mu_{c}$ $\displaystyle\geq\frac{1}{\sqrt{4\pi R}}\int_{-c}^{c}\int_{-1/A}^{1/A}e^{-(x+y \sigma)^{2}/4R}g(y)\mathrm{d}y\,\mathrm{d}x$ (194) $\displaystyle\geq\min\left(1,\frac{c}{\sqrt{2R+\sigma^{2}}}\right)\frac{4me^{- 1/8A^{2}}}{A\sqrt{2\pi}}$ $$

where we may lower bound the integrand since $|(x+y\sigma)^{2}/4R|\leq 1/2A$ over the rectangle $(x,y)\in[-c,c]\times[-1/A,1/A]$. Similarly, we consider the case $\sqrt{2R}<\sigma$ and $\sigma>Ac$. Then,

$$ $\displaystyle\mu_{c}$ $\displaystyle\geq\frac{1}{\sigma\sqrt{2\pi}}\int_{-c}^{c}\int_{-1/A}^{1/A}e^{- y^{2}/2}g\left(\frac{\sqrt{2R}y-x}{\sigma}\right)\mathrm{d}y\,\mathrm{d}x$ (195) $\displaystyle\geq\min\left(1,\frac{c}{\sqrt{2R+\sigma^{2}}}\right)\frac{4me^{- 1/2A^{2}}}{A\sqrt{2\pi}}.$ $$

Choosing $\kappa_{l}=\min\left(\kappa_{A},\frac{4me^{-1/8A^{2}}}{A\sqrt{2\pi}}\right)$ completes the proof.
∎

###### Corollary 1 .

In the same setting as Theorem 8,

$$ $\kappa_{l}\min\left(1,\frac{c^{2}}{2R+\sigma^{2}}\right)\leq\nu^{2}_{c}(R)\leq \kappa_{u}\min\left(1,\frac{c^{2}}{2R+\sigma^{2}}\right).$ (196) $$

###### Proof.

$\nu_{c}$ is trivially less than or equal to $1$. Recall the definition,

$$ $\displaystyle\nu_{c}(R)$ $\displaystyle=\frac{1}{2R+\sigma^{2}}\left(\mathbb{E}\left[\ell_{\bm{\theta}}^ {2}\mathbbm{1}_{|\ell_{\bm{\theta}}|\leq c}\right]+c^{2}(1-\mu_{c})\right)$ (197) $\displaystyle\leq\frac{c^{2}}{2R+\sigma^{2}}$ $$

which gives the upper bound with coefficient $1$. Now for the lower bound. We can write,

$$ $\displaystyle\nu_{c}$ $\displaystyle=\frac{1}{2R+\sigma^{2}}\left(\int_{0}^{\infty}\mathbb{P}(\ell_{ \bm{\theta}}^{2}\mathbbm{1}_{|\ell_{\bm{\theta}}|\leq c}\geq t)\,\mathrm{d}t+c ^{2}(1-\mu_{c})\right)$ (198) $\displaystyle=\frac{1}{2R+\sigma^{2}}\left(\int_{0}^{c^{2}}\mathbb{P}(\ell_{ \bm{\theta}}^{2}\geq t)\,\mathrm{d}t+c^{2}(1-\mu_{c})\right)$ $\displaystyle\geq\frac{c^{2}}{2R+\sigma^{2}}2(1-\mu_{c})$ $$

So we can now use the $\mu_{c}$ bound derived above to obtain the desired bound for $\nu_{c}$.

∎

###### Theorem 8 .

###### Proof.

###### Corollary 1 .

###### Proof.

## Appendix F Proof of stability and effectiveness theorems

### F.1 Proof of Theorem 2

To see there exists $c>0$ such that (CSC) holds, it is simpler to work with the inverse of the ratio. We remark that

$$ $\displaystyle\lim_{c\to 0^{+}}\frac{\nu_{c}}{\mu_{c}}$ $\displaystyle=\lim_{c\to 0^{+}}\frac{\mathbb{E}(\ell^{2}\mathbbm{1}_{|\ell| \leq c}+c^{2}\mathbbm{1}_{|\ell|>c})}{\mathbb{P}(|\ell|\leq c)}$ (199) $\displaystyle=\lim_{c\to 0^{+}}\frac{1}{{\mathbb{P}(|\ell|\leq c)}}\int_{|\ell |\leq c}\ell^{2}\,d\mathbb{P}+\frac{c^{2}(1-\mathbb{P}(|\ell|\leq c))}{\mathbb {P}(|\ell|\leq c)}$ (200) $\displaystyle=\lim_{c\to 0^{+}}\frac{1}{{\mathbb{P}(|\ell|\leq c)}}\int_{|\ell |\leq c}\ell^{2}\,d\mathbb{P}+\frac{c^{2}}{\mathbb{P}(|\ell|<c)}.$ (201) $$

Therefore, it suffices to show that (201) is less than $1$. Indeed, the former term converges to 0 0 by the Lebesgue-Differentiation Theorem. For the latter, let us assume that $\epsilon\sim\pi$ for some probability-measure $\pi$. Given that $\mathbf{x}\sim N(0,\mathbf{K})$, let us denote $f$ to be the (Gaussian) density of $\left\langle\mathbf{x},\bm{\theta}-{\bm{\theta}^{*}}\right\rangle$. It follows that

$$ $\displaystyle\mathbb{P}(|\ell|\leq c)$ $\displaystyle=\mathbb{P}(-c+\epsilon\leq\left\langle\mathbf{x},\bm{\theta}-\bm {\theta}^{*}\right\rangle\leq c+\epsilon)$ (202) $\displaystyle=\int_{\mathbb{R}}\int_{-c+\epsilon}^{c+\epsilon}f(x)\,dx\,d\pi( \epsilon).$ (203) $$

Differentiating with respect to $c$ yields,

$$ $\displaystyle\frac{d}{dc}\left(\int_{\mathbb{R}}\int_{-c+\epsilon}^{c+\epsilon }f(x)\,dx\,d\pi(\epsilon)\right)=\int_{\mathbb{R}}f(c+\epsilon)+f(-c+\epsilon) \,d\pi(\epsilon).$ (204) $$

By L’Hôpital’s rule, the latter term of (201) becomes

$$ $\displaystyle\lim_{c\to 0}\frac{c^{2}}{\mathbb{P}(|\ell|<c)}$ $\displaystyle=\lim_{c\to 0}\frac{2c}{\int_{\mathbb{R}}f(c+\epsilon)+f(-c+ \epsilon)\,d\pi(\epsilon)}$ (205) $\displaystyle=\lim_{c\to 0^{+}}\frac{2c}{\int_{\mathbb{R}}2f(\epsilon)\,d\pi( \epsilon)}$ (206) $\displaystyle=0.$ (207) $$

### F.2 Proof of Theorem 3

First, notice that $\sigma^{2}=q\lambda^{2}$. In the limit as $|R_{t}|\to 0$ we have,

$$ $\displaystyle\mu(R_{t})$ $\displaystyle=\mathbb{P}(|\epsilon|\leq c)$ (208) $\displaystyle=\begin{cases}1&\lambda\leq c\\ 1-q&\lambda>c\end{cases}$ (209) $$

$$ $\displaystyle\nu(R_{t})=\begin{cases}1&\lambda\leq c\\ c^{2}/\lambda^{2}&\lambda>c\end{cases}$ (210) $$

thus

$$ $\displaystyle\frac{\mu(R_{t})}{\nu(R_{t})}$ $\displaystyle=1$ $\displaystyle\lambda<c$ (211) $\displaystyle\frac{\mu(R_{t})}{\nu(R_{t})}$ $\displaystyle>1$ $\displaystyle c<\sqrt{(1-q)}\lambda$ (212) $\displaystyle\frac{\mu(R_{t})}{\nu(R_{t})}$ $\displaystyle\leq 1$ $\displaystyle\sqrt{(1-q)}\lambda\leq c<\lambda$ (213) $$

thus $c$ may always be chosen such that the (CSC) is less than $1$.

### F.3 Proof of Theorem 5

With $\mu$ and $\nu$ given by equations (161) and (162) we have that

$$ $\lim_{c\to 0}\frac{\mu^{2}(R_{t})}{\nu(R_{t})}=\frac{2}{\pi}<1$ (214) $$

Meanwhile, it can be seen that for all $R_{t}\geq 0$ $\mu^{2}_{c}(R_{t})/\nu_{c}(R_{t})$ is increasing and continuous in $c$. Since,

$$ $\lim_{c\to\infty}\frac{\mu_{c}^{2}(R_{t})}{\nu(R_{t})}=1$ (215) $$

we are done.

### F.4 Proof of Theorem 6

In light of Section F.2 above, we see that

$$ $\displaystyle\frac{\mu_{c}(R_{t})^{2}}{\nu_{c}(R_{t})}$ $\displaystyle=1$ $\displaystyle\lambda<c$ (216) $\displaystyle\frac{\mu_{c}(R_{t})^{2}}{\nu_{c}(R_{t})}$ $\displaystyle>1$ $\displaystyle c<(1-q)\lambda$ (217) $\displaystyle\frac{\mu_{c}(R_{t})^{2}}{\nu_{c}(R_{t})}$ $\displaystyle\leq 1$ $\displaystyle(1-q)\lambda\leq c<\lambda$ (218) $$

thus $c$ may always be chosen such that the (CCC) holds.

## Appendix G The risk under anisotropic data

In this section, we describe how to use equation (12) to solve for the risk. First, define

$$ $q_{z}(\mathbf{z})=\mathbf{z}^{T}R(z;\mathbf{K})\mathbf{z}/2,$ (219) $$

where $R(z;\mathbf{K})=(\mathbf{K}-z\mathbf{I})^{-1}$ is the resolvent of $\mathbf{K}$. Using Itô’s Lemma and the resolvent identity $R(z;\mathbf{K})(\mathbf{K}-z)=\mathbf{I}$.

$$ $\displaystyle\mathrm{d}q_{z}(\bm{\Theta}_{t})=$ $\displaystyle-\eta(t)\left(\|\bm{\Theta}_{t}-{\bm{\theta}^{*}}\|^{2}+2zq_{z}( \bm{\Theta}_{t})\right)\mu_{c(t)}(\mathcal{R}(\bm{\Theta}_{t}))\mathrm{d}t$ (220) $\displaystyle+\frac{\eta^{2}(t)}{d}\operatorname{Tr}(\mathbf{K}R(z;\mathbf{K}) )\nu_{c(t)}(\mathcal{R}(\bm{\Theta}_{t}))\mathrm{d}t+\mathrm{d}\mathcal{M}_{t}.$ $$

We shall let $Q_{z}(t)$ be the deterministic equivalent of this equation, that is

$$ $\frac{\mathrm{d}}{\mathrm{d}t}Q_{z}(t)=-\eta(t)\left(\mathcal{D}_{t}+2zQ_{z}(t )\right)\mu_{c(t)}(R_{t})+\frac{\eta^{2}(t)}{d}\operatorname{Tr}(\mathbf{K}R(z ;\mathbf{K}))\nu_{c(t)}(R_{t}),$ (221) $$

where (recalling $\Omega$ is the circle of radius $2$)

$$ $D_{t}=\frac{-1}{2\pi i}\oint_{\Omega}Q_{z}(t)\mathrm{d}z\quad\text{and}\quad R _{t}=\frac{-1}{2\pi i}\oint_{\Omega}zQ_{z}(t)\mathrm{d}z.$ $$

These are analogues of the same formulas that hold exactly for $\mathcal{D}(\bm{\Theta}_{t})$ and $\mathcal{R}(\bm{\Theta}_{t})$ when replacing $Q_{z}$ by $q_{z}(\bm{\Theta}_{t})$.

Now it is possible to precisely compare the solution of these ODEs to SGD, as the same machinery developed for Theorem 1 applies. In particular, Lemma 1 bounds the supremum difference $\sup_{z\in\Omega}|q_{z}(\Theta_{t})-Q_{z}(t)|$ (although now with $\mathcal{M}_{t}^{SDE}\equiv 0$). Hence, we conclude the following:

###### Theorem 9 .

Suppose that Assumptions 1,
2 and 3 hold.
Suppose that $\{\bm{\theta}_{k}\}$ is C-SGD.
Let $\overline{c}=\sup_{t}c(t)$ and ${\overline{\eta}}=\sup_{t}{\eta}(t)$.
There is a constant $\mathcal{C}=\mathcal{C}(\dutchcal{v},(n/d),\overline{c},\overline{\eta},\|\bm{
\theta}_{0}-{\bm{\theta}^{*}}\|^{2})$, a stochastic process $\mathcal{E}$, and a constant $m=m(\dutchcal{v})$ so that for any $1\leq u\leq md$

$$ $\sup_{0\leq k\leq n}\left\|\begin{bmatrix}\mathcal{R}(\bm{\theta}_{k})\\ \mathcal{D}(\bm{\theta}_{k})\end{bmatrix}-\begin{bmatrix}R_{k/d}\\ D_{k/d}\end{bmatrix}\right\|\leq\mathcal{C}\mathcal{E}(n/d)u\log(d)d^{-1/2},$ (222) $$

with probability $1-e^{-u}$ and provided the right hand side is less than $1$.
The stochastic process $\mathcal{E}$ is given by

$$ $\mathcal{E}(t)=\exp\left(\int_{0}^{t}\frac{C{\eta}(s)^{2}\sigma\,\mathrm{d}s}{ \sqrt{\mathcal{R}(\bm{\Theta}_{s})+R_{s}}}\right)$ $$

for an absolute constant $C>0$.
The constant $\mathcal{C}$ can be bounded by

$$ $\mathcal{C}\leq C\sqrt{n/d}\,\overline{\eta}\dutchcal{v}^{2}\cdot((1+\|\bm{ \theta}_{0}-{\bm{\theta}^{*}}\|^{2})\dutchcal{v}^{2}+\overline{c}^{2}\sqrt{n/d })\cdot\exp\left(C\max\{\overline{\eta},\overline{\eta}^{2}\}(n/d)\right)$ $$

for an absolute constant $C>0.$

We note that further details in this direction are shown in Collins-Woodfin et al. ().

###### Theorem 9 .

### G.1 Getting a system of ODEs

We may use Equation (221) to get an equivalent coupled system of $\dutchcal{d}$ ODEs which can solve for $R_{t}$. First, we may diagonalize,

$$ $\displaystyle\mathbf{K}=\sum_{i=1}{d}\lambda_{i}w_{i}w_{i}^{T}$ $\displaystyle R(z;\mathbf{K})=\sum_{i=1}{d}\frac{1}{\lambda_{i}-z}w_{i}w_{i}^{T}$ (223) $$

Where $\{\lambda_{i}\}_{i=1}{d}$ and $\{w_{i}\}_{i=1}{d}$ are the eigenvalues and eigenvectors of $\mathbf{K}$ respectively. Therefore,

$$ $Q_{z}(\bm{\Theta}_{t})=\frac{1}{2}\sum_{i=1}{d}\frac{1}{\lambda_{i}-z}\left \langle\bm{\Theta}_{t}-{\bm{\theta}^{*}},w_{i}\right\rangle^{2}.$ (224) $$

Define $v_{i}(t)=\left\langle\bm{\Theta}_{t}-{\bm{\theta}^{*}},w_{i}\right\rangle^{2}/2$. Then, $R_{t}=\sum_{i=1}{d}v_{i}(t)\lambda_{i}$ and $D_{t}=\sum_{i=1}{d}2v_{i}(t)$. Now, we can find a system of ODEs which describes the evolution of $\{v_{i}\}_{i=1}{d}$.

Choose $\Omega_{i}$ to be a complex curve enclosing only the $i$-th eigenvalue of $\mathbf{K}$. Integrating over both sides of equation (221) and using Cauchy’s integral formula, we see that

$$ $\displaystyle\frac{\mathrm{d}v_{i}}{\mathrm{d}t}=-2\eta(t)v_{i}\lambda_{i}\mu_ {c(t)}(R_{t})+\frac{\eta(t)^{2}}{d}\lambda_{i}\nu_{c(t)}(R_{t})(R_{t}+\sigma^{ 2}/2),\quad\forall i\in[\dutchcal{d}].$ (225) $$

This final system of ODEs is used in all experiments to solve for $R_{t}$.

### G.2 Getting an Integral Equation

Using Equation (221) and an integrating factor we see that

$$ $\displaystyle Q_{z}(t)=$ $\displaystyle Q_{z}(0)e^{-2z\Omega_{t}^{c}}+\frac{1}{d}\int_{0}^{t}\eta(s)^{2} \nu_{c(s)}(R_{s})\operatorname{Tr}(\mathbf{K}R(z;\mathbf{K})e^{-2z(\Omega_{t}^ {c}-\Omega_{s}^{t})})(R_{s}+\sigma^{2}/2)\mathrm{d}s$ (226) $\displaystyle-\eta(t)D_{t}e^{-2z\Omega_{t}^{c}}\mu_{c(t)}(R_{t})$ $$

where $\Omega_{t}^{c}=\int_{0}^{t}\eta(s)\mu_{c(s)}(R_{s})\mathrm{d}s$ is the integrated clipped learning rate. Now, multiplying by $z$, integrating both sides around $\Omega$, and multiplying by $-1/2\pi i$, we get

$$ $R_{t}=\mathcal{R}(\bm{\Phi}^{\mathrm{gf}}_{\Gamma_{T}^{c}})+\frac{1}{d}\int_{0 }^{t}{\tilde{\eta}}^{2}(s)\nu_{c_{s}}\operatorname{Tr}(\mathbf{K}^{2}e^{-2 \mathbf{K}(\Gamma_{t}^{c}-\Gamma_{s}^{c})})(R_{s}+\sigma^{2}/2)\mathrm{d}s,$ (227) $$

where the first term is identified with gradient flow as in Paquette et al. ().

## Appendix H Experimental details

### H.1 Clipped SGD and Homogenized Clipped SGD

The code to reproduce these results is available at [Github](https://github.com/nmarzz/clip).

#### H.1.1 Figure 1

The experiments creating Figure 1 were carried out on an M1 Macbook Air. Homogenized clipped SGD is solved via a standard Euler-Maruyama algorithm. The procedure for solving for the risk is described in Appendix G.

The synthetic data was generated with ambient dimension $\dutchcal{d}=500$ while the intrinsic dimension is $d=180$. For both experiments, $c_{t}=0.9$, $\eta=0.7$. We plot the $80$% confidence interval across $100$ runs.

The CIFAR10 data was used to perform binary classification by regressing to $\pm 1$ labels. The data is split into classes 1 and 2 where class 1 contains: birds, cats, and dogs. Class 2 contains: trucks, ships, and planes. The data matrix $D$ is first passed through a random features model so that

$$ $D_{rf}=\tanh{DA}$ (228) $$

where $A$ is a random features matrix of independent standard Gaussians. In order to estimate ${\bm{\theta}^{*}}$ the regression problem was first solved using Sci-kit learn Pedregosa et al. () and the resulting solution was taken to be ${\bm{\theta}^{*}}$. The differences $\{y_{i}-\left\langle{\bm{\theta}^{*}},\mathbf{x}_{i}\right\rangle\}$ for all $\mathbf{x}_{i}\in D_{rf}$ was then assumed to be the noise. A histogram of this noise is available in Figure 9a. The noise was then fitted to a Gaussian. Finally, $\eta=0.1$ and
$c=0.5$ and the C-SGD plot represents the $80$% confidence interval over $50$ runs.

The Wikitext2 data was first processed for next-token-prediction. The data was tokenized and split into context lengths of at most $512$. The data was then embedded using the Huggingface implementation of GPT-2 Radford et al. () and passed through the same random features model as with CIFAR10. We again used Sci-kit learn to estimate ${\bm{\theta}^{*}}$ and the noise terms whose histogram is available in Figure 9b. The noise resembled a mixture of $3$-Gaussians and we therefore fit the noise to a Gaussian mixture model. In this case $\eta=0.4$ and $c=0.5$ and the C-SGD plot represents the $80$% confidence interval over $50$ runs.

Figure: (a) CIFAR10 noise
Refer to caption: x21.png

#### H.1.2 Figure 4

The experiments creating were again carried out on an M1 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 norm via 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 a cosine learning rate decay
(base learning rate $0.00625$). Both networks used GELU activation function.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
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.

2. 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?
soundness: 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.
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.

[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.
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.

2. 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.

3. 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.

[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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: * In the conclusion, the authors suggest extending the analysis to more complex losses. What are the bottlenecks for such an analysis?
* 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?
* 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?

Minor: 
* In Theorem 1, the subscript for $\theta_{sd}$  in the denominator of the definition of $\mathcal{E}$ should include a ceiling (or floor).
soundness: 3
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.
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.
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.

* 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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. More intuitive explanations for the connection between C-SGD and S-HSGD are welcomed.

2. 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.

3. Do you also take stability into consideration when comparing C-SGD and SGD in Section 5?
soundness: 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.

2. The theory seems to be clear and complete.
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.
weaknesses: 1. Although the theory looks promising, I think it's still restrictive due to the settings it applies: 
    - 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.
    - The theory typically requires the data $x$ to be Gaussian, or close to Gaussian as in Appendix A. This is still a restrictive assumption. 

2. 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.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
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?

2. 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?
soundness: 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.

2. 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
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.
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.

2. 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.

Meta-review: The paper studies the properties of clipped SGD for linear regression with mean squared error loss under specific data and noise distributions. The authors have addressed all the reviewers' concerns. All the reviewers are happy to recommend the acceptance of the paper. Please incorporate all the comments and discussions into the final version.

Decision: Accept (Poster)