Implicit regularization of deep residual networks towards neural ODEs

Introduction

Residual networks are a successful family of deep learning models popularized by breakthrough results in computer vision (He et al., 2016b). The key idea behind residual networks, namely the presence of skip connections, is now ubiquitous in deep learning, and can be found, for example, in Transformer models (Vaswani et al., 2017). The main advantage of skip connections is to allow successful training with depth of the order of a thousand layers, in contrast to vanilla neural networks, leading to significant performance improvement (e.g., Wang et al., 2022). This has motivated research on the properties of residual networks in the limit where the depth tends to infinity. One of the main explored directions is the neural ordinary differential equation (ODE) limit (Chen et al., 2018).

Before presenting neural ODEs, we first introduce the mathematical formalism of deep residual networks. We consider a single model throughout the paper to simplify the exposition, but most of our results apply to more general models, as will be discussed later. We consider the formulation

where $s$ is the continuous-depth version of the layer index. It is important to note that this correspondence holds for fixed limiting functions $\mathcal{V}$ and $\mathcal{W}$. This is especially true at initialization, for example by setting the $V_{k}$ to zero and the $W_{k}$ to Gaussian matrices weight-tied across the depth. The initial residual network is then trivially equal to the neural ODE $\frac{dH}{ds}(s)=0$. Of course, more sophisticated initializations are possible, as shown, e.g., in Marion et al. (2022); Sander et al. (2022b). However, regardless of an ODE structure at initialization, a more challenging question is that of the structure of the network during and after training. Since the weights are updated during training, there is a priori no guarantee that an ODE limit still holds after training, even if it does at initialization.

The question of a potential ODE structure for the trained network is not a mere technical one. In fact, it is important for at least three reasons. First, it gives a precise answer to the question of the connection between (trained) residual networks and neural ODEs, providing more solid ground to a common statement in the community that both can coincide in the large-depth limit (see, e.g., Haber & Ruthotto, 2017; E et al., 2019; Dong et al., 2020; Massaroli et al., 2020; Kidger, 2022). Second, it opens exciting perspectives for understanding residual networks. Indeed, if trained residual networks are discretizations of neural ODEs, then it is possible to apply results from neural ODEs to the large family of residual networks. In particular, from a theoretical point of view, the approximation capabilities of neural ODEs are well understood (Teshima et al., 2020; Zhang et al., 2020) and it is relatively easy to obtain generalization bounds for these models (Hanson & Raginsky, 2022; Marion, 2023). From a practical standpoint, advantages of neural ODEs include memory-efficient training (Chen et al., 2018; Sander et al., 2022b) and weight compression (Queiruga et al., 2021). This is important because in practice memory is a bottleneck for training residual networks (Gomez et al., 2017). Finally, our analysis is a first step towards understanding the implicit regularization (Neyshabur et al., 2014; Vardi, 2023) of gradient descent for deep residual networks, that is, characterizing the properties of the trained network among all minimizers of the empirical risk.

Our first main contribution (Section 4.1) is to show that a neural ODE limit holds after training up to time $t$, i.e., there exists a function $\mathcal{V}(s,t)$ such that the residual network converges, as $L$ tends to infinity, to the ODE

This large-depth limit holds for any finite training time $t\geqslant 0$. However, the convergence of the optimization algorithm as $t$ tends to infinity, which we refer to as the long-time limit to distinguish it from the large-depth limit $L\to\infty$, is not guaranteed without further assumptions, due to the non-convexity of the optimization problem. We attack the question (Section 4.2) when the width is large enough by proving a Polyak-Łojasiewicz (PL) condition, which is now state of the art in analyzing the properties of optimization algorithms for deep neural networks (Liu et al., 2022). The main assumption for our PL condition to hold is that the width $m$ of the hidden layers should be greater than some constant times the number of data $n$. As a second main contribution, we show that the PL condition yields the long-time convergence of the gradient flow for residual networks with linear overparameterization. Finally, we prove the convergence with high probability in the long-time limit, namely the existence of functions $\mathcal{V}_{\infty}$ and $\mathcal{W}_{\infty}$ such that the discrete trajectory defined by the trained residual network (1) converges as both $L$ and $t$ tend to infinity to the solution of the neural ODE (2) with $\mathcal{V}=\mathcal{V}_{\infty}$ and $\mathcal{W}=\mathcal{W}_{\infty}$. In addition, our approach points out that this limiting ODE interpolates the training data. Finally, our results are illustrated by numerical experiments (Section 5).

Related work

Several works study the large-depth convergence of residual networks to differential equations, but without considering the training dynamics (Thorpe & van Gennip, 2023; Cohen et al., 2021; Marion et al., 2022; Hayou, 2023). Closer to our setting, Cont et al. (2022) and Sander et al. (2022b) analyze the dynamics of gradient descent for deep residual networks, as we do, but with significant differences. Cont et al. (2022) consider a $\nicefrac{{1}}{{\sqrt{L}}}$ scaling factor in front of the residual branch, resulting in a limit that is not a neural ODE. In addition, only $W$ is trained. Furthermore, to obtain convergence in the long-time limit, it is assumed that the data points are nearly orthogonal. Sander et al. (2022b) prove the existence of an ODE limit for trained residual networks, but in the simplified case of a linear activation and under a more restricted setting.

Polyak-Łojasiewicz conditions are a modern tool to prove long-time convergence of overparameterized neural networks (Liu et al., 2022). These conditions are a relaxation of convexity, and mean that the gradients of the loss with respect to the parameters cannot be small when the loss is large. They have been applied to residual networks with both linear (Bartlett et al., 2018; Wu et al., 2019; Zou et al., 2020) and nonlinear activations (Allen-Zhu et al., 2019; Frei et al., 2019; Barboni et al., 2022; Cont et al., 2022; MacDonald et al., 2022). Building on the proof technique of Nguyen & Mondelli (2020) for non-residual networks, we need only a linear overparameterization to prove our PL condition, i.e., we require $m=\Omega(n)$. This compares favorably with results requiring polynomial overparameterization (Allen-Zhu et al., 2019; Barboni et al., 2022) or assumptions on the data, either a margin condition (Frei et al., 2019) or a sample size smaller than the dimension of the data space (Cont et al., 2022; MacDonald et al., 2022).

Our paper can be related to a line of work on the implicit regularization of gradient-based algorithms for residual networks (Neyshabur et al., 2014). We show that the optimization algorithm does not just converge to any residual network that minimizes the empirical risk, but rather to the discretization of a neural ODE. Note that most implicit regularization results state that the optimization algorithm converges to an interpolator that minimizes some complexity measure, which can be a margin (Lyu & Li, 2020), a norm (Boursier et al., 2022), or a matrix rank (Li et al., 2021). Thus, an interesting next step is to understand if the neural ODE found by gradient flow actually minimizes some complexity measure, and to characterize its generalization properties.

Definitions and notation

This section is devoted to specifying the setup outlined in Section 1. Proofs are given in the appendix.

Gradient flow is the limit of gradient descent as the learning rate tends to zero. The parameters are set at time $t=0$ by the initialization, and then evolve according to the ODE

for $k\in\{1,\dots,L\}$. In the following, the dependence in $t$ is made explicit when necessary, e.g., we write $h_{k}^{L}(t)$ instead of $h_{k}^{L}$, and $F^{L}(x;t)$ instead of $F^{L}(x)$.

It turns out that, without further assumptions, the gradient flow can diverge in finite time. This is because the dynamics are not (globally) Lipschitz continuous, breaking the conditions of the Picard-Lindelöf theorem (see Lemma 16) for existence and uniqueness of ODE solutions. A common practice (Goodfellow et al., 2016, Section 10.11.1) is to consider instead a clipped gradient flow

The (clipped) gradient flow (5) has a unique solution for all $t\geqslant 0$.

In Section 4.2, we make additional assumptions to prove the long-time convergence of the gradient flow. We then prove that these assumptions ensure that the dynamics of the gradient flow (4) are well defined, eliminating the need for clipping.

The neural ODE corresponding to the residual network (3) is defined by

Clearly, our choices of $V_{k}^{L}$ and $W_{k}^{L}$ at initialization are discretizations of the Lipschitz continuous (in fact, constant) functions $\mathcal{V}(s)\equiv 0$ and $\mathcal{W}(s)\equiv W\sim\mathcal{N}(0,1)^{\otimes(m\times q)}$. Thus, Proposition 2 holds at initialization, and the residual network is equivalent to the trivial ODE $\frac{dH}{ds}(s)=0$. The next section shows that after training we obtain non-trivial dynamics, which still discretize neural ODEs.

Large-depth limit of residual networks

We study the large-depth limit of trained residual networks in two settings. In Section 4.1, we consider the case of a finite training time. We move in Section 4.2 to the case where the training time tends to infinity, which is tractable under a Polyak-Łojasiewicz condition. Proofs are given in the appendix.

We first consider the case where the neural network is trained with clipped gradient flow (5) on some training time interval $[0,T]$, $T>0$. This allows us to prove large-depth convergence to a neural ODE without further assumptions. We emphasize that stopping training after a finite training time is a common technique in practice, referred to as early stopping (Goodfellow et al., 2016, Section 7.8). It is considered as a form of implicit regularization, and our result sheds light on this intuition by showing that the complexity of the trained networks increases with $T$.

The following proposition is a key step in proving the main theorem of this section.

Moreover, with probability at least 1-\exp\big{(}-\frac{3qm}{16}\big{)}, the following expressions hold for $M$ and $K$:

where $M_{\pi}$ is the supremum of $\pi$ in Frobenius norm, and $\alpha$ and $\beta$ depend on $\mathcal{X}$, $\mathcal{Y}$, $M$, and $\sigma$.

This proposition ensures that the size of the weights and the difference between successive weights remain bounded throughout training. We can now state the main result, which states the convergence, for any training time in $[0,T]$, of the neural network to a neural ODE as $L\to\infty$. Recall that a sequence of functions $f^{L}$ of some variable $u$ is said to converge uniformly over $u\in U$ to $f$ if $\sup_{u\in U}\|f^{L}(u)-f(u)\|\to 0$.

Consider the residual network (3) with the training dynamics (5). Then the following statements hold as $L$ tends to infinity:

converges uniformly over $s\in$ and $t\in[0,T]$ to $\mathcal{Z}:=(\mathcal{V},\mathcal{W})$.

Uniformly over $s\in$, $t\in[0,T]$, and $x\in\mathcal{X}$, the hidden layer $h_{\left\lfloor Ls\right\rfloor}^{L}(t)$ converges to the solution at time $s$ of the neural ODE

Uniformly over $t\in[0,T]$ and $x\in\mathcal{X}$, the output $F^{L}(x;t)$ converges to $B(t)H(1,t)$.

Let us sketch the proof of statement $(ii)$, which is the cornerstone of the theorem. A first key idea is to introduce in (8) the piecewise-constant continuous-depth interpolation $\mathcal{Z}^{L}$ of the weights, whose ambient space does not depend on $L$, in contrast to the discrete weight sequence $Z_{k}^{L}$. Since the weights remain bounded during training by Proposition 3, the Arzelà-Ascoli theorem guarantees the existence of an accumulation point for $\mathcal{Z}^{L}$. We show that the accumulation point is unique because it is the solution of an ODE satisfying the conditions of the Picard-Lindelöf theorem. The uniqueness of the accumulation point then implies the existence of a limit for the weights.

There are two notable byproducts of our proof. The first one is an explicit description of the training dynamics of the limiting weights $A$, $B$, and $\mathcal{Z}$, as the solution of an ODE system, as presented in Appendix A.5. The second one, which we now describe, consists of norm bounds on the weights. Proposition 3 bounds the discrete weights and the difference between two consecutive weights respectively by some $M,K>0$. The proof of Theorem 4 shows that this bound carries over to the continuous weights, in the sense that $A(t)$, $\mathcal{V}(s,t)$, $\mathcal{W}(s,t)$, and $B(t)$ are uniformly bounded by $M$, and $\mathcal{V}(\cdot,t)$ and $\mathcal{W}(\cdot,t)$ are uniformly Lipschitz continuous with Lipschitz constant $K$. Formally, this last property means that, for any $s,s^{\prime}\in$ and $t\in[0,T]$,

The boundedness and Lipschitz continuity of the weights are important features because they limit the statistical complexity of neural ODEs (Marion, 2023). More generally, norm-based bounds are a common approach in the statistical theory of deep learning (see, e.g., Bartlett et al., 2017, and references therein). Looking at the formula (7) for $M$ and $K$, one can see in particular that the bounds diverge exponentially with $T$, providing an argument in favor of early stopping.

Our approach so far characterizes the large-depth limit of the neural network for a finite training time $T$, but two questions remain open. A first challenge is to characterize the value of the loss after training. A second one is to provide insight into the convergence of the optimization algorithm in the long-time limit, i.e., as $T$ tends to infinity. To answer these questions, we move to the setting where the width of the network is large enough, which allows us to prove a Polyak-Łojasiewicz condition and thereby the long-time convergence of the training loss to zero.

2 Convergence in the long-time limit for wide networks

Proving convergence of gradient-based optimization algorithms for neural networks is a major difficulty in deep learning theory. One direction recently explored considers sufficiently wide neural networks, and leverages the Polyak-Łojasiewicz (PL) condition. In our setting, they are written as follows (with the notation $Z^{L}=(V_{k}^{L},W_{k}^{L})_{k\in\{1,\dots,L\}}$):

For $M,\mu>0$, the residual network (3) is said to satisfy the $(M,\mu)$-local PL condition around a set of parameters $(\bar{A}^{L},\bar{Z}^{L},\bar{B}^{L})$ if, for every set of parameters $(A^{L},Z^{L},B^{L})$ such that

The next important point is to observe that, under the setup of Section 3 and some additional assumptions, the residual network satisfies the local PL condition of Definition 1.

Assume that the sample points $(x_{i},y_{i})$ are i.i.d. such that $\|x_{i}\|_{2}=\sqrt{q}$. Then there exist $c_{1},\ldots,c_{4}>0$ (depending only on $\sigma$) and $\delta>0$ such that, if

then, with probability at least $1-\delta$, the residual network (3) satisfies the $(M,\mu)$-local PL condition around its initialization, with $\displaystyle M=\frac{c_{3}}{\sqrt{nq}}$ and $\displaystyle\mu=\frac{c_{4}}{n\sqrt{n}q}$.

We emphasize that Proposition 5 requires the width $m$ to scale only linearly with the sample size $n$, which improves on the literature (see Section 2). The other assumptions are mild. Note that our proof shows that the parameter $\delta$ is small if $n$ grows at most polynomially with $d$ (see Appendix B.5).

We are now ready to state convergence in the long-time and large-depth limits to a global minimum of the empirical risk, when the local PL condition holds and the norm of the targets $y_{i}$ is small enough.

for some $C^{\prime}>0$ depending on $\sigma$. Moreover, the following statements hold as $t$ and $L$ tend to infinity:

converges uniformly over $s\in$ to $\mathcal{Z}_{\infty}:=(\mathcal{V}_{\infty},\mathcal{W}_{\infty})$.

Uniformly over $s\in$ and $x\in\mathcal{X}$, the hidden layer $h_{\left\lfloor Ls\right\rfloor}^{L}(t)$ converges to the solution at time $s$ of the neural ODE

Uniformly over $x\in\mathcal{X}$, the output $F^{L}(x;t)$ converges to $F_{\infty}(x)=B_{\infty}H(1)$. Furthermore, $F_{\infty}(x_{i})=y_{i}$ for all $i\in\{1,\dots,n\}$.

This theorem proves two important results of separate interest. On the one hand, equation (10) shows the long-time convergence of the gradient flow for deep residual networks under the linear overparameterization assumption $m\geqslant c_{1}n$ of Proposition 5. On the other hand, when both $t$ and $L$ tend to infinity, the network converges to a neural ODE that further interpolates the training data. Note that the order in which $t$ and $L$ tend to infinity does not matter by uniform convergence properties.

3 Generalizations to other architectures and initialization

To simplify the exposition, we have so far considered a particular residual architecture defined in (3). However, most of our results hold for a more general residual network of the form

It is easy to see that our residual network of interest (3) is a special case of the general model (11) if $\sigma$ satisfies the assumptions of Section 3. However, other choices are possible, such as convolutional layers or a Lipschitz continuous version of Transformer (Kim et al., 2021). This latter application is particularly interesting in the light of the literature analyzing the Transformer architecture from a neural ODE point of view (Lu et al., 2019; Sander et al., 2022a; Geshkovski et al., 2023).

Numerical experiments

We now present numerical experiments to validate our theoretical findings, using both synthetic and real-world data. Experimental details are given in Appendix E.

We consider the residual network (3) with the initialization scheme of Section 3. So, the $V_{k}^{L}$ are initialized to zero and the $W_{k}^{L}$ to weight-tied standard Gaussian matrices. To ease the presentation, we consider the case where $q=d=d^{\prime}$, and we do not train the weights $A^{L}$ and $B^{L}$, which therefore stay equal to the identity. The activation function is GELU (Hendrycks & Gimpel, 2016), which is a smooth approximation of ReLU: $x\mapsto\max(x,0)$. The sample points $(x_{i},y_{i})_{1\leqslant i\leqslant n}$ follow independent standard Gaussian distributions. Note that it does not hurt to take $x$ and $y$ independent since, in this subsection, our focus is on optimization results only and not on statistical aspects. The mean-squared error is minimized using full-batch gradient descent. The following experiments exemplify the large-depth ($t\in[0,T]$, $L\to\infty$) and long-time ($t\to\infty$, $L$ finite) limits.

We now turn to the long-time training setup, training for $80{,}000$ iterations with $L=64$. In Figure 2, we plot a specific (randomly-chosen) coefficient of matrices $V_{k}^{L}$ and $W_{k}^{L}$ across layers, for different training times. This illustrates Theorem 6 in a practical setting since, visually, the weights behave as a Lipschitz continuous function for any training time and converge to a Lipschitz continuous function as $t\to\infty$. We also display the loss as a function of the training time, corroborating the convergence of the loss to zero in Theorem 6.

2 Real-world data

Table 1 conveys several important messages. First, in accordance with our theory (Theorem 4), we obtain a neural ODE structure when using a smooth activation function and weight-tied initialization (lines $1$ and $3$ of Table 1). This is not the case when using the non-smooth ReLU activation and/or i.i.d. initialization. In fact, we prove in Appendix D that the smoothness of the weights is lost when training with ReLU in a simple setting, confirming this experimental observation. Furthermore, the third line of Table 1 shows that it is possible to obtain a reasonable accuracy with a neural ODE structure, which, as emphasized in Section 1, also comes with theoretical and practical advantages. Nevertheless, we obtain an improvement in accuracy in the cases corresponding to non-smooth weights, i.e., to a residual network that does not discretize an ODE. Extending our theory to such cases is left for future work.

Conclusion

We study the convergence of deep residual networks to neural ODEs. When properly scaled and initialized, residual networks trained with fixed-horizon gradient flow converge to neural ODEs as the depth tends to infinity. This result holds for very general architectures. In the case where both training time and depth tend to infinity, convergence holds under a local Polyak-Łojasiewicz condition. We prove such a condition for a family of deep residual networks with linear overparameterization.

The setting of neural ODE-like networks comes with strong guarantees, at the cost of some performance gap when compared with i.i.d. initialization as highlighted by the experimental section. Extending the mathematical large-depth study to the i.i.d. case is an interesting problem for future research. Previous work suggests that the correct limit object is then a stochastic differential equation instead of an ODE (Cohen et al., 2021; Cont et al., 2022; Marion et al., 2022).

P.M. is supported by a grant from Région Île-de-France and by MINES Paris - PSL. P.M. and Y.-H.W. are funded by a Google PhD Fellowship. M.S. is supported by the “Investissements d’avenir” program, reference ANR19-P3IA-0001, and by the European Research Council (ERC project NORIA). This work was granted access to the HPC resources of IDRIS under the allocation 2020-[AD011012073] made by GENCI.

References

In Section A, we give some results on the general residual network (11). In Section B, these results are instantiated in the specific case of the residual network (3), thus proving the results of the paper. Section C contains some lemmas that are useful for the proofs. We present in Section D a counter-example showing that a residual network with the ReLU activation can move away from the neural ODE structure during training. Finally, Section E presents some experimental details.

Appendix A Some results for general residual networks

Let $(\mathscr{U},\|\cdot\|)$, $(\mathscr{V},\|\cdot\|)$, and $(\mathscr{W},\|\cdot\|)$ be generic normed spaces. Then a function of two variables $g:\mathscr{U}\times\mathscr{V}\to\mathscr{W}$ is:

(Globally) Lipschitz continuous if there exists $K\geqslant 0$ such that, for $(u,v),(u^{\prime},v^{\prime})\in\mathscr{U}\times\mathscr{V}$,

Locally Lipschitz continuous in its first variable if, for any compacts $E\subset\mathscr{U},E^{\prime}\subset\mathscr{V}$, there exists $K\geqslant 0$ such that, for $(u,v),(u^{\prime},v)\in E\times E^{\prime}$,

Equivalent definitions hold for a function of one variable. Moreover, $g(\cdot,v)$ is said to be uniformly Lipschitz continuous for $v$ in $\mathscr{V}$ if there exists $K\geqslant 0$ such that, for $(u,v),(u^{\prime},v)\in\mathscr{U}\times\mathscr{V}$,

and uniformly Lipschitz continuous for $v$ in any compact if, for any compact $E^{\prime}\subset\mathscr{V}$, there exists $K\geqslant 0$ such that, for $(u,v),(u^{\prime},v)\in\mathcal{U}\times E^{\prime}$,

Throughout, we refer to a Lipschitz continuous function with Lipschitz constant $K\geqslant 0$ as $K$-Lipschitz.

As explained in Section 4.3, most of our results are proven for the general residual network

For a vector $x$, $\left\|x\right\|$ denotes the Euclidean norm. For a matrix $A$, the operator norm induced by the Euclidean norm is denoted by $\left\|A\right\|_{2}$, and the Frobenius norm is denoted by $\left\|A\right\|_{F}$. Finally, we use the notation $A^{L}$ (resp. $Z_{k}^{L}$, $B^{L}$) to denote the function $t\mapsto A^{L}(t)$ (resp. $t\mapsto Z_{k}^{L}(t)$, $t\mapsto B^{L}(t)$), since the parameters are considered as functions of the training time throughout this appendix.

First, in Section A.1, we study the case of the (clipped) gradient flow (5). We show that the weights and the difference between successive weights are bounded during the entire training. Section A.2 shows a similar result for the standard gradient flow (4) under a PL condition. In Section A.3, we show a generalized version of the Arzelà-Ascoli theorem, which allows us to prove the existence of a converging subsequence of the weights in the large-depth limit. Section A.4 is devoted to the convergence of the Euler scheme for parameterized ODEs. We then proceed to prove in Section A.5 our main result, i.e., the large-depth convergence of the gradient flow. The key step is to establish the uniqueness of the adherence point of the weights. Finally, in Section A.6, we prove the existence of a double limit for the weights and the hidden states when both the depth and the training time tend to infinity.

A.1 The trained weights are bounded in the finite training-time setup

Consider the residual network (12) initialized as explained in Appendix A and trained with the gradient flow (5) on $[0,T]$, for some $T\in(0,\infty)$. Let

Moreover, there exist $\alpha,\beta>0$ such that, for $t\in[0,T]$ and $k\in\{1,\dots,L-1\}$,

The following expressions for $\alpha$ and $\beta$ hold:

defining the gradient flow (5) are locally Lipschitz continuous, hence the gradient flow is defined on a maximal interval $[0,T_{\max})$ by the Picard-Lindelöf theorem (see Lemma 16). Let us show by contradiction that $T_{\max}=T$. Assume that $T_{\max}<T$. If this is true, again by the Picard-Lindelöf theorem, we know that the parameters diverge to infinity at $T_{\max}$. However, for any $t\in[0,T_{\max})$, we have

Bounds on $B^{L}$ and $Z_{k}^{L}$ by $M$ can be shown similarly. This contradicts the divergence of the parameters at $t=T_{\max}$. We conclude that the gradient flow is well defined on $[0,T]$ and that the bounds (17) hold.

It remains to bound the difference $\|Z_{k+1}^{L}(t)-Z_{k}^{L}(t)\|$. We have, for $t\in[0,T]$ and $k\in\{1,\dots,L-1\}$,

Furthermore, for $t\in[0,T]$, $k\in\{0,\dots,L-1\}$, and $i\in\{1,\dots,n\}$,

since $f(\cdot,Z_{k+1}^{L}(t))$ is $K_{1}$-Lipschitz, where $K_{1}$ is defined by (18), and $f(0,Z_{k+1}^{L}(t))=0$. Therefore, for any $k\in\{1,\dots,L\}$,

This bound shows that the pair $(h_{k,i}^{L}(t),Z_{k+1}^{L}(t))$ belongs to the compact $E$ defined in (19) for every $t\in[0,T]$, $k\in\{1,\dots,L\}$, and $i\in\{1,\dots,n\}$. In particular, $\|\partial_{2}f(h_{k-1,i}^{L}(t),Z_{k}^{L}(t))\|_{2}\leqslant K$, and

For $k\in\{1,\dots,L\}$ and $i\in\{1,\dots,n\}$,

Moreover, for $k\in\{0,\dots,L\}$ and $i\in\{1,\dots,n\}$,

where we use (17) and (21) for the last inequality. Putting all the pieces together, we obtain

Applying Grönwall’s inequality (see, e.g., Dragomir, 2003), we conclude that $\|Z_{k+1}^{L}(t)-Z_{k}^{L}(t)\|\leqslant(\|Z_{k+1}^{L}(0)-Z_{k}^{L}(0)\|+\frac{\beta T}{L})e^{\alpha T}$, as desired. ∎

A.2 The trained weights are bounded under the local PL condition

Moreover, the following expression for $\mu$ hold:

defining the gradient flow (5) are locally Lipschitz continuous, hence the gradient flow is defined on a maximal interval $[0,T_{\max})$ by the Picard-Lindelöf theorem (see Lemma 16). Let us show by contradiction that $T_{\max}=\infty$. Assume that $T_{\max}<\infty$. If this is true, again by the Picard-Lindelöf theorem, we know that the parameters diverge to infinity at $T_{\max}$. In particular, there exist $t\in(0,T_{\max})$ and $k\in\{1,\dots,L\}$ such that

Let $t^{*}\in(0,T_{\max})$ be the infimum of such times $t$. Then, for $t<t^{*}$ and $k\in\{1,\dots,L\}$,

and, by continuity of $A^{L}$, $B^{L}$, and $Z_{k}^{L}$, these inequalities also hold for $t=t^{*}$. By definition, this means that the $(M,\mu)$-local PL condition is satisfied for $t\leqslant t^{*}$, and ensures that

Therefore, by definition of the gradient flow (4),

Thus, by Grönwall’s inequality, for $t\leqslant t^{*}$,

Furthermore, by (23) and the definition of $M_{A}$, $M_{B}$, $M_{Z}$, we have, for $t\leqslant t^{*}$ and $k\in\{1,\dots,L\}$,

A quick scan through the proof of Proposition 7 reveals that by similar arguments, we have, for $t\leqslant t^{*}$, $k\in\{1,\dots,L\}$, and $i\in\{1,\dots,n\}$,

where the second inequality is a consequence of the Cauchy-Schwartz inequality. Let us now bound $\|Z_{k}^{L}(t^{*})-Z_{k}^{L}(0)\|$. We have, for $k\in\{1,\dots,L\}$,

since $(h_{k-1,i}^{L}(t),Z_{k}^{L}(t))\in E$ and $\|\partial_{2}f(h,z)\|\leqslant K$ for $(h,z)\in E$. Therefore, by (25),

where the last inequality is a consequence of the definition of $\mu$. Similarly, by (14) and (25),

This proves statement $(i)$ of the proposition. Moreover, the analysis above show that the derivatives of $A^{L}$, $Z_{k}^{L}$, and $B^{L}$ are bounded by a bounded integrable function independent of $L$ and $k$. This shows $(iii)$, together with the fact that the functions $A^{L}(t)$, $Z_{k}^{L}(t)$, and $B^{L}(t)$ admit limits as $t\to\infty$. Furthermore, the convergence towards their limit is uniform over $L$ and $k$, as we show for example for $A^{L}(t)$. If we denote by $A_{\infty}^{L}$ its limit, and apply the same steps as for bounding $\|A^{L}(t^{*})-A^{L}(0)\|_{F}$, we obtain, for any $t\geqslant 0$,

where the last inequality comes from the definition of $\mu$. The bound is independent of $L$, proving statement $(iv)$. Statement $(v)$ readily follows from (24).

To complete the proof, it remains to prove statement $(ii)$ by bounding the differences $\|Z_{k+1}^{L}(t)-Z_{k}^{L}(t)\|$. Now that we know that the weights are bounded, we can follow the same steps as in the proof of Proposition 7 and show the existence of $C_{1}$, $C_{2}>0$ such that

where the second inequality uses the definition of $\mu$. By Grönwall’s inequality,

A.3 Generalized Arzelà–Ascoli theorem

For $k\in\{1,\dots,L-1\}$, $\|Z_{k+1}^{L}(t)-Z_{k}^{L}(t)\|\leqslant\frac{C}{L}$,

For $k\in\{1,\dots,L\}$, $\|Z_{k}^{L}(t)\|\leqslant C$ and $\|\frac{dZ_{k}^{L}}{dt}(t)\|\leqslant b(t)$.

Note that if $I$ is a compact interval, then the existence of a (uniformly) convergent subsequence is guaranteed by the standard Arzelà–Ascoli theorem. Indeed, the uniform equicontinuity is a consequence of assumptions $(i)$ and $(ii)$, while $(ii)$ provides a uniform bound. However, if $I$ is not compact, more involved arguments are needed.

Assume, without loss of generality, that $b$ is also bounded by $C$. According to assumption $(i)$, for $t\in I$ and $i,j\in\{1,\dots,L\}$,

Also, according to $(ii)$, for $t,t^{\prime}\in I$ and $k\in\{1,\dots,L\}$,

It follows that, for $s,s^{\prime}\in$ and $t,t^{\prime}\in I$,

Therefore, with some simple algebra, we obtain

The statement of the proposition is then a consequence of the next three steps.

By considering (26) for the subsequence $\phi(L)$ and letting $L\to\infty$, we have that, for any $s,s^{\prime}\in$ and $t,t^{\prime}\in I$,

Let $\varepsilon>0$, $s\in$, and $t\in I$. Then, by (26) and (27), it is possible to find $\delta>0$ such that, for any $s^{\prime},s^{\prime\prime}\in$ and $t^{\prime},t^{\prime\prime}\in I$ satisfying $|s^{\prime}-s^{\prime\prime}|\leqslant\delta$ and $|t^{\prime}-t^{\prime\prime}|\leqslant\delta$,

Furthermore, there exists a finite set $\{s_{1},\dots,s_{S}\}\subset$ such that

In the sequel, we denote by $s^{*}$ an element of $\{s_{1},\dots,s_{S}\}$ that is at distance at most $\delta$ from $s$.

If $I$ is unbounded, then, by assumption $(ii)$ and since $b$ is integrable, there exists some $t_{0}>0$ such that, for $t\geqslant t_{0}$,

The same inequality holds for $\mathcal{Z}^{\phi}$ by letting $L$ tend to infinity. If $I$ is bounded, we simply let $t_{0}=\sup I$.

We may then pick a finite set $\{t_{1},\dots,t_{T}\}\subset[0,t_{0}]$ such that

Two cases may arise depending on the value of $t$. If $t\in[0,t_{0}]$, then there exists an element of the set $\{t_{1},\dots,t_{T}\}$ at distance at most $\delta$ from $t$, and we denote it by $t^{*}$. If $t>t_{0}$, we let $t^{*}=t_{0}$. According to (29) and (30), we then have in both cases that

To conclude, we have to bound the term $\|\mathcal{Z}^{\phi(L)}(s,t)-\mathcal{Z}^{\phi}(s,t)\|$ uniformly over $s$ and $t$. We first have

where the last inequality is a consequence of (31). The last term can be bounded as follows:

by using (28) and the fact that $s^{*}\in\{s_{1},\dots,s_{S}\}$. Putting all the pieces together, we finally obtain

By taking $L$ large enough, independent of $s$ and $t$, the sum of the last two terms can be made less than $\varepsilon$. Since $\varepsilon$ is arbitrary, this concludes the proof. ∎

A consequence of this result is a simplified version for sequences of functions only indexed by $L$ and not $k$, as follows.

A.4 Consistency of the Euler scheme for parameterized ODEs

Then $u_{\left\lfloor Ls\right\rfloor}^{L}$ tends to $U(s)$ uniformly over $s\in$, where $U$ is the unique solution of the ODE

Denote by $C$ the uniform Lipschitz constant of $g(\cdot,\theta)$ for $\|\theta\|\leqslant M$. Since $g(0,\cdot)\equiv 0$ and $g(\cdot,\Theta(s))$ is $C$-Lipschitz, one has

where $D_{E}=\sup_{x\in E}\|x\|<\infty$. A similar reasoning applies to the discrete scheme (32), using the discrete version of Grönwall’s inequality. More precisely, for any $k\in\{0,\dots,L-1\}$,

Overall, we can consider a restriction of $g$ to a compact set depending only on $M$, $C$, and $E$, which we will still denote by $g$ with a slight abuse of notation.Since $g$ is $\mathcal{C}^{1}$, it is therefore bounded and Lipschitz continuous, and we still let $C$ be its Lipschitz constant.

The next step is to recursively bound the size of this gap, first observing that $\Delta_{0}^{L}=\|a^{L}-a\|$. We have that

In the last inequality, we used the fact that $g$ is $C$-Lipschitz. Since,by definition, $\theta_{k+1}^{L}$ = $\Theta^{L}(\frac{k}{L-1})$, we obtain, for $k\in\{0,\dots,L-1\}$,

where $C_{\Theta}$ is the Lipschitz constant of $\Theta$. By the discrete Grönwall’s inequality, we deduce that, for $k\in\{0,\dots,L-1\}$,

This shows that the gaps $\Delta_{k}^{L}$ converge to zero uniformly over $k\in\{0,\dots,L\}$ as $L$ tends to infinity.

We conclude by observing that, for any $s\in$,

The results of Proposition 11 can be extended without much effort to two other related cases. First, the parameters $\theta_{k}^{L}$ may depend on some other variable $t$, as long as all assumptions are verified uniformly over $t$. Second, these parameters may converge to some limit parameters as both $L$ and $t$ go to infinity. This is encapsulated in the following two corollaries.

Then $u_{\left\lfloor Ls\right\rfloor}^{L}(t)$ tends to $U(s,t)$ uniformly over $s\in$ and $t\in I$, where $U(\cdot,t)$ is the unique solution of the ODE

Then $u_{\left\lfloor Ls\right\rfloor}^{L}(t)$ tends to $U(s)$ uniformly over $s\in$ as $L,t\to\infty$, where $U$ is the unique solution of the ODE

A.5 Large-depth convergence of the gradient flow

converges uniformly over $s\in$ and $t\in I$ to $\mathcal{Z}(s,t)$.

Uniformly over $s\in$, $t\in I$, and $x\in\mathcal{X}$, the hidden layer $h_{\left\lfloor Ls\right\rfloor}^{L}(t)$ converges to the solution at time $s$ of the neural ODE

Uniformly over $t\in I$ and $x\in\mathcal{X}$, the output $F^{L}(x;t)$ converges to $B(t)H(1,t)$.

In the remainder, we prove the uniqueness of the accumulation point $(Z^{\phi},A^{\phi},B^{\phi})$ by showing that it is the solution of an ODE that satisfies the assumptions of the Picard-Lindelöf theorem. The statements $(i)$ to $(iv)$ then follow easily.

Consider a general input $(x,y)\in\mathcal{X}\times\mathcal{Y}$, and let $H^{L}(s,t)=h_{\left\lfloor Ls\right\rfloor}^{L}(t)$ (recall that $h_{k}^{L}(t)$ is defined by the forward propagation (12)). Corollary 12, with $\theta_{k}^{L}=Z_{k}^{\phi(L)}$, $\Theta=\mathcal{Z}^{\phi}$, $a^{L}=A^{\phi(L)}x$, $g=f$, ensures that $H^{\phi(L)}(s,t)$ converges uniformly (over $s$ and $t$) to $H^{\phi}(s,t)$ that is the solution at time $s$ of the ODE

We now turn our attention to the backpropagation recurrence (13), which defines the backward state $p_{k}^{L}(t)$. First observe that the convergence of $H^{\phi(L)}$ implies that

The function $H^{\phi}(\cdot,t)$ is uniformly Lipschitz continuous for $t\in I$, as noted previously, and the same is true for $Z^{\phi}(\cdot,t)$ since $Z^{\phi}$ is Lipschitz continuous.

The function $h_{\left\lfloor(\phi(L)-1)s\right\rfloor+1}^{\phi(L)}(t)$ tends to $H^{\phi}(s,t)$ uniformly over $s$ and $t$, as seen in the beginning of the proof. More precisely, we know that $H^{\phi(L)}(s,t)=h_{\left\lfloor\phi(L)s\right\rfloor}^{\phi(L)}(t)$ tends to $H^{\phi}(s,t)$. Simple algebra and the fact that two successive iterates of (12) are separated by a distance proportional to $1/L$ show that both statements are equivalent. Furthermore, $\mathcal{Z}^{\phi(L)}(s,t)$ tends to $\mathcal{Z}^{\phi}(s,t)$ uniformly over $s$ and $t$ as noted above.

The function $g$ is $\mathcal{C}^{1}$ since $f$ is $\mathcal{C}^{2}$. We clearly have $g(0,\cdot)\equiv 0$. Finally, $g(\cdot,(h,Z))$ is uniformly Lipschitz continuous for $(h,Z)$ in any compact since $\partial_{1}f$ is continuous.

Overall, we obtain that $P^{\phi(L)}(s,t)$ converges uniformly (over $s$ and $t$) to $P^{\phi}(s,t)$, the solution at time $s$ of the backward ODE

The term inside $\pi$ can be rewritten as

Since $f$ is $\mathcal{C}^{2}$, $\partial_{2}f$ is locally Lipschitz continuous. Applying the first part of the proof to the specific case of $x_{i}$, we know that $H_{i}^{\phi(L)}$ and $P_{i}^{\phi(L)}$ uniformly bounded, and that $H_{i}^{\phi(L)}(s,t)$ and $P_{i}^{\phi(L)}(s,t)$ converge uniformly to $H_{i}^{\phi}(s,t)$ and $P_{i}^{\phi}(s,t)$. Therefore, the right-hand side of (37) converges uniformly over $s$ and $t$ to

A similar approach reveals that $A^{\phi}(t)$ and $B^{\phi}(t)$ are differentiable and that they verify the equations

which makes it a Banach space. We have to show that the mapping

is locally Lipschitz continuous with respect to this norm, where we recall that $H_{i}(s)$ in (42) is the solution at time $s$ of the initial value problem

and $P_{i}(s)$ is the solution at time $s$ of the initial value problem

To prove that the mapping (42) is locally Lipschitz continuous, we first check that it is well defined. Since $\mathcal{Z}$ is assumed to be only bounded (and not continuous), the solutions of the initial value problems (43) and (44) are well defined in the sense of the Caratheodory conditions, which are given in Lemma 17.

The norm inside the integral can be bounded by

Using Grönwall’s inequality, we obtain, for any $s\in$,

This shows that the function $(\mathcal{Z},A,B)\mapsto H_{i}$ is locally Lipschitz continuous. One proves by similar arguments that the function $(\mathcal{Z},A,B)\mapsto P_{i}$ is locally Lipschitz continuous. Thus, overall, the mapping (42) is locally Lipschitz continuous as a composition of locally Lipschitz continuous functions.

The uniform convergence of $(\mathcal{Z}^{L},A^{L},B^{L})$ to $(\mathcal{Z},A,B)$ is then easily shown by contradiction. Suppose that uniform convergence does not hold. If this is true, then there exists a subsequence that stays at distance $\varepsilon>0$ from $(\mathcal{Z},A,B)$ (in the sense of the uniform norm). Then arguments similar to the beginning of the proof show the existence of a second accumulation point, which is a contradiction. This shows the uniform convergence, yielding statements $(i)$ and $(ii)$ of the theorem.

Finally, reapplying Corollary 12 with $\theta_{k}^{L}=Z_{k}^{L}$, $\Theta=\mathcal{Z}$, $a^{L}=A^{L}x$, $g=f$, completes the proof by proving statements $(iii)$ and $(iv)$. ∎

Interestingly, the proof of Theorem 14 provides us with an explicit description of the evolution of the continuous-depth limiting weights during training. With the notation of the proof, the continuous weights satisfy the training dynamics:

where we recall that $H_{i}(s,t)$ is the solution at time $s$ of the initial value problem

and $P_{i}(s,t)$ is the solution at time $s$ of the problem

These equations can be thought of as the continuous-depth equivalent of the backpropagation equations.

A.6 Existence of the double limit when L,t𝐿𝑡L,t tend to infinity

Consider the residual network (12), and assume that:

Then the following four statements hold as $t$ and $L$ tend to infinity:

Uniformly over $s\in$ and $x\in\mathcal{X}$, the hidden layer $h_{\left\lfloor Ls\right\rfloor}^{L}(t)$ converges to the solution at time $s$ of the ODE

Uniformly over $x\in\mathcal{X}$, the output $F^{L}(x;t)$ converges to $F_{\infty}(x)=B_{\infty}H(1)$. Furthermore, $F_{\infty}(x_{i})=y_{i}$ for $i\in\{1,\dots,n\}$.

The existence of limits $A_{\infty}$ and $B_{\infty}$ to $A^{L}(t)$ and $B^{L}(t)$ as $L$ and $t$ tend to infinity is given by Lemma 19. The same argument applies to $Z_{\left\lfloor sL\right\rfloor}^{L}(t)$, which provides a limit $\mathcal{Z}_{\infty}(s)$ to the sequence. Furthermore, following the proof of the lemma, we see that the convergence of $Z_{\left\lfloor sL\right\rfloor}^{L}(t)$ to $\mathcal{Z}_{\infty}(s)$ is uniform over $s\in$. Corollary 13, applied with $\theta_{k}^{L}=Z_{k}^{L}$, $\Theta_{\infty}=\mathcal{Z}_{\infty}$, $a^{L}=A^{L}x$, $g=f$, then ensures that $h_{\left\lfloor Ls\right\rfloor}^{L}(t)$ converges uniformly (over $s\in$ and $x\in\mathcal{X}$) to $H(s)$ that is the solution at time $s$ of (45), as $L$ and $t$ tend to infinity. As a consequence, $F^{L}(x;t)$ converges uniformly over $x$ to $F_{\infty}(x)$ as $L,t\to\infty$. Furthermore, recall that

The left-hand side converges as $L,t\to\infty$ to by assumption of the proposition, while the right-hand side converges to

Therefore, $F_{\infty}(x_{i})=y_{i}$ for $i\in\{1,\dots,n\}$, and the proof is complete. ∎

Appendix B Proofs of the results of the main paper

In this section, we prove the results of the main paper. Most of these results follow from those presented in Section A. The only substantial proof is that of Proposition 5, which shows the local PL condition. It uses a result of Nguyen & Mondelli (2020) involving the Hermite transform and the sub-Gaussian variance proxy, which we define briefly. We refer to Debnath & Bhatta (2014, Chapter 17) and Vershynin (2018, Sections 2.5.2 and 3.4.1), respectively, for more detailed explanations.

The $r$-th normalized probabilist’s Hermite polynomial is given by

This family of polynomials forms an orthonormal basis of square-integrable functions for the inner product

Therefore, any function $\sigma$ such that $\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\sigma^{2}(x)e^{-x^{2}/2}dx<\infty$ can be decomposed on this basis. The $r$-th coefficient of this decomposition is denoted by $\eta_{r}(\sigma)$.

For a matrix $A$, we let $s_{\min}$ and $s_{\max}$ its minimum and maximum singular values, and similarly, $\lambda_{\min}$ and $\lambda_{\max}$ its minimum and maximum eigenvalues (whenever they exist).

Before delving into the proofs, we briefly describe the parts of this section that make use of the specific model (3). The most important one is the proof of Proposition 5, i.e., the proof that the residual network satisfies the $(M,\mu)$-local PL condition. Additionally, in the proof of Proposition 3, the expressions for $M$ and $K$ are valid only for the specific model (3). Finally, in the proof of Theorem 6, the beginning of the proof reveals that condition (22) of Proposition 8 on $\mu$ can be expressed as a condition on the norm of the labels $y_{i}$. This applies only to the specific model (3). Observe that, if one assumes that the general residual network of Section A satisfies the $(M,\mu)$-local PL condition with $\mu$ given by (22), then the rest of the proof of Theorem 6 unfolds, and the conclusions of the theorem hold for the general model.

B.1 Proof of Proposition 1

Proposition 1 is a consequence of Proposition 7 with $f(h,(V,W))=\frac{1}{\sqrt{m}}V\sigma(\frac{1}{\sqrt{q}}Wh)$.

B.2 Proof of Proposition 2

Proposition 11, with $\theta_{k}^{L}=(V_{k}^{L},W_{k}^{L})$, $\Theta=(\mathcal{V},\mathcal{W})$, $a^{L}=Ax$, $g(h,(V,W))=\frac{1}{\sqrt{m}}V\sigma(\frac{1}{\sqrt{q}}Wh)$, gives the existence and uniqueness of the solution of the neural ODE (6). Moreover, inspecting the proof of Proposition 11, equations (35) gives that, for any input $x\in\mathcal{X}$, the difference between the last hidden layer $h_{L}^{L}$ of the discrete residual network (3) and its continuous counterpart $H(1)$ in the neural ODE (6) is bounded by

where $C^{\prime}>0$ is independent of $L$ and $x\in\mathcal{X}$, and $\Theta^{L}(s)=\theta_{\left\lfloor(L-1)s\right\rfloor+1}^{L}$. The function $\Theta^{L}$ is a piecewise-constant interpolation of $\Theta$ with pieces of length $\frac{1}{L-1}$. Since $\Theta$ is Lipschitz continuous, the distance between $\Theta$ and $\Theta^{L}$ decreases as $\nicefrac{{C^{\prime\prime}}}{{L}}$ for some $C^{\prime\prime}>0$ depending on $\Theta$ but not on $L$. This yields $\|h_{L}^{L}-H(1)\|\leqslant\frac{C^{\prime}(1++C^{\prime\prime})}{L}$, where $C^{\prime}$ and $C^{\prime\prime}$ are independent of $L$ and $x\in\mathcal{X}$. Since $F^{L}(x)=Bh_{L}^{L}$ and $F(x)=BH(1)$, the result is proven.

B.3 Proof of Proposition 3

Furthermore, due to our initialization scheme described in Section 3,

B.4 Proof of Theorem 4

B.5 Proof of Proposition 5

Now that we have introduced the necessary notation, we can proceed to prove some preliminary estimates. Since $M\leqslant\frac{1}{2}\leqslant\sqrt{2qm}$, we have, for $k\in\{1,\dots,n\}$,

By Lemma 20, with probability at least 1-\exp\big{(}-\frac{qm}{16}\big{)}, one has $\|\bar{W}\|_{F}\leqslant\sqrt{2qm}$. Together with the previous inequalities, this implies

where the second inequality is a consequence of Lemma 18, as follows:

Let us now bound $\|\mathbf{h}_{k}\|_{F}$ and $\|\mathbf{p}_{k}\|_{F}$. We have

Moreover, by (46), for any $k\in\{0,\dots,L-1\}$,

where the second inequality is a consequence of (48). Therefore, by (49),

Moving on to $\|\mathbf{p}_{k}\|_{F}$, the chain rule leads to

where $\odot$ denotes the element-wise product. Noting that $|\sigma^{\prime}|\leqslant K_{\sigma}$ and using (48), we obtain

It follows that $\|\mathbf{p}_{k}\|_{F}\geqslant\exp(-2\sqrt{2}K_{\sigma})\|\mathbf{p}_{L}\|_{F}$. In addition,

Therefore, by Lemma 18, since $d^{\prime}\leqslant q$,

Collecting bounds, we conclude that, for $k\in\{0,\dots,L\}$,

A similar proof reveals that, for $k\in\{0,\dots,L\}$,

As a consequence, when $m\geqslant n$, by Lemma 18,

by (47) and by definition of $M$. Putting together the two bounds above as well as (47), (48), and (50), we obtain

where $C_{1}=K_{\sigma}\exp(2\sqrt{2}K_{\sigma})$ and $C_{2}=128C_{1}K_{\sigma}$. Thus, when $C_{1}\sqrt{n}\leqslant\frac{1}{32}\sqrt{m}\eta_{r}(\sigma)$, we have

for $k\leqslant\frac{L\eta_{r}(\sigma)}{C_{2}\sqrt{nq}}$. As a consequence, for $k\leqslant\frac{L\eta_{r}(\sigma)}{C_{2}\sqrt{nq}}$, returning to (52),

letting $C_{3}=\frac{\exp(-2\sqrt{2}K_{\sigma})}{8}$. Therefore,

where we used the inequality $\lfloor x\rfloor\geqslant x/2$ for $x\geqslant 1$. This proves the result, with

With appropriate values of $r$ and $m$, the probability of failure $\delta$ can be made as small as

for any $\varepsilon>0$. This is possible first by choosing $r$ such that $2/r\geqslant\varepsilon$, then by choosing $m$ such that the first two terms are less than $\varepsilon$. Moreover, we refer the interested reader to Goel et al. (2020, Lemmas A.2 and A.9) for quantitative estimates of $\eta_{r}(\sigma)$ for ReLU and sigmoid activations. Finally, the expression (53) is essentially the same as the one appearing in Nguyen & Mondelli (2020, Theorem 3.3). As in this paper, we note that this expression is small if $n$ grows at most polynomially with $d$, in which case the exponential term in $d$ dominates the polynomial term in $n$.

B.6 Proof of Theorem 6

By Proposition 5, there exists $\delta>0$ such that, with probability at least $1-\delta$, the residual network (3) satisfies the $(M,\mu)$-local PL condition around its initialization, with

A close examination of the quantities involved in the definition of $C$ reveals that it depends only on $\mathcal{X}$, $\sigma$, $n$, and $q$. In particular, it does not depend on the dimension $m$.

Appendix C Some technical lemmas

We start by recalling the Picard-Lindelöf theorem (see, e.g., Luk, 2017, for a self-contained presentation, and Arnold, 1992, for a textbook).

The next lemma gives conditions for the existence and uniqueness of the global solution of the initial value problem (54) when the assumption of continuity of $g$ in its second variable is removed, thereby generalizing the Picard-Lindelöf theorem.

Hence, by Grönwall’s inequality, for $s\leqslant s^{*}$,

Thus, $\|U^{*}\|\leqslant\|U_{0}\|\exp(C)$, which is impossible. Hence the maximal solution of the restricted problem is defined on $$. Furthermore, the maximal solution of the original problem coincides with the restricted one whenever$U(s)\in D$, which is the case for every$s\in$, hence the maximal solution is defined on$$. ∎

The next three lemmas recall well-known results from linear algebra, analysis, and random matrix theory. Recall that $s_{\min}$ and $\lambda_{\min}$ denote respectively the minimum singular value and eigenvalue of a matrix.

If $m\geqslant r$, then $\|AB\|_{F}\geqslant s_{\min}(A)\|B\|_{F}$. Furthermore, if $n\geqslant r$, then $\|AB\|_{F}\geqslant\|A\|_{F}s_{\min}(B)$.

The first statement is a consequence of, e.g., Loyka (2015), which establishes that $s_{\min}(A+A^{\prime})\geqslant s_{\min}(A)-s_{\max}(A^{\prime})$, yielding the first inequality since $s_{\max}(A^{\prime})=\|A\|_{2}\leqslant\|A\|_{F}$. As for the second one, we have

Since $m\geqslant r$, the rightmost quantity is equal to $s_{\min}(A)\|B\|_{F}$, proving the second statement of the lemma. The third statement is similar. ∎

Hence, for $x_{1},x_{2}>x_{0}$ and $y_{1},y_{2}>y_{0}$,

The quantity $\|W\|_{F}^{2}$ follows a chi-squared distribution with $qm$ degrees of freedom. Hence, according to Laurent & Massart (2000, Lemma 1), for $x\geqslant 0$,

Taking $x=\frac{(M_{W}^{2}-1)qm}{16}$, we see that

where the bound follows from $M_{W}\geqslant\sqrt{2}$. Since furthermore $2x\leqslant\frac{1}{2}(M_{W}^{2}-1)qm$, we obtain