1. A.1 What we Know
    2. A.2 When the Variance is Smaller
  12. B Practical Example: the Setting for the Plots
  13. C The Effect of Mini-batching
    1. C.1 Fixed Batches SGD Trajectory
    2. C.2 The Implicit Bias of the Order
  14. D The Philosophy of the Analysis
  15. E Dealing with Expectations
    1. E.1 Lemma for Expectations Without Replacement
    2. E.2 The Main Lemma
    3. E.3 Corollary for big $n$ and $k$
    4. E.4 Corollary about Covariances
  16. F Expanding in Taylor the Trajectories
    1. F.1 Notations
    2. F.2 Computing the Deviation between SGD and Big-Learning-Rate GD.
    3. F.3 Reorganizing the terms, 1
    4. F.4 Reorganizing the Terms, 2
  17. G Proof of Theorem 2 and 12
    1. G.1 (Step 1) The Summands and the Potential
    2. G.2 (Step 2) Taking the Expectation of the Regularizer
    3. G.3 (Step 3) Summing up.
    4. G.4 (Step 4) The Size of the Step Given the Hessian
  18. H A Deeper Look into $S_{0}$ of Theorem 2
  19. I The Whole Regularizer: Theorem 3
  20. J Size of the Error
  21. K The Error $\Delta-\alpha$.
  22. L Proof of Theorem 4
  23. M On the Gradients of Neural Networks
  24. N Saddles

##  Appendix A The Variance of SGD without replacement

###  A.1 What we Know

[Mishchenko et al., 2020] computed the variance of one step of SGD without
replacement. They showed that starting from the minimum of a strong convex
objective function, the variance of one step of SGD is upper bounded by
$O(\eta c\nabla^{2}L)$, while for SGD with replacement, it is upper bounded by
$O\left(\eta\frac{\lambda_{max}\nabla^{2}L}{\lambda_{min}\nabla^{2}L}\right)$.
They also observed empirically that SGD without replacement in some strong
convex settings has higher variance at initialization. However, they noted
that the variance for SGD without replacement decreases more rapidly. After
approximately $O(1)$ epochs, its variance becomes lower than that of SGD with
replacement, leading to faster convergence. They also have a result for non-
convex scenarios; yet, it applies in the regime where
$c\lambda_{max}\nabla^{2}L<1/\sqrt{2b}$, which may be too restrictive for
practical applications.

Nevertheless, these findings alone help explain the smaller variance sizes
observed in certain settings. In some cases indeed, as the dynamics converge,
it gets trapped in invariant sets like those identified by [Chen et al.,
2023]. Within these invariant sets, the dynamics might exhibit local strong
convexity. This is the case for diagonal networks, for example, but typically
not for general neural networks [Liu et al., 2020]. [Liu et al., 2020]. For
instance, consider the toy model $(a\cdot bx-y)^{2}$, where
$a,b,x,y\in\mathbb{R}^{+}$, of §B. In this model, the dynamics are driven to
the hyperplane where $a=b$, either by the regularizer in SGD without
replacement or by diffusion in SGD with replacement, and get trapped there.
When restricted to the subspace $a=b$, the objective function becomes locally
strongly convex, specifically $(a^{2}x-y)^{2}$. If $x,y>0$, near the minimum
at $a=\sqrt{y}/\sqrt{x}$, oscillations are observed to be of size
$O(\eta^{2})$ for SGD without replacement, compared to $O(\eta)$ for SGD with
replacement.

Nevertheless, in practical scenarios where the Hessian has large or zero
eigenvalues, these worst-case results from convex optimization may not fully
explain the trajectory or the size of the variance.

###  A.2 When the Variance is Smaller

It is easy to see that in the regime in which $c\|\nabla^{2}L\|\ll 1$ the
update to the parameters resulting from an epoch of SGD without replacement is
approximately deterministic; indeed,

$\theta^{SGD}_{k}-\theta\quad=\quad-\eta\sum_{i=1}^{k}\nabla L(B_{i})\ +\
O(c\|\nabla^{2}L\|)\quad=\quad-c\nabla L\ +\ O(c\|\nabla^{2}L\|).$

This suggests already that: (i) We have a big variance only in the presence of
big eigenvalues of the Hessian, and in case only in the direction of the
eigenvectors of the big eigenvalues. And (ii) we can expect the variance of
SGD without replacement to be smaller than the one of SGD with replacement
when some of the key ingredients of the trajectory are small.

Moreover, in the case in which our discretization explains the trajectory,
i.e., $\eta\nabla L\ll 1$, the variance of SGD without replacement get shrunk
by the addition of the regularizer in the term
$-\mathbb{E}\left[\begin{subarray}{c}\text{trajectory}\\\ \text{without
replacement}\end{subarray}\right]^{2}$.

We can thus conclude that the variance of the noise in one epoch of SGD
without replacement is smaller than the one with replacement at least when (i)
the Hessian $c\nabla^{2}L\ll 1$ is small, or (ii) the gradients $c\nabla L\ll
1$ are small. And we can go even further, consider at any epoch of SGD the
update in the direction of the eigenvector $v_{\lambda}$ of the eigenvalue
$\lambda$ of the Hessian.

  * •

If $c\lambda\ll 1$, $\langle v_{\lambda},\nabla L\rangle\neq 0$, the
eigenvalue is part of the bulk of small ones, then SGD without replacement has
very small variance in that direction, unlike SGD with replacement. The push
in that direction, in first approximation, is due only to full-batch gradient
descent and the regularizer.

  * •

For all $\lambda$s, even the big ones, if $\langle v_{\lambda},\nabla
L\rangle\ll 1$, then SGD without replacement has a small variance in that
direction, in particular, smaller than SGD with replacement. The push in that
direction, in first approximation, is due only to the regularizer, and if
$\eta\lambda>1$ to the oscillation of GD.

##  Appendix B Practical Example: the Setting for the Plots

The setting of Figs. 1 and 2 is the easiest possible neural network setting
trainable with SGD. We have the $f(\theta,x)=\theta_{1}\cdot\theta_{2}\cdot
x$, it is a linear shallow network with width, input, and output dimensions
being 1. The Dataset consists of 3 points $D=\\{(1,1),(1,2),(1,0)\\}$, the
chosen loss is the MSE. Precisely, the loss
$L(\theta)=(\theta_{1}\cdot\theta_{2}-1)^{2}+(\theta_{1}\cdot\theta_{2}-2)^{2}+(\theta_{1}\cdot\theta_{2})^{2}$
with initialization the white bullet $\theta=(1,6)$. The lowest norm global
minimum is $\pm(1,1)$.

This setting shares the same peculiarities of linear diagonal network
scenarios. In particular, our experiments extends to bigger linear diagonal
networks. Precisely, we have that, (i) the minimum with the widest valley is
also the min-norm solution, (ii) the min-norm solution coincindes also with
the global minimum that zeros out our regularizer, and (iii) the global minima
have loss $>0$. The datapoints have the same $x$ but different $y$. Thus the
SGD noise never fades out and keeps pushing toward the direction of the
regularizer. Moreover, this makes SGD with replacement coincide with a version
of GD with label noise. This is not a bad thing as label noise has generally
better and understood generalization capabilities [Damian et al., 2021].

The code that generated the figures can be found on this github repository.

##  Appendix C The Effect of Mini-batching

The goal of this section is to understand the role of the following two
properties of SGD without replacement:

  * •

The fact that the mini-batches add up to the dataset.

  * •

The fact that once the mini batches are sampled we do not care about their
order.

The first property above is shared by the SGD without replacement and Shuffle
Once, and the second by SGD with and without replacement. However, once we
take the expectation over the possible outcome of the initial shuffling, the
same holds for Shuffle Once. We argue that it is the fact that we do not care
about the order that allows us to rewrite our quantity as a derivative of a
penalization. This properties are not shared, e.g., by Adam.

###  C.1 Fixed Batches SGD Trajectory

We address here the following question:

Question:
Assume we sampled already the batches $B_{1},B_{2},\ldots,B_{k}$ (fixed) and
we make $k$ steps of SGD using them. How far are we from the GD trajectory?

For the reasons described in §2.3 and §2.4, we expand $k$ steps of SGD and GD
with learning rate $\eta$ at the beginning of the epoch, and we keep the terms
in which $\nabla L(\cdot)$ appears to the power 1. We write the difference
between this quantity in the case of SGD and the case of GD and we obtain the
following

######  Proposition 11.

The deviation due to mini-batches from the trajectory of the GD is

$\begin{split}\eta^{2}\sum_{1\leq i<j\leq
k}\nabla^{2}L(B_{j})\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\nabla L(B_{i})\quad-\quad\begin{subarray}{c}\text{same but full-batch:}\\\
B_{j}\curvearrowleft D\text{ for all }j\leq epoch\end{subarray}.\end{split}$

up to first order in $\eta k\nabla L(B_{i})$, $i=1,2,\ldots,k$. The error is
of order $O(\eta^{2+}k^{3}\|\nabla L\|^{2}).$

More details about the computation are in the proof in Appendix F, more
details about the size of the error in §J.

###  C.2 The Implicit Bias of the Order

We derived a formula for the deviation in the trajectory, which depends on the
order in which we observe the batches. It makes thus sense to examine the
expectation and standard deviation of this SGD discretization with respect to
the GD trajectory due to the randomly uniform order of the batches.

Assume we sampled already the batches $B_{1},B_{2},\ldots,B_{k}$ (fixed). How
far do we go from the GD/GF trajectory, on average over the possible orders of
the batches?

To do it, we consider the following quantity

$\frac{\eta^{2}}{2}\nabla_{\theta}\sum_{1\leq i<j\leq
k}[\nabla^{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}L(B_{j})]^{\top}\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\nabla L(B_{i})$ (11)

The derivative of this quantity in $\theta$ is

$\begin{split}&\quad\frac{\eta^{2}}{2}\sum_{1\leq i<j\leq
k}\nabla^{2}L(B_{j})\
\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\ \nabla
L(B_{i})\qquad\leftarrow\text{\lx@cref{creftype~refnum}{theo:SGD_effect_fixed_batches}!}\\\
&+\frac{\eta^{2}}{2}\sum_{1\leq i<j\leq k}\nabla^{2}L(B_{i})\
\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}^{\top}\ \nabla
L(B_{j})\qquad\ \ \leftarrow\text{flipped }i,j\\\
&+\frac{\eta^{2}}{2}\sum_{1\leq i<j\leq k}\nabla L(B_{j})^{\top}\
\Bigg{[}\nabla_{\theta}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}^{\top}\
\nabla L(B_{i}).\ \ \leftarrow\text{error term!}\end{split}$ (12)

In the first line we have half of the term in 9, and in the second line we
have the same quantity but with the indices switched. The third line is a part
of the error as constitute a term of second order in $\eta\nabla L$. This is
the key idea of the proof of the following theorem other than of the main
theorem, Theorem 2.

######  Proposition 12.

With an additive error of size smaller than $O(\text{that})\cdot(\eta k\nabla
L+1/k)$, we have

$\theta_{k}^{SGD}\quad\overset{\begin{subarray}{c}\text{expectation over}\\\
\text{order of
batches}\end{subarray}}{=}\quad\theta_{k}^{GD}\quad-\quad\eta\nabla_{\theta}Regularizer$

where where the regularizer is

$\begin{split}\eta\mathbb{E}_{order}\left[\sum_{1\leq i<j\leq k}\nabla
L(B_{j})^{\top}\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\nabla L(B_{i})\right]\quad-\quad\begin{subarray}{c}\text{same but full-
batch:}\\\ B_{j}\curvearrowleft D\text{ for all }j\leq
epoch\end{subarray}.\end{split}$

We can thus conclude that: (i) The reason why we can rewrite this deviation as
the derivative of a potential is that we do not care about the order in which
we see the batches. And (ii) this happens for every SGD technique once we
sample the batches, irrespective of how we sampled them.

##  Appendix D The Philosophy of the Analysis

We briefly present here the philosophy and tools of our analysis and proof.

Our analysis consists of two main phases: (i) writing down the low-order part
of the deviation, noticing that it is the derivative of a quantity, and (ii)
computing its moments. Precisely, we start by expanding in Taylor at the
beginning of the epoch the shift in trajectory between the SGD of learning
rate $\eta$ with batches $B_{1},B_{2},\ldots,B_{k}$ and the GD or learning
rate $\eta\cdot k$. We do this by iteratively considering the shift after $i$
steps with the GD with learning rate $\eta\cdot i$ on $\cup_{j=1}^{i}B_{j}$.
Indeed, we find that at every step $i$ the shift gets multiplied by
$I-\eta\nabla^{2}L(B_{i})$ and we add the terms
$\eta^{2}\nabla^{2}L(B_{i})\sum_{i<j}\nabla L(B_{j})$ (this will become the
regularizer) and the higher-order terms of the Taylor will become the error.
The part highlighted is the leading part in the case in which $\eta\nabla
L(B_{1}),\eta\nabla L(B_{1})+\eta\nabla
L(B_{2})),\ldots,\eta\sum_{j=1}^{k}\nabla L(B_{j})$ are small. Indeed those
quantities appear with exponent 1 in the "regularizer" part and with exponent
$\geq 2$ in the part that we consider to be the error. It is important to
notice that later we will weaken these assumptions. Precisely, if we take the
expectation already of the Taylor expansion of the error and then we highlight
this part, and not vice-versa, we will be able to just assume that the
expectations are small. This will imply that the result works in the case in
which $\eta^{1+}k\nabla L\ll 1$.

We follow by noticing that by adding terms that are $O(\eta k\nabla L)^{2}$,
that thus fall into the error part, this deviation between the trajectories
coincides with the derivative of a quantity. Now by subtracting to what we
obtained the analogous term but in the setting in which $B_{i}=D$ for all $i$,
i.e., the shift between small step and big step GD, we obtain our regularizer
(still as a function of the batches, there are still no expectations
involved).

We will later conclude by computing the moments of these quantities arising
from the Taylor series in the setting without replacement. In this setting, we
develop a lemma that helps us compute the moments of the quantities in play.
More details about this in §E.

##  Appendix E Dealing with Expectations

To prove our main result, we need to be able to compute all the expectations
that we encounter. Those are taken over the SGD sampling procedure, i.e.,
sampling without replacement:

######  Setting 13 (Sampling without replacement).

Assume $z_{1},z_{2},\ldots,z_{k}$ are sampled in one of the following two
equivalent ways.

  1. 1.

$\\{z_{1},z_{2},\ldots,z_{k}\\}$ is a set of $k$ different elements that has
been uniformly sampled from the family of all the possible different subsets
(without multiple copies) of cardinality $k$ of a set $D$ with cardinality
$n$.

  2. 2.

We sampled $z_{1}$ uniformly from $D$, $z_{2}$ uniformly from
$D\backslash\\{z_{1}\\}$, $\ldots$, and $z_{k}$ uniformly from
$D\backslash\\{z_{1},z_{2},\ldots,z_{k-1}\\}$.

All the expectations in what follows will be over this sampling procedure.
Indeed, if we see a batch or a data point we will not see it until the end of
the epoch.

We will assume we have a sequence of functions that take in input elements of
$D$ and output a tensor such that the shapes of the tensors match and we can
make a product. Precisely, for all $i\in\\{1,2,\ldots,k\\}$ we have
$f_{i}\colon D\to\mathbb{R}^{n_{i}\times n_{i+1}}$ where
$n_{1},n_{2},\ldots,n_{k+1}\in\mathbb{N}$. Precisely, in the following these
$f$s will take a training data point $z\in D$ in input and they will output a
derivative of the loss in the parameters evaluated at that data point, e.g.
$f_{1}(z_{1})=I-\nabla_{\theta}^{2}L(\theta,z_{1})$.

###  E.1 Lemma for Expectations Without Replacement

######  Lemma 14.

Let $D=\\{z_{j}\\}_{j\in\\{1,2,\ldots,n\\}}\subseteq\mathbb{R}^{d}$, let
$B_{1},B_{2},\ldots,B_{k}$ batches of size $b$ sampled without replacement
from $D$, see 13. Let $A\in\mathbb{R}^{d\times d}$ and denote by
$Z_{i}:=\tfrac{1}{b}\sum_{z\in B_{i}}z$ the average of the vectors in the
$i-th$ batch, by $\bar{z}:=\frac{1}{n}\sum_{z\in D}z$. Then

$\mathbb{E}_{\left[\begin{subarray}{c}without\\\
replacement\end{subarray}\right]}\left[\sum_{i=1,j}^{h}Z_{i}^{\top}AZ_{j}\right]-h\bar{z}^{\top}A\bar{z}\quad=\quad\frac{h(n-hb)}{b(n-1)}\left(\mathbb{E}_{z\in
D}\big{[}z^{\top}Az\big{]}-\bar{z}^{\top}A\bar{z}\right).$

###### Proof.

Denote by $\alpha:=\mathbb{E}_{z\in D}z^{\top}Az-\bar{z}^{\top}A\bar{z}$. Note
that

$\mathbb{E}_{\left[\begin{subarray}{c}without\\\
replacement\end{subarray}\right]}\left[\sum_{i,j=1}^{h}Z_{i}^{\top}AZ_{j}\right]\quad=\quad\mathbb{E}_{\left[\begin{subarray}{c}without\\\
replacement\end{subarray}\right]}\left[\sum_{1\leq i\neq j\leq
h}Z_{i}^{\top}AZ_{j}+\sum_{1\leq i\leq h}Z_{i}^{\top}AZ_{i}\right]$

$\begin{split}&h(h-1)\left(-\frac{\alpha}{n-1}\right)+h\left(\frac{b-1}{b}\bar{z}^{\top}A\bar{z}-\frac{b-1}{b}\frac{\alpha}{n-1}+\frac{1}{b}\mathbb{E}_{z\in
D}[z^{\top}Az]\right)\\\ &=\quad
h\bar{z}^{\top}A\bar{z}-\frac{1}{n-1}\left(h^{2}-\frac{h}{b}\right)\alpha+\frac{h}{b}\alpha\\\
&=\quad h\bar{z}^{\top}A\bar{z}-\frac{h^{2}b-hn}{b(n-1)}\alpha.\end{split}$
(13)

∎

###  E.2 The Main Lemma

######  Lemma 15 (How the expectation looks like).

Assume we are in 13 above. Then, when $S$ is sampled as in Item 1 of 13, the
expectation $\mathbb{E}\left[f_{1}(z_{1})\cdot f_{2}(z_{2})\cdot\ldots\cdot
f_{k}(z_{k})\right]$, is equal to

$\begin{split}\left[\prod_{i=0}^{k-1}(n-i)\right]^{-1}\sum\prod_{i=1}^{k}f_{i}(z_{i})\end{split}$
(14)

where, thus, the sum is taken over all the possible $k$-uple
$(z_{1},z_{2},\ldots,z_{k})$ of $k$ different elements of $D$. By averaging
over the sampling technique in Item 2, we obtain quantities like the following
in the case of commutation of the $f_{i}$s.

$\begin{split}\left[\prod_{i=0}^{k-1}\frac{n}{n-i}\right]\sum_{j=1}^{k}\sum_{\sigma\in\Pi}\prod_{\begin{subarray}{c}\text{all
the possible}\\\
0=i_{0}<i_{1}<\ldots<i_{j}=k\end{subarray}}\\!\\!\\!\\!\\!\left[\frac{-1}{n}\right]^{i_{j}-i_{j-1}-1}\mathbb{E}_{z\in
D}\left[\prod_{h=i_{j-1}+1}^{i_{j}}f_{\sigma(h)}(z)\right].\end{split}$ (15)

where $\Pi$ is the set of all the possible permutations of
$\\{1,2,\ldots,k\\}$. That is the sum of all the possible products of
expectations of products of functions. Each of the expectations of products of
$l$ functions is multiplied by $\left[\frac{-1}{n}\right]^{l-1}$. Another way
to rewrite it is $\left[\prod_{i=0}^{k}\frac{n}{n-i}\right]$ multiplied by

$\begin{split}&\prod_{i=1}^{k}\mathbb{E}[f_{i}]-n^{-1}\sum_{i\neq
j}\mathbb{E}[f_{i}f_{j}]\prod_{m\neq j,i}\mathbb{E}[f_{m}]+n^{-2}\sum_{i\neq
j\neq h\neq l}\mathbb{E}[f_{i}f_{j}]\mathbb{E}[f_{h}f_{l}]\prod_{m\neq
j,i,h,l}\mathbb{E}[f_{m}]+\ldots\end{split}$ (16)

###### Proof of Lemma 15..

Let us now prove what above, regarding the first part in Eq. 14, it follows
directly from the definition of average. We prove the other thing by
induction. Note that for $k=1,2$ we have the result in Eq. 15 already (base
case). Indeed, note that

$\mathbb{E}_{D\backslash\\{z\\}}[f]\quad=\quad\frac{1}{n-1}\sum_{x\in
D\backslash\\{z\\}}f(x)\quad=\quad\frac{n}{n-1}\left[\mathbb{E}_{D}[f]-\frac{f(z)}{n}\right]$
(17)

and by plugging this in

$\begin{split}\mathbb{E}_{z_{1}\in D}[f_{1}(z_{1})\cdot\mathbb{E}_{z_{2}\in
D\backslash\\{z_{1}\\}}[f_{2}(z_{2})]]\quad&=\quad\frac{n}{n-1}\mathbb{E}_{D}[f_{2}]\mathbb{E}[f_{1}]-\frac{1}{n-1}\mathbb{E}_{D}\left[f_{1}f_{2}\right].\end{split}$
(18)

Let us see the step $k=3$ to better explain what is happening

$\begin{split}&\mathbb{E}_{z_{1}\in D}[f_{1}(z_{1})\cdot\mathbb{E}_{z_{2}\neq
z_{3}\in D\backslash\\{z_{1}\\}}[f_{2}(z_{2})f_{3}(z_{3})]]\\\
&\quad=\quad\mathbb{E}_{z_{1}\in
D}\left[f_{1}(z_{1})\cdot\left(\frac{n-1}{n-2}\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{2}]\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{3}]-\frac{1}{n-2}\mathbb{E}_{D\backslash\\{z_{1}\\}}\left[f_{2}f_{3}\right]\right)\right]\\\
&\quad=\quad\mathbb{E}_{z_{1}\in
D}\Bigg{[}f_{1}(z_{1})\cdot\bigg{(}\frac{n-1}{n-2}\frac{n}{n-1}\left[\mathbb{E}_{D}[f_{2}]-\frac{f_{2}(z_{1})}{n}\right]\frac{n}{n-1}\left[\mathbb{E}_{D}[f_{3}]-\frac{f_{3}(z_{1})}{n}\right]\\\
&\qquad-\frac{1}{n-2}\left[\frac{n}{n-1}\mathbb{E}_{D}\left[f_{2}f_{3}\right]-\frac{f_{2}(z_{1})f_{3}(z_{1})}{n-1}\right]\bigg{)}\Bigg{]}.\end{split}$
(19)

Next by noting that

$\begin{split}(n-1)\
\frac{f_{2}(z_{1})}{n-1}\frac{f_{3}(z_{1})}{n-1}\quad=\quad\frac{f_{2}(z_{1})f_{3}(z_{1})}{n-1}\end{split}$
(20)

we conclude that

$\begin{split}&\mathbb{E}_{z_{1}\neq z_{2}\neq z_{3}\in
D}[f_{1}(z_{1})f_{2}(z_{2})f_{3}(z_{3})]\quad=\quad\frac{n^{3}}{n(n-1)(n-2)}\mathbb{E}[f_{1}]\mathbb{E}[f_{2}]\mathbb{E}[f_{3}]\\\
&\quad-\frac{n^{2}}{n(n-1)(n-2)}\left(\mathbb{E}\left[f_{1}f_{2}\right]\mathbb{E}[f_{3}]+\mathbb{E}[f_{1}]\mathbb{E}\left[f_{2}f_{3}\right]+\mathbb{E}\left[f_{1}\cdot\mathbb{E}[f_{2}]\cdot
f_{3}\right]\right)\\\
&\quad+2\frac{n}{n(n-1)(n-2)}\mathbb{E}[f_{1}f_{2}f_{3}].\end{split}$ (21)

More generally we will have all the possible products showing up with the
multiplier $(-n)^{-order+1}$. Indeed or what regards the inductive step, note
that by tower rule

$\begin{split}\mathbb{E}_{D}\left[\,f_{1}(z_{1})\cdot
f_{2}(z_{2})\cdot\ldots\cdot
f_{k}(z_{k})\right]\quad=\quad\mathbb{E}_{z_{1}\in D}\left[f_{1}(z_{1})\
\cdot\ \mathbb{E}_{D\backslash\\{z_{1}\\}}\left[f_{2}(z_{2})\cdot\ldots\cdot
f_{k}(z_{k})\right]\right]\end{split}$ (22)

So the expectation for $z_{1},z_{2},\ldots,z_{k}\in D$ without replacement it
is the same as the expectation over $z_{1}\in D$ of the expectation for
$z_{2},z_{3},\ldots,z_{k}\in D\backslash\\{z_{1}\\}$ without replacement. We
will also prove that Now, applying the inductive hypothesis for
$k\curvearrowleft k-1$ and $D\curvearrowleft D\backslash\\{z\\}$ on
$\mathbb{E}_{D\backslash\\{z_{1}\\}}\left[f_{2}(z_{2})\cdot\ldots\cdot
f_{k}(z_{k})\right]$ we obtain that

  * •

The multiplier is $\prod_{i=0}^{k-1}\frac{n}{n-i}$.

  * •

That we have
$n^{k}\prod_{i=1}^{k}\mathbb{E}[f_{i}]-n^{k-1}\sum_{i<j}\mathbb{E}[f_{i}f_{j}]\prod_{h\neq
i,j}\mathbb{E}[f_{h}]+\ldots$ and in general appears every possible
combination of expectations of products of the functions, such that when we
are taking the expectations of $l$ functions together, we have $(-1/n)^{l-1}$
multiplying the head coefficient.

######  Remark 16.

From now on we perform the computations in the case of commutations, but they
would not change at all in case of no commutation. It is just more difficult

Let us assume it works for $D\backslash\\{z_{1}\\}$ and $k-1$. Then the
expectation in that setting is the following and satisfies the points above.

$\begin{split}\left[\prod_{i=1}^{k}\frac{n-1}{n-i}\right]\left[\prod_{i=2}^{k}\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{i}]-(n-1)^{-1}\sum_{i\neq
j}\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{i}f_{j}]\prod_{m\neq
i,j}\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{m}]+\ \ldots\ \right]\end{split}$
(23)

Thus plugging this into Eq. 22 we obtain that
$\mathbb{E}_{D}\left[\,f_{1}(z_{1})\cdot f_{2}(z_{2})\cdot\ldots\cdot
f_{k}(z_{k})\right]$ is equal to

$\begin{split}\mathbb{E}_{D}\Bigg{[}f_{1}(z_{1})\cdot\Bigg{[}(n-1)^{k-1}\prod_{i=2}^{k}\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{i}]-(n-1)^{k-2}\sum_{i\neq
j}\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{i}f_{j}]\prod_{m\neq
i,j}\mathbb{E}_{D\backslash\\{z_{1}\\}}[f_{m}]\Bigg{]}\Bigg{]}\end{split}$
(24)

multiplied by $\left[\prod_{i=1}^{k}\frac{1}{n-i}\right]$. Next, note that

$\mathbb{E}_{D\backslash\\{z\\}}[f]\quad=\quad\frac{1}{n-1}\sum_{x\in
D\backslash\\{z\\}}f(x)\quad=\quad\frac{n}{n-1}\left[\mathbb{E}_{D}[f]-\frac{f(z)}{n}\right].$
(25)

Applying this above, we obtain

$\begin{split}&\left[\prod_{i=1}^{k}\frac{1}{n-i}\right]\mathbb{E}_{D}\Bigg{[}f_{1}(z_{1})\cdot\Bigg{[}(n-1)^{k-1}\prod_{i=2}^{k}\frac{n}{n-1}\Bigg{[}\mathbb{E}[f_{i}]-\frac{f_{i}(z_{1})}{n}\Bigg{]}\\\
&\quad-(n-1)^{k-2}\sum_{2\leq i\leq j\leq
k}\frac{n}{n-1}\left[\mathbb{E}[f_{i}f_{j}]-\frac{f_{i}(z_{1})f_{j}(z_{1})}{n}\right]\prod_{n\neq
i,j,1}\frac{n}{n-1}\left[\mathbb{E}[f_{i}]-\frac{f_{i}(z_{1})}{n}\right]\Bigg{]}\Bigg{]}\\\
&=\left[\prod_{i=0}^{k}\frac{1}{n-i}\right]\mathbb{E}_{D}\Bigg{[}f_{1}(z_{1})\cdot\Bigg{[}n^{k-1}\prod_{i=2}^{k}\Bigg{[}\mathbb{E}[f_{i}]-\frac{f_{i}(z_{1})}{n}\Bigg{]}\\\
&\qquad\qquad\quad\qquad\qquad-n^{k-2}\sum_{2\leq i\leq j\leq
k}\left[\mathbb{E}[f_{i}f_{j}]-\frac{f_{i}(z_{1})f_{j}(z_{1})}{n}\right]\prod_{h\neq
i,j,1}\left[\mathbb{E}[f_{h}]-\frac{f_{h}(z_{1})}{n}\right]\Bigg{]}\Bigg{]}\end{split}$
(26)

where the average is now taken over $D$. Note that for all $i,j$ it holds

$\begin{split}n^{k-1}\
\frac{f_{i}(z_{1})}{n}\frac{f_{j}(z_{1})}{n}\prod_{h\neq
i,j,1}^{k}\mathbb{E}[f_{h}]\quad=\quad n^{k-2}\
\frac{f_{i}(z_{1})f_{j}(z_{1})}{n}\prod_{h\neq
i,j,1}^{k}\mathbb{E}[f_{h}]\end{split}$ (27)

and the same holds for all the other expectations of products of more
functions. In general, the sign and power of $n$ multiplying all the
expectations of products of $l$ terms is $n^{-l+1}$. Precisely, we obtain

$\begin{split}&\mathbb{E}\left[f_{1}(z_{1})\cdot f_{2}(z_{2})\cdot\ldots\cdot
f_{k}(z_{k})\right]\\\
&\qquad=\left[\prod_{i=0}^{k}\frac{1}{n-i}\right]\mathbb{E}_{D}\Bigg{[}f_{1}(z_{1})\cdot
n^{k}\Bigg{[}\prod_{j>1}\mathbb{E}[f_{j}]-\sum_{i=2}^{k}\frac{f_{i}(z_{1})}{n}\prod_{j\neq
1,i}\mathbb{E}[f_{j}]\\\ &\qquad\qquad\qquad-n^{k-1}\sum_{2\leq
i<j}\Bigg{[}\mathbb{E}[f_{i}f_{j}]\prod_{n\neq
i,j,1}\left[\mathbb{E}[f_{i}]-\frac{f_{i}(z_{1})}{n}\right]\Bigg{]}\ +\
\ldots\Bigg{]}\end{split}$ (28)

That is equal to the usual $\left[\prod_{i=0}^{k}\frac{1}{n-i}\right]$
multiplied by

$\begin{split}&n^{k}\prod_{i=1}^{k}\mathbb{E}[f_{i}]-n^{k-1}\sum_{i\neq
j}\mathbb{E}[f_{i}f_{j}]\prod_{m\neq j,i}\mathbb{E}[f_{m}]+n^{k-2}\sum_{i\neq
j\neq h\neq l}\mathbb{E}[f_{i}f_{j}]\mathbb{E}[f_{h}f_{l}]\prod_{m\neq
j,i,h,l}\mathbb{E}[f_{m}]+\ldots\end{split}$ (29)

This concludes the proof Lemma 15. ∎

######  Remark 17.

When we are taking $z_{i}=z_{j}$ for all the possible $\binom{k}{2}$ couples
(i,j), and multiplying by all picked alone. Then
$\tfrac{1}{2}\cdot\binom{k}{2}\cdot\binom{k-2}{2}$ for the case of two couples
and all the rest alone, etc. When we are taking $m$ terms together, we can
choose them in $\binom{k}{m}$ so the size of the products in which those
appear is much smaller precisely is about the size of the others but we divide
by $n^{m-1}$ instead of $m$ and those are not
$k(k-1)\cdot\ldots\cdot(k-2m+1)/2^{m}$ but at the denominator there is $m!$ so
they are much less and much smaller. We will thus throw them in the error
later.

###  E.3 Corollary for big $n$ and $k$

Our setting is special: we can cancel out some terms because $n,k\gg 1$.
Assume then that we have 3 or more functions $f_{1},f_{2},f_{3},\ldots$. The
terms that multiply the expectation of the product of 3 or more of them, e.g.
$\mathbb{E}_{z\in D}f(z)g(z)h(z)$ in the big sum Lemma 15 can be thrown in the
error part, indeed

$\begin{split}&n^{-2}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)f_{3}(z)\big{]}\prod_{i=4}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\\\ &\quad=\quad O(n^{-1})\ \cdot\
n^{-1}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\prod_{i=3}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\end{split}$ (30)

if $\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)f_{3}(z)\big{]}=O(\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\mathbb{E}_{z\in D}\big{[}f_{3}(z)\big{]})$.
Or analogously

$\begin{split}&\binom{k}{3}n^{-2}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)f_{3}(z)\big{]}\prod_{i=4}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\\\ &\quad=\quad O(k^{-1})\ \cdot\
\binom{k}{4}n^{-2}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\mathbb{E}_{z\in
D}\big{[}f_{3}(z)f_{4}(z)\big{]}\prod_{i=5}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\end{split}$ (31)

if $\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)f_{3}(z)\big{]}=O(\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\mathbb{E}_{z\in
D}\big{[}f_{3}(z)f_{4}(z)\big{]})$.

We can thus conclude with a corollary of Lemma 15 by using this and induction
that

######  Corollary 18 (Corollary of Lemma 15.).

Assume the different averages over the dataset are of the same order, and
$n,k\gg 1$. Then Assume we are in 13 above. Then, when $S$ is sampled as in
Item 1 of 13, the expectation $\mathbb{E}\left[f_{1}(z_{1})\cdot
f_{2}(z_{2})\cdot\ldots\cdot f_{k}(z_{k})\right]$, up to a multiplicative
error of size $O(1/n)$, is equal to $\prod_{i=0}^{k}\frac{n}{n-i}$ multiplied
by

$\begin{split}&\prod_{i=1}^{k}\mathbb{E}[f_{i}]-n^{-1}\sum_{i\neq
j}\mathbb{E}[f_{i}f_{j}]\prod_{m\neq j,i}\mathbb{E}[f_{m}]+n^{-2}\sum_{i\neq
j\neq h\neq l}\mathbb{E}[f_{i}f_{j}]\mathbb{E}[f_{h}f_{l}]\prod_{m\neq
j,i,h,l}\mathbb{E}[f_{m}]+\ldots\end{split}$ (32)

where only the terms in which the expectations of products of up to 2 elements
appear are taken.

###  E.4 Corollary about Covariances

Secondly, note that we can rewrite this in terms of covariances, not of
expectations of products, indeed, for every term we have the analogous

$\begin{split}&n^{-1}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\prod_{i=3}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\ -\ n^{-1}\prod_{i=1}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\\\ &\quad=\quad n^{-1}\operatorname{Cov}_{z\in
D}\big{(}f_{1}(z),f_{2}(z)\big{)}\prod_{i=3}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\end{split}$ (33)

and analogously for a higher number of expectations of products of terms

$\begin{split}&n^{-2}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\mathbb{E}_{z\in
D}\big{[}f_{3}(z)f_{4}(z)\big{]}\prod_{i=5}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\\\ &\ -\ n^{-2}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\prod_{i=3}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\\\ &\quad=\quad n^{-2}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\operatorname{Cov}_{z\in
D}\big{(}f_{3}(z),f_{4}(z)\big{)}\prod_{i=5}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\end{split}$ (34)

and

$\begin{split}&n^{-2}\mathbb{E}_{z\in
D}\big{[}f_{1}(z)f_{2}(z)\big{]}\operatorname{Cov}_{z\in
D}\big{(}f_{3}(z),f_{4}(z)\big{)}\prod_{i=5}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\\\ &\ -\ n^{-2}\operatorname{Cov}_{z\in
D}\big{(}f_{3}(z),f_{4}(z)\big{)}\prod_{i\neq 3,4}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\\\ &\quad=\quad n^{-2}\operatorname{Cov}_{z\in
D}\big{(}f_{1}(z),f_{2}(z)\big{)}\operatorname{Cov}_{z\in
D}\big{(}f_{3}(z),f_{4}(z)\big{)}\prod_{i=5}^{k}\mathbb{E}_{z\in
D}\big{[}f_{i}(z)\big{]}\end{split}$ (35)

This and induction prove that

######  Corollary 19 (Corollary of Lemma 15.).

Assume the different averages over the dataset are of the same order, and
$n,k\gg 1$. Then Assume we are in 13 above. Then, when $S$ is sampled as in
Item 1 of 13, the expectation $\mathbb{E}\left[f_{1}(z_{1})\cdot
f_{2}(z_{2})\cdot\ldots\cdot f_{k}(z_{k})\right]$, up to a multiplicative
error of size $O(1/n)$, is equal to

$\begin{split}&\prod_{i=1}^{k}\mathbb{E}[f_{i}]\ -\ (n-1)^{-1}\sum_{i\neq
j}\operatorname{Cov}(f_{i},f_{j})\prod_{m\neq j,i}\mathbb{E}[f_{m}]\\\
&\quad+\ ((n-1)(n-2))^{-1}\sum_{i\neq j\neq h\neq
l}\operatorname{Cov}(f_{i},f_{j})\operatorname{Cov}(f_{h},f_{l})\prod_{m\neq
j,i,h,l}\mathbb{E}[f_{m}]+\ \ldots\end{split}$ (36)

where only the terms in which the expectations of products of up to 2 elements
appear are taken.

###### Proof of 19..

To conclude the proof just note that the constant

$\prod_{i=0}^{k}\frac{n}{n-i}$

coincides with

$\sum_{i=0}^{k/2}\left[\prod_{j=0}^{i}\binom{k-2j}{2}\right]\big{(}-n^{-1}\big{)}^{i}$

and contains the following terms

$1\ +\ \underbrace{\binom{k}{2}(-n^{-1})}_{\begin{subarray}{c}\text{}\\\
\text{covariances}\end{subarray}}\ +\
\underbrace{\binom{k}{2}\binom{k-2}{2}(-n^{-1})^{2}}_{\begin{subarray}{c}\text{the
double}\\\ \text{covariances}\end{subarray}}\ +\ \ldots$

and for all $i$ there are exactly $\prod_{j=0}^{i}\binom{k-2j}{2}$ terms with
$i$ couples taken together in the expectation, and those terms are multiplied
by $\big{(}-n^{-1}\big{)}^{i}$. ∎

##  Appendix F Expanding in Taylor the Trajectories

###  F.1 Notations

First, we recall the notations from Section 3.1. We denote by
$D=\\{z_{i}\\}_{i=1,2,\ldots,n}\subseteq V$ the training set of size $n$. We
have a parametric loss function $L\colon(\vartheta,z)\mapsto
L(\vartheta,x)\in\mathbb{R}$ that takes as input the parameters
$\theta\in\Theta$ and the data $z\subseteq V$ and outputs a real number,
admitting 3 weak derivatives in the parameters $\vartheta$. For every set
$B\subseteq V$ we define $L(\vartheta,B):=\tfrac{1}{|B|}\sum_{z\in
B}L(\vartheta,z)$. The goal of the optimization procedure is to find a minimum
$\theta^{*}\in\Theta$ for the objective function $L(\vartheta,D)$.

For readability, we will often omit the inputs of the function $L$. Precisely,
whenever we omit the parameter $\vartheta$ we are evaluating the loss at the
beginning of the epoch, we will denote the value of the parameters at the
beginning of the epoch with $\theta$. Whenever we omit the set of inputs we
are evaluating the loss over the whole training set $D$. Moreover, all the
derivatives we will take will be in the parameters $\vartheta$ and all the
expectations will be empirical expectations over a set $B\subseteq V$. As an
example

$L\text{ means }L(\theta,D)\quad\quad\text{and}\quad\quad\nabla L(B)\text{
means }\nabla_{\theta}L(\theta,B).$

Moreover, we will denote by $\theta_{i}^{SGD}$ the parameters after the $i-th$
step of SGD without replacement or, analogously, of Shuffle Once starting from
$\theta_{0}^{SGD}=\theta$ with learning rate $\eta>0$. In this section, we
will take also other algorithms in exam, such as SGD with replacement, GD, or
GD with noise injected. Analogously to SGD without replacement, we will denote
by $\theta_{i}$ the parameters after the $i-th$ step of the other algorithms
in exam, with initialization $\theta_{0}=\theta$ and the learning rate
$\eta>0$.

Let $b\in\mathbb{N}$ be the batch size and $k\in\mathbb{N}$ the number of
optimization steps considered at once. Generally, $k\leq n/b$ will be, and can
be thought of as, the number of batches or the number of steps in an epoch. We
denote by $B_{i}\subseteq D$ the batch used in the $i-th$ step, $i\leq k$.
Denote by $c:=\eta k$ and by
$H:=\frac{c^{2}}{2n}\big{(}\mathbb{E}[(\nabla^{2}L)^{2}]-(\nabla^{2}L)^{2}\big{)}$.
Finally, we denote by $A^{\dagger}$ the Moore-Penrose inverse of the matrix
$A$ and, for a PSD matrix $S$, we denote $\|v\|_{S}^{2}:=v^{\top}Sv$. For a
vector or matrix we denote the components with the indices in subscripts,
e.g., for $A\in\mathbb{R}^{d\times d}$, for $i,j\leq d$, we denote $A_{i,j}$
the $(i,j)$ component of the matrix $A$.

###  F.2 Computing the Deviation between SGD and Big-Learning-Rate GD.

In the following subsections of this section F we prove 9. This is a first
step towards the proof of Theorem 2. Let us write down the difference between
SGD and a GD with different learning rate. Precisely we compare here
$\theta_{k}^{SGD}$, so the parameters after $k$ steps of SGD with learning
rate $\eta$ and batches $B_{1},B_{2},\ldots,B_{k}$ and
$\theta_{1}^{GD,k\eta}$, so the parameters after one step of GD with learning
rate $k\eta$ on the dataset $D_{k}:=\cup_{i=1}^{k}B_{i}$. Precisely, note
that:

$\begin{split}\theta_{k}^{SGD,\eta}-\theta_{1}^{GD,k\eta}\
&=\quad\theta_{k-1}^{SGD,\eta}-\ \eta\nabla
L\big{(}\theta_{k-1}^{SGD,\eta},B_{k}\big{)}\ -\ \theta_{1}^{GD,(k-1)\eta}+\
\eta\nabla L\big{(}\theta,B_{k}\big{)}.\end{split}$ (37)

So defining this deviation $\Delta$ as below, we have that

$\begin{split}\Delta_{k}^{SGD}\quad:&=\quad\theta_{k}^{SGD,\eta}-\theta_{1}^{GD,k\eta}\\\
&=\quad\Delta_{k-1}^{SGD}\quad-\quad\eta\nabla
L\big{(}\theta_{k-1}^{SGD,\eta},B_{k}\big{)}\quad+\quad\eta\nabla
L\big{(}\theta,B_{k}\big{)}.\end{split}$ (38)

Next, expanding in Taylor centered in $\theta$ we have

$\begin{split}\Delta_{k}^{SGD}\quad&=\quad\Delta_{k-1}^{SGD}\quad-\quad\eta\nabla^{2}L\big{(}B_{k}\big{)}\left[\theta_{k-1}^{SGD,\eta}-\theta\right]\quad+\quad\begin{subarray}{c}\text{higher
order}\\\ \text{Taylor rest}\end{subarray}\\\
&=\quad\Delta_{k-1}^{SGD}\quad-\quad\eta\nabla^{2}L\big{(}B_{k}\big{)}\left[\theta_{1}^{GD,(k-1)\eta}-\theta+\Delta_{k-1}^{SGD}\right]\quad+\quad\begin{subarray}{c}\text{higher
order}\\\ \text{Taylor rest}\end{subarray}.\end{split}$ (39)

That is equal to

$\left[I-\eta\nabla^{2}L\big{(}B_{k}\big{)}\right]\Delta_{k-1}^{SGD}\quad+\quad\underbrace{\eta^{2}\nabla^{2}L\big{(}B_{k}\big{)}\left[\sum_{i=1}^{k-1}\nabla
L(B_{i})\right]}_{=\
\theta_{1}^{GD,\eta(k-1)}-\theta}\quad+\quad\begin{subarray}{c}\text{higher
order}\\\ \text{Taylor rest}\end{subarray}.$ (40)

We now consider the lowest order terms, let us define thus
$\alpha_{0}^{SGD}=0$, and for all $k\in\mathbb{N}$ denote
$\alpha_{k}^{SGD}=\left[I-\eta\nabla^{2}L\big{(}B_{k}\big{)}\right]\alpha_{k-1}^{SGD}+\eta^{2}\nabla^{2}L\big{(}B_{k}\big{)}\sum_{i=1}^{k-1}\nabla
L(B_{i})$. Thus we obtain

$\alpha_{k}^{SGD}\quad=\quad\eta^{2}\sum_{i=2}^{k}\left[\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\nabla^{2}L(B_{i})\left[\sum_{j=1}^{i-1}\nabla
L(B_{j})\right]\right].$ (41)

Next note that defining analogously $\alpha_{k}^{GD}$ in the case of
$B_{i}=D$, for all $i$, we have the difference between the GD with small and
big learning rates.

###  F.3 Reorganizing the terms, 1

To conclude this part, the quantity in Eq. 41 can be rewritten as

$\begin{split}&\eta^{2}\sum_{i=2}^{k}\left[\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\nabla^{2}L(B_{i})\left[\sum_{j=1}^{i-1}\nabla
L(B_{j})\right]\right]\\\ &=\quad\eta^{2}\sum_{1\leq i<j\leq
k}\Bigg{[}\sum_{l<k-j}\sum_{\begin{subarray}{c}\text{all the possible}\\\
j<h_{1}<h_{2}<\ldots<h_{l}\leq
k\end{subarray}}\prod_{m=1}^{l}(-\eta\nabla^{2}L(B_{h_{m}}))\Bigg{]}\
\nabla^{2}L(B_{j})\ \nabla L(B_{i}).\end{split}$ (42)

In particular, for all the batches $B_{i}$, in the sum above we have $\nabla
L(B_{i})$ multiplied by any possible product of $k-i-1$ terms that are for all
$j$ all the $I$ or $\nabla^{2}L(B_{j})$. To be precise, all but the product of
all identities. This can be rewritten by grouping starting from $j$ being the
biggest non-identity instead of the smallest one, as

$\begin{split}&\eta^{2}\sum_{1\leq i<j\leq
k}\nabla^{2}L(B_{j})\Bigg{[}\sum_{l<j-i}\sum_{\begin{subarray}{c}\text{all the
possible}\\\
i<h_{1}<h_{2}<\ldots<h_{l}<j\end{subarray}}\prod_{m=1}^{l}(-\eta\nabla^{2}L(B_{h_{m}}))\Bigg{]}\
\nabla L(B_{i})\\\ &=\quad\eta^{2}\sum_{1\leq i<j\leq
k}\nabla^{2}L(B_{j})\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\nabla L(B_{i}).\end{split}$ (43)

###  F.4 Reorganizing the Terms, 2

Thus the quantity above can be rewritten in 3 ways: The first we have seen is
Eq. 41

$\eta^{2}\sum_{i=2}^{k}\left[\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\nabla^{2}L(B_{i})\left[\sum_{j=1}^{i-1}\nabla
L(B_{j})\right]\right].$ (44)

The second is

$\begin{split}\eta^{2}\sum_{1\leq i<j\leq
k}\nabla^{2}L(B_{j})\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\nabla L(B_{i}).\end{split}$ (45)

Finally, let us expand it to products of Hessians instead of
$I-\eta\nabla^{2}L$. Note that we will work on expectation later, any
expectation we will work with does not change with re-ordering, thus every
moment of the quantity above will correspond to moments of

$\begin{split}-\sum_{i=2}^{k}\binom{k}{i}\left[\prod_{j=2}^{i}[-\eta\nabla^{2}L(B_{j})]\right]\
\eta\nabla L(B_{1}).\end{split}$ (46)

All this concludes the proof of 9.

##  Appendix G Proof of Theorem 2 and 12

The first two subsections serve as proof of 12. Later we proceed with the
proof of Theorem 2.

Note, however, that if $D=\\{B_{1},B_{2},\ldots,B_{k}\\}$, by taking $n=k$ and
calling $B_{i}$ every $z_{i}$ in the notations of 13, we obtain the setting of
the already sampled batches. From this point of view 12 is a particular case
of Theorem 3. We will prove just Theorem 3 without loss of generality.

###  G.1 (Step 1) The Summands and the Potential

Note that every summand of 9 is

$\nabla^{2}L(B_{j})\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\nabla L(B_{i}).$ (47)

Moreover, we have one for every $1\leq i<j\leq k$. Note that expanding all the
sums (remembering that $\nabla_{\theta}^{k}L(B)=\frac{1}{|B|}\sum_{z\in
B}\nabla_{\theta}^{k}L(\theta,z)$) we have that

$\begin{split}&\mathbb{E}\left(\nabla^{2}L(B_{j})\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\nabla L(B_{i})\right)\\\
&=\quad\mathbb{E}_{\left[\begin{subarray}{c}z_{i},z_{i+1},\ldots,z_{j}\\\
\text{all
different}\end{subarray}\right]}\left(\nabla_{\theta}^{2}L(z_{j})\left[\prod_{h=i+1}^{j-1}[I-\eta\nabla_{\theta}^{2}L(z_{h})]\right]\nabla_{\theta}L(z_{i})\right)\\\
&=\quad\mathbb{E}_{\left[\begin{subarray}{c}z_{i},z_{i+1},\ldots,z_{j}\\\
\text{all
different}\end{subarray}\right]}\left(\nabla_{\theta}^{2}L(z_{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}i})\left[\prod_{h=i+1}^{j-1}[I-\eta\nabla_{\theta}^{2}L(z_{h})]\right]\nabla_{\theta}L(z_{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}j})\right).\end{split}$
(48)

Where the second equality comes from the fact that we are averaging over the
orders, so the order does not matter. Note that in the line 2 and 3 above we
have the expectation of the elements in line 1 and 2 of LABEL:eq:deriv_1.

##### The Potential.

As in Eq. 11, let us define the function
$V_{i,j}\colon\mathbb{R}^{d}\to\mathbb{R}$ as follows

$\begin{split}V_{i,j}(\theta)\quad:=\quad\left[\nabla_{\theta}L(B_{j})\right]^{\top}\left[\prod_{h=i+1}^{j-1}[I-\eta\nabla_{\theta}^{2}L(B_{h})]\right]\nabla_{\theta}L(B_{i}).\end{split}$
(49)

Note that, analogously as in the paragraph above,
$\mathbb{E}[V_{i,j}(\theta)]$ is the expectation of

$\begin{split}[\nabla_{\theta}L(z_{j})]^{\top}\left[\prod_{h=i+1}^{j-1}[I-\eta\nabla_{\theta}^{2}L(z_{h})]\right]\nabla_{\theta}L(z_{i})\end{split}$
(50)

where $z_{i},z_{i+1},\ldots,z_{j}\in D$ are all different. Note that the
expectation is over a uniform distribution over a finite set, so we can
exchange differentiation in $\theta$ and expectation over $x\in D$. The
derivative in $\theta$ of $\mathbb{E}[V_{i,j}(\theta)]$ as already hinted is

$\begin{split}&\quad\mathbb{E}_{\left[\begin{subarray}{c}z_{i},z_{i+1},\ldots,z_{j}\\\
\text{all
different}\end{subarray}\right]}\left(\nabla_{\theta}^{2}L(z_{j})\left[\prod_{h=i+1}^{j-1}[I-\eta\nabla_{\theta}^{2}L(z_{h})]\right]\nabla_{\theta}L(z_{i})\right)\\\
&+\mathbb{E}_{\left[\begin{subarray}{c}z_{i},z_{i+1},\ldots,z_{j}\\\ \text{all
different}\end{subarray}\right]}\left(\nabla_{\theta}^{2}L(z_{i})\left[\prod_{h=i+1}^{j-1}[I-\eta\nabla_{\theta}^{2}L(z_{h})]\right]\nabla_{\theta}L(z_{j})\right)\\\
&-\mathbb{E}_{\left[\begin{subarray}{c}z_{i},z_{i+1},\ldots,z_{j}\\\ \text{all
different}\end{subarray}\right]}\left(\sum_{h=i+1}^{j-1}[\nabla_{\theta}L(z_{j})]^{\top}\left[\prod_{l=h+1}^{j-1}[I-\eta\nabla_{\theta}^{2}L(z_{l})]\right]\eta\nabla^{3}_{\theta}L(z_{h})\left[\prod_{l=i+1}^{h-1}[I-\eta\nabla_{\theta}^{2}L(z_{l})]\right]\nabla_{\theta}L(z_{i})\right)\end{split}$
(51)

Here the first two lines are simply the same expectation as seen above, and
the second is part of the terms in the sum in Eq. 97. Since for the
expectation the only thing that matters is how many elements we are
multiplying, we can write the expectation of the term in 9 as

$\begin{split}\frac{\eta^{2}}{2}\nabla_{\theta}\left(\sum_{i<j}\mathbb{E}_{\left[\begin{subarray}{c}\text{over
the}\\\ \text{sampling}\\\ \text{of
batches}\end{subarray}\right]}V_{i,j}(\theta)\right)\quad=\quad\frac{\eta^{2}}{2}\nabla_{\theta}\left(\sum_{1<i\leq
k}(k-i+1)\mathbb{E}_{\left[\begin{subarray}{c}\text{over the}\\\
\text{sampling}\\\ \text{of
batches}\end{subarray}\right]}V_{1,i}(\theta)\right)\end{split}$ (52)

minus the term where we exchange every $\nabla L(B_{i})$ with $\nabla L$ and
$\nabla^{2}L(B_{i})$ with $\nabla^{2}L$. This that if the mini-batches add up
to the dataset, every epoch of SGD corresponds to the same number of steps of
GD plus an additional step of the regularizer given by this term, precisely by
observing that

$\begin{split}&\frac{\eta^{2}}{2}\sum_{1\leq i<j\leq k}\nabla
L^{\top}[I-\eta\nabla^{2}L]^{j-i-1}\nabla L(B_{i})\\\
&\quad=\quad\frac{\eta^{2}}{2}\nabla
L^{\top}[\nabla^{2}L]^{2{\dagger}}\big{(}\exp(-\eta k\nabla^{2}L)+\eta
k\nabla^{2}L-I\big{)}\nabla L\end{split}$ (53)

we conclude that

$\begin{split}Reg\quad&=\quad\frac{1}{2}\sum_{1\leq i<j\leq k}\eta\nabla
L(B_{j})^{\top}\Bigg{[}\prod_{h=i+1}^{j-1}[I-\eta\nabla^{2}L(B_{h})]\Bigg{]}\
\eta\nabla L(B_{i})\\\ &\quad-\quad\nabla
L^{\top}[\nabla^{2}L]^{2{\dagger}}\big{(}[I-\eta\nabla^{2}L]^{k}+\eta
k\nabla^{2}L-I\big{)}\nabla L.\end{split}$ (54)

###  G.2 (Step 2) Taking the Expectation of the Regularizer

We compute now the expectations of the step on the regularizer in Eq. 54.
Recall from Eqs. 14, 15, and 36 and from 19 that we can write the expectation
as the non-commutative version of (we copy here the commutative version for
clarity)

$\begin{split}&\prod_{i=1}^{k}\mathbb{E}[f_{i}]\ -\ (n-1)^{-1}\sum_{i\neq
j}\operatorname{Cov}(f_{i},f_{j})\prod_{m\neq j,i}\mathbb{E}[f_{m}]\\\
&\quad+\ ((n-1)(n-2))^{-1}\sum_{i\neq j\neq h\neq
l}\operatorname{Cov}(f_{i},f_{j})\operatorname{Cov}(f_{h},f_{l})\prod_{m\neq
j,i,h,l}\mathbb{E}[f_{m}]+\ \ldots\end{split}$

First, note that the part we are removing due to GD is exactly

$\sum\prod\mathbb{E}[f_{i}]\quad=\quad\underbrace{\nabla
L^{\top}[\nabla^{2}L]^{2{\dagger}}\big{(}\exp(-\eta k\nabla^{2}L)+\eta
k\nabla^{2}L-I\big{)}\nabla L}_{\text{GD part}}$

because the expectation of every derivative is the full-batch derivative.
Let’s analyze the step on the regularizer in the form Eq. 46. Precisely, we
have to compute the following expectation

$-\ \mathbb{E}_{\left[\begin{subarray}{c}B_{1},B_{2},\ldots,B_{z}\\\ \text{all
disjoint}\end{subarray}\right]}\left[\sum_{i=2}^{k}\binom{k}{i}\left[\prod_{j=2}^{i}[-\eta\nabla^{2}L(B_{j})]\right]\
\eta\nabla L(B_{1})\right].$ (55)

Where $f_{1}=\nabla L$ and $f_{i}=-\eta\nabla^{2}L$ for all $i>1$. We split
this sum into 2 parts.

  1. (i)

The terms in which $f_{1}$ and $f_{i}$ are taken together in the covariances.
Here, every summand of the quantity above can be rewritten as

$\begin{split}&\mathbb{E}_{B_{1}\subseteq
D}\Bigg{[}\mathbb{E}_{\left[\begin{subarray}{c}B_{2},\ldots,B_{j-1},B_{j+1},\ldots,B_{i}\\\
\text{all disjoing}\\\ \text{and disjoint from
}B_{1}\end{subarray}\right]}\Bigg{[}\sum_{j=2}^{i}\left[\prod_{h=j+1}^{i}[-\eta\nabla^{2}L(B_{j})]\right]\eta\nabla^{2}L(B_{1})\\\
&\qquad\quad\cdot\left[\prod_{h=2}^{j-1}[-\eta\nabla^{2}L(B_{j})]\right]\
\eta\nabla L(B_{1})\Bigg{]}\Bigg{]}\quad-\quad\ldots.\end{split}$ (56)

We will better analyze this term in what follows.

  2. (ii)

The terms in which $f_{1}$, appear alone (so we have $\mathbb{E}_{z\in
D}[f_{1}(z)]$ appearing in the formula are terms in which figures the
covariance of at least 2 Hessians. These terms disappear around a stationary
point, as $\mathbb{E}_{z\in D}[f_{1}(z)]=\eta\nabla L\sim 0$ there.

$\begin{split}&-\ \mathbb{E}_{\left[\begin{subarray}{c}z_{2},\ldots,z_{i}\\\
\text{all
different}\end{subarray}\right]}\left[\sum_{i=2}^{k}\binom{k}{i}\left[\prod_{j=2}^{i}[-\eta\nabla^{2}L(B_{j})]\right]\right]\
\cdot\ \eta\nabla L.\end{split}$ (57)

###  G.3 (Step 3) Summing up.

The term in item (i) above can be rewritten as follows

$\begin{split}&\mathbb{E}_{z_{1}\in
D}\Bigg{[}\mathbb{E}_{\left[\begin{subarray}{c}z_{2},\ldots,z_{j-1},z_{j+1},\ldots,z_{i}\\\
\text{all different in
}D\end{subarray}\right]}\Bigg{[}\sum_{i=2}^{k}\binom{k}{i}\sum_{j=2}^{i}\left[\prod_{h=j+1}^{i}[-\eta\nabla^{2}L(B_{j})]\right]\eta\nabla^{2}L(B_{1})\\\
&\qquad\quad\cdot\left[\prod_{h=2}^{j-1}[-\eta\nabla^{2}L(B_{j})]\right]\
\eta\nabla L(B_{1})\Bigg{]}\Bigg{]}\quad-\quad\ldots.\end{split}$ (58)

We can rewrite the quantity above as follows

$\begin{split}&\sum_{i=2}^{k}\binom{k}{i}\sum_{j=2}^{i}\mathbb{E}_{\left[\begin{subarray}{c}z_{j+1},\ldots,z_{i}\\\
\text{all different in
}D\end{subarray}\right]}\left[\prod_{h=j+1}^{i}[-\eta\nabla^{2}L(B_{j})]\right]\mathbb{E}_{z_{1}\in
D}\Bigg{[}\eta\nabla^{2}L(B_{1})\\\
&\qquad\quad\cdot\mathbb{E}_{\left[\begin{subarray}{c}z_{2},\ldots,z_{j-1}\\\
\text{all different in
}D\end{subarray}\right]}\left[\prod_{h=2}^{j-1}[-\eta\nabla^{2}L(B_{j})]\right]\
\eta\nabla L(B_{1})\Bigg{]}\quad-\quad\ldots.\end{split}$ (59)

By observing that

$\operatorname{Cov}_{z\in D}(\nabla^{2}L(z),\nabla
L(z))\quad=\quad\frac{1}{2}\nabla\mathbb{E}_{z\in D}[\|\nabla L(z)-L\|^{2}]$

We can reorganize the terms as follows

$\begin{split}Reg\ step\ =\
-\frac{c}{n-k}\nabla_{\theta}\sum_{i=0}^{k-2}\mathbb{E}_{\left[\begin{subarray}{c}z_{1},\ldots,z_{i}\\\
\text{all different in
}D\end{subarray}\right]}\left[\prod_{j=1}^{i}[-\eta\nabla^{2}L(B_{j})]\right]\operatorname{\mathbb{V}ar}_{z\in
D}(\|\nabla L(z)-\nabla L\|^{2}_{S_{i}})\end{split}$ (60)

where $S_{i}$ is defined as

$S_{i}\quad:=\quad\frac{\eta^{2}}{2c}\sum_{j=0}^{k-i-2}\binom{k}{i+2}\mathbb{E}_{\left[\begin{subarray}{c}z_{1},\ldots,z_{j}\\\
\text{all different in
}D\end{subarray}\right]}\left[\prod_{j=1}^{k-i-2}[-\eta\nabla^{2}L(B_{j})]\right]$

Precisely, the part $\prod_{i}\mathbb{E}_{z\in D}[f_{i}(z)]$ in the notations
of 19 of this quantity is

$S_{i}\quad=\quad\frac{\eta^{2}}{2c}[-\eta\nabla^{2}L]^{-i-2}\left([I-\eta\nabla^{2}L]^{k}-\sum_{j=0}^{i+1}\binom{k}{j}(-\eta\nabla^{2}L)^{j}\right).$

This means that around stationary points and in the case in which
$\mathbb{E}[(\eta\nabla^{2}L)^{2}]-\mathbb{E}[\eta\nabla^{2}L]^{2}\ll n$
(usually as they are $O(1)$ ) We have

$Reg\ step\quad=\quad-\frac{\eta}{b-1}\
\nabla_{\theta}\sum_{i=0}^{k-2}(-\eta\nabla^{2}L)^{i}\operatorname{\mathbb{V}ar}_{z\in
D}(\|\nabla L(z)-\nabla L\|^{2}_{S_{i}}).$ (61)

###  G.4 (Step 4) The Size of the Step Given the Hessian

Note that in the case in which
$\mathbb{E}[(\eta\nabla^{2}L)^{2}]-\mathbb{E}[\eta\nabla^{2}L]^{2}\ll n$, that
happens often as usually as they are $O(1)$

$\begin{split}S_{i}\quad&=\quad\frac{\eta^{2}}{2c}[-\eta\nabla^{2}L]^{-i-2}\left([I-\eta\nabla^{2}L]^{k}-\sum_{j=0}^{i+1}\binom{k}{j}(-\eta\nabla^{2}L)^{j}\right)\\\
&=\quad\frac{\eta^{2}}{2c}\sum_{j=i+2}^{k}\binom{k}{j}(-\eta\nabla^{2}L)^{j-i-2}\end{split}$
(62)

This matrix is a function of the Hessian and on the span of eigenvectors of
the eigenvalue $\lambda$ of the Hessian, $S_{i}$ takes the following values
approximately

$S_{i}\quad=\quad\frac{\eta^{2}}{2c}\begin{cases}\binom{k}{i+2}-\binom{k}{i+3}\eta\lambda\qquad&\text{
when }|c\lambda|\ll 1\\\
\binom{k}{i+1}(\eta\lambda)^{-1}-\binom{k}{i}(\eta\lambda)^{-2}+\ldots&\text{
when }c\lambda\gg 0\\\ (-\eta\lambda)^{-i-2}\exp(-c\lambda)&\text{ when
}c\lambda\ll 0\end{cases}$ (63)

This concludes the proof of Theorem 2.

##  Appendix H A Deeper Look into $S_{0}$ of Theorem 2

Our goal in the rest of this section is to describe the nature of this
regularizer and in particular the role of the matrices $S_{i}$, $i\leq k-2$,
in driving qualitatively different behaviors between SGD with and without
replacement.

Recall from §3.1 that $c:=\eta k$ and
$H:=\frac{c^{2}}{2n}\big{(}\mathbb{E}[(\nabla^{2}L)^{2}]-(\nabla^{2}L)^{2}\big{)}$.

######  Proposition 20 (What $S_{i}$ is).

In the setting of Theorem 2 we have that $S_{i}$ approximately share
eigenspaces with $\nabla^{2}L$. More precisely,

$S_{i}\ =\
\frac{\eta^{2}}{2c}\sum_{j=i+2}^{k}\binom{k}{j}[-\eta\nabla^{2}L]^{j-i-2}\ =\
\frac{\eta^{2}}{2c}[-\eta\nabla^{2}L]^{-i-2}\left([I-\eta\nabla^{2}L]^{k}-\sum_{j=0}^{i-1}\binom{k}{j}[-\eta\nabla^{2}L]^{j}\right).$

Thus, on the eigenspace of the eigenvector $\lambda$ of the Hessian, we have
that

$S_{0}\quad\sim\quad\begin{cases}\frac{c}{4}H^{-1/2}\sqrt{\pi}\
\mathrm{erf}(\sqrt{H})\left(2+2H^{-1/2}(e^{-H}-1)-c\lambda\right)&\text{if
}c\lambda\text{ small}\\\ (2\lambda)^{-1}\qquad&\text{if }c\lambda>>0\\\
\tfrac{1}{2\lambda^{2}}\exp(-c\lambda)\left(e^{-H}-4H/c\lambda\right)\qquad&\text{if
}c\lambda<<0\end{cases}$ (64)

In particular, when $c\lambda$ is small we have up to $O(c^{2}\lambda^{2})$
that

$S_{0}\quad\sim\quad\frac{c}{4}\cdot\begin{cases}1-\frac{1}{3}c\lambda-\frac{1}{6}H+\frac{1}{10}c\lambda
H+\frac{1}{30}H^{2}-\frac{1}{42}c\lambda H^{2}&\text{if }H\text{ small}\\\
H^{-1}\exp(-H)\left(2H^{-1}-c\lambda\right)&\text{if }H\text{ big}\end{cases}$
(65)

and for $H\ll 1$ we have up to $O(H)$ approximately

$cS_{i}\quad\sim\quad\frac{1}{2}\begin{cases}\binom{k}{i+2}-\binom{k}{i+3}\eta\lambda&\text{if
}c\lambda\text{ small}\\\ \lambda^{-1}\qquad&\text{if }c\lambda>>0\\\
\lambda^{-2}\exp(-c\lambda)\qquad&\text{if }c\lambda<<0\end{cases}$ (66)

In addition, $\mathcal{S}_{i}$ in Theorem 2 is approximately the following

$\mathcal{S}_{i}\ =\ [I-\eta\nabla^{2}L]^{2{\dagger}}HS_{i}.$

Moreover, the non-diagonal part of $S_{i}$ only depends on $H$ so in
particular, if $\|H\|\ll 1$ then $S_{i}$ is essentially diagonal and
precisely, if $\lambda_{1},\lambda_{2},\ldots,\lambda_{p}$ are the eigenvalues
of $\nabla^{2}L=diag(\lambda_{1},\lambda_{2},\ldots,\lambda_{p})$ we have that

$S_{i}\quad=\quad
diag\big{(}f_{i}(\lambda_{1}),f_{i}(\lambda_{2}),\ldots,f_{i}(\lambda_{p})\big{)}\quad+\
O(H)$

with

$f_{i}(\lambda)\quad=\quad\tfrac{1}{2}\lambda^{-2}\left([1-\eta\lambda]^{k}-\sum_{j=0}^{i+1}\binom{k}{j}(-\eta\lambda)^{j}\right)\quad\cdot\quad\big{(}1+O(1/k)\big{)},$

or analogously

$f_{i}(\lambda)\quad=\quad\tfrac{1}{2}\sum_{j=i+2}^{k}\binom{k}{j}(-\eta\lambda)^{j-2}\quad\cdot\quad\big{(}1+O(1/k)\big{)},$

#####  $S_{0}$ and the small Hassian regime.

Note that $S_{0}$ Theorem 2 is

$\sum_{i=2}^{k}(k-i+1)\mathbb{E}_{\left[\begin{subarray}{c}z_{2},\ldots,z_{i-1}\\\
\text{all
different}\end{subarray}\right]}\left[\prod_{h=2}^{i-1}[I-\eta\nabla_{\theta}^{2}L(z_{h})]\right]$

Again using the Eqs. 14, 15, and 16 we can write the expectation as the non-
commutative version of (we write here the commutative version for clarity)
$\prod_{j=1}^{i-1}\left[1+\frac{j}{n-j}\right]$ that multiplies

$\begin{split}&[I-\eta\nabla^{2}L]^{i-2}-n^{-1}\binom{i-2}{2}\big{(}\mathbb{E}[(I-\eta\nabla^{2}L)^{2}]-\mathbb{E}[I-\eta\nabla^{2}L]^{2}\big{)}[I-\eta\nabla^{2}L]^{i-4}+\ldots\end{split}$

So calling $X:=\mathbb{E}[(\nabla^{2}L)^{2}]-\mathbb{E}[\nabla^{2}L]^{2}$, and
$Y:=I-\eta\nabla^{2}L$ we have

$\begin{split}&Y^{i-2}-\eta^{2}n^{-1}\binom{i-2}{2}XY^{i-4}+\eta^{4}n^{-2}\tfrac{1}{2}\binom{i-2}{2}\binom{i-4}{2}X^{2}Y^{i-6}+\ldots\end{split}$
(67)

Precisely, it is

$\begin{split}&Y^{i-2}-\eta^{2}n^{-1}\bigg{(}XY^{i-4}+YXY^{i-3}+Y^{2}XY^{i-2}+\ldots+\eta^{2}\tilde{X}Y^{i-3}+\ldots\end{split}$
(68)

and so on. We can anyways count how many terms of every kind we have,
precisely in the commutative case

$\begin{split}&S_{0}\quad=\quad\frac{\eta}{2k}\sum_{i=2}^{k}(k-i+1)\Bigg{(}Y^{i-2}-\eta^{2}n^{-1}\binom{i-2}{2}XY^{i-4}+\ldots\Bigg{)}\end{split}$
(69)

##### When $H\ll 1$.

Then we can consider And $\tilde{Y}:=\sum_{i=2}^{k}(k-i+1)Y^{i-2}$ is

$\sum_{i=2}^{k}(k-i+1)Y^{i-2}\quad=\quad\frac{-I+k-kY+Y^{k}}{(Y-I)^{2}}\quad=\quad\frac{[I-\eta\nabla^{2}L]^{k}+\eta
k\nabla^{2}L-I}{\eta^{2}[\nabla^{2}L]^{2}}$

That on the eigenspace of $\lambda$ eigenvalue of the Hessian, for $\eta k=c$
this is about

$\frac{\exp(-c\lambda)+c\lambda-I}{\eta^{2}\lambda^{2}}$ (70)

And if we expand in Taylor the exponential, we obtain, agreeing with [Smith et
al., 2021], that

$\frac{I-c\lambda+\tfrac{c^{2}\lambda^{2}}{2}-\tfrac{c^{3}\lambda^{3}}{6}+\frac{c^{4}\lambda^{4}}{24}+c\lambda-I}{\lambda^{2}}\quad=\quad\frac{c^{2}}{2}\
-\ \frac{c^{3}\lambda}{6}\ +\ \frac{c^{4}\lambda^{2}}{24}$

In particular,

$\eta^{2}\tilde{Y}\quad\sim\quad\begin{cases}\exp(-c\lambda)\qquad&\text{if
}c\lambda<<0\\\ \frac{c^{2}}{2}\ -\ \frac{c^{3}\lambda}{6}&\text{if
}c\lambda\sim 0\\\ c\lambda^{-1}&\text{if }c\lambda>>0\\\ \end{cases}$ (71)

##### When $c\lambda<<1$, whatever $X/n$.

Now regarding the terms with also $X$, we have that in the case of commutation
the sum is

$\eta^{4}X\frac{1}{n}\sum_{i=4}^{k}(k-i+1)\binom{i-2}{2}Y^{i-4}$

That happens to be, if $\eta\lambda<<1$

$\frac{\eta^{4}}{n}\binom{k}{4}X$

and otherwise

$\begin{split}&\frac{1}{n}X\lambda^{-4}\left(-3+c\lambda+\tfrac{1}{2}(1-\eta\lambda)^{k-2}[c^{2}\lambda^{2}-5\eta
c\lambda^{2}+4c\lambda+6\eta^{2}\lambda^{2}-12\eta\lambda+6]\right)\end{split}$
(72)

This, when $\eta\lambda<<1$ is

$\begin{split}&\frac{1}{n}\lambda^{-4}X\left(-3+c\lambda+\tfrac{1}{2}\exp(-c\lambda)[(c\lambda+2)^{2}+2]\right)\\\
&=\quad\frac{1}{n}X\left(\frac{c^{4}}{24}\ -\ \frac{c^{5}\lambda}{40}\ +\
\frac{c^{6}\lambda^{2}}{120}\ +\
O\big{(}c^{2i}\lambda^{i-2}/i!\big{)}\right)\end{split}$ (73)

We can here compute the size of this term as for $\tilde{Y}$. precisely the
size is

$\frac{1}{n}\left(\mathbb{E}[(\nabla^{2}L)^{2}]-\mathbb{E}[\nabla^{2}L]^{2}\right)\quad\times\quad\begin{cases}>\exp(-c\lambda)\qquad&\text{if
}\lambda<<0\\\ \frac{c^{4}}{4!}\ -\ \frac{3c^{5}\lambda}{5!}\ +\
\frac{5c^{6}\lambda^{2}}{6!}&\text{if }\lambda\sim 0\\\
<c\lambda^{-3}&\text{if }\lambda>>0\\\ \end{cases}$ (74)

More generally,

the term that multiply the $X^{i}$s are:

$\eta^{4}\sum_{i=2}^{k}(k-i+1)(I-\eta\lambda)^{i-2}\quad=\quad\frac{c^{2}}{2}\
-\ \frac{c^{3}\lambda}{6}\ +\ O(\lambda^{2})$

that is equal to

$\lambda^{-2}\left(\exp(-c\lambda)+c\lambda-1\right)$

for $i=0$. Recall $H:=\frac{c^{2}}{2n}X$, then the sum above is

$\eta^{4}\sum_{i=4}^{k}(k-i+1)\frac{(i-2)!}{(i-4)!\cdot
2}(I-\eta\lambda)^{i-4}\frac{X}{n}\quad=\quad\frac{c^{2}}{12}H\ -\
\frac{c^{3}\lambda}{20}H\ +\ O(\lambda^{2}H)$

that is equal to

$\lambda^{-4}H\left(-3+c\lambda+\tfrac{1}{2}\exp(-c\lambda)[c^{2}\lambda^{2}+4c\lambda+6]\right)$

for $i=1$, this

$\eta^{6}\sum_{i=6}^{k}(k-i+1)\frac{(i-2)!}{(i-6)!\cdot
8}(I-\eta\lambda)^{i-6}\frac{X^{2}}{n^{2}}\quad=\quad\frac{c^{2}}{60}H^{2}\ -\
\frac{c^{3}\lambda}{84}H^{2}\ +\ O(\lambda^{2}H^{2})$

that is equal to

$\lambda^{-6}H^{2}\left(-15+3c\lambda+\exp(-c\lambda)(15+12c\lambda+4.5c^{2}\lambda^{2}+c^{3}\lambda^{3}+c^{4}\lambda^{4}/8)\right)$

for $i=2$, this

$\eta^{8}\sum_{i=8}^{k}(k-i+1)\frac{(i-2)!}{(i-8)!\cdot 6\cdot
8}(I-\eta\lambda)^{i-8}\frac{X^{3}}{n^{3}}\quad=\quad\frac{c^{2}}{336}H^{3}\
-\ \frac{c^{3}\lambda}{432}H^{3}\ +\ O(\lambda^{2}H^{3})$

that is equal to

$\lambda^{-8}H^{3}\left(-105+15c\lambda+\exp(-c\lambda)\big{(}105+90c\lambda+\tfrac{75}{2}c^{2}\lambda^{2}+\ldots+c^{5}\lambda^{5}/4+c^{6}\lambda^{6}/48\big{)})\right)$

for $i=3$, and so on.

Thus we have that for $\lambda<<1$ or $\eta<<1$, the zeroth order in $\lambda$
of $S_{0}$ is:

$\frac{c^{2}}{2}\left(1-\frac{1}{6}H+\frac{1}{30}H^{2}-\frac{1}{168}H^{3}+\ldots\right).$

Here, at the denominators we have $(n+1)!\cdot(2n+1)$ that is OEIS A175925. So
we have

$\frac{c^{2}}{2}\sum_{m=0}^{k/2-1}\frac{1}{(m+1)!(2m+1)}(-H)^{m}\quad\sim\quad\frac{c^{2}}{2}H^{-1}\big{(}\sqrt{\pi
H}\ \mathrm{erf}(\sqrt{H})+e^{-H}-1\big{)}$

That for $H\to\infty$ goes to 0 as

$\frac{c^{2}}{2}\left(H^{-2}+O(H^{-3})\right)\ e^{-H}.$

The first order in $\lambda$ instead is $-c\lambda$ that multiplies

$\frac{c^{2}}{2}\left(\frac{1}{3}-\frac{1}{10}H+\frac{1}{42}H^{2}-\frac{1}{216}H^{3}+\ldots\right)$

precisely $-c\lambda$ that multiplies terms that at the denominator have
$n!\cdot(2n+1)$, that is OEIS A007680, precisely

$-c\lambda\frac{c^{2}}{2}\sum_{m=0}^{k/2-1}\frac{1}{m!(2m+1)}(-H)^{m}\quad\sim\quad-\frac{c^{3}\lambda}{4}\sqrt{\pi}H^{-1/2}\
\mathrm{erf}\\!\left(\sqrt{H}\right)$

That for $H\to\infty$ goes to 0 as

$-\frac{c^{3}\lambda}{4}\left(H^{-1}+O(H^{-2})\right)\ e^{-H}.$

Thus we can conclude that for $c\lambda<<1$, by recalling
$H:=\frac{c^{2}}{2n}X$ we have

$S\quad=\quad\frac{c}{4}\cdot\begin{cases}1-\frac{1}{3}c\lambda-\frac{1}{6}H+\frac{1}{10}c\lambda
H+\frac{1}{30}H^{2}-\frac{1}{42}c\lambda H^{2}&\text{if }H\text{ small}\\\
H^{-1}\exp(-H)\left(2H^{-1}-c\lambda\right)&\text{if }H\text{ big}\end{cases}$
(75)

and in general

$S\quad=\quad\frac{c}{4}H^{-1/2}\sqrt{\pi}\
\mathrm{erf}(\sqrt{H})\left(2+2H^{-1/2}(e^{-H}-1)-c\lambda\right)$ (76)

with an error of $O(c^{2}\lambda^{2})$.

##### If $c\lambda\neq 0$.

We sum all the elements in Eq. 69 multiplied by $X$ alone, then all the ones
by $X^{2}$ alone, then all the ones by all the other possible expectations of
products, and so on. All these sums are sums of powers of $\lambda$, precisely
all of them, as Eqs. 70 and 62 are a negative power of $\lambda$ multiplied by
some polynomial terms in $c\lambda$, usually a term that is $O(1)$ and one
that is $O(c\lambda)$, and another one that is
$O(\max\\{c^{i}\lambda^{i},1\\})\exp(-c\lambda)$. Precisely, all these terms
for $i\geq 1$ are $[-X/n]^{i}$ multiplied by

$\lambda^{-2i-2}\left(-a_{i}+b_{i}\cdot
c\lambda+\exp(-c\lambda)\left(a_{i}+(a_{i}-b_{i})c\lambda+O(c^{2}\lambda^{2}+c^{2i-2}\lambda^{2i-2})+\frac{c^{2i}\lambda^{2i}}{2^{i}i!}\right)\right)$
(77)

where

$a_{i}=(2i+1)!!\quad\text{and}\quad b_{i}=(2i-1)!!.$

##### If $\lambda<<0$.

This and the equation in Eq. 70 imply $\lambda<<0$ we have the exponential in
$\lambda$ that governs the terms. Moreover, since $\lambda^{2}>>1$, we have
that the biggest terms are the ones divided by $\lambda^{2}$ to a smaller
exponent. Recall that $H:=c^{2}X/2n$, and noting that generally $X/n=O(1/n)$.
So in this case $2H/c^{2}\lambda^{2}=X/\lambda^{2}n=O(\lambda^{2}n)^{-1}\ll
1$. We obtain that all the terms that sum the exponential have size smaller
than the last one. So in particular the size of $S_{0}$ in that direction is
about

$\lambda^{-2}\exp(-c\lambda)\left(1+\sum_{i=1}a_{i}\left[\frac{-H}{c^{2}\lambda^{2}}\right]^{i}+c\lambda(a_{i}-b_{i})\left[\frac{-H}{c^{2}\lambda^{2}}\right]^{i}+\ldots+\frac{(-H)^{i}}{i!}\right)$
(78)

that is

$\lambda^{-2}\exp(-c\lambda)\left(e^{-H}-6(c\lambda)^{-2}H-4(c\lambda)^{-1}H+O(H^{2}/\lambda)\right)$
(79)

and can be rewritten

$\lambda^{-2}\exp(-c\lambda)\left(e^{-H}-4(c\lambda)^{-1}H+O(H^{2}/c\lambda)\right).$
(80)

##### If $\lambda>>0$.

Analogously in this case, the term that governs the quantity is

$\lambda^{-2i-2}(-a_{i}+c\lambda b_{i})[-X/n]^{i}$

as the exponential eats all the other terms. Thus we have the following series

$\lambda^{-2}\sum_{i=0}^{k/2-1}-a_{i}\left[\frac{-H}{c^{2}\lambda^{2}}\right]^{i}+c\lambda
b_{i}\left[\frac{-H}{c^{2}\lambda^{2}}\right]^{i}$ (81)

And unlike the previous one, the biggest terms in the case in which
$\lambda>>0$ remain

$\frac{c}{\lambda}+O(\lambda^{-2})$

where the error is always negative and so in particular it is
$<\frac{c}{\lambda}$. This concludes the proof.

##  Appendix I The Whole Regularizer: Theorem 3

Assume $H\ll 1$. We proved that every epoch SGD without replacement, in
expectation is GD plus one additional step on a regularizer in Eq. 61. Let us
now rewrite everything in an orthonormal basis of eigenvectors for the
Hessian. We have that the update on $\theta_{i}$ eigenvector of the $i$-th
eigenvalue $\lambda_{i}$ of the Hessian $\nabla^{2}L$ is

$-\frac{\eta}{b-1}\sum_{j=0}^{k-2}(-\eta\lambda_{i})^{j}\
\nabla_{\theta_{i}}\operatorname{\mathbb{V}ar}_{z\in D}(\|\nabla L(z)-\nabla
L\|^{2}_{S_{j}}).$

Or analogously up to terms in the approximation error

$\begin{split}-\frac{\eta}{b-1}\sum_{j=0}^{k-2}(-\eta\lambda_{i})^{j}\text{trace}\big{(}S_{j}\cdot\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))\big{)}.\end{split}$ (82)

Next note that we proved that $S_{j}$ is approximately simultaneously
diagonalizable with $\nabla^{2}L$, so in this basis it is diagonal and on the
$i-th$ element of the diagonal it is

$\frac{\eta^{2}}{2c}\sum_{l=j+2}^{k}\binom{k}{l}(-\eta\lambda_{i})^{l-j-2}$

that approximately corresponds to

$S_{j}[i,i]=\frac{\eta^{2}}{2c}\begin{cases}\binom{k}{j+2}-\binom{k}{j+3}\eta\lambda_{i}&\text{if
}c\lambda_{i}\ll 1\\\
\frac{[1-\eta\lambda_{i}]^{k}}{-\eta\lambda_{i}^{j+2}}+\binom{k}{j+1}(\eta\lambda_{i})^{-1}&\text{if
}c\lambda_{i}\gg 1\end{cases}.$

By expanding the trace as a sum over the eigenvalues
$\lambda_{1},\lambda_{2},\ldots,\lambda_{l},\ldots$ of $\nabla^{2}L$, along
the direction $\theta_{i}$ we can rewrite our steps as

$\begin{split}&-\frac{\eta}{b-1}\sum_{l}\sum_{j=0}^{k-2}(-\eta\lambda_{i})^{j}S_{j}[l,l]\cdot\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}\\\
&=\quad-\frac{\eta}{b-1}\frac{\eta^{2}}{2c}\sum_{l}\sum_{j=0}^{k-2}(-\eta\lambda_{i})^{j}\sum_{h=j+2}^{k}\binom{k}{h}(-\eta\lambda_{l})^{h-j-2}\cdot\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}.\end{split}$ (83)

This concludes the proof of Theorem 3 by calling $R_{i,j}$ all the terms that
multiply the derivative of the covariance. Now we compute the size of the
elements $R_{i,j}$.

Then when $l\neq i$ and $c\lambda_{l}\ll 1$, is:

$\begin{split}&-\frac{\eta}{b-1}\frac{\eta^{2}}{2c}\sum_{l}\sum_{j=0}^{k-2}\binom{k}{j+2}(-\eta\lambda_{i})^{j}\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}.\end{split}$ (84)

Thus the sum of these terms for $l\neq i$ coincides with

$\begin{split}&-\frac{\eta}{b-1}\frac{c}{2}[c\nabla^{2}L]^{2{\dagger}}\big{(}[I-\eta\nabla^{2}L]^{k}+c\nabla^{2}L-I\big{)}\frac{d}{d\theta_{i}}trace(\operatorname{Cov}_{z\in
D}(\nabla L(z))).\end{split}$ (85)

While when $l\neq i$, $c\lambda_{l}\gg 1$ we approximately obtain

$\begin{split}&-\frac{\eta}{b-1}\frac{\eta^{2}}{2c}\sum_{l}\sum_{j=0}^{k-2}\binom{k}{j+1}(-\eta\lambda_{i})^{j}(\eta\lambda_{l})^{-1}\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}.\end{split}$ (86)

Thus the sum of these terms for $l\neq i$ coincides with

$\begin{split}-\frac{\eta}{b-1}c[c\nabla^{2}L]^{{\dagger}}\big{(}[I-\eta\nabla^{2}L]^{k}-I-[-\eta\nabla^{2}L]^{k}\big{)}trace\left([2c\nabla^{2}L]^{\dagger}\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))\right).\end{split}$ (87)

Instead, the term $l=i$ is the following

$\begin{split}&-\frac{\eta}{b-1}\frac{\eta^{2}}{2c}\sum_{j=0}^{k-2}(-\eta\lambda_{i})^{j}\sum_{h=j+2}^{k}\binom{k}{h}(-\eta\lambda_{i})^{h-j-2}\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{i,i}\\\
&=-\frac{\eta}{b-1}\frac{\eta^{2}}{2c}\sum_{j=2}^{k}(k-j+1)\binom{k}{j}(-\eta\lambda_{i})^{j-2}\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{i,i}\\\
&=-\frac{\eta}{b-1}\left[\frac{d}{d\theta_{i}}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{i,i}\right]\cdot\begin{cases}\tfrac{c}{4}&\text{if
}c\lambda_{i}\ll 1\\\
\left(\frac{k}{2c\lambda_{i}^{2}}+\frac{1}{2\lambda_{i}}\right)[1-\eta\lambda_{i}]^{k}&\text{if
}c\lambda_{i}=O(\eta^{-1})\end{cases}\end{split}$ (88)

We can thus conclude that the step on the regularizer along the direction
$\theta_{i}$ is $-\eta/(b-1)$ times the derivative along $\theta_{i}$ of the
quantity

$\sum_{j=0}^{k-2}(-\eta\lambda_{i})^{j}\underbrace{\frac{\eta^{2}}{2c}\sum_{\begin{subarray}{c}\lambda_{l}\text{
eigen-}\\\ \text{value of
}\nabla^{2}L\end{subarray}}\sum_{h=j+2}^{k}\binom{k}{h}(-\eta\lambda)^{h-j-2}\cdot\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}}_{\text{trace of }S_{j}\cdot\operatorname{Cov}_{z\in
D}(\nabla L(z))}.$ (89)

This can be rewritten as

$\begin{split}Reg_{i}\quad&=\quad
c(c\lambda_{i})^{-2}\big{(}[I-\eta\lambda_{i}]^{k}+c\lambda_{i}-I\big{)}\sum_{\begin{subarray}{c}\lambda_{l}\neq\lambda_{i}\text{
small}\\\ \text{eigenvalue}\\\ \text{of
}\nabla^{2}L\end{subarray}}\\!\\!\\!\\!\operatorname{Cov}_{z\in D}(\nabla
L(z))_{l,l}\\\\[5.69046pt] &\quad+\
c(c\lambda_{i})^{-1}\big{(}[I-\eta\lambda_{i}]^{k}-I-[-\eta\lambda_{i}]^{k}\big{)}\sum_{\begin{subarray}{c}\lambda_{l}\neq\lambda_{i}\text{
big}\\\ \text{eigenvalue}\\\ \text{of
}\nabla^{2}L\end{subarray}}\\!\\!\\!\\!(c\lambda_{l})^{-1}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}\\\\[5.69046pt] &\quad+\
c(c\lambda_{i})^{-1}\big{(}(k-1)[I-\eta\lambda_{i}]^{k}-c\lambda_{i}[I-\eta\lambda_{i}]^{k}+ck\lambda_{i}-(k-1)\big{)}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{i,i}\end{split}$ (90)

Thus on the small eigenvalues $|c\lambda|\ll 1$ we approximately have the
following regularizer

$\begin{split}Reg_{i}\quad&=\quad\frac{c}{4}\sum_{\begin{subarray}{c}\lambda_{l}\text{
small}\\\ \text{eigenvalue}\\\ \text{of
}\nabla^{2}L\end{subarray}}\\!\\!\\!\\!\operatorname{Cov}_{z\in D}(\nabla
L(z))_{l,l}\ +\ \sum_{\begin{subarray}{c}\lambda_{l}\text{ big}\\\
\text{eigenvalue}\\\ \text{of
}\nabla^{2}L\end{subarray}}\\!\\!\\!\\!(c\lambda_{l})^{-1}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}.\end{split}$ (91)

On the big ones $c\lambda\gg 1$ we have the following regularizer

$\begin{split}Reg_{i}\quad&=\quad\lambda^{-1}\sum_{\begin{subarray}{c}\lambda_{l}\text{
small}\\\ \text{eigenvalue}\\\ \text{of
}\nabla^{2}L\cup\lambda_{i}\end{subarray}}\\!\\!\\!\\!\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}\\\\[5.69046pt] &\quad+\
\lambda^{-1}(1+(-\eta\lambda)^{k})\sum_{\begin{subarray}{c}\lambda_{l}\neq\lambda\text{
big}\\\ \text{eigenvalue}\\\ \text{of
}\nabla^{2}L\end{subarray}}\\!\\!\\!\\!(c\lambda_{l})^{-1}\operatorname{Cov}_{z\in
D}(\nabla L(z))_{l,l}.\end{split}$ (92)

##  Appendix J Size of the Error

We show here some heuristics on how smaller the size of the error is compared
to the size of the regularizer. Also, we discuss the ingredients of it.

##### The size of the error.

Assume that every eigenvalue $\lambda$ of $\nabla^{2}L$ satisfies
$-\frac{\alpha}{c},2+\frac{\alpha}{c}$ for a constant $\alpha\geq 0$. From the
proof Theorem 2, precisely §K we see that the main part of the regularizer is
smaller than

$\frac{c^{3}}{12b}\nabla^{3}L\operatorname{Cov}_{z\in D}(\nabla L(z))\ \
O\left(1-\frac{\eta}{b-1}\right).$

along the near 0-eigenvalues of the Hessian $\nabla^{2}L$ and it is
upperbounded approximately by

$\frac{\eta c^{2}}{4b}[\nabla^{2}L]\nabla^{3}L\operatorname{Cov}_{z\in
D}(\nabla L(z))\ \ O\left(1-\frac{\eta}{b-1}\right)\quad+\quad
O\left(\frac{\eta}{b-1}\right)(\text{GD error})$

on the other eigendirections. Here the constant in the big $O$ is upperbounded
by $\exp(\alpha)$. Note that this is very small when
$c\operatorname{\mathbb{V}ar}{\nabla L}\ll 1$ or $\frac{c}{12}\nabla^{3}L\ll
1$ or just $\nabla L$ does not align well with the third derivative. In all
the other cases, we have to add these parts to the regularizer and look deeper
into the Taylor expansion for a small error part. Also, this is a coarse
analysis as in reality some of these terms $O(\eta\nabla L)^{2}$ are part of
the derivative of the regularizer and they can be removed.

##### The ingredients

The ingredients of these quantities are the following, all multiplied between
each other

$\eta\nabla^{3}L(\cdot),\quad\qquad
I-\eta\nabla^{2}L(\cdot),\quad\quad\text{and}\quad\quad\eta\nabla L(\cdot)$

and in particular, appearing in the forms

$V_{3}:=\left(\mathbb{E}_{z\in
D}[\|\nabla^{3}L(z)\|^{2}]-\|\nabla^{3}L\|^{2}\right)\quad\text{and}\quad
H:=\left(\mathbb{E}_{z\in
D}[\|\nabla^{2}L(z)\|^{2}]-\|\nabla^{2}L\|^{2}\right).$

##### Third derivative: $\nabla^{3}L=o(1/\eta)$.

We start our analysis by analyzing the size of the quantity

$\eta\cdot\nabla^{3}L(\cdot)$

that appears in the error. Generally, $\nabla^{3}L$ is $O(1)$, or anyways much
smaller than the Hessian. Even in the case of the edge of stability, the third
derivative gets no bigger than $\eta^{-c}$, $c<1$. It has been observed
empirically by [Damian et al., 2023] that that $c$ may be equal to
$\tfrac{3}{4}$. We however conjecture that that exponent was due to the fact
that they used MSE on a neural network with 3 layers and we conjecture that
generally for MSE the size of the third derivative never crosses

$O\left(\eta^{-\frac{2\text{depth}-3}{2\text{depth}-2}}\right),$

and attains it at the edge of stability. This allows us to conclude that in
the case of bigger eigenvalues of the Hessian, the error is almost always
smaller than the regularizer (as we have $\frac{\eta}{b}\nabla^{3}L<1$, and in
the case of $0$ ones we have $\nabla^{3}L=O(1)$ so it depends only on the size
of $\frac{c}{12}$ and the size of the gradients if the result is applicable or
not.

##### The usual size of the Hessian.

Both in the regularizer and in the error figure powers of
$[I-\eta\nabla^{2}L]$. In the regularizer the biggest exponent is $k-2$, in
the error is $2k-2$. Most of the eigenvalues of the Hessians are usually $0$
or very small positive. In many situations, a few eigenvalues are in the range
$1/\eta$ or a bit more, this induces some form of oscillation around the
manifold of minima. All these eigenvalues $\lambda$s of the mini-batch
Hessians in the range between $0$ and $2/\eta$ cause no issues. Indeed, in
these cases, the big products above are just shrinking, as
$1-\eta\lambda\in[-1,1]$ in that direction. In the case in which
$|1-\eta\lambda|=1+\frac{\alpha}{c}$, with $\alpha>1$, then anyways the bounds
hold but multiplied by a constant smaller than
$(1+\frac{\alpha}{k})^{2k}<\exp(2\alpha)$ for the error and smaller than
$(1+\frac{\alpha}{k})^{k}<\exp(\alpha)$ for the regularizer. Thus, e.g., if
every eigenvalue $\lambda$ of $\nabla^{2}L$ is in
$\lambda\in\left(-\frac{\alpha}{c},\frac{2}{\eta}+\frac{\alpha}{c}\right)$ for
reasonably small but O(1) constant $\alpha$ we have that we do not change
regime: if it was, the error remains smaller than the regularizer.

##### Where $1/n$ comes from.

In ll our errors figure quantities that are $1/n$ or $\eta/b$ smaller, those
re due to 19. Precisely, it says that the expectation of the product is
essentially the product of expectation plus a $O(1/n)$ part. When we are
taking together things like $[I-\eta\nabla^{2}L(\cdot)]$ those are usually
$i<k$ and comes out an $\eta$. So in those cases we have $O(\eta
k/n)=O(\eta/b)$.

##  Appendix K The Error $\Delta-\alpha$.

Let us call $E_{k}^{SGD}$ the error
$E_{k}^{SGD}=\Delta_{k}^{SGD}-\alpha_{k}^{SGD}$. Then we have that up to lower
order in $\eta\nabla L$ (so $+O([\eta\nabla L]^{3})$ the error satisfies

$\begin{split}E_{k}\quad&=\quad\Delta_{k}^{SGD}-\alpha_{k}^{SGD}\\\
&=\quad\Delta_{k-1}^{SGD}\quad-\quad\eta\nabla^{2}L\big{(}B_{k}\big{)}\left[\leavevmode\hbox
to18.14pt{\vbox to11.25pt{\pgfpicture\makeatletter\hbox{\hskip
9.07219pt\lower-5.62444pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-8.8722pt}{-3.62pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\theta_{1}^{GD,(k-1)\eta}-\theta$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{}{{}}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}{}\pgfsys@moveto{-8.8722pt}{-5.42444pt}\pgfsys@lineto{8.8722pt}{5.42444pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\Delta_{k-1}^{SGD}\right]\quad+\quad\begin{subarray}{c}\text{higher
order}\\\ \text{Taylor rest}\end{subarray}\\\
&\qquad-[I-\eta\nabla^{2}L\big{(}B_{k}\big{)}]\alpha_{k-1}^{SGD}+\leavevmode\hbox
to106.41pt{\vbox to19.4pt{\pgfpicture\makeatletter\hbox{\hskip
53.20573pt\lower-9.70006pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-53.00574pt}{0.50006pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\eta^{2}\nabla^{2}L\big{(}B_{k}\big{)}\left[\sum_{i=1}^{k-1}\nabla
L(B_{i})\right]$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{}{{}}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}{}\pgfsys@moveto{-53.00574pt}{-9.50006pt}\pgfsys@lineto{53.00574pt}{9.50006pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
&=\quad[I-\eta\nabla^{2}L(B_{k})]E_{k-1}^{SGD}\quad+\quad\begin{subarray}{c}\text{higher
order}\\\ \text{Taylor rest}\end{subarray}.\end{split}$ (93)

So we find the formula for it Keeping only the term with order 2 in $\nabla
L(\cdot)$s we obtain

$\begin{split}E_{k}^{SGD}\quad&=\quad[I-\eta\nabla^{2}L(B_{k})]E_{k-1}^{SGD}\quad+\quad\frac{\eta}{2}\nabla^{3}L(B_{k})\otimes[\theta_{k-1}^{SGD}-\theta]^{2}\\\
&=\quad[I-\eta\nabla^{2}L(B_{k})]E_{k-1}^{SGD}\quad+\quad\frac{\eta}{2}\nabla^{3}L(B_{k})\otimes[\theta_{1}^{GD,(k-1)\eta}-\theta+\Delta_{k-1}^{SGD}]^{2}\\\
&=\quad[I-\eta\nabla^{2}L(B_{k})]E_{k-1}^{SGD}\quad+\quad\frac{\eta}{2}\nabla^{3}L(B_{k})\otimes[\theta_{1}^{GD,(k-1)\eta}-\theta+\alpha_{k-1}^{SGD}+E_{k-1}^{SGD}]^{2}\end{split}$
(94)

This, again, up to second order in $\eta\nabla L$ is

$\begin{split}E_{k}^{SGD}\quad&=\quad[I-\eta\nabla^{2}L(B_{k})]E_{k-1}^{SGD}\quad+\quad\frac{\eta}{2}\nabla^{3}L(B_{k})\otimes[\theta_{1}^{GD,(k-1)\eta}-\theta+\alpha_{k-1}^{SGD}]^{2}\end{split}$
(95)

So by inductive hypothesis we have that the size of $E_{k}^{SGD}$ is the size
$E_{k-1}^{SGD}$ plus terms that are of the size of
$O(\eta\nabla^{3}L\otimes[\eta k\nabla L]^{2})$ that is
$O(\eta^{3}k^{3}\|\nabla L\|^{2})$. Moreover, we obtain that up to higher
order terms

$\begin{split}E_{k}^{SGD}\ &=\
\sum_{i=2}^{k}\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\frac{\eta}{2}\nabla^{3}L(B_{i})\otimes[\theta_{1}^{GD,(i-1)\eta}-\theta+\alpha_{i-1}^{SGD}]^{2}\end{split}$
(96)

and more precisely this is $\tfrac{1}{2}$ multiplied by

$\begin{split}&-\eta^{3}\sum_{i=1}^{k}\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\nabla^{3}L(B_{i})\otimes\left[\sum_{j=1}^{i-1}\left[\prod_{h=j+1}^{i-1}[I-\eta\nabla^{2}L(B_{h})]\right]\nabla
L(B_{j})\right]^{2}\\\
&\quad-\eta\sum_{i=1}^{k}\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\nabla^{3}L(B_{i})\otimes\left(\theta^{GD,(i-1)\eta}_{1}\right)^{2}.\\\
&\quad+2\eta\sum_{i=1}^{k}\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\nabla^{3}L(B_{i})\otimes\left[\theta^{GD,(i-1)\eta}_{1}\right]\otimes\alpha_{i-1}^{SGD}.\end{split}$
(97)

Now, defining analogously to $\Delta$ and $\alpha$ the error $E_{k}^{GD}$.
Concluding, we have that

$\begin{split}\theta_{k}^{SGD}-\theta_{k}^{GD}\quad&=\quad\Delta_{k}^{SGD}-\Delta_{k}^{GD}\quad=\quad\alpha_{k}^{SGD}-\alpha_{k}^{GD}+E_{k}^{SGD}-E_{k}^{GD}\end{split}$
(98)

and $\mathcal{R}:=\alpha_{k}^{SGD}-\alpha_{k}^{GD}$ is exactly the regularizer
appearing in the statement and $\mathcal{E}:=E_{k}^{SGD}-E_{k}^{GD}$ is the
error. We will see that once computing the expectations more terms cancel out
in the error and the regularizer, as for §E.

######  Remark 21 (Remarks on 9).

Note again that this holds for every version of SGD. In particular, there is
an analogous expansion for every first-order method.

##### The second and third terms of Eq. 97.

When computing $\mathcal{E}:=E_{k}^{SGD}-E_{k}^{GD}$ the parts relative to the
second and third terms of Eq. 97 are easier to handle. Precisely, the
subtraction of the term in the second line after applying 19 becomes a sum of
order

$\frac{\eta k}{n-k}O(\text{GD error})\quad=\quad\frac{\eta}{b-1}O(\text{GD
error})$

so even smaller than what it would be. Similarly, also the third term is of
the same size, by removing and adding

$2\eta\sum_{i=1}^{k}\sum_{i=1}^{k}[I-\eta\nabla^{2}L]^{k-i-1}\nabla^{3}L\otimes\left[\theta^{GD,(i-1)\eta}_{1}\right]\otimes\alpha_{i-1}^{SGD}$

Then we have that the difference between the SGD part and this is $O(1/(n-k))$
times the GD error and same for this minus the GD error. So, this part was
about

$\frac{5\eta k}{n-k}\quad=\quad\frac{5\eta}{b-1}$

smaller than the GD error. The main part of the error comes from the
difference of the terms in the first line.

##### The first line of Eq. 97.

######  Remark 22.

Next note that part of this falls into the regularizer, precisely all the
summands of the form

$\eta^{3}\mathbb{E}\left[\nabla
L(B_{l})^{\top}\nabla^{3}L(B_{i})\prod_{h=j}^{i}[I-\eta\nabla^{2}L(B_{h})]\nabla
L(B_{j})\right].$

The remaining terms can be treated as the regularizer. In particular, we
rewrite it as

$\begin{split}&\underbrace{-\eta^{3}\sum_{i=1}^{k}\left[\prod_{j=i+1}^{k}[I-\eta\nabla^{2}L(B_{j})]\right]\nabla^{3}L(B_{i})\otimes\left[\sum_{j=1}^{i-1}\left[\prod_{h=j+1}^{i-1}[I-\eta\nabla^{2}L(B_{h})]\right]\nabla
L(B_{j})\right]^{2}}_{\text{SGD part}}\\\
&\quad-\eta^{3}\sum_{i=1}^{k}[I-\eta\nabla^{2}L]^{k-i-1}\nabla^{3}L\otimes\left[\sum_{j=1}^{i-1}\left[\prod_{h=j+1}^{i-1}[I-\eta\nabla^{2}L(B_{h})]\right]\nabla
L(B_{j})\right]^{2}\\\
&\quad+\eta^{3}\sum_{i=1}^{k}[I-\eta\nabla^{2}L]^{k-i-1}\nabla^{3}L\otimes\left[\sum_{j=1}^{i-1}\left[\prod_{h=j+1}^{i-1}[I-\eta\nabla^{2}L(B_{h})]\right]\nabla
L(B_{j})\right]^{2}\\\ &\quad\underbrace{+\
\eta^{3}\sum_{i=1}^{k}[I-\eta\nabla^{2}L]^{k-i-1}\nabla^{3}L\otimes\left[\sum_{j=1}^{i-1}\
[I-\eta\nabla^{2}L]^{i-j-2}\nabla L\right]^{2}}_{\text{GD part}}.\end{split}$
(99)

The expectation of the difference between third and fourth line, using Lemma
14, when $\|I-\eta\nabla^{2}L(B_{i})\|\leq 1+\epsilon$ is smaller in size or
equal to

$\eta^{3}\sum_{i=1}^{k}[I-\eta\nabla^{2}L]^{k-i-1}\nabla^{3}L\otimes\left(\sum_{j=0}^{i-1}O\left(\frac{n(j-1)-(j-1)^{2}}{(n-1)b}\operatorname{Cov}_{z\in
D}(\nabla L)\right)\right)$

where the constant of the big O is $O\epsilon i$ to the first order in
$\epsilon,\ i$, and it is exponentially small in the directions in which
$|I-\eta\nabla^{2}L|<1$. This sums up to something smaller than

$\eta^{3}\sum_{i=1}^{k}[I-\eta\nabla^{2}L]^{k-i-1}\nabla^{3}LO\left(\frac{n(j-1)-(j-1)^{2}}{(n-1)b}\operatorname{Cov}_{z\in
D}(\nabla L(z))\right)$
$\quad<\quad\frac{1}{2b}O\left([\nabla^{2}L]^{3{\dagger}}\max\left\\{2[I-\eta\nabla^{2}L]^{k}-c^{2}(\nabla^{2}L)^{2}+2c\nabla^{2}L-2\right\\}\right)\nabla^{3}L\operatorname{Cov}_{z\in
D}(\nabla L(z))$

analogously, this is upper-bounded approximately by

$\frac{c^{3}}{6b}\nabla^{3}L\operatorname{Cov}_{z\in D}(\nabla L(z))$

along the 0-eigenvalues of the Hessian $\nabla^{2}L$ and it is upperbounded
approximately by

$\frac{\eta c^{2}}{2b}[\nabla^{2}L]\nabla^{3}L\operatorname{Cov}_{z\in
D}(\nabla L(z))$

along the other directions. The expectation of the difference between the
terms in first and second line is instead 19 of order approximately $1/n$ of
it, indeed we can upperbound it with

$-\frac{\eta}{b-1}\big{(}\text{GD part}+\text{part above}\big{)}.$

##### Summing all up.

This means that summing all up we obtain that the error, when
$-\epsilon<\eta\nabla^{2}L<2+\epsilon$ the part coming from the first line of
Eq. 97 is smaller than

$\frac{c^{3}}{12b}\nabla^{3}L\operatorname{Cov}_{z\in D}(\nabla L(z))\ \
O\left(1-\frac{\eta}{b-1}\right)\quad+\quad
O\left(\frac{\eta}{b-1}\right)(\text{GD error}).$

along the 0-eigenvalues of the Hessian $\nabla^{2}L$ and it is upperbounded
approximately by

$\frac{\eta c^{2}}{4b}[\nabla^{2}L]\nabla^{3}L\operatorname{Cov}_{z\in
D}(\nabla L(z))\ \ O\left(1-\frac{\eta}{b-1}\right)\quad+\quad
O\left(\frac{\eta}{b-1}\right)(\text{GD error}).$

On the other eigendirections. Note that this is even smaller when the noise
covariance does not properly align with the eigenvectors of the highest
eigenvalues of the third derivative. when $c\operatorname{\mathbb{V}ar}{\nabla
L}\ll 1$ and $\frac{c}{12}\nabla^{3}L\ll 1$ or just $\nabla L$ does not align
well with the third derivative. In all the other cases, we have to add these
parts to the regularizer and look deeper into the Taylor expansion for a small
error part.

##  Appendix L Proof of Theorem 4

######  Theorem (Regularizing the trace of Hessian, Theorem 4).

Assume all the training data are correctly classified. Then

$Fisher\quad=\quad\mathbb{E}_{z\in D}[\nabla L\nabla
L^{\top}]\quad=\quad\nabla^{2}L\quad=\quad Hessian.$

In particular, the local minima of $\text{trace}(S\cdot\text{Fisher})$
coincides with the local minima of $\text{trace}(S\cdot\text{Hessian})$.

Note that

$L\big{(}\theta,(x,y)\big{)}\quad=\quad-\log\big{(}p(y|x,\theta)\big{)}$

Indeed, note that the approximate Fisher information matrix we work with is

$Fisher\quad=\quad\mathbb{E}_{z\in D}\left[\nabla L\nabla
L^{\top}\right]\quad=\quad\mathbb{E}_{z\in
D}\left[\nabla\log\big{(}p(y|x,\theta)\big{)}\nabla\log\big{(}p(y|x,\theta)\big{)}^{\top}\right].$

In the final part of the training, when on the training data points we have
that the labels according to our model correspond with the ones on the
training dataset, we have that

$\quad\mathbb{E}_{(x,y)\in D}\left[\nabla L\nabla
L^{\top}\right]\quad=\quad\mathbb{E}_{x\in D}\left[\mathbb{E}_{y\sim
p(\cdot|x,\theta)}\left[\nabla\log\big{(}p(y|x,\theta)\big{)}\nabla\log\big{(}p(y|x,\theta)\big{)}^{\top}\right]\right].$

As $y_{i}=y\sim p(\cdot|x_{i},\theta)$ for all $z=(x_{i},y_{i})\in D$. This is
equal to the Hessian, indeed

$Hessian\quad=\quad\mathbb{E}_{z\in
D}\left[\nabla^{2}L\right]\quad=\quad\mathbb{E}_{x\in
D}\left[\mathbb{E}_{y\sim
p(\cdot|x,\theta)}\left[\nabla^{2}\log\big{(}p(y|x,\theta)\big{)}\right]\right].$

Thus noticing that $\mathbb{E}_{y\sim
p(\cdot|x,\theta)}[\nabla^{2}p(y|x,\theta)]=\nabla^{2}_{\theta}\mathbb{E}[p(y|x,\theta)]=\frac{d^{2}}{d\theta^{2}}1=0$,
we conclude that

$Fisher\quad=\quad Hessian.$

This proves Theorem 4.

##  Appendix M On the Gradients of Neural Networks

For a neural network decreasing $\|\nabla_{\theta}f(\theta,x)\|$ essentially
corresponds to decreasing $\|\nabla_{x}f(\theta,x)\|$. Precisely, let $\sigma$
be an activation function, let $W_{i}$ be the weight matrix of $i-th$ layer,
then enlarging the weight matrices to account for the biases,

$f(\theta,x)\quad=\quad W_{L}\cdot\sigma\circ
W_{L-1}\circ\ldots\cdot\sigma\circ W_{2}\cdot\sigma\circ W_{1}\cdot x$

Its derivative in the input is

$\frac{df(\theta,x)}{dx}\quad=\quad W_{L}\cdot\sigma^{\prime}\cdot
W_{L-1}\cdot\ldots\cdot\sigma^{\prime}\cdot W_{2}\cdot\sigma^{\prime}\cdot
W_{1}$

while its derivative in the parameters $\vartheta$ entry of $W_{i}$ is the
product of the derivatives of the activations and the weight matrices of the
following layers, multiplied by the preactivation of the $i-th$ layer.

$\frac{df(\theta,x)}{d\vartheta}\quad=\quad\big{(}W_{L}\cdot\sigma^{\prime}\cdot
W_{L-1}\cdot\ldots\cdot\sigma^{\prime}\cdot
W_{i+1}\cdot\sigma^{\prime}\big{)}\cdot\sigma\circ
W_{i-1}\cdot\ldots\sigma\circ W_{2}\cdot\sigma\circ W_{1}\cdot x$

Thus making the norm of the parameters’ gradient smaller means corresponds to
reducing the norm of the sum of all the preactivations of the neurons
multiplied by the product of the coming weights, thus reducing the norm of the
inputs’ gradient

##  Appendix N Saddles

Assume $\theta$ is a stationary point for $L$. We analyze here the dynamics in
the direction of a unitary eigenvector $v$ of the eigenvalue $\lambda$ of
$\nabla^{2}L$. Define

$u\quad:=\quad\frac{1}{n}\sum_{z\in D}\langle v_{\lambda},\nabla^{2}L(z)\nabla
L(z)\rangle\quad\neq\quad 0.$

First note that the update due to $k$ steps of GD from $\theta$, in our
regime, is

$\theta_{new}-\theta=[\nabla^{2}L]^{-1}(\exp(-c\nabla^{2}L)-I)\nabla
L(\theta)=:\beta\nabla L.$

Indeed at every step $i<k$ we have that

$\theta_{i+1}-\theta\quad=\quad-\eta\nabla
L+[I-\eta\nabla^{2}L](\theta_{i}-\theta)\quad=\quad-\eta\sum_{j=0}^{i}[I-\eta\nabla^{2}L]^{i-j}\nabla
L.$

Taking the limit we have the definition of $\beta$. We see here how far we go
after $m$ epochs in the direction of the eigenspace of $\lambda$ assuming
$c\nabla L<<1$, then denote $\beta:=\lambda^{-1}(\exp(-c\lambda)-I)$ the
update due to GD is $+\beta\nabla L$ and denote the step on the regularizer
$\alpha:=\frac{\eta}{b-1}Su$.

epochs | 1 | 2
---|---|---
$\theta_{t}-\theta$ | $-\alpha+\beta\nabla L$ | $-2\alpha+2\beta\nabla L+\lambda\beta(-\alpha+\beta\nabla L)$
$\nabla L(\theta_{t})-\nabla L$ | $\lambda(-\alpha+\beta\nabla L)$ | $\lambda\big{(}-(2+\lambda\beta)\alpha+(2+\lambda\beta)\beta\nabla L\big{)}$
$\nabla^{2}L(\theta_{t})-\nabla^{2}L$ | $\nabla^{3}L(-\alpha+\beta\nabla L)$ | $\nabla^{3}L\big{(}-(2+\lambda\beta)\alpha+(2+\lambda\beta)\beta\nabla L\big{)}$
$L(\theta_{t})-L$ | $\begin{subarray}{c}\nabla L(\theta_{1})(-\alpha+\beta\nabla L)+\lambda\|-\alpha+\beta\nabla L\|^{2}\\\ =\nabla L(-\alpha+\beta\nabla L)+\lambda(-\alpha+\beta\nabla L)^{2}+\tfrac{\lambda}{2}(-\alpha+\beta\nabla L)^{2}\end{subarray}$ | $\begin{subarray}{c}\nabla L^{\top}(\theta_{1}-\theta+\theta_{2}-\theta)\ +\ \tfrac{3\lambda}{2}\big{(}\|\theta_{1}-\theta\|^{2}+\|\theta_{2}-\theta\|^{2}\big{)}\end{subarray}$

And in general

epochs | m
---|---
$\theta_{m}-\theta$ | $-(\lambda\beta)^{-1}\big{(}(1+\lambda\beta)^{m}-1\big{)}\alpha+(\lambda\beta)^{-1}\big{(}(1+\lambda\beta)^{m}-1\big{)}\beta\nabla L$
$\nabla L(\theta_{m})-\nabla L$ | $\lambda(\theta_{m}-\theta)+\tfrac{1}{2}\nabla^{3}L(\theta_{m}-\theta)^{2}$
$\nabla^{2}L(\theta_{m})-\nabla^{2}L$ | $\nabla^{3}L(\theta_{m}-\theta)$
$L(\theta_{t})-L$ | $\nabla L^{\top}(\theta_{m}-\theta)+\tfrac{3\lambda}{2}\sum_{i=1}^{m}\|\theta_{i}-\theta_{i-1}\|^{2}+O(\sum_{i=1}^{m}\|\theta_{i}-\theta_{i-1}\|^{3})$

We have that after $m$ steps SGD in expectation takes the parameter vector
away of the following quantity

$\underbrace{-(\lambda\beta)^{-1}\big{(}(1+\lambda\beta)^{m}-1\big{)}\alpha}_{\text{SGD
regularizer
effect}}\quad+\quad\underbrace{\lambda^{-1}\big{(}(1+\lambda\beta)^{m}-1\big{)}\nabla
L}_{\text{GD effect}}.$

In the escaping directions, for $c\lambda=\eta k\lambda<0$, the regularizer
part is

$\tfrac{\eta}{b}(\exp(-c\lambda)-1)^{-1}\big{(}\exp(-cm\lambda)-1\big{)}\lambda^{-2}(\exp(-c\lambda)+c\lambda-1)u.$

Then, even forgetting about the $\nabla L$ part, so even if we start exactly
from a flat area

$\theta_{m}-\theta_{m-1}\quad=\quad-(\lambda\beta)^{-1}\lambda\beta(1+\lambda\beta)^{m-1}\alpha$

That is equal to

$\theta_{m}-\theta_{m-1}\quad=\quad-(1+\lambda\beta)^{m-1}\alpha$

Thus we have

$\theta_{m}-\theta_{m-1}=\tfrac{\eta}{b}\exp(-c(m-1)\lambda)\lambda^{-2}(\exp(-c\lambda)+c\lambda-1)u.$

Thus, since $\lambda^{-2}(\exp(-c\lambda)+c\lambda-1)>c/2-c^{2}\lambda/6$ for
all $c\lambda<0$ we have that

$\|\theta_{m}-\theta_{m-1}\|^{2}>\frac{\eta^{2}}{b^{2}}\exp(-2c(m-1)\lambda)\left(\frac{c}{2}-\frac{c^{2}\lambda}{6}\right)^{2}u^{2}.$

Thus

$\begin{split}&\frac{3\lambda}{2}\sum_{i=1}^{m}\|\theta_{i}-\theta_{i-1}\|^{2}<\frac{3\eta^{2}c^{2}\lambda
u^{2}}{8b^{2}}\left(1-\frac{c\lambda}{3}\right)^{\\!2}\
\sum_{i=0}^{m-1}\exp(-2ci\lambda)\end{split}$ (100)

So, we have that after $m$ steps we reduced the loss by at least of

$\frac{3\eta^{2}c^{2}\lambda
u^{2}}{8b^{2}}\left(1-\frac{c\lambda}{3}\right)^{\\!2}\frac{\exp(-2cm\lambda)-1}{\exp(-2c\lambda)-1}.$

Then we have that the loss decreased by $O(1)$ after a number of steps
(epochs)

$\\#epochs\quad>\quad\frac{1}{2|c\lambda|}\log\left(\frac{b^{2}}{\eta^{2}c^{4}\lambda
u^{2}}\right)+2.$

This means after

$\\#epochs\quad>\quad\frac{\log(\eta)+\log(u)+2\log(c)-\log(b)}{c\lambda}+2.$

So after this number of epochs, the saddle was escaped only thanks to the
effect of SGD.

Even in the case in which the saddles is higher order or the negative
eigenvalue is so small that $|c\lambda|\ll 1$ we have that the effect of SGD
pushes you away, indeed in this case

$\theta_{m}-\theta\quad=\quad m\alpha\quad=\quad
m\cdot\frac{\eta}{b-1}\frac{c}{2}u$

so after $m=\frac{b}{\eta}$ epochs $\theta_{m}-\theta=O(1)$ and if the first
non-zero derivative is the $i$-th we have the loss to decrease like

epochs | 1 | 2
---|---|---
$\theta_{t}-\theta$ | $-\alpha$ | $-2\alpha-c\frac{\nabla^{i}L}{(i-1)!}(-\alpha)^{i-1}$
$\nabla L(\theta_{t})-\nabla L$ | $\frac{\nabla^{i}L}{(i-1)!}(-\alpha)^{i-1}$ | $\ldots$
$\nabla^{j}L(\theta_{t})-\nabla^{j}L$ | $\frac{\nabla^{i}L}{(i-j)!}(-\alpha)^{i-j}$ | $(1+2^{i-j})\frac{\nabla^{i}L}{(i-j)!}(-\alpha)^{i-j}+\sum_{h=1}^{j-1}\frac{\nabla^{i}L}{(i-h)!}(-\alpha)^{i-h}(-2\alpha)^{h-j}$
$L(\theta_{t})-L$ | $\frac{\nabla^{i}L}{i!}(-\alpha)^{i}$ | $\ldots$
epochs | m
---|---
$\theta_{t}-\theta$ | $-m\alpha+c\sum_{i=1}^{m}\nabla L(\theta_{i})$
$\nabla L(\theta_{t})-\nabla L$ | $(-\alpha)^{i-1}\sum_{h=1}^{i}\frac{1}{h!}\left(1+\sum_{l=2}^{m}(l-1)^{i-h}l^{h-1}\right)$
$\nabla^{j}L(\theta_{t})-\nabla^{j}L$ | $(-\alpha)^{i-j}\sum_{h=j}^{i}\frac{\nabla^{i}L}{h!}\left(1+\sum_{l=2}^{m}(l-1)^{i-h}l^{h-j}\right)$
$L(\theta_{t})-L$ | $(-\alpha)^{i}\sum_{h=0}^{i}\frac{\nabla^{i}L}{h!}\left(1+\sum_{l=2}^{m}(l-1)^{i-h}l^{h-j}\right)$

And

$(-\alpha)^{i}\sum_{h=0}^{i}\frac{\nabla^{i}L}{h!}\left(1+\sum_{l=2}^{m}(l-1)^{i-h}l^{h-j}\right)$

in particular, is about the quantity

$\nabla^{i}L(-\alpha)^{i}\left[\sum_{h=0}^{i}\frac{1}{h!}\right]\int_{0}^{m}x^{i}dx\quad=\quad\nabla^{i}L(-\alpha)^{i}\frac{em^{i+1}}{i+1}.$

Thus the loss is smaller $O(1)$ if m is such that (taking the logarithms

$(i+1)\log(m)+i\log(|\alpha|)\sim 0$

so if $m\quad\sim\quad\frac{2b}{\eta cu}$ no matter the order of the saddle.