# Convergence and Regularization Properties
of Gradient Descent for Deep Residual Networks111Alain Rossier’s research was
supported through EPSRC Centre for Doctoral Training in Mathematics of Random
Systems: Analysis, Modelling and Simulation (EP/S023925/1).

Rama Cont1, Alain Rossier1,2 and Renyuan Xu3

1 Mathematical Institute, University of Oxford 2 Instadeep Ltd
3 Department of Industrial and Systems Engineering, University of Southern
California
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We prove linear convergence of gradient descent to a global optimum for the
training of deep residual networks with constant layer width and smooth
activation function. We show that if the trained weights, as a function of the
layer index, admit a scaling limit as the depth increases, then the limit has
finite $p-$variation with $p=2$. Proofs are based on non-asymptotic estimates
for the loss function and for norms of the network weights along the gradient
descent path. We illustrate the relevance of our theoretical results to
practical settings using detailed numerical experiments on supervised learning
problems.

###### Contents

  1. 1 Introduction
    1. 1.1 Convergence and regularization properties of deep learning algorithms
    2. 1.2 Contributions
  2. 2 Residual networks
  3. 3 Dynamics of weights and hidden states under gradient descent
    1. 3.1 Bounds on the hidden states, their Jacobians, and the loss gradients
    2. 3.2 Behaviour of weight norms along the gradient descent path
    3. 3.3 Local convergence of gradient descent
    4. 3.4 Scaling limit of trained weights
  4. 4 Numerical experiments
    1. 4.1 Identification of scaling behavior
    2. 4.2 Rate of convergence
    3. 4.3 Emergence of regularity of weights as a function of the layer index
  5. 5 Conclusion
  6. A Gradient of the loss function with respect to parameters
  7. B Boundedness of hidden states and Jacobians
  8. C Upper bounds on the gradient and Hessian of the loss function
  9. D Lower bounds on loss gradients
  10. E Weight norms and loss function under gradient descent
  11. F Supporting lemma for Theorem 3.5
  12. G Auxiliary results

##  1 Introduction

Whether gradient descent methods find globally optimal solutions in the
training of neural networks and how trained neural networks generalize are two
major open questions in the theory of deep learning. The non-convexity of the
loss functions for neural network training may lead to sub-optimal solutions
when applying gradient descent methods. It is thus relevant to understand from
a theoretical point of view whether specific neural network architectures with
a proper choice of learning rates for gradient descent methods can improve the
optimization landscape and/or eliminate sub-optimal solutions [23]. There is
some empirical evidence that gradient descent seems to select solutions that
generalize well [28] even without any explicit regularization. Hence, it is
believed that gradient descent induces an implicit regularization [21] and
characterizing the nature of this regularization is an interesting research
question.

In the present work we prove linear convergence of gradient descent to a
global minimum for a class of deep residual networks with constant layer width
and smooth activation function. Furthermore, we show that under practical
assumptions, the trained weights admit a scaling limit as a function of the
layer index which has finite $2$-variation. Our result shows that how implicit
regularization emerges from gradient descent. Our proofs are based on non-
asymptotic estimates for the loss function and norms of the network weights
along the gradient descent path. These non-asymptotic estimates are
interesting in their own right and may prove useful to other researchers for
the study of dynamics of learning algorithms.

###  1.1 Convergence and regularization properties of deep learning algorithms

Existing results on convergence and implicit regularization in deep learning
exploit three paradigms: over-parametrized neural networks with fixed depth
and large width, linear neural networks with sufficiently large depth, and
mean-field residual networks.

Under sufficient over-parametrization by width with fixed depth, many popular
neural network architectures (including feed-forward, convolutional, and
residual) with ReLU activation find a global optimum in linear time with
respect to the remaining error and the trained network generalizes well [1,
2]. However, the associated generalization bounds are intractable, and the
amount of over-parametrization implied in these results is often
unrealistically large. One can improve the asymptotic analysis [29, 30], but
it still falls short of leading to any practical insight. For smooth
activation functions, [10] studied the convergence of gradient descent for
various network architectures, including residual networks. They show that for
any depth, if the residual layers are wide enough and the learning rate is
small enough, gradient descent on the empirical mean-squared loss converges to
a solution with zero training loss in linear time. The rate of convergence is
proportional to the learning rate and the minimum eigenvalue of the Gram
matrix. [11] showed that in the over-parametrized regime, for a suitable
initialization with the last layer initialized at zero and other weights
initialized uniformly, gradient descent can find a global minimum
exponentially fast with high probability.

For linear deep neural networks (i.e. with identity activation function), [4]
showed that training with gradient descent is able to learn the positive
definite linear transformations using identity initialization. [25] proposed a
new initialization scheme named zero-asymmetric (ZAS) and proved that that
under such initialization, for an arbitrary target matrix, gradient descent
converges to an $\epsilon$-optimal point in
$\mathcal{O}(L^{3}\log(1/\epsilon))$ iterations, which scales polynomially
with the network depth $L$. Subsequent refinements of the convergence rates
and the width requirements have been established in [9, 31]. Finally, [27]
showed the implicit regularization of gradient descent for linear fully-
connected networks to $l_{2}$ max-margin solutions.

Another line of work deals with mean-field residual networks by looking at the
continuum limit of residual networks when either the depth $L$ or the width
$d$ goes to infinity. [26] build on the analysis of [8] for feed-forward
networks to study the average behaviour of randomly initialized residual
networks with width tending to infinity. They show that a careful
initialization, depending on the depth, may enhance expressivity. Further,
[20] proposed a continuum limit of deep residual networks by letting the depth
$L$ tends to infinity and showed that every local minimum of the loss
landscape is global. This characterization enables them to derive the first
global convergence result for multi-layer neural networks in the mean-field
regime.

In addition to the network architectures listed above, non-linear neural
networks with fixed width and large but finite depth are successful and
practically more popular [15, 16]. It is well-documented that for a fixed
number of parameters, going deeper allows the models to capture richer
structures [12, 24]. However, the theoretical foundations for such networks
remain widely open due to their complex training landscape.

###  1.2 Contributions

We consider a supervised learning problem where we seek to learn an unknown
mapping with inputs and outputs in $\mathbb{R}^{d}$ using a residual network
with constant width $d$ and a smooth activation function. We study the
convergence and implicit regularization of gradient descent for the mean-
squared error.

  * •

Linear convergence. For $\epsilon>0$, we prove that for a residual network of
depth $L=\Omega(1/\epsilon)$, we can choose a learning rate schedule such that
gradient descent on the training loss converges to a $\epsilon$-optimal
solution in $\Theta(\log(1/\epsilon))$ iterations.

  * •

Scaling limit of trained weights. The trained weights, as a function of the
layer, may admit a scaling limit as $L\to\infty$. We prove that such a scaling
limit is a matrix-valued function with finite $2$-variation.

  * •

Non-asymptotic estimates on loss function and weights along the gradient
descent path. In addition to the convergence results mentioned above, we
obtain (non-asymptotic) estimates along the gradient descent path for the loss
function and various norms of the weights, with tractable bounds.

  * •

Relevance to practical settings. We illustrate the relevance of our
theoretical results in practical settings using detailed numerical experiments
with networks of realistic width and depth.

Our analysis generalizes previous results on linear neural networks [25] to a
more general nonlinear setting relevant for learning problems. Our non-
asymptotic results stand in contrast to the mean-field analysis [20] which
requires infinite depth. Our tractable bounds improve upon the ones found for
networks over-parametrized by width [2, 10, 11, 29, 30], where the trained
weights do not leave the lazy training regime [6]: in our setting, the trained
weights are not necessarily staying close to their initialization. A key
ingredient in the proof is to study the evolution of various norms for the
weights under gradient descent iterations. These estimates are provided in
Lemmas 3.3 and 3.4.

Our theoretical results suggest that initialization of weights at scale
$L^{-1}$ together with a $L^{-1/2}$ scaling of the activation function leads
to convergence under a constant learning rate. The overarching principle is to
make sure that the gradient stays on the same scale as the weights (here
$L^{-1/2}$) during training. Our analysis also extends, with minimal changes,
to the case where linear layers are added at the beginning and the end of the
network.

#### Notations

Define
$(e_{m})_{m^{\prime}}=\mathbbm{1}_{\\{m^{\prime}=m\\}}\in\mathbb{R}^{d}$. For
a vector $x\in\mathbb{R}^{d}$, we denote $\left\lVert x\right\rVert_{2}$ the
Euclidean norm of $x$, and for a matrix $M\in\mathbb{R}^{d\times d}$, we
denote $\left\lVert M\right\rVert_{F}$ the Frobenius norm of $M$. When the
context is clear, we omit the superscript $x$ for the quantities that depend
on the input $x$. We denote $f=\mathcal{O}(g)$ if there exists $c>0$ such that
$f(z)\leq cg(z)$, where $z=(L,k,t,\eta_{L}(t),c_{0})$. That means, our Big-O
notation involves a constant that is independent of the depth $L$, the layer
number $k$, the iteration number $t$, the learning rates $\eta_{L}(t)$, and
the universal constant $c_{0}$ defined in Assumption 2.1. Similar definitions
stand for $\Omega$ and $\Theta$. For a function
$\sigma\colon\mathbb{R}\to\mathbb{R}$, define
$\sigma_{d}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ by
$\sigma_{d}(x)_{i}=\sigma(x_{i})$ for $i=1,\ldots,d$.

##  2 Residual networks

Let $x\in\mathbb{R}^{d}$ be an input vector, $\delta_{L}$ be a fixed positive
real number, and $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$ be a set of
parameters (or weights). In this section, we focus on a ResNet architecture
without bias with $L$ fully-connected layers:

$\begin{cases}h^{x,\,(L)}_{k}&=h^{x,\,(L)}_{k-1}+\delta_{L}\sigma_{d}\left(\alpha_{k}^{(L)}h^{x,\,(L)}_{k-1}\right),\,\,\,k=1,\ldots,L,\\\
h^{x,\,(L)}_{0}&=x.\end{cases}$ (2.1)

The output of the network is $h_{L}^{x,\,(L)}$, which we denote by
$\widehat{y}_{L}\left(x,W^{(L)}\right)$ to emphasize the dependence on the
input $x$ and the weights $\alpha^{(L)}$. 222The analysis with bias is done by
expanding the weights $\alpha_{k}^{(L)}$ and the hidden states $h_{k}^{(L)}$
with an additional dimension. Fix a training set
$D_{N}\coloneqq\\{(x_{i},y_{i}):i=1,\ldots,N\\}\subset\mathbb{R}^{d}\times\mathbb{R}^{d}$,
and the loss function
$\ell\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}_{+}$ defined by
$\ell(y,\widehat{y})\coloneqq\frac{1}{2}\left\lVert
y-\widehat{y}\right\rVert_{2}^{2}$.

We study the dynamics of the weights induced by gradient descent (GD) on the
mean-squared error $J_{L}\colon\mathbb{R}^{L\times d\times
d}\to\mathbb{R}_{+}$ defined by

$J_{L}\left(\alpha^{(L)}\right)\coloneqq\frac{1}{N}\sum_{i=1}^{N}\ell\left(y_{i},\widehat{y}_{L}\left(x_{i},\alpha^{(L)}\right)\right)=\frac{1}{2N}\sum_{i=1}^{N}\left\lVert
y_{i}-\widehat{y}_{L}\left(x_{i},\alpha^{(L)}\right)\right\rVert_{2}^{2}.$
(2.2)

We consider a gradient descent learning algorithm which sequentially updates
the weights using an initialization $A^{(L)}(0)\in\mathbb{R}^{L\times d\times
d}$ and

$\Delta A_{k}^{(L)}(t)\coloneqq
A_{k}^{(L)}(t+1)-A_{k}^{(L)}(t)=-\eta_{L}(t)\nabla_{\alpha_{k}}J_{L}\left(A^{(L)}(t)\right),$
(2.3)

where $\eta_{L}(t)>0$ is the learning rate at iteration $t\in\mathbb{N}$,
which may depend on the depth $L$, but is independent of the layer index $k$.

######  Assumption 2.1.

There exists a constant $c_{0}>0$ such that

  * (i)

Smooth activation function: $\sigma\in C^{2}(\mathbb{R})$,
$\sigma^{\prime}(0)=1$ and for all $z\in\mathbb{R}$,
$\left|\sigma(z)\right|\leq\left|z\right|$,
$\left|\sigma^{\prime}(z)\right|\leq 1$ and
$\left|\sigma^{\prime\prime}(z)\right|\leq 1$.

  * (ii)

Scaling factor: $\delta^{(L)}=L^{-1/2}$.

  * (iii)

Separated unit data: $\left\lVert x_{i}\right\rVert_{2}=\left\lVert
y_{i}\right\rVert_{2}=1$ and $\forall i\neq j$, $\left|\langle
x_{i},x_{j}\rangle\right|\leq(8N)^{-1}e^{-4c_{0}}$.

  * (iv)

Initialisation with $O(1/L)$ weights:

$\sup_{k,m}\left\lVert A_{k,m}^{(L)}(0)\right\rVert_{2}\leq
2^{-9/2}N^{-1/2}d^{-1/2}e^{-4.2c_{0}}L^{-1}.$

  * (v)

Small initial loss: $J_{L}(A^{(L)}(0))\leq
2^{-15}3^{-2}N^{-2}d^{-1}c_{0}^{2}e^{-8.2c_{0}}$.

Note that $\tanh$ satisfies Assumption 2.1 (i). Assumption 2.1 (ii) comes from
the scaling we observe in the experiments of Section 4.1. Assumption 2.1 (iii)
requires the training points to be sufficiently orthogonal to one another.
Among other cases, it is satisfied in the small data regime: take for example
$N$ points uniformly at random on the $d-$dimensional sphere, where $d>N^{4}$.
Hence, for $x_{i}\sim\mathcal{U}(\mathbb{S}^{d-1})$ i.i.d., we have by a union
bound and Chebychev inequality:

$\displaystyle\mathbb{P}\left(\max_{i\neq j}\left|\langle
x_{i},x_{j}\rangle\right|>N^{-1}\right)$ $\displaystyle\leq
N^{2}\mathbb{P}\left(\left|\langle x_{1},x_{2}\rangle\right|>N^{-1}\right)$
$\displaystyle\leq N^{4}\mathbb{V}\mathrm{ar}\left[\langle
x_{1},x_{2}\rangle\right]\leq
N^{4}\sum_{m=1}^{d}\mathbb{E}\left[(x_{1})_{m}^{2}\right]\mathbb{E}\left[(x_{2})_{m}^{2}\right]=N^{4}d^{-1}<1.$

Assumption 2.1 (iv) guarantees that the network at initialization stay well-
behaved, and does not bias the optimization path. Note also that Assumption
2.1 (iv) does not rule out the case of a stochastic initialization. Assumption
2.1 (v) relates to the fact that we are going to prove local convergence of
gradient descent to zero training loss. Proving global convergence under our
general framework is out of reach, as local minima are guaranteed to exist,
see Theorem 2 in [22]. In this paper, we address Corollary 3 in [22] by
providing conditions on the dataset and on the initialization procedure to
show convergence of gradient descent for residual networks of large depth and
finite width.

##  3 Dynamics of weights and hidden states under gradient descent

Recall that $\alpha^{(L)}$ denotes a generic weight vector, whereas
$A^{(L)}(t)$ denotes the weight vector obtained after $t$ iterations of
gradient descent on the objective function $J_{L}$, where the initial weights
$A^{(L)}(0)$ follow Assumption 2.1 (iv). The main results can be summarized as
follows.

First, in Section 3.1, we prove that if the network weights $\alpha^{(L)}_{k}$
are $\mathcal{O}(L^{-1/2})$, then the hidden states $h_{k}^{x,\,(L)}$ and the
Jacobian

$M_{k}^{x,\,(L)}\coloneqq\frac{\partial h_{L}^{x,\,(L)}}{\partial
h_{k}^{x,\,(L)}}\in\mathbb{R}^{d\times d}$ (3.1)

are uniformly bounded in $k$ and $L$. Then, under the same scaling assumption,
we derive an upper bound for the norm of the gradient $\nabla_{\alpha}J_{L}$
of the objective function with respect to the weights $\alpha^{(L)}$.
Furthermore, we derive a lower bound for the norm of the gradient
$\nabla_{\alpha}J_{L}$ under the additional regularity assumption
$\alpha_{k+1}^{(L)}-\alpha_{k}^{(L)}=\mathcal{O}(L^{-1})$.

Next, in Section 3.2, we let $\alpha^{(L)}(0)\in\mathbb{R}^{L\times d\times
d}$ be any initialization and define recursively
$\alpha^{(L)}(t+1)=\alpha^{(L)}(t)-\eta_{L}(t)\nabla_{\alpha}J_{L}\left(\alpha^{(L)}(t)\right)$.
Under some scaling assumptions for $\alpha^{(L)}(t)$ for $t=0,\ldots,T-1$, we
show that the loss function $J_{L}\left(\alpha^{(L)}(t)\right)$ at time $T$
admits an explicit upper bound. To show this, we study the effect of gradient
descent on the following norms of the weight vector:

$\mkern 1.0mu\overline{\mkern-1.5muf\mkern 0.0mu}\mkern
1.0mu^{(L)}\left(\alpha^{(L)}(t)\right)\coloneqq\frac{1}{2}\sum_{k=1}^{L}\left\lVert\alpha^{(L)}_{k}(t)\right\rVert_{F}^{2}\quad\text{and}\quad\mkern
1.0mu\overline{\mkern-1.5mug\mkern 0.0mu}\mkern
1.0mu^{(L)}\left(\alpha^{(L)}(t)\right)\coloneqq\frac{1}{2}L\sum_{k=1}^{L-1}\left\lVert\alpha^{(L)}_{k+1}(t)-\alpha_{k}^{(L)}(t)\right\rVert_{F}^{2}.$
(3.2)

The scaling in $L$ is chosen in such a way that we will be able to prove a
uniform bound (in $t$ and $L$) of the above norms along the gradient descent
path $A^{(L)}(t)$ when $A^{(L)}(0)$ satisfy Assumption 2.1 (iii).

Finally in Section 3.3 we show that under Assumption 2.1 with the parameter
$A^{(L)}(t)$ evolving according to the gradient descent dynamics (2.3), we
have that for all $\epsilon>0$, if we let $L=\Omega(1/\epsilon)$,
$\eta_{L}(t)=\eta_{0}$, and $T_{L}^{\,\mathrm{const}}=\Theta(\eta_{0}^{-1}\log
L)=\Omega(\eta_{0}^{-1}\log 1/\epsilon)$, then
$J_{L}\left(A^{(L)}(T^{\,\mathrm{const}}_{L})\right)<\epsilon$. That is, the
loss function can be made arbitrarily small with practical values for the
depth and the number of gradient steps. To prove this, we use recursion: we
first verify the scaling assumptions

$A^{(L)}(t)=\mathcal{O}(c_{0}L^{-1/2})\quad\textrm{and}\quad
A_{k+1}^{(L)}(t)-A_{k}^{(L)}(t)=\mathcal{O}(e^{-4.2c_{0}}L^{-1}),$ (3.3)

at initialization, i.e. for $t=0$. This enables us to use the results of
Section 3.1 to deduce an upper bound on the loss function
$J_{L}\left(A^{(L)}(1)\right)$ at time $t=1$, which in turn yields that the
scaling assumptions (3.3) are verified for $t=1$. We continue this process
until the upper bound on the loss is smaller than $\epsilon$.
Further, we prove that for $T_{L}$ satisfying (3.7), if the (pointwise) limit

$\mkern 1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern
1.0mu^{*}_{s}\coloneqq\lim_{L\to\infty}A^{(L)}_{\left\lfloor
Ls\right\rfloor}(T_{L})$ (3.4)

converges uniformly in $s\in\left[0,1\right]$ at a $\mathcal{O}(L^{-1/2})$
rate, then $\mkern 1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern 1.0mu^{*}$
is of finite $2$-variation, giving an implicit regularity to the solution
found by gradient descent. The numerical experiments in Section 4 confirm that
these effects are observable in settings relevant to practical supervised
learning problems.

###  3.1 Bounds on the hidden states, their Jacobians, and the loss gradients

We start the analysis by computing bounds on the hidden states and their
Jacobians (3.1). To do so, we define the following norm on the weights:

$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\coloneqq\max_{k=1,\ldots,L}\left\lVert\alpha^{(L)}_{k}\right\rVert_{F},$
(3.5)

where $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$ is a generic weight
vector. We check that the hidden states are uniformly bounded from above and
below in $k$ and $L$, and we prove an upper bound on the Jacobians, uniformly
in $k$ and $L$. We get explicit bounds when $L$ is large enough:

$\left\lVert x\right\rVert_{2}e^{-2c_{\alpha}}\leq\left\lVert
h^{x,\,(L)}_{k}\right\rVert_{2}\leq\left\lVert
x\right\rVert_{2}e^{1.1c_{\alpha}}\quad\mbox{and}\quad\left\lVert
M^{x,\,(L)}_{k}e_{m}\right\rVert_{2}\leq e^{c_{\alpha}},$

given the assumption that $\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq
c_{\alpha}L^{-1/2}$. The proof can be found in Appendix B. Note that the
bounds are deterministic, unlike the probabilistic results from [2, 3]. Next,
we derive that the norm of the gradient of the objective function is bounded
above by $J_{L}^{1/2}$, so that it ensures that the gradient updates (2.3)
stay local. The precise result and its proof can be found in Appendix C.

More crucially, we also need a lower bound on the norm of the gradient as a
function of the suboptimality gap. We first establish a lower bound for the
gradient of the loss with respect to the weights of the first layer.

######  Lemma 3.1.

Under Assumption 2.1 (i)–(iii), let $\alpha^{(L)}\in\mathbb{R}^{L\times
d\times d}$ such that $L\geq\max(5c_{0},4c_{0}^{2})$ and
$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq c_{0}L^{-1/2}$ hold. Then,
we have

$\left\lVert\nabla_{\alpha_{1}}J_{L}\left(\alpha^{(L)}\right)\right\rVert_{F}^{2}\geq\frac{1}{4N}e^{-2c_{0}}L^{-1}J_{L}\left(\alpha^{(L)}\right).$

###### Proof.

Fix $L\geq\max(5c_{0},4c_{0}^{2})$. In the proof, we omit the explicit
dependence in $L$. Observe first that

$\displaystyle\left\lVert\nabla_{\alpha_{k}}J_{L}(\alpha)\right\rVert_{F}^{2}$
$\displaystyle=\sum_{m,n=1}^{d}\left(\frac{1}{N}\sum_{i=1}^{N}\frac{\partial\ell}{\partial\alpha_{k,mn}}\left(y_{i},\widehat{y}\left(x_{i},\alpha\right)\right)\right)^{2}$
$\displaystyle=\sum_{m,n=1}^{d}\frac{\delta_{L}^{2}}{N^{2}}\sum_{i,j=1}^{N}h_{k-1,n}^{x_{i}}h_{k-1,n}^{x_{j}}\dot{\sigma}_{k,x_{i},m}\dot{\sigma}_{k,x_{j},m}\left(\left(M_{k}^{x_{i}}\right)^{\top}\left(\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right)\right)_{m}$
$\displaystyle\hskip
42.67912pt\left(\left(M_{k}^{x_{j}}\right)^{\top}\left(\widehat{y}\left(x_{j},\alpha\right)-y_{j}\right)\right)_{m}$
$\displaystyle=\frac{\delta_{L}^{2}}{N^{2}}\sum_{i,j=1}^{N}\big{\langle}h_{k-1}^{x_{i}},\,h_{k-1}^{x_{j}}\big{\rangle}\,\widetilde{M}_{k,i,j},$

where

$\widetilde{M}_{k,i,j}=\Big{\langle}\dot{\sigma}_{k,x_{i}}\odot\left(M_{k}^{x_{i}}\right)^{\top}\left(\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right),\,\,\dot{\sigma}_{k,x_{j}}\odot\left(M_{k}^{x_{j}}\right)^{\top}\left(\widehat{y}\left(x_{j},\alpha\right)-y_{j}\right)\Big{\rangle}.$

We focus on the case $k=1$. We first estimate, by Cauchy-Schwarz and Lemma
B.1,

$\displaystyle\left|\widetilde{M}_{1,i,j}\right|$
$\displaystyle\leq\left\lVert M_{1}^{x_{i}}\right\rVert_{2}\left\lVert
M_{1}^{x_{j}}\right\rVert_{2}\left\lVert\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right\rVert_{2}\left\lVert\widehat{y}\left(x_{j},\alpha\right)-y_{j}\right\rVert_{2}$
$\displaystyle\leq
e^{2c_{0}}\left\lVert\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right\rVert_{2}\left\lVert\widehat{y}\left(x_{j},\alpha\right)-y_{j}\right\rVert_{2}.$

#### Lower bound when $i=j$

First, as $\left|\sigma^{\prime\prime}\right|\leq 1$ and $L\geq 4c_{0}^{2}$,
we have $\dot{\sigma}_{1,x_{i},m}=\sigma^{\prime}(\alpha_{1}x_{i})_{m}\geq
1-\left\lVert\alpha_{1}\right\rVert_{F}\left\lVert x_{i}\right\rVert_{2}\geq
1-c_{0}L^{-1/2}\geq\frac{1}{2}$. Hence,

$\displaystyle\widetilde{M}_{1,i,i}$
$\displaystyle=\left\lVert\dot{\sigma}_{1,x_{i}}\odot\left(M_{1}^{x_{i}}\right)^{\top}\left(\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right)\right\rVert_{2}^{2}$
$\displaystyle\geq\frac{1}{4}\left\lVert\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right\rVert_{2}^{2}\prod_{k=1}^{L}\left(1-\delta_{L}\left\lVert\mathrm{diag}(\dot{\sigma}_{k,x_{i}})\alpha_{k}\right\rVert_{2}\right)^{2}$
$\displaystyle\geq\frac{1}{4}\left(1-\frac{c_{0}}{L}\right)^{2L}\left\lVert\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right\rVert_{2}^{2}\geq\frac{1}{4}e^{-2c_{0}}\left\lVert\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right\rVert_{2}^{2},$

where we applied Lemma G.2 in the second line, and the fact that
$\left\lVert\cdot\right\rVert_{2}\leq\left\lVert\cdot\right\rVert_{F}$. By
Assumption 2.1 (iii), $\left|\langle
x_{i},x_{j}\rangle\right|\leq(8N)^{-1}e^{-4c_{0}}$ for all $i\neq j$, so we
deduce

$\displaystyle\left\lVert\nabla_{\alpha_{1}}J_{L}(\alpha)\right\rVert_{F}^{2}$
$\displaystyle=\frac{\delta_{L}^{2}}{N^{2}}\left(\sum_{i=1}^{N}\widetilde{M}_{1,i,i}\left\lVert
x_{i}\right\rVert_{2}^{2}+\sum_{i\neq j}\widetilde{M}_{1,i,j}\langle
x_{i},x_{j}\rangle\right)$
$\displaystyle\geq\frac{1}{LN^{2}}\left(\frac{N}{2}e^{-2c_{0}}J_{L}(\alpha)-\frac{1}{8N}e^{-4c_{0}}\sum_{i\neq
j}\left|\widetilde{M}_{1,i,j}\right|\right)$
$\displaystyle\geq\frac{1}{LN^{2}}\left(\frac{N}{2}e^{-2c_{0}}J_{L}(\alpha)-\frac{1}{8N}e^{-2c_{0}}\sum_{i\neq
j}\left\lVert\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right\rVert_{2}\left\lVert\widehat{y}\left(x_{j},\alpha\right)-y_{j}\right\rVert_{2}\right)$
$\displaystyle\geq\frac{1}{LN^{2}}\left(\frac{N}{2}e^{-2c_{0}}J_{L}(\alpha)-\frac{1}{8N}e^{-2c_{0}}\left(\sum_{i=1}^{N}\left\lVert\widehat{y}\left(x_{i},\alpha\right)-y_{i}\right\rVert_{2}\right)^{2}\right)$
$\displaystyle\geq\frac{1}{LN^{2}}\left(\frac{N}{2}e^{-2c_{0}}J_{L}(\alpha)-\frac{N}{4}e^{-2c_{0}}J_{L}(\alpha)\right)=\frac{1}{4N}e^{-2c_{0}}L^{-1}J_{L}(\alpha).$

∎

Next, if we assume that the weights $\alpha^{(L)}$ are close to each other in
neighbouring layers, we can deduce that the gradient of the loss with respect
to weights in neighbouring layers are also close to each other. Hence, if we
couple this fact with Lemma 3.1, we can prove a lower bound on the norm of the
gradient of the loss with respect to the full weight vector $\alpha^{(L)}$.

######  Lemma 3.2.

Under Assumption 2.1 (i)–(iii), let $\alpha^{(L)}\in\mathbb{R}^{L\times
d\times d}$ such that $L\geq\max(5c_{0},4c_{0}^{2})$,
$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq c_{0}L^{-1/2}$, and
$\left\lVert\alpha^{(L)}_{k+1}-\alpha^{(L)}_{k}\right\rVert_{F}\leq
2^{-7/2}N^{-1/2}e^{-4.2c_{0}}L^{-1}$ for each $k$. Then,

$\left\lVert\nabla_{\alpha^{(L)}}J_{L}\left(\alpha^{(L)}\right)\right\rVert_{F}^{2}\geq\left(\frac{1}{16}N^{-1}e^{-2c_{0}}-17dc_{0}^{4}e^{6.4c_{0}}L^{-1}\right)J_{L}(\alpha).$

###### Proof.

Fix $L\geq\max(5c_{0},4c_{0}^{2})$. In the proof, we omit the explicit
dependence in $L$. We use Lemma D.1 to estimate the difference of neighbouring
gradients:

$\displaystyle\frac{\partial J_{L}}{\partial\alpha_{k,mn}}-\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}$
$\displaystyle=\frac{\delta_{L}}{N}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}\left(\dot{\sigma}_{k,x_{i},m}-\dot{\sigma}_{k+1,x_{i},m}\right)\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}e_{m}$
$\displaystyle+\frac{\delta_{L}^{2}}{N}\sum_{i=1}^{N}\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}\xi^{x_{i},\,(L)}_{k,mn},$

where $\xi^{x,\,(L)}_{k,mn}$ satisfies

$\left\lVert\xi^{x,\,(L)}_{k,mn}\right\rVert_{2}^{2}\leq
2\left(h^{x}_{k-1,n}\right)^{2}\left\lVert\alpha_{k+1}-\alpha_{k}\right\rVert_{F}^{2}+2\left\lVert\alpha_{k,n}\right\rVert_{2}^{4}\left\lVert
h_{k-1}^{x}\right\rVert_{2}^{4}.$

By Lemma B.1 and the fact that $\sigma^{\prime}$ is $1-$Lipschitz by
Assumption 2.1 (i), we bound further:

$\displaystyle\left\lVert\nabla_{\alpha_{k+1}}J_{L}\left(\alpha\right)-\nabla_{\alpha_{k}}J_{L}\left(\alpha\right)\right\rVert_{F}^{2}=\sum_{m,n=1}^{d}\left(\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}-\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}\right)^{2}$ $\displaystyle\leq
4\sum_{m,n=1}^{d}\frac{1}{LN}\sum_{i=1}^{N}\left(h_{k-1,n}^{x_{i}}\right)^{2}\left\lVert
M^{x_{i}}_{k}e_{m}\right\rVert_{2}^{2}\left(\alpha_{k}h^{x_{i}}_{k-1}-\alpha_{k+1}h^{x_{i}}_{k}\right)_{m}^{2}\ell(y_{i},\widehat{y}(x_{i},\alpha))$
$\displaystyle\qquad+\frac{4}{L^{2}N}\sum_{i=1}^{N}e^{2c_{0}}\left(2de^{2.2c_{0}}\left\lVert\alpha_{k+1}-\alpha_{k}\right\rVert_{F}^{2}+2dc_{0}^{4}e^{4.4c_{0}}L^{-2}\right)\ell(y_{i},\widehat{y}(x_{i},\alpha))$
$\displaystyle\leq
e^{4.2c_{0}}\frac{4}{LN}\sum_{i=1}^{N}\left\lVert\alpha_{k}h^{x_{i}}_{k-1}-\alpha_{k+1}h^{x_{i}}_{k}\right\rVert_{2}^{2}\ell(y_{i},\widehat{y}(x_{i},\alpha))+9dc_{0}^{4}e^{6.4c_{0}}L^{-4}J_{L}(\alpha).$

Then, simply note that

$\displaystyle\left\lVert\alpha_{k}h^{x_{i}}_{k-1}-\alpha_{k+1}h^{x_{i}}_{k}\right\rVert_{2}^{2}$
$\displaystyle\leq
2\left\lVert\left(\alpha_{k+1}-\alpha_{k}\right)h^{x_{i}}_{k}\right\rVert_{2}^{2}+2\left\lVert\alpha_{k}\left(h^{x_{i}}_{k}-h^{x_{i}}_{k-1}\right)\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{1}{64}N^{-1}e^{-6.2c_{0}}L^{-2}+2c_{0}^{4}e^{2.2c_{0}}L^{-3}.$

Hence,

$\left\lVert\nabla_{\alpha_{k+1}}J_{L}\left(\alpha\right)-\nabla_{\alpha_{k}}J_{L}\left(\alpha\right)\right\rVert_{F}^{2}\leq\left(\frac{1}{16}N^{-1}e^{-2c_{0}}+17dc_{0}^{4}e^{6.4c_{0}}L^{-1}\right)L^{-3}J_{L}(\alpha).$

Finally, we use the reverse triangle inequality and Cauchy-Schwarz inequality:

$\displaystyle\left\lVert\nabla_{\alpha_{k}}J_{L}\left(\alpha\right)\right\rVert_{F}^{2}$
$\displaystyle\geq\frac{1}{2}\left\lVert\nabla_{\alpha_{1}}J_{L}\left(\alpha\right)\right\rVert_{F}^{2}-(k-1)\sum_{k^{\prime}=1}^{k-1}\left\lVert\nabla_{\alpha_{k+1}}J_{L}\left(\alpha\right)-\nabla_{\alpha_{k}}J_{L}\left(\alpha\right)\right\rVert_{F}^{2}$
$\displaystyle\geq\frac{1}{8}N^{-1}e^{-2c_{0}}L^{-1}J_{L}(\alpha)-\frac{(k-1)^{2}}{L^{3}}\left(\frac{1}{16}N^{-1}e^{-2c_{0}}+17dc_{0}^{4}e^{6.4c_{0}}L^{-1}\right)J_{L}(\alpha)$
$\displaystyle\geq\left(\frac{1}{16}N^{-1}e^{-2c_{0}}-17dc_{0}^{4}e^{6.4c_{0}}L^{-1}\right)L^{-1}J_{L}(\alpha).$

The second inequality holds by Lemma 3.1 and (i) above. Hence,

$\left\lVert\nabla_{\alpha}J_{L}\left(\alpha^{(L)}\right)\right\rVert_{F}^{2}=\sum_{k=1}^{L}\left\lVert\nabla_{\alpha_{k}}J_{L}(\alpha^{(L)})\right\rVert_{F}^{2}\geq\left(\frac{1}{16}N^{-1}e^{-2c_{0}}-17dc_{0}^{4}e^{6.4c_{0}}L^{-1}\right)J_{L}(\alpha).$

∎

It guarantees that for $L\gg 1$, every critical point close to the origin is a
global minimum of the objective function, similarly to what is known for
linear residual networks [14, 17, 18, 19].

###  3.2 Behaviour of weight norms along the gradient descent path

In Section 3.1, we establish bounds on the gradient of the loss function
evaluated at a generic weight vector $\alpha^{(L)}\in\mathbb{R}^{L\times
d\times d}$. We now proceed to understand how $\alpha^{(L)}$ changes under a
gradient descent update. To do so, we study the local version of the weight
norms defined in (3.2). Define for $x,y\in\mathbb{R}^{d}$ and $k=0,\ldots,L$:

$G^{\,x,y,\,(L)}_{k}\left(\alpha^{(L)}\right)\coloneqq\frac{\partial\ell(y,\,\cdot\,)}{\partial
h^{(L)}_{k}}\left(\widehat{y}\big{(}x,\alpha^{(L)}\big{)}\right)\in\mathbb{R}^{d}.$
(3.6)

Also, for clarity, denote
$h_{k}^{x,(L)}\left(\alpha^{(L)}\right)\in\mathbb{R}^{d}$ for the hidden state
of the $k^{th}$ layer using input $x\in\mathbb{R}^{d}$ and network weights
$\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$.

######  Lemma 3.3.

Let $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$ and define
$\widetilde{\alpha}^{(L)}\coloneqq\alpha^{(L)}-\eta_{L}\nabla_{\alpha}J_{L}\left(\alpha^{(L)}\right)$.
Define further
$f^{(L)}_{k,m}\left(\alpha^{(L)}\right)\coloneqq\frac{1}{2}L\left\lVert\alpha^{(L)}_{k,m}\right\rVert_{2}^{2}$
Under Assumption 2.1 (i)–(ii), we have

$f^{(L)}_{k,m}\left(\widetilde{\alpha}^{(L)}\right)^{1/2}\leq
f^{(L)}_{k,m}\left(\alpha^{(L)}\right)^{1/2}+\frac{1}{\sqrt{2}}\eta_{L}\left(\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i},\,(L)}\left(\alpha^{(L)}\right)\right\rVert_{2}^{2}\left\lVert
G^{\,x_{i},y_{i},\,(L)}_{k}\left(\alpha^{(L)}\right)\right\rVert_{\infty}^{2}\right)^{1/2}.$

######  Lemma 3.4.

Let $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$ and $c_{\alpha}>0$ such
that $L\geq 5c_{\alpha}$ and
$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq c_{\alpha}L^{-1/2}$.
Define
$\widetilde{\alpha}^{(L)}\coloneqq\alpha^{(L)}-\eta_{L}\nabla_{\alpha}J_{L}\left(\alpha^{(L)}\right)$,
and let
$g^{(L)}_{k}\left(\alpha^{(L)}\right)\coloneqq\frac{1}{2}L^{2}\left\lVert\alpha^{(L)}_{k+1}-\alpha^{(L)}_{k}\right\rVert_{F}^{2}$.
Under Assumption 2.1 (i)–(ii), we have

$\displaystyle g^{(L)}_{k}\left(\widetilde{\alpha}^{(L)}\right)$
$\displaystyle\leq
g^{(L)}_{k}\left(\alpha^{(L)}\right)\left(1+L^{-1/2}\eta_{L}\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i},\,(L)}\left(\alpha^{(L)}\right)\right\rVert_{2}^{2}\left\lVert
G^{x_{i},y_{i},\,(L)}_{k+1}\left(\alpha^{(L)}\right)\right\rVert_{\infty}\right)^{2}$
$\displaystyle+\mathcal{O}\Big{(}c_{\alpha}e^{2.1c_{\alpha}}\left(c_{\alpha}e^{1.1c_{\alpha}}L^{-1}+2L^{-1/2}\right)\eta_{L}g_{k}\big{(}\alpha^{(L)}\big{)}^{1/2}J_{L}\big{(}\alpha^{(L)}\big{)}^{1/2}\Big{)},$

where the Big-O constant is also independent of $c_{\alpha}$.

The proofs of Lemmas 3.3 and 3.4 can be found in Appendix E.

###  3.3 Local convergence of gradient descent

In this section, we initialize the weight vector $A^{(L)}(0)$ according to
Assumption 2.1 (iv) and we let the weights $A^{(L)}(t)$ evolve according to
the gradient descent dynamics (2.3). We show that under some a priori
conditions on the initial parameters, the initial loss, and the learning
rates, we are able to prove a practical upper bound on the loss function along
the gradient descent path.

######  Theorem 3.5.

Let $L$ be large enough. Under Assumption 2.1 (i)–(v), let the parameter
$A^{(L)}(t)$ evolve according to the gradient descent dynamics (2.3) with
learning rates $\eta_{L}(t)$ until time $T_{L}\in\mathbb{N}$, chosen in such a
way that for each $t=0,\ldots,T_{L}-1$, we have

$\eta_{L}(t)\leq\frac{1}{160}N^{-1}d^{-1}e^{-10.5c_{0}}\quad\mbox{and}\quad\sum_{t=0}^{T_{L}-1}\eta_{L}(t)\leq
d^{-1}\log L.$ (3.7)

Then, for each $t=0,\ldots,T_{L}$, we have

$J_{L}(A(t))\leq\exp\left(-\frac{1}{32}N^{-1}e^{-2c_{0}}\sum_{t^{\prime}=0}^{t-1}\eta_{L}(t^{\prime})\right)J_{0}+34dc_{0}^{4}e^{6.4c_{0}}\left(\sum_{t^{\prime}=0}^{t-1}\eta_{L}(t^{\prime})\right)L^{-1}J_{0}.$

Theorem 3.5 is a local convergence result since we assume that the initial
loss lies below a certain level by Assumption 2.1 (v). We are able to show
convergence as $L\to\infty$ of the loss to zero when the horizon $T_{L}$
depends explicitly on the depth while satisfying (3.7).

###### Proof.

We choose $L$ big enough so that

$\frac{3}{64}N^{-1}d^{-1}c_{0}^{2}e^{2.2c_{0}}(\log L)^{3/2}\leq L^{1/2},\quad
34c_{0}^{4}e^{6.4c_{0}}\log L\leq L.$ (3.8)

Note that it trivially implies that $L\geq\max(4c_{0}^{2},5c_{0})$. In the
proof, we omit the explicit dependence in $L$. Denote $J_{0}\coloneqq
J_{L}(A(0))$ the initial loss. We first prove jointly that

$\displaystyle J_{L}(A(t))$ $\displaystyle\leq 2J_{0},$ (3.9)
$\displaystyle\max_{k}\left\lVert A_{k}(t)\right\rVert_{F}$ $\displaystyle\leq
c_{0}L^{-1/2},$ $\displaystyle\max_{k}\left\lVert
A_{k+1}(t)-A_{k}(t)\right\rVert_{F}$ $\displaystyle\leq
2^{-7/2}N^{-1/2}e^{-4.2c_{0}}L^{-1}.$

for $t=0,\ldots,T_{L}$ by induction on $t$. For $t=0$, by Assumption 2.1 (iv),
we directly have

$\displaystyle\max_{k}\left\lVert A_{k}(0)\right\rVert_{F}$ $\displaystyle\leq
d^{1/2}\sup_{k,m}\left\lVert A_{k,m}(0)\right\rVert_{2}\leq
L^{-1}<c_{0}L^{-1/2},$ (3.10) $\displaystyle\left\lVert
A_{k+1}(0)-A_{k}(0)\right\rVert_{F}$ $\displaystyle\leq
d^{1/2}\sup_{m}\left\lVert
A_{k+1,m}(0)-A_{k,m}(0)\right\rVert_{2}<2^{-7/2}N^{-1/2}e^{-4.2c_{0}}L^{-1}.$

Let $t\geq 0$. Assume that (3.9) holds true for all $t^{\prime}\leq t<T_{L}$.
We prove that (3.9) holds for $t+1$. Define $f_{k,m}(t)\coloneqq
f_{k,m}\left(A^{(L)}(t)\right)$ as in Lemma 3.3 and $g_{k}(t)\coloneqq
g_{k}\left(A^{(L)}(t)\right)$ as in Lemma 3.4. As
$L\geq\max(4c_{0}^{2},5c_{0})$, we can apply Lemma 3.3 and Lemma B.1 with the
induction hypothesis.

$\displaystyle f_{k,m}(t+1)^{1/2}$ $\displaystyle\leq
f_{k,m}(t)^{1/2}+\frac{1}{\sqrt{2}}e^{2.1c_{0}}\eta_{L}(t)\left(\frac{2}{N}\sum_{i=1}^{N}\ell\left(y_{i},\widehat{y}(x_{i},A(t))\right)\right)^{1/2}$
$\displaystyle=f_{k,m}(t)^{1/2}+e^{2.1c_{0}}\eta_{L}(t)J_{L}(A(t))^{1/2}.$
(3.11)

Similarly, we apply Lemma 3.4 with $c_{\alpha}=c_{0}$ and Lemma B.1 with the
induction hypothesis.

$\displaystyle g_{k}(t+1)$ $\displaystyle\leq
g_{k}(t)\left(1+e^{3.2c_{0}}\eta_{L}(t)L^{-1/2}J_{L}(A(t))^{1/2}\right)^{2}$
$\displaystyle\quad+\mathcal{O}\Big{(}c_{0}e^{2.1c_{0}}\left(c_{0}e^{1.1c_{0}}L^{-1}+2L^{-1/2}\right)\eta_{L}g_{k}(t)^{1/2}J_{L}\big{(}A(t)\big{)}^{1/2}\Big{)}.$
(3.12)

Now, we want to apply Lemma F.1 to bound $J_{L}(A(t))$. We check that using
Lemma 3.2, the assumptions of Lemma F.1 are verified for

$c_{\alpha}(t^{\prime})=c_{0},\quad\underline{c}\equiv\underline{c}(t^{\prime})=\frac{1}{16}N^{-1}e^{-2c_{0}},\quad\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern 1.0mu\equiv\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern
1.0mu(t^{\prime})=34dc_{0}^{4}e^{6.4c_{0}}J_{0}\quad\text{for}\,\,t^{\prime}\leq
t.$

Thus, as
$\eta_{L}(t)<2^{-5}5^{-1}N^{-1}d^{-1}e^{-10.5c_{0}}<2^{-1}c_{0}e^{-3.2c_{0}}$,
we deduce the following bound on the loss function at all times
$t^{\prime}=0,\ldots,t+1$.

$J_{L}(A(t^{\prime}))\leq\exp\left(-\frac{1}{2}\underline{c}\sum_{t^{\prime\prime}=0}^{t^{\prime}-1}\eta_{L}(t^{\prime\prime})\right)J_{0}+\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern
1.0muL^{-1}\sum_{t^{\prime\prime}=0}^{t^{\prime}-1}\eta_{L}(t^{\prime\prime})$
(3.13)

Bound on $J_{L}(A(t+1))$: Plugging in (3.7) and (3.8) into (3.13), we verify
that

$J_{L}(A(t+1))\leq\left(1+34c_{0}^{4}e^{6.4c_{0}}L^{-1}\log L\right)J_{0}\leq
2J_{L}(A(0)).$

Bound on $f_{k,m}(t+1)$: We plug (3.13) into (3.11) and sum over $t$ to deduce

$\displaystyle f_{k,m}(t+1)^{1/2}$ $\displaystyle\leq
f_{k,m}(0)^{1/2}+e^{2.1c_{0}}\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})J_{L}(A(t^{\prime}))^{1/2}$
$\displaystyle\leq\frac{1}{3\sqrt{2}}d^{-1/2}c_{0}L^{-1/2}+e^{2.1c_{0}}R_{L}(t),$
(3.14)

where we use (3.10) for the second inequality and

$R_{L}(t)\coloneqq\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})J_{L}(A(t^{\prime}))^{1/2}.$

To find an upper bound to $R_{L}(t)$, we use the inequality
$\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ in (3.13), with the help of (3.8):

$\displaystyle R_{L}(t)$
$\displaystyle\leq\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})\exp\left(-\frac{1}{4}\underline{c}\sum_{t^{\prime\prime}=0}^{t^{\prime}-1}\eta_{L}(t^{\prime\prime})\right)J_{0}^{1/2}+\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern
1.0mu^{1/2}L^{-1/2}\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})\left(\sum_{t^{\prime\prime}=0}^{t^{\prime}-1}\eta_{L}(t^{\prime\prime})\right)^{1/2}$

Now, we estimate the following quantity using (3.7):

$\displaystyle\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})\left(\sum_{t^{\prime\prime}=0}^{t^{\prime}-1}\eta_{L}(t^{\prime\prime})\right)^{1/2}$
$\displaystyle\leq\left(\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})\right)^{3/2}\leq
d^{-3/2}(\log L)^{3/2}.$

Next, we use the fact $\eta_{L}(t)<\mkern
1.0mu\overline{\mkern-1.5mu\eta\mkern 0.0mu}\mkern
1.0mu=2^{-5}5^{-1}N^{-1}d^{-1}e^{-10.5c_{0}}$ and

$\left(1-\exp\left(-\frac{1}{4}\underline{c}\mkern
1.0mu\overline{\mkern-1.5mu\eta\mkern 0.0mu}\mkern
1.0mu\right)\right)x\leq\mkern 1.0mu\overline{\mkern-1.5mu\eta\mkern
0.0mu}\mkern
1.0mu\left(1-\exp\left(-\frac{1}{4}\underline{c}x\right)\right)\,\,\,\mbox{for
all}\,\,x\in\left[0,\mkern 1.0mu\overline{\mkern-1.5mu\eta\mkern 0.0mu}\mkern
1.0mu\right]$

to deduce that the following sum is telescoping:

$\displaystyle\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})\exp\left(-\frac{1}{4}\underline{c}\sum_{t^{\prime\prime}=0}^{t^{\prime}-1}\eta_{L}(t^{\prime\prime})\right)$
$\displaystyle\leq\frac{1-\exp\left(-\frac{1}{4}\underline{c}\sum_{t^{\prime}=0}^{t}\eta_{L}(t^{\prime})\right)}{1-\exp(-\frac{1}{4}\underline{c}\mkern
1.0mu\overline{\mkern-1.5mu\eta\mkern 0.0mu}\mkern 1.0mu)}\mkern
1.0mu\overline{\mkern-1.5mu\eta\mkern 0.0mu}\mkern 1.0mu$ $\displaystyle\leq
8\underline{c}^{-1}.$

Hence, by Assumption 2.1 (v) and (3.8),

$\displaystyle R_{L}(t)$ $\displaystyle\leq
128Ne^{2c_{0}}J_{0}^{1/2}+6d^{1/2}c_{0}^{2}e^{3.2c_{0}}(\log
L)^{3/2}L^{-1/2}J_{0}^{1/2}$
$\displaystyle\leq\frac{2c_{0}}{3\sqrt{2}}d^{-1/2}e^{-2.1c_{0}}$ (3.15)

Plugging it in (3.14), we obtain

$f_{k,m}(t+1)^{1/2}\leq\frac{c_{0}}{3\sqrt{2}}d^{-1/2}+\frac{2c_{0}}{3\sqrt{2}}d^{-1/2}=\frac{c_{0}}{\sqrt{2}}d^{-1/2}.$

Hence, this completes the induction step for the norm of $A$:

$\left\lVert
A^{(L)}(t+1)\right\rVert_{F,\infty}\leq\sqrt{2}d^{1/2}L^{-1/2}\sup_{k,m}f_{k,m}(t+1)^{1/2}\leq
c_{0}L^{-1/2}.$

Bound on $g_{k}(t+1)$: By (3.8), $L^{1/2}\geq c_{0}e^{1.1c_{0}}$, so we can
rewrite (3.12):

$g_{k}(t+1)\leq
g_{k}(t)u_{L}(t)+g_{k}(t)^{1/2}\,\mathcal{O}\left(c_{0}e^{2.1c_{0}}\eta_{L}(t)L^{-1/2}J_{L}(A(t))^{1/2}\right),$

where

$u_{L}(t)\coloneqq\left(1+\eta_{L}(t)L^{-1/2}e^{3.2c_{0}}J_{L}(A(t))^{1/2}\right)^{2}.$

We can thus apply Lemma G.4 (ii), together with the identity $1+x\leq\exp(x)$
and (3.15) to deduce that

$\displaystyle g_{k}(t+1)^{1/2}$
$\displaystyle\leq\exp\left(e^{3.2c_{0}}R_{L}(t)L^{-1/2}\right)\left(g_{k}(0)^{1/2}+\mathcal{O}\left(c_{0}e^{2.1c_{0}}R_{L}(t)L^{-1/2}\right)\right)$
$\displaystyle\leq\exp\left(c_{0}e^{1.1c_{0}}L^{-1/2}\right)\left(1+\mathcal{O}(c_{0}^{2}L^{-1/2})\right)g_{k}(0)^{1/2}$
$\displaystyle\leq\sqrt{2}g_{k}(0)^{1/2}.$

The last inequality is derived with the help of (3.8). We finish the induction
step by observing that $g_{k,m}(0)^{1/2}\leq
2^{-9/2}N^{-1/2}d^{-1/2}e^{-4.2c_{0}}$ by Assumption 2.1 (iv).

Convergence of $J_{L}(A(T_{L}))\to 0$: We now have all the tools to deduce the
rate of convergence of $J_{L}(A(T_{L}))$ to zero. We observe from the
induction result above that the assumptions of Lemma F.1 are verified for
$c_{\alpha}(t)=c_{0}$, $\underline{c}(t)=2^{-4}N^{-1}e^{-2c_{0}}$ and $\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern
1.0mu(t)=34dc_{0}^{4}e^{6.4c_{0}}J_{0}$ by Lemma 3.2, for each
$t\in\left[0,T\right)$. In particular, we have

$J_{L}(A(T_{L}))\leq\exp\left(-\frac{1}{32}N^{-1}e^{-2c_{0}}\sum_{t=0}^{T_{L}-1}\eta_{L}(t)\right)J_{0}+34dc_{0}^{4}e^{6.4c_{0}}\left(\sum_{t=0}^{T_{L}-1}\eta_{L}(t)\right)L^{-1}J_{0}.$
(3.16)

∎

######  Remark 3.6.

Let $\eta_{0}>0$ be a fixed learning rate, independent of $k,L$ and $t$, and
let $J_{0}\coloneqq J_{L}\left(A^{(L)}(0)\right)$ be the initial loss. Observe
that from Theorem 3.5, if we choose

  * •

$\eta_{L}(t)=\eta_{0}$ and $T_{L}^{\,\mathrm{const}}=\Theta(\eta_{0}^{-1}\log
L)$, then conditions (3.7) are satisfied, so we deduce

$J_{L}\left(A^{(L)}(T_{L}^{\,\mathrm{const}})\right)\leq\exp(-\underline{c}\eta_{0}T_{L}^{\,\mathrm{const}})J_{0}+\mathcal{O}(\eta_{0}T_{L}^{\,\mathrm{const}}L^{-1}).$

Hence, for an error level $\epsilon>0$, gradient descent with constant
learning rate for a network of depth $L=\Omega(1/\epsilon)$ reaches
$J_{L}\left(A^{(L)}(T_{L}^{\,\mathrm{const}})\right)<\epsilon$ in
$\Theta(\eta_{0}^{-1}\log 1/\epsilon)$ iterations.

  * •

$\eta_{L}(t)=\eta_{0}(t+1)^{-1}$ and
$T_{L}^{\,\mathrm{decay}}=\Theta(\exp(\eta_{0}^{-1}\log L))$, then conditions
(3.7) are satisfied. We deduce that

$J_{L}\left(A^{(L)}(T_{L}^{\,\mathrm{decay}})\right)\leq\exp(-\underline{c}\eta_{0}\log
T_{L}^{\,\mathrm{decay}})J_{0}+\mathcal{O}(\eta_{0}\log
T_{L}^{\,\mathrm{decay}}L^{-1}).$

Hence, for an error level $\epsilon>0$, gradient descent with decaying
learning rate for a network of depth $L=\Omega(1/\epsilon)$ reaches
$J_{L}\left(A^{(L)}(T_{L}^{\,\mathrm{decay}})\right)<\epsilon$ in
$\Theta(\exp(\eta_{0}^{-1}\log 1/\epsilon))$ iterations.

The above convergence rates above are confirmed by our experiments in Section
4. Note that gradient descent converges exponentially faster when using
constant learning rates rather than decaying ones. This is because the
parameters $A^{(L)}(t)$ and the gradients $\nabla_{A}J_{L}(A^{(L)}(t))$ are
already on the same scale $\mathcal{O}(L^{-1/2})$. Note also that Theorem 3.5
is not in contradiction with [5, Theorem 6] stating that gradient descent
might get stuck at the critical point
$\left(\delta^{(L)},A^{(L)}\right)=(0,0)$ that is usually not a global
minimizer. Indeed, we force $\delta^{(L)}$ to have a non-trivial scaling by
Assumption 2.1 (iv), so that $(0,0)$ is simply not a point in the parameter
space.

###  3.4 Scaling limit of trained weights

In many cases the trained weights, viewed as a function of the layer index
$k/L$, have a scaling limit which is a function defined on $[0,1]$. We show
that such a limit then admits finite $p$-variation with $p=2$.

######  Proposition 3.7.

Let $\left(A^{(L)}(t)\colon t=1,\ldots,T_{L}\right)$ follow the gradient
descent dynamics (2.3), where the assumptions of Theorem 3.5 are satisfied for
$T=T_{L}$. Assume there exists $\mkern 1.0mu\overline{\mkern-1.5muA\mkern
0.0mu}\mkern 1.0mu^{*}\coloneqq\left[0,1\right]\to\mathbb{R}^{d\times d}$ such
that

$\displaystyle\mathop{\sup}_{s\in[0,1]}L^{1/2}\left\lVert
L^{1/2}A_{\left\lfloor Ls\right\rfloor}^{(L)}(T_{L})-\mkern
1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern 1.0mu^{*}_{s}\right\rVert_{F}$
$\displaystyle\mathop{\longrightarrow}^{L\to\infty}0$ (3.17)

Then, the scaling limit $\mkern 1.0mu\overline{\mkern-1.5muA\mkern
0.0mu}\mkern 1.0mu^{*}$ has finite $p$-variation with $p=2$.

Conditions 3.17 may seem strong, but they are related to the norm
$f^{(L)}_{k,m}(T_{L})$ defined in Lemma 3.3 having a limit as $L\to\infty$.
Under the hypothesis of Theorem 3.5, we have shown in the proof of Theorem 3.5
that the norm $f^{(L)}_{\left\lfloor Ls\right\rfloor,m}(T_{L})$ stay uniformly
bounded (in $s$ and $m$) as $L\to\infty$. Condition 3.17 has also been
verified in numerical experiments, see Section 4.3.

###### Proof.

Fix a partition $\pi=\left\\{0=s_{0}<s_{1}<\ldots<s_{K}=1\right\\}$, where the
mesh of the partition $\left\lVert\pi\right\rVert$ is small enough. In the
following, $c>0$ denotes a constant independant of $s$ and $L$. For
$i=1,\ldots,K-1$, let $L_{i}\in\mathbb{N}$ big enough so that Theorem 3.5
applies. We estimate directly

$\displaystyle\left\lVert\mkern 1.0mu\overline{\mkern-1.5muA\mkern
0.0mu}\mkern 1.0mu^{*}_{s_{i+1}}-\mkern 1.0mu\overline{\mkern-1.5muA\mkern
0.0mu}\mkern 1.0mu^{*}_{s_{i}}\right\rVert_{F}$ $\displaystyle\leq\left\lVert
L_{i}^{1/2}A_{\left\lfloor
L_{i}s_{i+1}\right\rfloor}^{(L_{i})}(T_{L_{i}})-\mkern
1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern
1.0mu^{*}_{s_{i+1}}\right\rVert_{F}+\left\lVert L_{i}^{1/2}A_{\left\lfloor
L_{i}s_{i}\right\rfloor}^{(L_{i})}(T_{L_{i}})-\mkern
1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern
1.0mu^{*}_{s_{i}}\right\rVert_{F}$ $\displaystyle+L_{i}^{1/2}\left\lVert
A^{(L_{i})}_{\left\lfloor
L_{i}s_{i+1}\right\rfloor}(T_{L_{i}})-A^{(L_{i})}_{\left\lfloor
L_{i}s_{i}\right\rfloor}(T_{L_{i}})\right\rVert_{F}$ $\displaystyle\leq
cL_{i}^{-1/2}+L_{i}^{1/2}\left\lVert A^{(L_{i})}_{\left\lfloor
L_{i}s_{i+1}\right\rfloor}(T_{L_{i}})-A^{(L_{i})}_{\left\lfloor
L_{i}s_{i}\right\rfloor}(T_{L_{i}})\right\rVert_{F}$

We now use the proof of Theorem 3.5 to deduce a uniform bound (in $k$ and $L$)
on the quantity $g^{(L)}_{k}(T_{L})$ defined in Lemma 3.4. That means,
$L\left\lVert A^{(L)}_{\left\lfloor
Ls\right\rfloor}(T_{L})-A^{(L)}_{\left\lfloor
Ls\right\rfloor+1}(T_{L})\right\rVert_{F}<c<\infty$. We can apply the triangle
inequality to deduce

$\left\lVert\mkern 1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern
1.0mu^{*}_{s_{i+1}}-\mkern 1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern
1.0mu^{*}_{s_{i}}\right\rVert_{F}\leq
cL_{i}^{-1/2}+cL_{i}^{-1/2}\left(\left\lfloor
L_{i}s_{i+1}\right\rfloor-\left\lfloor L_{i}s_{i}\right\rfloor\right)\leq
cL_{i}^{-1/2}+cL_{i}^{1/2}\left|s_{i+1}-s_{i}\right|.$

Hence,

$\sum_{i=0}^{K-1}\left\lVert\mkern 1.0mu\overline{\mkern-1.5muA\mkern
0.0mu}\mkern 1.0mu^{*}_{s_{i+1}}-\mkern 1.0mu\overline{\mkern-1.5muA\mkern
0.0mu}\mkern 1.0mu^{*}_{s_{i}}\right\rVert_{F}^{2}\leq
c\sum_{i=0}^{K-1}L_{i}^{-1}+L_{i}\left|s_{i+1}-s_{i}\right|^{2}.$ (3.18)

As $\left\lVert\pi\right\rVert$ is small enough, we can choose
$L_{i}=\Theta(\left|s_{i+1}-s_{i}\right|^{-1})$ to deduce that the RHS of
(3.18) is bounded uniformly in $\pi$. Taking a supremum over all such
partitions then show that $\mkern 1.0mu\overline{\mkern-1.5muA\mkern
0.0mu}\mkern 1.0mu^{*}$ has finite $p$-variation with $p=2$. ∎

##  4 Numerical experiments

To illustrate the results of Section 3, we design numerical experiments with
the following set-up. We have a fixed training set
$\left\\{(x_{i},y_{i}):i=1,\ldots,N\right\\}$ in
$\mathbb{R}^{d}\times\mathbb{R}^{d}$, where $d$ is the dimension of the inputs
and outputs and $N$ is the size of the dataset. For any depth
$L\in\mathbb{N}$, we initialize the weights of the network (2.1) with
$\delta_{L}=L^{-\alpha_{0}}$ and each entry of $A_{k}^{(L)}$ is independent
and normally distributed with standard deviation $d^{-1}L^{-\beta_{0}}$, where
$\alpha_{0},\beta_{0}\in\left[0,1\right]$. The weights are trained using
gradient descent on the (unregularized) mean squared error $J_{L}$ defined in
(2.2) with a fixed learning rate $\eta_{0}$ independent of $d,k,L$ and the
training time $t$. We perform a fixed number $T\in\mathbb{N}$ of gradient
updates, with no early stopping.

###  4.1 Identification of scaling behavior

We run two experiments to discover the best scaling for $\delta_{L}$. Denote
$\alpha_{t}$ the scaling of $\delta_{L}$ at time $t$, i.e. $\alpha_{t}\propto
L^{-\alpha_{t}}$, and denote $\beta_{t}$ the scaling of the weights
$A^{(L)}(t)$ at time $t$, i.e. $A^{(L)}(t)\propto L^{-\beta_{t}}$. The first
experiment is to let $\delta_{L}$ trainable with gradient descent with
learning rate $\eta_{0}$, and observe the resulting scaling $\alpha_{t}$.

Figure 1: Left: scaling $\alpha_{t}$ of $\delta_{L}$ against the initial
scaling $\alpha_{0}$ for different training times. Right: Average loss value
across depths $L\in\left\\{2^{k}:k\in\left[3,12\right]\right\\}$ for different
initializations $\alpha_{0}$, as a function of the number of gradient steps
$t$.

We observe in Figure 1 (left) that $\alpha_{t}$ tend to get closer to $1/2$ as
$t$ increases. However, this is far from being exact, even though the networks
have all converged, see Figure 1 (right). It is interesting to note that
$\alpha_{0}=1/2$ is a fixed point, meaning that the networks initialized with
this scaling will keep $\alpha_{t}\approx 1/2$ during the entire training. The
second experiment is to let $\delta_{L}=L^{-\alpha_{0}}$ at initialization and
keep it fixed during training, i.e. $\alpha_{t}=\alpha_{0}$ for each $t$. We
thus have weights $A^{(L)}(0)$ that scale like $L^{-\beta_{0}}$ initially, and
that are updated with $\eta_{L}(t)\nabla_{A_{k}}J_{L}(A^{(L)}(t))\propto
L^{-\alpha_{0}}J_{L}(A^{(L)}(t))^{1/2}$ by Lemma C.1. Thus, it is reasonable
to expect that if $\beta_{0}>\alpha_{0}$, and the loss $J_{L}$ at small times
$t$ is independent of the depth, then $\beta_{t}\approx\alpha_{0}$ for small
times $t$.

Figure 2: Both figures: horizontal axis is the initial scaling $\beta_{0}$ of
the weights $A$, and the vertical axis is the fixed scaling $\alpha_{0}$ of
$\delta_{L}$. Left: Final total scaling $\alpha_{0}+\beta_{T}$. Right: Average
final loss after $T=200$ epochs. The depths at which we train our networks are
$L\in\left\\{2^{k}:k\in\left[3,10\right]\right\\}$.

In fact, we observe in Figure 2 (left) that the total scaling
$\alpha_{0}+\beta_{T}$ is independent of $\beta_{0}$ and is roughly equal to
$2\alpha_{0}$. We observe in Figure 2 (right) that the parameters that gives
the best performance is around $\alpha_{0}=1/2$, again independently of
$\beta_{0}$. This is expected, as

$h_{k}^{(L)}-h_{k-1}^{(L)}=\delta_{L}\sigma_{d}\left(A_{k}^{(L)}h_{k-1}^{(L)}\right)\propto
L^{-\alpha_{0}-\beta},$

so the final scaling of the increments of the hidden states is roughly
$2\alpha_{0}$, which should be around $1$ to guarantee stability of the large
depth limit.

###  4.2 Rate of convergence

We now verify that the convergence rates of gradient descent agree with the
theoretical rates derived in Remark 3.6. To do so, we run our experiments with
different initial learning rates, and take the average loss curve across the
depths. We then plot the number of gradient steps needed to reach a certain
loss level.

Figure 3: Both figures: horizontal axis is the inverse loss level
$1/\epsilon$, in log-scale, and the vertical axis is the number of gradient
steps needed for the average loss to drop below $\epsilon$. The average is
taken over the depths $L\in\left\\{2^{k}:k\in\left[3,10\right]\right\\}$.
Left: constant learning rates $\eta_{L}(t)=\eta_{0}$. Right: decaying learning
rates $\eta_{L}(t)=\eta_{0}(t+1)^{-1}$.

We observe in Figure 3 that the number of gradient steps needed to attain a
given level $\epsilon$ is linear in $\log(1/\epsilon)$ for constant learning
rates, and exponential in $\log(1/\epsilon)$ for learning rates decaying like
$1/t$. We also see that in both cases, the rate of convergence is inversely
proportional to the initial learning rate $\eta_{0}$.

###  4.3 Emergence of regularity of weights as a function of the layer index

Recall the results of Proposition 3.7 stating that under condition (3.17), the
rescaled trained weights $L^{1/2}A^{(L)}_{\left\lfloor Ls\right\rfloor}(T)$
converge to a limit $\mkern 1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern
1.0mu^{*}_{s}$ that has finite $2$-variation. We verify that condition (3.17)
holds by running experiments for varying depths and looking at the quantities

$\mkern 1.0mu\overline{\mkern-1.5muf\mkern 0.0mu}\mkern
1.0mu^{(L)}(t)\coloneqq\frac{1}{2}\sum_{k=1}^{L}\left\lVert
A^{(L)}_{k}(t)\right\rVert_{F}^{2}\quad\text{and}\quad\mkern
1.0mu\overline{\mkern-1.5mug\mkern 0.0mu}\mkern
1.0mu^{(L)}(t)\coloneqq\frac{1}{2}L\sum_{k=1}^{L-1}\left\lVert
A^{(L)}_{k+1}(t)-A_{k}^{(L)}(t)\right\rVert_{F}^{2}.$

Figure 4:  Evolution of weight norms along gradient descent path for different
depths $L\in\left\\{2^{4},2^{5},2^{6},2^{8},2^{10}\right\\}$. Left:
$L^{2}$-type norm $\mkern 1.0mu\overline{\mkern-1.5muf\mkern 0.0mu}\mkern
1.0mu^{(L)}(t)$ as a function of gradient iterations. Right: Quadratic
variation-type norm $\mkern 1.0mu\overline{\mkern-1.5mug\mkern 0.0mu}\mkern
1.0mu^{(L)}(t)$ as a function of gradient iterations.

We observe in Figure 4 that at initialization $t=0$, the sum of the squared
norms $\mkern 1.0mu\overline{\mkern-1.5muf\mkern 0.0mu}\mkern 1.0mu^{(L)}$ is
$\mathcal{O}(L^{-1})$, and becomes $\mathcal{O}(1)$ during training $t\gg 1$.
However, the smoothness of the weights as measured by $\mkern
1.0mu\overline{\mkern-1.5mug\mkern 0.0mu}\mkern 1.0mu^{(L)}(t)$ is constant
with $t$ for large $L$. That means, the conservation of smoothness during
training is a feature of the architecture (smooth activation function) and of
gradient descent, not of the particular weight initialization nor of a
particular scaling.

We observe in Figure 5 that as $L\to\infty$, the rescaled trained weights
converge to a limit $\mkern 1.0mu\overline{\mkern-1.5muA\mkern 0.0mu}\mkern
1.0mu^{*}$. This is a striking result, indicative of the stability of this
network architecture [13]: there is no a priori reason that networks with
different depths and trained independently of each other should behave
similarly. The limiting behaviour of trained weights of residual networks with
a smooth activation function was first observed in [7], where the limit is
explicitly derived and proved.

Figure 5: Scatter plot of the rescaled weights $L^{1/2}A^{(L)}_{k,(7,18)}(T)$
for different values of $L\in\left\\{4^{x}:x\in[3,6]\right\\}$ at the end of
the training $T=500$. Horizontal axis is the scaled layer index $k/L$.

##  5 Conclusion

We prove linear convergence of gradient descent to a global minimum of the
training loss for deep residual networks with constant layer width and smooth
activation function. We further show that if the trained weights, as a
function of the layer index, admits a scaling limit as the depth of the
network tends to infinity, then it has finite $2-$variation.
A natural question to investigate next is the generalization capability of the
trained weights obtained by gradient descent, which we characterize in this
work. Indeed, it is still an open question whether the weights obtained by
gradient descent admit the tightest generalization gap among all the other
global minima. Also, our work can be generalized to study other residual
architectures (for example with ReLU activation) by looking at alternative
norms along the gradient descent path.

## References

  * [1] Z. Allen-Zhu, Y. Li, and Y. Liang, Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers, in Advances in Neural Information Processing Systems, 2019, pp. 6158–6169.
  * [2] Z. Allen-Zhu, Y. Li, and Z. Song, A Convergence Theory for Deep Learning via Over-Parameterization, in Proceedings of Machine Learning Research, vol. 97, 2019, pp. 242–252.
  * [3] S. Arora, N. Cohen, N. Golowich, and W. Hu, A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks, in 7th International Conference on Learning Representations (ICLR), 2019.
  * [4] P. Bartlett, D. Helmbold, and P. Long, Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks, in International Conference on Machine Learning (ICML), PMLR, 2018, pp. 521–530.
  * [5] P. L. Bartlett, S. N. Evans, and P. M. Long, Representing smooth functions as compositions of near-identity functions with implications for deep network optimization, arXiv preprint:1804.05012, (2018).
  * [6] L. Chizat, E. Oyallon, and F. Bach, On Lazy Training in Differentiable Programming, in Advances in Neural Information Processing Systems, 2019.
  * [7] A.-S. Cohen, R. Cont, A. Rossier, and R. Xu, Scaling Properties of Deep Residual Networks, in Proceedings of the 38th International Conference on Machine Learning, 2021, pp. 2039–2048.
  * [8] A. Daniely, R. Frostig, and Y. Singer, Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity, in Advances in Neural Information Processing Systems 29, 2016, pp. 2253–2261.
  * [9] S. Du and W. Hu, Width Provably Matters in Optimization for Deep Linear Neural Networks, in Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, 2019, pp. 1655–1664.
  * [10] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai, Gradient Descent Finds Global Minima of Deep Neural Networks, in Proceedings of the 36th International Conference on Machine Learning, 2019, pp. 1675–1685.
  * [11] W. E, C. Ma, Q. Wang, and L. Wu, Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections, arXiv preprint arXiv:1904.05263, (2019).
  * [12] R. Eldan and O. Shamir, The Power of Depth for Feedforward Neural Networks, in 29th Annual Conference on Learning Theory, PMLR, 2016, pp. 907–940.
  * [13] E. Haber and L. Ruthotto, Stable architectures for deep neural networks, Inverse Problems, 34 (2018).
  * [14] M. Hardt and T. Ma, Identity Matters in Deep Learning, in 5th International Conference on Learning Representations (ICLR), 2017.
  * [15] K. He, X. Zhang, S. Ren, and J. Sun, Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification, in Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2015.
  * [16] , Deep Residual Learning for Image Recognition, in 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, IEEE Computer Society, 2016, pp. 770–778.
  * [17] K. Kawaguchi, Deep Learning without Poor Local Minima, in Advances in Neural Information Processing Systems 29, 2016, pp. 586–594.
  * [18] T. Laurent and J. von Brecht, Deep Linear Networks with Arbitrary Loss: All Local Minima Are Global, in Proceedings of Machine Learning Research, vol. 80, 2018.
  * [19] H. Lu and K. Kawaguchi, Depth Creates No Bad Local Minima, 2017.
  * [20] Y. Lu, C. Ma, Y. Lu, J. Lu, and L. Ying, A mean field analysis of deep resnet and beyond: Towards provably optimization via overparameterization from depth, in International Conference on Machine Learning, PMLR, 2020, pp. 6426–6436.
  * [21] B. Neyshabur, R. Tomioka, and N. Srebro, In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning, arXiv preprint arXiv:1412.6614, (2014).
  * [22] H. Petzka and C. Sminchisescu, Non-attracting Regions of Local Minima in Deep and Wide Neural Networks, Journal of Machine Learning Research, 22 (2021), pp. 1–34.
  * [23] R. Sun, D. Li, S. Liang, T. Ding, and R. Srikant, The Global Landscape of Neural Networks: An Overview, IEEE Signal Processing Magazine, 37 (2020), pp. 95–108.
  * [24] M. Telgarsky, Representation Benefits of Deep Feedforward Networks, arXiv preprint arXiv:1509.08101, (2015).
  * [25] L. Wu, Q. Wang, and C. Ma, Global Convergence of Gradient Descent for Deep Linear Residual Networks, in Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [26] G. Yang and S. Schoenholz, Mean Field Residual Networks: On the Edge of Chaos, in Advances in Neural Information Processing Systems 30, 2017, pp. 7103–7114.
  * [27] C. Yun, S. Krishnan, and H. Mobahi, A Unifying View on Implicit Bias in Training Linear Neural Networks, arXiv preprint arXiv:2010.02501, (2020).
  * [28] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals, Understanding Deep Learning (still) Requires Rethinking Generalization, Communications of the ACM, 64 (2021), pp. 107–115.
  * [29] H. Zhang, D. Yu, M. Yi, W. Chen, and T.-Y. Liu, Convergence Theory of Learning Over-parameterized ResNet: A Full Characterization, 2019.
  * [30] D. Zou and Q. Gu, An Improved Analysis of Training Over-parameterized Deep Neural Networks, in Advances in Neural Information Processing Systems, 2019, pp. 2055–2064.
  * [31] D. Zou, P. M. Long, and Q. Gu, On the Global Convergence of Training Deep Linear ResNets, 8th International Conference on Learning Representations (ICLR), (2020).

##  Appendix A Gradient of the loss function with respect to parameters

Let $x,y\in\mathbb{R}^{d}$ and $\alpha^{(L)}\in\mathbb{R}^{L\times d\times
d}$. We want to compute the gradient of $\ell(y,\widehat{y}(x,\alpha^{(L)}))$
with respect to the network parameters $\\{\alpha^{(L)}_{k}:k=1,\ldots,L\\}$.
Fix $1\leq k\leq L$ and $1\leq m,n\leq d$. We first observe that

$\displaystyle\frac{\partial\ell}{\partial\alpha^{(L)}_{k,mn}}\left(y,\widehat{y}(x,\alpha^{(L)})\right)$
$\displaystyle=\nabla_{\widehat{y}}\,\ell\left(y,\widehat{y}\left(x,\alpha^{(L)}\right)\right)^{\top}\frac{\partial
h_{L}^{(L)}}{\partial h^{(L)}_{k}}\frac{\partial
h_{k}^{(L)}}{\partial\alpha^{(L)}_{k,mn}}.$

By induction, we obtain

$\displaystyle M_{k}^{(L)}\coloneqq\frac{\partial h_{L}^{(L)}}{\partial
h_{k}^{(L)}}$ $\displaystyle=\prod_{j=k+1}^{L}\frac{\partial
h_{j}^{(L)}}{\partial h_{j-1}^{(L)}}$
$\displaystyle=\prod_{j=k+1}^{L}\left(I_{d}+\delta_{L}\frac{\partial}{\partial
h_{j-1}^{(L)}}\sigma_{d}\left(\alpha^{(L)}_{j}h_{j-1}^{(L)}\right)\right)$
$\displaystyle=\prod_{j=k+1}^{L}\left(I_{d}+\delta_{L}\mathrm{diag}\left(\nabla\sigma_{d}\left(\alpha^{(L)}_{j}h_{j-1}^{(L)}\right)\right)\alpha^{(L)}_{j}\right).$
(A.1)

We also have

$\frac{\partial
h_{k}^{(L)}}{\partial\alpha^{(L)}_{k,mn}}=\delta_{L}\sigma^{\prime}\left(\left(\alpha^{(L)}_{k}h_{k-1}^{(L)}\right)_{m}\right)h_{k-1,n}^{(L)}e_{m}\in\mathbb{R}^{d}.$

Denote
$\dot{\sigma}^{(L)}_{k,m}\coloneqq\sigma^{\prime}\left(\left(\alpha^{(L)}_{k}h_{k-1}^{(L)}\right)_{m}\right)$.
Regrouping everything, we get

$\frac{\partial\ell}{\partial\alpha^{(L)}_{k,mn}}=\delta_{L}\,h_{k-1,n}^{(L)}\,\dot{\sigma}^{(L)}_{k,m}\,\nabla_{\widehat{y}}\,\ell\left(y,\widehat{y}\left(x,\alpha^{(L)}\right)\right)^{\top}M_{k}^{(L)}e_{m}.$
(A.2)

##  Appendix B Boundedness of hidden states and Jacobians

This section contains two useful results for our analysis.

######  Lemma B.1.

Let $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$ and $c_{\alpha}>0$ such
that $L\geq 5c_{\alpha}$ and

$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}=\max_{k=1,\ldots,L}\left\lVert\alpha^{(L)}_{k}\right\rVert_{F}\leq
c_{\alpha}L^{-1/2}.$

Then, under Assumption 2.1 (i)–(ii), we have that for all $x\in\mathbb{R}^{d}$
and for every $k=1,\ldots,L$,

$\left\lVert x\right\rVert_{2}e^{-2c_{\alpha}}\leq\left\lVert
h^{x,\,(L)}_{k}\right\rVert_{2}\leq\left\lVert
x\right\rVert_{2}e^{1.1c_{\alpha}}\hskip 28.45274pt\mbox{and}\hskip
28.45274pt\left\lVert M^{x,\,(L)}_{k}e_{m}\right\rVert_{2}\leq
e^{c_{\alpha}}.$

Note that we did not try to optimize the constants in front of the bounds, and
one can easily sharpen them if needed.

###### Proof.

We follow the same lines as [2]. Fix $L\geq 5c_{\alpha}$. In the proof, we
omit the explicit dependence in $L$. First, note that we can write the
logarithm of the norm of the hidden state as follows:

$\displaystyle\log\left\lVert h_{k}\right\rVert$
$\displaystyle=\log\left\lVert
x\right\rVert+\frac{1}{2}\sum_{j=1}^{k}\log\frac{\left\lVert
h_{j}\right\rVert^{2}}{\left\lVert h_{j-1}\right\rVert^{2}}$
$\displaystyle=\log\left\lVert
x\right\rVert+\frac{1}{2}\sum_{j=1}^{k}\log\left(1+\underbrace{\frac{2\delta_{L}}{\left\lVert
h_{j-1}\right\rVert^{2}}\Big{\langle}h_{j-1},\sigma(\alpha_{j}h_{j-1})\Big{\rangle}+\delta_{L}^{2}\frac{\left\lVert\sigma(\alpha_{j}h_{j-1})\right\rVert^{2}}{\left\lVert
h_{j-1}\right\rVert^{2}}}_{\eqqcolon\,\Delta_{j}}\right).$

We can bound $\Delta_{j}$ further:

$\displaystyle\Delta_{j}$ $\displaystyle\leq
2\delta_{L}\left\lVert\alpha_{j}\right\rVert_{F}+\delta_{L}^{2}\left\lVert\alpha_{j}\right\rVert_{F}^{2}$
$\displaystyle\leq
2c_{\alpha}L^{-1}+c_{\alpha}^{2}L^{-2}\leq\frac{11}{5}c_{\alpha}L^{-1}.$ (B.1)

The first inequality holds by Cauchy-Schwartz and Assumption 2.1 (ii), the
second by hypothesis, and the third by Assumption 2.1 (i). Thus, we conclude
the proof of the upper bound by noting that $\log(1+z)\leq z$ for all $z>-1$.
For the lower bound, first observe that Cauchy-Schwartz yields

$\Delta_{j}\geq-2\delta_{L}\left\lVert\alpha_{j}\right\rVert_{F}\geq-2c_{\alpha}L^{-1}.$

From (B.1), we also have
$\left|\Delta_{j}\right|\leq\frac{11}{25}<\frac{1}{2}$, so we can use the fact
that $\log(1+z)\geq z-z^{2}$ for all $\left|z\right|<\frac{1}{2}$ to deduce
that

$\displaystyle\log\left\lVert h_{k}\right\rVert$
$\displaystyle\geq\log\left\lVert
x\right\rVert+\frac{1}{2}\sum_{j=1}^{k}\left(\Delta_{j}-\Delta_{j}^{2}\right)$
$\displaystyle\geq\log\left\lVert x\right\rVert-
c_{\alpha}-\frac{121}{25}c_{\alpha}^{2}L^{-1}\geq\log\left\lVert
x\right\rVert-2c_{\alpha},$

which concludes the proof for the lower bound on the hidden states.
For the upper bound on the Jacobians, we apply Lemma G.1 repeatedly on $M_{k}$
to get

$\displaystyle\log\left\lVert M_{k}e_{m}\right\rVert_{2}$
$\displaystyle\leq\log\left\lVert
e_{m}\right\rVert_{2}+\sum_{j=k+1}^{L}\log\left\lVert
I_{d}+\delta_{L}\mathrm{diag}\left(\nabla\sigma_{d}\left(\alpha_{j}h_{j-1}\right)\right)\alpha_{j}\right\rVert_{2}$
$\displaystyle\leq\sum_{j=k+1}^{L}\delta_{L}\left\lVert\mathrm{diag}\left(\nabla\sigma_{d}\left(\alpha_{j}h_{j-1}\right)\right)\alpha_{j}\right\rVert_{2}\leq\sum_{j=k+1}^{L}\delta_{L}\left\lVert\alpha_{j}\right\rVert_{F}\leq
c_{\alpha},$

where we use
$\left\lVert\cdot\right\rVert_{2}\leq\left\lVert\cdot\right\rVert_{F}$ and
Assumption 2.1 (ii) in the third inequality. ∎

We deduce directly an upper bound on the loss function $J_{L}$ that does not
depend on $L$.

######  Corollary B.2.

Under the same hypotheses as Lemma B.1, we have

$J_{L}\left(\alpha^{(L)}\right)\leq 1+e^{2.2c_{\alpha}}.$

###### Proof.

By definition of the loss function and using Lemma B.1, we have

$\displaystyle J_{L}\left(\alpha^{(L)}\right)$
$\displaystyle=\frac{1}{2N}\sum_{i=1}^{N}\left\lVert
y_{i}-\widehat{y}_{L}\left(x_{i},\alpha^{(L)}\right)\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{1}{2N}\sum_{i=1}^{N}2\left\lVert
y_{i}\right\rVert^{2}+2\left\lVert h^{x_{i},\,(L)}_{L}\right\rVert_{2}^{2}\leq
1+e^{2.2c_{\alpha}}.$

∎

##  Appendix C Upper bounds on the gradient and Hessian of the loss function

######  Lemma C.1.

Let $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$ and $c_{\alpha}>0$ such
that $L\geq 5c_{\alpha}$ and
$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq c_{\alpha}L^{-1/2}$. Then,
under Assumption 2.1 (i)–(ii), for $k=1,\ldots L$, it holds that

$\left\lVert\nabla_{\alpha_{k}}J_{L}\left(\alpha^{(L)}\right)\right\rVert_{F}^{2}\leq
2de^{4.2c_{\alpha}}L^{-1}J_{L}\left(\alpha^{(L)}\right).$

###### Proof.

Fix $L\geq 5c_{\alpha}$. In the proof, we omit the explicit dependence in $L$.
We first use Cauchy-Schwartz and (A.2) to bound the Frobenius norm.

$\displaystyle\left\lVert\nabla_{\alpha_{k}}J_{L}(\alpha)\right\rVert_{F}^{2}$
$\displaystyle=\sum_{m,n=1}^{d}\left(\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}(\alpha)\right)^{2}$
$\displaystyle\leq\sum_{m,n=1}^{d}\frac{1}{N}\sum_{i=1}^{N}\left(\frac{\partial\ell}{\partial\alpha_{k,mn}}\left(y_{i},\widehat{y}(x_{i},\alpha)\right)\right)^{2}$
$\displaystyle\leq\sum_{m,n=1}^{d}\frac{\delta_{L}^{2}}{N}\sum_{i=1}^{N}\left(h^{x_{i}}_{k-1,n}\right)^{2}\left\lVert\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)\right\rVert_{2}^{2}\left\lVert
M_{k}^{x_{i}}e_{m}\right\rVert_{2}^{2}$
$\displaystyle=\frac{2L^{-1}}{N}\sum_{i=1}^{N}\left\lVert
h^{x_{i}}_{k-1}\right\rVert_{2}^{2}\ell(y_{i},\widehat{y}(x_{i},\alpha))\left\lVert
M_{k}^{x_{i}}\right\rVert_{F}^{2}$ $\displaystyle\leq
2de^{4.2c_{\alpha}}L^{-1}J_{L}(\alpha),$

where we use the fact that
$2\ell(y,\widehat{y})=\left\lVert\nabla_{\widehat{y}}\,\ell\left(y,\widehat{y}\right)\right\rVert_{2}^{2}$
and Lemma B.1 in the last inequality. ∎

Finally, we derive an upper bound on the spectral norm of the Hessian of the
loss function.

######  Lemma C.2.

Let $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$ and $c_{\alpha}>0$ such
that $L\geq 5c_{\alpha}$ and
$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq c_{\alpha}L^{-1/2}$. Then,
under Assumption 2.1 (i)–(ii), we have

$\left\lVert\nabla^{2}_{\alpha}J_{L}\left(\alpha^{(L)}\right)\right\rVert_{2}\leq
5de^{4.3c_{\alpha}}.$

###### Proof.

Fix $L\geq 5c_{\alpha}$. In the proof, we omit the explicit dependence in $L$.
We use first-order information (A.2) to compute the second-order derivatives.
Straightforward but lengthy computations show that

$\nabla^{2}_{\alpha}J_{L}\left(\alpha^{(L)}\right)=H_{\mathrm{psd}}+H+\widetilde{H}+\mathcal{O}\left(L^{-1/2}\right),$

where $H_{\mathrm{psd}},H,\widetilde{H}\in\mathbb{R}^{Ld^{2}\times Ld^{2}}$
are given by the following formulae:

$H_{\mathrm{psd}}=\frac{1}{N}\sum_{i=1}^{N}H^{x_{i}}_{\mathrm{psd}}\quad
H=\frac{1}{N}\sum_{i=1}^{N}H^{x_{i}}\quad\widetilde{H}=\frac{1}{N}\sum_{i=1}^{N}\widetilde{H}^{x_{i}},$

where

$\displaystyle\left(H^{x_{i}}_{\mathrm{psd}}\right)_{(k,\,mn)\,(k^{\prime},\,m^{\prime}n^{\prime})}$
$\displaystyle=\delta_{L}^{2}h^{x_{i}}_{k-1,n}h^{x_{i}}_{k^{\prime}-1,n^{\prime}}\dot{\sigma}_{k,x_{i},m}\dot{\sigma}_{k^{\prime},x_{i},m^{\prime}}\left(M^{x_{i}}_{k}e_{m}\right)^{\top}\left(M^{x_{i}}_{k^{\prime}}e_{m^{\prime}}\right)$
$\displaystyle H^{x_{i}}_{(k,\,mn)\,(k^{\prime},\,m^{\prime}n^{\prime})}$
$\displaystyle=\delta_{L}h^{x_{i}}_{k-1,n}h^{x_{i}}_{k-1,n^{\prime}}\ddot{\sigma}_{k,x_{i},m}\left(\widehat{y}(x_{i},\alpha)-y_{i}\right)^{\top}M_{k}^{x_{i}}e_{m}\mathbbm{1}_{m=m^{\prime}}\mathbbm{1}_{k=k^{\prime}}$
$\displaystyle\widetilde{H}^{x_{i}}_{(k,\,mn)\,(k^{\prime},\,m^{\prime}n^{\prime})}$
$\displaystyle=\delta_{L}^{2}h^{x_{i}}_{k-1,n}\dot{\sigma}_{k,x_{i},m}\dot{\sigma}_{k,x_{i},m^{\prime}}\left(\widehat{y}(x_{i},\alpha)-y_{i}\right)^{\top}M_{k,-k^{\prime}}^{x_{i}}e_{m}\mathbbm{1}_{m^{\prime}=n^{\prime}}\mathbbm{1}_{k<k^{\prime}}.$

Here, $M_{k,-k^{\prime}}^{x_{i}}$ is defined as the same product of matrices
as $M_{k}^{x_{i}}$ in (A.1), but without the term $j=k^{\prime}$. By the same
reasoning as in Lemma B.1, we still have $\left\lVert
M_{k,-k^{\prime}}^{x_{i}}e_{m}\right\rVert_{2}\leq e^{c_{\alpha}}$.
We readily see that for each $i$ there exists $Q_{i}$ such that
$H^{x_{i}}_{\mathrm{psd}}=Q_{i}^{\top}Q_{i}$, so $H_{\mathrm{psd}}$ is
positive semi-definite. The trace of $H_{\mathrm{psd}}$ is straightforward to
compute.

$\displaystyle\mathrm{tr}\left(H_{\mathrm{psd}}\right)=\frac{1}{N}\sum_{i=1}^{N}\mathrm{tr}\left(H^{x_{i}}_{\mathrm{psd}}\right)$
$\displaystyle=\frac{\delta_{L}^{2}}{N}\sum_{i=1}^{N}\sum_{k,m,n}\left|h_{k-1,n}^{x_{i}}\right|^{2}\left(\dot{\sigma}_{k,x_{i},m}\right)^{2}\left\lVert
M^{x_{i}}_{k}e_{m}\right\rVert_{2}^{2}.$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}L^{-1}\sum_{k=1}^{L}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{2}\left\lVert
M^{x_{i}}_{k}\right\rVert_{F}^{2}.$

We deduce that by Lemma B.1 that $\mathrm{tr}\left(H_{\mathrm{psd}}\right)\leq
d^{2}e^{4.2c_{\alpha}}$.
The upper bound on the Frobenius norm of $H$ and $\widetilde{H}$ is no harder.

$\displaystyle\left\lVert H^{x_{i}}\right\rVert^{2}_{F}$
$\displaystyle\leq\sum_{k=1}^{L}\sum_{m=1}^{d}\delta_{L}^{2}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{4}\ell(y_{i},\widehat{y}(x_{i},\alpha))\left\lVert
M^{x_{i}}_{k}e_{m}\right\rVert_{2}^{2}\leq
de^{6.4c_{\alpha}}\ell(y_{i},\widehat{y}(x_{i},\alpha)),$
$\displaystyle\left\lVert\widetilde{H}^{x_{i}}\right\rVert_{F}^{2}$
$\displaystyle\leq\sum_{k\neq k^{\prime}}\delta_{L}^{4}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{2}\ell(y_{i},\widehat{y}(x_{i},\alpha))d^{2}e^{2c_{\alpha}}\leq
d^{2}e^{4.2c_{\alpha}}\ell(y_{i},\widehat{y}(x_{i},\alpha)).$

Hence, $\left\lVert
H\right\rVert_{F}\leq\sqrt{2d}e^{3.2c_{\alpha}}J_{L}(\alpha)^{1/2}$ and
$\lVert\widetilde{H}\rVert_{F}\leq\sqrt{2}de^{2.1c_{\alpha}}J_{L}(\alpha)^{1/2}$.
Using Corollary B.2 and wrapping both terms together, we get

$\displaystyle\left\lVert\nabla^{2}_{\alpha}J\left(\alpha^{(L)}\right)\right\rVert_{2}$
$\displaystyle\leq\left\lVert H_{\mathrm{psd}}\right\rVert_{2}+\left\lVert
H\right\rVert_{2}+\lVert\widetilde{H}\rVert_{2}+\mathcal{O}(L^{-1/2})$
$\displaystyle\leq\mathrm{tr}(H_{\mathrm{psd}})^{1/2}+\left\lVert
H\right\rVert_{F}+\lVert\widetilde{H}\rVert_{F}+\mathcal{O}(L^{-1/2})$
$\displaystyle\leq 5de^{4.3c_{\alpha}}.$

∎

##  Appendix D Lower bounds on loss gradients

This section contains a supporting result for the proof of Lemma 3.2.

######  Lemma D.1.

Let $\alpha^{(L)}\in\mathbb{R}^{L\times d\times d}$. Under Assumption 2.1
(i)–(ii), we have, for $k=1,\ldots,L-1$,

$\displaystyle\frac{\partial J_{L}}{\partial\alpha_{k,mn}}-\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}$
$\displaystyle=\frac{\delta_{L}}{N}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}\left(\dot{\sigma}_{k,x_{i},m}-\dot{\sigma}_{k+1,x_{i},m}\right)\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}e_{m}$
$\displaystyle+\frac{\delta_{L}^{2}}{N}\sum_{i=1}^{N}\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}\xi^{x_{i},\,(L)}_{k,mn},$

where $\xi^{x,\,(L)}_{k,mn}\in\mathbb{R}^{d}$ satisfies

$\left\lVert\xi^{x,\,(L)}_{k,mn}\right\rVert_{2}^{2}\leq
2\left(h^{x}_{k-1,n}\right)^{2}\left\lVert\alpha_{k+1}-\alpha_{k}\right\rVert_{F}^{2}+2\left\lVert\alpha_{k,n}\right\rVert_{2}^{4}\left\lVert
h_{k-1}^{x}\right\rVert_{2}^{4}.$

###### Proof.

We use the gradient computation (A.2) and the definition (A.1) to get

$\displaystyle\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}\left(\alpha^{(L)}\right)$
$\displaystyle=\frac{\delta_{L}}{N}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}\dot{\sigma}_{k,x_{i},m}\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha^{(L)})\right)^{\top}M_{k}^{x_{i}}e_{m},$
$\displaystyle\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}\left(\alpha^{(L)}\right)$
$\displaystyle=\frac{\delta_{L}}{N}\sum_{i=1}^{N}\left(h_{k-1,n}^{x_{i}}+\delta_{L}\sigma_{k,x_{i},n}\right)\dot{\sigma}_{k+1,x_{i},m}\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha^{(L)})\right)^{\top}M_{k+1}^{x_{i}}e_{m}.$

We use the identity
$M_{k}^{x_{i}}=M_{k+1}^{x_{i}}\Big{(}I_{d}+\delta_{L}\mathrm{diag}\left(\dot{\sigma}_{k+1,x_{i}}\right)\alpha_{k+1}\Big{)}$
and we take the difference of the two equations above to get

$\displaystyle\frac{\partial J_{L}}{\partial\alpha_{k,mn}}-\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}$
$\displaystyle=\frac{\delta_{L}}{N}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}\left(\dot{\sigma}_{k,x_{i},m}-\dot{\sigma}_{k+1,x_{i},m}\right)\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}e_{m}$
$\displaystyle+\frac{\delta_{L}^{2}}{N}\sum_{i=1}^{N}\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}\xi^{x_{i},\,(L)}_{k,mn},$

where

$\displaystyle\left\lVert\xi^{x,\,(L)}_{k,mn}\right\rVert_{2}^{2}$
$\displaystyle\leq
2\left(h^{x}_{k-1,n}\right)^{2}\left\lVert\alpha_{k+1}-\alpha_{k}\right\rVert_{F}^{2}+2\left(\dot{\sigma}_{k+1,x,m}\right)^{2}\left(\sigma\left(\alpha_{k}h^{x}_{k-1}\right)_{n}-\left(\alpha_{k}h^{x}_{k-1}\right)_{n}\right)^{2}$
$\displaystyle\leq
2\left(h^{x}_{k-1,n}\right)^{2}\left\lVert\alpha_{k+1}-\alpha_{k}\right\rVert_{F}^{2}+2\left\lVert\alpha_{k,n}\right\rVert_{2}^{4}\left\lVert
h_{k-1}^{x}\right\rVert_{2}^{4}.$

We use the fact that $\left|\sigma(z)-z\right|\leq z^{2}$ by Assumption 2.1
(i). ∎

##  Appendix E Weight norms and loss function under gradient descent

This section contains the proof of Lemmas 3.3 and 3.4.

#### Proof of Lemma 3.3

Fix $L\in\mathbb{N}^{*}$. In the proof, we omit the explicit dependence in
$L$. We use the identity
$\frac{1}{2}(A^{2}-B^{2})=B(A-B)+\frac{1}{2}(A-B)^{2}$ and the gradient
descent update rule to first compute

$f_{k,m}(\widetilde{\alpha})-f_{k,m}(\alpha)=\underbrace{-L\eta_{L}\sum_{n=1}^{d}\alpha_{k,mn}\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}\left(\alpha\right)}_{\eqqcolon\,S_{1}(\alpha)}+\underbrace{\frac{L\eta_{L}^{2}}{2}\sum_{n=1}^{d}\left(\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}\right)^{2}\left(\alpha\right)}_{\eqqcolon\,S_{2}(\alpha)}.$
(E.1)

Recall that the gradient of the loss $\ell$ with respect to the parameter
$\alpha_{k,mn}$ at sample $\left(x,y\right)$ is given by (A.2), so that we can
compute

$\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}\left(\alpha\right)=\frac{\delta_{L}}{N}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}(\alpha)\,\dot{\sigma}_{k,x_{i},m}(\alpha)\,\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}\left(x_{i},\alpha\right)\right)^{\top}M_{k}^{x_{i}}(\alpha)\,e_{m}.$

Recall also from (3.6) that

$G^{x,y}_{k}(\alpha)\cdot e_{m}=\frac{\partial\ell(y,\cdot)}{\partial
h_{k}}\left(\widehat{y}(x,\alpha)\right)e_{m}=\nabla_{\widehat{y}}\,\ell\left(y,\widehat{y}(x,\alpha)\right)^{\top}M_{k}^{x}(\alpha)\,e_{m}.$

We focus on the square of first order term $S_{1,m}(\alpha)$ defined above. We
have

$\displaystyle S_{1}(\alpha)^{2}$
$\displaystyle=\frac{L^{2}\delta_{L}^{2}\eta_{L}^{2}}{N^{2}}\left(\sum_{n=1}^{d}\alpha_{k,mn}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}(\alpha)\,\dot{\sigma}_{k,x_{i},m}(\alpha)\,G^{\,x_{i},y_{i}}_{k}(\alpha)\cdot
e_{m}\right)^{2}$ $\displaystyle\leq
L^{2}\delta_{L}^{2}\eta_{L}^{2}\sum_{n=1}^{d}\alpha_{k,mn}^{2}\sum_{n=1}^{d}\left(\frac{1}{N}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}(\alpha)\,\dot{\sigma}_{k,x_{i},m}(\alpha)\,G^{\,x_{i},y_{i}}_{k}(\alpha)\cdot
e_{m}\right)^{2}$ $\displaystyle\leq
2L\delta_{L}^{2}\eta_{L}^{2}f_{k,m}(\alpha)\sum_{n=1}^{d}\frac{1}{N}\sum_{i=1}^{N}\left(h_{k-1,n}^{x_{i}}(\alpha)\,\dot{\sigma}_{k,x_{i},m}(\alpha)\,G^{\,x_{i},y_{i}}_{k}(\alpha)\cdot
e_{m}\right)^{2}$ $\displaystyle\leq
2\eta_{L}^{2}f_{k,m}(\alpha)\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i}}(\alpha)\right\rVert_{2}^{2}\left\lVert
G^{\,x_{i},y_{i}}_{k}(\alpha)\right\rVert_{\infty}^{2}.$

We used twice the Cauchy-Schwarz inequality and Assumption 2.1 (i)-(ii).
Define now

$r_{k}(\alpha)\coloneqq\eta_{L}\left(\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i}}(\alpha)\right\rVert_{2}^{2}\left\lVert
G^{\,x_{i},y_{i}}_{k}(\alpha)\right\rVert_{\infty}^{2}\right)^{1/2}.$

By similar estimations, we also upper bound the second-order term:
$S_{2}(\alpha)\leq\frac{1}{2}r_{k}(\alpha)^{2}$. Equation (E.1) then yields to

$\displaystyle f_{k,m}(\widetilde{\alpha})$ $\displaystyle\leq
f_{k,m}(\alpha)+\left|S_{1}(\alpha)\right|+S_{2}(\alpha)$ $\displaystyle\leq
f_{k,m}(\alpha)+\sqrt{2}r_{k}(\alpha)f_{k,m}(\alpha)^{1/2}+\frac{1}{2}r_{k}(\alpha)^{2}=\left(f_{k,m}(\alpha)^{1/2}+\frac{1}{\sqrt{2}}r_{k}(\alpha)\right)^{2}.$

$\Box$

#### Proof of Lemma 3.4

Fix $L\in\mathbb{N}^{*}$. In the proof, we omit the explicit dependence in
$L$. Define
$g_{k,m}\left(\alpha\right)\coloneqq\frac{1}{2}L^{2}\left\lVert\alpha_{k+1,m}-\alpha_{k,m}\right\rVert_{2}^{2}$
so that $g_{k}=\sum_{m=1}^{d}g_{k,m}$. We also omit the dependence in $\alpha$
when it is clear. We use the identity
$\frac{1}{2}(A^{2}-B^{2})=B(A-B)+\frac{1}{2}(A-B)^{2}$ and the gradient
descent update rule to first compute

$\displaystyle g_{k,m}(\widetilde{\alpha})-g_{k,m}(\alpha)$
$\displaystyle=\underbrace{L^{2}\eta_{L}\sum_{n=1}^{d}\left(\alpha_{k+1,mn}-\alpha_{k,mn}\right)\left(\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}-\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}\right)\left(\alpha\right)}_{\eqqcolon\,S_{1,m}(\alpha)}$
$\displaystyle\quad+\underbrace{\frac{L^{2}\eta_{L}^{2}}{2}\sum_{n=1}^{d}\left(\frac{\partial
J_{L}}{\partial\alpha_{k,mn}}-\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}\right)^{2}\left(\alpha\right)}_{\eqqcolon\,S_{2,m}(\alpha)}.$

Next, we use Lemma D.1 to estimate the difference of gradients with respect to
weights in neighbouring layers. We also use the fact that $L\geq 5c_{\alpha}$
and $\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq c_{\alpha}L^{-1/2}$ to
apply Lemma B.1. Recall the definition of $G$ in (3.6).

$\displaystyle\frac{\partial J_{L}}{\partial\alpha_{k,mn}}-\frac{\partial
J_{L}}{\partial\alpha_{k+1,mn}}$
$\displaystyle=\frac{\delta_{L}}{N}\sum_{i=1}^{N}h_{k-1,n}^{x_{i}}\left(\dot{\sigma}_{k,x_{i},m}-\dot{\sigma}_{k+1,x_{i},m}\right)G^{x_{i},y_{i}}_{k+1}\cdot
e_{m}$
$\displaystyle+\frac{\delta_{L}^{2}}{N}\sum_{i=1}^{N}\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}\xi^{x_{i},\,(L)}_{k,mn},$

where $\xi^{x,\,(L)}_{k,mn}\in\mathbb{R}^{d}$ satisfies

$\sum_{n=1}^{d}\left\lVert\xi^{x,\,(L)}_{k,mn}\right\rVert_{2}^{2}\leq
4c_{\alpha}^{2}e^{2.2c_{\alpha}}L^{-1}.$ (E.2)

We focus on the first order term $S_{1,m}(\alpha)$ defined above. We have

$\displaystyle S_{1,m}(\alpha)$
$\displaystyle=\frac{\eta_{L}\delta_{L}L^{2}}{N}\sum_{i=1}^{N}G^{x_{i},y_{i}}_{k+1}\cdot
e_{m}\left(\dot{\sigma}_{k,x_{i},m}-\dot{\sigma}_{k+1,x_{i},m}\right)\sum_{n=1}^{d}\left(\alpha_{k+1,mn}-\alpha_{k,mn}\right)h_{k-1,n}^{x_{i}}$
$\displaystyle+\frac{\eta_{L}\delta_{L}^{2}L^{2}}{N}\sum_{i=1}^{N}\nabla_{\widehat{y}}\,\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)^{\top}M_{k+1}^{x_{i}}\sum_{n=1}^{d}\left(\alpha_{k+1,mn}-\alpha_{k,mn}\right)\xi^{x_{i}}_{k,mn}.$

Now, as $\sigma^{\prime}$ is $1-$Lipschitz, we can write

$\displaystyle\left|S_{1,m}(\alpha)\right|$
$\displaystyle\leq\frac{\eta_{L}\delta_{L}L^{2}}{N}\sum_{i=1}^{N}\left\lVert
G^{x_{i},y_{i}}_{k+1,}\right\rVert_{\infty}\left|\left(\alpha_{k+1}-\alpha_{k}\right)h_{k-1}^{x_{i}}\right|_{m}\left|\alpha_{k}h_{k-1}-\alpha_{k+1}h_{k}\right|_{m}$
$\displaystyle+\eta_{L}\delta_{L}^{2}L^{2}\left[\frac{2}{N}\sum_{i=1}^{N}\ell\left(y_{i},\widehat{y}(x_{i},\alpha)\right)\left\lVert
M_{k+1}^{x_{i}}\right\rVert_{2}^{2}\left\lVert\alpha_{k+1,m}-\alpha_{k,m}\right\rVert_{2}^{2}\sum_{n=1}^{d}\left\lVert\xi^{x_{i}}_{k,mn}\right\rVert_{2}^{2}\right]^{1/2}.$

We now use the fact that $L\geq 5c_{\alpha}$ and
$\left\lVert\alpha^{(L)}\right\rVert_{F,\infty}\leq c_{\alpha}L^{-1/2}$ to
apply Lemma B.1 on the second term and deduce that

$\displaystyle\left|S_{1,m}(\alpha)\right|$
$\displaystyle\leq\frac{\eta_{L}\delta_{L}L^{2}}{N}\sum_{i=1}^{N}\left\lVert
G^{x_{i},y_{i}}_{k+1}\right\rVert_{\infty}\left|\left(\alpha_{k+1}-\alpha_{k}\right)h_{k-1}^{x_{i}}\right|_{m}^{2}$
$\displaystyle+\frac{\eta_{L}\delta_{L}L^{2}}{N}\sum_{i=1}^{N}\left\lVert
G^{x_{i},y_{i}}_{k+1}\right\rVert_{\infty}\left|\left(\alpha_{k+1}-\alpha_{k}\right)h_{k-1}^{x_{i}}\right|_{m}\left|\alpha_{k+1}\left(h_{k}^{x_{i}}-h_{k-1}^{x_{i}}\right)\right|_{m}$
$\displaystyle+2e^{c_{\alpha}}\eta_{L}\left(\sum_{n=1}^{d}\left\lVert\xi^{x_{i}}_{k,mn}\right\rVert_{2}^{2}\right)^{1/2}g_{k,m}(\alpha)^{1/2}J_{L}(\alpha)^{1/2}.$

We apply Cauchy-Schwarz to the first and second term and equation (E.2) to the
third term to get

$\displaystyle\left|S_{1,m}(\alpha)\right|$ $\displaystyle\leq
2\eta_{L}L^{-1/2}\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{2}\left\lVert
G^{x_{i},y_{i}}_{k+1}\right\rVert_{\infty}g_{k,m}(\alpha)$
$\displaystyle+\eta_{L}\delta_{L}L^{2}\left[\frac{1}{N}\sum_{i=1}^{N}\left\lVert
G^{x_{i},y_{i}}_{k+1}\right\rVert_{\infty}^{2}\left\lVert\alpha_{k+1,m}-\alpha_{k,m}\right\rVert_{2}^{2}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{2}\left\lVert\alpha_{k+1,m}\right\rVert_{2}^{2}\delta_{L}^{2}\left\lVert\sigma_{k,x_{i}}\right\rVert_{2}^{2}\right]^{1/2}$
$\displaystyle+4c_{\alpha}e^{2.1c_{\alpha}}\eta_{L}L^{-1/2}g_{k,m}(\alpha)^{1/2}J_{L}(\alpha)^{1/2}.$

We now use Lemma B.1 and the identity
$G^{x_{i},y_{i}}_{k+1}=M_{k+1}^{x_{i}}\left(\widehat{y}(x_{i},\alpha)-y_{i}\right)$
to estimate the second term in the RHS:

$\displaystyle\left|S_{1,m}(\alpha)\right|$ $\displaystyle\leq
2\eta_{L}L^{-1/2}\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{2}\left\lVert
G^{x_{i},y_{i}}_{k+1}\right\rVert_{\infty}g_{k,m}(\alpha)$
$\displaystyle+2c_{\alpha}^{2}e^{3.2c_{\alpha}}\eta_{L}L^{-1}g_{k,m}(\alpha)^{1/2}J_{L}(\alpha)^{1/2}+4c_{\alpha}e^{2.1c_{\alpha}}\eta_{L}L^{-1/2}g_{k,m}(\alpha)^{1/2}J_{L}(\alpha)^{1/2}.$

Thus,

$\displaystyle\left|S_{1,m}(\alpha)\right|$ $\displaystyle\leq
2\eta_{L}L^{-1/2}\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{2}\left\lVert
G^{x_{i},y_{i}}_{k+1}\right\rVert_{\infty}g_{k,m}(\alpha)$
$\displaystyle+2c_{\alpha}e^{2.1c_{\alpha}}\eta_{L}\left(c_{\alpha}e^{1.1c_{\alpha}}L^{-1}+2L^{-1/2}\right)g_{k,m}(\alpha)^{1/2}J_{L}(\alpha)^{1/2}.$

Define

$\displaystyle r_{k}(\alpha)$
$\displaystyle\coloneqq\eta_{L}\frac{1}{N}\sum_{i=1}^{N}\left\lVert
h_{k-1}^{x_{i}}\right\rVert_{2}^{2}\left\lVert
G^{x_{i},y_{i}}_{k+1}\right\rVert_{\infty}$
$\displaystyle\mathcal{E}_{k,m}(L,d,\alpha)$ $\displaystyle\coloneqq
c_{\alpha}e^{2.1c_{\alpha}}\eta_{L}\left(c_{\alpha}e^{1.1c_{\alpha}}L^{-1}+2L^{-1/2}\right)g_{k,m}(\alpha)^{1/2}J_{L}(\alpha)^{1/2}.$

We then have $\left|S_{1,m}(\alpha)\right|\leq
2L^{-1/2}g_{k,m}(\alpha)r_{k}(\alpha)+2\mathcal{E}_{k,m}(L,d,\alpha)$. We use
similar techniques to derive the upper bound $S_{2,m}(\alpha)\leq
L^{-1}g_{k,m}(\alpha)r_{k}(\alpha)^{2}+\mathcal{O}(\mathcal{E}_{k,m}(L,d,\alpha))$.
Hence, we deduce the following recurrence relation.

$g_{k,m}(\widetilde{\alpha})\leq
g_{k,m}(\alpha)+\left|S_{1,m}(\alpha)\right|+S_{2,m}(\alpha)\leq
g_{k,m}(\alpha)\left(1+L^{-1/2}r_{k}(\alpha)\right)^{2}+\mathcal{O}\left(\mathcal{E}_{k,m}(L,d,\alpha)\right).$

Summing over $m=1,\ldots,d$ and using Cauchy-Schwarz on the
$\mathcal{E}_{k,m}$ terms, we get

$g_{k}(\widetilde{\alpha})\leq
g_{k}(\alpha)\left(1+L^{-1/2}r_{k}(\alpha)\right)^{2}+\mathcal{O}\left(\mathcal{E}_{k}(L,d,\alpha)\right),$

where

$\mathcal{E}_{k}(L,d,\alpha)\coloneqq
c_{\alpha}e^{2.1c_{\alpha}}\eta_{L}\left(c_{\alpha}e^{1.1c_{\alpha}}L^{-1}+2L^{-1/2}\right)g_{k}(\alpha)^{1/2}J_{L}(\alpha)^{1/2}.$
(E.3)

$\Box$

##  Appendix F Supporting lemma for Theorem 3.5

######  Lemma F.1.

Let $\alpha^{(L)}(0)\in\mathbb{R}^{L\times d\times d}$ be any weight
initialization. Define recursively
$\alpha^{(L)}(t+1)=\alpha^{(L)}(t)-\eta_{L}(t)\nabla_{\alpha}J_{L}\left(\alpha^{(L)}(t)\right)$
for $t=0,\ldots,T-1$. Assume that for all $t=0,\ldots,T-1$, there exist
$c_{\alpha}(t),\underline{c}(t),\mkern 1.0mu\overline{\mkern-1.5muc\mkern
0.0mu}\mkern 1.0mu(t)>0$ such that

  * (i)

$L\geq 5\max_{t<T}c_{\alpha}(t)$,

  * (ii)

$\left\lVert\alpha^{(L)}(t)\right\rVert_{F,\infty}\leq c_{\alpha}(t)L^{-1/2}$,
and

  * (iii)

$\left\lVert\nabla_{\alpha^{(L)}}J_{L}\left(\alpha^{(L)}(t)\right)\right\rVert_{F}^{2}\geq\underline{c}(t)J_{L}\left(\alpha^{(L)}(t)\right)-\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern 1.0mu(t)L^{-1}$.

Then, under Assumption 2.1 (i)–(ii), if the learning rates satisfy:

$\eta_{L}(t)<\min\left(\frac{1}{2}c_{\alpha}(t)e^{-3.2c_{\alpha}(t)},\,\frac{1}{10}\underline{c}(t)d^{-1}e^{-8.5c_{\alpha}(t)}\right),$

we have, for each $t=0,\ldots,T$:

$J_{L}\left(\alpha^{(L)}(t)\right)\leq\exp\left(-\frac{1}{2}\sum_{t^{\prime}=0}^{t-1}\underline{c}(t^{\prime})\eta_{L}(t^{\prime})\right)J_{L}\left(\alpha^{(L)}(0)\right)+L^{-1}\sum_{t^{\prime}=0}^{t-1}\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern
1.0mu(t^{\prime})\eta_{L}(t^{\prime}).$ (F.1)

###### Proof.

Fix $L\geq 5\max_{t<T}c_{\alpha}(t)$. We omit the explicit dependence in $L$.
Fix $t\in\left[0,T\right)$. We first view
$\alpha(t),\,\nabla_{\alpha}J_{L}(\alpha(t))\in\mathbb{R}^{L\times d\times d}$
as vectors in the Euclidean space $\mathbb{R}^{Ld^{2}}$, and we get by
hypothesis and by Lemma C.1 that

$\displaystyle\left\lVert\mathrm{vec}(\alpha(t))\right\rVert_{2}=\left\lVert\alpha(t)\right\rVert_{F}$
$\displaystyle=\left(\sum_{k=1}^{L}\left\lVert\alpha_{k}(t)\right\rVert_{F}^{2}\right)^{1/2}\leq
c_{\alpha}(t),$ $\displaystyle\underline{c}(t)J_{L}(\alpha(t))-\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern 1.0mu(t)L^{-1}$
$\displaystyle=\left\lVert\nabla_{\alpha}J_{L}(\alpha(t))\right\rVert_{F}^{2}\leq
2e^{4.2c_{\alpha}(t)}J_{L}(\alpha(t)).$

We want to use Lemma G.3 with $p=Ld^{2}$, $R=c_{\alpha}$, $x_{0}=\alpha(t)$
and $x=\alpha(t)-\eta_{L}(t)\nabla_{\alpha}J_{L}(\alpha(t))$. For this, we
need to check two assumptions. The first is an upper bound on the spectral
norm of the Hessian of $J_{L}$, which we get from Lemma C.2.

$H_{\infty}(t)=\sup_{\left\lVert\alpha^{\prime}\right\rVert_{F}\leq\,c_{\alpha}(t)}\left\lVert\nabla^{2}J_{L}(\alpha^{\prime})\right\rVert_{2}\leq
5de^{4.3c_{\alpha}(t)}.$

The second is an upper bound on the norm of
$x-x_{0}=-\eta_{L}(t)\nabla_{\alpha}J_{L}(\alpha(t))$, which we get from Lemma
C.1.

$\displaystyle\eta_{L}(t)\left\lVert\nabla_{\alpha}J_{L}(\alpha(t))\right\rVert_{2}$
$\displaystyle\leq\sqrt{2}\eta_{L}(t)e^{2.1c_{\alpha}(t)}J_{L}(\alpha(t))^{1/2}$
$\displaystyle\leq\sqrt{2}\eta_{L}(t)e^{2.1c_{\alpha}(t)}\left(1+e^{2.2c_{\alpha}(t)}\right)^{1/2}$
$\displaystyle\leq 2\eta_{L}(t)e^{3.2c_{\alpha}(t)}\leq c_{\alpha}(t),$

where the second inequality comes from Corollary B.2 and the third inequality
from the fact that $(1+z)^{1/2}\leq(2z)^{1/2}$ for $z\geq 1$. Hence, we can
apply Lemma G.3 and deduce that

$\displaystyle J_{L}\left(\alpha(t+1)\right)$
$\displaystyle=J_{L}\Big{(}\alpha(t)-\eta_{L}(t)\nabla_{\alpha}J_{L}(\alpha(t))\Big{)}-J_{L}(\alpha(t))$
$\displaystyle\leq
J_{L}\left(\alpha(t)\right)-\eta_{L}(t)\left\lVert\nabla_{\alpha}J_{L}(\alpha(t))\right\rVert_{F}^{2}+\frac{1}{2}H_{\infty}(t)\eta_{L}(t)^{2}\left\lVert\nabla_{\alpha}J_{L}(\alpha(t))\right\rVert_{2}^{2}$
$\displaystyle\leq\left(1-\underline{c}(t)\eta_{L}(t)+5d\eta_{L}(t)^{2}e^{8.5c_{\alpha}(t)}\right)J_{L}\left(\alpha(t)\right)+\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern 1.0mu(t)\eta_{L}(t)L^{-1}.$

To finish the proof, we apply Lemma G.4 (i) with

$u_{L}(t)\coloneqq\underline{c}(t)\eta_{L}(t)-5d\eta_{L}(t)^{2}e^{8.5c_{\alpha}(t)}\geq\frac{1}{2}\underline{c}(t)\eta_{L}(t)>0,$

and the fact that $1-x\leq e^{-x}$. Hence,

$\displaystyle J_{L}(\alpha(T))$
$\displaystyle\leq\exp\left(-\sum_{t=0}^{T-1}u_{L}(t)\right)J_{L}(\alpha(0))+L^{-1}\sum_{t=0}^{T-1}\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern 1.0mu(t)\eta_{L}(t)$
$\displaystyle\leq\exp\left(-\frac{1}{2}\sum_{t=0}^{T-1}\underline{c}(t)\eta_{L}(t)\right)J_{L}(\alpha(0))+L^{-1}\sum_{t=0}^{T-1}\mkern
1.0mu\overline{\mkern-1.5muc\mkern 0.0mu}\mkern 1.0mu(t)\eta_{L}(t).$

∎

##  Appendix G Auxiliary results

######  Lemma G.1.

For any $A\in\mathbb{R}^{m\times n}$ and $B\in\mathbb{R}^{n\times p}$, we have

$\left\lVert AB\right\rVert_{F}\leq\left\lVert A\right\rVert_{2}\left\lVert
B\right\rVert_{F}.$

###### Proof.

Let $B=\left[b_{1},\ldots,b_{p}\right]$ the columns of $B$. Then $\left\lVert
B\right\rVert_{F}^{2}=\sum_{i=1}^{p}\left\lVert b_{i}\right\rVert_{2}^{2}$. We
use the fact that the spectral norm is compatible with the Euclidian norm to
deduce

$\left\lVert AB\right\rVert_{F}^{2}=\sum_{i=1}^{p}\left\lVert
Ab_{i}\right\rVert_{2}^{2}\leq\sum_{i=1}^{p}\left\lVert
A\right\rVert^{2}_{2}\left\lVert b_{i}\right\rVert^{2}_{2}=\left\lVert
A\right\rVert^{2}_{2}\left\lVert B\right\rVert_{F}^{2}.$

∎

######  Lemma G.2.

Let $x\in\mathbb{R}^{d}$ and
$\left\\{A_{k}:k=1,\ldots,L\right\\}\subset\mathbb{R}^{d\times d}$ such that
$\max_{k}\left\lVert A_{k}\right\rVert_{2}<1$. Then

$\left\lVert\left[\prod_{k=1}^{L}(I_{d}+A_{k})\right]x\,\right\rVert_{2}\geq\left\lVert
x\right\rVert_{2}\prod_{k=1}^{L}(1-\left\lVert A_{k}\right\rVert_{2}).$

###### Proof.

First observe that for $A,B\in\mathbb{R}^{d\times d}$ and
$x\in\mathbb{R}^{d}$, we have $\left\lVert
ABx\right\rVert_{2}\geq\sigma_{\min}(A)\left\lVert Bx\right\rVert_{2}$, where
$\sigma_{\min}(A)$ is the smallest singular value of $A$. This is easy to see,
as $\sigma_{\min}(A)^{2}$ is the smallest eigenvalue of $A^{\top}A$, so

$\left\lVert
ABx\right\rVert_{2}^{2}=(Bx)^{\top}A^{\top}A(Bx)\geq\sigma_{\min}(A)^{2}\left\lVert
Bx\right\rVert_{2}^{2}.$

Observe also that for all $A\in\mathbb{R}^{d\times d}$ with $\left\lVert
A\right\rVert_{2}<1$, we have $\sigma_{\min}(I_{d}+A)\geq 1-\left\lVert
A\right\rVert_{2}>0$. Indeed, there exists $v\in\mathbb{R}^{d}$ such that
$\left\lVert v\right\rVert_{2}=1$ and
$v^{\top}(I_{d}+A)v=\sigma_{\min}(I_{d}+A)^{2}$. Hence,

$\sigma_{\min}(I_{d}+A)=\left(1+v^{\top}Av\right)^{1/2}\geq\left(1-\left\lVert
A\right\rVert_{2}\right)^{1/2}\geq 1-\left\lVert A\right\rVert_{2}.$

Combining these two facts, we deduce that

$\left\lVert\left[\prod_{k=1}^{L}(I_{d}+A_{k})\right]x\,\right\rVert_{2}\geq\left\lVert
x\right\rVert_{2}\prod_{k=1}^{L}\sigma_{\min}(I_{d}+A_{k})\geq\left\lVert
x\right\rVert_{2}\prod_{k=1}^{L}(1-\left\lVert A_{k}\right\rVert_{2}).$

∎

######  Lemma G.3.

Let $f\in C^{2}(\mathbb{R}^{p})$ satisfying $\sup_{\left\lVert
x\right\rVert_{2}<R}\left\lVert\nabla^{2}f(x)\right\rVert_{2}\leq H_{\infty}$
for some $H_{\infty},R>0$. Then, for all $x\in\mathbb{R}^{p}$ such that
$\left\lVert x-x_{0}\right\rVert_{2}<R$,

$\Big{|}f(x)-f(x_{0})-\langle\nabla_{x}f(x),x-x_{0}\rangle\Big{|}\leq\frac{H_{\infty}}{2}\left\lVert
x-x_{0}\right\rVert_{2}^{2}.$

###### Proof.

We apply the fundamental theorem of calculus for line integrals between
$x_{0}$ and $x$:

$f(x)-f(x_{0})=\int_{0}^{1}\big{\langle}\nabla_{x}f(x_{0}+t(x-x_{0})),x-x_{0}\big{\rangle}\mathrm{d}t.$

Hence, by Cauchy-Schwartz inequality and by hypothesis,

$\displaystyle\Big{|}f(x)-f(x_{0})-\big{\langle}\nabla_{x}f(x_{0}),x-x_{0}\big{\rangle}\Big{|}$
$\displaystyle\leq\int_{0}^{1}\left\lVert\nabla_{x}f(x_{0}+t(x-x_{0}))-\nabla_{x}f(x_{0})\right\rVert_{2}\left\lVert
x-x_{0}\right\rVert_{2}\mathrm{d}t$
$\displaystyle\leq\int_{0}^{1}H_{\infty}\left\lVert
t(x-x_{0})\right\rVert_{2}\left\lVert x-x_{0}\right\rVert_{2}\mathrm{d}t$
$\displaystyle=\frac{H_{\infty}}{2}\left\lVert x-x_{0}\right\rVert_{2}^{2}.$

∎

######  Lemma G.4 (Discrete Grönwall inequalities).

Let
$(u_{n})_{n\in\mathbb{N}},(v_{n})_{n\in\mathbb{N}},(w_{n})_{n\in\mathbb{N}}\subset\mathbb{R}_{>0}$.
Then

  * (i)

If $e_{n+1}\leq u_{n}e_{n}+v_{n}$ for each $n\geq 0$, then

$e_{n}\leq\left(\prod_{n^{\prime}=0}^{n-1}u_{n^{\prime}}\right)e_{0}+\sum_{n^{\prime}=0}^{n-1}\left(\prod_{n^{\prime\prime}=n^{\prime}+1}^{n-1}u_{n^{\prime\prime}}\right)v_{n^{\prime}}.$

  * (ii)

If $g_{0}>0$ and $0<g_{n+1}\leq u_{n}g_{n}+w_{n}g_{n}^{1/2}$, then

$g_{n}^{1/2}\leq\left(\prod_{n^{\prime}=0}^{n-1}u_{n}^{1/2}\right)g_{0}^{1/2}+\frac{1}{2}\sum_{n^{\prime}=0}^{n-1}\left(\prod_{n^{\prime\prime}=n^{\prime}+1}^{n-1}u_{n^{\prime\prime}}^{1/2}\right)\frac{w_{n^{\prime}}}{u_{n^{\prime}}^{1/2}}.$

The first inequality is well-known, but we give proofs for both, for the sake
of completeness.

###### Proof.

To prove (i), we start by defining
$\widetilde{e}_{n}=\left(\prod_{n^{\prime}=0}^{n-1}u_{n^{\prime}}\right)^{-1}e_{n}$.
Then,

$\widetilde{e}_{n+1}-\widetilde{e}_{n}=\left(\prod_{n^{\prime}=0}^{n}u_{n^{\prime}}\right)^{-1}\left(e_{n+1}-u_{n}e_{n}\right)\leq\left(\prod_{n^{\prime}=0}^{n}u_{n^{\prime}}\right)^{-1}v_{n}.$

Hence, summing over $n$, we get

$\displaystyle
e_{n}=\left(\prod_{n^{\prime}=0}^{n-1}u_{n^{\prime}}\right)\widetilde{e}_{n}$
$\displaystyle\leq\left(\prod_{n^{\prime}=0}^{n-1}u_{n^{\prime}}\right)\left(e_{0}+\sum_{n^{\prime}=0}^{n-1}\left(\prod_{n^{\prime\prime}=0}^{n^{\prime}}u_{n^{\prime\prime}}\right)^{-1}v_{n^{\prime}}\right)$
$\displaystyle=\left(\prod_{n^{\prime}=0}^{n-1}u_{n^{\prime}}\right)e_{0}+\sum_{n^{\prime}=0}^{n-1}\left(\prod_{n^{\prime\prime}=n^{\prime}+1}^{n-1}u_{n^{\prime\prime}}\right)v_{n^{\prime}}.$

To prove (ii), we simply complete the square: $u_{n}g_{n}+w_{n}g_{n}^{1/2}\leq
u_{n}\left(g_{n}^{1/2}+\frac{w_{n}}{2u_{n}}\right)^{2}$. Hence,

$g_{n+1}^{1/2}\leq u_{n}^{1/2}g_{n}^{1/2}+\frac{w_{n}}{2u_{n}^{1/2}}.$

We can thus apply part (i) to $e_{n}=g_{n}^{1/2}$ to deduce the result.

∎