Deep linear networks for regression
are implicitly regularized towards flat minima

Pierre Marion, Lénaïc Chizat

Institute of Mathematics

EPFL

Station Z, CH-1015 Lausanne, Switzerland

<EMAIL_ADDRESS>
###### Abstract.

The largest eigenvalue of the Hessian, or sharpness, of neural networks is a
key quantity to understand their optimization dynamics. In this paper, we
study the sharpness of deep linear networks for overdetermined univariate
regression. Minimizers can have arbitrarily large sharpness, but not an
arbitrarily small one. Indeed, we show a lower bound on the sharpness of
minimizers, which grows linearly with depth. We then study the properties of
the minimizer found by gradient flow, which is the limit of gradient descent
with vanishing learning rate. We show an implicit regularization towards flat
minima: the sharpness of the minimizer is no more than a constant times the
lower bound. The constant depends on the condition number of the data
covariance matrix, but not on width or depth. This result is proven both for a
small-scale initialization and a residual initialization. Results of
independent interest are shown in both cases. For small-scale initialization,
we show that the learned weight matrices are approximately rank-one and that
their singular vectors align. For residual initialization, convergence of the
gradient flow for a Gaussian initialization of the residual network is proven.
Numerical experiments illustrate our results and connect them to gradient
descent with non-vanishing learning rate.

##  1\. Introduction

Neural networks have intricate optimization dynamics due to the non-convexity
of their objective. A key quantity to understand these dynamics is the largest
eigenvalue of the Hessian or sharpness $S({\mathcal{W}})$, in particular
because of its connection with the choice of learning rate $\eta$. Classical
theory from convex optimization indicates that the sharpness should remain
lower than $2/\eta$ to avoid divergence (Nesterov, 2018). The relevance of
this point of view for deep learning has recently been questioned since neural
networks have been shown to often operate at the edge of stability (Cohen et
al., 2021), where the sharpness oscillates around $2/\eta$, while the loss
still steadily decreases, albeit non-monotonically. Damian et al. (2023)
explained the stability of gradient descent slightly above the $2/\eta$
threshold to be a general phenomenon for non-quadratic objectives, where the
third-order derivatives of the loss induce a self-stabilization effect. They
also show that, under appropriate assumptions, gradient descent on a risk
$R^{L}$ implicitly solves the constrained minimization problem

$\min_{\mathcal{W}}R^{L}({\mathcal{W}})\quad\textnormal{such that}\quad
S({\mathcal{W}})\leqslant\frac{2}{\eta}\,.$ (1)

Trainability of neural networks initialized with a sharpness larger than
$2/\eta$ is also studied by Lewkowycz et al. (2020), which describes a
transient catapult regime, which lasts until the sharpness goes below
$2/\eta$. These results beg the question of quantifying the largest learning
rate that enables successful training of neural networks. For classification
with linearly separable data and logistic loss, Wu et al. (2024) show that
gradient descent converges for any learning rate. In this work, we address the
case of deep linear networks for an overdetermined univariate regression task,
where overdetermined means that the sample size $n$ is larger that the data
dimension $d$ and the data empirical covariance matrix is nonsingular. As
illustrated by Figure 1(a), the picture then differs from the classification
case: when the learning rate exceeds some critical value, the network fails to
learn. We further remark that this critical value does not seem to be related
to the initial scale: when the learning rate is under the critical value,
learning is successful for a wide range of initial scales. In Figure 1(b), we
see that the large initialization scales correspond to initial sharpnesses
well over the $2/\eta$ threshold, confirming that training is possible while
initializing beyond the $2/\eta$ threshold.

(a) Squared distance of the trained network to the empirical risk minimizer,
for various learning rates and initialization scales. Training succeeds when
the learning rate is lower than a critical value independent of the
initialization scale.

(b) Sharpness at initialization and after training, for various learning rates
and initialization scales. For a given learning rate $\eta$, the dashed lines
represent the $2/\eta$ threshold. The dotted black lines represent the lower
and upper bounds given in Theorem 1 and Corollary 3.

(c) Evolution during training of the squared distance to the empirical risk
minimizer and of sharpness, for $\eta=0.02$ and an initialization scale of
$0.3$. The network does not enter edge of stability.

(d) Evolution during training of the squared distance to the empirical risk
minimizer and of sharpness, for $\eta=0.1$ and an initialization scale of
$0.3$. The network enters edge of stability.

Figure 1. Training a deep linear network on a univariate regression task with
quadratic loss. The weight matrices are initialized as Gaussian random
variables, whose standard deviation is the x-axis of plots 1(a) and 1(b).
Experimental details are given in Appendix C.

To understand where the critical value for the learning rate comes from, we
characterize the sharpness of minimizers of the empirical risk. Since we
consider an overdetermined regression problem, all minimizers of the empirical
risk implement the same optimal linear regressor (they are equal in function
space), but may have different sharpnesses since they differ in parameter
space. We show that there exist minimizers with arbitrarily large sharpness,
but not with arbitrarily small sharpness. Indeed, the sharpness of any
minimizer grows linearly with depth, as made precise next.

######  Theorem 1.

Let $X\in{\mathbb{R}}^{n\times d}$ be a design matrix and
$y\in{\mathbb{R}}^{n}$ a target. Then the sharpness of any linear network
$x\mapsto W_{L}\dots W_{1}x$ of depth $L$ that implements the optimal linear
regressor $w^{\star}\in{\mathbb{R}}^{d}$ is at least

$S_{\min}:=2L\lambda\|w^{\star}\|_{2}^{2-\frac{2}{L}}\,,$

where $\lambda$ is the lowest eigenvalue of the empirical covariance matrix
$\hat{\Sigma}:=\frac{1}{n}X^{\top}X$.

We note that this bound is similar to a result of Mulayoff and Michaeli
(2020), although we alleviate their assumption of data whiteness
($\hat{\Sigma}=I$), and our proof technique differs, since we do not require
tensor algebra, and instead exhibit a direction in which the second derivative
of the loss is large.

This result shows that it is not possible to find a minimizer of the empirical
risk in regions of low sharpness. Combined with (1), this suggests an
interpretation of the critical value for the learning rate: gradient descent
should not be able to converge to a global minimizer as soon as

$S_{\min}>\frac{2}{\eta}\quad\Leftrightarrow\quad\eta>\frac{2}{S_{\min}}\,.$

This is coherent with the observations in Figure 1(a): in this case,
$2/S_{\min}=0.2$, and training fails for $\eta=0.2$, but succeeds for
$\eta\leqslant 0.1$. In summary, the sharpness of minimizers is lower bounded,
causing gradient descent with large learning rate to fail.

To deepen our understanding of the training dynamics, we quantify the
sharpness of the minimizer found by gradient descent (when it succeeds): we
know that it has to be larger than $S_{\min}$, but is it close to $S_{\min}$
or is it much larger? Inspecting Figure 1(b), we see that the answer
empirically depends on the interplay between initialization scale and learning
rate. For small initialization scale, the sharpness after training is equal to
a value relatively close to $S_{\min}$ and independent of the learning rate.
As the initialization scale increases, the sharpness of the trained network
also increases, and plateaus at the value $2/\eta$. The plateauing for large
initialization scales can be explained by the edge of stability analysis (1),
which upper bounds the sharpness of the minimizer by $2/\eta$ (see Figure
1(d)). However, this gives no insight on the value of the sharpness when the
learning rate is sufficiently small so that the network does not enter the
edge of stability regime (see Figure 1(c)).

In this paper, we study the limiting case for vanishing $\eta$, i.e., training
with gradient flow. As our main finding, we bound the sharpness of the
minimizer found by gradient flow: the ratio between the sharpness after
training and $S_{\min}$ is less than a constant depending mainly on the
condition number of the empirical covariance matrix $\hat{\Sigma}$. In
particular, the ratio does not depend on the width or depth of the network.
This shows an implicit regularization towards flat minima. This is remarkable
in particular insofar as flatter minima have been found to generalize better
(Hochreiter and Schmidhuber, 1997; Jastrzębski et al., 2017; Keskar et al.,
2017; Jiang et al., 2020), although the picture is subtle (Dinh et al., 2017;
Neyshabur et al., 2017; Andriushchenko et al., 2023). Note that the phenomenon
we exhibit is different from the well-studied implicit regularization towards
flat minima caused by stochasticity in SGD (Keskar et al., 2017; Smith and Le,
2018; Blanc et al., 2020; Damian et al., 2021; Li et al., 2022; Liu et al.,
2023). In the present study, the dynamics are purely deterministic, and the
low sharpness is due to the fact that the weight matrices found by gradient
flow have (approximately) the same norm across layers, and that this norm is
(approximately) the smallest possible one so that the network can minimize the
risk. We investigate two initialization schemes, quite different in nature:
small-scale initialization and residual initialization. Let us explain both
settings, by presenting our approach, contributions of independent interest,
and related works.

Small-scale initialization. In this setting, we consider an initialization of
the weight matrices $W_{k}$ with i.i.d. Gaussian entries of small variance. We
show convergence of the empirical risk to zero, then characterize the
structure of the minimizer found by gradient flow, a novel result of interest
independently of its connection with sharpness. At convergence, the weight
matrices are close to being rank-one, in the sense that all their singular
values but the largest one are small. Furthermore, the first left singular
vector of any weight matrix aligns with the first right singular vector of the
next weight matrix. From this specific structure, we deduce our bound on the
sharpness of the trained network. The bound is illustrated on Figure 1(b),
where our lower and upper theoretical bounds on the sharpness are plotted as
dotted black lines. We observe that the sharpness after training, when
starting from a small-scale initialization, is indeed situated between the
black lines.

The result and proof extend the study by Ji and Telgarsky (2020) for
classification, although the parameters do not diverge to infinity contrarily
to the classification case, thus requiring a finer control of the distance to
the rank-one aligned solution. In regression, implicit regularization towards
low-rank structure in parameter space was also studied by Saxe et al. (2014);
Lampinen and Ganguli (2019); Gidel et al. (2019); Saxe et al. (2019); Varre et
al. (2023) for two-layer neural networks and in Timor et al. (2023) for deep
ReLU networks. This latter paper assumes convergence of the optimization
algorithm and show that a solution with minimal $\ell_{2}$-norm has to be low-
rank. In our linear setting, we instead show convergence. As detailed below,
we impose mild requirements on the structure on the initialization beyond its
scale; they are satisfied for instance by initializing one weight matrix to
zero and the others with i.i.d. Gaussian entries. In particular, we do not
require the so-called “zero-balanced initialization” as is common in the
literature on deep linear networks (see, e.g., Arora et al., 2018; Advani et
al., 2020; Li et al., 2021) or a deficient-margin initialization as in Arora
et al. (2019a). Finally, the limit when initialization scale tends to zero has
been described for deep linear networks in Jacot et al. (2021) for
multivariate regression. It consists in a saddle-to-saddle dynamics, where the
rank of the weight matrices increases after each saddle. The present study
considers instead a non-asymptotic setting where the initialization scale is
small but nonzero, and shows convergence to a rank-one limit because
univariate and not multivariate regression is considered.

We note that sharpness at initialization can be made arbitrarily small, since
it is controlled by the initialization scale, while sharpness after training
scales as $\Theta(L)$. This therefore showcases an example of sharpening
during training (although we make no statement on monotonicity).

Residual initialization. Architectures of deep neural networks used in
practice often present residual connections, which stabilize training (He et
al., 2015). This prompts us to consider square weight matrices
$W_{k}\in{\mathbb{R}}^{d\times d}$ that are initialized as

$W_{k}(0)=I+\frac{s}{\sqrt{Ld}}N_{k}\,,$ (2)

where the $N_{k}\in{\mathbb{R}}^{d\times d}$ are filled with i.i.d. standard
Gaussian entries and $s\geqslant 0$ is a hyperparameter tuning the
initialization scale. The scaling of the residual branch in $1/\sqrt{d}$ is
common and corresponds for instance to the so-called Glorot and He
initializations respectively from Glorot and Bengio (2010) and He et al.
(2015). It ensures that the variance of the residual branch is independent of
the width $d$. Similarly, as studied in Arpit et al. (2019); Marion et al.
(2022), the scaling in $1/\sqrt{L}$ is the right one so that the
initialization noise neither blows up nor decays when $L\to\infty$. Note that,
in practice, this scaling factor is often replaced by batch normalization
(Ioffe and Szegedy, 2015), which has been shown empirically to have a similar
effect to $1/\sqrt{L}$ scaling (De and Smith, 2020).

In this setting which we refer to as residual initialization, we show global
convergence of the empirical risk. To our knowledge, it is the first time that
convergence is proven for a standard Gaussian initialization of the residual
network outside the large width $d\geqslant n$ regime. Previous works
considered either an identity initialization (Bartlett et al., 2018; Arora et
al., 2019a; Zou et al., 2020) or a smooth initialization such that
$\|W_{k+1}(0)-W_{k}(0)\|_{F}={\mathcal{O}}(1/L)$ (Sander et al., 2022; Marion
et al., 2024). The extension to standard Gaussian initialization leverages
sharp bounds for the singular values of the product of $W_{k}(0)$. Our main
assumption, in alignment with the literature, is that the risk at
initialization should not be larger than a constant (depending on
$\hat{\Sigma}$ and $s$).

We then show that the weights after training can be written

$W_{k}(\infty)=I+\frac{s}{\sqrt{Ld}}N_{k}+\frac{1}{L}\theta_{k}\,,$

where the Frobenius norm of the $\theta_{k}$ is bounded by a constant
(depending only on $s$). This structure finally enables us to bound the
sharpness of the trained network. Remark that, to connect this analysis with
our discussion of sharpness in univariate regression, we add to the residual
network a final fixed projection vector $w\in{\mathbb{R}}^{d}$, so that our
neural network writes $x\mapsto w^{\top}W_{L}\dots W_{1}x$, but the proof of
convergence also holds without this projection.

Experimentally, we give in Appendix C plots in the residual case that are
qualitatively similar to Figure 1. The main difference is that the initial
sharpness is less sensitive to the initialization scale $s$.

Organization of the paper. Section 2 details our setting and notations.
Section 3 studies the sharpness of minimizers of the empirical risk and proves
Theorem 1. Dynamics of gradient flow starting from small-scale initialization
and residual initialization are respectively presented in Sections 4 and 5.
The Appendix contains proofs, additional plots, experimental details, and
related works.

##  2\. Setting

Model. We consider linear networks of depth $L$ from ${\mathbb{R}}^{d}$ to
${\mathbb{R}}$, which are linear maps

$x\mapsto w^{\top}W_{L}\dots W_{1}x$ (3)

parameterized by weight matrices $W_{1},\dots,W_{L}$, where
$W_{k}\in{\mathbb{R}}^{d_{k}\times d_{k-1}}$, $d_{0}=d$ and
$w\in{\mathbb{R}}^{d_{L}}$ is a fixed vector. This definition includes both
fully-connected networks by setting $d_{L}=1$ and $w=1$, and residual networks
by setting $d_{1}=\dots=d_{L}=d$, the $W_{k}$ close to the identity, and $w$
to some fixed (potentially random) vector in ${\mathbb{R}}^{d}$. We let
${\mathcal{W}}=(W_{1},\dots,W_{L})$ and
$w_{\textnormal{prod}}=W_{1}^{\top}\dots W_{L}^{\top}w$. Given
$X\in{\mathbb{R}}^{n\times d}$ a design matrix and $y\in{\mathbb{R}}^{n}$ a
target, we consider the empirical risk for regression

$R^{L}({\mathcal{W}}):=\frac{1}{n}\|y-XW_{1}^{\top}\dots
W_{L}^{\top}w\|_{2}^{2}=\frac{1}{n}\|y-Xw_{\textnormal{prod}}\|_{2}^{2}=:R^{1}(w_{\textnormal{prod}})\,.$

The notations $R^{L}({\mathcal{W}})$ and $R^{1}(w_{\textnormal{prod}})$ may
seem redundant, but are actually practical to define gradients of the risk
both with respect to a single matrix $W_{k}$ and to the product
$w_{\textnormal{prod}}$. We next make the following assumption on the data.

  * $(A_{1})$

The covariance matrix
$\hat{\Sigma}=\frac{1}{n}X^{\top}X\in{\mathbb{R}}^{d\times d}$ is full rank.
We denote respectively by $\lambda$ and $\Lambda$ its smallest and largest
eigenvalue.

This assumption implies that there exists a unique minimizer
$w^{\star}\in{\mathbb{R}}^{d}$ to the regression problem
$\min_{w_{\textnormal{prod}}\in{\mathbb{R}}^{d}}R^{1}(w)$. This minimizer
satisfies the identity $\nabla R^{1}(w^{\star})=0\Leftrightarrow
X^{\top}y=X^{\top}Xw^{\star}$. However, due to the overparameterization
induced by the neural network, there exists an infinity of global minimizers
of the problem $\min_{{\mathcal{W}}}R^{L}({\mathcal{W}})$, which correspond to
different parameterizations of the optimal mapping $x\mapsto w^{\star\top}x$.
We let $R_{\min}=R^{1}(w^{\star})$ be the minimum of $R^{1}$ (and $R^{L}$).

Gradient flow. We consider that the neural network is trained by gradient flow
on the empirical risk $R^{L}$, that is, the parameters evolve according to the
ordinary differential equation

$\frac{dW_{k}}{dt}=-\frac{\partial R^{L}}{\partial W_{k}}\,.$ (4)

An application of the chain rule gives

$\nabla_{k}R^{L}({\mathcal{W}}):=\frac{\partial R^{L}}{\partial
W_{k}}=W_{k+1}^{\top}\dots W_{L}^{\top}w\nabla
R^{1}(w_{\textnormal{prod}})^{\top}W_{1}^{\top}\dots W_{k-1}^{\top}\,,$ (5)

with

$\nabla
R^{1}(w_{\textnormal{prod}})=-\frac{2}{n}X^{\top}(y-Xw_{\textnormal{prod}})=-\frac{2}{n}X^{\top}X(w^{\star}-w_{\textnormal{prod}})\,,$
(6)

where the second equality comes from the identity satisfied by $w^{\star}$
given above.

Notations. For $k\in\\{1,\dots L\\}$, we denote respectively by $\sigma_{k}$,
$u_{k}$, and $v_{k}$ the first singular value (which equals the $\ell_{2}$
operator norm), the first left singular vector and the first right singular
vector of $W_{k}$. The $\ell_{2}$ operator norm of a matrix $M$ is denoted by
$\|M\|_{2}$ and its Frobenius norm by $\|M\|_{F}$. Its smallest singular value
is denoted by $\sigma_{\min}(M)$. For a vector $v$, we let $\|v\|_{2}$ its
Euclidean norm. Finally, for quantities that depend on the gradient flow time
$t$, we omit for concision their explicit dependence on $t$ when it is
dispensable.

##  3\. Lower bounds on the sharpness of minimizers

To define the sharpness of the model, we let $p=\sum_{k=1}^{L}d_{k}d_{k-1}$
and identify the space of parameters with ${\mathbb{R}}^{p}$, which amounts to
stacking all the entries of the weight matrices in a large $p$-dimensional
vector. Then the norm of the parameters seen as a $p$-dimensional vector can
be related to the Frobenius norm of the matrices by

$\|{\mathcal{W}}\|_{2}^{2}=\sum_{k=1}^{L}\|W_{k}\|_{F}^{2}\,.$

This allows us to define the Hessian of the risk
$H:{\mathbb{R}}^{p}\to{\mathbb{R}}^{p\times p}$, and we denote by
$S({\mathcal{W}})$ its largest eigenvalue for some parameters ${\mathcal{W}}$.
The following result gives two lower bounds on the sharpness of any minimizer
of the empirical risk (and is a strictly stronger statement than Theorem 1).

######  Theorem 2.

Under Assumption $(A_{1})$, for any ${\mathcal{W}}$ that minimizes
$R^{L}({\mathcal{W}})$, we have

$\displaystyle S({\mathcal{W}})\geqslant
2\lambda\|w^{\star}\|_{2}^{2-\frac{1}{L}}\sum_{k=1}^{L}\frac{1}{\|W_{k}\|_{F}}\,,$

and

$S({\mathcal{W}})\geqslant
S_{\min}=2L\lambda\|w^{\star}\|_{2}^{2-\frac{2}{L}}\,.$

The proof of the result relies on the following variational characterization
of the sharpness as the direction of the highest change of the gradient

$S({\mathcal{W}})^{2}=\lim_{\xi\to
0}\sup_{\|W_{k}-\tilde{W}_{k}\|_{F}\leqslant\xi}\frac{\sum_{k=1}^{L}\|\nabla_{k}R^{L}({\mathcal{W}})-\nabla_{k}R^{L}(\tilde{{\mathcal{W}}})\|_{F}^{2}}{\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{F}^{2}}\,.$
(7)

By considering the direction $\tilde{W}_{k}=(1+\xi\beta_{k})W_{k}$ for some
well-chosen $\beta_{k}\in{\mathbb{R}}$, the first lower bound can then be
proven. The bound shows that the sharpness of minimizers can be arbitrarily
high if one of the matrices has a low-enough norm. More precisely, take any
minimizer ${\mathcal{W}}=(W_{1},\dots W_{L})$ and consider
${\mathcal{W}}^{C}=(CW_{1},W_{2}/C,W_{3},\dots,W_{L})$, for some $C>0$. Then
${\mathcal{W}}^{C}$ is still a minimizer, and

$\displaystyle
S({\mathcal{W}}^{C})\geqslant\frac{2\lambda\|w^{\star}\|_{2}^{2-\frac{1}{L}}}{\|W_{2}/C\|_{F}}=\frac{2\lambda\|w^{\star}\|_{2}^{2-\frac{1}{L}}C}{\|W_{2}\|_{F}}\xrightarrow{C\to\infty}\infty.$

The fact that a reparameterization of the network can lead to arbitrarily high
sharpness is consistent with a similar result by Dinh et al. (2017) for two-
layer ReLU networks.

Note that the first lower bound is arbitrarily small for minimizers such that
the norms $\|W_{k}\|_{F}$ are large. This prompts us to prove the second part
of the result, which gives a uniform lower bound. The proof technique is
similar, but requires considering a rank-one direction of change from $W_{k}$,
that is $\tilde{W}_{k}=W_{k}+\xi\beta_{k}u_{k}v_{k}^{\top}$ for some
$\beta_{k}\in{\mathbb{R}},u_{k}\in{\mathbb{R}}^{d_{k}},v_{k}\in{\mathbb{R}}^{d_{k-1}}$.

As already noted by Mulayoff and Michaeli (2020), the intuition behind the
linear scaling of the bound with depth can be seen from a one-dimensional
example: take $f(x_{1},\dots,x_{L})=\prod_{k=1}^{L}x_{i}$. Then an easy
computation shows that the sharpness of $f$ at $(1,\dots,1)$ is equal to
$L-1$. This showcases a simple example where the output of $f$ is constant
with $L$ while its sharpness grows linearly with $L$.

##  4\. Analysis of gradient flow from small initialization

In this section, we characterize the structure of the minimizer found by
gradient flow starting from a small-scale initialization. The proof is
inspired by the one of Ji and Telgarsky (2020) for linearly-separable
classification, with a finer analysis due to the finiteness of minimizers in
our setting.

We consider the model (3) with $d_{L}=1$ and $w=1$. Denoting by $R_{0}$ the
empirical risk when the weight matrices are equal to zero, we can state our
main assumption for this section.

  * $(A_{2})$

The initialization satisfies that $R^{L}({\mathcal{W}}(0))\leqslant R_{0}$ and
$\nabla R^{L}({\mathcal{W}}(0))\neq 0$.

It is satisfied for instance if one of the weight matrices $W_{k}$ is equal to
zero at initialization while the others have i.i.d. Gaussian entries, so that
$R^{L}({\mathcal{W}}(0))=R_{0}$ and $\nabla_{k}R^{L}({\mathcal{W}}(0))\neq 0$
(almost surely).

Linear networks trained by gradient flow possess the following remarkable
property (Arora et al., 2018) that shall be useful in the remainder.

######  Lemma 1.

For any time $t\geqslant 0$ and any $k\in\\{1,\dots,L-1\\}$,

$W_{k+1}^{\top}(t)W_{k+1}(t)-W_{k+1}^{\top}(0)W_{k+1}(0)=W_{k}(t)W_{k}^{\top}(t)-W_{k}(0)W_{k}^{\top}(0)\,.$

Define now

$\displaystyle\varepsilon$ $\displaystyle:=3\max_{1\leqslant k\leqslant
L}\|W_{k}(0)\|_{F}^{2}+2\sum_{k=1}^{L-1}\|W_{k}(0)W_{k}^{\top}(0)-W_{k+1}^{\top}(0)W_{k+1}(0)\|_{2}\,.$

Note that $\varepsilon$ only depends on the initialization, and can be made
arbitrarily small by scaling down the initialization. The following key lemma
connects throughout training three key quantities to $\varepsilon$.

######  Lemma 2.

The parameters following gradient flow satisfy for any $t\geqslant 0$ that

  * •

for $k\in\\{1,\dots,L\\}$,
$\|W_{k}(t)\|_{F}^{2}-\|W_{k}(t)\|_{2}^{2}\leqslant\varepsilon\,,$

  * •

for $j,k\in\\{1,\dots,L\\}$,
$|\sigma_{k}^{2}(t)-\sigma_{j}^{2}(t)|\leqslant\varepsilon\,,$

  * •

for $k\in\\{1,\dots,L-1\\}$, $\displaystyle\langle
v_{k+1}(t),u_{k}(t)\rangle^{2}\geqslant
1-\frac{\varepsilon}{\sigma_{k+1}^{2}(t)}\,.$

The first identity of the Lemma bounds the sum of the squared singular values
of $W_{k}(t)$, except the largest one. In other words, it quantifies how close
$W_{k}(t)$ is to the rank-one approximation given by the first term in its
singular value decomposition. The second statement bounds the distance between
the spectral norms of any two weight matrices. The last bound quantifies the
alignment between the first left singular vector of $W_{k}(t)$ and the first
right singular vector of $W_{k+1}(t)$. In particular, if $\varepsilon$ is
small and $\sigma_{k+1}^{2}(t)$ is of order $1$, then $v_{k+1}(t)$ and
$u_{k}(t)$ are nearly aligned.

We next use this Lemma to show that the neural network satisfies a Polyak-
Łojasiewicz (PL) condition, which is one of the main tools to study non-convex
optimization dynamics (Rebjock and Boumal, 2023). A well-known result,
recalled in Appendix A for completeness, shows that this implies exponential
convergence of the gradient flow to the minimum of the empirical risk.

######  Theorem 3.

Under Assumptions $(A_{1})$–$(A_{2})$, the network satisfies the PL condition
for $t\geqslant 1$, in the sense that there exists some $\mu>0$ such that, for
$t\geqslant 1$,

$\sum_{k=1}^{L}\big{\|}\nabla_{k}R^{L}({\mathcal{W}}(t))\big{\|}_{F}^{2}\geqslant\mu(R^{L}({\mathcal{W}}(t))-R_{\min})\,.$

The proof leverages the structure of the gradient of the risk with respect to
the first weight matrix, which relies on the linearity of the neural network
and the fact that we consider a univariate output. More precisely, recall
that, by (5),

$\nabla_{1}R^{L}({\mathcal{W}}(t))=\underbrace{(W_{L}(t)\dots
W_{2}(t))^{\top}}_{d_{1}\times 1}\underbrace{\nabla
R^{1}(w_{\textnormal{prod}}(t))^{\top}}_{1\times d_{0}}\,.$

Therefore the Frobenius norm of the gradient decomposes as the product of two
vector norms

$\displaystyle\big{\|}\nabla_{1}R^{L}({\mathcal{W}}(t))\big{\|}_{F}^{2}$
$\displaystyle=\|W_{L}(t)\dots W_{2}(t)\|_{2}^{2}\|\nabla
R^{1}(w_{\textnormal{prod}}(t))\|_{2}^{2}$ $\displaystyle\geqslant
4\lambda\|W_{L}(t)\dots
W_{2}(t)\|_{2}^{2}(R^{L}({\mathcal{W}}(t))-R_{\min})\,,$

where the lower bound unfolds from a straightforward computation. The delicate
step is to lower bound $\|W_{L}(t)\dots W_{2}(t)\|_{2}$, which we approach by
distinguishing depending on the magnitude of $\sigma_{1}(t)=\|W_{1}(t)\|_{2}$.
If $\sigma_{1}(t)$ is large, we use Lemma 2 to deduce both that all
$\sigma_{k}(t)$ are large and then that the first singular vectors of
successive weight matrices are aligned. This implies that the product of
weight matrices has a large norm. To analyze the case where $\sigma_{1}(t)$ is
small, we use Assumption $(A_{2})$ to bound away $R^{L}({\mathcal{W}}(t))$
from $R_{0}$ for $t\geqslant 1$, and therefore $w_{\textnormal{prod}}(t)$ from
$0$. The fact that $w_{\textnormal{prod}}(t)$ cannot be too close to $0$ while
$\sigma_{1}(t)$ is small implies that $\|W_{L}(t)\dots W_{2}(t)\|_{2}$ is
large. All in all, this allows us to lower bound $\|W_{L}(t)\dots
W_{2}(t)\|_{2}$, and the PL condition follows.

Theorem 3 shows convergence of the risk to its minimum, and thus that
$w_{\textnormal{prod}}\to w^{\star}$. To characterize the weights at the end
of the training, we make the next assumption on the scale of initialization.

  * $(A_{3})$

We have $\varepsilon\leqslant 1$, $\|w^{\star}\|_{2}\geqslant 1$, and
$32L\sqrt{\varepsilon}\leqslant 1$.

The key condition in Assumption $(A_{3})$ is the last one, which means that
the initialization has to be scaled down as the depth increases, so that
$\varepsilon={\mathcal{O}}(1/L^{2})$. Combined with the fact that
$\|w_{\textnormal{prod}}\|_{2}\to\|w^{\star}\|_{2}$ and with Lemma 2, this can
be used to show the following corollary.

######  Corollary 1.

Under Assumptions $(A_{1})$–$(A_{3})$, there exists $T\geqslant 1$, such that,
for all $t\geqslant T$ and $k\in\\{1,\dots,L\\}$,

$\displaystyle\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}$
$\displaystyle\leqslant\sigma_{k}(t)\leqslant\big{(}2\|w^{\star}\|_{2}\big{)}^{1/L}\,.$

Together with Lemma 2, this result gives a precise description of the
structure of the weights at the end of the gradient flow trajectory. Up to the
small factor $\varepsilon$, the weights are rank-one matrices, with equal
norms and aligned singular vectors. Since the product of weights aligns with
$w^{\star}$, this means that the first right singular vector of $W_{1}$ has to
align with $w^{\star}$, and then the weight matrices align with their
neighbors in order to propagate the signal in the network.

Furthermore, this result has two main consequences. Since it shows that the
weights evolve in a ball of fixed radius, it can be combined with the PL
condition of Theorem 3 to deduce the convergence of the iterates (and not just
of the risk).

######  Corollary 2.

Under Assumptions $(A_{1})$–$(A_{3})$, the gradient flow dynamics (4) converge
to a global minimizer ${\mathcal{W}}^{\textnormal{SI}}$ of the risk.

Corollary 1 also implies that the operator norms of the weight matrices are
equal up to a constant factor, and are not much larger than
$\|w^{\star}\|_{2}^{1/L}$, which is the smallest norm possible to minimize the
risk if all matrices have the same norm. Combining this idea with the
variational characterization (7) of the sharpness and the explicit formulas
(5)–(6) for the gradients, we derive the following upper bound on the
sharpness of the found minimizer.

######  Corollary 3.

Under Assumptions $(A_{1})$–$(A_{3})$, the following bounds on the sharpness
of the minimizer ${\mathcal{W}}^{\textnormal{SI}}$ hold:

$1\leqslant\frac{S({\mathcal{W}}^{\textnormal{SI}})}{S_{\min}}\leqslant
4\frac{\Lambda}{\lambda}\,.$

This result shows that the sharpness of the minimizer is close to $S_{\min}$
in the sense that their ratio is bounded by a constant times the condition
number of $\hat{\Sigma}$. For example, in the case of white data
($\hat{\Sigma}=I$), we obtain that
$S({\mathcal{W}}^{\textnormal{SI}})\leqslant 4S_{\min}$.

##  5\. Analysis of gradient flow from residual initialization

We now study the case of residual initialization. We consider a linear network
of the form (3) with

$W_{k}(t)=I+\frac{s}{\sqrt{Ld}}N_{k}+\frac{1}{L}\theta_{k}(t)\,,$

where each matrix is a $d\times d$ matrix and the $N_{k}$ are filled with
i.i.d. Gaussian entries ${\mathcal{N}}(0,1)$. We refer to Section 1 for a
discussion of the scaling factor in front of $N_{k}$. Following the standard
initialization of residual networks, we assume that the $\theta_{k}$ are
initialized to zero. Note that the scaling factor $1/L$ in front of the
$\theta_{k}$ has no impact on the dynamics; it is convenient for exposition
and computations, since we show that, with this scaling factor, the
$\theta_{k}$ are of order ${\mathcal{O}}(1)$ after training.

Before stating the main result of this section on the convergence of the
gradient flow, recall that $w\in{\mathbb{R}}^{d}$ is a fixed vector appended
at the end of the residual network to project its output back in
${\mathbb{R}}$.

######  Theorem 4.

Under Assumption $(A_{1})$, there exist $C_{1},\dots,C_{5}>0$ depending only
on $s$ such that, if

$L\geqslant C_{1}\,,\quad d\geqslant C_{2}\,,\quad
R^{L}({\mathcal{W}}(0))-R_{\min}\leqslant\frac{C_{3}\lambda^{2}\|w\|_{2}^{2}}{\Lambda}\,,$

then, with probability at least

$1-16\exp(-C_{4}d)\,,$

the gradient flow dynamics (4) converge to a global minimizer
${\mathcal{W}}^{\textnormal{RI}}$ of the risk. Furthermore, the minimizer
${\mathcal{W}}^{\textnormal{RI}}$ satisfies

$W_{k}^{\textnormal{RI}}=I+\frac{s}{\sqrt{Ld}}N_{k}+\frac{1}{L}\theta_{k}^{\textnormal{RI}}\quad\textnormal{with}\quad\|\theta_{k}^{\textnormal{RI}}\|_{F}\leqslant
C_{5}\,,\quad 1\leqslant k\leqslant L\,.$ (8)

To our knowledge, Theorem 4 is the first result showing convergence of
gradient flow for standard Gaussian initialization of residual networks
without assuming overparameterization. The main requirement is that the loss
at initialization be not too large, as is standard in the literature analyzing
gradient flow for deep linear residual networks (Bartlett et al., 2018; Arora
et al., 2019a; Zou et al., 2020; Sander et al., 2022). Note that our bound on
the loss at initialization does not depend on the width $d$, depth $L$, or
sample size $n$. We emphasize that the same proof holds for multivariate
regression, in the absence of the projection vector $w$, which we employ in
the current exposition to connect this result with the analysis of sharpness
for univariate regression in Section 3. Details on adaptation to multivariate
regression are given in Appendix B.8. Finally, the precise dependence of
$C_{1}$ to $C_{4}$ on $s$ can be found in the proof.

The proof is a refinement of the analysis for identity initialization of
residual networks (Zou et al., 2020; Sander et al., 2022). From the expression
of the gradients (5), we can show that

$\displaystyle 4\Lambda\|w\|_{2}^{2}\|\Pi_{L:k+1}\|_{2}^{2}$
$\displaystyle\|\Pi_{k-1:1}\|_{2}^{2}(R({\mathcal{W}})-R_{\min})$
$\displaystyle\geqslant\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}^{2}\geqslant
4\lambda\|w\|_{2}^{2}\sigma_{\min}^{2}(\Pi_{L:k+1})\sigma_{\min}^{2}(\Pi_{k-1:1})(R({\mathcal{W}})-R_{\min})\,,$

with $\Pi_{L:k}:=W_{L}\dots W_{k}$ and $\Pi_{k:1}:=W_{k}\dots W_{1}$. Letting

$t^{*}=\inf\big{\\{}t\in{\mathbb{R}}_{+},\exists
k\in\\{1,\dots,L\\},\|\theta_{k}(t)\|_{F}>C_{5}\big{\\}}\,,$

the crucial step is to lower bound $\sigma_{\min}^{2}(\Pi_{L:k+1})$ and
$\sigma_{\min}^{2}(\Pi_{k-1:1})$ uniformly for $t\in[0,t^{\star}]$, in order
to get a PL condition valid for $t\in[0,t^{\star}]$. Then, the condition on
the loss at initialization is used to prove that $t^{\star}=\infty$, thereby
the PL condition holds for all $t\geqslant 0$. We deduce both convergence and
the bound on the norm of $\theta_{k}^{\textnormal{RI}}$. The lower bound on
$\sigma_{\min}^{2}(\Pi_{L:k+1})$ and $\sigma_{\min}^{2}(\Pi_{k-1:1})$ is
straightforward in the case of an identity initialization. In the case of
Gaussian initialization, the proof is more intricate, and leverages the
following high probability bounds on the singular values of residual networks.

######  Lemma 3.

There exist $C_{1},\dots,C_{4}>0$ depending only on $s$ such that, if

$L\geqslant C_{1}\,,\quad d\geqslant C_{2}\,,\quad
u\in[C_{3},C_{4}L^{1/4}]\,,$

then, with probability at least

$1-8\exp\Big{(}-\frac{du^{2}}{32s^{2}}\Big{)}\,,$

it holds for all $\theta$ such that $\max_{1\leqslant k\leqslant
L}\|\theta_{k}\|_{2}\leqslant\frac{1}{64}\exp(-2s^{2}-4u)$ and all
$k\in\\{1,\dots,L\\}$ that

$\Big{\|}\Big{(}I+\frac{s}{\sqrt{Ld}}N_{k}+\frac{1}{L}\theta_{k}\Big{)}\dots\Big{(}I+\frac{s}{\sqrt{Ld}}N_{1}+\frac{1}{L}\theta_{1}\Big{)}\Big{\|}_{2}\leqslant
4\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\,,$

and

$\sigma_{\min}\Big{(}\Big{(}I+\frac{s}{\sqrt{Ld}}N_{k}+\frac{1}{L}\theta_{k}\Big{)}\dots\Big{(}I+\frac{s}{\sqrt{Ld}}N_{1}+\frac{1}{L}\theta_{1}\Big{)}\Big{)}\geqslant\frac{1}{4}\exp\Big{(}-\frac{2s^{2}}{d}-u\Big{)}\,.$

The proof of this result goes in three steps. We first study the evolution of
the norm of the activations across the layers of the residual network when
$\theta=0$, and prove a high-probability bound by leveraging concentration
inequalities for Gaussian and $\chi^{2}$ distributions. Then an
$\varepsilon$-net argument allows to bound the singular values. Finally, the
extension to $\theta$ in a ball around $0$ is done via a perturbation
analysis. The proof technique is related to previous works (Marion et al.,
2022; Zhang et al., 2022), but provides a crisper and sounder bound. More
precisely, Marion et al. (2022) show a bound on the norm of the activations
with a probability of failure that decays polynomially with the width $d$,
which is not sufficient to apply the $\varepsilon$-net argument that requires
an exponentially decreasing probability of failure. As for Zhang et al.
(2022), they provide a similar bound with the purpose of showing convergence
of wide residual networks, however with a less sharp probability of failure
that increases polynomially with depth.111We further note an incorrect use of
concentration inequalities for $\chi^{2}$ distributions that are assumed to be
sub-Gaussian while they are in fact only sub-exponential. Details are given in
Appendix B.9.  Finally, as previously, the dependence of $C_{1}$ to $C_{4}$ on
$s$ can be found in the proof.

The characterization (8) of the minimizer in Theorem 4 allows to bound its
sharpness, as made precise by the following corollary. It holds under the same
assumptions and high-probability bound as the conclusion of Theorem 4.

######  Corollary 4.

Under the assumptions of Theorem 4, there exists $C>0$ depending only on $s$
such that the following bounds on the sharpness of the minimizer
${\mathcal{W}}^{\textnormal{RI}}$ hold:

$1\leqslant\frac{S({\mathcal{W}}^{\textnormal{RI}})}{S_{\min}}\leqslant
C\|w^{\star}\|_{2}^{2/L}\frac{\Lambda}{\lambda}\,.$

As for Corollary 3, the proof relies on the fact that the norms of the weight
matrices are close to each other and to the smallest possible norm to minimize
the risk. This result shows again an implicit regularization towards a low-
sharpness minimizer. Experimental illustration and connection with gradient
descent with non-vanishing learning rate is provided in Appendix C.

##  6\. Conclusion

This paper studies dynamics of gradient flow for deep linear networks on a
regression task. For small-scale initialization, we prove that the learned
weight matrices are approximately rank-one and that their singular vectors
align. For residual initialization, convergence of the gradient flow for a
Gaussian initialization is proven. In both cases, we obtain that the sharpness
of the solution found by gradient flow is close to the smallest sharpness
among all minimizers. Interesting next steps include studying the dynamics at
any initialization scale, as well as extension to non-linear networks.

## Acknowledgments

Authors thank Matus Telgarsky for insightful discussions, and Eloïse Berthier
and Guillaume Dalle for thoughtful proofreading and remarks.

## References

  * Advani et al. (2020) M. S. Advani, A. M. Saxe, and H. Sompolinsky.  High-dimensional dynamics of generalization error in neural networks.  _Neural Networks_ , 132:428–446, 2020.
  * Agarwala et al. (2023) A. Agarwala, F. Pedregosa, and J. Pennington.  Second-order regression models exhibit progressive sharpening to the edge of stability.  In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 169–195. PMLR, 23–29 Jul 2023.
  * Andriushchenko et al. (2023) M. Andriushchenko, F. Croce, M. Müller, M. Hein, and N. Flammarion.  A modern look at the relationship between sharpness and generalization.  In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 840–902. PMLR, 23–29 Jul 2023.
  * Arora et al. (2018) S. Arora, N. Cohen, and E. Hazan.  On the optimization of deep networks: Implicit acceleration by overparameterization.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 244–253. PMLR, 10–15 Jul 2018.
  * Arora et al. (2019a) S. Arora, N. Cohen, N. Golowich, and W. Hu.  A convergence analysis of gradient descent for deep linear neural networks.  In _International Conference on Learning Representations_ , 2019a.
  * Arora et al. (2019b) S. Arora, N. Cohen, W. Hu, and Y. Luo.  Implicit regularization in deep matrix factorization.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019b.
  * Arpit et al. (2019) D. Arpit, V. Campos, and Y. Bengio.  How to initialize your network? Robust initialization for WeightNorm & ResNets.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32, pages 10902–10911. Curran Associates, Inc., 2019\.
  * Bartlett et al. (2018) P. Bartlett, D. Helmbold, and P. Long.  Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 521–530. PMLR, 10–15 Jul 2018.
  * Blanc et al. (2020) G. Blanc, N. Gupta, G. Valiant, and P. Valiant.  Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process.  In J. Abernethy and S. Agarwal, editors, _Proceedings of Thirty Third Conference on Learning Theory_ , volume 125 of _Proceedings of Machine Learning Research_ , pages 483–513. PMLR, 09–12 Jul 2020.
  * Bradbury et al. (2018) J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang.  JAX: composable transformations of Python+NumPy programs, 2018\.  URL http://github.com/google/jax.
  * Cohen et al. (2021) J. Cohen, S. Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar.  Gradient descent on neural networks typically occurs at the edge of stability.  In _International Conference on Learning Representations_ , 2021.
  * Damian et al. (2021) A. Damian, T. Ma, and J. D. Lee.  Label noise SGD provably prefers flat global minimizers.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 27449–27461. Curran Associates, Inc., 2021.
  * Damian et al. (2023) A. Damian, E. Nichani, and J. D. Lee.  Self-stabilization: The implicit bias of gradient descent at the edge of stability.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * De and Smith (2020) S. De and S. Smith.  Batch normalization biases residual blocks towards the identity function in deep networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 19964–19975. Curran Associates, Inc., 2020.
  * Dinh et al. (2017) L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio.  Sharp minima can generalize for deep nets.  In D. Precup and Y. W. Teh, editors, _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1019–1028. PMLR, 06–11 Aug 2017.
  * Ghosh (2021) M. Ghosh.  Exponential tail bounds for chisquared random variables.  _Journal of Statistical Theory and Practice_ , 15(2):35, 2021.
  * Gidel et al. (2019) G. Gidel, F. Bach, and S. Lacoste-Julien.  Implicit regularization of discrete gradient dynamics in linear neural networks.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Glorot and Bengio (2010) X. Glorot and Y. Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In Y. Teh and M. Titterington, editors, _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , volume 9 of _Proceedings of Machine Learning Research_ , pages 249–256. PMLR, 2010.
  * Gunasekar et al. (2017) S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro.  Implicit regularization in matrix factorization.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * He et al. (2015) K. He, X. Zhang, S. Ren, and J. Sun.  Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 1026–1034. IEEE Computer Society, 2015.
  * Hochreiter and Schmidhuber (1997) S. Hochreiter and J. Schmidhuber.  Flat minima.  _Neural Computation_ , 9(1):1–42, 1997.
  * Ioffe and Szegedy (2015) S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In F. Bach and D. Blei, editors, _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 448–456. PMLR, 2015.
  * Jacot et al. (2021) A. Jacot, F. Ged, B. Şimşek, C. Hongler, and F. Gabriel.  Saddle-to-saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity.  _arXiv preprint arXiv:2106.15933_ , 2021.
  * Jastrzębski et al. (2017) S. Jastrzębski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey.  Three factors influencing minima in SGD.  _arXiv preprint arXiv:1711.04623_ , 2017.
  * Ji and Telgarsky (2020) Z. Ji and M. Telgarsky.  Directional convergence and alignment in deep learning.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 17176–17186. Curran Associates, Inc., 2020.
  * Jiang et al. (2020) Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio.  Fantastic generalization measures and where to find them.  In _International Conference on Learning Representations_ , 2020.
  * Keskar et al. (2017) N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang.  On large-batch training for deep learning: Generalization gap and sharp minima.  In _International Conference on Learning Representations_ , 2017.
  * Lampinen and Ganguli (2019) A. K. Lampinen and S. Ganguli.  An analytic theory of generalization dynamics and transfer learning in deep linear networks.  In _International Conference on Learning Representations_ , 2019.
  * Lewkowycz et al. (2020) A. Lewkowycz, Y. Bahri, E. Dyer, J. Sohl-Dickstein, and G. Gur-Ari.  The large learning rate phase of deep learning: the catapult mechanism.  _arXiv preprint arXiv:2003.02218_ , 2020.
  * Li et al. (2021) Z. Li, Y. Luo, and K. Lyu.  Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning.  In _International Conference on Learning Representations_ , 2021.
  * Li et al. (2022) Z. Li, T. Wang, and S. Arora.  What happens after SGD reaches zero loss? –a mathematical framework.  In _International Conference on Learning Representations_ , 2022.
  * Liu et al. (2023) H. Liu, S. M. Xie, Z. Li, and T. Ma.  Same pre-training loss, better downstream: Implicit bias matters for language models.  In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 22188–22214. PMLR, 23–29 Jul 2023.
  * MacDonald et al. (2023) L. E. MacDonald, J. Valmadre, and S. Lucey.  On progressive sharpening, flat minima and generalisation.  _arXiv preprint arXiv:2305.14683_ , 2023.
  * Marion et al. (2022) P. Marion, A. Fermanian, G. Biau, and J.-P. Vert.  Scaling ResNets in the large-depth regime.  _arXiv preprint arXiv:2206.06929_ , 2022.
  * Marion et al. (2024) P. Marion, Y.-H. Wu, M. E. Sander, and G. Biau.  Implicit regularization of deep residual networks towards neural ODEs.  In _The Twelfth International Conference on Learning Representations_ , 2024.
  * Michel Petrovitch (1901) M. Michel Petrovitch.  Sur une manière d’étendre le théorème de la moyenne aux équations différentielles du premier ordre.  _Mathematische Annalen_ , 54(3):417–436, 1901\.
  * Mulayoff and Michaeli (2020) R. Mulayoff and T. Michaeli.  Unique properties of flat minima in deep networks.  In H. D. III and A. Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 7108–7118. PMLR, 13–18 Jul 2020.
  * Nesterov (2018) Y. Nesterov.  _Lectures on Convex Optimization_.  Springer Optimization and Its Applications. Springer Cham, 2nd edition, 2018.
  * Neyshabur et al. (2017) B. Neyshabur, S. Bhojanapalli, D. Mcallester, and N. Srebro.  Exploring generalization in deep learning.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Rebjock and Boumal (2023) Q. Rebjock and N. Boumal.  Fast convergence to non-isolated minima: four equivalent conditions for $\mathrm{C}^{2}$ functions.  _arXiv preprint arXiv:2303.00096_ , 2023.
  * Sander et al. (2022) M. E. Sander, P. Ablin, and G. Peyré.  Do residual neural networks discretize neural ordinary differential equations?  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 36520–36532. Curran Associates, Inc., 2022.
  * Saxe et al. (2014) A. Saxe, J. McClelland, and S. Ganguli.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks.  In _International Conference on Learning Representations_ , 2014.
  * Saxe et al. (2019) A. M. Saxe, J. L. McClelland, and S. Ganguli.  A mathematical theory of semantic development in deep neural networks.  _Proceedings of the National Academy of Sciences_ , 116(23):11537–11546, 2019.
  * Smith and Le (2018) S. L. Smith and Q. V. Le.  A bayesian perspective on generalization and stochastic gradient descent.  In _International Conference on Learning Representations_ , 2018.
  * Timor et al. (2023) N. Timor, G. Vardi, and O. Shamir.  Implicit regularization towards rank minimization in ReLU networks.  In S. Agrawal and F. Orabona, editors, _Proceedings of The 34th International Conference on Algorithmic Learning Theory_ , volume 201 of _Proceedings of Machine Learning Research_ , pages 1429–1459. PMLR, 20 Feb–23 Feb 2023.
  * Varre et al. (2023) A. V. Varre, M.-L. Vladarean, L. Pillaud-Vivien, and N. Flammarion.  On the spectral bias of two-layer linear networks.  In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 64380–64414. Curran Associates, Inc., 2023.
  * Vershynin (2018) R. Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
  * Wang et al. (2022) Z. Wang, Z. Li, and J. Li.  Analyzing sharpness along GD trajectory: Progressive sharpening and edge of stability.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 9983–9994. Curran Associates, Inc., 2022.
  * Wu et al. (2024) J. Wu, P. L. Bartlett, M. Telgarsky, and B. Yu.  Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency.  _arXiv preprint arXiv:2402.15926_ , 2024.
  * Yun et al. (2021) C. Yun, S. Krishnan, and H. Mobahi.  A unifying view on implicit bias in training linear neural networks.  In _International Conference on Learning Representations_ , 2021.
  * Zhang et al. (2022) H. Zhang, D. Yu, M. Yi, W. Chen, and T.-Y. Liu.  Stabilize deep ResNet with a sharp scaling factor $\tau$.  _Machine Learning_ , 111(9):3359–3392, 2022.
  * Zou et al. (2020) D. Zou, P. M. Long, and Q. Gu.  On the global convergence of training deep linear ResNets.  In _International Conference on Learning Representations_ , 2020.

Appendix

Organization of the Appendix. Appendix A presents some useful preliminary
lemmas. The proofs of the results of the main paper are presented in Appendix
B, while additional plots and experimental details are given in Appendix C.
Finally, Appendix D discusses some additional related work.

##  Appendix A Technical lemmas

######  Lemma 4.

For $\alpha>0$ and $x\in[0,\nicefrac{{1}}{{2}}]$,

$(1-x)^{\alpha}\geqslant 1-2\alpha x\,.$

For $\alpha>0$ and $x>0$ such that $\alpha x\leqslant 1$,

$(1+x)^{\alpha}\leqslant 1+2\alpha x\,.$

###### Proof.

Regarding the first inequality of the Lemma, we have

$\displaystyle(1-x)^{\alpha}$
$\displaystyle=\exp(\alpha\log(1-x))\geqslant\exp(\alpha(-2x))\geqslant
1-2\alpha x\,,$

where the first inequality holds for $x\in[0,\nicefrac{{1}}{{2}}]$. The second
inequality of the Lemma is proven by

$(1+x)^{\alpha}=\exp(\alpha\log(1+x))\leqslant\exp(\alpha x)\leqslant
1+2\alpha x\,,$

where the second inequality holds when $\alpha x\leqslant 1$. ∎

######  Lemma 5.

There exists an absolute constant $C>0$ such that, for $L\geqslant C$ and
$x\geqslant 1$,

$L\exp(-\sqrt{L}x)\leqslant 4\exp(-x)\,.$

###### Proof.

For any $x\in{\mathbb{R}}$,

$\displaystyle L\exp(-\sqrt{L}x)\leqslant 4\exp(-x)$
$\displaystyle\Leftrightarrow\exp((\sqrt{L}-1)x)\geqslant\frac{L}{4}\,.$

Then, for $L\geqslant 1$ and $x\geqslant 1$, we have

$\displaystyle\exp((\sqrt{L}-1)x)$ $\displaystyle\geqslant
1+(\sqrt{L}-1)x+\frac{1}{2}(\sqrt{L}-1)^{2}x^{2}$
$\displaystyle=1+(\sqrt{L}-1)x+\frac{1}{2}(L+1-2\sqrt{L})x^{2}$
$\displaystyle\geqslant(\sqrt{L}-1)x+\frac{L}{4}+\frac{1}{2}(\frac{L}{2}+1-2\sqrt{L})x^{2}$

For $L$ large enough, $\frac{L}{2}+1-2\sqrt{L}\geqslant 0$. Thus, since
$x\geqslant 1$,

$\displaystyle\exp((\sqrt{L}-1)x)$
$\displaystyle\geqslant(\sqrt{L}-1)x+\frac{L}{4}+\frac{1}{2}(\frac{L}{2}+1-2\sqrt{L})x$
$\displaystyle=\frac{L}{4}+(\frac{L}{4}-\frac{1}{2})x$
$\displaystyle\geqslant\frac{L}{4}\,,$

where the last inequality holds for $L$ large enough. This concludes the
proof. ∎

######  Lemma 6.

Let $h\in{\mathbb{R}}^{d}$, $N\in{\mathbb{R}}^{d\times d}$ with i.i.d.
standard Gaussian entries, and

$Y_{1}=\frac{\|Nh\|_{2}^{2}}{\|h\|_{2}^{2}}\,,\quad
Y_{2}=\frac{h^{\top}Nh}{\|h\|_{2}^{2}}\,,$

Then

$Y_{1}\sim\chi^{2}(d)\quad\textnormal{and}\quad
Y_{2}\sim{\mathcal{N}}(0,1)\,.$

###### Proof.

We have, for $i\in\\{1,\dots,d\\}$,

$(Nh)_{i}=\sum_{j=1}^{d}N_{ij}h_{j}\,.$

By independence of the $(N_{ij})_{1\leqslant j\leqslant d}$, we deduce that
$(Nh)_{i}$ follows a ${\mathcal{N}}(0,\|h\|^{2})$ distribution. Furthermore,
by independence of the rows of $N$, the $(Nh)_{i}$ are independent. Thus

$\displaystyle Y_{1}=\frac{1}{\|h\|^{2}}\sum_{i=1}^{d}(Nh)_{i}^{2}$

follows a $\chi^{2}(d)$ distribution. Moving on to $Y_{2}$, we have

$Y_{2}=\frac{1}{\|h\|^{2}}\sum_{i,j=1}^{d}N_{ij}h_{i}h_{j}\,.$

Thus $Y_{2}$ follows a centered Gaussian distribution, and by independence of
the $(N_{ij})_{1\leqslant i,j\leqslant d}$, its variance is equal to

$\frac{1}{\|h\|^{4}}\sum_{i,j=1}^{d}h_{i}^{2}h_{j}^{2}=1\,,$

which concludes the proof. ∎

The next lemma shows that the PL condition implies exponential convergence of
the gradient flow. It is a well-known fact (see, e.g., Rebjock and Boumal,
2023, for an overview of similar conditions), proved here for completeness.

######  Lemma 7.

Let $f:{\mathbb{R}}^{p}\to{\mathbb{R}}$ be a differentiable function lower
bounded by $f_{\min}\in{\mathbb{R}}$, and consider the gradient flow dynamics

$\frac{dx}{dt}=-\nabla f(x(t))\,.$

If $f$ satisfies the Polyak-Łojasiewicz inequality for $t\geqslant 0$

$\|\nabla f(x(t))\|_{2}\geqslant\mu(f(x(t))-f_{\min})\,,$

then, for $t\geqslant 0$,

$f(x(t))-f_{\min}\leqslant(f(x(0))-f_{\min})e^{-\mu t}\,.$

###### Proof.

By the chain rule,

$\displaystyle\frac{d}{dt}f(x(t))=\Big{\langle}\nabla
f(x(t)),\frac{dx}{dt}\Big{\rangle}=-\|\nabla f(x(t))\|_{2}^{2}\,.$

Plugging in the Polyak-Łojasiewicz inequality,

$\frac{d}{dt}f(x(t))\leqslant-\mu(f(x(t))-f_{\min})\,.$

Thus

$\frac{d}{dt}(f(x(t))-f_{\min})\leqslant-\mu(f(x(t))-f_{\min})\,.$

To solve this differential inequality, one can for instance use the comparison
theorem (Michel Petrovitch, 1901), which states that $f(x(t))-f_{\min}$ is
smaller that the solution $g$ of the initial value problem

$g(0)=f(x(0))-f_{\min}\,,\quad\frac{d}{dt}g(t)=-\mu g(t)\,.$

This gives the conclusion of the Lemma. ∎

######  Lemma 8.

With the notation introduced in Section 2, the following identities holds

$R^{L}({\mathcal{W}})=R_{\min}+\frac{1}{n}\|X(w^{\star}-w_{\textnormal{prod}})\|_{2}^{2}\,,$

and

$4\lambda(R^{L}({\mathcal{W}})-R_{\min})\leqslant\|\nabla
R^{1}(w_{\textnormal{prod}})\|^{2}\leqslant
4\Lambda(R^{L}({\mathcal{W}})-R_{\min})\,.$

###### Proof.

We have

$\displaystyle R^{L}({\mathcal{W}})$
$\displaystyle=\frac{1}{n}\|y-Xw_{\textnormal{prod}}\|_{2}^{2}$
$\displaystyle=\frac{1}{n}\|y-Xw^{\star}+X(w^{\star}-w_{\textnormal{prod}})\|_{2}^{2}$
$\displaystyle=\frac{1}{n}\|y-Xw^{\star}\|_{2}+\frac{1}{n}\|X(w^{\star}-w_{\textnormal{prod}})\|_{2}^{2}+\frac{2}{n}\big{\langle}y-Xw^{\star},X(w^{\star}-w_{\textnormal{prod}})\big{\rangle}$
$\displaystyle=R_{\min}+\frac{1}{n}\|X(w^{\star}-w_{\textnormal{prod}})\|_{2}^{2}+\frac{2}{n}\big{\langle}X^{\top}(y-Xw^{\star}),w^{\star}-w_{\textnormal{prod}}\big{\rangle}\,,$

where the scalar product is equal to zero by the characterization of
$w^{\star}$ given in Section 2. This gives the first identity of the Lemma.
Next,

$\displaystyle R^{L}({\mathcal{W}})-R_{\min}$
$\displaystyle=\frac{1}{n}(w^{\star}-w_{\textnormal{prod}})^{\top}X^{\top}X(w^{\star}-w_{\textnormal{prod}})$
$\displaystyle\leqslant\frac{1}{n}\|w^{\star}-w_{\textnormal{prod}}\|_{2}\|X^{\top}X(w^{\star}-w_{\textnormal{prod}})\|_{2}\,.$

By the formula (6) for the gradient of $R^{1}$,

$\displaystyle\|\nabla R^{1}(w_{\textnormal{prod}})\|_{2}$
$\displaystyle=\frac{2}{n}\|X^{\top}X(w^{\star}-w_{\textnormal{prod}})\|_{2}\geqslant
2\lambda\|w^{\star}-w_{\textnormal{prod}}\|_{2}\,.$

Plugging in the formula above, we obtain that

$R^{L}({\mathcal{W}})-R_{\min}\leqslant\frac{1}{2\lambda}\|\nabla
R^{1}(w_{\textnormal{prod}})\|_{2}\cdot\frac{1}{2}\|\nabla
R^{1}(w_{\textnormal{prod}})\|_{2}=\frac{1}{4\lambda}\|\nabla
R^{1}(w_{\textnormal{prod}})\|_{2}^{2}\,.$

Finally, to obtain the upper bound on the gradient, note that

$\displaystyle\|\nabla R^{1}(w_{\textnormal{prod}})\|_{2}^{2}$
$\displaystyle=\frac{4}{n^{2}}\|X^{\top}X(w^{\star}-w_{\textnormal{prod}})\|_{2}^{2}$
$\displaystyle=\frac{4}{n^{2}}(w^{\star}-w_{\textnormal{prod}})^{\top}X^{\top}XX^{\top}X(w^{\star}-w_{\textnormal{prod}})$
$\displaystyle\leqslant\frac{4\Lambda}{n}(w^{\star}-w_{\textnormal{prod}})^{\top}X^{\top}X(w^{\star}-w_{\textnormal{prod}})$
$\displaystyle=4\Lambda(R^{L}({\mathcal{W}})-R_{\min})\,.$

∎

######  Lemma 9.

Take $W_{1},\dots W_{L}\in{\mathbb{R}}^{d\times d}$ such that, for all
$k\in\\{1,\dots,L\\}$,

$\|W_{k}\dots W_{1}\|_{2}\leqslant M\,,$

and

$\sigma_{\min}(W_{k}\dots W_{1})\geqslant m\,,$

where $M\geqslant 1$ and $m\in(0,1)$. Then, for all $\theta$ such that
$\max_{1\leqslant k\leqslant
L}\|\theta_{k}\|_{2}\leqslant\frac{m^{2}}{4M^{2}}$, letting
$\tilde{W}_{k}=W_{k}+\frac{\theta_{k}}{L}$, we have

$\|\tilde{W}_{k}\dots\tilde{W}_{1}\|_{2}\leqslant 2M\,,$

and

$\sigma_{\min}(\tilde{W}_{k}\dots\tilde{W}_{1})\geqslant\frac{m}{2}\,.$

###### Proof.

First note that the assumptions imply that, for any $1\leqslant j<k\leqslant
L$,

$\|W_{k}\dots W_{j+1}\|_{2}\leqslant\frac{\|W_{k}\dots W_{j+1}W_{j}\dots
W_{1}\|_{2}}{\sigma_{\min}(W_{j}\dots W_{1})}=\frac{\|W_{k}\dots
W_{1}\|_{2}}{\sigma_{\min}(W_{j}\dots W_{1})}\leqslant\frac{M}{m}\,.$ (9)

It shall come in handy to extend this formula to the case where $j=k$, where
we define the empty matrix product to be equal to the identity matrix, which
has an operator norm of $1\leqslant\frac{M}{m}$.

Now, take any $\theta$ as in the Lemma and any $h_{0}\in{\mathbb{R}}^{d}$.
Let, for $k\geqslant 0$,

$h_{k}=W_{k}\dots W_{1}h_{0}\,,$

and

$\tilde{h}_{k}=\tilde{W}_{k}\dots\tilde{W}_{1}h_{0}\,.$

Then

$h_{k}=W_{k}h_{k-1}$

and

$\tilde{h}_{k}=\Big{(}W_{k}+\frac{\theta_{k}}{L}\Big{)}\tilde{h}_{k-1}\,.$

Thus

$\tilde{h}_{k}-h_{k}=\frac{\theta_{k}}{L}\tilde{h}_{k-1}+W_{k}(\tilde{h}_{k-1}-h_{k-1})\,.$

Since $\tilde{h}_{0}-h_{0}=0$, we get by recurrence that, for $k\geqslant 1$,

$\tilde{h}_{k}-h_{k}=\sum_{j=1}^{k}W_{k}\dots
W_{j+1}\frac{\theta_{j}}{L}\tilde{h}_{j-1}\,.$ (10)

From there, let us prove by recurrence that

$\|\tilde{h}_{k}\|_{2}\leqslant 2M\|\tilde{h}_{0}\|_{2}\,.$ (11)

This equation holds for $k=0$ since $M\geqslant 1$. Next, assume that it holds
up to a certain rank $k-1$, and let us prove it at rank $k$. From (10), we get
that

$\|\tilde{h}_{k}-h_{k}\|_{2}\leqslant\frac{1}{L}\sum_{j=1}^{k}\|W_{k}\dots
W_{j+1}\|_{2}\|\theta_{j}\|_{2}\|\tilde{h}_{j-1}\|_{2}\,.$ (12)

Since $M\geqslant 1$ and $m<1$, the bound on $\|\theta_{j}\|_{2}$ from the
assumptions of the Lemma implies in particular that
$\|\theta_{j}\|_{2}\leqslant\frac{m}{2M}$. Utilizing this, as well as (9) and
the recurrence hypothesis (11) up to rank $k-1$, we get

$\|\tilde{h}_{k}-h_{k}\|_{2}\leqslant\frac{1}{L}\sum_{j=1}^{k}\frac{M}{m}\cdot\frac{m}{2M}\cdot
2M\|\tilde{h}_{0}\|_{2}\leqslant M\|\tilde{h}_{0}\|_{2}\,.$

Then

$\|\tilde{h}_{k}\|_{2}\leqslant\|h_{k}\|_{2}+\|\tilde{h}_{k}-h_{k}\|_{2}\leqslant\|W_{k}\dots
W_{1}\|_{2}\|h_{0}\|_{2}+M\|\tilde{h}_{0}\|_{2}\leqslant
2M\|\tilde{h}_{0}\|_{2}\,.$

This concludes the proof of the recurrence hypothesis at rank $k$. We
therefore get that

$\|\tilde{W}_{k}\dots\tilde{W}_{1}\|_{2}\leqslant 2M\,.$

To prove the lower bound on the smallest singular value of
$\tilde{W}_{k}\dots\tilde{W}_{1}$, observe that

$\displaystyle\|\tilde{h}_{k}\|_{2}$
$\displaystyle\geqslant\|h_{k}\|_{2}-\|\tilde{h}_{k}-h_{k}\|_{2}$
$\displaystyle\geqslant\sigma_{\min}(W_{k}\dots
W_{1})\|h_{0}\|_{2}-\frac{1}{L}\sum_{j=1}^{k}\|W_{k}\dots
W_{j+1}\|_{2}\|\theta_{j}\|_{2}\|\tilde{h}_{j-1}\|_{2}\,,$

by (12). Finally, by (9), the bound on $\|\theta_{j}\|_{2}$ from the
assumptions, and the upper bound we just proved on $\|\tilde{h}_{j-1}\|_{2}$,
we have

$\|\tilde{h}_{k}\|_{2}\geqslant
m\|h_{0}\|_{2}-\frac{1}{L}\sum_{j=1}^{k}\frac{M}{m}\cdot\frac{m^{2}}{4M^{2}}\cdot
2M\|h_{0}\|_{2}\geqslant\frac{m}{2}\|h_{0}\|_{2}\,.$

This concludes the proof. ∎

##  Appendix B Proofs

###  B.1. Proof of Theorem 2

For a twice continuously differentiable function
$f:{\mathbb{R}}^{p}\to{\mathbb{R}}$, the largest eigenvalue $S$ of its Hessian
$H(f):{\mathbb{R}}^{p}\to{\mathbb{R}}^{p\times p}$ at some
$x\in{\mathbb{R}}^{p}$ admits the variational characterization

$S(x)=\lim_{\xi\to 0}\sup_{\|x-\tilde{x}\|\leqslant\xi}\frac{\|\nabla
f(x)-\nabla f(\tilde{x})\|_{2}}{\|x-\tilde{x}\|_{2}}\,.$

In our case, the parameters are a set of matrices and the formula above
translates into

$S({\mathcal{W}})^{2}=\lim_{\xi\to
0}\sup_{\|W_{k}-\tilde{W}_{k}\|_{F}\leqslant\xi}\frac{\sum_{k=1}^{L}\|\nabla_{k}R^{L}({\mathcal{W}})-\nabla_{k}R^{L}(\tilde{{\mathcal{W}}})\|_{F}^{2}}{\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{F}^{2}}\,.$
(13)

We now take ${\mathcal{W}}$ to be an arbitrary minimizer of $R^{L}$. To obtain
the lower bound, consider for $\xi\leqslant 1$

$\tilde{W}_{k}(\xi)=W_{k}+\xi M_{k}\,,$

where the $M_{k}\in{\mathbb{R}}^{d_{k}\times d_{k-1}}$ are parameters that
will be chosen later (depending only on the $W_{k}$ and not on $\xi$). Then

$S({\mathcal{W}})^{2}\geqslant\lim_{\xi\to
0}\frac{\sum_{k=1}^{L}\|\nabla_{k}R^{L}({\mathcal{W}})-\nabla_{k}R^{L}(\tilde{{\mathcal{W}}}(\xi))\|_{F}^{2}}{\xi^{2}\sum_{k=1}^{L}\|M_{k}\|_{F}^{2}}\,,$
(14)

To alleviate notations, we drop the dependence of $\tilde{W}_{k}$ on $\xi$.
Recall that, for any parameters ${\mathcal{W}}^{0}$,

$\nabla_{k}R^{L}({\mathcal{W}}^{0})=W_{k+1}^{0\top}\dots W_{L}^{0\top}w\nabla
R^{1}(w_{\textnormal{prod}}^{0})^{\top}W_{1}^{0\top}\dots W_{k-1}^{0\top}\,,$

with

$w_{\textnormal{prod}}^{0}=W_{1}^{0\top}\dots
W_{L}^{0\top}w\quad\textnormal{and}\quad\nabla
R^{1}(w_{\textnormal{prod}}^{0})=-\frac{2}{n}X^{\top}X(w^{\star}-w_{\textnormal{prod}}^{0})\,.$

For minimizers of the empirical risk, $\nabla_{k}R^{L}({\mathcal{W}})=0$, so

$\displaystyle\Delta_{k}:=\nabla_{k}R^{L}({\mathcal{W}})-\nabla_{k}R^{L}(\tilde{{\mathcal{W}}})=-\tilde{W}_{k+1}^{\top}\dots\tilde{W}_{L}^{\top}w\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}\tilde{W}_{1}^{\top}\dots\tilde{W}_{k-1}^{\top}\,.$
(15)

Minimizers of the empirical risk also satisfy that
$w_{\textnormal{prod}}=w^{\star}$. Thus, by adding and subtracting
differences,

$\displaystyle\nabla R^{1}(\tilde{w}_{\textnormal{prod}})$
$\displaystyle=\frac{2}{n}X^{\top}X(\tilde{w}_{\textnormal{prod}}-w_{\textnormal{prod}})$
$\displaystyle=\frac{2}{n}X^{\top}X\Big{(}\sum_{k=1}^{L}\tilde{W}_{1}^{\top}\dots\tilde{W}_{k-1}^{\top}(\tilde{W}_{k}^{\top}-W_{k}^{\top})W_{k+1}^{\top}\dots
W_{L}^{\top}w\Big{)}$ $\displaystyle=\frac{2}{n}\xi
X^{\top}X\Big{(}\sum_{k=1}^{L}W_{1}^{\top}\dots
W_{k-1}^{\top}M_{k}^{\top}W_{k+1}^{\top}\dots
W_{L}^{\top}w\Big{)}+{\mathcal{O}}(\xi^{2})\,.$ (16)

Here, and in the remainder of this proof, the notation ${\mathcal{O}}$ is
taken with respect to the limit when $\xi\to 0$, everything else being fixed.
In particular, inspecting the expression above, we see that $\nabla
R(\tilde{w}_{\textnormal{prod}})={\mathcal{O}}(\xi)$, and therefore, going
back to (15), that

$\Delta_{k}=-W_{k+1}^{\top}\dots W_{L}^{\top}w\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}W_{1}^{\top}\dots
W_{k-1}^{\top}+{\mathcal{O}}(\xi^{2})\,.$

Denote $\bar{\Delta}_{k}$ the product in the last line above. By the
inequality of arithmetic and geometric means, and by subadditivity of the
operator norm,

$\displaystyle\sum_{k=1}^{L}\|\Delta_{k}\|_{F}^{2}$
$\displaystyle=\sum_{k=1}^{L}\|\bar{\Delta}_{k}\|_{F}^{2}+{\mathcal{O}}(\xi^{3})$
$\displaystyle\geqslant\sum_{k=1}^{L}\|\bar{\Delta}_{k}\|_{2}^{2}+{\mathcal{O}}(\xi^{3})$
$\displaystyle\geqslant
L\Big{(}\prod_{k=1}^{L}\|\bar{\Delta}_{k}\|_{2}\Big{)}^{2/L}+{\mathcal{O}}(\xi^{3})$
$\displaystyle\geqslant
L\big{(}\|\bar{\Delta}_{L}\cdots\bar{\Delta}_{1}\|_{2}\big{)}^{2/L}+{\mathcal{O}}(\xi^{3})\,.$
(17)

By definition of $\bar{\Delta}_{k}$,

$\displaystyle\bar{\Delta}_{L}\cdots\bar{\Delta}_{1}$ $\displaystyle=-\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}\underbrace{w_{\textnormal{prod}}\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}\cdots w_{\textnormal{prod}}\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}}_{L-1\textnormal{ times}}$
$\displaystyle=(\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}w^{\star})^{L-1}\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}\,.$

Thus

$\displaystyle\|\bar{\Delta}_{L}\cdots\bar{\Delta}_{1}\|_{2}$
$\displaystyle=(\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}w^{\star})^{L-1}\|\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})\|_{2}$ $\displaystyle\geqslant(\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}w^{\star})^{L-1}\frac{\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}w^{\star}}{\|w^{\star}\|_{2}}$
$\displaystyle=\frac{(\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}w^{\star})^{L}}{\|w^{\star}\|_{2}}\,,$

and, by (17),

$\sum_{k=1}^{L}\|\Delta_{k}\|_{F}^{2}\geqslant L\frac{(\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}w^{\star})^{2}}{\|w^{\star}\|_{2}^{2/L}}+{\mathcal{O}}(\xi^{3})\,.$
(18)

Coming back to (16), we have

$\displaystyle w^{\star\top}\nabla R^{1}(\tilde{w}_{\textnormal{prod}})$
$\displaystyle=\xi\sum_{k=1}^{L}w^{\star\top}\frac{2}{n}X^{\top}XW_{1}^{\top}\dots
W_{k-1}^{\top}M_{k}^{\top}W_{k+1}^{\top}\dots
W_{L}^{\top}w+{\mathcal{O}}(\xi^{2})\,.$

At this point, the computations diverge for the two inequalities we want to
prove. For the first inequality, we take $M_{k}=\beta_{k}W_{k}$, where the
$\beta_{k}$ are free parameters to be optimized. We have

$\displaystyle w^{\star\top}\nabla R^{1}(\tilde{w}_{\textnormal{prod}})$
$\displaystyle=\xi\sum_{k=1}^{L}\beta_{k}w^{\star\top}\frac{2}{n}X^{\top}XW_{1}^{\top}\dots
W_{k-1}^{\top}W_{k}^{\top}W_{k+1}^{\top}\dots
W_{L}^{\top}w+{\mathcal{O}}(\xi^{2})$
$\displaystyle=\xi\sum_{k=1}^{L}\beta_{k}w^{\star\top}\frac{2}{n}X^{\top}Xw_{\textnormal{prod}}+{\mathcal{O}}(\xi^{2})$
$\displaystyle\geqslant
2\xi\lambda\|w^{\star}\|_{2}^{2}\sum_{j=k}^{L}\beta_{k}+{\mathcal{O}}(\xi^{2})\,.$

Therefore, by (18),

$\sum_{k=1}^{L}\|\Delta_{k}\|_{F}^{2}\geqslant
4L\xi^{2}\lambda^{2}\|w^{\star}\|_{2}^{4-\frac{2}{L}}\Big{(}\sum_{k=1}^{L}\beta_{k}\Big{)}^{2}+{\mathcal{O}}(\xi^{3})\,.$

Furthermore,

$\sum_{k=1}^{L}\|M_{k}\|_{F}^{2}=\sum_{k=1}^{L}\beta_{k}^{2}\|W_{k}\|_{F}^{2}\,.$

By (14), we get

$\displaystyle S({\mathcal{W}})^{2}\geqslant
4L\lambda^{2}\|w^{\star}\|_{2}^{4-\frac{2}{L}}\frac{\Big{(}\sum_{k=1}^{L}\beta_{k}\Big{)}^{2}}{\sum_{k=1}^{L}\beta_{k}^{2}\|W_{k}\|_{F}^{2}}\,.$

The first lower bound unfolds by taking $\beta_{k}=1/\|W_{k}\|_{F}$.

Moving on to the second lower-bound, we now take

$M_{k}=\beta_{k}\frac{u_{k}v_{k}^{\top}}{\|u_{k}\|_{2}\|v_{k}\|_{2}}\,,\quad
u_{k}=W_{k-1}\dots W_{1}\frac{2}{n}X^{\top}Xw^{\star}\,,\quad
v_{k}=W_{k+1}^{\top}\dots W_{L}^{\top}w\,,$

where again the $\beta_{k}$ are free parameters to be optimized. We therefore
have

$\displaystyle w^{\star\top}\nabla R^{1}(\tilde{w}_{\textnormal{prod}})$
$\displaystyle=\sum_{k=1}^{L}\underbrace{w^{\star\top}\frac{2}{n}X^{\top}XW_{1}^{\top}\dots
W_{k-1}^{\top}}_{=u_{k}^{\top}}M_{k}^{\top}\underbrace{W_{k+1}^{\top}\dots
W_{L}^{\top}w}_{=v_{k}}+{\mathcal{O}}(\xi^{2})$
$\displaystyle=\xi\sum_{k=1}^{L}\beta_{k}\|u_{k}\|_{2}\|v_{k}\|_{2}+{\mathcal{O}}(\xi^{2})$
$\displaystyle=\xi\sum_{k=1}^{L}\beta_{k}\|W_{k+1}^{\top}\dots
W_{L}^{\top}w\|_{2}\|w^{\star\top}\frac{2}{n}X^{\top}XW_{1}^{\top}\dots
W_{k-1}^{\top}\|_{2}+{\mathcal{O}}(\xi^{2})$
$\displaystyle\geqslant\xi\sum_{k=1}^{L}\beta_{k}\|W_{k+1}^{\top}\dots
W_{L}^{\top}ww^{\star\top}\frac{2}{n}X^{\top}XW_{1}^{\top}\dots
W_{k-1}^{\top}\|_{2}+{\mathcal{O}}(\xi^{2})\,,$

where the last line unfolds from subadditivity of the operator norm. We let
$A_{k}=W_{k+1}^{\top}\dots
W_{L}^{\top}ww^{\star\top}\frac{2}{n}X^{\top}XW_{1}^{\top}\dots
W_{k-1}^{\top}$, and choose $\beta_{k}=\|A_{k}\|_{2}$. Then

$\displaystyle w_{\textnormal{prod}}^{\top}\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})$
$\displaystyle\geqslant\xi\sum_{k=1}^{L}\|A_{k}\|_{2}^{2}+{\mathcal{O}}(\xi^{2})\,.$

Coming back to (18), we get

$\sum_{k=1}^{L}\|\Delta_{k}\|_{F}^{2}\geqslant\frac{L\xi^{2}}{\|w^{\star}\|_{2}^{2/L}}\Big{(}\sum_{k=1}^{L}\|A_{k}\|_{2}^{2}\Big{)}^{2}+{\mathcal{O}}(\xi^{3})\,.$

Furthermore,

$\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{F}^{2}=\xi^{2}\sum_{k=1}^{L}\beta_{k}^{2}\frac{\|u_{k}v_{k}^{\top}\|_{F}^{2}}{\|u_{k}\|_{2}^{2}\|v_{k}\|_{2}^{2}}=\xi^{2}\sum_{k=1}^{L}\beta_{k}^{2}=\xi^{2}\sum_{k=1}^{L}\|A_{k}\|_{2}^{2}\,.$

Therefore, we obtain, by (14),

$S({\mathcal{W}})^{2}\geqslant\frac{L}{\|w^{\star}\|_{2}^{2/L}}\sum_{k=1}^{L}\|A_{k}\|_{2}^{2}\,.$

We can lower bound the sum similarly to (17):

$\displaystyle\sum_{k=1}^{L}\|A_{k}\|_{2}^{2}$ $\displaystyle\geqslant
L\big{(}\|A_{L}\cdots A_{1}\|_{2}\big{)}^{2/L}\,,$

and

$\displaystyle A_{L}\cdots A_{1}$
$\displaystyle=w^{\star\top}\frac{2}{n}X^{\top}X\underbrace{w^{\star}w^{\star\top}\frac{2}{n}X^{\top}X\cdots
w^{\star}w^{\star\top}\frac{2}{n}X^{\top}X}_{L-1\textnormal{ times}}$
$\displaystyle=\Big{(}w^{\star\top}\frac{2}{n}X^{\top}Xw^{\star}\Big{)}^{L-1}w^{\star\top}\frac{2}{n}X^{\top}X\,.$

Thus

$\displaystyle\|A_{L}\cdots A_{1}\|_{2}$
$\displaystyle=\Big{(}w^{\star\top}\frac{2}{n}X^{\top}Xw^{\star}\Big{)}^{L-1}\|w^{\star\top}\frac{2}{n}X^{\top}X\|_{2}$
$\displaystyle\geqslant(2\lambda\|w^{\star}\|_{2}^{2})^{L-1}2\lambda\|w^{\star}\|_{2}$
$\displaystyle=2^{L}\lambda^{L}\|w^{\star}\|_{2}^{2L-1}\,.$

Therefore

$\sum_{k=1}^{L}\|A_{k}\|_{2}^{2}\geqslant
4L\lambda^{2}\|w^{\star}\|_{2}^{4-\frac{2}{L}}\,.$

We finally obtain

$S({\mathcal{W}})^{2}\geqslant
4L^{2}\lambda^{2}\|w^{\star}\|_{2}^{4-\frac{4}{L}}\,,$

which gives the second lower bound.

###  B.2. Proof of Lemma 1

This identity can be shown by noting that the identity is trivially true for
$t=0$, then differentiating on both sides with respect to time, and using (5).
We refer, e.g., to Arora et al. (2018) for a detailed proof.

###  B.3. Proof of Lemma 2

Before proving the three statements of the lemma in order, we let

$\bar{\varepsilon}=\max_{1\leqslant k\leqslant
L}\|W_{k}(0)\|_{F}^{2}+\sum_{k=1}^{L-1}\|W_{k+1}^{\top}(0)W_{k+1}(0)-W_{k}(0)W_{k}^{\top}(0)\|_{2}\,.$

Note that $\bar{\varepsilon}\leqslant\varepsilon$.

First statement. The claim is true for $k=L$ since $W_{L}$ is a (row) vector.
For $k\in\\{1,\dots,L-1\\}$, taking the $2$-norm in Lemma 1, we have

$\displaystyle\begin{split}\|W_{k+1}^{\top}W_{k+1}\|_{2}&=\|W_{k}W_{k}^{\top}+W_{k+1}^{\top}(0)W_{k+1}(0)-W_{k}(0)W_{k}^{\top}(0)\|_{2}\\\
&\leqslant\|W_{k}W_{k}^{\top}\|_{2}+\|W_{k+1}^{\top}(0)W_{k+1}(0)-W_{k}(0)W_{k}^{\top}(0)\|_{2}\,.\end{split}$

Thus, using $\|A^{\top}A\|_{2}=\|AA^{\top}\|_{2}=\|A\|_{2}^{2}$,

$\|W_{k+1}\|_{2}^{2}-\|W_{k+1}^{\top}(0)W_{k+1}(0)-W_{k}(0)W_{k}^{\top}(0)\|_{2}\leqslant\|W_{k}\|_{2}^{2}\,.$
(19)

We now take the trace in Lemma 1 to obtain

$\|W_{k+1}\|_{F}^{2}-\|W_{k+1}(0)\|_{F}^{2}=\|W_{k}\|_{F}^{2}-\|W_{k}(0)\|_{F}^{2}\,.$

Combining with the inequality above, we have that

$\displaystyle\|W_{k}\|_{F}^{2}-\|W_{k}\|_{2}^{2}$
$\displaystyle\leqslant\|W_{k+1}\|_{F}^{2}-\|W_{k+1}\|_{2}^{2}+\|W_{k}(0)\|_{F}^{2}-\|W_{k+1}(0)\|_{F}^{2}$
$\displaystyle+\|W_{k+1}^{\top}(0)W_{k+1}(0)-W_{k}(0)W_{k}^{\top}(0)\|_{2}$

Summing from $k$ to $L-1$ and telescoping, we have

$\displaystyle\|W_{k}\|_{F}^{2}-\|W_{k}\|_{2}^{2}$
$\displaystyle\leqslant\|W_{L}\|_{F}^{2}-\|W_{L}\|_{2}^{2}+\|W_{k}(0)\|_{F}^{2}-\|W_{L}(0)\|_{F}^{2}$
$\displaystyle+\sum_{k^{\prime}=k}^{L-1}\|W_{k^{\prime}+1}^{\top}(0)W_{k^{\prime}+1}(0)-W_{k^{\prime}}(0)W_{k^{\prime}}^{\top}(0)\|_{2}\,.$

The first two terms compensate since $W_{L}$ is a vector, and the remainder of
the terms is less than $\bar{\varepsilon}\leqslant\varepsilon$ by definition.
This gives the first statement of the Lemma.

Second statement. Assume without loss of generality that $j>k$. By recurrence
over (19), we obtain that

$\sigma_{j}^{2}\leqslant\sigma_{k}^{2}+\sum_{k^{\prime}=k}^{j-1}\|W_{k^{\prime}+1}^{\top}(0)W_{k^{\prime}+1}(0)-W_{k^{\prime}}(0)W_{k^{\prime}}^{\top}(0)\|_{2}\leqslant\sigma_{k}^{2}+\bar{\varepsilon}\,.$

The reverse inequality can be shown similarly: by considering again Lemma 1
and taking the $2$-norm, we get

$\|W_{k}W_{k}^{\top}\|_{2}\leqslant\|W_{k+1}^{\top}W_{k+1}\|_{2}+\|W_{k+1}^{\top}(0)W_{k+1}(0)-W_{k}(0)W_{k}^{\top}(0)\|_{2}$

Thus

$\|W_{k}\|_{2}^{2}\leqslant\|W_{k+1}\|_{2}^{2}+\|W_{k+1}^{\top}(0)W_{k+1}(0)-W_{k}(0)W_{k}^{\top}(0)\|_{2}\,.$

As previously, we get by recurrence that

$\sigma_{k}^{2}\leqslant\sigma_{j}^{2}+\bar{\varepsilon}\,.$

Combined with the reverse bound above, this gives the second statement of the
lemma.

Third statement. Let us lower and upper bound
$u_{k}^{\top}W_{k+1}^{\top}W_{k+1}u_{k}$. We have on the one hand, by Lemma 1,

$\displaystyle u_{k}^{\top}W_{k+1}^{\top}W_{k+1}u_{k}$
$\displaystyle=u_{k}^{\top}W_{k}W_{k}^{\top}u_{k}-u_{k}^{\top}W_{k}(0)W_{k}^{\top}(0)u_{k}+u_{k}^{\top}W_{k+1}^{\top}(0)W_{k+1}(0)u_{k}$
$\displaystyle\geqslant
u_{k}^{\top}W_{k}W_{k}^{\top}u_{k}-u_{k}^{\top}W_{k}(0)W_{k}^{\top}(0)u_{k}$
$\displaystyle\geqslant\sigma_{k}^{2}-\|W_{k}(0)\|_{2}^{2}\,.$

On the other hand,

$\displaystyle u_{k}^{\top}W_{k+1}^{\top}W_{k+1}u_{k}$
$\displaystyle=u_{k}^{\top}\big{(}W_{k+1}^{\top}W_{k+1}-v_{k+1}\sigma_{k+1}^{2}v_{k+1}^{\top}\big{)}u_{k}+u_{k}^{\top}v_{k+1}\sigma_{k+1}^{2}v_{k+1}^{\top}u_{k}$
$\displaystyle\leqslant\|W_{k+1}^{\top}W_{k+1}-v_{k+1}\sigma_{k+1}^{2}v_{k+1}^{\top}\|_{2}+\langle
v_{k+1},u_{k}\rangle^{2}\sigma_{k+1}^{2}$

The $2$-norm above is equal to the second largest eigenvalue of
$W_{k+1}^{\top}W_{k+1}$, which is the square of the second largest singular
value of $W_{k+1}$. In particular, it is lower than
$\|W_{k+1}\|_{F}^{2}-\|W_{k+1}\|_{2}^{2}$ which is the sum of the squared
singular values of $W_{k+1}$ except the largest one. We obtain

$u_{k}^{\top}W_{k+1}^{\top}W_{k+1}u_{k}\leqslant\|W_{k+1}\|_{F}^{2}-\|W_{k+1}\|_{2}^{2}+\langle
v_{k+1},u_{k}\rangle^{2}\sigma_{k+1}^{2}\leqslant\bar{\varepsilon}+\langle
v_{k+1},u_{k}\rangle^{2}\sigma_{k+1}^{2}$

by the first statement of the Lemma. Combining lower and upper bounds of
$u_{k}^{\top}W_{k+1}^{\top}W_{k+1}u_{k}$, we get

$\bar{\varepsilon}+\langle
v_{k+1},u_{k}\rangle^{2}\sigma_{k+1}^{2}\geqslant\sigma_{k}^{2}-\|W_{k}(0)\|_{2}^{2}\,.$

Thus

$\langle
v_{k+1},u_{k}\rangle^{2}\geqslant\frac{\sigma_{k}^{2}-\|W_{k}(0)\|_{2}^{2}-\bar{\varepsilon}}{\sigma_{k+1}^{2}}\geqslant\frac{\sigma_{k+1}^{2}-\bar{\varepsilon}-\|W_{k}(0)\|_{2}^{2}-\bar{\varepsilon}}{\sigma_{k+1}^{2}}\,,$

by the second statement of the Lemma. We finally obtain

$\langle v_{k+1},u_{k}\rangle^{2}\geqslant
1-\frac{2\bar{\varepsilon}+\|W_{k}(0)\|_{2}^{2}}{\sigma_{k+1}^{2}}\geqslant
1-\frac{\varepsilon}{\sigma_{k+1}^{2}}\,,$

by definition of $\varepsilon$ and $\bar{\varepsilon}$.

###  B.4. Proof of Theorem 3

We lower bound the first term in the sum of the left-hand side. Recall that,
by (5), we have

$\nabla_{1}R^{L}(W(t))=\underbrace{(W_{L}(t)\dots
W_{2}(t))^{\top}}_{d_{1}\times 1}\underbrace{\nabla
R^{1}(w_{\textnormal{prod}}(t))^{\top}}_{1\times d_{0}}\,,$

thus

$\big{\|}\nabla_{1}R^{L}(W(t))\big{\|}_{F}^{2}=\|W_{L}(t)\dots
W_{2}(t)\|_{2}^{2}\big{\|}\nabla
R^{1}(w_{\textnormal{prod}}(t))\big{\|}_{2}^{2}\,.$ (20)

We show that $\|W_{L}(t)\dots W_{2}(t)\|_{2}$ is large by distinguishing
between two cases depending on the magnitude of
$\sigma_{1}(t)=\|W_{1}(t)\|_{2}$. To this aim, let $C>\sqrt{2\varepsilon}L$.

Large spectral norm. We first consider the case where

$\sigma_{1}>C>\sqrt{2\varepsilon}L\,.$ (21)

By Lemma 2, for $k\in\\{1,\dots,L-1\\}$,

$\sigma_{k}^{2}\geqslant\sigma_{1}^{2}-\varepsilon>\varepsilon\,,$

where the second inequality unfolds from (21). Then, again by Lemma 2, for
$k\in\\{1,\dots,L-1\\}$,

$\displaystyle\langle v_{k+1},u_{k}\rangle^{2}$ $\displaystyle\geqslant
1-\frac{\varepsilon}{\sigma_{k+1}^{2}}>0\,.$

It is always possible (without loss of generality) to choose the orientation
of the $u_{k}$ and $v_{k}$ such that $\langle v_{k+1},u_{k}\rangle\geqslant 0$
for any $k\in\\{1,\dots L-1\\}$. Making this choice, the equation above
implies that

$\displaystyle\|v_{k+1}-u_{k}\|^{2}$ $\displaystyle=2-2\langle
v_{k+1},u_{k}\rangle$ $\displaystyle\leqslant
2\bigg{(}1-\sqrt{1-\frac{\varepsilon}{\sigma_{k+1}^{2}}}\bigg{)}\,.$

For $x\in[0,1]$, $\sqrt{1-x}\geqslant 1-x$, and thus

$\|v_{k+1}-u_{k}\|_{2}^{2}\leqslant\frac{2\varepsilon}{\sigma_{k+1}^{2}}\,.$
(22)

Let us show that this implies a lower bound on $\|W_{L}\dots W_{2}\|_{2}$. To
do so, let us denote recursively

$x_{1}=v_{2},\quad x_{k+1}=W_{k+1}x_{k}\quad\textnormal{for}\quad
k\in\\{1,\dots,L-1\\}\,.$

We then have $x_{L}=W_{L}\dots W_{2}x_{1}$, thus

$\|W_{L}\dots
W_{2}\|_{2}\geqslant\frac{\|x_{L}\|_{2}}{\|x_{1}\|_{2}}=\|x_{L}\|_{2}\,.$

Our goal is thus to lower bound $\|x_{L}\|_{2}$, which entails a lower bound
on $\|W_{L}\dots W_{2}\|_{2}$. To this aim, first note that, for any
$k\in\\{1,\dots,L-1\\}$,

$\displaystyle\langle x_{k+1},u_{k+1}\rangle$ $\displaystyle=\langle
W_{k+1}x_{k},u_{k+1}\rangle$ $\displaystyle=\sigma_{k+1}\langle
x_{k},v_{k+1}\rangle$ $\displaystyle=\sigma_{k+1}\langle
x_{k},u_{k}+v_{k+1}-u_{k}\rangle$ $\displaystyle\geqslant\sigma_{k+1}\langle
x_{k},u_{k}\rangle-\sigma_{k+1}\|x_{k}\|_{2}\|v_{k+1}-u_{k}\|_{2}$
$\displaystyle\geqslant\sigma_{k+1}\langle
x_{k},u_{k}\rangle-\sqrt{2\varepsilon}\|x_{k}\|_{2}\,.$ (23)

where the last equation stems from (22). Denote
$\alpha_{k}=\langle\frac{x_{k}}{\|x_{k}\|_{2}},u_{k}\rangle$. Then the
previous equation shows that

$\alpha_{k+1}\geqslant\frac{\|x_{k}\|_{2}}{\|x_{k+1}\|_{2}}(\sigma_{k+1}\alpha_{k}-\sqrt{2\varepsilon})=\frac{\|x_{k}\|_{2}\sigma_{k+1}}{\|x_{k+1}\|_{2}}\Big{(}\alpha_{k}-\frac{\sqrt{2\varepsilon}}{\sigma_{k+1}}\Big{)}\,.$

Further note that $\|x_{k+1}\|_{2}\leqslant\sigma_{k+1}\|x_{k}\|_{2}$, thus

$\alpha_{k+1}\geqslant\alpha_{k}-\frac{\sqrt{2\varepsilon}}{\sigma_{k+1}}\,.$

By recurrence,

$\alpha_{k}\geqslant\alpha_{2}-\sqrt{2\varepsilon}\sum_{k^{\prime}=2}^{k-1}\frac{1}{\sigma_{k+1}}\geqslant\alpha_{2}-\sqrt{2\varepsilon}\sum_{k^{\prime}=2}^{k-1}\frac{1}{\sqrt{\sigma_{1}^{2}-\varepsilon}}=\alpha_{2}-\frac{\sqrt{2\varepsilon}(k-2)}{\sqrt{\sigma_{1}^{2}-\varepsilon}}\,.$

Coming back to (23), we have

$\|x_{k+1}\|_{2}\geqslant\langle
x_{k+1},u_{k+1}\rangle\geqslant\|x_{k}\|_{2}(\sigma_{k+1}\alpha_{k}-\sqrt{2\varepsilon})\,,$

thus by recurrence,

$\displaystyle\|x_{L}\|_{2}\geqslant\|x_{2}\|_{2}\prod_{k=2}^{L-1}(\sigma_{k+1}\alpha_{k}-\sqrt{2\varepsilon})$
$\displaystyle\geqslant\|x_{2}\|_{2}\prod_{k=2}^{L-1}\Big{(}\sqrt{\sigma_{1}^{2}-\varepsilon}\Big{(}\alpha_{2}-\frac{\sqrt{2\varepsilon}(k-2)}{\sqrt{\sigma_{1}^{2}-\varepsilon}}\Big{)}-\sqrt{2\varepsilon}\Big{)}$
$\displaystyle\geqslant\|x_{2}\|_{2}\prod_{k=2}^{L-1}\Big{(}\sqrt{\sigma_{1}^{2}-\varepsilon}\alpha_{2}-\sqrt{2\varepsilon}k\Big{)}\,.$

Finally, by definition,
$\alpha_{2}=\langle\frac{x_{2}}{\|x_{2}\|_{2}},u_{2}\rangle$. Since
$x_{2}=W_{2}x_{1}=W_{2}v_{2}=\sigma_{2}u_{2}$, we obtain that $\alpha_{2}=1$,
and thus

$\displaystyle\|W_{L}\dots W_{2}\|_{2}$ $\displaystyle\geqslant\|x_{L}\|_{2}$
$\displaystyle\geqslant\sigma_{2}\prod_{k=2}^{L-1}\Big{(}\sqrt{\sigma_{1}^{2}-\varepsilon}-\sqrt{2\varepsilon}k\Big{)}$
$\displaystyle\geqslant\sqrt{\sigma_{1}^{2}-\varepsilon}\Big{(}\sqrt{\sigma_{1}^{2}-\varepsilon}-\sqrt{2\varepsilon}(L-1)\Big{)}^{L-2}$
$\displaystyle\geqslant\Big{(}\sqrt{\sigma_{1}^{2}}-\sqrt{\varepsilon}-\sqrt{2\varepsilon}(L-1)\Big{)}^{L-1}$
$\displaystyle\geqslant\big{(}\sigma_{1}-\sqrt{2\varepsilon}L\big{)}^{L-1}\,.$

We finally get

$\|W_{L}\dots
W_{2}\|_{2}\geqslant\big{(}C-\sqrt{2\varepsilon}L\big{)}^{L-1}\,,$ (24)

which is a positive quantity by definition of $C$.

Small spectral norm. We now inspect the case where (21) is not satisfied, that
is, $\sigma_{1}(t)\leqslant C$. First note that, by the formula (6) for the
gradient of $R^{1}$,

$\|\nabla R^{1}(w_{\textnormal{prod}})\|_{2}\leqslant
2\Lambda\|w^{\star}-w_{\textnormal{prod}}\|_{2}\leqslant
2\Lambda(\|w^{\star}\|_{2}+\|w_{\textnormal{prod}}\|_{2})\,.$

Thus, for $\|w_{\textnormal{prod}}\|_{2}\leqslant\|w^{\star}\|_{2}$,
$w_{\textnormal{prod}}\mapsto R^{1}(w_{\textnormal{prod}})$ is
$4\Lambda\|w^{\star}\|_{2}$-Lipschitz. Let us use this property to lower bound
$\|w_{\textnormal{prod}}(t)\|_{2}$ by a constant independent of $t$, for
$t\geqslant 1$. Either we have
$\|w_{\textnormal{prod}}(t)\|_{2}\geqslant\|w^{\star}\|_{2}$, or
$\|w_{\textnormal{prod}}\|_{2}\leqslant\|w^{\star}\|_{2}$, but then, by the
Lipschitzness property,

$|R^{1}(w_{\textnormal{prod}}(t))-R_{0}|\leqslant
4\Lambda\|w^{\star}\|_{2}\|w_{\textnormal{prod}}(t)-0\|_{2}=4\Lambda\|w^{\star}\|_{2}\|w_{\textnormal{prod}}(t)\|_{2}\,,$

where we recall that $R_{0}$ is the risk associated to the null parameters.
Furthermore, for $t\geqslant 1$,

$\displaystyle R^{1}(w_{\textnormal{prod}}(t))$
$\displaystyle=R^{L}({\mathcal{W}}(t))$ $\displaystyle\leqslant
R^{L}({\mathcal{W}}(1))$ (The risk is decreasing along the gradient flow)
$\displaystyle<R^{L}({\mathcal{W}}(0))$ ($\nabla R^{L}({\mathcal{W}}(0))\neq
0$ by Assumption $(A_{2})$) $\displaystyle\leqslant R_{0}\,.$ (by Assumption
$(A_{2})$)

Thus, for $t\geqslant 1$,

$|R^{1}(w_{\textnormal{prod}}(t))-R_{0}|>R_{0}-R^{L}({\mathcal{W}}(1))>0\,.$

To summarize, we proved that, for $t\geqslant 1$,

$\|w_{\textnormal{prod}}(t)\|_{2}\geqslant\min\Big{(}\frac{R_{0}-R^{L}({\mathcal{W}}(1))}{4\Lambda\|w^{\star}\|_{2}},\|w^{\star}\|_{2}\Big{)}>0\,.$

Note that the fact that $\|w^{\star}\|_{2}>0$ is also a consequence of
Assumption $(A_{2})$. Indeed, if $w^{\star}$ were equal to zero, $R_{0}$ would
be the minimum of the risk, thus $(A_{2})$ would imply both that
${\mathcal{W}}(0)$ is a minimizer of $R^{L}$ and $\nabla
R^{L}({\mathcal{W}}(0))\neq 0$, which is contradictory.

Furthermore,

$\|w_{\textnormal{prod}}(t)\|_{2}\leqslant\|W_{L}(t)\dots
W_{2}(t)\|_{2}\|W_{1}(t)\|_{2}=\|W_{L}(t)\dots W_{2}(t)\|_{2}\sigma_{1}(t)\,.$

Then, for $t\geqslant 1$,

$\displaystyle\|W_{L}(t)\dots W_{2}(t)\|_{2}$
$\displaystyle\geqslant\frac{1}{\sigma_{1}(t)}\min\Big{(}\frac{R_{0}-R^{L}({\mathcal{W}}(1))}{4\Lambda\|w^{\star}\|_{2}},\|w^{\star}\|_{2}\Big{)}$
$\displaystyle\geqslant\frac{1}{C}\min\Big{(}\frac{R_{0}-R^{L}({\mathcal{W}}(1))}{4\Lambda\|w^{\star}\|_{2}},\|w^{\star}\|_{2}\Big{)}\,.$
(25)

Conclusion. Combining (24) and (25), we obtain that, for $t\geqslant 1$,

$\|W_{L}(t)\dots
W_{2}(t)\|_{2}\geqslant\min\bigg{(}\big{(}C-\sqrt{2\varepsilon}L\big{)}^{L-1},\frac{1}{C}\min\Big{(}\frac{R_{0}-R^{L}({\mathcal{W}}(1))}{4\Lambda\|w^{\star}\|_{2}},\|w^{\star}\|_{2}\Big{)}\bigg{)}=:\sqrt{\mu_{1}}\,,$

where $\mu_{1}>0$ by the proof above. Then, for $t\geqslant 1$, by (20),

$\big{\|}\nabla_{1}R^{L}(W(t))\big{\|}_{F}^{2}\geqslant\mu_{1}\|\nabla
R^{1}(w_{\textnormal{prod}}(t))\|_{2}^{2}\,.$

By Lemma 8,

$\|\nabla R^{1}(w_{\textnormal{prod}}(t))\|_{2}^{2}\geqslant
4\lambda(R^{L}({\mathcal{W}}(t))-R_{\min})\,.$

Thus, taking $\mu=4\mu_{1}\lambda>0$, for $t\geqslant 1$,

$\sum_{k=1}^{L}\big{\|}\nabla_{k}R^{L}({\mathcal{W}}(t))\big{\|}_{F}^{2}\geqslant\big{\|}\nabla_{1}R^{L}({\mathcal{W}}(t))\big{\|}_{F}^{2}\geqslant\mu(R^{L}({\mathcal{W}}(t))-R_{\min})\,.$

###  B.5. Proof of Corollary 1

We first show that Assumption $(A_{3})$ implies a number of estimates that are
useful in the following. Since $\|w^{\star}\|_{2}\geqslant 1$, we have

$\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}\geqslant\Big{(}\frac{1}{2}\Big{)}^{1/L}\geqslant\frac{1}{2}\,$
(26)

thus

$8L\varepsilon\leqslant
8L\sqrt{\varepsilon}\leqslant\frac{1}{4}\leqslant\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}\leqslant\big{(}2\|w^{\star}\|_{2}\big{)}^{1/L}\,.$
(27)

Moreover,

$\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}\geqslant\frac{1}{4}\,$

so we also have

$8L\varepsilon\leqslant\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}\,.$
(28)

Let us now prove the Corollary. We first note that Theorem 3 implies
exponential convergence of the empirical risk to its minimum by Lemma 7. This
also implies the (exponential) convergence of $w_{\textnormal{prod}}$ to
$w^{\star}$, since, by Lemma 8,

$\displaystyle
R^{L}({\mathcal{W}})-R_{\min}=\frac{1}{n}\|X(w^{\star}-w_{\textnormal{prod}})\|_{2}^{2}\geqslant\lambda\|w^{\star}-w_{\textnormal{prod}}\|_{2}^{2}\,.$

Furthermore,

$\|w_{\textnormal{prod}}\|_{2}=\|W_{1}^{\top}\dots
W_{L}^{\top}\|_{2}\leqslant\|W_{1}\|_{2}\dots\|W_{L}\|_{2}\leqslant\Big{(}\max_{k=1}^{L}\sigma_{k}\Big{)}^{L}\,.$

Let us show that, for $t$ large enough,

$\max_{k=1}^{L}\sigma_{k}\geqslant\Big{(}\frac{\|w^{\star}\|}{2}\Big{)}^{1/L}+\varepsilon\,.$
(29)

If it were not the case, then

$\displaystyle\|w_{\textnormal{prod}}\|_{2}$
$\displaystyle\leqslant\Big{(}\max_{k=1}^{L}\sigma_{k}\Big{)}^{L}$
$\displaystyle\leqslant\Big{(}\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}+\varepsilon\Big{)}^{L}$
$\displaystyle=\frac{\|w^{\star}\|_{2}}{2}\Big{(}1+\varepsilon\Big{(}\frac{2}{\|w^{\star}\|_{2}}\Big{)}^{1/L}\Big{)}^{L}$
$\displaystyle\leqslant\frac{\|w^{\star}\|_{2}}{2}\Big{(}1+2L\varepsilon\Big{(}\frac{2}{\|w^{\star}\|_{2}}\Big{)}^{1/L}\Big{)}\,,$

where the last inequality holds by Lemma 4 since

$L\varepsilon\Big{(}\frac{2}{\|w^{\star}\|_{2}}\Big{)}^{1/L}\leqslant
1\quad\Leftrightarrow\quad
L\varepsilon\leqslant\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}\,,$

which holds by (27). Then, we obtain

$\displaystyle\|w_{\textnormal{prod}}\|_{2}$
$\displaystyle\leqslant\frac{3\|w^{\star}\|_{2}}{4}\,,$

since

$1+2L\varepsilon\Big{(}\frac{2}{\|w^{\star}\|_{2}}\Big{)}^{1/L}\leqslant\frac{3}{2}\quad\Leftrightarrow\quad
4L\varepsilon\leqslant\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}\,,$

which also holds by (27). The inequality
$\|w_{\textnormal{prod}}\|_{2}\leqslant\frac{3\|w^{\star}\|_{2}}{4}$
contradicts the fact that $w_{\textnormal{prod}}$ converges to $w^{\star}$,
thus proving (29). Then, we have

$\displaystyle\max_{k=1}^{L}\sigma_{k}^{2}$
$\displaystyle\geqslant\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}+2\varepsilon\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}\geqslant\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}+\varepsilon\,,$

where the last inequality holds by (26). Furthermore, by Lemma 2, for all
$k\in\\{1,\dots,L\\}$,

$\sigma_{k}^{2}\geqslant\max_{j=1}^{L}\sigma_{j}^{2}-\varepsilon\,.$

This brings the first inequality of the Corollary. We now show the second
inequality of the Corollary. First note that, by Lemma 2,

$\|W_{k}-\sigma_{k}u_{k}v_{k}^{\top}\|_{F}^{2}=\|W_{k}\|_{F}^{2}-\|W_{k}\|_{2}^{2}\leqslant\varepsilon\,,$

since both quantities are equal to the sum of the squared singular values of
$W_{k}$ except the largest one. Then, adding and substracting,

$\displaystyle\|W_{1}^{\top}\dots W_{L}^{\top}$
$\displaystyle-\sigma_{1}\dots\sigma_{L}v_{1}u_{1}^{\top}\dots
v_{L}u_{L}^{\top}\|_{2}$
$\displaystyle\leqslant\sum_{k=1}^{L}\|W_{1}^{\top}\dots
W_{k-1}^{\top}(W_{k}^{\top}-\sigma_{k}u_{k}v_{k}^{\top})\sigma_{k+1}\dots\sigma_{L}v_{k+1}u_{k+1}^{\top}\dots
v_{L}u_{L}^{\top}\|_{2}$
$\displaystyle\leqslant\sum_{k=1}^{L}\|W_{1}\|_{2}\dots\|W_{k-1}\|_{2}\|W_{k}^{\top}-\sigma_{k}u_{k}v_{k}^{\top}\|_{2}\sigma_{k+1}\dots\sigma_{L}$
$\displaystyle\leqslant\sum_{k=1}^{L}\sigma_{1}\dots\sigma_{k-1}\|W_{k}^{\top}-\sigma_{k}u_{k}v_{k}^{\top}\|_{F}\sigma_{k+1}\dots\sigma_{L}$
$\displaystyle\leqslant\sqrt{\varepsilon}\sum_{k=1}^{L}\prod_{j\neq
k}\sigma_{j}$
$\displaystyle=\sqrt{\varepsilon}\prod_{j=1}^{L}\sigma_{j}\sum_{k=1}^{L}\frac{1}{\sigma_{k}}$
$\displaystyle\leqslant\sqrt{\varepsilon}\prod_{j=1}^{L}\sigma_{j}\frac{L}{\min\sigma_{k}}$
$\displaystyle\leqslant\frac{L\sqrt{\varepsilon}}{\Big{(}\frac{\|w^{\star}\|}{2}\Big{)}^{1/L}}\prod_{j=1}^{L}\sigma_{j}\,,$

by the first inequality of the Corollary. Moreover, using again the first
inequality of the Corollary and Lemma 2, we have that

$\langle v_{k+1},u_{k}\rangle^{2}\geqslant
1-\frac{\varepsilon}{\sigma_{k+1}^{2}}\geqslant
1-\frac{\varepsilon}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}}\,.$

Since $u_{L}=1$, we deduce that

$\displaystyle\|\sigma_{1}\dots\sigma_{L}v_{1}u_{1}^{\top}\dots
v_{L}u_{L}^{\top}\|_{2}$
$\displaystyle=\prod_{k=1}^{L}\sigma_{k}\|v_{1}\|_{2}\prod_{k=1}^{L-1}u_{k}^{\top}v_{k+1}$
$\displaystyle\geqslant\prod_{k=1}^{L}\sigma_{k}\Bigg{(}1-\frac{\varepsilon}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}}\Bigg{)}^{\frac{L-1}{2}}$
$\displaystyle\geqslant\prod_{k=1}^{L}\sigma_{k}\Bigg{(}1-\frac{(L-1)\varepsilon}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}}\Bigg{)}\,$

where in the last step we used Lemma 4 which is valid since

$\frac{\varepsilon}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}}\leqslant\frac{1}{2}\quad\Leftrightarrow\varepsilon\leqslant\frac{1}{2}\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}\,,$

which holds by (28). By the triangular inequality, we now have

$\displaystyle\prod_{k=1}^{L}\sigma_{k}\Bigg{(}1-\frac{(L-1)\varepsilon}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}}\Bigg{)}$
$\displaystyle\leqslant\|\sigma_{1}\dots\sigma_{L}v_{1}u_{1}^{\top}\dots
v_{L}u_{L}^{\top}\|_{2}$ $\displaystyle\leqslant\|W_{1}^{\top}\dots
W_{L}^{\top}\|_{2}+\|W_{1}^{\top}\dots
W_{L}^{\top}-\sigma_{1}\dots\sigma_{L}v_{1}u_{1}^{\top}\dots
v_{L}u_{L}^{\top}\|_{2}$ $\displaystyle\leqslant\|W_{1}^{\top}\dots
W_{L}^{\top}\|_{2}+\frac{L\sqrt{\varepsilon}}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}}\prod_{k=1}^{L}\sigma_{k}\,,$

Thus

$\prod_{k=1}^{L}\sigma_{k}\Bigg{(}1-\frac{(L-1)\varepsilon}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}}-\frac{L\sqrt{\varepsilon}}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}}\Bigg{)}\leqslant\|W_{1}^{\top}\dots
W_{L}^{\top}\|_{2}\,.$

Using (27) and (28),

$\displaystyle
1-\frac{(L-1)\varepsilon}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{2/L}}-\frac{L\sqrt{\varepsilon}}{\Big{(}\frac{\|w^{\star}\|_{2}}{2}\Big{)}^{1/L}}\geqslant
1-\frac{1}{8}-\frac{1}{8}=\frac{3}{4}\,.$

Moreover, the product of the singular values can be lower-bounded by the
smallest one to the power $L$, so

$\frac{3(\min\sigma_{k})^{L}}{4}\leqslant\|W_{1}^{\top}\dots
W_{L}^{\top}\|_{2}\,.$

Let us show that, for $t$ large enough,

$\min\sigma_{k}\leqslant(2\|w^{\star}\|_{2})^{1/L}-\varepsilon\,.$

If it were not the case, we would have

$\displaystyle\|W_{1}^{\top}\dots W_{L}^{\top}\|_{2}$
$\displaystyle\geqslant\frac{3\big{(}(2\|w^{\star}\|_{2})^{1/L}-\varepsilon\big{)}^{L}}{4}$
$\displaystyle=\frac{3}{2}\|w^{\star}\|_{2}\Big{(}1-\frac{\varepsilon}{(2\|w^{\star}\|_{2})^{1/L}}\Big{)}^{L}$
$\displaystyle\geqslant\frac{3}{2}\|w^{\star}\|_{2}\Big{(}1-\frac{2L\varepsilon}{(2\|w^{\star}\|_{2})^{1/L}}\Big{)}$
$\displaystyle\geqslant\frac{9}{8}\|w^{\star}\|_{2}\,,$ (30)

where the second inequality holds by Lemma 4 since

$\frac{\varepsilon}{(2\|w^{\star}\|_{2})^{1/L}}\leqslant\frac{1}{2}\,,$

by (27), and the third since

$\frac{2L\varepsilon}{(2\|w^{\star}\|_{2})^{1/L}}\leqslant\frac{1}{4}\quad\Leftrightarrow\quad
L\varepsilon\leqslant\frac{(2\|w^{\star}\|_{2})^{1/L}}{8}\,,$

also by (27). Since $9/8>1$, the inequality (30) is a contradiction with the
fact that $\|W_{1}^{\top}\dots
W_{L}^{\top}\|_{2}=\|w_{\textnormal{prod}}\|_{2}\to\|w^{\star}\|_{2}$, showing
that, for $t$ large enough,

$\min\sigma_{k}\leqslant(2\|w^{\star}\|_{2})^{1/L}-\varepsilon\,.$

Thus

$\min\sigma_{k}^{2}\leqslant(2\|w^{\star}\|_{2})^{2/L}+\varepsilon^{2}-2\varepsilon(2\|w^{\star}\|_{2})^{1/L}\,.$

By Lemma 2, for all $k\in\\{1,\dots,L\\}$,

$\displaystyle\sigma_{k}^{2}$
$\displaystyle\leqslant\min\sigma_{j}^{2}+\varepsilon$
$\displaystyle\leqslant(2\|w^{\star}\|_{2})^{2/L}+\varepsilon^{2}-2\varepsilon(2\|w^{\star}\|_{2})^{1/L}+\varepsilon$
$\displaystyle\leqslant(2\|w^{\star}\|_{2})^{2/L}\,,$

since

$\varepsilon^{2}-2\varepsilon(2\|w^{\star}\|_{2})^{1/L}+\varepsilon\leqslant
0\quad\Leftrightarrow\quad\varepsilon\leqslant
2(2\|w^{\star}\|_{2})^{1/L}-1\,,$

which holds true by Assumption $(A_{3})$ since

$\varepsilon\leqslant 1\leqslant 2(2\|w^{\star}\|_{2})^{1/L}-1\,$

since $\|w^{\star}\|_{2}\geqslant 1$.

###  B.6. Proof of Corollary 2

By the PL condition of Theorem 3 and by Lemma 7, we know that the risk
converges exponentially to its minimum:

$R^{L}({\mathcal{W}}(t))-R_{\min}\leqslant(R^{L}({\mathcal{W}}(1))-R_{\min})e^{-\mu(t-1)}\,.$

To conclude on the convergence of ${\mathcal{W}}(t)$ to a minimizer of the
risk, let us show that ${\mathcal{W}}(t)$ converges by proving that the norm
of its gradient is integrable. We have, by (5),

$\nabla_{k}R^{L}({\mathcal{W}}(t))=W_{k+1}^{\top}(t)\dots
W_{L}^{\top}(t)\nabla
R^{1}(w_{\textnormal{prod}}(t))^{\top}W_{1}^{\top}(t)\dots
W_{k-1}^{\top}(t)\,.$

Thus, by subadditivity of the operator norm,

$\displaystyle\|\nabla_{k}R^{L}({\mathcal{W}}(t))\|_{2}$
$\displaystyle\leqslant\|W_{k+1}(t)\|_{2}\dots\|W_{L}(t)\|_{2}\|\nabla
R^{1}(w_{\textnormal{prod}}(t))\|_{2}\|W_{1}(t)\|_{2}\dots\|W_{k-1}(t)\|_{2}\,.$

By Corollary 1, for $t\geqslant T$,

$\|\nabla_{k}R^{L}({\mathcal{W}}(t))\|_{2}\leqslant(2\|w^{\star}\|_{2})^{\frac{L-1}{L}}\|\nabla
R^{1}(w_{\textnormal{prod}}(t))\|_{2}\,.$

We now use Lemma 8 to get that, for $t\geqslant T$,

$\displaystyle\|\nabla_{k}R^{L}({\mathcal{W}}(t))\|_{2}$
$\displaystyle\leqslant
2(2\|w^{\star}\|_{2})^{\frac{L-1}{L}}\sqrt{\Lambda}\sqrt{R^{L}({\mathcal{W}}(t))-R_{\min}}$
$\displaystyle\leqslant
2(2\|w^{\star}\|_{2})^{\frac{L-1}{L}}\sqrt{\Lambda}\sqrt{R^{L}({\mathcal{W}}(1))-R_{\min}}e^{-\frac{\mu}{2}(t-1)}\,.$

This implies convergence of ${\mathcal{W}}(t)$ to a limit
${\mathcal{W}}^{\textnormal{SI}}$, which concludes the proof.

###  B.7. Proof of Corollary 3

The lower bound unfolds directly from Theorem 2 since
${\mathcal{W}}^{\textnormal{SI}}$ is a minimizer of the empirical risk. To
obtain the upper bound, we begin similarly to the proof of Theorem 2. For
simplicity, we denote ${\mathcal{W}}={\mathcal{W}}^{\textnormal{SI}}$ in the
remainder of the proof. We have, as in the proof of Theorem 2,

$S({\mathcal{W}})^{2}=\lim_{\xi\to
0}\sup_{\|W_{k}-\tilde{W}_{k}\|_{F}\leqslant\xi}\frac{\sum_{k=1}^{L}\|\nabla_{k}R^{L}({\mathcal{W}})-\nabla_{k}R^{L}(\tilde{{\mathcal{W}}})\|_{F}^{2}}{\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{F}^{2}}\,,$
(31)

with

$\displaystyle\Delta_{k}$
$\displaystyle:=\nabla_{k}R^{L}({\mathcal{W}})-\nabla_{k}R^{L}(\tilde{{\mathcal{W}}})$
$\displaystyle=-W_{k+1}^{\top}\dots W_{L}^{\top}\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}W_{1}^{\top}\dots
W_{k-1}^{\top}+{\mathcal{O}}(\xi^{2})\,,$

and

$\displaystyle\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})=\frac{2}{n}X^{\top}X\Big{(}\sum_{k=1}^{L}W_{1}^{\top}\dots
W_{k-1}^{\top}(\tilde{W}_{k}^{\top}-W_{k}^{\top})W_{k+1}^{\top}\dots
W_{L}^{\top}\Big{)}+{\mathcal{O}}(\xi^{2})\,.$

We recall that, as in the proof of Theorem 2, the notation ${\mathcal{O}}$ is
taken with respect to the limit when $\xi\to 0$, everything else being fixed.
Contrarily to the proof of Theorem 2 where we exhibited a specific direction
$\tilde{W}$ to get a lower bound, we here seek an upper bound valid for all
$\tilde{W}$. By subadditivity of the operator norm and by Corollary 1, we have

$\displaystyle\|\nabla R^{1}(\tilde{w}_{\textnormal{prod}})\|_{2}$
$\displaystyle\leqslant
2\Lambda\sum_{k=1}^{L}\|W_{1}\|_{2}\dots\|W_{k-1}\|_{2}\|\tilde{W}_{k}-W_{k}\|_{2}\|W_{k+1}\|_{2}\dots\|W_{L}\|_{2}+{\mathcal{O}}(\xi^{2})$
$\displaystyle\leqslant
2\Lambda(2\|w^{\star}\|_{2})^{(L-1)/L}\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{2}+{\mathcal{O}}(\xi^{2})\,.$
(32)

Moving on to bounding the Frobenius norm of $\Delta_{k}$, we observe that the
dominating term of this matrix decomposes as a rank-one matrix. Thus, again by
subadditivity of the operator norm, equation (32) and Corollary 1,

$\displaystyle\|\Delta_{k}\|_{F}$ $\displaystyle=\|W_{k+1}^{\top}\dots
W_{L}^{\top}\|_{2}\|\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})^{\top}W_{1}^{\top}\dots
W_{k-1}^{\top}\|_{2}+{\mathcal{O}}(\xi^{2})$
$\displaystyle\leqslant\|W_{k+1}\|_{2}\dots\|W_{L}\|_{2}\|\nabla
R^{1}(\tilde{w}_{\textnormal{prod}})\|_{2}\|W_{1}\|_{2}\dots\|W_{k-1}\|_{2}+{\mathcal{O}}(\xi^{2})$
$\displaystyle\leqslant
2\Lambda(2\|w^{\star}\|_{2})^{2(L-1)/L}\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{2}+{\mathcal{O}}(\xi^{2})\,.$

Then

$\displaystyle\|\Delta_{k}\|_{F}^{2}$ $\displaystyle\leqslant
4\Lambda^{2}(2\|w^{\star}\|_{2})^{4(L-1)/L}\Big{(}\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{2}\Big{)}^{2}+{\mathcal{O}}(\xi^{3})$
$\displaystyle\leqslant
4L\Lambda^{2}(2\|w^{\star}\|_{2})^{4(L-1)/L}\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{2}^{2}+{\mathcal{O}}(\xi^{3})\,.$
$\displaystyle\leqslant
4L\Lambda^{2}(2\|w^{\star}\|_{2})^{4(L-1)/L}\sum_{k=1}^{L}\|W_{k}-\tilde{W}_{k}\|_{F}^{2}+{\mathcal{O}}(\xi^{3})\,.$

Thus, by (31),

$\displaystyle S({\mathcal{W}})^{2}\leqslant\lim_{\xi\to
0}4L^{2}\Lambda^{2}(2\|w^{\star}\|_{2})^{4(L-1)/L}+{\mathcal{O}}(\xi)\leqslant
2^{6}L^{2}\Lambda^{2}\|w^{\star}\|_{2}^{4-\frac{4}{L}}\,.$

Therefore

$S({\mathcal{W}})\leqslant 8L\Lambda\|w^{\star}\|_{2}^{2-\frac{2}{L}}\,,$

which concludes the proof by definition of $S_{\min}$.

###  B.8. Proof of Theorem 4

To alleviate notations, we omit in this proof to write the explicit dependence
of parameters on time. Starting from (5), since the gradient decomposes as a
rank-one matrix, we have

$\displaystyle\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}^{2}$
$\displaystyle=\|W_{k+1}^{\top}\dots W_{L}^{\top}w\|_{2}^{2}\|\nabla
R^{1}(w_{\textnormal{prod}})^{\top}W_{1}^{\top}\dots W_{k-1}^{\top}\|^{2}_{2}$
$\displaystyle\geqslant\sigma_{\min}^{2}(W_{k+1}^{\top}\dots
W_{L}^{\top})\|w\|_{2}^{2}\sigma_{\min}^{2}(W_{1}^{\top}\dots
W_{k-1}^{\top})\|\nabla R^{1}(w_{\textnormal{prod}})\|_{2}^{2}$

By Lemma 8,

$\|\nabla R^{1}(w_{\textnormal{prod}})\|_{2}^{2}\geqslant
4\lambda(R^{L}({\mathcal{W}})-R_{\min})\,.$

Recall the notation introduced in Section 5

$\Pi_{L:k}:=W_{L}\dots W_{k}\quad\textnormal{and}\quad\Pi_{k:1}:=W_{k}\dots
W_{1}\,.$

Then

$\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}^{2}\geqslant
4\lambda\|w\|_{2}^{2}\sigma_{\min}^{2}(\Pi_{L:k+1})\sigma_{\min}^{2}(\Pi_{k-1:1})(R({\mathcal{W}})-R_{\min})\,.$
(33)

We now let $u>0$ (whose value will be specified next), and

$t^{*}=\inf\Big{\\{}t\in{\mathbb{R}}_{+},\exists
k\in\\{1,\dots,L\\},\|\theta_{k}\|_{F}>\frac{1}{64}\exp(-2s^{2}-4u)\Big{\\}}\,.$

Let us lower bound the minimum singular values of $\Pi_{k:}$ and $\Pi_{:k}$
uniformly for $t\in[0,t^{\star}]$ by Lemma 3. By definition of $t^{\star}$,
for $t\leqslant t^{\star}$ and for any $k\in\\{1,\dots,L\\}$,
$\|\theta_{k}\|_{2}\leqslant\frac{1}{64}\exp(-2s^{2}-4u)$. Therefore, renaming
$\tilde{C}_{1}$ to $\tilde{C}_{4}$ the constants of Lemma 3, and taking
$u=\tilde{C}_{3}$, we get that, if

$L\geqslant\max\Big{(}\tilde{C}_{1},\Big{(}\frac{\tilde{C}_{3}}{\tilde{C}_{4}}\Big{)}^{4}\Big{)}\,,\quad
d\geqslant\tilde{C}_{2}\,,$ (34)

then, with probability at least

$1-8\exp\Big{(}-\frac{d\tilde{C}_{3}^{2}}{32s^{2}}\Big{)}\,,$

it holds for $t\leqslant t^{\star}$ and for all $k\in\\{1,\dots,L\\}$ that

$\|\Pi_{k:1}\|_{2}\leqslant
4\exp\Big{(}\frac{s^{2}}{2}+\tilde{C}_{3}\Big{)}\,,$ (35)

and

$\sigma_{\min}(\Pi_{k:1})\geqslant\frac{1}{4}\exp\Big{(}-\frac{2s^{2}}{d}-\tilde{C}_{3}\Big{)}\,.$

By symmetry, the same statement holds for $\Pi_{L:k}$ instead of $\Pi_{k:1}$.
By the union bound, the statement holds simultaneously for all $\Pi_{L:k}$ and
$\Pi_{k:1}$ with probability at least

$1-16\exp\Big{(}-\frac{d\tilde{C}_{3}^{2}}{32s^{2}}\Big{)}\,.$

We show next that this event implies the convergence of gradient flow towards
a minimizer satisfying the statement (8) of the theorem, which shall conclude
the proof of the Theorem with

$\displaystyle\begin{split}C_{1}=\max\Big{(}\tilde{C}_{1},\Big{(}\frac{\tilde{C}_{3}}{\tilde{C}_{4}}\Big{)}^{4}&\Big{)}\,,\quad
C_{2}=\tilde{C}_{2}\,,\quad
C_{3}=2^{-36}\exp\Big{(}-4s^{2}-\frac{16s^{2}}{\tilde{C}_{2}}-20\tilde{C}_{3}\Big{)}\,,\\\
C_{4}&=\frac{\tilde{C}_{3}^{2}}{32s^{2}}\,,\quad
C_{5}=\frac{1}{64}\exp(-2s^{2}-4\tilde{C}_{3})\,.\end{split}$ (36)

Under this event, we have

$\sigma_{\min}^{2}(\Pi_{L:k+1})\sigma_{\min}^{2}(\Pi_{k-1:1})\geqslant\frac{1}{2^{8}}\exp\Big{(}-\frac{8s^{2}}{d}-4\tilde{C}_{3}\Big{)}\,,$

thus by (33)

$\displaystyle\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}^{2}\geqslant\frac{1}{2^{6}}\exp\Big{(}-\frac{8s^{2}}{d}-4\tilde{C}_{3}\Big{)}\lambda\|w\|_{2}^{2}(R({\mathcal{W}})-R_{\min})\,.$

Therefore we get the PL condition, for $t\leqslant t^{\star}$,

$\sum_{k=1}^{L}\big{\|}\nabla_{k}R^{L}({\mathcal{W}})\big{\|}_{F}^{2}\geqslant\mu(R^{L}({\mathcal{W}})-R_{\min})\,,$

with

$\mu:=\frac{1}{2^{6}}\exp\Big{(}-\frac{8s^{2}}{d}-4\tilde{C}_{3}\Big{)}\lambda\|w\|^{2}L\,.$

By Lemma 7, this implies that, for $t\leqslant t^{\star}$,

$R^{L}({\mathcal{W}})-R_{\min}\leqslant(R^{L}({\mathcal{W}}(0))-R_{\min})e^{-\mu
t}\,.$ (37)

Let us now show that $t^{\star}=\infty$. We have, since $\theta(0)=0$ and by
definition of the gradient flow,

$\displaystyle\|\theta_{k}\|_{F}=\|\theta_{k}-\theta_{k}(0)\|_{F}\leqslant
L\int_{0}^{t}\|\nabla_{k}R^{L}({\mathcal{W}}(\tau))\|_{F}d\tau\,.$ (38)

We now upper bound the gradient as follows: starting again from (5),

$\displaystyle\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}$
$\displaystyle=\|W_{k+1}^{\top}\dots W_{L}^{\top}w\|_{2}\|\nabla
R^{1}(w_{\textnormal{prod}})^{\top}W_{1}^{\top}\dots W_{k-1}^{\top}\|_{2}$
$\displaystyle\leqslant\|W_{k+1}^{\top}\dots
W_{L}^{\top}\|_{2}\|w\|_{2}\|W_{1}^{\top}\dots W_{k-1}^{\top}\|_{2}\|\nabla
R^{1}(w_{\textnormal{prod}})\|_{2}\,.$

By Lemma 8, we get

$\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}\leqslant
2\sqrt{\Lambda}\|W_{k+1}^{\top}\dots
W_{L}^{\top}\|_{2}\|w\|_{2}\|W_{1}^{\top}\dots
W_{k-1}^{\top}\|_{2}\sqrt{R^{L}({\mathcal{W}})-R_{\min}}\,.$ (39)

By (35) and (37), for $t\leqslant t^{\star}$,

$\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}\leqslant
16\exp(s^{2}+2\tilde{C}_{3})\sqrt{\Lambda}\|w\|_{2}\sqrt{R^{L}({\mathcal{W}}(0))-R_{\min}}e^{-\frac{\mu}{2}t}\,.$
(40)

Plugging this into (38), we get, for $t\leqslant t^{\star}$,

$\displaystyle\|\theta_{k}\|_{F}$ $\displaystyle\leqslant
16\exp(s^{2}+2\tilde{C}_{3})\sqrt{\Lambda}\|w\|_{2}\sqrt{R^{L}({\mathcal{W}}(0))-R_{\min}}L\int_{0}^{t}e^{-\frac{\mu}{2}\tau}d\tau$
$\displaystyle\leqslant\frac{32\exp(s^{2}+2\tilde{C}_{3})\sqrt{\Lambda}\|w\|_{2}\sqrt{R^{L}({\mathcal{W}}(0))-R_{\min}}L}{\mu}$
$\displaystyle=\frac{2^{11}\exp(s^{2}+\frac{8s^{2}}{d}+6\tilde{C}_{3})\sqrt{\Lambda}\sqrt{R^{L}({\mathcal{W}}(0))-R_{\min}}}{\lambda\|w\|_{2}}\,,$

where the last equality comes from the definition of $\mu$. By definition (36)
of $C_{3}$, for $t\leqslant t^{\star}$,

$\displaystyle\|\theta_{k}\|_{F}$ $\displaystyle\leqslant
2^{11}\exp(s^{2}+\frac{8s^{2}}{d}+6\tilde{C}_{3})\sqrt{C_{3}}\leqslant\frac{1}{128}\exp(-2s^{2}-4\tilde{C}_{3})\,.$

If we had $t^{\star}<\infty$, we would have, by definition of $t^{\star}$,
$\|\theta_{k}(t^{\star})\|_{F}\geqslant\frac{1}{64}\exp(-2s^{2}-4\tilde{C}_{3})$.
This contradicts the equation above, showing that $t^{\star}=\infty$. By (37),
this implies convergence of the risk to its minimum. We also see by (40) that
$\nabla_{k}R^{L}({\mathcal{W}})$ is integrable, so ${\mathcal{W}}$ has a limit
as $t$ goes to infinity. This limit ${\mathcal{W}}^{\textnormal{RI}}$ is a
minimizer of the risk and satisfies the condition (8) by definition of
$t^{\star}=\infty$.

Extension to multivariate regression. We emphasize that a very similar proof
holds in the case of multivariate regression, where the neural network is
defined as the linear map from ${\mathbb{R}}^{d}$ to ${\mathbb{R}}^{d}$

$x\mapsto W_{L}\dots W_{1}x\,,$

and we now aim at minimizing the mean squared error loss

$R^{L}({\mathcal{W}})=\frac{1}{n}\|Y-W_{L}\dots W_{1}X^{\top}\|_{2}^{2}\,,$

where $X,Y\in{\mathbb{R}}^{n\times d}$. In this case, as shown in Zou et al.
(2020); Sander et al. (2022), the following bounds on the gradient hold under
Assumption $(A_{1})$:

$\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}^{2}\geqslant
4\lambda\sigma_{\min}^{2}(\Pi_{L:k+1})\sigma_{\min}^{2}(\Pi_{k-1:1})(R({\mathcal{W}})-R_{\min})\,,$

and

$\|\nabla_{k}R^{L}({\mathcal{W}})\|_{F}^{2}\leqslant
4\Lambda\|\Pi_{L:k+1}\|_{2}^{2}\|\Pi_{k-1:1}\|_{2}^{2}(R({\mathcal{W}})-R_{\min})\,.$

Comparing with (33) and (39), the only difference is the absence of
$\|w\|_{2}$ here. From there, the same computations as above hold (taking
$\|w\|_{2}=1$), and give the following result.

######  Theorem 5.

Under Assumptions $(A_{1})$ and $(A_{4})$, there exist $C_{1},\dots,C_{5}>0$
depending only on $s$ such that, if

$L\geqslant C_{1}\,,\quad d\geqslant C_{2}\,,\quad
R^{L}({\mathcal{W}}(0))-R_{\min}\leqslant\frac{C_{3}\lambda^{2}}{\Lambda}\,,$

then, with probability at least

$1-16\exp(-C_{4}d)\,,$

the gradient flow dynamics (4) converge to a global minimizer
${\mathcal{W}}^{\textnormal{RI}}$ of the risk. Furthermore, the minimizer
${\mathcal{W}}^{\textnormal{RI}}$ satisfies

$W_{k}^{\textnormal{RI}}=I+\frac{s}{\sqrt{Ld}}N_{k}+\frac{1}{L}\theta_{k}^{\textnormal{RI}}\quad\textnormal{with}\quad\|\theta_{k}^{\textnormal{RI}}\|_{F}\leqslant
C_{5}\,,\quad 1\leqslant k\leqslant L\,.$

###  B.9. Proof of Lemma 3

We begin by proving the result when $\theta=0$, then explain how to extend to
any $\theta$ in a ball around $0$. Recall that $\Pi_{k:1}$ denotes the product
of weight matrices up to the $k$-th. Let

$M_{s,u}=2\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\,,\quad
m_{s,u}=\frac{1}{2}\exp\Big{(}-\frac{2s^{2}}{d}-u\Big{)}\,,$

and denote by $A$ the event that for all $k$, $\|\Pi_{k:1}\|_{2}\leqslant
M_{s,u}$ and $B$ the event that for all $k$,
$\sigma_{\min}(\Pi_{k:1})\geqslant m_{s,u}$. We begin by bounding the
probability of $\bar{A}$, then bound the probability of $\bar{B}\cap A$.

Useful identities. To this aim, we first introduce some notations and derive
some useful identities. We let ${\mathcal{F}}_{k}$ the filtration generated by
the random variables $N_{1},\dots,N_{k}$. For some $h_{0}\in{\mathbb{R}}^{d}$,
we let

$h_{k}=\Pi_{k:1}h_{0}=\Big{(}I+\frac{s}{\sqrt{Ld}}N_{k}\Big{)}\dots\Big{(}I+\frac{s}{\sqrt{Ld}}N_{1}\Big{)}h_{0}$

In particular, $h_{k+1}$ and $h_{k}$ are related through

$h_{k+1}=\Big{(}I+\frac{s}{\sqrt{Ld}}N_{k+1}\Big{)}h_{k}.$

Taking the squared norm, we get

$\displaystyle\|h_{k+1}\|_{2}^{2}$
$\displaystyle=\|h_{k}\|_{2}^{2}+\frac{s^{2}}{Ld}\|N_{k+1}h_{k}\|_{2}^{2}+\frac{2s}{\sqrt{Ld}}h_{k}^{\top}N_{k+1}h_{k}\,.$

Dividing by $\|h_{k}\|_{2}^{2}$ and taking the logarithm leads to

$\ln(\|h_{k+1}\|_{2}^{2})=\ln(\|h_{k}\|_{2}^{2})+\ln\bigg{(}1+\frac{s^{2}\|N_{k+1}h_{k}\|_{2}^{2}}{Ld\|h_{k}\|_{2}^{2}}+\frac{2sh_{k}^{\top}N_{k+1}h_{k}}{\sqrt{Ld}\|h_{k}\|_{2}^{2}}\bigg{)}\,.$
(41)

Let

$Y_{k,1}=\frac{s^{2}\|N_{k+1}h_{k}\|_{2}^{2}}{Ld\|h_{k}\|_{2}^{2}}\,,\quad
Y_{k,2}=\frac{2sh_{k}^{\top}N_{k+1}h_{k}}{\sqrt{Ld}\|h_{k}\|_{2}^{2}}\,,$

and $Y_{k}=Y_{k,1}+Y_{k,2}$. Then, by Lemma 6,

$Y_{k,1}|{\mathcal{F}}_{k}\sim\frac{s^{2}}{Ld}\chi^{2}(d)\quad\textnormal{and}\quad
Y_{k,2}|{\mathcal{F}}_{k}\sim{\mathcal{N}}\Big{(}0,\frac{4s^{2}}{Ld}\Big{)}\,.$
(42)

This shows in particular that $Y_{k,1}$ and $Y_{k,2}$ are independent of
$N_{1},\dots,N_{k}$, and depend only on $N_{k+1}$. Then, letting

$S_{k,1}=\sum_{j=0}^{k-1}Y_{j,1}\quad\textnormal{and}\quad
S_{k,2}=\sum_{j=0}^{k-1}Y_{j,2}\,,$

both are sums of i.i.d. random variables. In particular,

$S_{L,1}\sim\frac{s^{2}}{Ld}\chi^{2}(Ld)\quad\textnormal{and}\quad
S_{L,2}\sim{\mathcal{N}}\Big{(}0,\frac{4s^{2}}{d}\Big{)}\,.$

Bound on $\mathbb{P}(\bar{A})$. We first bound the deviation of the norm of
$h_{k}=\Pi_{k:1}h_{0}$ for any fixed $h_{0}\in{\mathbb{R}}^{d}$, then conclude
on the operator norm of $\Pi_{k:1}$ by an $\varepsilon$-net argument. For any
(fixed) $h_{0}\in{\mathbb{R}}^{d}$ and $u>0$, we have

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant L}$
$\displaystyle\frac{\|h_{k}\|_{2}^{2}}{\|h_{0}\|_{2}^{2}}\geqslant\exp(s^{2}+2u)\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}\ln(\|h_{k}\|_{2}^{2})-\ln(\|h_{0}\|_{2}^{2})\geqslant s^{2}+2u\Big{)}$
$\displaystyle=\mathbb{P}\bigg{(}\max_{1\leqslant k\leqslant
L}\sum_{j=0}^{k-1}\ln\Big{(}1+\frac{s^{2}\|N_{j+1}h_{j}\|_{2}^{2}}{Ld\|h_{j}\|_{2}^{2}}+\frac{2sh_{j}^{\top}N_{j+1}h_{j}}{\sqrt{Ld}\|h_{j}\|_{2}^{2}}\Big{)}\geqslant
s^{2}+2u\bigg{)}$ $\displaystyle\leqslant\mathbb{P}\bigg{(}\max_{1\leqslant
k\leqslant
L}\sum_{j=0}^{k-1}\frac{s^{2}\|N_{j+1}h_{j}\|_{2}^{2}}{Ld\|h_{j}\|_{2}^{2}}+\frac{2sh_{j}^{\top}N_{j+1}h_{j}}{\sqrt{Ld}\|h_{j}\|_{2}^{2}}\geqslant
s^{2}+2u\bigg{)}\,,$

by using $\ln(1+x)\leqslant x$. Thus

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}\frac{\|h_{k}\|_{2}^{2}}{\|h_{0}\|_{2}^{2}}\geqslant\exp(s^{2}+2u)\Big{)}$
$\displaystyle\leqslant\mathbb{P}\bigg{(}\max_{1\leqslant k\leqslant
L}S_{k,1}+S_{k,2}\geqslant s^{2}+2u\bigg{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}S_{k,1}\geqslant s^{2}+u\Big{)}+\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}S_{k,2}\geqslant u\Big{)}$

by the union bound. We now study the two deviation probabilities separately.
Beginning by the first one, recall that $\frac{Ld}{s^{2}}S_{L,1}$ follows a
$\chi^{2}(Ld)$ distribution. Chi-squared random variables are sub-exponential,
and more precisely satisfy the following property (Ghosh, 2021): if
$X\sim\chi^{2}(p)$ and $u>0$, then

$\mathbb{P}(X\geqslant
p+u)\leqslant\exp\Big{(}-\frac{u^{2}}{4(p+u)}\Big{)}\,.$ (43)

Since the $S_{k,1}$ are increasing, we have, for $u>0$,

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant L}S_{k,1}\geqslant
s^{2}+u\Big{)}$ $\displaystyle=\mathbb{P}(S_{L,1}\geqslant s^{2}+u)$
$\displaystyle=\mathbb{P}\Big{(}\frac{Ld}{s^{2}}S_{L,1}\geqslant
Ld+\frac{Ldu}{s^{2}}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}-\frac{L^{2}d^{2}u^{2}}{4s^{4}(Ld+\frac{Ldu}{s^{2}})}\Big{)}=\exp\Big{(}-\frac{Ldu^{2}}{4s^{4}+us^{2}}\Big{)}\,.$

Moving on to $S_{k,2}$, we have, for $u,\lambda>0$,

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant L}S_{k,2}\geqslant
u\Big{)}=\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant L}\exp(\lambda
S_{k,2})\geqslant\exp(\lambda u)\Big{)}\,.$

Furthermore, $\exp(\lambda S_{k,2})$ is a sub-martingale, since $S_{k,2}$ is a
martingale and by Jensen’s inequality:

$\mathbb{E}(\exp(\lambda
S_{k+1,2})|{\mathcal{F}}_{k})\geqslant\exp(\lambda\mathbb{E}(S_{k+1,2}|{\mathcal{F}}_{k}))=\exp(\lambda
S_{k,2})\,.$

Thus, by Doob’s martingale inequality,

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant L}S_{k,2}\geqslant
u\Big{)}\leqslant\mathbb{E}(\exp(\lambda S_{L,2}))\exp(-\lambda u)\,.$

Furthermore, since $S_{L,2}\sim{\mathcal{N}}(0,\frac{4s^{2}}{d})$,

$\mathbb{E}(\exp(\lambda
S_{L,2}))=\exp\Big{(}\frac{4s^{2}\lambda^{2}}{d}\Big{)}\,.$

Therefore,

$\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant L}S_{k,2}\geqslant
u\Big{)}\leqslant\exp\Big{(}-\lambda u+\frac{4s^{2}\lambda^{2}}{d}\Big{)}\,.$

This quantity is minimal for $\lambda=\frac{du}{8s^{2}}$. We get, for all
$u>0$,

$\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant L}S_{k,2}\geqslant
u\Big{)}\leqslant\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}\,.$ (44)

Therefore, for any $u>0$,

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}\frac{\|h_{k}\|_{2}^{2}}{\|h_{0}\|_{2}^{2}}$
$\displaystyle\geqslant\exp(s^{2}+2u)\Big{)}\leqslant\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}+\exp\Big{(}-\frac{Ldu^{2}}{4s^{4}+us^{2}}\Big{)}\,.$
(45)

To conclude on the operator norm of $\Pi_{k:1}$, consider $\Sigma$ a $1/2$-net
of the unit sphere of ${\mathbb{R}}^{d}$. By Vershynin (2018, Corollary
4.2.13), it is possible to take such a net of cardinality $5^{d}$. Let us show
that, for any $u\in{\mathbb{R}}$,

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}\|\Pi_{k:1}\|_{2}$ $\displaystyle\geqslant
2\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\Big{)}\leqslant\mathbb{P}\Big{(}\bigcup_{h_{0}\in\Sigma}\max_{1\leqslant
k\leqslant
L}\|\Pi_{k:1}h_{0}\|_{2}\geqslant\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\Big{)}\,.$
(46)

Indeed, assume that there exists $k$ such that $\|\Pi_{k:1}\|_{2}\geqslant
2\exp(\frac{s^{2}}{2}+u)$. By definition of the operator norm, there exists
$x$ on the unit sphere of ${\mathbb{R}}^{d}$ such that

$\|\Pi_{k:1}x\|=\|\Pi_{k:1}\|_{2}\,.$

But then, by definition of $\Sigma$, there exists $h_{0}\in\Sigma$ such that
$\|x-h_{0}\|_{2}\leqslant 1/2$. Then

$\|\Pi_{k:1}(x-h_{0})\|_{2}\leqslant\frac{1}{2}\|\Pi_{k:1}\|_{2}\,.$

Therefore, by the triangular inequality,

$\displaystyle\|\Pi_{k:1}h_{0}\|_{2}\geqslant\|\Pi_{k:1}x\|_{2}-\|\Pi_{k:1}(x-h_{0})\|_{2}\geqslant\frac{1}{2}\|\Pi_{k:1}\|_{2}\,.$

Then

$\|\Pi_{k:1}h_{0}\|_{2}\geqslant\frac{1}{2}\|\Pi_{k:1}\|_{2}\geqslant\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\,,$

which proves (46). By the union bound, we conclude that

$\displaystyle\mathbb{P}(\bar{A})=\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}\|\Pi_{k:1}\|_{2}$ $\displaystyle\geqslant
2\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\Big{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}\bigcup_{h_{0}\in\Sigma}\max_{1\leqslant
k\leqslant
L}\|\Pi_{k:1}h_{0}\|_{2}\geqslant\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\Big{)}$
$\displaystyle\leqslant|\Sigma|\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}\|\Pi_{k:1}h_{0}\|_{2}\geqslant\exp\Big{(}\frac{s^{2}}{2}+u\Big{)}\Big{)}\,,$

where now $h_{0}$ denotes any unit-norm fixed vector in ${\mathbb{R}}^{d}$.
Thus, by (45),

$\displaystyle\mathbb{P}(\bar{A})$ $\displaystyle\leqslant
5^{d}\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}\|\Pi_{k:1}h_{0}\|_{2}^{2}\geqslant\exp(s^{2}+2u)\Big{)}$
$\displaystyle\leqslant
5^{d}\Big{(}\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}+\exp\Big{(}-\frac{Ldu^{2}}{4s^{4}+us^{2}}\Big{)}\Big{)}\,.$

This upper bound will be simplified in the conclusion of the proof.

Bound on $\mathbb{P}(\bar{B}\cap A)$. We now move on to proving the lower-
bound on $\sigma_{\min}(\Pi_{k:1})$. We again use an $\varepsilon$-net
argument, as follows. Let $\Sigma$ be an $\varepsilon$-net for
$\varepsilon=\frac{m_{s,u}}{M_{s,u}}$. Then

$\displaystyle\mathbb{P}\Big{(}A\cap\Big{\\{}\min_{1\leqslant k\leqslant
L}\sigma_{\min}(\Pi_{k:1})\leqslant
m_{s,u}\Big{\\}}\Big{)}\leqslant\mathbb{P}\Big{(}\bigcup_{h_{0}\in\Sigma}\min_{1\leqslant
k\leqslant L}\|\Pi_{k:1}h_{0}\|_{2}\leqslant 2m_{s,u}\Big{)}\,.$

Indeed, assume that $A$ holds, that is $\|\Pi_{k:1}\|_{2}\leqslant M_{s,u}$,
and that there exists $k$ such that

$\sigma_{\min}(\Pi_{k:1})\leqslant m_{s,u}\,.$

By definition of the singular value, there exists $x$ on the unit sphere of
${\mathbb{R}}^{d}$ such that

$\|\Pi_{k:1}x\|_{2}=\sigma_{\min}(\Pi_{k:1})\,.$

But then, by definition of $\Sigma$, there exists $h_{0}\in\Sigma$ such that
$\|x-h_{0}\|_{2}\leqslant\varepsilon$. Then

$\|\Pi_{k:1}(x-h_{0})\|_{2}\leqslant\varepsilon\|\Pi_{k:1}\|_{2}\,.$

Under $A$, the right-hand side is smaller than $\varepsilon M_{s,u}$.
Therefore, by the triangular inequality,

$\displaystyle\|\Pi_{k:1}h_{0}\|_{2}\leqslant\|\Pi_{k:1}x\|_{2}+\|\Pi_{k:1}(h_{0}-x)\|_{2}\leqslant
m_{s,u}+\varepsilon M_{s,u}=2m_{s,u}\,.$

By the union bound, we conclude that

$\displaystyle\mathbb{P}\Big{(}A\cap\Big{\\{}\min_{1\leqslant k\leqslant
L}\sigma_{\min}(\Pi_{k:1})\leqslant m_{s,u}\Big{\\}}\Big{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}A\cap\Big{\\{}\bigcup_{h_{0}\in\Sigma}\min_{1\leqslant
k\leqslant L}\|\Pi_{k:1}h_{0}\|_{2}\leqslant 2m_{s,u}\Big{\\}}\Big{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}\bigcup_{h_{0}\in\Sigma}\min_{1\leqslant
k\leqslant L}\|\Pi_{k:1}h_{0}\|_{2}\leqslant 2m_{s,u}\Big{)}$
$\displaystyle\leqslant|\Sigma|\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\|\Pi_{k:1}h_{0}\|_{2}\leqslant 2m_{s,u}\Big{)}$
$\displaystyle=\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}^{d}\mathbb{P}\Big{(}\min_{1\leqslant
k\leqslant L}\|\Pi_{k:1}h_{0}\|_{2}\leqslant 2m_{s,u}\Big{)}\,,$

where the cardinality of the net is given by Vershynin (2018, Corollary
4.2.13). We now take a fixed $h_{0}\in{\mathbb{R}}^{d}$, and compute

$\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\frac{\|h_{k}\|_{2}}{\|h_{0}\|_{2}}\leqslant
2m_{s,u}\Big{)}=\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\frac{\|h_{k}\|_{2}^{2}}{\|h_{0}\|_{2}^{2}}\leqslant 4m_{s,u}^{2}\Big{)}\,.$

Denote by $E$ the event

$\bigcap_{1\leqslant k\leqslant
L}\Big{\\{}Y_{k,2}\geqslant-\frac{1}{2}\Big{\\}}\,.$

We have, by (41),

$\displaystyle\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\frac{\|h_{k}\|_{2}^{2}}{\|h_{0}\|_{2}^{2}}\leqslant 4m_{s,u}^{2}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\ln(\|h_{k}\|_{2}^{2})-\ln(\|h_{0}\|_{2}^{2})\leqslant\ln(4m_{s,u}^{2})\Big{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\sum_{j=0}^{k-1}\ln(1+Y_{j,2})\leqslant\ln(4m_{s,u}^{2})\Big{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}\Big{\\{}\min_{1\leqslant k\leqslant
L}\sum_{j=0}^{k-1}\ln(1+Y_{j,2})\leqslant\ln(4m_{s,u}^{2})\Big{\\}}\cap
E\Big{)}+\mathbb{P}(\bar{E})\,.$

Using the inequality $\ln(1+x)\geqslant x-x^{2}$ for
$x\geqslant-\nicefrac{{1}}{{2}}$, we obtain

$\displaystyle\mathbb{P}\Big{(}\frac{\|h_{L}\|_{2}^{2}}{\|h_{0}\|_{2}^{2}}\leqslant
4m_{s,u}^{2}\Big{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}\Big{\\{}\min_{1\leqslant k\leqslant
L}\sum_{j=0}^{k-1}(Y_{j,2}-Y_{j,2}^{2})\leqslant\ln(4m_{s,u}^{2})\Big{\\}}\cap
E\Big{)}+\mathbb{P}(\bar{E})\,.$

Thus, by the union bound,

$\displaystyle\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\frac{\|h_{L}\|_{2}^{2}}{\|h_{0}\|_{2}^{2}}\leqslant 4m_{s,u}^{2}\Big{)}$
$\displaystyle\leqslant\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}\sum_{j=0}^{k-1}(Y_{j,2}-Y_{j,2}^{2})\leqslant\ln(4m_{s,u}^{2})\Big{)}+\sum_{k=0}^{L-1}\mathbb{P}\Big{(}Y_{k,2}<-\frac{1}{2}\Big{)}$
$\displaystyle=:P_{1}+P_{2}\,.$

We handle both terms separately. Beginning by the second term, we have, for
$k\in\\{1,\dots L\\}$,

$\displaystyle\mathbb{P}\Big{(}Y_{k,2}<-\frac{1}{2}\Big{)}\leqslant\exp\Big{(}-\frac{Ld}{32s^{2}}\Big{)}\,,$

where we used (42) and the tail bound $\mathbb{P}(N\geqslant u)\leqslant
e^{-u^{2}/2}$ if $N\sim{\mathcal{N}}(0,1)$. Moving on to the first term, we
have

$\displaystyle P_{1}$ $\displaystyle=\mathbb{P}\Big{(}\min_{1\leqslant
k\leqslant L}S_{k,2}-S_{k,3}\leqslant\ln(4m_{s,u}^{2})\Big{)}\,,$

where we let $S_{k,3}=\sum_{j=0}^{k-1}Y_{j,2}^{2}$. By definition of
$m_{s,u}$, we have

$\ln(4m_{s,u}^{2})=-\frac{4s^{2}}{d}-2u\,.$

Thus we can split the probability into two parts by the union bound:

$\displaystyle P_{1}$ $\displaystyle\leqslant\mathbb{P}\Big{(}\min_{1\leqslant
k\leqslant L}S_{k,2}\leqslant-u\Big{)}+\mathbb{P}\Big{(}\max_{1\leqslant
k\leqslant L}S_{k,3}\geqslant\frac{4s^{2}}{d}+u\Big{)}\,.$

Let us bound each probability separately. We have, for $u>0$,

$\displaystyle\mathbb{P}\Big{(}\min_{1\leqslant k\leqslant
L}S_{k,2}\leqslant-u\Big{)}=\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}-S_{k,2}\geqslant u\Big{)}=\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}S_{k,2}\geqslant
u\Big{)}\leqslant\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}\,,$

by symmetry of $S_{k,2}$ and by (44). Moving on to $S_{k,3}$, we have that

$Y_{j,2}^{2}|{\mathcal{F}}_{j}\sim\frac{4s^{2}}{Ld}{\mathcal{N}}(0,1)^{2}=\frac{4s^{2}}{Ld}\chi^{2}(1)\,,$

thus

$\frac{Ld}{4s^{2}}S_{k,3}\sim\chi^{2}(L)\,.$

By monotonicity of $S_{k,3}$ and by (43),

$\displaystyle\mathbb{P}\Big{(}\max_{1\leqslant k\leqslant
L}S_{k,3}\geqslant\frac{4s^{2}}{d}+u\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}S_{L,3}\geqslant\frac{4s^{2}}{d}+u\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\frac{Ld}{4s^{2}}S_{L,3}\geqslant
L+\frac{Ldu}{4s^{2}}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}-\frac{L^{2}d^{2}u^{2}}{64s^{4}(L+\frac{Ldu}{4s^{2}})}\Big{)}=\exp\Big{(}-\frac{Ld^{2}u^{2}}{16(4s^{2}+du)}\Big{)}\,.$

Putting everything together, we proved that

$\displaystyle\mathbb{P}(\bar{B}\cap A)$
$\displaystyle\leqslant\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}^{d}(P_{1}+P_{2})=\exp\Big{(}d\ln\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}\Big{)}(P_{1}+P_{2})\,,$

with

$P_{1}\leqslant\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}+\exp\Big{(}-\frac{Ld^{2}u^{2}}{16(4s^{2}+du)}\Big{)}\,$

and

$P_{2}\leqslant L\exp\Big{(}-\frac{Ld}{32s^{2}}\Big{)}\,.$

Bounding the probability of failure. Putting together the two main bounds we
showed, we have

$\displaystyle\mathbb{P}(\bar{A}\cup\bar{B})=\mathbb{P}(\bar{A})+\mathbb{P}(\bar{B}\cup
A)$ $\displaystyle\leqslant
5^{d}\Big{(}\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}+\exp\Big{(}-\frac{Ldu^{2}}{4s^{4}+us^{2}}\Big{)}\Big{)}$
$\displaystyle+\exp\Big{(}d\ln\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}\Big{)}\Big{(}\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}+\exp\Big{(}-\frac{Ld^{2}u^{2}}{16(4s^{2}+du)}\Big{)}+L\exp\Big{(}-\frac{Ld}{32s^{2}}\Big{)}\Big{)}.$

This expression is valid for all $u,s>0$ and $L,d\geqslant 1$. We now simplify
the expression of our upper bound by algebraic computations using the
assumptions of the Theorem. To somewhat alleviate the technicality of the
computations, we stop at this point tracking some of the explicit constants
and let $C$ denote a positive absolute constant that might vary from equality
to equality. We show next that the conditions

$\displaystyle L\geqslant C,\quad d\geqslant C,\quad u\geqslant
C\max(s^{2},s^{-2/3}),\quad u\leqslant CL^{1/4}$ (47)

imply that

$\mathbb{P}(\bar{A}\cup\bar{B})\leqslant
8\exp\Big{(}-\frac{du^{2}}{32s^{2}}\Big{)}\,.$

This shall conclude the proof of the Lemma with

$C_{1}=C,\quad C_{2}=C,\quad C_{3}=C\max(s^{2},s^{-2/3}),\quad C_{4}=C\,.$

First note that the conditions (47) imply that

$\displaystyle u\geqslant Cs\quad\textnormal{and}\quad u\geqslant C\,.$ (48)

We study the terms of the bound on $\mathbb{P}(\bar{A}\cup\bar{B})$ one by
one. First, we have by (48) that

$5^{d}\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}=\exp\Big{(}d\ln(5)-\frac{du^{2}}{16s^{2}}\Big{)}\leqslant\exp\Big{(}-\frac{du^{2}}{32s^{2}}\Big{)}\,.$

Next,

$\displaystyle 5^{d}\exp\Big{(}-\frac{Ldu^{2}}{4s^{4}+us^{2}}\Big{)}$
$\displaystyle\leqslant 5^{d}\exp\Big{(}-\frac{Ldu^{2}}{8us^{2}}\Big{)}$
$\displaystyle=5^{d}\exp\Big{(}-\frac{Ldu}{8s^{2}}\Big{)}$
$\displaystyle=\exp\Big{(}d\ln(5)-\frac{Ldu}{8s^{2}}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}-\frac{Ldu}{16s^{2}}\Big{)}\,,$

where the first inequality uses $u\geqslant s^{2}$ by (47), and the last one
uses that $\frac{Lu}{s^{2}}\geqslant C$. This is true since $L\geqslant C$ and
$u\geqslant Cs^{2}$ by (47). Then we can bound this term by

$\exp\Big{(}-\frac{du^{2}}{32s^{2}}\Big{)}\,,$

since $u\leqslant CL$ which is implied by the assumption $u\leqslant CL^{1/4}$
in (47). Next,

$\displaystyle\ln\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}$
$\displaystyle=\ln\Big{(}8\exp\Big{(}\frac{s^{2}}{2}+\frac{2s^{2}}{d}+2u\Big{)}+1\Big{)}$
$\displaystyle\leqslant\ln\Big{(}9\exp\Big{(}\frac{s^{2}}{2}+\frac{2s^{2}}{d}+2u\Big{)}\Big{)}\,,$

where we used that the exponential of a positive term is greater than $1$.
Then

$\ln\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}\leqslant\ln(9)+\frac{s^{2}}{2}+\frac{2s^{2}}{d}+2u\leqslant
3+3u\,,$ (49)

since $u\geqslant s^{2}$, $d\geqslant 4$ by (47). Thus we can bound the three
remaining terms appearing in the bound of $\mathbb{P}(\bar{A}\cup\bar{B})$, as
follows:

$\displaystyle\exp\Big{(}d\ln\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}\Big{)}\exp\Big{(}-\frac{du^{2}}{16s^{2}}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}3d+3du-\frac{du^{2}}{16s^{2}}\Big{)}\leqslant\exp\Big{(}-\frac{du^{2}}{32s^{2}}\Big{)}\,,$

since

$u^{2}\geqslant Cs^{2}(1+u)\,.$

This is the case by (48), which implies that

$u^{2}=\frac{1}{2}u^{2}+\frac{1}{2}uu\geqslant\frac{C^{2}}{2}s^{2}+\frac{C}{2}s^{2}u=\frac{C^{2}+C}{2}s^{2}(1+u)\,.$

Next, by (49),

$\displaystyle\exp\Big{(}d\ln\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}\Big{)}\exp\Big{(}-\frac{Ld^{2}u^{2}}{16(4s^{2}+du)}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}3d+3du-\frac{Ld^{2}u^{2}}{16(4s^{2}+du)}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}3d+3du-\frac{Ld^{2}u^{2}}{32du}\Big{)}\,,$

since $du\geqslant u\geqslant Cs^{2}$ by (47). Thus

$\displaystyle\exp\Big{(}d\ln\Big{(}\frac{2M_{s,u}}{m_{s,u}}+1\Big{)}\Big{)}\exp\Big{(}-\frac{Ld^{2}u^{2}}{16(4s^{2}+du)}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}3d+3du-\frac{Ldu}{32}\Big{)}\leqslant\exp\Big{(}-\frac{Ldu}{64}\Big{)},$

where the second inequality uses that $L\geqslant C$ by (47), and $Lu\geqslant
C$ since $L\geqslant C$ and $u\geqslant C$ by (47) and (48). We can also bound
this term by

$\exp\Big{(}-\frac{du^{2}}{32s^{2}}\Big{)}\,,$

since $L\geqslant Cu/s^{2}$, using first that $L\geqslant Cu^{4}$ then that
$u\geqslant Cs^{-2/3}$, by (47). Regarding the last term of the bound of
$\mathbb{P}(\bar{A}\cup\bar{B})$, we have by (49) that