# STRENGTH OF MINIBATCH NOISE IN SGD

**Liu Ziyin[∗], Kangqiao Liu[∗], Takashi Mori, & Masahito Ueda**
The University of Tokyo

ABSTRACT

The noise in stochastic gradient descent (SGD), caused by minibatch sampling,
is poorly understood despite its practical importance in deep learning. This work
presents the first systematic study of the SGD noise and fluctuations close to a
local minimum. We first analyze the SGD noise in linear regression in detail and
then derive a general formula for approximating SGD noise in different types of
minima. For application, our results (1) provide insight into the stability of training
a neural network, (2) suggest that a large learning rate can help generalization
by introducing an implicit regularization, (3) explain why the linear learning ratebatchsize scaling law fails at a large learning rate or at a small batchsize and (4) can
provide an understanding of how discrete-time nature of SGD affects the recently
discovered power-law phenomenon of SGD.

1 INTRODUCTION

Stochastic gradient descent (SGD) is the simple and efficient optimization algorithm behind the
success of deep learning (Allen-Zhu et al., 2019; Xing et al., 2018; Zhang et al., 2018; Wang et al.,
2020; He and Tao, 2020; Liu et al., 2021; Simsekli et al., 2019; Wu et al., 2020). Minibatch noise, also
known as the SGD noise, is the primary type of noise in the learning dynamics of neural networks.
Practically, minibatch noise is unavoidable because a modern computer’s memory is limited while the
size of the datasets we use is large; this demands the dataset to be split into “minibatches" for training.
At the same time, using minibatch is also a recommended practice because using a smaller batch
size often leads to better generalization performance (Hoffer et al., 2017). Therefore, understanding
minibatch noise in SGD has been one of the primary topics in deep learning theory. Dominantly many
theoretical studies take two approximations: (1) the continuous-time approximation, which takes
the infinitesimal step-size limit; (2) the Hessian approximation, which assumes that the covariance
matrix of the SGD noise is equal to the Hessian H. While these approximations have been shown to
provide some qualitative understanding, the limitation of these approximations is not well understood.
For example, it is still unsure when such approximations are valid, which hinders our capability to
assess the correctness of the results obtained by approximations.

In this work, we fill this gap by deriving analytical formulae for discrete-time SGD with arbitrary
learning rates and exact minibatch noise covariance. In summary, the main contributions are: (1)
we derive the strength and the shape of the minibatch SGD noise in the cases where the noise for
discrete-time SGD is analytically solvable; (2) we show that the SGD noise takes a different form
in different kinds of minima and propose general and more accurate approximations. This work is
organized as follows: Sec. 2 introduces the background. Sec. 3 discusses the related works. Sec. 4
outlines our theoretical results. Sec. 5 derives new approximation formulae for SGD noises. In
Sec. 6, we show how our results can provide practical and theoretical insights to problems relevant to
contemporary machine learning research. For reference, the relationship of this work to the previous
works is shown in Table 1.

2 BACKGROUND

In this section, we introduce the minibatch SGD algorithm. Let _xi,yi_ _i_ 1 [be a training set. We]
can define the gradient descent (GD) algorithm for a differentiable loss function L as wt **wt** 1
=
_λ_ **wL** **w,** **x,** **y**, where λ is the learning rate and w R[D] is the weights of the model. We consider { }[N]
−
an additive loss function for applying the minibatch SGD. = −
**Definition∇** ( { **1.** })A loss function _L_ _xi,yi_ _i_ 1[,] **[w] ∈[)]** is additive if _L_ _xi,yi_ _i_ 1[,] **[w][)]**
1

_N_ _i_ 1 _[ℓ][(][x][i][,y][i][,]_ **[w][)][ for some differentiable, non-negative function]=** _[ ℓ][(⋅)][.]_ =

({ }[N] ({ }[N] =

=

[∑][N]


-----

Table 1: Summary of related works on the noise and stationary distribution of SGD. This work fills the gap of
the lack of theoretical results for the actual SGD dynamics, which is discrete-time and with minibatch noise.

|Setting|Artificial Noise Hessian Approximation Noise Minibatch Noise|
|---|---|
|Continuous-time|Sato and Nakagawa (2014); Welling and Teh (2011) Jastrzebski et al. (2018); Zhu et al. (2019) Blanc et al. (2020); Mori et al. (2021) Mandt et al. (2017); Meng et al. (2020) Wu et al. (2020); Xie et al. (2021)|
|Discrete-time|Yaida (2019); Gitman et al. (2019) Liu et al. (2021) This Work Liu et al. (2021)|



This definition is quite general. Most commonly studied and used loss functions are additive, e.g.,
the mean-square error (MSE) and cross-entropy loss. For an additive loss, the minibatch SGD with
momentum algorithm can be defined.
**Definition 2. The minibatch SGD with momentum algorithm by sampling with replacement computes**
the update to the parameter w with the following set of equations:

**gˆt** _S[1]_ _t_

**mt** _µmt_ 1 ˆgt; (1)

⎧
⎪⎪⎪⎪wt = **w[∑]t** _[i]1[∈]−[B]_ _λ[∇]m[ℓ][(]t[x]._ _[i][,y][i][,]_ **[w][t][−][1][)][;]**
⎨ = +

where µ 0, 1 is the momentum hyperparameter,⎪⎪⎪⎪⎩ = − − _S_ _Bt_ is the minibatch size, and the set
_Bt_ _i1,...iS_ are S i.i.d. random integers sampled uniformly from 1,N .
∈[ ) ∶= ∣ ∣

One can decompose the gradient into a deterministic plus a stochastic term. Note that = { } [ ] EB **gˆt** _L_
is equal to the gradient for the GD algorithm. We use EB to denote the expectation over batches,
and use Ew to denote the expectation over the stationary distribution of the model parameters.[ ] = ∇
Therefore, we can write ˆgt EB **gˆt** _ηt, where ηt_ (⋅)S[1] _t_ **gt** is the

noise term; the noise covariance is(⋅) _C_ **wt** cov _ηt,ηt_ . Of central importance to us is the averaged
asymptotic noise covariance = C [ lim] +t Ewt _C_ **wt ∶=. Also, we consider the asymptotic model[∑][i][∈][B]** [∇][ℓ][(][x][i][,y][i][,] **[w][t][−][1][) −]** [E][B][[][ˆ] ]
fluctuation Σ limt cov **wt,** **wt** (. Σ gives the strength and shape of the fluctuation of) ∶= ( ) **w around**
→∞
a local minimum and is another quantity of central importance to this work. Throughout this work, ∶= [ ( )] _C_
→∞
is called the “noise" and ∶= Σ the “fluctuation".( )


3 RELATED WORKS

**Noise and Fluctuation in SGD. Deep learning models are trained with SGD and its variants. To**
understand the parameter distribution in deep learning, one needs to understand the stationary
distribution of SGD (Mandt et al., 2017). Sato and Nakagawa (2014) describes the stationary
distribution of stochastic gradient Langevin dynamics using discrete-time Fokker-Planck equation.

Yaida (2019) connects the covariance of parameter Σ to that of the noise C through the fluctuationdissipation theorem. When Σ is known, one may obtain by Laplace approximation the stationary
distribution of the model parameter around a local minimum w[∗] as _w[∗],_ Σ . Therefore, knowing
Σ can be of great practical use. For example, it has been used to estimate the local minimum escape
efficiency (Zhu et al., 2019; Liu et al., 2021) and argue that SGD prefers a flatter minimum; it can N( )
also be used to assess parameter uncertainty and prediction uncertainty when a Bayesian prior is
specified (Mandt et al., 2017; Gal and Ghahramani, 2016; Pearce et al., 2020). Empirically, both the
fluctuation and the noise are known to crucially affect the generalization of a deep neural network.
Wu et al. (2020) shows that the strength and shape of the Σ due to the minibatch noise lead to better
generalization of neural networks in comparison to an artificially constructed noise.

**Hessian Approximation of the Minibatch Noise. However, it is not yet known what form C and**
Σ actually take for SGD in a realistic learning setting. Early attempts assume isotropic noise in the
continuous-time limit (Sato and Nakagawa, 2014; Mandt et al., 2017). In this setting, the noise is
an isotropic Gaussian with C _ID, and Σ is known to be proportional to the inverse Hessian H_ [−][1].
More recently, the importance of noise structure was realized (Hoffer et al., 2017; Jastrzebski et al.,
2018; Zhu et al., 2019; HaoChen et al. ∼, 2020). “Hessian approximation", which assumes C _c0H_
for some unknown constant c0, has often been adopted for understanding SGD (see Table 1); this
assumption is often motivated by the fact that C _Jw_ _H, where Jw is the Fisher information matrix ≈_
(FIM) (Zhu et al., 2019); the fluctuation can be solved to be isotropic: Σ _ID. However, it is not_
known under what conditions the Hessian approximation is valid, while previous works have argued = ≈
that it can be very inaccurate (Martens, 2014; Liu et al., 2021; Thomas et al. ∼, 2020; Kunstner et al.,
2019). However, Martens (2014) and Kunstner et al. (2019) only focuses on the natural gradient
descent (NGD) setting; Thomas et al. (2020) is closest to ours, but it does not apply to the case with
momentum, a matrix learning rate, or regularization.


-----

**Discrete-time SGD with a Large Learning Rate. Recently, it has been realized that networks**
trained at a large learning rate have a dramatically better performance than networks trained with a
vanishing learning rate (lazy training) (Chizat and Bach, 2018). Lewkowycz et al. (2020) shows that
there is a qualitative difference between the lazy training regime and the large learning rate regime;
the performance features two plateaus in testing accuracy in the two regimes, with the large learning
rate regime performing much better. However, the theory regarding discrete-time SGD at a large
learning rate is almost non-existent, and it is also not known what Σ may be when the learning rate is
non-vanishing. Our work also sheds light on the behavior of SGD at a large learning rate. Some other
works also consider discrete-time SGD in a similar setting (Fontaine et al., 2021; Dieuleveut et al.,
2020; Toulis et al., 2017), but the focus is not on deriving analytical formulae or does not deal with
the stationary distribution.

4 SGD NOISE AND FLUCTUATION IN LINEAR REGRESSION

This section derives the shape and strength of SGD noise and fluctuation for linear regression;
concurrent to our work, Kunin et al. (2021) also studies the same problem but with continuous-time
approximation; our result is thus more general. To emphasize the message, we discuss the label noise
case in more detail. The other situations also deserve detailed analysis; we delay such discussion
to the appendix due to space constraints. Notation: S denotes the minibatch size. w R[D] is the
model parameter viewed in a vectorized form; λ R denotes a scalar learning rate; when the
learning rate takes the form of a preconditioning matrix, we use Λ R[D][×][D]. A R[D][×][D] ∈denotes the
+
covariance matrix of the input data. When a matrix ∈ _X is positive semi-definite, we write X_ 0;
throughout, we require Λ 0. γ R denotes the weight decay hyperparameter; when the weight ∈ ∈
decay hyperparameter is a matrix, we write Γ R[D][×][D]. µ is the momentum hyperparameter in SGD. ≥
For two matrices X,Y, the commutator is defined as ≥ ∈ _X,Y_ _XY_ _Y X. Other notations are_
introduced in the context.[1] The results of this section are numerically verified in Appendix ∈ A.
[ ] ∶= −

4.1 KEY PREVIOUS RESULTS
When N _S, the following proposition is well-known and gives the exact noise due to minibatch_
sampling. See Appendix E.1 for a derivation.
**Proposition 1. ≫** _The noise covariance of SGD as defined in Definition 2 is_

1 _N_
_C_ **w** _ℓi_ **w** _ℓi_ **w** (2)

_SN_ _i_ 1 _S_

_where the notations ℓi_ **w** _l_ _xi,yi,_ **w** _and L_ **w** _L_ _xi,yi_ _i_ 1[,] **[w][)][ are used.]**

( ) = ∑= ∇ ( )∇ ( )[T] − [1]

[∇][L][(][w][)∇][L][(][w][)][T][,]

This gradient covariance matrix( ) ∶= ( _C is crucial to understand the minibatch noise. The standard)_ ( ) ∶= ({ }[N]=
literature often assumes C **w** _H_ **w** ; however, the following well-known proposition shows that
this approximation can easily break down.

_ProofProposition 2.. Because Let ℓi is non-negative for all w∗_ _be the solution such that(_ ) ≈ ( ) _i, L_ **w** _L_ **w 0∗ implies that 0, then C ℓi** **ww∗** 0 0.. The differentiability

( ) = ( ) =

in turn implies that each _ℓi_ **w** 0; therefore, C 0.
∗ ∗
( ) = ( ) =

This proposition implies that there is no noise if our model can achieve zero training loss (which is∗

∇ ( ) = = ◻

achievable for an overparametrized model). This already suggests that the Hessian approximation
_C_ _H is wrong since the Hessian is unlikely to vanish in any minimum. The fact that the noise_
strength vanishes at L 0 suggests that the SGD noise might at least be proportional to L **w**, which
we will show to be true for many cases. The following theorem relates ∼ _C and Σ of the discrete-time_
SGD algorithm with momentum for a matrix learning rate. = ( )
**Theorem 1. (Liu et al., 2021) Consider running SGD on a quadratic loss function with Hessian H,**
_learning rate matrix Λ, momentum µ. Assuming ergodicity, then_

_µ_

1 _µ_ ΛHΣ ΣHΛ (3)

1 _µ[2][ Λ][H][Σ][H][Λ][ +]_ 1 _µ[2][ (][Λ][H][Λ][H][Σ][ +][ Σ][H][Λ][H][Λ][) =][ Λ][C][Λ][.]_

( − )( + ) − [1][ +][ µ][2]

Propostion 1 and Theorem 1 allow one to solve C and Σ. Equation (3) can be seen as a general

− −

form of the Lyapunov equation (Lyapunov, 1992) and is hard to solve in general (Hammarling, 1982;

Ye et al., 1998; Simoncini, 2016). Solving this analytical equation in settings of machine learning
relevance is one of the main technical contributions of this work.

1We use the word global minimum to refer to the global minimum of the loss function, i.e., where L 0 and
a local minimum refers to a minimum that has a non-negative loss, i.e., L 0.
=
≥


-----

4.2 RANDOM NOISE IN THE LABEL

We first consider the case when the labels contain noise. The loss function takes the form

1 _N_
_L_ **w** **w[T]xi** _yi_ _,_ (4)

2N _i_ 1

( ) = ∑= ( − )[2]

where xi R[D] are drawn from a zero-mean Gaussian distribution with feature covariance A
EB _xx[T]_, and yi **u[T]xi** _ϵi, for some fixed u and ϵi_ R is drawn from a distribution with zero
mean and finite second momentum ∈ _σ[2]. We redefine w_ **u** **w and let N** with D held fixed. ∶=
The following lemma finds[ ] = + C as a function of Σ. ∈
− → →∞

**Lemma 1.** _Covariance matrix for SGD noise in the label_ _Let N_ _and the model be updated_
_according to Eq. (1) with loss function in Eq. (4). Then,_
( ) →∞

_C_ [1] (5)

_S_

=

The model fluctuation can be obtained using this lemma.

[(][A][Σ][A][ +][ Tr][[][A][Σ][]][A][ +][ σ][2][A][)][.]

**Theorem 2.** _Fluctuation of model parameters with random noise in the label_ _Let the assumptions_
_be the same as in Lemma 1 and_ Λ,A 0. Then,
( )
[ Σ] = _[σ][2]_ _µ_ _[,]_ (6)

_S_ _S_

Tr ΛAG[−]µ[1] =
_where κµ_ 1 _S_ [Tr][ [[][Λ][AG][]]µ[−][1] [(][1][ +][ κ][µ] [)]1[Λ]µ[G][−][1]S

**Remark. ∶= This result is numerically validated in Appendix−** [1] []][ with][ G][µ][ ∶=][ 2][(][1][ −] _[µ][)][I][D][ −(][ 1]+[−][µ]_ [+] A[ 1]. The subscript[)] [Λ][A][.] _µ refers to momentum._
_To obtain results for vanilla SGD, one can set µ_ 0, which has the effect of reducing Gµ _G_
2ID 1 _S[1]_

_note that the results for momentum can be likewise studied. The assumption =_ Λ,A 0 is not too → =
_strong because this condition holds for a scalar learning rate and common second-order methods −(_ + [)] [Λ][A][. From now on, we focus on the case when][ µ][ =][ 0][ for notational simplicity, but we]
_such as Newton’s method._ [ ] =

If σ[2] 0, then Σ 0. This means that when there is no label noise, the model parameter has a
vanishing stationary fluctuation, which corroborates Proposition 2. When a scalar learning rate λ 1
and 1 = _S, we have =_
≪

Σ (7)

≪ 2S [I][D][,]

which is the result one would expect from the continuous-time theory with the Hessian approximation ≈ _[λσ][2]_
(Liu et al., 2021; Xie et al., 2021; Zhu et al., 2019), except for a correction factor of σ[2]. Therefore, a
Hessian approximation fails to account for the randomness in the data of strength σ[2]. We provide a
systematic and detailed comparison with the Hessian approximation in Table 2 of Appendix B.

Moreover, it is worth comparing the exact result in Theorem 2 with Eq. (7) in the regime of nonvanishing learning rate and small batch size. One notices two differences: (1) an anisotropic
enhancement, appearing in the matrix Gµ and taking the form _λ_ 1 1 _S_ _A; compared with the_
result in Liu et al. (2021), this term is due to the compound effect of using a large learning rate
and a small batchsize; (2) an isotropic enhancement term κ, which causes the overall magnitude − ( + / )
of fluctuations to increase; this term does not appear in the previous works that are based on the
Hessian approximation and is due to the minibatch sampling process alone. As the numerical
example in Appendix A shows, at large batch size, the discrete-time nature of SGD is the leading
source of fluctuation; at small batch size, the isotropic enhancement becomes the dominant source of
fluctuation. Therefore, the minibatch sampling process causes two different kinds of enhancement to
the fluctuation, potentially increasing the exploration power of SGD at initialization but reducing the
convergence speed.

Now, combining Theorem 2 and Lemma 1, one can obtain an explicit form of the noise covariance.

**Theorem 3. The noise covariance matrix of minibatch SGD with random noise in the label is**


_C_ _[σ][2]_ _µ_ _µ_ (8)

_S [A][ +][ σ]S[2][2][ (][1][ +][ κ]S[µ]_

= [+][ Tr][[][Λ][AG][−][1][]][I][D][)] _[A.]_

[)(][Λ][AG][−][1]


-----

By definition, C _J is the FIM. The Hessian approximation, in sharp contrast, can only account_
for the term in orange. A significant modification containing both anisotropic and isotropic (up
to Hessian) is required to fully understand SGD noise, even in this simple example. Additionally, =
comparing this result with the training loss (127), one can find that the noise covariance contains one
term that is proportional to the training loss. In fact, we will derive in Sec. 5 that containing a term
proportional to training loss is a general feature of the SGD noise. We also study the case when the
input is contaminated with noise. Interestingly, the result is the same with the label noise case with
_σ[2]_ replaced by a more complicated term of the form Tr _AK_ [−][1]BU . We thus omit this part from the
main text. A detailed discussion can be found in Appendix E.3.1. In the next section, we study the
effect of regularization on SGD noise and fluctuation. [ ]

4.3 LEARNING WITH REGULARIZATION

Now, we show that regularization also causes a unique SGD noise. The loss function for Γ _L2_
regularized linear regression is

_N_ −

1 2
_LΓ_ **w** **w** **u** _xi_ 1 (9)

2N _i_ 1 2 **[w][T][Γ][w][ =][ 1]2** [(][w][ −] **[u][)][T][A][(][w][ −]** **[u][) +][ 1]2** **[w][T][Γ][w][,]**

where Γ is a symmetric matrix; conventionally, one set( ) = ∑= [( − )[T] ] + Γ _γID with a scalar γ_ 0. For conciseness,
we assume that there is no noise in the label, namely yi **u[T]xi with a constant vector u. One**
important quantity in this case will be uu[T] _U_ . The noise for this form of regularization can be = >
calculated but takes a complicated form. =
∶=
**Proposition 3.** _Noise covariance matrix for learning with L2 regularization_ _Let the algorithm be_
_updated according to Eq. (1) on loss function (9) with N_ _and_ _A,_ Γ 0. Then,
( )

_C_ [1] →∞ [ ] = (10)

_S_

_where A[′]_ _K_ [−][1]A, Γ =[′] _K[(][−][A][1][Σ]Γ[A] with[ +][ Tr] K[[][A][Σ] A[]][A][ +] Γ[ Tr]._ [[][Γ][′][T][A][Γ][′][U] []][A][ +][ Γ][A][′][UA][′][Γ][)] _[,]_

Notice that the last term∶= ∶= ΓA[′]UA[′]Γ in C ∶= is unique to the regularization-based noise: it is rank-1 +
because U is rank-1. This term is due to the mismatch between the regularization and the minimum of
the original loss. Also, note that the term Tr _AΣ_ is proportional to the training loss. Define the test
loss to be Ltest limt Ewt [1]2 [(][w][t][ −] **[u][)][T][A][(][w][t][ −]** **[u][)]][, we can prove the following theorem. We]**

will show that one intriguing feature of discrete-time SGD is that the weight decay can be negative.[ ]

→∞

**Theorem 4.** _Test loss and model fluctuation for L ∶=_ [ 2 regularization _Let the assumptions be the same_
_as in Proposition 3. Then_
( )

_Ltest_ _[λ]_ (11)

2S 2 [Tr][[][AK] [−][2][Γ][2][U] []][,]

Tr _A[2]K[−][1]G[−][1]_
_where κ_ 1 _S_ [Tr][[][A][2][K][−][1][G][−][1] =[]] _[,][ r][ ∶=][(][ Tr]1[Tr][[]S[[][A][AK][Tr][3][K][[][A][−][−][3][2][2][Γ][K][Γ][2][−][G][2][1][U][−][G][1][−][]][U][1][κ][]][]][ +][, with][ r][) +][ G][ 1][ ∶=][ 2][I][D][ −]_ _[λ]_ [(][K][ +][ 1]S _[K]_ [−][1][A][2][)][. Moreover,]

[ ]

_let_ Γ,U 0, then

− _[λ]_ − _[λ]_

∶=

[ ] =Σ _[λ]_ (12)

_S_ [Tr][[][AK] [−][2][Γ][2][U] [](][1][ +][ λκ]S _S_ _S [A][)]_ _[K]_ [−][1][G][−][1][.]

=

This result is numerically validated in Appendix[)] _[AK]_ [−][1] A[G]. The test loss[−][1][ +][ λ] [(][A][2][K] ([−]11[2][Γ])[2] has an interesting consequence.[U][ +][ λr]
One can show that there exist situations where the optimal Γ is negative.[2] When discussing the test
loss, we make the convention that if wt diverges, then Ltest .
**Corollary 1. Let γ[∗]** arg minγ Ltest. There exist a, λ and S such that γ[∗] 0.
= ∞

The proof shows that when the learning rate is sufficiently large, only negative weight decay is= <
allowed. This agrees with the argument in Liu et al. (2021) that discrete-time SGD introduces an
implicit L2 regularization that favors small norm solutions. A too-large learning rate requires a
negative weight decay because a large learning rate already over-regularizes the model and one needs

2Some readers might argue that discussing test loss is meaningless when N ; however, this criticism
does not apply because the size of the training set is not the only factor that affects generalization. In fact, this
section’s crucial message is that using a large learning rate affects the generalization by implicitly regularizing →∞
the model and, if one over-regularizes, one needs to offset this effect.


-----

to introduce an explicit negative weight decay to offset this over-regularization effect of SGD. This is
a piece of direct evidence that using a large learning rate can help regularize the models. It has been
hypothesized that the dynamics of SGD implicitly regularizes neural networks such that the training
favors simpler solutions (Kalimeris et al., 2019). Our result suggests one new mechanism for such a
regularization.

5 NOISE STRUCTURE FOR GENERIC SETTINGS

The results in the previous sections suggest that (1) the SGD noises differ for different kinds of
situations, and (2) SGD noise contains a term proportional to the training loss in general. These two
facts motivate us to derive the noise covariance differently for different kinds of minima. Let f **w,x**
denote the output of the model for a given input x R[D]. Here, we consider a more general case;
_f_ **w,x** may be any differentiable function, e.g., a non-linear deep neural network. The number of( )
parameters in the model is denoted by P, and hence w ∈ R[P] . For a training dataset _xi,yi_ _i_ 1,2,...,N,
the loss function with a( ) _L2 regularization is given by_
=
∈ { }

_LΓ_ **w** _L0_ **w** [1] (13)

2 **[w][T][Γ][w][,]**

1
where L0 **w** _N_ _i_ 1 _[ℓ][(][f]_ [(][w][,x][i][)][,y]([i][)][ is the loss function without regularization, and]) = ( ) + _[ H][0]_ [is the]

Hessian of L0. We focus on the MSE loss ℓ _f_ **w,xi** _,yi_ _f_ **w,xi** _yi_ 2. Our result crucially
=
relies on the following two assumptions, which relate to the conditions of different kinds of local( ) = [∑][N]
minima. ( ( ) ) = [ ( ) − ][2]/
**Assumption 1. (Fluctuation decays with batch size) Σ is proportional to S[−][1], i.e. Σ** _O_ _S[−][1]_ .

This is justified by the results in all the related works (Liu et al., 2021; Xie et al., 2021 =; Meng et al.( ),
2020; Mori et al., 2021), where Σ is found to be O _S[−][1]_ .
**Assumption 2. (Weak homogeneity)** _L_ _ℓi_ is small; in particular, it is of order o _L_ .
( )

This assumption amounts to assuming that the current training loss ∣ − ∣ _L reflects the actual level of(_ )
approximation for each data point well. In fact, since L 0, one can easily show that _L_ _ℓi_ _O_ _L_ .
Here, we require a slightly stronger condition for a more clean expression, when _L_ _ℓi_ _O_ _L_
we can still get a similar expression but with some constant that hinders the clarity. Relaxing this ≥ ∣ − ∣= ( )
condition can be an important and interesting future work. The above two conditions allow us to state ∣ − ∣= ( )
our general theorem formally.
**Theorem 5. Let the training loss be LΓ** _L0_ [1]2 **[w][T][Γ][w][ and the models be optimized with SGD in]**

_the neighborhood of a local minimum w[∗]. Then,_

= +

_C_ **w** [2][L][0][(][w][)] _H0_ **w** (14)

_S_ _S_

( ) = ( ) − [1]

The noise takes different forms for different kinds of local minima.[∇][L][Γ][(][w][)∇][L][Γ][(][w][)][T][ +][ o][(][L][0][)][.]
**Corollary 2. Omitting the terms of order o** _L0_ _, when Γ_ 0,

_C_ [2][L][0][(][w][∗][)] _H0_ **w[∗]** ( ) ≠ (15)

_S_ _S_ [Γ][w][∗][w][∗][T][Γ][ +][ O][(][S][−][2][) +][ O][(∣][w][ −] **[w][∗][∣][2][)][.]**

_When Γ_ 0 and L =0 **w[∗]** 0, ( ) − [1]
= ( ) ≠C [2][L][0][(][w][∗][)] _H0_ **w[∗]** _O_ _S[−][2]_ _O_ **w** **w[∗]** _._ (16)

_S_

_When Γ_ 0 and L0 **w[∗]** = 0, ( ) + ( ) + (∣ − ∣[2])
= _C_ [1] ( ) = (17)

_S_

**Remark. Assumption =** _2 can be replaced by a weaker but more technical assumption called the_

[(][Tr][[][H][0][(][w][∗][)][Σ][]][I][D][ −] _[H][0][(][w][∗][)][Σ][)]_ _[H][0][(][w][∗][) +][ O][(][S][−][2][) +][ O][(∣][w][ −]_ **[w][∗][∣][2][)][.]**

_“decoupling assumption", which has been used in recent works to derive the continuous-time distri-_
_bution of SGD (Mori et al., 2021; Wojtowytsch, 2021). The Hessian approximation was invoked in_
_most of the literature without considering the conditions of its applicability (Jastrzebski et al., 2018;_
_Zhu et al., 2019; Liu et al., 2021; Wu et al., 2020; Xie et al., 2021). Our result does provide such_


-----

_conditions for applicability. As indicated by the two assumptions, this theorem is applicable when_
_the batch size is not too small and when the local minimum has a loss close to 0. The reason for_
_the failure of the Hessian approximation is that, while the FIM is equal to the expected Hessian_
_J_ E _H_ _, there is no reason to expect the expected Hessian to be close to the actual Hessian of the_
_minimum._
= [ ]

The proof is given in Appendix C. Two crucial messages this corollary delivers are (1) the SGD
noise is different in strength and shape in different kinds of local minima and that they need to be
analyzed differently; (2) the SGD noise contains a term that is proportional to the training loss L0 in
general. Recently, it has been experimentally demonstrated that the SGD noise is indeed proportional
to the training loss in realistic deep neural network settings, both when the loss function is MSE
and cross-entropy (Mori et al., 2021); our result offers a theoretical justification. The previous
works all treat all the minima as if the noise is similar (Jastrzebski et al., 2018; Zhu et al., 2019;
Liu et al., 2021; Wu et al., 2020; Xie et al., 2021), which can lead to inaccurate or even incorrect
understanding. For example, Theorem 3.2 in Xie et al. (2021) predicts a high escape probability from
a sharp local or global minimum. However, this is incorrect because a model at a global minimum has
zero probability of escaping due to a vanishing gradient. In contrast, the escape rate results derived
in Mori et al. (2021) correctly differentiate the local and global minima. We also note that these
general formulae are consistent with the exact solutions we obtained in the previous section than the
Hessian approximation. For example, the dependence of the noise strength on the training loss in
Theorem 2, and the rank-1 noise of regularization are all reflected in these formulae. In contrast, the
simple Hessian approximation misses these crucial distinctions. Lastly, combining Theorem 5 with
Theorem 1, one can also find the fluctuation.
**Corollary 3. Let the noise be as in Theorem 5, and omit the terms of order O** _S[−][2]_ _and_
_O_ **w** **w[∗]** _. Then, when Γ_ 0 and when Λ, H0 **w[∗]** _and Γ commute with each other, Pr_ Σ

_S1_ (∣1Λµ −[(][2][L][0][H]∣[2][0])[ −] [Γ][w][∗][w][∗][T][Γ][)(] ≠[H][0][ +][ Γ][)][+][ [][2][I][D][ −] 1Λµ([(][H][0])[ +][ Γ][)]]−1. When Γ 0 and L0( **w[∗])** ′ =0,

1

2L0 Λ
_PrΣ−_ _S_ 1 _µ_ 1 _µ_ _[H][0][)]_ _. When Γ_ 0+ and L0 **w[∗]** 0, PrΣ 0 =. Here the superscript( ) ≠

−
_is the Moore-Penrose pseudo inverse, Pr_ diag 1,..., 1, 0,..., 0 _is the projection operator with_

( − ) _[P][r][Λ]_ [(][2][I][D][ −] +

_r non-zero entries, =_ _r_ _D is the rank of the Hessian =_ _H0, and(_ _r) =[′]_ _D is the rank of =_ _H0_ Γ. For the
_null space+_ _H0, Σ can be arbitrary._ ∶= ( )
≤ ≤ +

6 APPLICATIONS

One major advantage of analytical solutions is that they can be applied in a simple “plug-in" manner
by the practitioners or theorists to analyze new problems they encounter. In this section, we briefly
outline a few examples where the proposed theories can be relevant.

6.1 HIGH-DIMENSIONAL REGRESSION

We first apply our result to the high-dimensional regression problem and show how over-andunderparametrization might play a role in determining the minibatch noise. Here, we take N,D
with the ratio α _N_ _D held fixed. The loss function is L_ **w** 21N _i_ 1 2. As in the
→∞

standard literature (Hastie et al., 2019), we assume the existence of label noise: yi **u[T]xi** _ϵi, with_
=
Var _ϵi_ _σ[2]. A key difference between our setting and the standard high-dimensional setting is ∶=_ / ( ) = [∑][N] [(][w][T][x][i] [−] _[y][i][)]_
that, in the standard setting (Hastie et al., 2019), one uses the GD algorithm with vanishing learning = +
rate[ λ instead of the minibatch SGD algorithm with a non-vanishing learning rate. Tackling the] =
high-dimensional regression problem with non-vanishing λ and a minibatch noise is another main
technical contribution of this work. In this setting, we can obtain the following result on the noise
covariance matrix.
**Proposition 4. Let** _A[ˆ]_ _N[1]_ _i_ _[x][i][x]i[T]_ _[and suppose assumptions][ 1][ and][ 2][ hold. With fixed][ S][,][ λ][, then]_

_C_ _S[1]_ _AΣ_ _ID_ _AΣ_ _A[ˆ]_ max 0, _[σ]S[2]_ _α_ [)}][ ˆ]A.

= [∑][N]

We note that this proposition follows from Theorem 5, showing an important theoretical application
of our general theory. An interesting observation is that one = [(][Tr][[][ ˆ] ] − [ˆ] ) + { [(][1][ −] [1] Σ-independent term proportional to σ[2]
emerges in the underparametrized regime (α 1). However, for the overparametrized regime, the
noise is completely dependent on Σ, which is a sign that the stationary solution has no fluctuation.
This shows that the degree of underparametrization also plays a distinctive role in the fluctuation. In >
fact, one can prove the following theorem, which is verified in Appendix A.2.


-----

Figure 1: Realistic learning settings with neural networks and logistic regression. Left: Variance of training loss
of a neural network with width d and tanh activation on the MNIST dataset. We see that the variance explodes
after d 200. In contrast, rescaling the learning rate by 1 _d results in a constant noise level in training. This_
suggests that the stability condition we derived for high-dimension regression is also useful for understanding
deep learning. ≥ **Middle: Stability of Adam with the same setting. Adam also experiences a similar stability/**
problem when the model width increases. Right: Logistic regression on MNIST trained with SGD; with λ 1.5,
_S_ 32. We see that the optimal performance is also achieved at negative weight decay strength γ, suggesting
that a large learning rate can indeed introduce effective regularization. =
=

**Theorem 6. When a stationary solution exists for w, we have Tr** _A[ˆ]Σ_ max 0, _[λσ]S_ [2] _α_ [)][ ˆ]κ _,_

_where ˆκ_ 1 TrS [Tr][G[ˆ][[][−]G[ ˆ][1][ ˆ]A[−][1]][ ˆ]A _[with][ ˆ]G_ 2ID _λ_ 1 _S_ _A._ [ ] = { [(][1][ −] [1] }

6.2 IMPLICATION FOR ∶= − _[λ]_ ] NEURAL ∶= NETWORK − ( − T[1]RAINING[)][ ˆ]

It is commonly believed that the high-dimensional linear regression problem can be a minimal model
for deep learning. Taking this stance, Theorem 6 suggests a technique for training neural networks.
For SGD to converge, a positive semi-definite Σ must exist; however, Σ 0 if and only if ˆκ 0.
From ˆκ 0, we have _i_ 1 2 _λai_ 11 1 _S_ _A. This means that each_
≥ ≥

summand should have the order of= / − + D/ _S. Thus the upper bound of λ should have the order of 2S_ _aD,_
where a > is the typical value of ∑[D] _ai’s. One implication of the dependence on the dimension is that the[<][ S][, where][ a][i][ are the eigenvalues of][ ˆ]_
stability of a neural network trained with SGD may strongly depend on its width/ _d, and one may/_
rescale the learning rate according to the width to stabilize neural network training. See Figure 1-Left
and Middle. We train a two-layer tanh neural network on MNIST and plot the variance of its training
loss in the first epoch with fixed λ 0.5. We see that, when d 200, the training starts to destabilize,
and the training loss begins to fluctuate dramatically. When rescaling the learning rate by 1 _d, we see_
that the variance of the training loss is successfully kept roughly constant across all = ≥ _d. This suggests_
a training technique worth being explored by practitioners in the field. In Figure 1-Middle, we also/
use Adam for training the same network and find a similar stabilizing trick to work for Adam.

6.3 A NATURAL LEARNING EXAMPLE WITH NEGATIVE WEIGHT DECAY
Sec. 4.3 shows that a too-large learning rate introduces an effective L2 regularization that can be
corrected by setting the weight decay to be negative. This effect can be observed in more realistic
learning settings. We train a logistic regressor on the MNIST dataset with a large learning rate (of
order O 1 ). Figure 1-Right confirms that, at a large learning rate, the optimal weight decay can
indeed be negative. This agrees with our argument that using a large learning rate can effectively
regularize the training.( )

6.4 SECOND-ORDER METHODS
Understanding stochastic second-order methods (including the adaptive gradient methods) is also
important for deep learning (Agarwal et al., 2017; Zhang and Liu, 2021; Martens, 2014; Kunstner
et al., 2019). In this section, we apply our theory to two standard second-order methods: damped
Newton’s method (DNM) and natural gradient descent (NGD). We provide more accurate results
than those derived in Liu et al. (2021). The derivations are given in Appendix D.2. For DNM, the
preconditioning learning rate matrix is defined as Λ _λA[−][1]. The model fluctuation is shown to_
_λσ[2]_
be proportional to the inverse of the Hessian: Σ _gS_ _λD_ _[A][−][1][, where][ g][ ∶=][ 2][(][1][ −]_ _[µ][) −(][ 1]1[−][µ]µ_ _S_
∶=

The main difference with the previous results is that the fluctuation now depends explicitly on the

− +

dimension D, and implies a stability condition: = S _λD_ _g, corroborating the stability condition[+][ 1]_ [)] _[λ][.]_
we derived above. For NGD, the preconditioning matrix is defined by the inverse of the Fisher
information that Λ _Sλ_ _[J][(][w][)][−][1][ =]_ _Sλ_ _[C]_ [−][1][. We show that] ≥ / [ Σ][ =][ λ]2 1 1D 1 1µ 1 1µ _S1_

solution when σ 0, which also contains a correction related to D compared to the result in Liu

+ + −

∶= 1 1 1

et al. (2021) which is Σ _[λ]2_ 1 _µ_ 1 _µ_ _S_ [(] [+] [)] _[A][−][1][ is one]_
=

+ −

= [(] [+] [)] _[A][−][1][. A consequence is that][ J][ ∼]_ [Σ][−][1][. The surprising]


-----

fact is that the stability of both NGD and DNM now crucially depends on D; combining with the
results in Sec. 6.1, this suggests that the dimension of the problem may crucially affect the stability
and performance of the minibatch-based algorithms. This result also implies that some features we
derived are shared across many algorithms that depend on minibatch noise and that our results may
be relevant to a broad class of optimization algorithms other than SGD.

6.5 FAILURE OF THE λ _S SCALING LAW_
One well-known technique in deep learning training is that one can scale λ linearly as one increases
−
the batch size S to achieve high-efficiency training without hindering the generalization performance;
however, it is known that this scaling law fails when the learning rate is too large, or the batch size is
too small (Goyal et al., 2017). In Hoffer et al. (2017), this scaling law is established on the ground
that Σ _λ_ _S. However, our result in Theorem 2 suggests the reason for the failure even for the_
simple setting of linear regression. Recall that the exact Σ takes the form:
∼ /

Σ _[λσ]S_ [2] 1 _[κ]S[µ]_ _µ_

for a scalar λ. One notices that the leading term is indeed proportional to = ( + _λ_ _S. However, the_

[)] _[G][−][1]_

discrete-time SGD results in a second-order correction in S, and the term proportional to 1 _S[2]_ does
not contain a corresponding λ; this explains the failure of the scaling law in small/ _S, where the_
second-order contribution of S becomes significant. To understand the failure at large λ, we need to/
look at the term Gµ:

_Gµ_ 2 1 _µ_ _ID_ _λ_ [1][ −] _[µ]_

1 _µ_ _S_

One notices that the second term contains a part that only depends on = ( − ) −( _λ but not on S. This part is_
negligible compared to the first term when λ is small; however, it becomes significant as the second + [+][ λ] [)] _[A.]_
term approaches the first term. Therefore, increasing λ changes this part of the fluctuation, and the
scaling law no more holds if λ is large.

6.6 POWER LAW TAIL IN DISCRETE-TIME SGD


It has recently been discovered that the SGD noise causes a heavytail distribution (Simsekli et al., 2019; 2020), with a tail decaying
like a power law with tail index β (Hodgkinson and Mahoney,
2020). In continuous-time, the stationary distribution has been
found to obey a Student’s t-like distribution, p _w_ _L[−(][1][+][β][)/][2]_

1 _β_ 2
_σ[2]_ _aw[2]_ (Meng et al., 2020; Mori et al., 2021; Wo−( + )/ ( ) ∼ ∼
jtowytsch, 2021). However, this result is only established for
continuous-time approximations to SGD and one does not know( + )

Figure 2: Comparison of the pro
what affects the exponent β for discrete-time SGD. Our result in

posed theory with the continuous
Theorem 2 can serve as a tool to find the discrete-time correction

time theory on the SGD station
to the tail index of the stationary distribution. In Appendix D.3, we

ary distribution for aλ 1. The

show that the tail index of discrete-time SGD in 1d can be estimated

proposed theory agrees with the

as β _λ,S_ [2]aλ[S] experiment exactly. =

which depends only on the batch size, while [2]aλ[S]

et al.(, 2021) =). See Figure[−] _[S][. A clear discrete-time contribution is] 2; the proposed formula agrees with the experiment. Knowing the tail index[ −(][S][ +][ 1][)]_
_β is important for understanding the SGD dynamics because β is equal to the smallest moment of_

[+] [1][ is the tail index in the continuous-time limit (][Mori]
_w that diverges. For example, when β_ 4, then the kurtosis of w diverges, and one expects to see
outliers of w very often during training; when β 2, then the second moment of w diverges, and
one does not expect w to converge in the minimum under consideration. Our result suggests that the ≤
discrete-time dynamics always leads to a heavier tail than the continuous-time theory expects, and ≤
therefore is more unstable.

7 OUTLOOK

In this work, we have presented a systematic analysis with a focus on exactly solvable results to
promote our fundamental understanding of SGD. One major limitation is that we have only focused
on studying the asymptotic behavior of SGD in local minimum. For example, Ziyin et al. (2022)
showed that SGD can converge to a local maximum when the learning rate is large. One important
future step is thus to understand the SGD noise beyond a strongly convex landscape.


-----

ACKNOWLEDGEMENT

Liu Ziyin thanks Jie Zhang, Junxia Wang, and Shoki Sugimoto. Ziyin is supported by the GSS
Scholarship of The University of Tokyo. Kangqiao Liu was supported by the GSGC program of
the University of Tokyo. This work was supported by KAKENHI Grant Numbers JP18H01145 and
JP21H05185 from the Japan Society for the Promotion of Science.

REFERENCES

Agarwal, N., Bullins, B., and Hazan, E. (2017). Second-order stochastic optimization for machine
learning in linear time. The Journal of Machine Learning Research, 18(1):4148–4187.

Allen-Zhu, Z., Li, Y., and Song, Z. (2019). A convergence theory for deep learning via overparameterization. In International Conference on Machine Learning, pages 242–252. PMLR.

Amari, S.-I. (1998). Natural gradient works efficiently in learning. Neural Comput., 10(2):251–276.

Blanc, G., Gupta, N., Valiant, G., and Valiant, P. (2020). Implicit regularization for deep neural
networks driven by an ornstein-uhlenbeck like process. In Conference on learning theory, pages
483–513. PMLR.

Chizat, L. and Bach, F. (2018). A note on lazy training in supervised differentiable programming.
_arXiv preprint arXiv:1812.07956, 8._

Clauset, A., Shalizi, C. R., and Newman, M. E. (2009). Power-law distributions in empirical data.
_SIAM review, 51(4):661–703._

Dieuleveut, A., Durmus, A., Bach, F., et al. (2020). Bridging the gap between constant step size
stochastic gradient descent and markov chains. Annals of Statistics, 48(3):1348–1382.

Fontaine, X., Bortoli, V. D., and Durmus, A. (2021). Convergence rates and approximation results
for sgd and its continuous-time counterpart.

Gal, Y. and Ghahramani, Z. (2016). Dropout as a bayesian approximation: Representing model
uncertainty in deep learning. In international conference on machine learning, pages 1050–1059.
PMLR.

Gitman, I., Lang, H., Zhang, P., and Xiao, L. (2019). Understanding the role of momentum in
stochastic gradient methods. In Advances in Neural Information Processing Systems, pages
9633–9643.

Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y.,
and He, K. (2017). Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint
_arXiv:1706.02677._

Hammarling, S. J. (1982). Numerical solution of the stable, non-negative definite lyapunov equation
lyapunov equation. IMA Journal of Numerical Analysis, 2(3):303–323.

HaoChen, J. Z., Wei, C., Lee, J. D., and Ma, T. (2020). Shape matters: Understanding the implicit
bias of the noise covariance. arXiv preprint arXiv:2006.08680.

Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. (2019). Surprises in high-dimensional
ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560.

He, F. and Tao, D. (2020). Recent advances in deep learning theory. arXiv preprint arXiv:2012.10931.

Hodgkinson, L. and Mahoney, M. W. (2020). Multiplicative noise and heavy tails in stochastic
optimization. arXiv preprint arXiv:2006.06293.

Hoffer, E., Hubara, I., and Soudry, D. (2017). Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In Advances in Neural Information Processing
_Systems, pages 1731–1741._


-----

Janssen, P. H. M. and Stoica, P. (1988). On the expectation of the product of four matrix-valued
gaussian random variables. IEEE Transactions on Automatic Control, 33(9):867–870.

Jastrzebski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Storkey, A., and Bengio, Y. (2018).
Three factors influencing minima in SGD.

Kalimeris, D., Kaplun, G., Nakkiran, P., Edelman, B., Yang, T., Barak, B., and Zhang, H. (2019). Sgd
on neural networks learns functions of increasing complexity. Advances in Neural Information
_Processing Systems, 32:3496–3506._

Kunin, D., Sagastuy-Brena, J., Gillespie, L., Margalit, E., Tanaka, H., Ganguli, S., and Yamins, D. L.
(2021). Rethinking the limiting dynamics of sgd: modified loss, phase space oscillations, and
anomalous diffusion. arXiv preprint arXiv:2107.09133.

Kunstner, F., Balles, L., and Hennig, P. (2019). Limitations of the empirical fisher approximation for
natural gradient descent. arXiv preprint arXiv:1905.12558.

Levy, M. and Solomon, S. (1996). Power laws are logarithmic boltzmann laws. International Journal
_of Modern Physics C, 7(04):595–601._

Lewkowycz, A., Bahri, Y., Dyer, E., Sohl-Dickstein, J., and Gur-Ari, G. (2020). The large learning
rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02218.

Liu, K., Ziyin, L., and Ueda, M. (2021). Noise and fluctuation of finite learning rate stochastic
gradient descent. arXiv preprint arXiv:2012.03636.

Lyapunov, A. M. (1992). The general problem of the stability of motion. International journal of
_control, 55(3):531–534._

Mandt, S., Hoffman, M. D., and Blei, D. M. (2017). Stochastic gradient descent as approximate
bayesian inference. J. Mach. Learn. Res., 18(1):4873–4907.

Martens, J. (2014). New insights and perspectives on the natural gradient method. cite
arxiv:1412.1193Comment: New title and abstract. Added multiple sections, including a proper
introduction/outline and one on convergence speed. Many other revisions throughout.

Meng, Q., Gong, S., Chen, W., Ma, Z.-M., and Liu, T.-Y. (2020). Dynamic of stochastic gradient
descent with state-dependent noise. arXiv preprint arXiv:2006.13719.

Mori, T., Ziyin, L., Liu, K., and Ueda, M. (2021). Logarithmic landscape and power-law escape rate
of sgd. arXiv preprint arXiv:2105.09557.

Pearce, T., Leibfried, F., and Brintrup, A. (2020). Uncertainty in neural networks: Approximately
bayesian ensembling. In International conference on artificial intelligence and statistics, pages
234–244. PMLR.

Sato, I. and Nakagawa, H. (2014). Approximation analysis of stochastic gradient langevin dynamics
by using fokker-planck equation and ito process. In International Conference on Machine Learning,
pages 982–990. PMLR.

Simoncini, V. (2016). Computational methods for linear matrix equations. SIAM Review, 58(3):377–
441.

Simsekli, U., Sagun, L., and Gurbuzbalaban, M. (2019). A tail-index analysis of stochastic gradient
noise in deep neural networks. In International Conference on Machine Learning, pages 5827–
5837. PMLR.

Simsekli, U., Sener, O., Deligiannidis, G., and Erdogdu, M. A. (2020). Hausdorff dimension, heavy
tails, and generalization in neural networks. Advances in Neural Information Processing Systems,
33.

Thomas, V., Pedregosa, F., Merriënboer, B., Manzagol, P.-A., Bengio, Y., and Le Roux, N. (2020).
On the interplay between noise and curvature and its effect on optimization and generalization. In
_International Conference on Artificial Intelligence and Statistics, pages 3503–3513. PMLR._


-----

Toulis, P., Airoldi, E. M., et al. (2017). Asymptotic and finite-sample properties of estimators based
on stochastic gradients. Annals of Statistics, 45(4):1694–1727.

Wang, X., Zhao, Y., and Pourpanah, F. (2020). Recent advances in deep learning. International
_Journal of Machine Learning and Cybernetics, 11(4):747–750._

Welling, M. and Teh, Y. W. (2011). Bayesian learning via stochastic gradient langevin dynamics. In
_Proceedings of the 28th international conference on machine learning (ICML-11), pages 681–688._
Citeseer.

Wojtowytsch, S. (2021). Stochastic gradient descent with noise of machine learning type. part ii:
Continuous time analysis. arXiv preprint arXiv:2106.02588.

Wu, J., Hu, W., Xiong, H., Huan, J., Braverman, V., and Zhu, Z. (2020). On the noisy gradient descent
that generalizes as sgd. In International Conference on Machine Learning, pages 10367–10376.
PMLR.

Xie, Z., Sato, I., and Sugiyama, M. (2021). A diffusion theory for deep learning dynamics: Stochastic
gradient descent exponentially favors flat minima. In International Conference on Learning
_Representations._

Xing, C., Arpit, D., Tsirigotis, C., and Bengio, Y. (2018). A walk with sgd. _arXiv preprint_
_arXiv:1802.08770._

Yaida, S. (2019). Fluctuation-dissipation relations for stochastic gradient descent. In International
_Conference on Learning Representations._

Ye, H., Michel, A. N., and Hou, L. (1998). Stability theory for hybrid dynamical systems. IEEE
_transactions on automatic control, 43(4):461–474._

Zhang, C., Liao, Q., Rakhlin, A., Miranda, B., Golowich, N., and Poggio, T. (2018). Theory of deep
learning iib: Optimization properties of sgd. arXiv preprint arXiv:1801.02254.

Zhang, Z. and Liu, Z. (2021). On the distributional properties of adaptive gradients. In Uncertainty
_in Artificial Intelligence, pages 419–429. PMLR._

Zhu, Z., Wu, J., Yu, B., Wu, L., and Ma, J. (2019). The anisotropic noise in stochastic gradient
descent: Its behavior of escaping from sharp minima and regularization effects. In International
_Conference on Machine Learning, pages 7654–7663. PMLR._

Ziyin, L., Li, B., Simon, J. B., and Ueda, M. (2022). SGD can converge to local maxima. In
_International Conference on Learning Representations._


-----

Figure 3: Left: 1d experiments with label noise. The parameters are set to be a 1.5 and λ 1.
**Right: Experiments with L2 regularization with weight decay strength γ. The parameters are set to**
be a 1, λ 0.5, S 1. This is the standard case with a vanishing optimal γ. The vertical lines show = =
where our theory predicts a divergence.
= = =

(a) a 1, S 10 (b) S 50 (c) S 10

Figure 4: Comparison between theoretical predictions and experiments. (a) 1d experiment. We plot = = = =
Σ as an increasing function of λ. We see that the continuous-time approximation fails to predict the
divergence at a learning rate and the prediction in Liu et al. (2021) severely underestimates the model
fluctuation. In contrast, our result is accurate throughout the entire range of learning rates. (b)-(c) 2d
experiments. The straight line shows where the proposed theory predicts a divergence in the variance,
which agrees with experiment exactly. The Hessian has eigenvalues 1 and 0.5, and λ 1.5. For a
large batch size, the discrete-time Hessian approximation is quite accurate; for a small S, the Hessian
approximation underestimates the overall strength of the fluctuation. In contrast, the continuous-time =
result is both inaccurate in shape and in strength.

A EXPERIMENTS

A.1 LABEL NOISE AND REGULARIZATION

Theorem 2 can be verified empirically. We run 1d experiment in Figure 4(a) and high dimensional
experiments in Figures 4(b)-(c), where we choose D 2 for visualization. We see that the continuous
Hessian approximation fails badly for both large and small batch sizes. When the batch size is
large, both the discrete-time Hessian approximation and our solution give a accurate estimate of the =
shape and the spread of the distribution. This suggests that when the batch size is large, discreteness
is the determining factor of the fluctuation. When the batch size is small, the discrete Hessian
approximation severely underestimates the strength of the noise. This reflects the fact that the
isotropic noise enhancement is dominant at a small batch size.

In Figure 3-Left, we run a 1d experiment with λ 1, N 10000 and σ[2] 0.25. Comparing the
predicted Σ, we see that the proposed theory agrees with the experiment across all ranges of S.
The continuous theory with the Hessian approximation fails almost everywhere, while the recently = = =
proposed discrete theory with the Hessian approximation underestimates the fluctuation when S
is small. In Figure 3-Right, we plot a standard case where the optimal regularization strength γ is
vanishing.

Now, we validate the existence of the optimal negative weight decay as predicted by our formula. For
illustration, we plot in Figure 5 the test loss (11) for a 1d example while varying either S or λ. The
orange vertical lines show the place where the theory predicts a divergence in the test loss. We also


-----

Figure 5: 1d experiments with L2 regularization with weight decay strength γ. The parameters are
set to be a 4, λ 1, S 64. This shows a case where the optimal γ is negative. The vertical lines
show where our theory predicts a divergence.
= = =

Figure 6: High-dimensional linear regression. We see that the predicted fluctuation coefficient agrees
with the experiment well. The slight deviation is due to a finite training time and finite N and D. On
the other hand, a naive Hessian approximation results in a qualitatively wrong result.

plot a standard case where the optimal γ is close to 0 in Appendix A. Also, we note that the proposed
theory agrees better with the experiment.

A.2 HIGH-DIMENSIONAL REGRESSION

See Figure 6-Left. We vary N with D 1000 held fixed. We set λ 0.01 and S 32. We see that
the agreement between the theory and experiment is good, even for this modest dimension number D.
The vertical line shows where the over-to-underparametrization transition takes place. As expected, = = =
there is no fluctuation when α 1, and the fluctuation gradually increases as α . On the other
hand, the Hessian approximation gives a wrong picture, predicting fluctuation to rise when there is
no fluctuation and predicting a constant fluctuation just when the fluctuation starts to rise. < →∞


-----

Table 2: Comparison with previous results. For notational conciseness, we compare the case when
all the relevant matrices commute. The model fluctuation Σ, the expected training loss Ltrain
and the expected test loss Ltest calculated by continuous- and discrete-time theories with Hessian
approximation C _H are presented. Exact solutions to these quantities obtained in the present work_
are shown in the rightmost column.
≈

|Col1|Hessian Approximation|Col3|Exact Solution|
|---|---|---|---|
||Cts-time Approximation|D-time Solution|This Work|
||Σ|Σ|Σ|
|Label Noise Input Noise L2 Regularization|2λ ID S 2λ ID S 2λ ID S|Sλ (2ID −λA)−1 Sλ (2ID −λK)−1 Sλ (2ID −λK)−1|λ Sσ 2 (1 + λ Sκ ) [2ID −λ (1 + S1 ) A]−1 λTr[AK S−1BU](1 + λ Sκ ′ ) [2ID −λ (1 + S1 ) K]−1 Eq. (12)|
||Ltrain|Ltrain|Ltrain|
|Label Noise Input Noise L2 Regularization|4λ S Tr[A] + 1 2σ2 4λ S Tr[K] + 1 2Tr[AK−1BU] 4λ S Tr[K] + 1 2Tr[AK−1ΓU]|Eq. (20) Eq. (28) Eq. (37)|σ 22 (1 + λ Sκ ) 1 2Tr[AK−1BU] (1 + Sλ κ′) Eq. (151)|
||Ltest|Ltest|Ltest|
|Label Noise Input Noise L2 Regularization|4λ Tr[A] S 4λ S Tr[A] + 1 2Tr[B′TAB′U] 4λ S Tr[A] + 1 2Tr[AK−2Γ2U]|2λ S Tr[A(2ID −λA)−1 ] Eq. (29) Eq. (38)|λ 2σ S2 κ 2λ Tr[AK−1BU]κ′ 1 2Tr[B′TAB′U] S + Eq. (11)|



B COMPARISON WITH CONVENTIONAL HESSIAN APPROXIMATION


We compare our results for the three cases with the results obtained with the conventional Hessian
approximation of the noise covariance, i.e., C _H, where H is the Hessian of the loss function. We_
summarize the analytical results for a special case in Table 2.
≈

B.1 LABEL NOISE

We first consider discrete-time dynamics with the Hessian approximation. The matrix equation is

ΣA _AΣ_ _λAΣA_ _S [λ]_ _[A.]_ (18)

Compared with the exact result (3), it is a large- + −S limit up to the constant = _σ[2]. This constant factor is_
ignored during the approximation that J **w** EB _l_ _l[T]_ EB _l_ _H_ **w**, which is exact
only when l _xi_ _,_ **w** is a negative log likelihood function of w. Solving the matrix equation yields
( ) ∶= [∇ ∇ ] ≈ [∇∇[T] ] ∶= ( )
({ } ) Σ _[λ]_ (19)

_S_

The training loss and the test loss are = [(][2][I][D][ −] _[λA][)][−][1][.]_

_Ltrain_ _[λ]_ (20)

2S [Tr][[][A][(][2][I][D][ −] _[λA][)][−][1][] +][ 1]2_ _[σ][2][,]_

_Ltest_ = _[λ]_ (21)

2S [Tr][[][A][(][2][I][D][ −] _[λA][)][−][1][]][.]_

On the other hand, by taking the large- = _S limit directly from the exact equation (3), the factor σ[2]_ is
present:

ΣA _AΣ_ _λAΣA_ _S [λ]_ _[σ][2][A.]_ (22)
+ − =

For the continuous-time limit with the Hessian approximation, the matrix equation is

ΣA _AΣ_ _S [λ]_ _[A,]_ (23)

which is the small-λ limit up to the factor σ[2] +. The variance is =

Σ _[λ]_ (24)

2S [I][D][.]

=


-----

The training and the test error are

_Ltrain_ _[λ]_ (25)

4S [Tr][[][A][] +][ 1]2 _[σ][2][,]_

_Ltest_ = _[λ]_ (26)

4S [Tr][[][A][]][.]

Again, taking the small-λ limit directly from the exact result (3) shows the presence of the factor σ[2]

=

on the right hand side of the matrix equation.


B.2 INPUT NOISE

The case with the input noise is similar to the label noise. This can be understood if we replace
_A by K and σ[2]_ by Tr _AK_ [−][1]BU . The model parameter variance resulting from the discrete-time
dynamics under the Hessian approximation is

[ ]

Σ _[λ]_ (27)

_S_

The training and the test error are

= [(][2][I][D][ −] _[λK][)][−][1][.]_

_Ltrain_ _[λ]_ (28)

2S [Tr][[][K][(][2][I][D][ −] _[λK][)][−][1][] +][ 1]2_ [Tr][[][AK] [−][1][BU] []][,]

_Ltest_ = _[λ]_ (29)

2S [Tr][[][A][(][2][I][D][ −] _[λK][)][−][1][] +][ 1]2_ [Tr][[][B][′][T][AB][′][U] []][.]

The large-S limit from the exact matrix equation (144) results in a prefactor Tr _AK_ [−][1]BU in the

=

fluctuation:

[ ]

Σ _[λ]_ (30)

_S_ [Tr][[][AK] [−][1][BU] [](][2][I][D][ −] _[λK][)][−][1][.]_

For the continuous-time limit, we take = _λ_ 0. The Hessian approximation gives

Σ _[λ]_ → (31)

2S [I][D][,]

_Ltrain =_ _[λ]_ (32)

4S [Tr][[][K][] +][ 1]2 [Tr][[][AK] [−][1][BU] []][,]

_Ltest_ = _[λ]_ (33)

4S [Tr][[][A][] +][ 1]2 [Tr][[][B][′][T][AB][′][U] []][.]

The large-S limit again produces a prefactor Tr _AK_ [−][1]BU .

=

B.3 _L2 REGULARIZATION_ [ ]

For learning with regularization, there is a more difference between the Hessian approximation and
the limit taken directly from the exact theory. We first adopt the Hessian approximation for the
discrete-time dynamics. The matrix equation is

ΣK _KΣ_ _λKΣK_ _S [λ]_ _[K,]_ (34)

which is similar to the previous subsection. However, it is different from the large-S limit of the exact

+ − =

matrix equation (154):

ΣK _KΣ_ _λKΣK_ _[λ]_ (35)

_S_

This significant difference suggests that the conventional Fisher-to-Hessian approximation J _H_
fails badly. The fluctuation, the training loss, and the test loss with the Hessian approximation are + − = [(][Tr][[][AK] [−][2][Γ][2][U] []][A][ +][ AK] [−][1][Γ][U] [Γ][K] [−][1][A][)] _[.]_
≈

Σ _[λ]_ (36)

_S_

_Ltrain =_ _[λ]_ (37)

[(][2]2[I][D]S[ −][Tr][λK][[][K][(][)][2][−][I][1][D][,] [ −] _[λK][)][−][1][] +][ 1]2_ [Tr][[][AK] [−][1][Γ][U] []][,]

_Ltest_ = _[λ]_ (38)

2S [Tr][[][A][(][2][I][D][ −] _[λK][)][−][1][] +][ 1]2_ [Tr][[][AK] [−][2][Γ][2][U] []][,]

=


-----

while the large-S limit of the exact theory yields

Σ _[λ]_ (39)

_S_ [Tr][[][AK] [−][2][Γ][2][U] []][AK] [−][1][(][2][I][D][ −] _[λK][)][−][1][ +][ λ]S [A][2][K]_ [−][3][Γ][2][(][2][I][D][ −] _[λK][)][−][1][U,]_

_Ltrain =_ _[λ]_
= 2S[1] [Tr][[][AK] [−][2][Γ][2][U] []][Tr][[][A][(][2][I][D][ −] _[λK][)][−][1][] +][ λ]2S_ [Tr][[][A][2][K] [−][2][Γ][2][(][2][I][D][ −] _[λK][)][−][1][U]_ []] (40)

2 [Tr][[][AK] [−][1][Γ][U] []][,]

_Ltest_ +[λ]
= 2S[1][Tr][[][AK] [−][2][Γ][2][U] []][Tr][[][A][(][2][I][D][ −] _[λK][)][−][1][] +][ λ]2S_ [Tr][[][A][3][K] [−][3][Γ][2][(][2][I][D][ −] _[λK][)][−][1][U]_ []] (41)

2 [Tr][[][AK] [−][2][Γ][2][U] []][.]

+

The continuous-time results are obtained by taking the small-λ limit on Eqs. (36)-(38) for the Hessian
approximation and on Eqs. (39)-(41) for the limiting cases of the exact theory. Specifically, for the
Hessian approximation, we have

Σ _[λ]_ (42)

2S [I][D][,]

_Ltrain =_ _[λ]_ (43)

4S [Tr][[][K][] +][ 1]2 [Tr][[][AK] [−][1][Γ][U] []][,]

_Ltest_ = _[λ]_ (44)

4S [Tr][[][A][] +][ 1]2 [Tr][[][AK] [−][2][Γ][2][U] []][.]

The small-λ limit of the exact theory yields =

Σ _[λ]_ (45)

2S [Tr][[][AK] [−][2][Γ][2][U] []][AK] [−][1][ +][ λ]2S [A][2][K] [−][3][Γ][2][U,]

_Ltrain =_ _[λ]_ (46)

4S [Tr][[][AK] [−][2][Γ][2][U] []][Tr][[][A][] +][ λ]4S [Tr][[][A][2][K] [−][2][Γ][2][U] [] +][ 1]2 [Tr][[][AK] [−][1][Γ][U] []][,]

_Ltest_ = _[λ]_ (47)

4S [Tr][[][AK] [−][2][Γ][2][U] []][Tr][[][A][] +][ λ]4S [Tr][[][A][3][K] [−][3][Γ][2][U] [] +][ 1]2 [Tr][[][AK] [−][2][Γ][2][U] []][.]

=


-----

C PROOF OF THE GENERAL FORMULA

C.1 PROOF OF THEOREM 5 AND COROLLARY 2

We restate the theorem.

**Theorem 7. Let the training loss be LΓ** _L0_ [1]2 **[w][T][Γ][w][ and the models be optimized with SGD in]**

_the neighborhood of a local minimum w[∗]. When Γ_ 0, the noise covariance is given by

= +

_C_ [2][L][0][(][w][∗][)] _H0_ **w[∗]** ≠ (48)

_S_ _S_ [Γ][w][∗][w][∗][T][Γ][ +][ O][(][S][−][2][) +][ O][(∣][w][ −] **[w][∗][∣][2][)][.]**

_When Γ_ 0 and L =0 **w[∗]** 0, ( ) − [1]
= ( ) ≠C [2][L][0][(][w][∗][)] _H0_ **w[∗]** _O_ _S[−][2]_ _O_ **w** **w[∗]** _._ (49)

_S_

_When Γ_ 0 and L0 **w[∗]** = 0, ( ) + ( ) + (∣ − ∣[2])
= _C_ [1] ( ) = (50)

_S_

_Proof. We will use the following shorthand notations: =_ [(][Tr][[][H][0][(][w][∗][)][Σ][]][I][D][ −] _[H][0][(][w][∗][)][Σ][)]_ _[H][0][(] ℓ[w]i[∗][) +] ℓ[ O]f[(][S]w[−][2],x[) +]i_ _[ O],y[(∣]i_ **[w], ℓ[ −][′]i** **[w][∗]∂f[∣][2][)][,][.][ ℓ]i[′′]** _∂f_ [2][ .]

The Hessian of the loss function without regularization H0 **w** _L0_ **w** is given by

∶= ( ( ) ) [∶=][ ∂ℓ][i] [∶=][ ∂][2][ℓ][i]

_N_ _N_

( ) = ∇∇[T] ( )

_H0_ **w** [1] _ℓ[′′]i_ _ℓ[′]i[∇∇][T][f]_ [(][w][,x][i][)][.] (51)

_N_ _i_ 1 _N_ _i_ 1

The last term of Eq. (( 51) =) can be ignored when∑= [∇][f] [(][w][,x][i][)∇] L[f]0[(][w][,x]1, since[i][)][T][ +][ 1] ∑=

1 2 1 2

_N_ _N_ _N_

≪

_N_ _i_ 1 _ℓ[′]i[∇∇][T][f]_ [(][w][,x][i][)∥]F _N[1]_ _i_ 1 _ℓ[′]i[)][2][)]_ / _N[1]_ _i_ 1 _f_ **w,xi** _F_ /

1

∥ [1] ∑= ≤( ∑= ( _N_ ( ∑= ∥∇∇[T] ( 2 )∥[2] [)]

_ℓ[′][2]_ _N[1]_ _i_ 1 _f_ **w,xi** _F_ _,_

1

= ⟨ ⟩[1][/][2] ( ∑= ∥∇∇N [T] ( )∥[2] [)] 2

2L0 **w** _N[1]_ _i_ 1 _f_ **w,xi** _F_ _,_

√

where _F stands for the Frobenius norm=_ [3], and we have defined the variable( )( ∑= ∥∇∇[T] ( )∥[2] [)]ℓ[′][2] _N[1]_ _i_ 1[(][ℓ][′]i[)][2][.]

Since ℓ[′′]i
=

∥⋅∥ _N_ ⟨ ⟩∶= [∑][N]

[=][ 1][ for the mean-square error, we obtain]H0 **w** [1] _f_ **w,xi** _f_ **w,xi** _O_ _L0_ (52)

_N_ _i_ 1

√

near a minimum. The Hessian with regularization( ) = ∑= ∇ ( _H)∇Γ_ **w(** )[T] +LΓ (w is just given by) _H0_ **w** Γ.

On the other hand, the SGD noise covariance C **w** is given by Eq. (2). By assumption 2, the SGD

( ) = ∇∇[T] ( ) ( )+

noise covariance is directly related to the Hessian:
( )

_N_

_C_ **w** _f_ **w,xi** _f_ **w,xi**

_SN_ _i_ 1 _S_

( ) = [⟨][ℓ][′][2][⟩]2 ∑= _N∇_ ( )∇ ( )[T] − [1]

_ℓi_ _L0_ _f_ **w,xi** _f_ **w,x[∇][L]i** [Γ][(][w][)∇][L][Γ][(][w][)][T]

_SN_ _i_ 1

+ ∑= ( − )∇ ( )∇ ( )[T]

[2][L][0][(][w][)] _H0_ **w** (53)

_S_ _S_

This finishes the proof. = ( ) − [1] [∇][L][Γ][(][w][)∇][L][Γ][(][w][)][T][ +][ o][(][L][0][)][.]

3In the linear regression problem, the last term of Eq. ( ◻ 51) does not exist since Tf **w, xi** 0.
∇∇ ( ) =


-----

Now we prove Corollary 2.

_Proof. Near a minimum w[∗]_ of the full loss LΓ **w**, we have

_LΓ_ **w** _H0_ **w[∗]** **w** ( **w)[∗]** Γw[∗] _O_ **w** **w[∗]** _,_ (54)

within the approximation∇ _L(Γ_ **w) =** _LΓ(_ **w)([∗]** −1 2 ) +w **w[∗]** + _H(∣Γ_ **w −[∗]** **w∣[2])** **w[∗]** _O_ **w** **w[∗]** .
Equations (14) and (54) give the SGD noise covariance near a minimum of LΓ **w** .
( ) = ( )+( / )( − )[T] ( )( − )[T] + (∣ − ∣[2])

Now it is worth discussing two different cases separately: (1) with regularization and (2) without

( )

regularization. We first discuss the case when regularization is present. In this case, the regularization
Γ is not small enough, and the SGD noise covariance is not proportional to the Hessian. Near a local
or global minimum w **w[∗], the first term of the right-hand side of Eq. (54) is negligible, and hence**
we obtain
≈

Ew _C_ **w** [2][L][0][(][w][∗][)] _H0_ **w[∗]**

_S_ _S_ [Γ][w][∗][w][∗][T][Γ]

[ ( )] = [2]+[L] E[0]w[(][w] [ [∗]S [1][)][H]H[0]0[(]([w]w[∗][∗][)(]) −[w][ −][1] **[w][∗][)(][w][ −]** **[w][∗][)][T][H][0][(][w][∗][)] +][ O][(∣][w][ −]** **[w][∗][∣][2][)]** (55)

_S_ _S_ [Γ][w][∗][w][∗][T][Γ][ +][ O][(][S][−][2][) +][ O][(∣][w][ −] **[w][∗][∣][2][)][.]**

where we have used the fact that= E(w ) − w[1][∗]. The SGD noise does not vanish even at a global
minimum of LΓ **w** . Note that this also agrees with the exact result derived in Sec. 4.3: together with
an anisotropic noise that is proportional to the Hessian, a rank-[ ] = 1 noise proportional to the strength of
the regularization appears. This rank-1 noise is a signature of regularization.( )

On the other hand, as we will see below, the SGD noise covariance is proportional to the Hessian
near a minimum when there is no regularization, i.e., Γ 0. We have
=

_C_ **w** [2][L][0][(][w][)] _H0_ **w** (56)

_S_ _S [H][0][(][w][∗][)(][w][ −]_ **[w][∗][)(][w][ −]** **[w][∗][)][T][H][0][(][w][∗][) +][ O][(∣][w][ −]** **[w][∗][∣][2][)][.]**

For this case, we need to differentiate between a local minimum and a global minimum. When( ) = ( ) − [1]
_L0_ **w[∗]** is not small enough (e.g. at a local but not global minimum),
( )

_C_ **w** [2][L][0][(][w][∗][)] _H0_ **w** _H0_ **w**

_S_ _S_

( ) = ( ) + [(][w][ −] **[w][∗][)][T][H][0][(][w][∗][)(][w][ −]** **[w][∗][)]** ( )

− _S [1]_ _[H][0][(][w][∗][)(][w][ −]_ **[w][∗][)(][w][ −]** **[w][∗][)][T][H][0][(][w][∗][) +][ O][(∣][w][ −]** **[w][∗][∣][2][)]**

[2][L][0][(][w][∗][)] _H0_ **w** _O_ _S[−][2]_ _O_ **w** **w[∗]**

_S_

= ( ) + ( ) + (∣ − ∣[2])

[2][L][0][(][w][∗][)] _H0_ **w[∗]** _O_ _S[−][2]_ _O_ **w** **w[∗]** _,_ (57)

_S_

and so, to leading order,= ( ) + ( ) + (∣ − ∣[2])

_C_ [2][L][0][(][w][∗][)] _H0_ **w[∗]** _,_ (58)

_S_

which is proportional to the Hessian but also proportional to the achievable approximation error. = ( )

On the other hand, when L0 **w[∗]** is vanishingly small (e.g. at a global minimum), we have 2L0 **w**
**w** **w[∗]** _H0_ **w[∗]** **w** **w[∗]**, and thus obtain
( ) ( ) ≈
( _C −_ **w** )[T] [1] ( )( − )

_S_

( ) = _O[[(][w]S[ −][−][2][w][∗][)] O[T][H]w[0][(][w]w[∗][)(][∗]_ **[w][ −],** **[w][∗][)][H][0][(][w][∗][) −]** _[H][0][(][w][∗][)(][w][ −]_ **[w][∗][)(][w][ −]** **[w][∗][)][T][H][0][(][w][∗][)]](59)**

i.e., + ( ) + (∣ − ∣[2])

E _C_ [1] (60)

_S_

This completes the proof.[ ] = [(][Tr][[][H][0][Σ][]][I][D][ −] _[H][0][Σ][)]_ _[H][0][ +][ O][(][S][−][2][) +][ O][(∣][w][ −]_ **[w][∗][∣][2][)][.]**


-----

**Remark. It should be noted that the second term on the right-hand side of Eq. (59) would typically be**
_much smaller than the first term for large D. For example, when H0_ **w[∗]** _aID with a_ 0, the first
_and the second terms are respectively given by_ _a[2]_ _S_ **w** **w[∗]** _ID and_ _a[2]_ _S_ **w** **w[∗]** **w** **w[∗]** _._
_The Frobenius norm of the former is given by_ _Da[2]_ _S_ **w** **w[∗]** _, while that of the latter is given(_ ) = >
_by_ _a[2]_ _S_ **w** **w[∗]** _, which indicates that in Eq. ( (_ / )∥59), the first term is dominant over the second− ∥[2] −( / )( − )( − )[T]
_term for large D. Therefore the second term of Eq. ( (_ _59/_ _) can be dropped for large)∥_ − ∥[2] _D, and Eq. (59) is_
_simplified as (_ / )∥ − ∥[2]

_C_ **w** _S_ _H0_ **w[∗]** ; (61)

⎧⎪⎪E (C ) ≈ [(][w]S[−][w][∗][)]H[T][H]0[0].[(][w][∗][)(][w][−][w][∗][)] ( )

_Again, the SGD noise covariance is proportional to the Hessian.⎨_

⎪⎪ [ ] ≈ [Tr][[][H][0][Σ][]]
⎩

In conclusion, as long as the regularization is small enough, that the SGD noise covariance near
a minimum is proportional to the Hessian is a good approximation. This implies that the noise is
multiplicative, which is known to lead to a heavy tail distribution (Clauset et al., 2009; Levy and
Solomon, 1996). Thus, we have studied the nature of the minibatch SGD noise in three different
situations. As an example, we have demonstrated the power of this general formulation by applying
it to the high-dimensional linear regression problem in Sec. 6.1.

C.2 PROOF OF COROLLARY 3

_Proof. We prove the case where Γ_ 0 and L **w[∗]** 0 as an example. Substituting Theorem 5 into
Theorem 1yields
=1 ( ) ≠ 2L0

2ID (62)

1 _µ_ [Λ][H][0][]] [Λ][H][0][Σ][ =] _S_ 1 _µ_

where we have assumed necessary commutation relations. Suppose that the Hessian[ − _H0 is of rank-r_
with r _D. The singular-value decomposition and its Moore-Penrose pseudo inverse are given by +_ ( − ) [Λ][2][H][0][,]
_H0_ _USV_ [T] and H0[+]
matrix with elements being singular values of ≤ _H0, and S[+]_ is obtained by inverting every non-zero
entry of = _S. Multiplying[=] H[ V S]0[+]_ [to both sides of the above equation, we have][+][U][ T][, respectively, where][ U][ and][ V][ are unitary,][ S][ is a rank-][r][ diagonal]

_PrΣ_ 2L0 Λ −1 _,_ (63)

where Pr diag 1, 1,..., 1, 0,..., = _S0_ is the projection operator with1 _µ_ 1 _µ_ _[H][0][)]_ _r non-zero entries. When the_

( − ) _[P][r][Λ]_ [(][2][I][D][ −] +

Hessian is full-rank, i.e., r _D, the Moore-Penrose pseudo inverse is nothing but the usual inverse._
The other cases can be calculated similarly. = ( )
=


-----

D APPLICATIONS

D.1 INFINITE-DIMENSIONAL LIMIT OF THE LINEAR REGRESSION PROBLEM

Now we apply the general theory in Sec. 5 to linear regressions in the high-dimensional limit, namely
_N,D_ with α _N_ _D held fixed._

D.1.1 →∞PROOF OF ∶= PROPOSITION/ 4


The loss function

_N_

1 2
_L_ **w** **w[T]xi** _yi_ (64)

2N _i_ 1

with yi **u[T]** _ϵi can be written as_ ( ) = ∑= ( − )

_N_

T

= +L **w** [1] _A[+]v_ ˆA **w** **u** _A[+]v_ _A[+]v_ [1] _ϵ[2]i_ _[,]_ (65)

2 2 **[v][T][ ˆ]** 2N _i_ 1

( ) = ) ( − − [ˆ] ) − [1] + ∑=

where _A[ˆ]_ _N[1]_ _i_ 1 _[x][i][x]i[T][(][is an empirical covariance for the training data and][w][ −]_ **[u][ −]** [ˆ] **[ v][ ∶=][ 1]N** _i_ 1 _[x][i][ϵ][i][. The]_

symbol denotes the Moore-Penrose pseudoinverse. We also introduce the the averaged traing

= =

loss: Ltrain ∶= E[∑]w[N] _L_ **w** [∑][N]
(⋅)[+]

The minimum of the loss function is given by

∶= [ ( )]

**w[∗]** **u** _A[ˆ][+]v_ Πr, (66)

where r R[D] is an arbitrary vector and= Π is the projection onto the null space of + + _A[ˆ]. Since_
1 Π _A[ˆ][+][ ˆ]A, w[∗]_ is also expressed as
∈
− = **w[∗]** _A[ˆ][+]_ _A[ˆ]u_ **v** Πr. (67)

In an underparameterized regime α 1, Π 0 almost surely holds as long as the minimum eigenvalue

= ( + ) +

of A (not _A[ˆ]) is positive (Hastie et al., 2019). In this case,_ _A[ˆ][+]_ _A[ˆ][−][1]_ and we obtain
> =

**w[∗]** **u** _A[ˆ][−][1]v_ for α 1=. (68)

On the other hand, in an overparameterized regime α 1, Π 0 and there are infinitely many global

= + >

minima. In the ridgeless regression, we consider the global minimum that has the minimum norm
**w[∗]**, which corresponds to > ≠
∥ ∥ **w[∗]** _A[ˆ][+]_ _A[ˆ]u_ **v** 1 Π **u** _A[ˆ][+]v_ for ridgeless regression with α 1. (69)

In both cases, the loss function is expressed as

= ( + ) = ( − ) + <

_N_

_L_ **w** [1] _A_ **w** **w[∗]** _Av_ [1] _ϵ[2]i_ _[.]_ (70)

2 2 **[v][T][ ˆ]** 2N _i_ 1

( ) = ( − ) − [1] + ∑=

Asymptotically, wt converges to a stationary point[(][w][ −] **[w][∗][)][T][ ˆ]** **w[∗]** with fluctuation Σ obeying the following
equation (Theorem 1:
_λA[ˆ]Σ_ _λΣ A[ˆ]_ _λ[2][ ˆ]AΣ A[ˆ]_ _λ[2]C._ (71)

The SGD noise covariance C is given by Eq. ( + 14 −). In the present case, the Hessian is given by = _H_ _A[ˆ]_
and we also have

_N_ _N_ _N_ =

1 2

_ℓ[′]i[)][2][ =][ 1]_ **w[T]xi** _yi_ 2 _ℓi_ 2L **w** _._ (72)

_N_ _i_ 1 _N_ _i_ 1 _N_ _i_ 1

∑= ( ∑= ( − ) = ∑= = ( )

On the other hand, _L_ **w** _L_ **w** _A[ˆ]_ **w** **w[∗]** **w** **w[∗]** _A, and hence Ew_ _L_ **w** _L_ **w**
_AˆΣ A[ˆ]. Therefore we obtain_
∇ ( )∇ ( )[T] = ( − )( − )[T][ ˆ] [∇ ( )∇ ( )[T]] =

_C_ Ew _C_ **w** [2][L][train] _Aˆ_ _AˆΣ A.[ˆ]_ (73)

_S_ _S_

= [ ( )] = − [1]


-----

Now, we find Ltrain. First, we define X R[N] [×][D] as Xik _xi_ _k, and_ _ϵ_ R[N] as _ϵi_ _ϵi. Then_
**w[∗]** 1 Π **u** _A[ˆ][+]v_ 1 Π **u** _X_ [T]X _X_ [T]ϵ.
∈ = ( ) ⃗ ∈ ⃗ =

With this notation, we have _A[ˆ]_ _X_ [T]X _N_, and the loss function is expressed as

= ( − ) + = ( − ) + ( )[+] ⃗

_N_

_L_ _w_ [1] = _A_ **w/** **w[∗]** _ϵ[T]X_ _X_ [T]X _X_ [T]ϵ [1] _ϵ[2]i_ _[.]_ (74)

2 [(][w][ −] **[w][∗][)][T][ ˆ]** 2N 2N _i_ 1

We therefore obtain( ) = ( − ) − [1] ( )[+] ⃗ + ∑=

[⃗]

_Ltrain_ [1] _AΣ_ _ϵ[T]X_ _X_ [T]X _X_ [T]ϵ _[σ][2]_ (75)

2 [Tr][[][ ˆ] 2N [E][[⃗] 2 _[.]_

Here, = ] − [1] ( )[+] ⃗] +
E _ϵ[T]X_ _X_ [T]X _X_ [T]ϵ _σ[2]Tr_ _X_ [T]X _X_ [T]X _σ[2]Tr_ 1 Π _._ (76)
We can prove that the following identity is almost surely satisfied (Hastie et al., 2019) as long as the

[⃗ ( )[+] ⃗] = [( )( )[+]] = ( − )
smallest eigenvalue of A (not _A[ˆ]) is positive:_

Tr 1 Π min _D,N_ _._ (77)

We therefore obtain

( − ) = { }

1
_AΣ_ [1] for α 1,
2 [Tr][[][ ˆ] 2 _α_ [)] _[σ][2]_

_Ltrain_ [1] _AΣ_ ⎧ (78)
= 2 [Tr][[][ ˆ] ] − 2[σ]N[2] [min][{][D,N] [} +][ σ]2[2] ⎪⎪⎪⎪⎪⎨ 12 [Tr][[]A[ ˆ]Σ] + [(][1][ −] [1] for α > 1

By substituting Eq. (78) into Eq. (73), we obtain the following SGD noise covariance:[=] ⎪⎪⎪⎪⎪ ] ≤

⎩

1

_AΣ_ _AΣ_ _A[ˆ]_ _[σ][2]_ _A_ for α 1,
_S_ _S_ _α_ [)][ ˆ]

_C_ ⎧ (79)
= ⎪⎪⎪⎪⎪⎨ _S1_ [(][Tr][[]A[ ˆ]Σ] − _A[ˆ]Σ)_ _A[ˆ] +_ [(][1][ −] [1] for α > 1.

This finishes the proof. ⎪⎪⎪⎪⎪ ] − [ˆ] ) ≤

⎩ [(][Tr][[][ ˆ]

D.1.2 PROOF OF THEOREM ◻ 6

_Proof. We have to solve this equation:_

_AˆΣ_ Σ A[ˆ] _λA[ˆ]Σ A[ˆ]_ _λC,_ (80)

where C is given in Proposition 4. Using the similar trick of multiplying by + − = _G[ˆ]_ 2ID _λ_ 1 _S_ _A_

as in Appendix E.2.2, one obtains

_λσ[2]_ ∶= − ( − [1] [)][ ˆ]

_S_ _α_ [)][ ˆ]κ for α 1;

Tr _A[ˆ]Σ_ (81)

0 for α 1,

where ˆκ 1 TrS [Tr]G[ˆ][[][−]G[ ˆ][1][ ˆ]A[−][1][ ˆ]A [with][ ˆ]G [ 2ID] = {λ 1 [(][1]S[ −] _A[1]_ . > ≤

[ ]

Substituting the above trace into the matrix equation, we have ∶= − _[λ]_ ] ∶= − ( − [1] [)][ ˆ]

Σ _λσS_ [2] _α_ [)(][1][ +][ λ]S _κ[ˆ]_ _G[ˆ][−][1]_ for α 1; (82)

0 for α 1.

= { [(][1][ −] [1] ) >

≤

D.2 SECOND-ORDER METHODS


**Proposition 5. Suppose that we run DNM with Λ** _λA[−][1]_ _with random noise in the label. The model_
_fluctuation is_

_λσ ∶=[2]_
Σ (83)

_gS_ _λD_ _[A][−][1][,]_

_where g_ 2 1 _µ_ 1[1][−]µ[µ] _S_ = −

+

∶= ( − ) −( [+][ 1] [)] _[λ][.]_


-----

_Proof. Substituting Λ_ _λA[−][1]_ into Eqs. (3) and (5) yields
= _gΣ_ _[λ]_ (84)

_S_

where g 2 1 _µ_ 1[1][−]µ[µ] _S_ = [(][Tr][[][A][Σ][] +][ σ][2][)] _[A][−][1][,]_
∶== ( − ) −( + [+][ 1] [)] _[λ][. Multiplying]Tr_ _AΣ_ _[ A]λDσ[ and taking trace on both sides, we have][2]_ (85)

_gS_ _λD_ _[.]_

Therefore, the model fluctuation is [ ] =

−

_λσ[2]_
Σ (86)

_gS_ _λD_ _[A][−][1][.]_

=

−

**Proposition 6. Suppose that we run NGD with Λ** _S[λ]_ _[J][(][w][)][−][1][ ≈]_ _S[λ]_ _[C]_ [−][1][ with random noise in the]

_label. The model fluctuation is_

∶=

2[⎤]

_λ_ _σ[2]_ 2 1 _σ[2]_

Σ ¿λ2g2 4λ _g_ _A[−][1],_ (87)

⎡ 4 _[g][ −]_ [1]2 1 _D_ 4 1 _D_ 1 _µ_ [)] 1 _D_ 1 _D_ [)]
⎢ Á ⎥
⎢ ÁÀ ⎥

= ⎢ + ( − ⎥

_where g_ ⎢⎢⎣ 1 1D 1 1µ +1 1µ[+]S1[ 1][.] + + + [+][ 4] [(][ σ] +[2] ⎥⎥⎦

+ + −

∶=

_Proof. Similarly to the previous case, the matrix equation satisfied by[+]_ Σ is

_λ_ _µ_ _λ_

1 _µ_ _C_ [−][1]AΣ ΣAC [−][1]

1 _µ[2]_ _S [C]_ [−][1][A][Σ][AC] [−][1][ +] 1 _µ[2]_ _S_ _S [C]_ [−][1][.]

(88)

( − )( + ) − [1][ +][ µ][2]

− − [(][C] [−][1][AC] [−][1][A][Σ][ +][ Σ][AC] [−][1][AC] [−][1][) =][ λ]

Although it is not obvious how to directly solve this equation, it is possible to guess one solution
according to the hope that Σ be proportional to J [−][1], in turn, A[−][1] (Amari, 1998; Liu et al., 2021).
We assume that Σ _xA[−][1]_ and substitute it into the above equation to solve for x. This yields one
solution without claiming its uniqueness. By simple algebra, this x is solved to be
=

_σ[2]_ 2 1 _σ[2]_ 2

_x_ _[λ]_ ¿λ2g2 4λ _g_ _._ (89)

4 _[g][ −]_ [1]2 1 _D_ 4 1 _D_ 1 _µ_ [)] 1 _D_ 1 _D_ [)]

Á
ÁÀ

Let σ 0. We obtain the result in Sec. = 6.4 +. ( −

+ [+][ 1] + + + [+][ 4] [(][ σ] +[2]

D.3 =ESTIMATION OF TAIL INDEX

In Mori et al. (2021); Meng et al. (2020), it is shown that the (1d) discrete-time SGD results in a
distribution that is similar to a Student’s t-distribution:

_p_ _w_ _σ[2]_ _aw[2]_ 2, (90)

where σ[2] is the degree of noise in the label, and a is the local curvature of the minimum. For large w,

( ) ∼( + )[−] [1][+][β]

this distribution is a power-law distribution with tail index:

_p_ _w_ _w_ _,_ (91)

and it is not hard to check that β also equal to the smallest moment of(∣ ∣) ∼∣ ∣[−(][1][+][β][)] _w that diverges: E_ _w[β]_ .
Therefore, estimating β can be of great use both empirically and theoretically.

[ ] = ∞

In continuous-time, it is found that βcts [2]aλ[S]

hypothesize that the discrete-time nature causes a change in the tail index β _βcts_ _ϵ, and we are_
interested in finding ϵ. We propose a “semi-continuous" approximation to give the formula to estimate = [+][ 1][ (][Mori et al.][,][ 2021][). For discrete-time SGD, we]
the tail index. Notice that Theorem 2 gives the variance of the discrete-time SGD, while Eq. = + (90)
can be integrated to give another value of the variance, and the two expressions must be equal for
consistency. This gives us an equation that β must satisfy:

(92)
∫ _[p][(][w][;]_ _[β][)(][w][ −]_ [E][[][w][])][2][ =][ Var][[][w][]][,]


-----

Figure 7: Tail index β of the stationary distribution of SGD in a 1d linear regression problem. Left to
**Right: aλ** 0.2, 1.0, 1.8.
=

this procedure gives the following formula:

_β_ _λ,S_ [2][S] (93)

_aλ_

and one immediately recognizes that ( _S_ ) = 1 is the discrete-time contribution to the tail index. See

[−] _[S][ =][ β][cts][ +][ ϵ,]_

Figure 7 for additional experiments. We see that the proposed formula agrees with the experimentally
measured value of the tail index for all ranges of the learning rate, while the result of −( + ) Mori et al.
(2021) is only correct when λ 0[+]. Hodgkinson and Mahoney (2020) also studies the tail exponent
of discrete-time SGD; however, their conclusion is only that the “index decreases with the learning
rate and increases with the batch size". In contrast, our result give the functional form of the tail index →
directly. In fact, this is the first work that gives any functional form for the tail index of discrete-time
SGD fluctuation to the best of our knowledge.

The following proposition gives the intermediate steps in the calculation.

**Proposition 7.** _Tail index estimation for discrete-time SGD_ _Let the parameter distribution be_

_p_ _w_ _σ[2]_ _aw[2]_ 2, and Var _w_ _be given by Theorem 2. Then_
( ) ∼( + ( )− [1][+][β] [ ] )

_β_ _λ,S_ [2][S] (94)

_aλ_

( ) =

_Proof. The normalization factor for the distribution exists if[−]_ _[S.]_ _β_ 0:

_a_ _σ[β]Γ_ [1][+]2[β] _._ > (95)
√ _π_ Γ _[β]2_

( [)]

N =

If β 2, the variance exists and the value is

( [)]

_σ[2]_

> Var _w_ (96)

_a_ _β_ 2

By equating Eq. (96) with the exact variance[ (] =6), we are able to solve for an expression of the tail

( − ) _[.]_

index as
_β_ _λ,S_ [2][S] (97)

_aλ_

( ) = [−] _[S.]_


-----

E PROOFS AND ADDITIONAL THEORETICAL CONSIDERATIONS

E.1 PROOF OF PROPOSITION 1

The with-replacement sampling is defined in Definition 2. Let us here define the without-replacement
sampling.
**Definition 3. A minibatch SGD without replacement computes the update to the parameter w with**
the following set of equations:

**gt** _S[1]_ _t_ (98)

**wt** **wt** 1 _λgˆt,_

where S _Bt_ _N is the minibatch size, and the set{[ˆ]_ = [∑]−[i][∈][B] [∇][ℓ][(][x][i][,y] B[i]t[,] is an element uniformly-randomly drawn[w][t][−][1][)][;]

= −

from the set of all S-size subsets of 1,...,N .
∶= ∣ ∣≤

From the definition of the update rule for sampling with or without replacement, the covariance { }
matrix of the SGD noise can be exactly derived.
**Proposition 8. The covariance matrices of noise in SGD due to minibatch sampling as defined in**
_Definitions 2 and 3 with an arbitrary N are_

_C_ **w** _SS1_ _NNNS1_ _i=N1_ _i_ 1 _i_ _i_ _with replacementwithout replacement_ (99)

_where the shorthand notation(_ ) = { ([[][ 1]−− [∑]) [[][N][ 1] [∇][∑] ℓ[ℓ][N][i]=i[∇]w[ℓ][∇][T][ℓ][i][−∇][∇] l[ℓ][T][L]x[(][−∇]i[w],y[)∇]i[L], **w[(][L][w][(][)∇] is used.[w][)][L][T][(][]][w][,]** [)][T][]] _[,]_ (( ) )

In the limit of S 1 or N _S, two cases coincide. In the(_ ) ∶= ( ) _N_ _S limit, both methods of sampling_
have the same noise covariance as stated in Proposition 1:
= ≫ 1 _N_ ≫

_C_ **w** _SN_ _i_ 1 _ℓi_ _ℓ[T]i_ _S_ (100)

**Remark. We also note that a different way of defining minibatch noise exists in(** ) = ∑= ∇ ∇ [−] [1] _Hoffer et al. (2017)._

[∇][L][(][w][)∇][L][(][w][)][T][.]

_The difference is that our definition requires the size of each minibatch to be exactly S, while Hoffer_
_et al. (2017) treats the batch size also as a random variable and is only expected to be S. In_
_comparison, our definition agrees better with the common practice._

Now we prove Proposition 8.

_Proof. We derive the noise covariance matrices for sampling with and without replacement. We first_
derive the case with replacement. According to the definition, the stochastic gradient for sampling
with replacement can be rewritten as


_N_

**gˆ** [1] **gnsn,** (101)

_S_ _n_ 1

where gn _ℓn and_ = ∑=

_sn_ _l, if l_ multiple n[′]s are sampled in S, with 0 _l_ _S._ (102)

∶= ∇

The probability of sn assuming value l is given by the multinomial distribution

= − ≤ ≤

_l_ _S_ _l_

_P_ _sn_ _l_ 1 _._ (103)

−

_l_ _N_ _N_

Therefore, the expectation value of( _s =n is given by) = ([S][)(][ 1]_ [)] ( − [1] [)]

_S_
EB _sn_ _l_ 0 _lP_ _sn_ _l_ _N [S]_ _[,]_ (104)

which gives [ ] = ∑= ( = ) =


EB **gˆ** **g** [1]

_N_

[ ] = ∶=


_N_
**gn** _L_ **w** _._ (105)
_n_ 1
∑= = ∇ ( )


-----

For the covariance, we first calculate the covariance betweencovariance of multinomial distribution, we have for n _n[′]_ _sn and sn′_ . Due to the properties of the

EB _snsn_ cov _sn,sn_ E _sn_
′ ≠ ′

[ ] = [ ] + [ ][2]

_N_ [2][ +][ S]N[2][2]

= − _[S]_

_[S][(][S][ −]_ [1][)] ; (106)

_N_ [2]

and for n _n[′]_ =

EB _snsn_ Var _sn_ E _sn_

=

_N_ 1

[ ] = _[S]_ [ ] + [[S][2] ][2]

_N_ _N_ _N_ [2]
−

= +

_[SN][ +][ S][(][S][ −]_ [1][)] _._ (107)

_N_ [2]

Substituting these results into the definition of the noise covariance yields=

_C_ **w** EB **gˆgˆ[T]** EB **gˆ** EB **gˆ**

_N_ _N_

( ) = [1] [ ] −gng[n[T][′]][E][B][[][[s][n]][s][T][n][′][] −] **[gg][T]**

_S[2]_ _n_ 1 _n[′]_ 1

= ∑=N ∑= _N_

_S[1][2]_ _n,n[′]_ 1 **gngn[T][′][ S][(][S]N[ −][2]** [1][)] _S[1][2]_ _n_ 1 **gngn[T]** _N_ [2] _N_ [2] **gg[T]**

= 1 ∑N= + ∑= [[] _[SN][ +][ S][(][S][ −]_ [1][)] − _[S][(][S][ −]_ [1][)] ] −

_NS_ _n_ 1 **gngn[T]** _S_ **[gg][T]**

= ∑= _N_ [−] [1]

_S[1]_ _N_ _i_ 1 _ℓi_ _ℓ[T]i_ (108)

= ∑= ∇ ∇ [−∇][L][(][w][)∇][L][(][w][)][T][]] _[.]_

Then, we derive the noise covariance for sampling without replacement. Similarly, according to the[[][ 1]
definition, the stochastic gradient for sampling without replacement can be rewritten as

_N_

**gˆ** [1] **gnsn,** (109)

_S_ _n_ 1

where = ∑=

_sn_ 1, if n _S._ (110)

The probability of n that is sampled in S from = {[0] N[,] [if] is given by[ n][ ∉] _[S][;]_

∈

_S_ 1[)]
_P_ _sn_ 1 _[S]_ (111)

_N [.]_

The expectation value of sn is then given by( = ) = ([N]S−[−][)][1] =

([N]

EB _sn_ _P_ _sn_ 1 _N [S]_ _[,]_ (112)

which gives [ ] = ( = ) =

_N_

EB **gˆ** **g** [1] **gn** _L_ **w** _._ (113)

_N_ _n_ 1

For the covariance, we first calculate the covariance betweenn _n[′]_ [ ] = ∶= ∑= = ∇ _s(n and)_ _sn′. By definition, we have for_

EB _snsn_ _P_ _sn_ 1,s[′]n _n_ _n_

≠ ′

[ ] = _S(_ 2[)] = _S_ 1[)] [=][ 1][) =][S][(][S][ P][ −][(][s][1][n][)] [=][ 1][∣][s][′] [=][ 1][)][P] [(][s][′] [=][ 1][)] (114)

_N_ _N_ 1

= ([N]S−[−]1[2][)] ([N]S−[−][)][1] =

([N]−[−][1] ([N] ( − ) [;]


-----

and for n _n[′]_
= EB _snsn_ _P_ _sn_ _l_ _N [S]_ _[.]_ (115)

Substituting these results into the definition of the noise covariance yields

[ ] = ( = ) =

_C_ **w** EB **gˆgˆ[T]** EB **gˆ** EB **gˆ**

_N_ _N_

( ) = [1] [ ] −gng[n[T][′]][E][B][[][[s][n]][s][T][n][′][] −] **[gg][T]**

_S[2]_ _n_ 1 _n[′]_ 1

= ∑=N ∑= _N_

_S[1][2]_ _n,n[′]_ 1 **gngn[T][′][ S]N** [(]N[S][ −] [1]1[)] _S[2]_ _n_ 1 **gngn[T]** _N_ _N_ _N_ 1

= 1 _N∑=_ _S_ _N_ _N_ _S_ ∑= [[][ S]

_NS_ _N_ 1 _n_ 1 **gng(n[T]** −S) N[+][ 1]1 [−] _[S][(]([S][ −] −[1][)])_ [] −] **[gg][T]**
− −

= _N_ _S_ ∑= _N_ [−]

_S_ _N_ −1 _N_ _i_ 1 _ℓi_ _ℓ[T]i(_ − ) **[gg][T]** (116)

−
= ( − ) [[][ 1] ∑= ∇ ∇ [−∇][L][(][w][)∇][L][(][w][)][T][]] _[.]_


E.2 PROOFS IN SEC. 4.2

E.2.1 PROOF OF LEMMA 1

_Proof. From the definition of noise covariance (2), the covariance matrix for the noise in the label is_

1 _N_
_C_ **w** _li_ **wt** 1 _li_ **wt** 1

_NS_ _i_ 1 _S_

− −

( ) = 1 ∑=N ∇ ( )∇ ( )[T] − [1] _N_ 1 _N_

_S[1]_ _N_ _i_ **w[T]xi** _ϵi_ _xix[T]i_ _i_ [∇]i[)][L][T][(][ −][w][t]S[1][−][1][)∇]N[L][(]i[w]w[t][−][1][T][)]x[T]i _ϵi_ _xi_ ⎡ _N_ _j_ _x[T]j_ _j_ _j[)][T][⎤]_

⎢ ⎥

= [1] 1 ∑N (w[T]xi −xix[T]i)[x]i[T][w][ +][(][w][ ϵ]i[2][T][x][x]i[x][−][T]i _[ϵ]_ [[][ 1]N ∑w[T](xixi − 1) _N]_ ⎢⎢⎣x[T]i _[x]∑i[T][w][)]_ [(][w][T][x] [−] _[ϵ]_ (117)⎥⎥⎦

_S_ _N_ _i_ _S_ _N_ _i_ ⎡ _N_ _j_ ⎤

⎢ ⎥

= ∑( [) −] [1] ∑( )] ⎢ ∑( ⎥

[1] [[][ 1] ⎢⎣ ⎥⎦ (118)

_S_

Gaussian random variables in the third line is evaluated as follows.where we have invoked the law of large numbers and the expectation value of the product of four= [(][A][ww][T][A][ +][ Tr][[][A][ww][T][]][A][ +][ σ][2][A][)][,]

Because N is large, we invoke the law of large numbers to obtain the _j,k_ -th component of the
matrix as

1 _N_ _D_ ( ) _D_
lim **w[T]xixix[T]i** _[x]i[T][w][)][jk]_ _wixixjxk_ (119)
_N_ _N_ _i_ 1 _i_ _i[′][ x][i][′][w][i][′][]]_ _[.]_

Because the average is taken with respect to→∞ ∑= ( [=][ E][B][[][w] x[T] and each[xxx][T][x][T] x[w] is a Gaussian random variable, we apply the[]][jk] [=][ E][B] [[]∑ ∑
expression for the product of four Gaussian random variables E _x1x2x3x4_ E _x1x2_ E _x3x4_
E _x1x3_ E _x2x4_ E _x1x4_ E _x2x3_ 2E _x1_ E _x2_ E _x3_ E _x4_ (Janssen and Stoica, 1988) to obtain

_D_ _D_ [ ] = [ ] [ ] +

[ ] [ EB ]+ _w[_ _ixixj]xk[_ ]− [ ] [ ] [ ] [ ]

_i_ _i[′][ x][i][′][w][i][′][]]_

_D_ _D_ _D_ _D_

[∑ ∑

EB _wixixj_ EB _xk_ _wixixk_ EB _xj_
_i_ _i[′][ x][i][′][w][i][′][] +][ E][B][ []_ _i_ _i[′][ x][i][′][w][i][′][]]_
= [∑ _D_ ]D [ ∑ ∑ ] [ ∑

EB _wixi_

2+ _Aww [∑i[T]A_ _jk_ ∑i[′] Tr[ x][i][′]A[w]ww[i][′][]] [E][T][B][ []A[x]jk[j][x].[k][]] (120)

Writing Σ Ew **ww[T]**, we obtain

= ( ) + [ ]

∶= [ ] Ew _C_ **w** _C_ [1] (121)

_S_

[ ( )] =∶ = [(][A][Σ][A][ +][ Tr][[][A][Σ][]][A][ +][ σ][2][A][)][.]


-----

This method has been utilized repeatedly in this work.

E.2.2 PROOF OF THEOREM 2

_Proof. We substitute Eq. (5) into Eq. (3) which is a general solution obtained in a recent work (Liu_
et al., 2021):

_µ_

1 _µ_ ΛAΣ ΣAΛ (122)

1 _µ[2][ Λ][A][Σ][A][Λ][ +]_ 1 _µ[2][ (][Λ][A][Λ][A][Σ][ +][ Σ][A][Λ][A][Λ][) =][ Λ][C][Λ][.]_

To solve it, we assume the commutation relation that( − )( + ) − [1][ +][ µ][2] Λ,A ΛA _AΛ_ 0. Therefore, the above

− −

equation can be alternatively rewritten as
[ ] ∶= − =

1 _µ_ _ID_

2 1 _µ_ _S_ 2 1 _µ_ _S_

[( − ) − [1] [(] [1][ −] + _[µ]_ [+][ 1] [)] [Λ][A][]] [Σ][A][Λ][ +][ Λ][A][Σ] [[(][1][ −] _[µ][)][I][D][ −]_ [1] [(] [1][ −] + _[µ]_ [+][ 1] [)] [Λ][A][]] (123)

_S_ [Tr][[][A][Σ][]][Λ][A][ =][ 1]S [σ][2][Λ][A.]

− [1]

To solve this equation, we first need to solve for Tr _AΣ_ . Multiplying Eq. (123) by G[−]µ[1]

1

2 1 _µ_ _ID_ 1[1][−]µ[µ] _S_ − and taking trace, we obtain[ ] ∶=

+

[ ( − ) −( [+][ 1]Tr[)]A[Λ]Σ[A][]] _S_ [Tr][[][A][Σ][]][Tr][[][Λ][AG]µ[−][1] _S [σ][2][Tr][[][Λ][AG]µ[−][1]_ (124)

which solves to give [ ] − [1] [] =][ 1] []][,]

Tr ΛAG[−]µ[1]

Tr _AΣ_ _[σ][2]_ (125)

_S_ 1 _S_ [Tr][[][Λ][AG]µ[−][1] _S [κ][µ][.]_

[ []]

Therefore, Σ is [ ] =

− [1] [] ∶=][ σ][2] 1

Σ _[σ][2]_ _._ (126)

−

_S_ _S_ 1 _µ_ _S_

= [(][1][ +][ κ] [)] [Λ] [[][2][(][1][ −] _[µ][)][I][D][ −(]_ [1][ −] + _[µ]_ [+][ 1] [)] [Λ][A][]]


E.2.3 TRAINING ERROR AND TEST ERROR FOR LABEL NOISE

In the following theorem, we calculate the expected training and test loss for random noise in the
label.
**Theorem 8.** _Approximation error and test loss for SGD noise in the label_ _The expected approxi-_
_mation error, or the training loss, is defined as Ltrain_ Ew _L_ **w** _; the expected test loss is defined_
_as Ltest_ ([1]2 [E][w][E][B][ [(][w][T][x][)][2][]][. For SGD with noise in the label given by Eq.]) [ (][5][)][, the expected]

_approximation error and test loss are_ ∶= [ ( )]

∶=

_Ltrain_ _[σ][2]_ (127)

2 _S_

=

_Ltest_ _[λσ][2]_ [(][1][ +][ λκ] [)] _[,]_ (128)

2S [κ.]

**Remark. Notably, the training loss decomposes into two additive terms. The term that is proportional**

=

_to 1 is the bias, caused by insufficient model expressivity to perfectly fit all the data points, while_
_the second term that is proportional to λκ_ _S is the variance in the model parameter, induced by the_
_randomness of minibatch noise._
**Remark. When the learning rate λ is vanishingly small, the expected test loss diminishes whereas/**
_the training error remains finite as long as label noise exists._

_Proof. We first calculate the approximation error. By definition,_

_Ltrain_ Ew _L_ **w**

_λσ[2]_

∶= [1] [ ( )]

2 [Tr][[][A][Σ][] +][ 1]2 _[σ][2][ =][ 1]2_ _S [κ][ +][ 1]2_ _[σ][2]_

=

_[σ][2]_ (129)

2 _S_

= [(][1][ +][ λκ] [)] _[.]_


-----

The test loss is


_Ltest_ [1]
= 2[λσ][E][2][w][ [][w][T][A][w][] =][ 1]2 [Tr][[][A][Σ][]] (130)

2S [κ.]

=


E.3 MINIBATCH NOISE FOR RANDOM NOISE IN THE INPUT

E.3.1 NOISE STRUCTURE

Similar to label noise, noise in the input data can also cause fluctuation. We assume that the training
data points ˜xi _xi_ _ηi can be decomposed into a signal part and a random part. As before, we assume_
Gaussian distributions, xi 0,A and ηi 0,B . The problem remains analytically solvable
if we replace the Gaussian assumption by the weaker assumption that the fourth-order moment exists = +
and takes some matrix form. For conciseness, we assume that there is no noise in the label, namely ∼N( ) ∼N( )
_yi_ **u[T]xi with a constant vector u. One important quantity in this case will be uu[T]** _U_ . Notice
that the trick w **u** **w no more works, and so we write the difference explicitly here. The loss**
function then takes the form = ∶=
− =1 _N_ 2

_L_ **w** **w** **u** _xi_ **w[T]ηi** 1 (131)

2N _i_ 1 2 [(][w][ −] **[u][)][T][A][(][w][ −]** **[u][) +][ 1]2** **[w][T][B][w][.]**

The gradient( _L) =_ _A_ ∑ B= [(w − **u)[T]** _B +u vanishes at]_ = **w** _A_ _B_ _Au, which is the minimum_
of the loss function and the expectation of the parameter at convergence. It can be seen that, even
∗
at the minimum ∇ **w = (, the loss function remains finite unless +** )( − ) + ∶= ( u 0 +, which reflects the fact that in the)[−][1]
presence of input noise, the network is not expressive enough to memorize all the information of the
∗
data. The SGD noise covariance for this type of noise is calculated in the following proposition. =
**Proposition 9.** _Covariance matrix for SGD noise in the input_ _Let the algorithm be updated_
_according to Eq. (1) or (98) with random noise in the input while the limit N_ _is taken with D_
_held fixed. Then the noise covariance is (_ )
→∞

_C_ [1] (132)

_S_

_where K_ _A_ _B, and Σ_ Ew **w** **w** **w** **w** _._
**Remark. It can be seen that the form of the covariance =** [{][K][Σ][K][ +][ Tr]∗ [[][K][Σ][]][K]∗[ +][ Tr] (132[[][AK]) of input noise is similar to that of label[−][1][BU] []][K][}] _[,]_
_noise (5) ∶= with replacing +_ _A ∶= by K and [(_ _σ −[2]_ _by)( Tr_ _AK −_ [−][1])BU[T]] _, suggesting that these two types of noise_
_share a similar nature._

[ ]

Defining the test loss as Ltest 12 [E][w][E][B][ [(][w][T][x][ −] **[u][T][x][)][2][]][, Proposition][ 9][ can then be used to]**
calculate the test loss and the model fluctuation.
**Theorem 9.** _Training error, test loss and model fluctuation for noise in the input ∶=_ _The expected_
_training loss is defined as Ltrain_ Ew _L_ **w** _, and the expected test loss is defined as Ltest_
1
( )
2 [E][w][E][B][ [(][w][T][x][ −] **[u][T][x][)][2][]][. For SGD with noise in the input given in Proposition][ (][9][)][, the expected]**
_approximation error and test loss are ∶=_ [ ( )] ∶=

_Ltrain_ [1] (133)

2 [Tr][[][AK] [−][1][BU] [](][1][ +][ λ]S [κ][′][)] _[,]_

_Ltest_ = _[λ]_ (134)

2S [Tr][[][AK] [−][1][BU] []][κ][′][ +][ 1]2 [Tr][[][B][′][T][AB][′][U] []][,]

Tr _KG[′−][1]_
_where κ[′]_ 1 _λ_ _S[1]_ [Tr][[][KG][′−][1][]][ with] =[ G][′][ ∶=][ 2][I][D][−][λ] [(][1][ +][ 1]S

[ ]

_Then the covariance matrix of model parameters is_

−

∶= [)] _[K][, and][ B][′][ ∶=][ K]_ [−][1][B][. Moreover, let]1 [ [][K,U] [] =][ 0][.]

Σ _[λ][Tr][[][AK]_ [−][1][BU] []] 1 _[λκ][′]_ _._ (135)

−

_S_ _S_ _S_

**Remark. Note that** _K,U =_ 0 is necessary only for an analytical expression of( + Σ. It can be obtained

[)[][2][I][D][ −] _[λ]_ [(][1][ +][ 1] [)] _[K][]]_

_by solving Eq. (144) even without invoking_ _K,U_ 0. In general, the condition that _K,U_ 0
_does not hold. Therefore, only the training and test error can be calculated exactly. [_ ] =
**Remark. The test loss is always smaller than or equal to the training loss because all matrices [** ] = [ ] =
_involved here are positive semidefinite._


-----

E.3.2 PROOF OF PROPOSITION 9

_Proof. We define Σ_ Ew **w** **w∗** **w** **w∗** . Then,

Ew **ww ∶=** [T] [( Σ − _A_ )( B − _AUA)[T]]_ _A_ _B_ Σ _A[′]UA[′][T]_ ΣA, (136)

Ew **w** **u** **w** **u** Σ _B[′]UB[′][T]_ ΣB, (137)

[ ] = + ( + )[−][1] ( + )[−][1] ∶= + ∶=

where we use the shorthand notations [( − )( − ) A[T]] =[′] +A _B_ _A,∶= B[′]_ _A_ _B_ _B and ΣA_ Σ _A[′]UA[′][T],_
ΣB Σ _B[′]UB[′][T]. We remark that the covariance matrix Σ here still satisfies the matrix equation_
(3) with the Hessian being K _A_ _B._ ∶= ( + )[−][1] ∶= ( + )[−][1] ∶= +
∶= +

The noise covariance is

∶= +

1 _N_

_C_ **w** _S[1]_ _N_ _i_ **w[T]x˜i** **u[T]xi** _x˜ix˜[T]i_ _xi_ **u[T]xi** _S_
( ) = ∑( − ) [(][w][T] [˜] − )[T] − [1]

[1] [∇][L][(][w][)∇][L][(][w][)][T]

_S_

= [{][A] Tr[(][w][ −]A[u]w[)(][w]u[ −] **[u]w[)][T][A]u[ +][ B][ww]K** [T] Tr[B][ +]B[ A]ww[(][w][T][ −]K[u][)][w]. [T][B][ +][ B][w][(][w][ −] **[u][)][T][A]** (138)

In Eq. (138), there are four terms without trace and two terms with trace. We first calculate the+ [ ( − )( − )[T]] + [ ] }
traceless terms. For the latter two terms, we have

Ew **w** **u** **w[T]** Σ _A[′]UB[′][T],_ (139)

Ew **w** **w** **u** Σ _B[′]UA[′][T]._ (140)

[( − ) ] = −

Because A[′] _B[′]_ _ID, after simple algebra the four traceless terms result in[_ ( − )[T]] = − 2 _A_ _B_ Σ _A_ _B_ .

The two traceful terms add to Tr _AΣB_ _BΣA_ _K. With the relation AB[′]_ _BA[′], what inside the_

+ = ( + ) ( + )

trace is

[ + ] =

_AΣB_ _BΣA_ _KΣ_ _AK_ [−][1]BU. (141)

Therefore, the asymptotic noise is + = +

_C_ Ew _C_ **w**
∶= [1] [ ( )] (142)

_S_

= [1] (143)

_S_ [{][K][Σ][K][ +][ Tr][[][A][Σ][B][ +][ B][Σ][A][]][K][}]

= [{][K][Σ][K][ +][ Tr][[][K][Σ][]][K][ +][ Tr][[][AK] [−][1][BU] []][K][}] _[.]_


E.3.3 PROOF OF THEOREM 9

_Proof. The matrix equation satisfied by Σ is_

ΣK _KΣ_ _λ_ 1 [1] (144)

_S_ _S_

By using a similar technique as in Appendix + − ( + E.2.2, the trace Tr _KΣ_ can be calculated to give

[)] _[K][Σ][K][ =][ λ]_ [(][Tr][[][K][Σ][]][K][ +][ Tr][[][AK] [−][1][BU] []][K][)] _[.]_

[ ]

Tr _KΣ_ _[λ][Tr][[][AK]_ [−][1][BU] []] _κ[′],_ (145)

_S_

Tr _KG[′−][1]_ [ ] =
where κ[′] 1 _λ_ _S[1]_ [Tr][[][KG][′−][1][]][ with][ G][′][ ∶=][ 2][I][D][ −] _[λ]_ [(][1][ +][ 1]S

[ ]

With Eq. (∶=145−), the training error and the test error can be calculated. The approximation error is[)] _[K][.]_


_Ltrain_ Ew _L_ **w** [1] (146)

2 [Tr][[][A][Σ][B][ +][ B][Σ][A][] =][ 1]2 [Tr][[][AK] [−][1][BU] [](][1][ +][ λ]S [κ][′][)] _[.]_

= [ ( )] =


-----

The test loss takes the form of a bias-variance tradeoff:

_Ltest_ [1]
= 2[λ][E][w][E][B][ [(][w][T][x][ −] **[u][T][x][)][2][] =][ 1]2** [E][w][ [(][w][ −] **[u][)][T][A][(][w][ −]** **[u][)] =][ 1]2** [Tr][[][A][Σ][B][]]

= 2S [Tr][[][AK] [−][1][BU] [](][1][ +][ λκ]S [′] 2 [Tr][[][B][′][T][AB][′][U] []]

_[λ]_ [)] [Tr][[][AG][′−][1][] +][ 1] (147)

2S [Tr][[][AK] [−][1][BU] []][κ][′][ +][ 1]2 [Tr][[][B][′][T][AB][′][U] []][.]

=

Let _K,U_ 0. Then Σ can be explicitly solved because it is a function of K and U . Specifically,

1

[ ] =

Σ _[λ][Tr][[][AK]_ [−][1][BU] []] 1 _[λκ][′]_ _._ (148)

−

_S_ _S_ _S_

= ( + [)[][2][I][D][ −] _[λ]_ [(][1][ +][ 1] [)] _[K][]]_


E.4 PROOFS IN SEC. 4.3

E.4.1 PROOF OF PROPOSITION 3

_Proof. The covariance matrix of the noise is_

1 _N_

_C_ **w** [1] **w** **u** _xixi_ Γw _x[T]i_ _[x]i[T]_

_S_ _N_ _i_ _S_

( ) = ∑ [( − )[T] + ][ [(][w][ −] **[u][) +][ w][T][Γ][] −]** [1]

[1] [∇][L][Γ][(][w][)∇][L][Γ][(][w][)][T](149)

_S_

Using a similar trick as in Appendix= [{][A][(][w][ −] **[u][)(][w][ −]** **[u][)][T] E.3.2[A][ +][ Tr], the asymptotic noise is[[][A][(][w][ −]** **[u][)(][w][ −]** **[u][)][T][]][A][}][.]**


_C_ [1] (150)

_S_

= [(][A][Σ][A][ +][ Tr][[][A][Σ][]][A][ +][ Tr][[][Γ][′][T][A][Γ][′][U] []][A][ +][ Γ][A][′][UA][′][Γ][)] _[.]_

E.4.2 PROOF OF THEOREM 4


Besides the test loss and the model fluctuation, we derive the approximation error here as well.

**Theorem.** Training error, test loss and model fluctuation for learning with L2 regularization The
expected training loss is defined as Ltrain Ew _L_ **w**, and the expected test loss is defined as
_Ltest_ [1]2 [E] ([w][E][B][ [(][w][T][x][ −] **[u][T][x][)][2][]][. For noise induced by L][2][ regularization given in Proposition])** [ 3][,]

let _A,_ Γ 0. Then the expected approximation error and test loss are ∶= [ ( )]

∶=

[ ] =

_Ltrain_ _[λ]_
= 2S [Tr][1] [[][AK] [−][2][Γ][2][U] []][Tr][[][AG][−][1][](][1][ +][ λκ]S 2S _S_ [Tr][[][AG][−][1](151)[])]

2 [Tr][[][AK] [−][1][Γ][U] []][,] [) +][ λ] [(][Tr][[][A][2][K] [−][2][Γ][2][G][−][1][U] [] +][ λr]

_Ltest_ _[λ]_ + (152)

2S 2 [Tr][[][AK] [−][2][Γ][2][U] []][,]

= Tr _A[2]K[−][1]G[−][1]_

where κ 1 [(]S[Tr][Tr][[][[][A][AK][2][K][−][−][1][2][G][Γ][−][2][1][U][]] [,][ r][]][κ][ ∶=][ +][ Tr][ r]1[) +][[]S[A][Tr][ 1][3][K][[][A][−][3][2][Γ][K][2][−][G][1][−][G][1][−][U][1][]][]] [, with][ G][ ∶=][ 2][I][D][ −] _[λ]_ [(][K][ +][ 1]S _[K]_ [−][1][A][2][)][. Moreover,]

[ ]

if A, Γ and U commute with each other, the model fluctuation is

− _[λ]_ − _[λ]_

∶=

Σ _[λ]_ (153)

_S_ [Tr][[][AK] [−][2][Γ][2][U] [](][1][ +][ λκ]S _S_ _S [A][)]_ _[K]_ [−][1][G][−][1][.]

**Remark. = Because Γ may not be positive semidefinite, the test loss can be larger than the training**

[)] _[AK]_ [−][1][G][−][1][ +][ λ] [(][A][2][K] [−][2][Γ][2][U][ +][ λr]

_loss, which is different from the input noise case._


-----

_Proof. The matrix equation obeyed by Σ is_

ΣK _KΣ_ _λKΣK_ _S [A][Σ][A][ =][ λ]S_ [Tr][[][A][Σ][]][A][ +][ λ]S

(154)

+ − − _[λ]_ [(][Tr][[][AK] [−][2][Γ][2][U] []][A][ +][ AK] [−][1][Γ][U] [Γ][K] [−][1][A][)] _[,]_

where we use the shorthand notation K _A_ Γ. Let _A,_ Γ 0. Using the trick in Appendix E.2.2,
the trace term Tr _AΣ_ is calculated as
∶= + [ ] =

[ ] Tr _AΣ_ _[λ]_ (155)

_S_

Tr _A[2]K[−][1]G[−][1]_ [ ] =
where κ 1 _S_ [Tr][[][A][2][K][−][1][G][−][1][]] [,][ r][ ∶=][ Tr]1 [[]S[A][Tr][3][K][[][A][−][3][2][Γ][K][(][2][Tr][−][G][1][−][G][[][1][AK][−][U][1][]][]] [, and][−][2][Γ][ G][2][U][ ∶=][]][κ][ 2][ +][I][ r][D][)][ −][,] _[λ]_ [(][K][ +][ 1]S _[K]_ [−][1][A][2][)][.]

[ ]

The training error is ∶= − _[λ]_ − _[λ]_

_Ltrain_ [1]
= 2[1] [Tr][[][A][Σ][Γ][ +][ ΓΣ][A][]]

= 2[λ][Tr][[][K][Σ][] +][ 1]2 [Tr][[][AK] [−][1][Γ][U] []]

= 2S[1][Tr][[][AK] [−][2][Γ][2][U] []][Tr][[][AG][−][1][](][1][ +][ λκ]S 2S _S_ [Tr][[][AG][−][1](156)[])]

2 [Tr][[][AK] [−][1][Γ][U] []][.] [) +][ λ] [(][Tr][[][A][2][K] [−][2][Γ][2][G][−][1][U] [] +][ λr]

The test loss is+

_Ltest_ [1]
= 2[1] [E][w][E][B][ [(][w][T][x][ −] **[u][T][x][)][2][]]**

= 2[λ][E][w][ [(][w][ −] **[u][)][T][A][(][w][ −]** **[u][)] =][ 1]2** [Tr][[][A][Σ][Γ][]] (157)

2S 2 [Tr][[][AK] [−][2][Γ][2][U] []][.]

=

Let A, Γ and U commute with each other. Then,[(][Tr][[][AK] [−][2][Γ][2][U] []][κ][ +][ r][) +][ 1]

Σ _[λ]_ (158)

_S_ [Tr][[][AK] [−][2][Γ][2][U] [](][1][ +][ λκ]S _S_ _S [A][)]_ _[K]_ [−][1][G][−][1][.]

= [)] _[AK]_ [−][1][G][−][1][ +][ λ] [(][A][2][K] [−][2][Γ][2][U][ +][ λr]

E.4.3 PROOF OF COROLLARY 1

For a 1d example, the training loss and the test loss have a simple form. We use lowercase letters for
1d cases.

**Corollary 4. For a 1d SGD with L2 regularization, the training loss and the test loss are**

_aγ_ 2 _a_ _γ_ _λ_ _a_ _γ_ _S[2]_ _[a][(][a][ −]_ _[γ][)]]_
_Ltrain_ _u[2],_ (159)

2 _a_ _γ_ ( 2 +a ) − γ [(λ +a )[2] γ+ _S[2]_ _[a][2][]]_

= _aγ[2]_ 2 _λ_ _a_ _γ_

_Ltest_ ( + ) ( + ) − [( + )[2] + (160)

2 _a_ _γ_ 2 _a_ _γ_ _λ_ _a_ _γ_ _S[2]_ _[a][2][]]_ _[u][2][.]_
− ( + )

=

_Proof. The training error and the test loss for 1d cases can be easily obtained from Theorem(_ + ) ( + ) − [( + )[2] + E.4.2.


Now we prove Corollary 1.

_Proof. The condition for convergence is 1_ _S_ [Tr][[][A][2][K] [−][1][G][−][1][] >][ 0][. Specifically,]

_λ_ _a_ _γ_ − 2[λ] _a_ _γ_ _λ_ _S [2]_ _[a][2][ <][ 0][.]_ (161)
( + )[2] − ( + ) +


-----

For a given γ, the learning rate needs to satisfy

2 _a_ _γ_
_λ_ (162)

_a_ _γ_ _S[2]_ _[a][2][ .]_

( + )
<

For a given λ, γ needs to satisfy

( + )[2] +

1 _aλ_ 1 _S_ _[a][2][λ][2]_ 1 _aλ_ 1 _S_ _[a][2][λ][2]_
√ _γ_ √ _,_ (163)

_λ_ _λ_

− − − [2] − + − [2]

which indicates a constraint on λ: < <

_S_

_aλ_ (164)

√ 2 _[.]_

<

If γ is allowed to be non-negative, the optimal value can only be 0 due to the convergence condition.
Therefore, a negative optimal γ requires an upper bound on it being negative, namely


1 _aλ_
− +


1 _S_ _[a][2][λ][2]_
− [2]


0. (165)
<

(166)


Solving it, we have


2
_aλ_ _._

1 _S[2]_

>

By combining with Eq. (164), a necessary condition for the existence of a negative optimal γ is

+


2 _S_

(167)

1 _S[2]_ √ 2

Hence, a negative optimal γ exists, if and only if + < [→(][S][ −] [2][)][2][ >][ 0][ →] _[S][ ≠]_ [2][.]


_aλ_
< <


_S_

(168)
2 _[,][ and][ S][ ≠]_ [2][.]


1 _S[2]_
+


For higher dimension with Γ _γID, it is possible to calculate the optimal γ for minimizing the test_
loss (11) as well. Specifically, the condition is given by
=

_d_ _d_ _f_ _γ_

_dγ [L][test][ ∶=][ 1]2_ _dγ_ _g_ _γ_ (169)

( )

where

( ) [=][ 0][,]

_f_ _γ_ _γ[2]Tr_ _AK_ [−][2] _ID_ _[λ]_ (170)

_S [A][2][K]_ [−][1][G][−][1][)] _[U]_ []] _[,]_

_g_ (γ ) ∶= 1 [ ( + (171)

_S_ [Tr][[][A][2][K] [−][1][G][−][1][]][.]

Although it is impossible to solve the equation analytically, it can be solved numerically.( ) ∶= − _[λ]_


-----

