Soufiane Hayou, Arnaud Doucet, and Judith Rousseau

Exact Convergence Rates of the Neural Tangent Kernel in the Large Depth Limit

Soufiane Hayou hayou@nus.edu.sg Affiliation: Department of Mathematics Affiliation: National University of Singapore Arnaud Doucet arnaud.doucet@stats.ox.ac.uk Affiliation: Department of Statistics Affiliation: University of Oxford Judith Rousseau judith.rousseau@stats.ox.ac.uk Affiliation: Department of Statistics Affiliation: University of Oxford

Abstract

Recent work by Jacot et al. 2018 has shown that training a neural network using gradient descent in parameter space is related to kernel gradient descent in function space with respect to the Neural Tangent Kernel (NTK). Lee et al. 2019 built on this result by establishing that the output of a neural network trained using gradient descent can be approximated by a linear model when the network width is large. Indeed, under regularity conditions, the NTK converges to a time-independent kernel in the infinite-width limit. This regime is often called the NTK regime. In parallel, recent works on signal propagation (Poole et al. 2016; Schoenholz et al. 2017; Hayou et al. 2019a) studied the impact of the initialization and the activation function on signal propagation in deep neural networks. In this paper, we connect these two theories by quantifying the impact of the initialization and the activation function on the NTK when the network depth becomes large. In particular, we provide a comprehensive analysis of the convergence rates of the NTK regime to the infinite depth regime.

^†^†heading: 0 0000 0-00 0/00 00/00 meila00a^†^†shortheadings: Exact convergence rates of the NTK regime / Hayou, Doucet, and Rousseau^†^†firstpage: 0

keywords

Neural tangent kernel, Overparameterized neural networks, deep neural networks, infinite depth limit, initialization.

1 Introduction

The theoretical analysis of the generalization capacity of Deep Neural Networks (DNNs) has been the topic of a multitude of work; see e.g. Du et al. 2018; Nguyen and Hein 2018; Zhang et al. 2017; Zou et al. 2018). Recently, there has been an growing interest in the implicit bias of DNNs in the infinite-width limit (e.g. infinite number of neurons per layer for a fully connected neural network and infinite number of channels for a convolutional neural network). Jacot et al. 2018 introduced the Neural Tangent Kernel (NTK) that characterises DNN training with gradient flow. The infinite-width limit of these dynamics is referred to as the NTK regime or Lazy training regime. This nomenclature follows from the fact that, in this regime, the NTK remains constant (with respect to training time) during training and the training procedure is well approximated by a first order Taylor expansion of the output function near its initial value. Lee et al. 2019 demonstrated that such a simple model could lead to surprisingly good performance. However, most experiments in the NTK regime have been conducted with shallow neural networks and do not extend to DNNs. In this paper, we address this topic by establishing the limitations of the NTK regime for DNNs, showing how it differs from the actual training of DNNs with Stochastic Gradient Descent.

Neural Tangent Kernel.

Jacot et al. 2018 showed that training a neural network (NN) with GD (Gradient Descent) in parameter space is equivalent to GD in a function space with respect to the NTK. Du et al. 2019b used a similar approach to prove that full batch GD converges to global minima for shallow neural networks, and Karakida et al. 2019 linked the Fisher information matrix to the NTK, studying its spectral distribution for infinite-width NN. The infinite-width limit for different architectures was studied by Yang 2019, who introduced a tensor formalism that can express neural computations for a variety of architectures. Lee et al. 2019 studied a linear approximation of the full batch GD dynamics based on the NTK, and gave a method to approximate the NTK for different architectures. Finally, Arora et al. 2019b proposed an efficient algorithm to compute the NTK for convolutional architectures (Convolutional NTK). In all of these papers, the authors only studied the effect of the infinite-width limit (NTK regime) on relatively shallow networks.

Information propagation.

In parallel, information propagation in infinite-width DNNs has been studied by Hayou et al. 2019a; Lee et al. 2018; Schoenholz et al. 2017; Yang and Schoenholz 2017. These works provide an analysis of the signal propagation at initialization. In particular, they study the impact of the choice of initialization hyper-parameters (variance of the initial random weights). They identify a set of hyper-parameters known as the Edge of Chaos (EOC) and a class of activation functions ensuring ‘deeper’ propagation of the information carried by the input, so that the network output still carries some information about the input. In this paper, we prove that the EOC initialization has also some benefits on the NTK at initialization, which, in the infinite-width limit, remains constant during training.

NTK training and SGD training.

Stochastic Gradient Descent (SGD) has been successfully used to train DNNs. Following the introduction of the NTK in Jacot et al. 2018, Lee et al. 2019 suggested a different approach to training overparameterized neural networks. The idea originates from the conjecture that, in overparameterized models, a local minimum exists near the initial weights. Thus, using a first order Taylor expansion at these initial weights, the NN reduces to a simple linear model, and this linear model is trained¹¹ 1 With quadratic loss, the linear model has an analytic solution and no training is required. instead of the original NN. Hereafter, we refer to this training procedure as the NTK training and the trained model as the NTK regime. If we replace SGD with the (continuous-time) gradient flow and consider the infinite-width limit, then these two training regimes become identical under some mild conditions. We provide further details in Section 2.

Contributions.

The NTK is usually studied in the context of finite depth and infinite-width. The large depth limit is often overlooked. Our aim in this paper is to provide a comprehensive theoretical analysis of the NTK regime in the large depth limit. This limit should be interpreted as infinite-width-then-infinite-depth limit of the NTK. Our contributions are as follows

•

We prove that the NTK regime is always trivial in the sense that the NTK is degenerate in the infinite depth limit. However, the convergence rate to this trivial regime is controlled by the initialization hyper-parameters.
•

We prove that for some standard neural architectures (Fully-connected and convolutional NNs), the EOC initialization provides sub-exponential convergence rates to this trivial regime, while other initialization schemes yield an exponential rate. More precisely, we obtain an exact convergence rate of $\Theta(\log(L)L^{-1})$ when the hyper-parameters are chosen in the EOC, where the notation $g(x)=\Theta(m(x))$ means there exist two constants $A,B>0$ such that $A\,m(x)\leq g(x)\leq B\,m(x)$ . On the other hand, this rate becomes $\mathcal{O}(e^{-\gamma L}))$ when the initialization hyper-parameters are not in the EOC. For the same depth $L$ , the NTK regime is thus “less trivial” for an EOC initialization.
•

We characterize the convergence rate of the NTK for ResNet architectures. We show that, contrary to fully-connected and convolution NNs, this rate is always $\Theta(\log(L)L^{-1})$ irrespective of the initialization.
•

We leverage our theoretical results on the asymptotic behaviour of the NTK to obtain practical guidelines for the choice of the learning rate for SGD training. We establish the existence of a learning rate passband for SGD training; any choice of the learning rate outside of this passband yields poor performance.

Table 1: “Does the model learn?”. We train a Feedforward NN on CIFAR10 using both standard SGD training and NTK training defined in Section 2. For shallow networks, both SGD and NTK yield good performance (See Section 5). However, for deep networks, the NTK training yields trivial accuracy of around

\sim 10\%

for any initialization scheme.

		EOC Init	Other Init
$L=3$	NTK	✓	✓
$L=3$	SGD	✓	✓
$L=30$	NTK	✓	✗
$L=30$	SGD	✓	✗
$L=300$	NTK	✗	✗
$L=300$	SGD	✓	✗

Table 1 summarizes the behaviour of NTK and SGD training for different depths and initialization schemes of a Fully-connected Feedforward Neural Network (FFNN) on the CIFAR10 dataset. We show whether the model test accuracy is significantly larger than $10\%$ , which is the accuracy of the trivial random classifier. The results displayed in this table illustrate that for shallow FFNN ( $L=3$ ), the model learns to classify with both NTK training and SGD training for any initialization scheme. For a medium depth network ( $L=30$ ), NTK training and SGD training both succeed in training the model with an initialization in the EOC, while they both fail with other initializations. It has already been observed that, with SGD, an EOC initialization is beneficial for the training of DNNs (Hayou et al. 2019a; Schoenholz et al. 2017). Our results show that the EOC initialization is also beneficial for NTK training (Section 2). However, for a deeper network with $L=300$ , NTK training fails for any initialization, while SGD training succeeds in training the model with EOC initialization. This confirms the limitations of NTK training for DNNs, suggesting that parameter updates might play a more significant role in generalization of DNNs compared to the implicit architectural bias²² 2 We refer to the implicit bias solely induced by the architecture and not the training algorithm.. However, although the large depth NTK regime is trivial, we leverage this asymptotic analysis to obtain a theoretical upper bound on the learning rate (Section 4). We illustrate our theoretical results through extensive simulations. All the proofs are detailed in the appendix.

Related work.

After the first version of this paper was made publicly available (Hayou et al. 2019b), similar albeit weaker results on the behaviour of the NTK in the large depth limit have been derived independently. Xiao et al. 2020 studied the effect of the initialization on the trainability/generalization of the NTK regime in the case of FFNN, via the condition number of the kernel matrix. Their results agree with ours in the case of FFNN. However, we also provide here uniform convergence rates of the kernel. Huang et al. 2020 considered a scaled version of ResNet (where the blocks are scaled) with ReLU and proved an upper bound on the convergence rate of order $\mathcal{O}\left(\frac{\text{polylog}L}{L}\right)$ , while our results give the exact rate of $\Theta(\log(L)L^{-1})$ for both ReLU and Tanh. Note that for NTK training, a lower bound on the rate is more useful than an upper bound as we want to ensure that the convergence rate of the NTK to the trivial infinite-depth regime is not fast. Our $\Theta(\log(L)L^{-1})$ rate has the advantage of being both an upper and a lower bound. More generally, scaling ResNet was shown to be an effective way to avoid degeneracy in the large depth limit (Hayou et al. 2021). Other papers studied the spectrum of the NTK for fixed depth $L$ , e.g. (Bietti and Bach 2021; Chen and Xu 2021).

2 Neural Networks and Neural Tangent Kernel

Consider a neural network consisting of $L$ layers of widths $(n_{l})_{1\leq l\leq L}$ , $n_{0}=d$ , and let $\theta=(\theta^{l})_{1\leq l\leq L}$ be the flattened vector of weights and bias indexed by the layer’s index, and $p$ be the dimension of $\theta$ . The output function $f$ of the neural network is given by some mapping $s:\mathbb{R}^{n_{L}}\rightarrow\mathbb{R}^{o}$ of the last layer $y^{L}(x)$ ; $o$ being the dimension of the output (e.g. number of classes for a classification problem). For any input $x\in\mathbb{R}^{d}$ , we thus have $f(x,\theta)=s(y^{L}(x))\in\mathbb{R}^{o}$ . As we train the model, $\theta$ changes with time $t$ , and we denote by $\theta_{t}$ the value of $\theta$ at training time $t$ and $f_{t}(x)=f(x,\theta_{t})$ . Let $\mathcal{D}=\{(x_{i},z_{i}):1\leq i\leq N\}$ be a general dataset, and let $\mathcal{X}=(x_{i})_{1\leq i\leq N}$ , $\mathcal{Z}=(z_{j})_{1\leq j\leq N}$ be the sequences of inputs and outputs respectively. For all functions $g:\mathbb{R}^{d\times o}\rightarrow\mathbb{R}^{k}$ we denote by $g(\mathcal{X},\mathcal{Z})$ the matrix in $\mathbb{R}^{k\times N}$ with entries $g(x_{i},z_{i}),i\in[N]\overset{\small{def}}{=}\{1,\dots,N\}$ .

The NTK is defined as the $o\times o$ dimensional kernel $K^{L}_{\theta}$ given for all $x,x^{\prime}\in\mathbb{R}^{d}$ by

K^{L}_{\theta_{t}}(x,x^{\prime})=\nabla_{\theta}f(x,\theta_{t})\nabla_{\theta}f(x^{\prime},\theta_{t})^{T}=\sum_{l=1}^{L}\nabla_{\theta^{l}}f(x,\theta_{t})\nabla_{\theta^{l}}f(x^{\prime},\theta_{t})^{T}\in\mathbb{R}^{o\times o}.

Jacot et al. 2018 studied the dynamics of the output of the NN as a function of the training time $t$ when the network is trained using a GD algorithm. For parameters $\theta$ , the empirical loss is given by $\mathcal{L}(\theta)=\frac{1}{N}\sum_{i=1}^{N}\ell(f(x_{i},\theta),y_{i})$ . The GD updates are given by

\hat{\theta}_{t+1}=\hat{\theta}_{t}-\eta\nabla_{\theta}\mathcal{L}(\hat{\theta}_{t}),

(1)

where $\eta>0$ is the learning rate.
Let $T>0$ be the training time and $N_{s}=T/\eta$ be the number of steps of the discrete GD (1). Jacot et al. 2018 studied the continuous time limit of (1), often called gradient flow, with discretization step $\Delta t=\eta$ , which yields

d{\theta_{t}}=-\nabla_{\theta}\mathcal{L}(\theta_{t})dt.

(2)

This can be written as

d\theta_{t}=-\frac{1}{N}\nabla_{\theta}f(\mathcal{X},\theta_{t})^{T}\nabla_{z}\ell(f(\mathcal{X},\theta_{t}),\mathcal{Z})dt,

where $\nabla_{\theta}f(\mathcal{X},\theta_{t})$ is a matrix of dimension $oN\times p$ and $\nabla_{z}\ell(f(\mathcal{X},\theta_{t}),\mathcal{Z})$ is the flattened vector of dimension $oN$ constructed from the concatenation of the vectors $\nabla_{z}\ell(z,y_{i})_{|z=f(x_{i},\theta_{t})},i\leq N$ . As a result, the output function $f_{t}(x)=f(x,\theta_{t})\in\mathbb{R}^{o}$ satisfies the following ordinary differential equation (ODE)

df_{t}(x)=-\frac{1}{N}\nabla_{\theta}f(x,\theta_{t})\nabla_{\theta}f(\mathcal{X},\theta_{t})^{T}\nabla_{z}\ell(f_{t}(\mathcal{X}),\mathcal{Z})dt.

(3)

Given the dataset $\mathcal{D}$ , the NTK matrix at training time $t$ , denoted by $K^{L}_{\theta_{t}}(\mathcal{X},\mathcal{X})$ , is the $oN\times oN$ matrix defined blockwise by

K^{L}_{\theta_{t}}(\mathcal{X},\mathcal{X})=\left(\begin{array}[]{cccc}K^{L}_{\theta_{t}}(x_{1},x_{1})&\cdots&K^{L}_{\theta_{t}}(x_{1},x_{N})\\ K^{L}_{\theta_{t}}(x_{2},x_{1})&\cdots&K^{L}_{\theta_{t}}(x_{2},x_{N})\\ \vdots&\ddots&\vdots\\ K^{L}_{\theta_{t}}(x_{N},x_{1})&\cdots&K^{L}_{\theta_{t}}(x_{N},x_{N})\end{array}\right).

By applying Eq. (3) to the vector $\mathcal{X}$ , we obtain

df_{t}(x_{j})=-\frac{1}{N}K_{\theta_{t}}^{L}(x_{j},\mathcal{X})\nabla_{z}\ell(f_{t}(\mathcal{X}),\mathcal{Z})dt,\quad j=1,\cdots,N.

(4)

In the case of FFNN, Jacot et al. 2018 proved that with gradient descent, $K_{\theta_{t}}^{L}$ converges to a kernel function $K^{L}$ (independent on $\theta_{t}$ ) for all $t\leq T$ (where $T$ is an upper bound on the training time) as the widths $n_{1},\cdots,n_{L}$ go to infinity sequentially, i.e. $n_{1}\to\infty$ , then $n_{2}\to\infty$ , $\dots$ , then $n_{L}\to\infty$ . This was later generalized by Yang 2020 to the case where the limits can be taken simultaneously. This result holds under the technical assumption $\int_{0}^{T}\|\nabla_{z}\ell(f_{t}(\mathcal{X}),\mathcal{Z})\|_{2}dt<\infty$ a.s. with respect to the initialization weights. In this limit, Eq. (4) becomes

df_{t}(x_{j})=-\frac{1}{N}K^{L}(x_{j},\mathcal{X})\nabla_{z}\ell(f_{t}(\mathcal{X}),\mathcal{Z})dt,\quad j\in[N].

(5)

We note hereafter $\hat{K}^{L}=K^{L}(\mathcal{X},\mathcal{X})$ . For instance, with the quadratic loss $\ell(z^{\prime},z)=\frac{1}{2}||z^{\prime}-z||^{2}$ , Eq. (5) becomes

df_{t}(x_{j})=-\frac{1}{N}\hat{K}^{L}(f_{t}(\mathcal{X})-\mathcal{Z})dt,\quad j\in[N],

(6)

which is the ODE of a simple linear model that has the following closed-form solution

f_{t}(\mathcal{X})=e^{-\frac{t}{N}\hat{K}^{L}}f_{0}(\mathcal{X})+(I-e^{-\frac{t}{N}\hat{K}^{L}})\mathcal{Z}.

(7)

For general input $x\in\mathbb{R}^{d}$ (not necessarily in the dataset), we have

f_{t}(x)=f_{0}(x)+\gamma(x,\mathcal{X})(I-e^{-\frac{t}{N}\hat{K}^{L}})(\mathcal{Z}-f_{0}(\mathcal{X}))

(8)

where $\gamma(x)=K^{L}(x,\mathcal{X})(\hat{K}^{L})^{-1}$ .
The infinite-width limit of the training dynamics is given by Eq. (5), which leads to Eq. (8) under the quadratic loss. For other loss functions such as the cross-entropy loss (often used for classification tasks), some approximations can be used to obtain the infinite-width limit (see Lee et al. 2019 for more details). These approximations are implemented in the Python package Neural-Tangents (Novak et al. 2020). Hereafter we refer to $f_{\infty}$ , i.e. the limit of $f_{t}$ in Eq. (6) as $t$ goes to infinity by the NTK regime solution or simply the NTK regime when there is no confusion.

As observed in Du et al. 2019a, the convergence rate (w.r.t time) of $f_{t}$ to $f_{\infty}$ (infinite training time) is given by the smallest eigenvalue of $\hat{K}^{L}$ . If the NTK becomes singular in the large depth limit, then the NTK training fails (the kernel matrix $\hat{K}^{L}$ converges to a singular matrix). Importantly, since $K^{L}$ is constant during training, its value is fixed at initialization. Therefore, we would naturally expect the initialization hyper-parameters to impact the infinite-width NTK; in Section 3, we prove several results on this link between initialization and the NTK.

An important aspect which will be of interest in the interpretation of our theoretical results is that, with the quadratic loss, the NTK regime solution $f_{\infty}$ is scale invariant in the sense that $f_{\infty}$ does not change if we scale the kernel by some scalar. In particular, this scalar can be depth-dependent, i.e. for any scaling factor $a_{L}$ ,

\gamma(x,\mathcal{X})=K^{L}(x,\mathcal{X})(\hat{K}^{L})^{-1}=(K^{L}(x,\mathcal{X})/a_{L})(\hat{K}^{L}/a_{L})^{-1}.

(9)

Thus, studying the NTK regime with kernel $K^{L}$ is equivalent to studying the NTK regime with any scaled kernel $K^{L}/a_{L}$ , as both kernels yield the same solution $f_{\infty}$ . In Theorems 1 and 2, we study scaled kernels to mitigate an exploding kernel effect in the limit of large depth. With the scale-invariance property stated above, the NTK regime solution remains unchanged in this case.

Another important aspect of the NTK regime is the generalization properties of $f_{\infty}$ . From Eq. (8), we can see that the term $\gamma$ plays a crucial role in the generalization capacity of the NTK regime. Different works (Du et al. 2019a; Arora et al. 2019a) have demonstrated that the inverse of the NTK matrix plays a crucial role in the generalization error of wide NN. Indeed, Cao and Gu 2019 proved that training a network of depth $L$ in the Lazy training regime yields a generalization bound of the form $\mathcal{O}(L\sqrt{\mathcal{Z}^{T}(\hat{K}^{L})^{-1}\mathcal{Z}/N})$ in the infinite-width limit, where $\mathcal{Z}$ is the vector of training data outputs. Moreover, Eq. (8) shows that the Reproducing Kernel Hilbert Space (RKHS) generated by $K^{L}$ controls $f_{t}$ . To see this, observe that for any $t\in(0,T)$ we can deduce from Eq. (8) that there exist coefficients $a_{1},...,a_{N}\in\mathbb{R}$ such that for all $x\in\mathbb{R}^{d}$ , $f_{t}(x)-f_{0}(x)=\sum_{i=1}^{N}a_{i}K^{L}(x_{i},x)$ , showing that the ‘training residual’ $f_{t}-f_{0}$ belongs to the RKHS of the NTK. In other words, with NTK training, $K^{L}$ controls what the network learns beyond initialization.

3 Asymptotic Neural Tangent Kernel

In this section, we study the behaviour of $K^{L}$ as $L$ goes to $\infty$ . We prove that $K^{L}$ converges in this limit to a degenerate kernel (i.e. rank-one kernel) and therefore the NTK regime becomes trivial. However, with an EOC initialization, this convergence is slow, which allows the use of NTK training for deeper NNs (NTK training is successful with $L=30$ , see Section 5). However, since the limiting NTK is trivial, NTK training necessarily fails for large depth DNNs. We restrict our analysis to the case where the output dimension is 1 ( $o=1$ ), the generalization of our results to multi-dimensional outputs is straightforward.

3.1 NTK parameterization and the Edge of Chaos: FFNN and CNN architectures

Let $\phi$ be the activation function (e.g. ReLU, Tanh etc.). We first establish results for the following architectures:

Feedforward Fully-connected Neural Network (FFNN).

Given depth $L$ , widths $(n_{l})_{1\leq l\leq L}$ , weights $w^{l}$ and bias $b^{l}$ . For some input $x\in\mathbb{R}^{d}$ , the forward propagation of the FFNN using the NTK parameterization³³ 3 The NTK parameterization introduces the factors $1/\sqrt{n_{l}}$ in front of the weights, this is necessary for the infinite-width limit. is given by

	$\displaystyle y^{1}_{i}(x)$	$\displaystyle=\frac{\sigma_{w}}{\sqrt{d}}\sum_{j=1}^{d}w^{1}_{ij}x_{j}+\sigma_{b}b^{1}_{i},$		(10)
	$\displaystyle y^{l}_{i}(x)$	$\displaystyle=\frac{\sigma_{w}}{\sqrt{n_{l-1}}}\sum_{j=1}^{n_{l-1}}w^{l}_{ij}\phi(y^{l-1}_{j}(x))+\sigma_{b}b^{l}_{i},\quad 2\leq l\leq L,$		(10)

where $\sigma_{b},\sigma_{w}\geq 0$ are constants. In this standard parameterization of FFNNs, $\sigma_{w}/\sqrt{n_{l-1}}$ and $\sigma_{b}$ are absorbed in the weights, and $(\sigma_{b},\sigma_{w})$ are called initialization hyper-parameters. In the NTK parameterization above, they are just constants in front of the weights. However, since these constants essentially represent the scale of the initialization weights, we preserve the nomenclature ‘initialization hyper-parameters’ to refer to $(\sigma_{b},\sigma_{w})$ .

Convolutional Neural Network (CNN).

Consider a 1-dimensional convolutional neural network of depth $L$ , denoting by $[m:n]$ the set of integers $\{m,m+1,...,n\}$ for $m\leq n$ , the forward propagation is given by

	$\displaystyle y^{1}_{i,\alpha}(x)$	$\displaystyle=\frac{\sigma_{w}}{\sqrt{v_{1}}}\sum_{j=1}^{n_{0}}\sum_{\beta\in ker}w^{1}_{i,j,\beta}x_{j,\alpha+\beta}+\sigma_{b}b^{1}_{i},$		(11)
	$\displaystyle y^{l}_{i,\alpha}(x)$	$\displaystyle=\frac{\sigma_{w}}{\sqrt{v_{l}}}\sum_{j=1}^{n_{l-1}}\sum_{\beta\in ker}w^{l}_{i,j,\beta}\phi(y^{l-1}_{j,\alpha+\beta}(x))+\sigma_{b}b^{l}_{i},\quad 2\leq l\leq L,$		(11)

where $i\in[n_{l}]$ is the channel number, $\alpha\in[0:M-1]$ is the neuron location in the channel, $n_{l}$ is the number of channels in the $l^{th}$ layer, and $M$ is the number of neurons in each channel, $ker=[-k:k]$ is a filter with size $2k+1$ and $v_{l}=n_{l-1}(2k+1)$ . Here, $w^{l}\in\mathbb{R}^{n_{l}\times n_{l-1}\times(2k+1)}$ . We assume periodic boundary conditions, so that $y^{l}_{i,\alpha}=y^{l}_{i,\alpha+M}=y^{l}_{i,\alpha-M}$ , and for $l=0$ , $x_{i,\alpha+M_{0}}=x_{i,\alpha}=x_{i,\alpha-M_{0}}$ . For the sake of simplification, we only consider the case of 1D CNN, the generalization to a $m$ -dimensional CNN for $m\in\mathbb{N}$ is straightforward.
Hereafter we write $y^{l}(x)=\mathcal{F}(w^{l},y^{l-1}(x))$ for either recursions (10) or (11).

We also denote by $x\cdot x^{\prime}$ the inner product in $\mathbb{R}^{d}$ for $x,x^{\prime}\in\mathbb{R}^{d}$ and for $x,x^{\prime}\in\mathbb{R}^{n_{0}\times(2k+1)}$ , let $[x,x^{\prime}]_{\alpha,\alpha^{\prime}}$ be a convolutional mapping defined by

[x,x^{\prime}]_{\alpha,\alpha^{\prime}}=\sum_{j=1}^{n_{0}}\sum_{\beta\in ker_{0}}x_{j,\alpha+\beta}x_{j,\alpha^{\prime}+\beta}^{{}^{\prime}}.

For both architectures, we initialize the weights and bias with $w^{l}_{ij},b^{l}_{i}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{N}(0,1)$ , where $\mathcal{N}(\mu,\sigma^{2})$ denotes the Gaussian distribution of mean $\mu$ and variance $\sigma^{2}$ . we are interested in infinite-width regime, which corresponds to an infinite number of neurons for fully-connected layers , and an infinite number of channels for convolutional layers, i.e. $\min_{l\geq 1}n_{l}$ goes to infinity.

A classical result in the literature of signal propagation at initialization is the following: in the infinite-width limit, the neurons $(y^{l}_{i}(.))_{i,l}$ converge to zero-mean Gaussian processes, as proved by Neal 1995; Lee et al. 2018; Matthews et al. 2018; Hayou et al. 2019a; Schoenholz et al. 2017; hence, their covariance kernels characterize their behaviour. Hereafter, we denote by $q^{l}(x,x^{\prime})$ (resp. $q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ ) the covariance between $y^{l}_{1}(x)$ and $y^{l}_{1}(x^{\prime})$ (resp. $y^{l}_{1,\alpha}(x)$ and $y^{l}_{1,\alpha^{\prime}}(x^{\prime})$ ). The choice of the neuron index 1 is arbitrary since different neurons in the same layer of a FFNN are identically distributed (a similar result holds in CNNs for the channel index instead of the neuron index). We denote the corresponding correlations by $c^{l}(x,x^{\prime})$ for FFNN and $c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ for CNN. In particular, we easily obtain $q^{1}(x,x^{\prime})=\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{d}x\cdot x^{\prime}$ for FFNN and $q^{1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{n_{0}(2k+1)}[x,x^{\prime}]_{\alpha,\alpha^{\prime}}$ for CNN.

Jacot et al. 2018 established a recursive formula for the infinite-width NTK of an FFNN when $\sigma_{w}=1$ . We generalize the result to any $\sigma_{w}>0$ in the next Lemmas, and Lemmas 2, 3 and 4 generalize it to other architectures as well. These generalizations are quite straightforward and can be established using the same induction as in Jacot et al. 2018.

Lemma 0 (Generalization of Theorem 1 in Jacot et al. 2018).

Consider an FFNN of the form (10). Then, as $n_{1},n_{2},...,n_{L-1}\rightarrow\infty$ sequentially, we have for all $x,x^{\prime}\in\mathbb{R}^{d}$ , $i,i^{\prime}\leq n_{L}$ , $K^{L}_{ii^{\prime}}(x,x^{\prime})=\delta_{ii^{\prime}}K^{L}(x,x^{\prime})$ , where $K^{L}(x,x^{\prime})$ is given by the recursive formula

K^{L}(x,x^{\prime})=\dot{q}^{L}(x,x^{\prime})K^{L-1}(x,x^{\prime})+\hat{q}^{L}(x,x^{\prime}),\quad\textrm{where}

$\hat{q}^{l}(x,x^{\prime})=\sigma_{b}^{2}+\sigma_{w}^{2}\mathbb{E}[\phi(y_{1}^{l-1}(x))\phi(y_{1}^{l-1}(x^{\prime}))]$ and $\dot{q}^{l}(x,x^{\prime})=\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(y_{1}^{l-1}(x))\phi^{\prime}(y_{1}^{l-1}(x^{\prime}))]$ .

Lemma 1 is proved in Appendix 2.
For CNNs, the next lemma shows that a similar recursion for the infinite-width NTK holds. The infinite-width for CNNs is obtained by taking the number of channels to infinity.

Lemma 0 (Infinite-width NTK of a CNN).

Consider a CNN of the form (11), then we have that for all $x,x^{\prime}\in\mathbb{R}^{d}$ , $i,i^{\prime}\leq n_{1}$ and $\alpha,\alpha^{\prime}\in[0:M-1]$

K^{1}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}\left(\frac{\sigma_{w}^{2}}{n_{0}(2k+1)}[x,x^{\prime}]_{\alpha,\alpha^{\prime}}+\sigma_{b}^{2}\right).

For $l\geq 2$ , as $n_{1},n_{2},...,n_{l-1}\rightarrow\infty$ sequentially, we have for all $i,i^{\prime}\leq n_{l}$ , $\alpha,\alpha^{\prime}\in[0:M-1]$ , $K^{l}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}K^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ , where $K^{l}_{\alpha,\alpha^{\prime}}$ is given by the recursion

\displaystyle K^{l}_{\alpha,\alpha^{\prime}}

\displaystyle=\frac{1}{2k+1}\sum_{\beta\in ker_{l}}\Psi^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta},

where $\Psi^{l-1}_{\alpha,\alpha^{\prime}}=\dot{q}^{l}_{\alpha,\alpha^{\prime}}K^{l-1}_{\alpha,\alpha^{\prime}}+\hat{q}^{l}_{\alpha,\alpha^{\prime}}$ , and $\hat{q}^{l}_{\alpha,\alpha}$ , resp. $\dot{q}^{l}_{\alpha,\alpha^{\prime}}$ is defined as $q^{l}$ , resp. $\dot{q}^{l}$ in Lemma 1, with $y_{1,\alpha}^{l-1}(x),y_{1,\alpha^{\prime}}^{l-1}(x^{\prime})$ in place of $y_{1}^{l-1}(x),y_{1}^{l-1}(x^{\prime})$ .

Lemma 2 is proved in Appendix 2.

In the remainder of the paper, we leverage the above recursive formulas for the NTK to analyse its dynamics as $L$ goes to infinity. To alleviate the notations, hereafter, we use the notation $K^{L}$ for the NTK of both FFNN and CNN. For FFNN, $K^{L}$ is given in Lemma 1, whereas for CNN, $K^{L}=K^{L}_{\alpha,\alpha^{\prime}}$ and is given in Lemma 2 for any $\alpha,\alpha^{\prime}$ , i.e. all results that follow are true for any $\alpha,\alpha^{\prime}$ . We now present a brief review the EOC theory.

Edge of Chaos (EOC).

Recall that the weights and bias are randomly initialized with a Gaussian distribution (see above). Given an input $x$ , we denote by $q^{l}(x)$ the variance of $y^{l}(x)$ . The convergence analysis of $q^{l}(x)$ as $l$ increases is provided in Lee et al. 2018, Schoenholz et al. 2017, and Hayou et al. 2019a. Under general regularity conditions, it is proved that $q^{l}(x)$ converges to a point $q(\sigma_{b},\sigma_{w})>0$ independent of $x$ as $l\rightarrow\infty$ . The asymptotic behaviour of the correlation $c^{l}(x,x^{\prime})$ between $y^{l}(x)$ and $y^{l}(x^{\prime})$ for any two inputs $x$ and $x^{\prime}$ is also driven by the choice of $(\sigma_{b},\sigma_{w})$ ; Schoenholz et al. 2017 show that if $\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(\sqrt{q(\sigma_{b},\sigma_{w})}Z)^{2}]<1$ , where $Z\sim\mathcal{N}(0,1)$ then $c^{l}(x,x^{\prime})$ converges to 1 exponentially quickly, This is called the ordered phase. On the other hand, if $\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(\sqrt{q(\sigma_{b},\sigma_{w})}Z)^{2}]>1$ then $c^{l}(x,x^{\prime})$ converges to $c<1$ , this is referred to as the chaotic phase. The authors define the EOC as the set of parameters $(\sigma_{b},\sigma_{w})$ , such that $\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(\sqrt{q(\sigma_{b},\sigma_{w})}Z)^{2}]=1$ . The behaviour of $c^{l}(x,x^{\prime})$ in the EOC is studied in Hayou et al. 2019a where it is proved to converge to 1 at a polynomial rate. We provide a comprehensive review of the theory of signal propagation theory at initialization in Appendix 0.2. Notice that most results on signal propagation are stated with standard parameterization ( $\sigma_{w}/\sqrt{n_{l-1}}$ and $\sigma_{b}$ are absorbed in the weights and bias at initialization). The two parameterizations are actually closely related and yield similar results for a properly scaled learning rate. In this work, we focus exclusively on the NTK parameterization introduced above and derive our results in this setting. We will show in this section that a choice of $(\sigma_{b},\sigma_{W})$ satisfying the EOC condition is beneficial for the NTK. On the contrary, any initialization in the ordered or chaotic phase, leads to exponential convergence rate of $K^{L}$ to a constant kernel in the limit of infinite depth.

Let us first introduce some notation for the uniform convergence results. For $\epsilon\in(0,1)$ , we define the set $B_{\epsilon}$ by

	$\displaystyle\text{FFNN : }B_{\epsilon}$	$\displaystyle=\{(x,x^{\prime})\in\mathbb{R}^{d}:c^{1}(x,x^{\prime})\leq 1-\epsilon\},$
	$\displaystyle\text{CNN : }B_{\epsilon}$	$\displaystyle=\{(x,x^{\prime})\in\mathbb{R}^{d}:\forall\alpha,\alpha^{\prime},c^{1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})\leq 1-\epsilon\}.$

We prove uniform convergence results on $B_{\epsilon}$ . Given a dataset $\mathcal{D}$ with inputs $\mathcal{X}$ , the existence of $\epsilon>0$ such that for all $x\neq x^{\prime}\in\mathcal{X},(x,x^{\prime})\in B_{\epsilon}$ is guaranteed provided that there is no collinearity between inputs in the dataset $\mathcal{D}$ .
In the next proposition, we prove that with a choice of $(\sigma_{b},\sigma_{w})$ in the ordered or chaotic phase, the infinite-width kernel $K^{L}$ converges to a constant kernel exponentially quickly in the limit of large depth.

Proposition 1 (NTK with Ordered/Chaotic Initialization).

Let $(\sigma_{b},\sigma_{w})$ be either in the ordered or in the chaotic phase. Then, there exist $\lambda>0$ such that for all $\epsilon\in(0,1)$ , there exists $\gamma>0$ such that

\sup_{(x,x^{\prime})\in B_{\epsilon}}|K^{L}(x,x^{\prime})-\lambda|\leq e^{-\gamma L}.

The proof of Proposition 1 is provided in Section 8.1.1. It relies on the asymptotic analysis of the second moment of the gradient.

Proposition 1 shows that off-diagonal terms of the NTK matrix $\hat{K}^{L}$ converge to a constant $\lambda>0$ as the depth grows when $(\sigma_{b},\sigma_{w})$ is chosen to be in the ordered or chaotic phases. The exponential convergence rate implies that even with a small number of layers, the kernel $K^{L}$ is close to being degenerate. This suggests that NTK training fails in this case, and the performance of the NTK regime solution will be no better than that of a random classifier. Empirically, we find that with depth $L=30$ , the NTK training fails when the network is initialized in the ordered phase (Section 5). However, this can be mitigated by using hyper-parameters $(\sigma_{b},\sigma_{w})$ in the EOC as we show in the next result. Before stating the results for the EOC initialization, we first introduce the following assumption on the input space of CNN.

Assumption 1.

For all $x,x^{\prime}\in\mathcal{X}$ , $q^{1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ is independent of $\alpha,\alpha^{\prime}$ .

Under Assumption 1, there exists some function $e:(x,x^{\prime})\mapsto e(x,x^{\prime})$ such that for all $\alpha,\alpha^{\prime}$ and $x,x^{\prime}\in\mathcal{X}$

\sum_{j}\sum_{\beta\in ker}x_{j,\alpha+\beta}x^{\prime}_{j,\alpha^{\prime}+\beta}=e(x,x^{\prime})

which combined with Proposition 2 implies that the NTK in the CNN architecture is the same as that in the FFNN architecture with $e(x,x^{\prime})$ replacing $x\cdot x^{\prime}$ . It is a constraint on the set of inputs $\mathcal{X}$ . Hereafter, for all CNN analysis, for some function $G$ and set $E$ , taking the supremum $\sup_{(x,x^{\prime})\in E}G(x,x^{\prime})$ should be interpreted as $\sup_{(x,x^{\prime})\in E\cap\mathcal{X}^{2}}G(x,x^{\prime})$ . In the following we will specify clearly whenever we use this assumption.

When we choose $(\sigma_{b},\sigma_{w})$ in the EOC, the next result shows that the NTK explodes in the limit of large depth. However, leveraging our remark on the scale invariance property of the NTK (see Eq. (9)), we show that a scaled version of the kernel converges at a polynomial rate to the degenerate kernel (this is better than the exponential rate in the Ordered/Chaotic phase).

Theorem 1 (NTK in the EOC).

Let $(\sigma_{b},\sigma_{w})\in\text{EOC}$ , $\tilde{K}^{L}=K^{L}/L$ , and $E\subset\mathbb{R}^{d}$ any compact set. We have that

\sup_{x\in E}|\tilde{K}^{L}(x,x)-\tilde{K}^{\infty}(x,x)|=\Theta(L^{-1}).

Moreover, there exists a constant $\lambda\in(0,1)$ such that for all $\epsilon\in(0,1)$

\sup_{(x,x^{\prime})\in B_{\epsilon}}\big|\tilde{K}^{L}(x,x^{\prime})-\tilde{K}^{\infty}(x,x^{\prime})\big|=\Theta(\log(L)L^{-1}),\quad\textup{where}

•

If $\phi(x)=\max(0,x)$ , i.e. the ReLU activation function, then $\tilde{K}^{\infty}(x,x^{\prime})=\frac{\sigma_{w}^{2}\|x\|~\|x^{\prime}\|}{d}(1-(1-\lambda)\mathbbm{1}_{x\neq x^{\prime}})$ with $\lambda=1/4$ .
•

If $\phi=\textrm{Tanh}(x)$ , i.e. the Hyperbolic Tangent activation function, then $\tilde{K}^{\infty}(x,x^{\prime})=q(1-(1-\lambda)\mathbbm{1}_{x\neq x^{\prime}})$ where $q>0$ is a constant and $\lambda=1/3$ .

All results hold for CNN under Assumption 1.

Theorem 1 is proved in Section 8.1.2. The proof requires a special form of inequalities to control the convergence rate (i.e. to obtain $\Theta$ instead of $\mathcal{O}$ ). Theorem 1 shows that the EOC initialization yields a polynomial convergence rate (w.r.t $L$ ) of $\tilde{K}^{L}$ to the trivial kernel $\tilde{K}^{\infty}$ . This is important knowing that $\tilde{K}^{\infty}$ is trivial and brings hardly any information on $x$ ⁴⁴ 4 Notice that the RKHS of $\tilde{K}^{\infty}$ is restricted to constant functions for Tanh and functions of the form $x\to\alpha\|x\|,\alpha\in\mathbb{R}$ , for ReLU.. Indeed, the convergence rate of $\tilde{K}^{L}$ to $\tilde{K}^{\infty}$ is $\Theta(\log(L)L^{-1})$ . This means that as $L$ grows, with a choice of $(\sigma_{b},\sigma_{w})$ in the EOC, the kernel $\tilde{K}$ is still much farther from the trivial kernel $\tilde{K}^{\infty}$ compared to the Ordered/Chaotic initialization. The EOC allows thus the use of NTK training on deeper networks. Empirical results in Section 5 confirm this theoretical findings. In the next section, we show how the network architecture can impact the behaviour of the infinite-width NTK in the large depth limit.

3.2 Residual Neural Networks (ResNet)

Another important feature of DNNs, which is known to be highly influential, is the network architecture. For residual networks (commonly known as ResNet), the NTK also follows a simple recursion expression in the infinite-width limit. Consider a ResNet of the form

y^{l}(x)=y^{l-1}(x)+\mathcal{F}(w^{l},y^{l-1}(x)),\quad l\geq 2,

(12)

where $\mathcal{F}$ is either a dense layer as in (10) or a convolutional layer as in (11)). The NTK recursion is given in the following lemma.

Lemma 0 (NTK of a ResNet with fully connected layers in the infinite-width limit).

Let $K^{res,1}$ be the exact NTK for the ResNet with 1 layer. Then
$\bullet$ For the first layer (without residual connections), we have for all $x,x^{\prime}\in\mathbb{R}^{d}$

K^{res,1}_{ii^{\prime}}(x,x^{\prime})=\delta_{ii^{\prime}}\left(\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{d}x\cdot x^{\prime}\right).

$\bullet$ For $l\geq 2$ , as $n_{1},n_{2},...,n_{l-1}\rightarrow\infty$ recursively, we have for all $i,i^{\prime}\in[n_{l}]$ , $K^{res,l}_{ii^{\prime}}=\delta_{ii^{\prime}}K^{l}_{res}$ , where $K^{l}_{res}$ is given by the recursive formula for all $x,x^{\prime}\in\mathbb{R}^{d}$

K_{res}^{l}(x,x^{\prime})=K_{res}^{l-1}(x,x^{\prime})(\dot{q}^{l}(x,x^{\prime})+1)+q^{l}(x,x^{\prime}).

Adding skip connections has a direct impact on the recursion of the infinite-width NTK; it explicitly adds a term $K_{res}^{l-1}$ to the recursion. A similar result holds for residual networks with convolutional layers.

Lemma 0 (NTK of a ResNet with convolutional layers in the infinite-width limit).

Let $K^{res,1}$ be the exact NTK for the ResNet with 1 layer. Then
$\bullet$ For the first layer (without residual connections), we have for all $x,x^{\prime}\in\mathbb{R}^{d}$

K^{res,1}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}\Big(\frac{\sigma_{w}^{2}}{n_{0}(2k+1)}[x,x^{\prime}]_{\alpha,\alpha^{\prime}}+\sigma_{b}^{2}\Big).

$\bullet$ For $l\geq 2$ , as $n_{1},n_{2},...,n_{l-1}\rightarrow\infty$ recursively, we have for all $i,i^{\prime}\in[n_{l}]$ , $\alpha,\alpha^{\prime}\in[0:M-1]$ , $K^{res,l}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}K^{res,l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ , where $K^{res,l}_{\alpha,\alpha^{\prime}}$ is given by the recursive formula for all $x,x^{\prime}\in\mathbb{R}^{d}$ , using the same notations as in lemma 2,

K^{res,l}_{\alpha,\alpha^{\prime}}=K^{res,l-1}_{\alpha,\alpha^{\prime}}+\frac{1}{2k+1}\sum_{\beta}\Psi^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta},

where $\Psi^{l}_{\alpha,\alpha^{\prime}}=\dot{q}^{l}_{\alpha,\alpha^{\prime}}K^{res,l}_{\alpha,\alpha^{\prime}}+\hat{q}^{l}_{\alpha,\alpha^{\prime}}$ .

The additional terms $K_{res}^{l-1}(x,x^{\prime})$ (resp. $K^{res,l-1}_{\alpha,\alpha^{\prime}}$ ) in the recursive formulas of Lemma 3 (resp. Lemma 4) appear as a result of the skip connections in the ResNet architecture. It turns out that this term helps in slowing down the convergence rate of the NTK. The next proposition shows that for any $\sigma_{w}>0$ ⁵⁵ 5 We omit the bias in the ResNet architecture for the sake of simplification., the infinite-width NTK of a ResNet explodes (exponentially) as $L$ grows. However, a normalized version $\bar{K}^{L}=K^{L}/\alpha_{L}$ of the NTK of a ResNet will always have a polynomial convergence rate to a limiting trivial kernel. Recall that the NTK regime is scale-invariant (Eq. (9)), i.e. the scaling factor $\alpha_{L}$ does not change this regime.

Theorem 2 (NTK for ResNet).

Consider a ResNet satisfying

y^{l}(x)=y^{l-1}(x)+\mathcal{F}(w^{l},y^{l-1}(x)),\quad l\geq 2,

(13)

where $\mathcal{F}$ is either a convolutional or dense layer (Eqs. (10) and (11)) with ReLU activation. Let $K^{L}_{res}$ be the corresponding NTK, and $\bar{K}^{L}_{res}=K^{L}_{res}/\alpha_{L}$ (Normalized NTK) with $\alpha_{L}=L(1+\frac{\sigma_{w}^{2}}{2})^{L-1}$ . Then, for all compact sets $E\subset\mathbb{R}^{d}$ , we have

\sup_{x\in E}|\bar{K}^{L}_{res}(x,x)-\bar{K}^{\infty}_{res}(x,x)|=\Theta(L^{-1}).

Moreover, there exists a constant $\lambda\in(0,1)$ such that for all $\epsilon\in(0,1)$

\sup_{x,x^{\prime}\in B_{\epsilon}}\big|\bar{K}^{L}_{res}(x,x^{\prime})-\bar{K}^{\infty}_{res}(x,x^{\prime})\big|=\Theta(\log(L)L^{-1}),

where $\bar{K}^{\infty}_{res}(x,x^{\prime})=\frac{\sigma_{w}^{2}\|x\|~\|x^{\prime}\|}{d}(1-(1-\lambda)\mathbbm{1}_{x\neq x^{\prime}})$ .
All results hold for ResNet with Convolutional layers under Assumption 1.

The proof techniques of Theorem 2 are similar to that of Theorem 1. Details are provided in Section 8.
Theorem 2 shows that the NTK of a ReLU ResNet explodes exponentially w.r.t $L$ . However, the normalized kernel $\bar{K}^{L}_{res}=K^{L}_{res}(x,x^{\prime})/\alpha_{L}$ converges to a limiting kernel $\bar{K}^{\infty}_{res}$ at the exact polynomial rate $\Theta(\log(L)L^{-1})$ for all $\sigma_{w}>0$ . This allows for NTK training of deep ResNet, similarly to the EOC initialization for the FFNN or the CNN networks. However, $\bar{K}^{L}_{res}$ converges to a trivial kernel. Thus, NTK training will fail at some point as we increase the depth. This is empirically verified in Section 5.

3.3 Spectral decomposition of the limiting NTK

To refine the analysis presented in Section 3, we study the limiting behaviour of the spectrum of the kernels studied in Theorems 1, 2 and Proposition 1, on the unit sphere $\mathbb{S}^{d-1}=\{x\in\mathbb{R}^{d}:\|x\|_{2}=1\}$ . On the sphere $\mathbb{S}^{d-1}$ , all of these kernels (namely $K^{L}$ for FFNN in the Ordered/Chaotic phase, $\tilde{K}^{L}$ for FFNN⁶⁶ 6 The NTK for CNN is generally not a dot-product kernel since it depends on the quantities $[x,x^{\prime}]_{\alpha,\alpha^{\prime}}$ . We restrict our analysis to FFNN and ResNet with fully-connected layers. in the EOC, and $\bar{K}_{res}^{L}$ for ResNets with fully-connected layers) are dot-product kernels, i.e. for any of these kernels, denoted by $\kappa_{L}$ , there exists a function $g_{L}$ such that $\kappa^{L}(x,x^{\prime})=g_{L}(x\cdot x^{\prime})$ for all $x,x^{\prime}\in\mathbb{S}^{d-1}$ . This type of kernels is known to be diagonalizable on the sphere $\mathbb{S}^{d-1}$ and its eigenfunctions are the so-called Spherical Harmonics of $\mathbb{S}^{d-1}$ . This diagonalization result has been independently observed in other works (Geifman et al. 2020; Cao et al. 2021; Bietti and Bach 2021). In the next proposition, we leverage the results of Section 3 to study the aforementioned kernels from a spectral perspective.

Proposition 2 (Spectral decomposition on $\mathbb{S}^{d-1}$ ).

Let $\kappa^{L}$ be either, $K^{L}$ for an FFNN with $L$ layers initialized in the Ordered phase (Proposition 1), $\tilde{K}^{L}$ for an FFNN with $L$ layers initialized in the EOC (Theorem 1), or $\bar{K}^{L}_{res}$ for a ResNet with $L$ Fully Connected layers (Theorem 2). Then, for all $L\geq 1$ , there exists $(\mu^{L}_{k})_{k\geq}$ such that for all $x,x^{\prime}\in\mathbb{S}^{d-1}$

\kappa^{L}(x,x^{\prime})=\sum_{k\geq 0}\mu^{L}_{k}\sum_{j=1}^{N(d,k)}Y_{k,j}(x)Y_{k,j}(x^{\prime}).

$(Y_{k,j})_{k\geq 0,j\in[1:N(d,k)]}$ are spherical harmonics of $\mathbb{S}^{d-1}$ , and $N(d,k)$ is the number of harmonics of order $k$ .

Moreover, we have that $0<\mu^{\infty}_{0}=\lim\limits_{L\rightarrow\infty}\mu^{L}_{0}<\infty$ , and for all $k\geq 1,$ $\lim\limits_{L\rightarrow\infty}\mu^{L}_{k}=0$ .

The proof of Proposition 2 is based on a result from spectral theory analysis. The limiting eigenvalues are obtained by a simple application of the dominated convergence theorem.
Proposition 2 shows that in the limit of large depth $L$ , the kernel $\kappa^{L}$ becomes close to the rank-one kernel $\kappa^{\infty}$ $(x,x^{\prime})\mapsto\mu^{\infty}_{0}Y_{0}(x)Y_{0}(x^{\prime})$ , where $Y_{0}$ is a function (constant function for Tanh and $x\to\|x\|$ for ReLU). Therefore, in the limit of infinite depth, the RKHS of the kernel $\kappa^{L}$ is reduced to the space spanned by $Y_{0}$ , confirming that the NTK regime solution is trivial in this limit (recall that $f_{\infty}-f_{0}$ is in the RKHS of $\kappa_{L}$ ), hence, NTK training fails.

3.4 Scaled ResNet

A natural extension of the ResNet architecture is the introduction of scaling factors for the blocks of the residual branches. In this section, we study the impact of a particular scaling scheme and show that this simple procedure can significantly reduce the convergence rate to the infinite depth trivial NTK regime.

Theorem 3 (Scaled ResNet).

Consider a ResNet satisfying

y^{l}(x)=y^{l-1}(x)+\frac{1}{\sqrt{l}}\mathcal{F}(w^{l},y^{l-1}(x)),\quad l\geq 2,

(14)

where $\mathcal{F}$ is either a convolutional or dense layer (eq. (10) and eq. (11)) with ReLU activation. Then the results of Theorem 2 apply with $\alpha_{L}=L^{1+\sigma_{w}^{2}/2}$ and the convergence rate becomes $\Theta(\log(L)^{-1})$ .

Theorem 3 shows that scaling the residual blocks by $1/\sqrt{l}$ has two important effects on the kernel $K^{L}$ : first, it stabilizes the NTK which only grows as $L^{1+\frac{\sigma_{w}^{2}}{2}}$ instead of $L(1+\frac{\sigma_{w}^{2}}{2})^{L-1}$ ; second, it drastically slows down the convergence rate to the limiting (trivial) $\bar{K}^{\infty}_{res}$ . Both properties are highly desirable for NTK training. The second property in particular means that with this scaling, the RKHS of $K^{L}/\alpha_{L}$ is ‘richer’ compared to the non-scaled case. We show in Section 5 a case where NTK training with scaled ResNet succeeds to achieve non-trivial performance while the non-scaled NTK regime fails.

Refer to caption — Figure 1: Train/Test accuracy of an FFNN with ReLU activation on Fashion MNIST dataset for different depths and learning rates, trained with SGD for 10 epochs. The plot is in log-log scale.

A similar scaling was studied in Huang et al. 2020, where authors scale the blocks with $1/L$ instead of our scaling $1/\sqrt{l}$ , and show that it also stabilizes the NTK of ResNet. It is also possible to force the NTK regime to remain ‘expressive’, i.e. non-trivial, in the infinite depth regime by using more aggressive scaling factors (Hayou et al. 2021).

4 Learning Rate Passband

Tuning the learning rate (LR) is crucial for the training of DNNs with SGD; a large/small LR could cause the training to fail. Empirically, the optimal LR tends to decrease as the network depth grows. In this section, we use the NTK linear model presented in Section 2 to establish the existence of an LR passband, i.e. an interval of values for the LR where training occurs. The idea is to use the infinite-width NTK to approximate the largest eigenvalue of the exact NTK (finite-width NTK) which governs gradient updates. Recall the dynamics of the linear model in the infinite-width limit

df_{t}(\mathcal{X})=-\frac{1}{N}\hat{K}^{L}(f_{t}(\mathcal{X})-\mathcal{Z})dt.

(15)

The GD update with learning rate $\eta$ is given by

f_{t+1}(\mathcal{X})=(I-\frac{\eta}{N}\hat{K}^{L})f_{t}(\mathcal{X})-\frac{\eta}{N}\hat{K}^{L}\mathcal{Z}.

(16)

To ensure stability in Eq. (16), a necessary condition is that $\|I-\frac{\eta}{N}\hat{K}^{L}\|_{F}<1$ , which implies having

\eta<\frac{2}{\mu_{\max}(\frac{1}{N}\hat{K}^{L})}

where $\mu_{\max}$ refers to the largest eigenvalue.
Consider the case of an FFNN with Tanh activation for instance, initialized in the EOC. Then, as $L$ grows we have that $\hat{K}^{L}=qL((1-\lambda)I+\lambda U)+\mathcal{O}(\log(L))$ (Theorem 1). Therefore, for large $L$ and $N$ , we have that $\mu_{\max}(\frac{1}{N}\hat{K}^{L})\sim q\lambda L$ .
The upper bound on $\eta$ scales as $1/L$ , therefore, we expect the passband to have a linear upper bound when we plot $\log(LR)$ vs $\log(L)$ . To validate this hypothesis, we train an FFNN on Fashion-MNIST dataset. Figure 1 shows the train/test accuracy for a grid of LRs and depths. The slope of the red line is $-1$ which confirms our prediction that the upper bound of the LR passband grows as $L^{-1}$ . A similar bound has been introduced recently in Hayase and Karakida 2021 in the different context of networks achieving dynamical isometry with Hard-Tan activation function. Figure 1 also shows that the lower bound of the passband and depths are almost uncorrelated.⁷⁷ 7 We currently do not have an explanation for this effect.

5 Experiments

5.1 Behaviour of $K^{L}$ as $L$ goes to infinity

Proposition 1, and Theorems 1 and 2 show that the NTK (or scaled NTK) converges to a trivial kernel. Figure 2 shows the normalized eigenvalues of the NTK of an FFNN on 2D sphere. In the Ordered phase, the eigenvalues converge quickly to zero as the depth grows, while with an EOC initialization, the eigenvalues converge to zero at a slower rate. For $L=300$ , the NTK in the EOC is ‘richer’ than the NTK in the Ordered phase, in the sense that the small eigenvalues with EOC are relatively much bigger than those with the Ordered phase intialization. This reflects directly on the RKHS of the NTK, and allows the NTK regime solution to be more expressive since it is a linear combination of the eigenfunctions of the NTK.

5.2 Can NTK regime explain DNN performance?

We train FFNN, Vanilla CNN (stacked convolutional layers without pooling, followed by a dense layer), Vanilla ResNet (ResNet with FFNN blocks) with different depths using two training methods:

Table 2: Test accuracy for varying architectures and depths on MNIST and CIFAR10 dataset. Test accuracy is reported after 100 training epochs for

L\in\{3,30\}

and

160

epochs for

L=300

	MNIST				CIFAR10
	NTK Training		SGD Training		NTK Training		SGD Training
	EOC	Ordered	EOC	Ordered	EOC	Ordered	EOC	Ordered
L=3
FFNN-ReLU	$96.64_{\pm 0.11}$	$96.57_{\pm 0.12}$	$97.05_{\pm 0.27}$	$97.11_{\pm 0.31}$	$48.13_{\pm 0.10}$	$48.45_{\pm 0.14}$	$55.13_{\pm 0.23}$	$54.10_{\pm 0.12}$
FFNN-Tanh	$95.34_{\pm 1.04}$	$96.32_{\pm 0.41}$	$97.19_{\pm 0.11}$	$97.03_{\pm 0.29}$	$48.32_{\pm 0.15}$	$48.10_{\pm 0.10}$	$56.13_{\pm 0.34}$	$54.10_{\pm 0.23}$
CNN-ReLU	$97.13_{\pm 0.31}$	$97.23_{\pm 0.22}$	$98.95_{\pm 0.12}$	$98.89_{\pm 0.18}$	$49.11_{\pm 0.16}$	$42.76_{\pm 3.32}$	$60.23_{\pm 0.45}$	$59.05_{\pm 0.15}$
V-ResNet	$96.73_{\pm 0.05}$	$96.71_{\pm 0.16}$	$97.19_{\pm 0.23}$	$97.12_{\pm 0.14}$	$47.82_{\pm 0.73}$	$48.01_{\pm 0.20}$	$54.40_{\pm 0.24}$	$54.28_{\pm 0.33}$
L=30
FFNN-ReLU	$96.95_{\pm 0.22}$	—	$97.55_{\pm 0.09}$	—	$48.32_{\pm 0.10}$	—	$56.10_{\pm 0.41}$	—
FFNN-Tanh	$97.30_{\pm 0.15}$	—	$97.87_{\pm 0.17}$	—	$48.40_{\pm 0.12}$	—	$57.39_{\pm 0.08}$	—
CNN-ReLU	$98.60_{\pm 0.13}$	—	$99.02_{\pm 0.07}$	—	$48.42_{\pm 0.10}$	—	$75.39_{\pm 0.31}$	—
V-ResNet	—	—	$98.17_{\pm 0.03}$	$98.13_{\pm 0.08}$	—	—	$57.09_{\pm 0.47}$	$58.13_{\pm 0.18}$
L=300
FFNN-ReLU	—	—	$98.14_{\pm 0.12}$	—	—	—	$30.25_{\pm 3.23}$	—
FFNN-Tanh	—	—	$98.54_{\pm 0.18}$	—	—	—	$58.25_{\pm 0.43}$	—
CNN-ReLU	—	—	$99.43_{\pm 0.04}$	—	—	—	$76.25_{\pm 0.21}$	—
V-ResNet	—	—	$98.23_{\pm 0.09}$	$98.19_{\pm 0.06}$	—	—	$58.87_{\pm 0.44}$	$59.25_{\pm 0.10}$
S-ResNet	$97.10_{\pm 0.13}$	$97.15_{\pm 0.10}$	$98.57_{\pm 0.06}$	$98.76_{\pm 0.8}$	$46.77_{\pm 0.19}$	$47.13_{\pm 0.10}$	$59.14_{\pm 0.37}$	$59.91_{\pm 0.51}$

SGD training.

We use SGD with a batchsize of 128 and a learning rate $10^{-1}$ for $L\in\{3,30\}$ and $10^{-2}$ for $L=300$ (this learning rate was found by a grid search of exponential step size 10; note that the optimal learning rate with NTK parameterization is usually bigger than the optimal learning rate with standard parameterization). We use $100$ training epochs for $L\in\{3,30\}$ , and $150$ epochs for $L=300$ , with 1 Tesla v100 GPU for all our experiments, which ran for (approximately) 2 weeks.

NTK training.

We use the Python library Neural-Tangents introduced by Novak et al. 2020 with $10K$ samples from MNIST/CIFAR10⁸⁸ 8 CIFAR10: https://www.cs.toronto.edu/~kriz/cifar.html
MNIST: http://yann.lecun.com/exdb/mnist/. This corresponds to the inversion of a $10K\times 10K$ matrix to obtain the NTK regime solution discussed in Section 2.

For the EOC initialization, we use $(\sigma_{b},\sigma_{w})=(0,\sqrt{2})$ for ReLU, and $(\sigma_{b},\sigma_{w})=(0.2,1.298)$ for Tanh. For the Ordered phase initialization, we use $(\sigma_{b},\sigma_{w})=(1,0.1)$ for both ReLU and Tanh (We use the algorithm presented in Hayou et al. 2019a to compute EOC values). Table 2 displays the test accuracies for both NTK training and SGD training. The dashed lines refer to the trivial test accuracy $\sim 10\%$ , which is the test accuracy of a uniform random classifier with 10 classes i.e. in these cases the model does not learn. For $L=300$ , NTK training fails for all architectures and initializations confirming the results of Theorems 1 and 2, and Proposition 1; while SGD succeeds in training FFNN and CNN with an EOC initialization and fails with an Ordered initialization, and succeeds in training ResNet with both initialization schemes (which confirms findings in Yang and Schoenholz 2017 that ResNet ‘live’ in the EOC). This shows that the NTK regime cannot explain DNN performance trained with SGD. We also run experiments with a scaled ResNet (S-ResNet) architecture and report the results for depth $L=300$ . S-ResNet is NTK-trainable even with depth $L=300$ , which is not the case with standard ResNet. Further results on the performance of scaled ResNet with SGD are provided in the next section.

5.3 Does Scaled ResNet outperform ResNet with SGD?

Theorem 3 shows that scaled ResNet is better than standard ResNet in preserving the expressivity of NTK as the depth grows. However, it is not clear whether this scaling has an impact on the performance of the ResNet trained with SGD. This section provides an empirical invistigation of this question.

Table 3: Test accuracy on CIFAR100 for ResNet.

		Epoch 10	Epoch 160
ResNet32	standard	54.18 $\pm$ 1.21	72.49 $\pm$ 0.18
ResNet32	scaled	53.89 $\pm$ 2.32	74.07 $\pm$ 0.22
ResNet50	standard	51.09 $\pm$ 1.73	73.63 $\pm$ 1.51
ResNet50	scaled	55.39 $\pm$ 1.52	75.02 $\pm$ 0.44
ResNet104	standard	47.02 $\pm$ 3.23	74.77 $\pm$ 0.29
ResNet104	scaled	56.38 $\pm$ 2.54	76.14 $\pm$ 0.98

We train standard and scaled ResNets with depths 32, 50, and 104 on CIFAR100 with SGD. We use a decaying learning rate schedule; we start with 0.1 and divide by 10 after $n_{e}/2$ epochs, where $n_{e}$ is the total number of epochs; we scale again, by 10, after $n_{e}/4$ epochs. We use a batch size of 128, and we train the model for 160 epochs. Table 3 displays test accuracy for standard ResNet and scaled ResNet after 10 and 160 epochs of SGD training; Scaled ResNet outperforms ResNet and converges faster. However, it is not clear whether this is linked to the NTK, or caused by something else. The impact of scaling ResNet blocks is well understood in the NTK regime but remains an open question in the feature learning regime (the regime where the NTK changes with training time) which occurs with SGD training.

6 Conclusion and Limitations

In this paper, we have shown that the infinite depth limit of the NTK regime is trivial and cannot explain the performance of DNNs. However, the convergence occurs with hyper-parameters dependent rate, which is has a direct impact on the empirical performance (Table 2). These findings add to a recent line of research which shows that the infinite-width approximation of the NTK does not fully capture the training dynamics of DNNs. Indeed, recent works have shown that the NTK for finite width neural networks changes with time (Chizat and Bach 2019; Ghorbani et al. 2021; Huang and Yau 2020). Hanin and Nica 2020 showed that it can even be random in the limit $n,L\rightarrow\infty$ (where $n$ is a width of the network) with fixed ratio $\gamma=\frac{L}{n}$ . An interesting property in this regime is the “feature learning” which the NTK regime lacks. Further research is needed in order to understand the difference between the two regimes.

7 Proof techniques

The techniques used in the proofs range from simple algebraic manipulation to more specialized inequalities. A summary of the key ideas is given below.

Lemmas 1, 2, 3, 4.

The proofs of these lemmas are simple and follow the same inductive argument as in the proof of the original NTK result in Jacot et al. 2018. Note that these results can also be obtained using results from Yang 2020.

Proposition 1, Theorems 1, 2, 3.

The proof of these results follow two steps; firstly, we derive the asymptotic behaviour of the NTK in the limit of large depth $L$ ; secondly, we control this asymptotics using uniform upper/lower bounds. We analyse the asymptotic behaviour of the NTK of FFNN using existing results on signal propagation in deep FFNN. For CNNs, the dynamics are more complicated as they involve convolution operators. We use some results from the theory of Circulant Matrices for this purpose. The use of Assumption 1 also simplifies the analysis for CNNs with $(\sigma_{b},\sigma_{w})$ chosen in the EOC.
It is relatively easy to control the dynamics of the NTK in the Ordered/Chaotic phase. However, these dynamics become much more sophisticated when the network is initialized in the EOC; technical lemmas which we call Appendix Lemmas are introduced for this purpose. A key ingredient in the proofs of Theorems 1, 2, and 3, is the following lemma, which we state and prove in the appendix.

Lemma. [Uniform bounds] Let $A\subset\mathbb{R}$ be a compact set and $g$ a non-decreasing function on $A$ . Define the sequence $\zeta_{l}$ by $\zeta_{l}=g(\zeta_{l-1})$ and $\zeta_{0}\in A$ . Assume that there exist $\alpha_{l},\beta_{l}$ that do not depend on $\zeta_{0}$ (in the sense that sequences $\alpha_{l},\beta_{l}$ are the same for all $\zeta_{0}\in A$ ), with $\beta_{l}=o(\alpha_{l})$ , such that for all $\zeta_{0}\in A$ ,

\zeta_{l}=\alpha_{l}+\mathcal{O}_{\zeta_{0}}(\beta_{l})

where $\mathcal{O}_{\zeta_{0}}$ means that the $\mathcal{O}$ bound depends on $\zeta_{0}$ . Then, we have that

\sup_{\zeta_{0}\in A}|\zeta_{l}-\alpha_{l}|=\mathcal{O}(\beta_{l}),

i.e. we can choose the bound $\mathcal{O}$ to be independent of $\zeta_{0}$ .

Proposition 2.

The spectral decomposition of zonal kernels on the sphere is a classical result in spectral theory which was recently applied to NTK (Geifman et al. 2020; Cao et al. 2021; Bietti and Mairal 2019). In order to prove the convergence of the eigenvalues, we use the Dominated Convergence theorem, leveraging the asymptotic results in Proposition 1 and Theorems 1, 2.

8 Proofs

In this section, we provide proofs for the main results. We use several technical lemmas which we state and prove in the appendix. To distinguish between lemmas in the main text and those in the appendix, we call the later Appendix Lemmas. We refer to some results in the Appendix by the name ‘Fact’. These are simple results that have appeared (or are similar to) in previous works.

8.1 Proofs on the limiting NTK: 1, Theorems 1, 2 and 3

In this section we prove the four theorems describing the limiting behaviour of $K^{L}$ or scaled versions of it.

8.1.1 Proof of 1: NTK in the ordered/chaotic phase

We prove the result for an FFNN architecture. The proof easily extends to a CNN architecture under 1, using Appendix Lemmas 7 and 8.

Let $x,x^{\prime}\in\mathbb{R}^{d}$ be two inputs. From lemma 1, we have that

K^{l}(x,x^{\prime})=K^{l-1}(x,x^{\prime})\dot{q}^{l}(x,x^{\prime})+q^{l}(x,x^{\prime})

where $q^{1}(x,x^{\prime})=\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{d}x^{T}x^{\prime}$ and $q^{l}(x,x^{\prime})=\sigma_{b}^{2}+\sigma_{w}^{2}\mathbb{E}_{f\sim\mathcal{N}(0,q^{l-1})}[\phi(f(x))\phi(f(x^{\prime}))]$ and $\dot{q}^{l}(x,x^{\prime})=\sigma_{w}^{2}\mathbb{E}_{f\sim\mathcal{N}(0,q^{l-1})}[\phi^{\prime}(f(x))\phi^{\prime}(f(x^{\prime}))]$ . From facts 1, 2, 4, 9, and 17 in the appendix, in the ordered/chaotic phase, there exist $k,\beta,\eta,l_{0}>0$ and $\alpha\in(0,1)$ such that for all $l\geq l_{0}$ we have

\sup_{(x,x^{\prime})\in B_{\epsilon}}|q^{l}(x,x^{\prime})-k|\leq e^{-\beta l},\quad\text{and}\quad\sup_{(x,x^{\prime})\in B_{\epsilon}}|\dot{q}^{l}(x,x^{\prime})-\alpha|\leq e^{-\eta l}.

Therefore, there exists $M>0$ such that for any $l\geq l_{0}$ and $x,x^{\prime}\in\mathbb{R}^{d}$

K^{l}(x,x^{\prime})\leq M.

Letting $r_{l}=\sup_{(x,x^{\prime})\in B_{\epsilon}}|K^{l}(x,x^{\prime})-\frac{k}{1-\alpha}|$ , we have

r_{l}\leq\alpha r_{l-1}+Me^{-\eta l}+e^{-\beta l}.

We conclude using Appendix Lemma 2.

8.1.2 Proof of Theorem 1 : FFNN and CNN in the EOC

We prove the results for an FFNN architecture. In the case of a CNN architecture, under 1, the NTK of a CNN is the same as that of an FFNN. Therefore, the results on the NTK of FFNN are all valid to the NTK of CNN $K^{l}_{\alpha,\alpha^{\prime}}$ for any $\alpha,\alpha^{\prime}$ .

Let $\epsilon\in(0,1)$ , $E\subset\mathbb{R}^{d}$ , $(\sigma_{b},\sigma_{w})\in$ EOC, and $x,x^{\prime}\in\mathbb{R}^{d}$ . Recall that $c^{l}(x,x^{\prime})=\frac{q^{l}(x,x^{\prime})}{\sqrt{q^{l}(x,x)q^{l}(x^{\prime},x^{\prime})}}$ . Let $\gamma_{l}:=1-c^{l}(x,x^{\prime})$ and $f$ be the correlation function defined by the recursive equation $c^{l+1}=f(c^{l})$ (See appendix 0.2). By definition, we have that $\dot{q}^{l}(x,x)=f^{\prime}(c^{l-1}(x,x^{\prime}))$ . Let us first prove the result for ReLU.

•

$\phi=$ ReLU: From fact 11 in the appendix, we know that, when choosing the hyper-parameters $(\sigma_{w},\sigma_{b})$ in the EOC for ReLU, the variance $q^{l}(x,x)$ is constant w.r.t $l$ and is given by $q^{l}(x,x)=q^{1}(x,x)=\frac{\sigma_{w}^{2}}{d}||x||^{2}$ . Moreover, from fact 16, we have that $\dot{q}^{l}(x,x)=1$ . Therefore

K^{l}(x,x)=K^{l-1}(x,x)+\frac{\sigma_{w}^{2}}{d}||x||^{2}=l\frac{\sigma_{w}^{2}}{d}||x||^{2}=l\tilde{K}^{\infty}(x,x)

which concludes the proof for $K^{L}(x,x)$ . Note that the results is ’exact’ for ReLU, which means the upper bound $\mathcal{O}(L^{-1})$ is valid but not optimal in this case. However, we will see that this bound is optimal for Tanh.

From Appendix Lemma 5, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|c^{l}(x,x^{\prime})-1+\frac{\kappa}{l^{2}}-\kappa^{\prime}\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

and

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|f^{\prime}(c^{l}(x,x^{\prime}))-1+\frac{3}{l}-\kappa^{\prime\prime}\frac{\log(l)}{l^{2}}\right|=\mathcal{O}(l^{-2}).

Using Appendix Lemma 4 with $a_{l}=K^{l+1}(x,x^{\prime}),b_{l}=q^{l+1}(x,x^{\prime}),\lambda_{l}=f^{\prime}(c^{l}(x,x^{\prime}))$ , we conclude that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|\frac{K^{l+1}(x,x^{\prime})}{l}-\frac{1}{4}\frac{\sigma_{w}^{2}}{d}\|x\|\|x^{\prime}\|\right|=\Theta(\log(l)l^{-1}).

Using the compactness of $B_{\epsilon}$ , we conclude that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|\frac{K^{l}(x,x^{\prime})}{l}-\frac{1}{4}\frac{\sigma_{w}^{2}}{d}\|x\|\|x^{\prime}\|\right|=\Theta(\log(l)l^{-1}).

•

$\phi=Tanh$ : The proof in the case of Tanh is slightly different from that of ReLU. We use different technical lemmas to conclude.

From Appendix Lemma 6, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|c^{l}(x,x^{\prime})-1+\frac{\kappa}{l}-\kappa(1-\kappa^{2}\zeta)\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

where $\kappa=\frac{2}{f^{\prime\prime}(1)}>0$ and $\zeta=\frac{f^{3}(1)}{6}>0$ . Moreover, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|f^{\prime}(c^{l}(x,x^{\prime}))-1+\frac{2}{l}-2(1-\kappa^{2}\zeta)\frac{\log(l)}{l^{2}}\right|=\mathcal{O}(l^{-2}).

We conclude in the same way as in the case of ReLU using Appendix Lemma 4. The only difference is that, in this case, the limit of the sequence $b_{l}=q^{l+1}(x,x^{\prime})$ is the limiting variance $q$ (from facts 3, 1) does not depend on $(x,x^{\prime})$ .

8.1.3 Proof of Theorem 2: NTK for ResNET

Similarly to the previous theorem, we prove the result for a ResNet architecture with fully-connected layers and we use 1 so that the dynamics of the correlation and NTK are exactly the same for FFNN, hence all results on FFNN apply to CNN.

Let $\epsilon\in(0,1)$ , $E\subset\mathbb{R}^{d}$ , and $x,x^{\prime}\in\mathbb{R}^{d}$ . We first prove the result for the diagonal terms $K^{L}_{res}(x,x)$ , we deal afterwards with off-diagonal terms $K^{L}_{res}(x,x^{\prime})$ .

•

Diagonal terms: from fact 12, we have that $\dot{q}^{l}(x,x)=\frac{\sigma_{w}^{2}}{2}f(1)=\frac{\sigma_{w}^{2}}{2}$ . Moreover, it is easy to see that the variance terms for a ResNet follow the recursive formula $q^{l}(x,x)=q^{l-1}(x,x)+\sigma_{w}^{2}/2\times q^{l-1}(x,x)$ , hence

$q^{l}(x,x)=(1+\sigma_{w}^{2}/2)^{l-1}\frac{\sigma_{w}^{2}}{d}\|x\|^{2}.$ (17)

Recall that the recursive formula of NTK of a ResNet with fully-connected layers is given by (Appendix Lemma 3)

$K_{res}^{l}(x,x^{\prime})=K_{res}^{l-1}(x,x^{\prime})(\dot{q}^{l}(x,x^{\prime})+1)+q^{l}(x,x^{\prime}).$

Hence, for the diagonal terms we obtain

$K_{res}^{l}(x,x)=K_{res}^{l-1}(x,x)\left(\frac{\sigma_{w}^{2}}{2}+1\right)+q^{l}(x,x).$

Letting $\hat{K}_{res}^{l}=K_{res}^{l}/\left(1+\frac{\sigma_{w}^{2}}{l}\right)^{l-1}$ yields

$\hat{K}_{res}^{l}(x,x)=\hat{K}_{res}^{l-1}(x,x)+\frac{\sigma_{w}^{2}}{d}\|x\|^{2}.$

Therefore, $\bar{K}_{res}^{l}(x,x)=\frac{\hat{K}_{res}^{1}(x,x)}{l}+\left(1-1/l\right)\frac{\sigma_{w}^{2}}{d}\|x\|^{2}$ , the conclusion is straightforward since $E$ is compact and $\hat{K}_{res}^{1}(x,x)$ is continuous which implies that it is uniformly bounded on $E$ .

•

Off-diagonal terms: the argument is similar to that of Theorem 1 with few key differences. From Appendix Lemma 9 we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|c^{l}(x,x^{\prime})-1+\frac{\kappa_{\sigma_{w}}}{l^{2}}-\kappa_{\sigma_{w}}^{\prime}\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

where $\kappa_{\sigma_{w}},\kappa_{\sigma_{w}}^{\prime}>0$ . Moreover, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|f^{\prime}(c^{l}(x,x^{\prime}))-1+\frac{3(1+\frac{2}{\sigma_{w}^{2}})}{l}-\kappa_{\sigma_{w}}^{\prime\prime}\frac{\log(l)}{l^{2}}\right|=\mathcal{O}(l^{-2}).

Let $\alpha=\frac{\sigma_{w}^{2}}{2}$ . We also have $\dot{q}^{l+1}(x,x^{\prime})=\alpha f^{\prime}(c^{l}(x,x^{\prime}))$ where $f$ is the ReLU correlation function given in fact 12. It follows that for all $(x,x^{\prime})\in B_{\epsilon}$

1+\dot{q}^{l+1}(x,x^{\prime})=(1+\alpha)(1-3l^{-1}+\zeta\frac{\log(l)}{l^{2}}+\mathcal{O}(l^{-3}))

for some constant $\zeta\neq 0$ that does not depend on $x,x^{\prime}$ . The bound $\mathcal{O}$ does not depend on $x,x^{\prime}$ either. Now let $a_{l}=\frac{K^{l+1}_{res}(x,x^{\prime})}{(1+\alpha)^{l}}$ . Using the recursive formula of the NTK, we obtain

a_{l}=\lambda_{l}a_{l-1}+b_{l}

where $\lambda_{l}=1-3l^{-1}+\zeta\frac{\log(l)}{l^{2}}+\mathcal{O}(l^{-3})$ , $b_{l}=\frac{\sigma_{w}^{2}}{d}\sqrt{\|x\|\|x^{\prime}\|}f(c^{l}(x,x^{\prime}))=q(x,x^{\prime})+\mathcal{O}(l^{-2})$ with $q(x,x^{\prime})=\frac{\sigma_{w}^{2}}{d}\sqrt{\|x\|\|x^{\prime}\|}$ and where we used the fact that $c^{l}(x,x^{\prime})=1+\mathcal{O}(l^{-2})$ (Appendix Lemma 5) and the formula for ResNet variance terms given by Eq. (17). Observe that all bounds $\mathcal{O}$ are independent from the inputs $(x,x^{\prime})$ . Therefore, using Appendix Lemma 4, we have

\sup_{x,x^{\prime}\in B_{\epsilon}}\big|K^{L+1}_{res}(x,x^{\prime})/L(1+\alpha)^{L}-\bar{K}^{\infty}_{res}(x,x^{\prime})\big|=\Theta(L^{-1}\log(L)),

which can also be written as

\sup_{x,x^{\prime}\in B_{\epsilon}}\big|K^{L}_{res}(x,x^{\prime})/(L-1)(1+\alpha)^{L-1}-\bar{K}^{\infty}_{res}(x,x^{\prime})\big|=\Theta(L^{-1}\log(L)),

We conclude by observing that $K^{L}_{res}(x,x^{\prime})/(L-1)(1+\alpha)^{L-1}=K^{L}_{res}(x,x^{\prime})/L(1+\alpha)^{L-1}+\mathcal{O}(L^{-1})$ where $\mathcal{O}$ can be chosen to depend only on $\epsilon$ .

8.1.4 Proof of Theorem 3: NTK for Scaled ResNet

We use the same techniques as in the non-scaled case. Let us prove the result for fully connected layers, the proof for convolutional layers follows the same analysis.

Let $\epsilon\in(0,1)$ and $x,x^{\prime}\in B_{\epsilon}$ be two inputs. We first prove the result for the diagonal term $K^{L}_{res}(x,x)$ then $K^{L}_{res}(x,x^{\prime})$ .

•

We have that $\dot{q}^{l}(x,x)=\frac{\sigma_{w}^{2}}{2l}f(1)=\frac{\sigma_{w}^{2}}{2l}$ . Moreover, we have $q^{l}(x,x)=q^{l-1}(x,x)+\sigma_{w}^{2}/2l\times q^{l-1}(x,x)=\left[\prod_{k=1}^{l}(1+\sigma_{w}^{2}/2k)\right]\frac{\sigma_{w}^{2}}{d}\|x\|^{2}$ . Recall that

$K_{res}^{l}(x,x)=K_{res}^{l-1}(x,x)(1+\frac{\sigma_{w}^{2}}{2l})+q^{l}(x,x)$

letting $k_{l}^{\prime}=\frac{K_{res}^{l}(x,x)}{\prod_{k=1}^{l}(1+\sigma_{w}^{2}/2k)}$ , we obtain

$k_{l}^{\prime}=k_{l-1}^{\prime}+\frac{\sigma_{w}^{2}}{d}\|x\|.$

Using the fact that $\prod_{k=1}^{l}(1+\sigma_{w}^{2}/2k)=\Theta(l^{\sigma_{w}^{2}/2})$ , we conclude for $K_{res}^{l}(x,x)$ .

•

Recall that

K_{res}^{l}(x,x^{\prime})=K_{res}^{l-1}(x,x^{\prime})(\dot{q}^{l}(x,x^{\prime})+1)+q^{l}(x,x^{\prime}).

Let $c^{l}:=c^{l}(x,x^{\prime})$ . From Appendix Lemma 10 we have that

1-c^{l}=\frac{\zeta}{\log(l)^{2}}-\frac{\nabla}{\log(l)^{3}}+o\left(\frac{1}{\log(l)^{3}}\right),

$\zeta=\frac{16}{s^{2}\sigma_{w}^{4}}$ and $\nabla>0$ . Using the Taylor expansion of $f^{\prime}$ as in Appendix Lemma 5, it follows that

f^{\prime}(c^{l}(x,x^{\prime}))=1-\frac{6}{\sigma_{w}^{2}}\log(l)^{-1}+\zeta^{\prime}\log(l)^{-2}+\mathcal{O}(\log(l)^{-3})

where $\zeta^{\prime}=\frac{\nabla}{\sqrt{2\pi\zeta}}$ . We obtain

1+\dot{q}^{l}(x,x^{\prime})=1+\frac{\sigma_{w}^{2}}{2l}-3l^{-1}\log(l)^{-1}+\zeta^{\prime\prime}l^{-1}\log(l)^{-2}+\mathcal{O}(l^{-1}\log(l)^{-3})

where $\zeta^{\prime\prime}=\frac{\sigma_{w}^{2}}{2}\zeta^{\prime}$ . Letting $a_{l}=\frac{K^{l+1}_{res}(x,x^{\prime})}{\prod_{k=1}^{l}(1+\sigma_{w}^{2}/2k)}$ , we obtain

a_{l}=\lambda_{l}a_{l-1}+b_{l}

where $\lambda_{l}=1-l^{-1}-3l^{-1}\log(l)^{-1}+\mathcal{O}(l^{-1}\log(l)^{-2})$ , $b_{l}=\sqrt{q^{1}(x,x)}\sqrt{q^{1}(x^{\prime},x^{\prime})}f(c^{l}(x,x^{\prime}))=q(x,x^{\prime})+\mathcal{O}(\log(l)^{-2})$ with $q=\sqrt{q^{1}(x,x)}\sqrt{q^{1}(x^{\prime},x^{\prime})}$ and where we used the fact that $c^{l}=1+\mathcal{O}(\log(l)^{-2})$ (Appendix Lemma 10).

Now we proceed in the same way as in the proof of Appendix Lemma 4. Let $x_{l}=\frac{a_{l}}{l}-q$ , then there exists $M_{1},M_{2}>0$ such that

x_{l-1}(1-\frac{1}{l})-M_{1}l^{-1}\log(l)^{-1}\leq x_{l}\leq x_{l-1}(1-\frac{1}{l})-M_{2}l^{-1}\log(l)^{-1}.

Therefore, there exists $l_{0}$ independent of $(x,x^{\prime})$ such that for all $l\geq l_{0}$

x_{l}\leq x_{l_{0}}\prod_{k=l_{0}}^{l}(1-\frac{1}{k})-M_{2}\sum_{k=l_{0}}^{l}\prod_{j=k+1}^{l}(1-\frac{1}{j})k^{-1}\log(k)^{-1}

and

x_{l}\geq x_{l_{0}}\prod_{k=l_{0}}^{l}(1-\frac{1}{k})-M_{1}\sum_{k=l_{0}}^{l}\prod_{j=k+1}^{l}(1-\frac{1}{j})k^{-1}\log(k)^{-1}.

After simplification, we have that

\sum_{k=l_{0}}^{l}\prod_{j=k+1}^{l}(1-\frac{1}{j})k^{-1}\log(k)^{-1}=\Theta\left(\frac{1}{l}\int^{l}\frac{1}{\log(t)}dt\right)=\Theta(\log(l)^{-1}),

where we have used the asymptotic approximation of the Logarithmic Intergal function $\text{Li}(x)=\int^{t}\frac{1}{\log(t)}\sim_{x\rightarrow\infty}\frac{x}{\log(x)}.$

We conclude that $\alpha_{L}=L\times\prod_{k=1}^{l}(1+\sigma_{w}^{2}/2k)\sim L^{1+\frac{\sigma_{w}^{2}}{2}}$ and the convergence rate of the NTK is now $\Theta(\log(L)^{-1})$ which is better than $\Theta(L^{-1}\log(L))$ . The convergence is uniform over the set $B_{\epsilon}$ .

In the limit of large $L$ , the matrix NTK of the scaled resnet has the following form

\hat{AK}^{l}_{res}=qU+\log(L)^{-1}\Theta(M_{L})

where $U$ is the matrix of ones, and $M_{L}$ has all elements but the diagonal equal to 1 and the diagonal terms are $\mathcal{O}(L^{-1}\log(L))\rightarrow 0$ . Therefore, $M_{L}$ is inversible for large $L$ which makes $\hat{K}^{l}_{res}$ also inversible. Moreover, observe that the convergence rate for scaled resnet is $\log(L)^{-1}$ which means that for the same depth $L$ , the NTK remains far more expressive for scaled resnet compared to standard resnet, this is particularly important for the generalization.

8.2 Proof of Proposition 2: Spectral analysis of the NTK

We start by presenting a brief review of the theory of Spherical Harmonics, see (MacRobert 1967) for more details.

8.2.1 Some facts on Spherical harmonics

Let $\mathbb{S}^{d-1}$ be the unit sphere in $\mathbb{R}^{d}$ defined by $\mathbb{S}^{d-1}=\{x\in\mathbb{R}^{d}:\|x\|_{2}=1\}$ . For some $k\geq 1$ , there exists a set $(Y_{k,j})_{1\leq j\leq N(d,k)}$ of Spherical Harmonics of degree $k$ with $N(d,k)=\frac{2k+d-2}{k}{k+d-3\choose d-2}$ .

The set of functions $(Y_{k,j})_{k\geq 1,j\in[1:N(d,k)]}$ form an orthonormal basis with respect to the uniform measure on the unit sphere $\mathbb{S}^{d-1}$ .
For some function $g$ , the Hecke–Funk formula is given by

\int_{\mathbb{S}^{d-1}}g(\langle x,w\rangle)Y_{k,j}(w)d\nu_{d-1}(w)=\frac{\Omega_{d-1}}{\Omega_{d}}Y_{k,j}(x)\int_{-1}^{1}g(t)P^{d}_{k}(t)(1-t^{2})^{(d-3)/2}dt

where $\nu_{d-1}$ is the uniform measure on the unit sphere $\mathbb{S}^{d-1}$ , $\Omega_{d}$ is the volume of the unit sphere $\mathbb{S}^{d-1}$ , and $P^{d}_{k}$ is the multi-dimensional Legendre polynomials given explicitly by Rodrigues’ formula

P^{d}_{k}(t)=\left(-\frac{1}{2}\right)^{k}\frac{\Gamma(\frac{d-1}{2})}{\Gamma(k+\frac{d-1}{2})}(1-t^{2})^{\frac{3-d}{2}}\left(\frac{d}{dt}\right)^{k}(1-t^{2})^{k+\frac{d-3}{2}}.

$(P^{d}_{k})_{k\geq 0}$ form an orthogonal basis of $L^{2}([-1,1],(1-t^{2})^{\frac{d-3}{2}}dt)$ , i.e.

\langle P^{d}_{k},P^{d}_{k^{\prime}}\rangle_{L^{2}([-1,1],(1-t^{2})^{\frac{d-3}{2}}dt)}=\delta_{k,k^{\prime}}

where $\delta_{ij}$ is the Kronecker symbol. Moreover, we have

\|P^{d}_{k}\|^{2}_{L^{2}([-1,1],(1-t^{2})^{\frac{d-3}{2}}dt)}=\frac{(k+d-3)!}{(d-3)(k-d+3)!}.

Using the Heck–Funk formula, we can easily conclude that any dot product kernel on the unit sphere $\mathbb{S}^{d-1}$ , i.e. kernel of the form $\kappa(x,x^{\prime})=g(\langle x,x^{\prime}\rangle)$ can be decomposed on the Spherical Harmonics basis. Indeed, for any $x,x^{\prime}\in\mathbb{S}^{d-1}$ , the decomposition on the spherical harmonics basis yields

\kappa(x,x^{\prime})=\sum_{k\geq 0}\sum_{j=1}^{N(d,k)}\left[\int_{\mathbb{S}^{d-1}}g(\langle w,x^{\prime}\rangle)Y_{k,j}(w)d\nu_{d-1}(w)\right]Y_{k,j}(x).

Using the Hecke–Funk formula yields

\kappa(x,x^{\prime})=\sum_{k\geq 0}\sum_{j=1}^{N(d,k)}\left[\frac{\Omega_{d-1}}{\Omega_{d}}\int_{-1}^{1}g(t)P^{d}_{k}(t)(1-t^{2})^{(d-3)/2}dt\right]Y_{k,j}(x)Y_{k,j}(x^{\prime}),

we conclude that

\kappa(x,x^{\prime})=\sum_{k\geq 0}\mu_{k}\sum_{j=1}^{N(d,k)}Y_{k,j}(x)Y_{k,j}(x^{\prime})

where $\mu_{k}=\frac{\Omega_{d-1}}{\Omega_{d}}\int_{-1}^{1}g(t)P^{d}_{k}(t)(1-t^{2})^{(d-3)/2}dt$ .

We now use these result in the proof of the next theorem.

8.2.2 Proof of Proposition 2

From the recursive formulas of the NTK for FFNN, CNN and ResNet architectures, it is straightforward that, on the unit sphere $\mathbb{S}^{d-1}$ , the kernel $\kappa^{L}$ is zonal in the sense that it depends only on the scalar product. More precisely, for all $L\geq 1$ , there exists a function $g^{L}$ such that for all $x,x^{\prime}\in\mathbb{S}^{d-1}$

\kappa^{L}(x,x^{\prime})=g^{L}(\langle x,x^{\prime}\rangle).

Using the previous results on Spherical Harmonics, we have that for all $x,x^{\prime}\in\mathbb{S}^{d-1}$

\kappa^{L}(x,x^{\prime})=\sum_{k\geq 0}\mu^{L}_{k}\sum_{j=1}^{N(d,k)}Y_{k,j}(x)Y_{k,j}(x^{\prime})

where $\mu^{L}_{k}=\frac{\Omega_{d-1}}{\Omega_{d}}\int_{-1}^{1}g^{L}(t)P^{d}_{k}(t)(1-t^{2})^{(d-3)/2}dt$ .

For $k=0$ , we have that for all $L\geq 1$ , $\mu^{L}_{0}=\frac{\Omega_{d-1}}{\Omega_{d}}\int_{-1}^{1}g^{L}(t)(1-t^{2})^{(d-3)/2}dt$ . By a simple dominated convergence argument, we have that $\lim_{L\rightarrow\infty}\mu^{L}_{0}=q\lambda\frac{\Omega_{d-1}}{\Omega_{d}}\int_{-1}^{1}(1-t^{2})^{(d-3)/2}dt>0$ , where $q,\lambda$ are given in Theorems 1, 2 and Proposition 1 (where we take $q=1$ for the Ordered/Chaotic phase initialization in Proposition 1). Using the same argument, we have that for $k\geq 1$ , $\lim_{L\rightarrow\infty}\mu^{L}_{k}=q\lambda\frac{\Omega_{d-1}}{\Omega_{d}}\int_{-1}^{1}P^{d}_{k}(t)(1-t^{2})^{(d-3)/2}dt=q\lambda\frac{\Omega_{d-1}}{\Omega_{d}}\langle P^{d}_{0},P^{d}_{k}\rangle_{L^{2}([-1,1],(1-t^{2})^{\frac{d-3}{2}}dt)}=0$ .

Acknowledgements

The project leading to this work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 834175).

References

Arora et al. (2019a) S. Arora, S.S. Du, W. Hu, , Z. Li, and R. Wand. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In ICML, 2019a.
Arora et al. (2019b) S. Arora, S.S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In NeurIPS, 2019b.
Bietti and Bach (2021) A. Bietti and F. Bach. Deep equals shallow for reLU networks in kernel regimes. In ICLR, 2021.
Bietti and Mairal (2019) A. Bietti and J. Mairal. On the inductive bias of neural tangent kernels. In NeurIPS, 2019.
Cao and Gu (2019) Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In NeurIPS, 2019.
Cao et al. (2021) Y. Cao, Z. Fang, Y. Wu, D. Zhou, and Q. Gu. Towards understanding the spectral bias of deep learning. In IJCAI, 2021.
Chen and Xu (2021) L. Chen and S. Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In ICLR, 2021.
Chizat and Bach (2019) L. Chizat and F. Bach. A note on lazy training in supervised differentiable programming. In NeurIPS, 2019.
Du et al. (2018) S.S. Du, J.D. Lee, Y. Tian, B. Poczos, and A Singh. Gradient descent learns one-hidden-layer CNN: Don’t be afraid of spurious local minima. In ICML, 2018.
Du et al. (2019a) S.S. Du, J.D. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In ICML, 2019a.
Du et al. (2019b) S.S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR, 2019b.
Geifman et al. (2020) A. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and R. Basri. On the similarity between the laplace and neural tangent kernels. In NeurIPS, 2020.
Ghorbani et al. (2021) B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029–1054, 2021.
Hanin and Nica (2020) B. Hanin and M. Nica. Finite depth and width corrections to the neural tangent kernel. In ICLR, 2020.
Hayase and Karakida (2021) T. Hayase and R. Karakida. The spectrum of Fisher information of deep networks achieving dynamical isometry. In AISTATS, 2021.
Hayou et al. (2019a) S. Hayou, A. Doucet, and J. Rousseau. On the impact of the activation function on deep neural networks training. In ICML, 2019a.
Hayou et al. (2019b) S. Hayou, A. Doucet, and J. Rousseau. Mean-field behaviour of neural tangent kernel for deep neural networks. arXiv:1905.13654, 2019b.
Hayou et al. (2021) S. Hayou, E. Clerico, B. He, G. Deligiannidis, A. Doucet, and J. Rousseau. Stable resnet. In AISTATS, 2021.
Huang and Yau (2020) J. Huang and H.T Yau. Dynamics of deep neural networks and neural tangent hierarchy. In ICML, 2020.
Huang et al. (2020) K. Huang, Y. Wang, M. Tao, and T. Zhao. Why do deep residual networks generalize better than deep feedforward networks? – a neural tangent kernel perspective. In NeurIPS, 2020.
Jacot et al. (2018) A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In NeurIPS, 2018.
Karakida et al. (2019) R. Karakida, S. Akaho, and S. Amari. Universal statistics of Fisher information in deep neural networks: Mean field approach. In AISTATS, 2019.
Lee et al. (2018) J. Lee, Y. Bahri, R. Novak, S.S. Schoenholz, J. Pennington, and J. Sohl-Dickstein. In ICLR, 2018.
Lee et al. (2019) J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In NeurIPS, 2019.
Lillicrap et al. (2016) T. Lillicrap, D. Cownden, D. Tweed, and C. Akerman. Random synaptic feedback weights support error backpropagation for deep learning. Nature Communications, 7(13276), 2016.
MacRobert (1967) T.M. MacRobert. Spherical Harmonics: An Elementary Treatise on Harmonic Functions, with Applications. Pergamon Press, 1967.
Matthews et al. (2018) A.G. Matthews, J. Hron, M. Rowland, R.E. Turner, and Z. Ghahramani. Gaussian process behaviour in wide deep neural networks. In ICLR, 2018.
Neal (1995) R.M. Neal. Bayesian learning for neural networks. Springer Science & Business Media, 118, 1995.
Nguyen and Hein (2018) Q. Nguyen and M. Hein. Optimization landscape and expressivity of deep CNNs. In ICML, 2018.
Novak et al. (2020) Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In ICLR, 2020. URL https://github.com/google/neural-tangents.
Poole et al. (2016) B. Poole, S. Lahiri, M. Raghu, J. Sohl-Dickstein, and S. Ganguli. Exponential expressivity in deep neural networks through transient chaos. In NeurIPS, 2016.
Schoenholz et al. (2017) S.S. Schoenholz, J. Gilmer, S. Ganguli, and J. Sohl-Dickstein. Deep information propagation. In ICLR, 2017.
Xiao et al. (2018) L. Xiao, Y. Bahri, J. Sohl-Dickstein, S. S. Schoenholz, and P. Pennington. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. In ICML, 2018.
Xiao et al. (2020) Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and generalization in deep neural networks. In ICML, 2020.
Yang (2019) G. Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04760, 2019.
Yang (2020) G. Yang. Tensor programs iii: Neural matrix laws. arXiv preprint arXiv:2009.10685, 2020.
Yang and Schoenholz (2017) G. Yang and S. Schoenholz. Mean field residual networks: On the edge of chaos. In NeurIPS, 2017.
Zhang et al. (2017) C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Zou et al. (2018) D. Zou, Y. Cao, D. Zhou, and Q. Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. arXiv preprint arXiv:1811.08888, 2018.

Appendix

0 Some facts on the infinite-width regime and on NTKs

0.1 Gaussian process limit

In this section we recall some results on the Gaussian process limit of the of the function $f_{\theta}(x)=s(y_{\theta}^{L}(x))$ modelled as a DNN, when the weights parameters are drawn from Gaussian distributions.

0.1.1 Forward propagation

FeedForward Neural Network.

For some input $x\in\mathbb{R}^{d}$ , the propagation of this input through the network is given by Eq. (10). When we take the limit $n_{l-1}\rightarrow\infty$ recursively over $l$ , this implies, using the Central Limit Theorem, that $y_{i}^{l}(x)$ is a Gaussian variable for any input $x$ . This gives an error of order $\mathcal{O}(1/\sqrt{n_{l-1}})$ (standard Monte Carlo error). More generally, an approximation of the random process $y_{i}^{l}(.)$ by a Gaussian process was first proposed by [28] in the single layer case and has been extended to the multiple layer case by [23] and [27]. The limiting Gaussian process kernels follow a recursive formula given by, for any inputs $x,x^{\prime}\in\mathbb{R}^{d}$

	$\displaystyle\kappa^{l}(x,x^{\prime})$	$\displaystyle=\mathbb{E}[y^{l}_{i}(x)y^{l}_{i}(x^{\prime})]$
		$\displaystyle=\sigma^{2}_{b}+\sigma^{2}_{w}\mathbb{E}[\phi(y^{l-1}_{i}(x))\phi(y^{l-1}_{i}(x^{\prime}))]$
		$\displaystyle=\sigma^{2}_{b}+\sigma^{2}_{w}\Psi_{\phi}(\kappa^{l-1}(x,x),\kappa^{l-1}(x,x^{\prime}),\kappa^{l-1}(x^{\prime},x^{\prime})),$

where $\Psi_{\phi}$ is a function that only depends on the activation function $\phi$ . This provides a simple recursive formula for the computation of the kernel $\kappa^{l}$ ; see, e.g., [23] for more details.

Convolutional Neural Networks.

The propagation of the input through the network is described by Eq. (11). The infinite-width approximation with 1D CNN yields a recursion for the kernel. However, the infinite-width here means infinite number of channels, with a Monte Carlo error of $\mathcal{O}(1/\sqrt{n_{l-1}})$ . The kernel in this case depends on the choice of the neurons in the channel and is given by

\kappa^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\mathbb{E}[y^{l}_{i,\alpha}(x)y^{l}_{i,\alpha^{\prime}}(x^{\prime})]=\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta\in ker}\mathbb{E}[\phi(y^{l-1}_{1,\alpha+\beta}(x))\phi(y^{l-1}_{1,\alpha^{\prime}+\beta}(x^{\prime}))]

so that

\kappa^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta\in ker}F_{\phi}(\kappa^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x),\kappa^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}),\kappa^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x^{\prime},x^{\prime})).

The convolutional kernel $\kappa^{l}_{\alpha,\alpha^{\prime}}$ has the ‘self-averaging’ property; i.e. it is an average over the kernels corresponding to different combination of neurons in the previous layer. However, it is easy to simplify the analysis in this case by studying the average kernel per channel defined by $\hat{\kappa}^{l}=\frac{1}{N^{2}}\sum_{\alpha,\alpha^{\prime}}\kappa^{l}_{\alpha,\alpha^{\prime}}$ . Indeed, by summing terms in the previous equation and using the fact that we use circular padding, we obtain

\hat{\kappa}^{l}(x,x^{\prime})=\sigma_{b}^{2}+\sigma_{w}^{2}\frac{1}{N^{2}}\sum_{\alpha,\alpha^{\prime}}F_{\phi}(\kappa^{l-1}_{\alpha,\alpha^{\prime}}(x,x),\kappa^{l-1}_{\alpha,\alpha^{\prime}}(x,x^{\prime}),\kappa^{l-1}_{\alpha,\alpha^{\prime}}(x^{\prime},x^{\prime})).

This expression is similar in nature to that of FFNN. We will use this observation in the proofs.

Note that our analysis only requires the approximation that, in the infinite-width limit, for any two inputs $x,x^{\prime}$ , the variables $y^{l}_{i}(x)$ and $y^{l}_{i}(x^{\prime})$ are Gaussian with covariance $\kappa^{l}(x,x^{\prime})$ for FFNN, and $y^{l}_{i,\alpha}(x)$ and $y^{l}_{i,\alpha^{\prime}}(x^{\prime})$ are Gaussian with covariance $\kappa^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ for CNN. We do not need the much stronger approximation that the process $y^{l}_{i}(x)$ ( $y^{l}_{i,\alpha}(x)$ for CNN) is a Gaussian process.

Residual Neural Networks.

The propagation for ResNet architectures is described by (12). The infinite-width limit approximation for ResNet yields similar results with an additional residual terms. It is straighforward to see that, in the case of a ResNet with FFNN-type layers, we have that

\displaystyle\kappa^{l}(x,x^{\prime})=\kappa^{l-1}(x,x^{\prime})+\sigma^{2}_{b}+\sigma^{2}_{w}F_{\phi}(\kappa^{l-1}(x,x),\kappa^{l-1}(x,x^{\prime}),\kappa^{l-1}(x^{\prime},x^{\prime})),

whereas for ResNet with CNN-type layers, we have that

\begin{split}\kappa^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})&=\kappa^{l-1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})+\sigma_{b}^{2}\\ &+\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta\in ker}F_{\phi}(\kappa^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x),\kappa^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}),\kappa^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x^{\prime},x^{\prime})).\end{split}

0.1.2 Gradient Independence

In the literature of signal propagation in DNNs, an ubiquitous approximation is that of the gradient independence which is similar in nature to the practice of feedback alignment [25]. This approximation states that, for wide neural networks, the weights used for forward propagation are independent from those used for back-propagation. When used for the computation of Neural Tangent Kernel, this approximation was proven to give the exact computation for standard architectures such as FFNN, CNN and ResNets [36] (Theorem D.1).

This result has been extensively used in the literature as an approximation before being proved to yields exact computation for the NTK, and theoretical results derived under this approximation were verified empirically; see references below.

Gradient Covariance back-propagation.

Analytical formulas for gradient covariance back-propagation were derived using this result, in [16, 32, 37, 23, 31, 33, 35]. Empirical results showed an excellent match for FFNN in [32], for Resnets in [35] and for CNN in [33].

Neural Tangent Kernel.

The Gradient Independence approximation was implicitly used in [21] to derive the infinite-width Neural Tangent Kernel (See [21], Appendix A.1). Authors have found that this infinite-width NTK computed with the Gradient Independence approximation yields excellent match with empirical (exact) NTK.

We use this result in our proofs and we refer to it simply by the Gradient Independence.

0.2 On the theory of signal propagation in DNNs

For FFNN layers, let $q^{l}(x):=q^{l}(x,x)$ be the variance of $y^{l}_{1}(x)$ (the choice of the index $1$ is not important since, in the infinite-width limit, the random variables $(y^{l}_{i}(x))_{i\in[1:N_{l}]}$ are iid). Let $q^{l}(x,x^{\prime})$ , resp. $c^{l}_{1}(x,x^{\prime})$ be the covariance, resp. the correlation between $y^{l}_{1}(x)$ and $y^{l}_{1}(x^{\prime})$ . For Gradient back-propagation, let $\tilde{q}^{l}(x,x^{\prime})$ be the Gradient covariance defined by $\tilde{q}^{l}(x,x^{\prime})=\mathbb{E}\left[\frac{\partial\mathcal{L}}{\partial y^{l}_{1}}(x)\frac{\partial\mathcal{L}}{\partial y^{l}_{1}}(x^{\prime})\right]$ where $\mathcal{L}$ is some loss function. Similarly, let $\tilde{q}^{l}(x)$ be the Gradient variance at point $x$ . We also define $\dot{q}^{l}(x,x^{\prime})=\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(y^{l-1}_{1}(x))\phi^{\prime}(y^{l-1}_{1}(x^{\prime}))]$ .
For CNN layers, we use similar notation across channels. Let $q^{l}_{\alpha}(x)$ be the variance of $y^{l}_{1,\alpha,}(x)$ (the choice of the index $1$ is not important here either since, in the limit of infinite number of channels, the random variables $(y^{l}_{i,\alpha}(x))_{i\in[1:N_{l}]}$ are iid). Let $q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ the covariance between $y^{l}_{1,\alpha}(x)$ and $y^{l}_{1,\alpha^{\prime}}(x^{\prime})$ , and $c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ the corresponding correlation. We also define the pseudo-covariance $\hat{q}^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\sigma_{b}^{2}+\sigma_{w}^{2}\mathbb{E}[\phi(y^{l-1}_{1,\alpha}(x))\phi(y^{l-1}_{1,\alpha^{\prime}}(x^{\prime}))]$ and $\dot{q}^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\sigma_{w}^{2}\mathbb{E}[\phi(y^{l-1}_{1,\alpha}(x))\phi(y^{l-1}_{1,\alpha^{\prime}}(x^{\prime}))]$ .
The Gradient covariance is defined by $\tilde{q}^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\mathbb{E}\left[\frac{\partial\mathcal{L}}{\partial y^{l}_{1,\alpha}}(x)\frac{\partial\mathcal{L}}{\partial y^{l}_{1,\alpha^{\prime}}}(x^{\prime})\right]$ .

0.2.1 Covariance propagation and the Edge of Chaos

Covariance propagation for FFNN.

In Section 0.1.1, we derived the covariance kernel propagation in an FFNN. For two inputs $x,x^{\prime}\in\mathbb{R}^{d}$ , we have

q^{l}(x,x^{\prime})=\sigma^{2}_{b}+\sigma^{2}_{w}\mathbb{E}[\phi(y^{l-1}_{i}(x))\phi(y^{l-1}_{i}(x^{\prime}))]

(1)

this can be written as

q^{l}(x,x^{\prime})=\sigma^{2}_{b}+\sigma^{2}_{w}\mathbb{E}\left[\phi\left(\sqrt{q^{l}(x)}Z_{1}\right)\phi\left(\sqrt{q^{l}(x^{\prime})}(c^{l-1}Z_{1}+\sqrt{1-(c^{l-1})^{2}}Z_{2}\right)\right],\quad Z_{1},Z_{2}\overset{iid}{\sim}\mathcal{N}(0,1),

with $c^{l-1}:=c^{l-1}(x,x^{\prime})$ .
With ReLU, and since ReLU is positively homogeneous (i.e. $\phi(\lambda x)=\lambda\phi(x)$ for $\lambda\geq 0$ ), we have that

q^{l}(x,x^{\prime})=\sigma^{2}_{b}+\frac{\sigma^{2}_{w}}{2}\sqrt{q^{l}(x)}\sqrt{q^{l}(x^{\prime})}f(c^{l-1})

where $f$ is the ReLU correlation function given by [16]

\displaystyle f(c)=\frac{1}{\pi}(c\arcsin{c}+\sqrt{1-c^{2}})+\frac{1}{2}c.

Covariance propagation for CNN.

The only difference with FFNN is that the independence is across channels and not neurons. Simple calculus yields

q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\mathbb{E}[y^{l}_{i,\alpha}(x)y^{l}_{i,\alpha^{\prime}}(x^{\prime})]=\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta\in ker}\mathbb{E}[\phi(y^{l-1}_{1,\alpha+\beta}(x))\phi(y^{l-1}_{1,\alpha^{\prime}+\beta}(x^{\prime}))]

Observe that

q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\frac{1}{2k+1}\sum_{\beta inker}\hat{q}^{l}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime})

(2)

With ReLU, we have

q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta\in ker}\sqrt{q^{l}_{\alpha+\beta}(x)}\sqrt{q^{l}_{\alpha^{\prime}+\beta}(x^{\prime})}f(c^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime})).

Covariance propagation for ResNet with ReLU.

In the case of ResNet, only an added residual term shows up in the recursive formula. For a ResNet with FFNN layers, the recursion reads

q^{l}(x,x^{\prime})=q^{l-1}(x,x^{\prime})+\sigma^{2}_{b}+\frac{\sigma^{2}_{w}}{2}\sqrt{q^{l}(x)}\sqrt{q^{l}(x^{\prime})}f(c^{l-1})

(3)

with CNN layers, we have instead

q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=q^{l-1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})+\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta\in ker}\sqrt{q^{l}_{\alpha+\beta}(x)}\sqrt{q^{l}_{\alpha^{\prime}+\beta}(x^{\prime})}f(c^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}))

(4)

Edge of Chaos (EOC)

Let $x\in\mathbb{R}^{d}$ be an input. The convergence of $q^{l}(x)$ as $l$ increases has been studied by [32] and [16]. In particular, under weak regularity conditions, it is proven that $q^{l}(x)$ converges to a point $q(\sigma_{b},\sigma_{w})>0$ independent of $x$ as $l\rightarrow\infty$ . The asymptotic behaviour of the correlations $c^{l}(x,x^{\prime})$ between $y^{l}(x)$ and $y^{l}(x^{\prime})$ for any two inputs $x$ and $x^{\prime}$ is also driven by $(\sigma_{b},\sigma_{w})$ : the dynamics of $c^{l}$ is controlled by a function $f$ i.e. $c^{l+1}=f(c^{l})$ called the correlation function. The authors define the EOC as the set of parameters $(\sigma_{b},\sigma_{w})$ such that $\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(\sqrt{q(\sigma_{b},\sigma_{w})}Z)^{2}]=1$ where $Z\sim\mathcal{N}(0,1)$ . Similarly the Ordered, resp. Chaotic, phase is defined by $\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(\sqrt{q(\sigma_{b},\sigma_{w})}Z)^{2}]<1$ , resp. $\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(\sqrt{q(\sigma_{b},\sigma_{w})}Z)^{2}]>1$ . In the Ordered phase, the gradient will vanish as it backpropagates through the network, and the correlation $c^{l}(x,x^{\prime})$ converges exponentially to $1$ . Hence the output function becomes constant (hence the name ’Ordered phase’). In the Chaotic phase, the gradient explodes and the correlation converges exponentially to some limiting value $c<1$ which results in the output function being discontinuous everywhere (hence the ’Chaotic’ phase name). In the EOC, the second moment of the gradient remains constant throughout the backpropagation and the correlation converges to 1 at a sub-exponential rate, which allows deeper information propagation. Hereafter, $f$ will always refer to the correlation function.

0.2.2 Gradient Covariance back-propagation

Gradient back-propagation for FFNN.

The gradient back-propagation is given by

\displaystyle\frac{\partial\mathcal{L}}{\partial y^{l}_{i}}

\displaystyle=\phi^{\prime}(y^{l}_{i})\sum_{j=1}^{N_{l+1}}\frac{\partial\mathcal{L}}{\partial y^{l+1}_{j}}W^{l+1}_{ji}.

where $\mathcal{L}$ is some loss function. Using the Gradient Independence 0.1.2, we have as in [32]

\tilde{q}^{l}(x)=\tilde{q}^{l+1}(x)\frac{N_{l+1}}{N_{l}}\chi(q^{l}(x)).

where $\chi(q^{l}(x))=\sigma_{w}^{2}\mathbb{E}[\phi(\sqrt{q^{l}(x)}Z)^{2}]$ .

Gradient Covariance back-propagation for CNN.

We have that

\frac{\partial{\mathcal{L}}}{\partial W^{l}_{i,j,\beta}}=\sum_{\alpha}\frac{\partial{\mathcal{L}}}{\partial y^{l}_{i,\alpha}}\phi(y^{l-1}_{j,\alpha+\beta})

Moreover,

\frac{\partial{\mathcal{L}}}{\partial y^{l}_{i,\alpha}}=\sum_{j=1}^{n}\sum_{\beta\in ker}\frac{\partial{\mathcal{L}}}{\partial y^{l+1}_{j,\alpha-\beta}}W^{l+1}_{i,j,\beta}\phi^{\prime}(y^{l}_{i,\alpha}).

Using the Gradient Independence 0.1.2, and taking the average over the number of channels we have that

\mathbb{E}\left[\frac{\partial{\mathcal{L}}}{\partial y^{l}_{i,\alpha}}^{2}\right]=\frac{\sigma_{w}^{2}\mathbb{E}\left[\phi^{\prime}(\sqrt{q^{l}_{\alpha}(x)}Z)^{2}\right]}{2k+1}\sum_{\beta\in ker}\mathbb{E}\left[\frac{\partial{\mathcal{L}}}{\partial y^{l+1}_{i,\alpha-\beta}}^{2}\right].

We can get similar recursion to that of the FFNN case by summing over $\alpha$ and using the periodic boundary condition, this yields

\sum_{\alpha}\mathbb{E}\left[\frac{\partial{\mathcal{L}}}{\partial y^{l}_{i,\alpha}}^{2}\right]=\chi(q^{l}_{\alpha}(x))\sum_{\alpha}\mathbb{E}\left[\frac{\partial{\mathcal{L}}}{\partial y^{l+1}_{i,\alpha}}^{2}\right].

0.2.3 Some facts on the theory of information propagation

The results presented here are based on an initialization of the model with $w^{l}_{ij},b^{l}_{i}\stackrel{{\scriptstyle iid}}{{\sim}}\mathcal{N}(0,1)$ and under the following conditions:

•

The input data is a subset of a compact set $E$ of $\mathbb{R}^{d}$ , and no two inputs are co-linear.
•

All calculations are done in the limit of infinitely wide networks.

These results are compiled from previous papers and recalled here for the sake of completeness.

Results for FFNN with Tanh activation.

Fact 1.

For any choice of $\sigma_{b},\sigma_{w}\in\mathbb{R}^{+}$ , there exist $q,\lambda>0$ such that for all $l\geq 1$ , $\sup_{x\in\mathbb{R}^{d}}|q^{l}(x,x)-q|\leq e^{-\lambda l}$ . (Eq. (3) and conclusion right after in [32]).

Fact 2.

In the Ordered phase, there exists $\gamma>0$ such that $\sup_{x,x^{\prime}\in\mathbb{R}^{d}}|c^{l}(x,x^{\prime})-1|\leq e^{-\gamma l}$ . (Eq. (8) in [32])

Fact 3.

Let $(\sigma_{b},\sigma_{w})\in$ EOC. Using the same notation as in fact 4, we have that $\sup_{(x,x^{\prime})\in B_{\epsilon}}|1-c^{l}(x,x^{\prime})|=\mathcal{O}(l^{-1})$ . (Proposition 3 in [16]).

Fact 4.

Let $B_{\epsilon}=\{(x,x^{\prime})\in\mathbb{R}^{d}:c^{1}(x,x^{\prime})<1-\epsilon\}$ . In the chaotic phase, there exist $c<1$ such that for all $\epsilon\in(0,1)$ , there exists $\gamma>0$ such that $\sup_{(x,x^{\prime})\in B_{\epsilon}}|c^{l}(x,x^{\prime})-c|\leq e^{-\gamma l}$ . (Eqs. (8) and (9) in [32])

Fact 5 (Correlation function).

The correlation function $f$ is defined by

f(x)=\frac{\sigma_{b}^{2}+\sigma_{w}^{2}\mathbb{E}[\phi(\sqrt{q}Z_{1})\phi(\sqrt{q}(xZ_{1}+\sqrt{1-x^{2}}Z_{2}))]}{q}

where $q$ is given in Fact 1 and $Z_{1},Z_{2}$ are iid standard Gaussian variables.

Fact 6.

$f$ has a derivative of any order $j\geq 1$ given by

f^{(j)}(x)=\sigma_{w}^{2}q^{j-1}\mathbb{E}[\phi^{(j)}(Z_{1})\phi^{(j)}(xZ_{1}+\sqrt{1-x^{2}}Z_{2})],\quad\forall x\in[-1,1]

As a result, we have that $f^{(j)}(1)=\sigma_{w}^{2}q^{j-1}\mathbb{E}[\phi^{(j)}(Z_{1})^{2}]>0$ for all $j\geq 1$ .

The proof of the previous fact is straightforward following the same integration by parts technique as in the proof of lemma 1 in [16]. The result follows by induction.

Fact 7.

Let $(\sigma_{b},\sigma_{w})\in$ EOC. We have that $f^{\prime}(1)=1$ (by definition of EOC). As a result, the Taylor expansion of $f$ near 1 is given by

f(c)=c+\alpha(1-c)^{2}-\zeta(1-c)^{3}+O((1-c)^{4}).

where $\alpha,\zeta>0$ .

Proof.

The proof is straightforward using fact 6, and integral-derivative interchanging. ∎

Results for FFNN with ReLU activation.

Fact 8.

The ordered phase for ReLU is given by $\textrm{Ord}=\{(\sigma_{b},\sigma_{w})\in(\mathbb{R}^{+})^{2}:\sigma_{w}<\sqrt{2}\}$ . Moreover, for any $(\sigma_{b},\sigma_{w})\in\mathrm{Ord}$ , there exist $\lambda$ such that for all $l\geq 1$ , $\sup_{x\in\mathbb{R}^{d}}|q^{l}(x,x)-q|\leq e^{-\lambda l}$ , where $q=\frac{\sigma_{b}^{2}}{1-\sigma_{w}^{2}/2}$ .

The proof is straightforward using Eq. (1).

Fact 9.

For any $(\sigma_{b},\sigma_{w})$ in the Ordered phase, there exist $\lambda$ such that for all $l\geq 1$ , $\sup_{(x,x^{\prime})\in\mathbb{R}^{d}}|c^{l}(x,x^{\prime})-1|\leq e^{-\lambda l}$ .

The proof of this claim follows from standard Banach Fixed point theorem in the same fashion as for Tanh in [32].

Fact 10.

The Chaotic phase for ReLU is given by $\textrm{Ch}=\{(\sigma_{b},\sigma_{w})\in(\mathbb{R}^{+})^{2}:\sigma_{w}>\sqrt{2}\}$ . Moreover, for any $(\sigma_{b},\sigma_{w})\in\mathrm{Ch}$ , for all $l\geq 1$ , $x\in\mathbb{R}^{d},q^{l}(x,x)\gtrsim(\sigma_{w}^{2}/2)^{l}$ .

The variance explodes exponentially in the Chaotic phase, which means the output of the Neural Network can grow arbitrarily in this setting. Hereafter, when no activation function is mentioned, and when we choose " $(\sigma_{b},\sigma_{w})$ in the Ordered/Chaotic phase", it should be interpreted as " $(\sigma_{b},\sigma_{w})$ in the Ordered phase" for ReLU and " $(\sigma_{b},\sigma_{w})$ in the Ordered/Chaotic phase" for Tanh.

Fact 11.

For ReLU FFNN in the EOC, we have that $q^{l}(x,x)=\frac{\sigma_{w}^{2}}{d}||x||^{2}$ for all $l\geq 1$ .

The proof is straightforward using Eq. 1 and that $(\sigma_{b},\sigma_{w})=(0,\sqrt{2})$ in the EOC.

Fact 12.

The EOC of ReLU is given by the singleton $\{(\sigma_{b},\sigma_{w})=(0,\sqrt{2})\}$ . In this case, the correlation function of an FFNN with ReLU is given by

f(x)=\frac{1}{\pi}(x\arcsin{x}+\sqrt{1-x^{2}})+\frac{1}{2}x

(Proof of Proposition 1 in [16]).

Fact 13.

Let $(\sigma_{b},\sigma_{w})\in$ EOC. Using the same notation as in fact 4, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}|1-c^{l}(x,x^{\prime})|=\mathcal{O}(l^{-2})

(Follows straightforwardly from Proposition 1 in [16]).

Fact 14.

We have that

f(c)=c+s(1-c)^{3/2}+b(1-c)^{5/2}+O((1-c)^{7/2}

(5)

with $s=\frac{2\sqrt{2}}{3\pi}$ and $b=\frac{\sqrt{2}}{30\pi}$ .

This result was proven in [16] (in the proof of Proposition 1) for order $3/2$ , the only difference is that here we push the expansion to order $5/2$ .

Results for CNN with Tanh activation function.

Fact 15.

For any choice of $\sigma_{b},\sigma_{w}\in\mathbb{R}^{+}$ , there exist $q,\lambda>0$ such that for all $l\geq 1$ , $\sup_{\alpha,\alpha^{\prime}}\sup_{x\in\mathbb{R}^{d}}|q^{l}_{\alpha,\alpha^{\prime}}(x,x)-q|\leq e^{-\lambda l}$ . (Eq. (2.5) in [33] and variance convergence result in [32]).

The behaviour of the correlation $c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ was studied in [33] only in the case $x^{\prime}=x$ . We give a comprehensive analysis of the asymptotic behaviour of $c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ in the next section.

General results on the correlation function.

Fact 16.

Let $f$ be either the correlation function of Tanh or ReLU. We have that

•

$f(1)=1$ (lemma 2 in [16]).
•

In the ordered phase $0<f^{\prime}(1)<1$ (By definition).
•

In the Chaotic phase $f^{\prime}(1)>1$ (By definition).
•

In the EOC, $f^{\prime}(1)=1$ (By definition).
•

In the Ordered phase and the EOC, $1$ is the unique fixed point of $f$ ([16]).
•

In the Chaotic phase, $f$ has two fixed points, $1$ which is unstable, and $c<1$ which is a stable fixed point [32].

Fact 17.

Let $\epsilon\in(0,1)$ . In the Ordered/Chaotic phase, with either ReLU or Tanh, there exists $\alpha\in(0,1)$ , $\gamma>0$ such that

\sup_{(x,x^{\prime})\in B_{\epsilon}}|f^{\prime}(c^{l}(x,x^{\prime}))-\alpha|\leq e^{-\gamma l}

Proof.

This result follows from a simple first order expansion inequality. For Tanh with $(\sigma_{b},\sigma_{w})$ in the Ordered phase, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}|f^{\prime}(c^{l}(x,x^{\prime}))-f^{\prime}(1)|\leq\zeta_{l}\sup_{(x,x^{\prime})\in B_{\epsilon}}|c^{l}(x,x^{\prime})-1|

where $\zeta_{l}=\sup_{t\in(\min_{(x,x^{\prime}\in B_{\epsilon})}c^{l}(x,x^{\prime}),1)}|f^{\prime\prime}(t)|\rightarrow|f^{\prime\prime}(1)|$ . We conclude for Ordered phase with Tanh using fact 2. The same argument can be used for Chaotic phase with Tanh using fact 4; in this case, $\alpha=f^{\prime}(c)$ where $c$ is the unique stable fixed point of the correlation function $f$ .

In the Ordered phase with ReLU, let $\tilde{f}$ be the correlation function. It is easy to see that $\tilde{f}^{\prime}(c)=\frac{\sigma_{w}^{2}}{2}f^{\prime}(c)$ where $f$ is given in fact 12. $f^{\prime}(x)=1-\frac{\sqrt{2}}{\pi}(1-x)^{1/2}+\mathcal{O}((1-x)^{3/2})$ . Therefore, there exists $l_{0},\zeta>0$ such that for $l>l_{0}$ ,

\sup_{(x,x^{\prime})\in B_{\epsilon}}|f^{\prime}(c^{l}(x,x^{\prime}))-f^{\prime}(1)|\leq\zeta\sup_{(x,x^{\prime})\in B_{\epsilon}}|c^{l}(x,x^{\prime})-1|^{1/2}

We conclude using fact 9. ∎

1 Technical lemmas

In this section we provide a number of technical lemmas used to control certain types of bounds.

1.1 A technical lemma for the derivation of uniform bounds

Results in theorem 1 and 2 and Proposition 1 involve a supremum over the set $B_{\epsilon}$ . To obtain such results, we need a ’uniform’ Taylor analysis of the correlation $c^{l}(x,x^{\prime})$ (see the next section) where uniformity is over $(x,x^{\prime})\in B_{\epsilon}$ . It turns out that such result is trivial when the correlation follows a dynamical system that is controlled by a non-decreasing function. We clarify this in the next lemma.

Appendix Lemma 1 (Uniform Bounds).

Let $A\subset\mathbb{R}$ be a compact set and $g$ a non-decreasing function on $A$ . Define the sequence $\zeta_{l}$ by $\zeta_{l}=g(\zeta_{l-1})$ and $\zeta_{0}\in A$ . Assume that there exist $\alpha_{l},\beta_{l}$ that do not depend on $\zeta_{0}$ (in the sense that $\alpha_{l},\beta_{l}$ are the same for all $\zeta_{0}\in A$ ), with $\beta_{l}=o(\alpha_{l})$ , such that for all $\zeta_{0}\in A$ ,

\zeta_{l}=\alpha_{l}+\mathcal{O}_{\zeta_{0}}(\beta_{l})

where $\mathcal{O}_{\zeta_{0}}$ means that the $\mathcal{O}$ bound depends on $\zeta_{0}$ . Then, we have that

\sup_{\zeta_{0}\in A}|\zeta_{l}-\alpha_{l}|=\mathcal{O}(\beta_{l})

i.e. we can choose the bound $\mathcal{O}$ to be independent of $\zeta_{0}$ .

Proof.

Let $\zeta_{0,m}=\min A$ and $\zeta_{0,M}=\max A$ . Let $(\zeta_{m,l})$ and $(\zeta_{M,l})$ be the corresponding sequences. Since $g$ is non-decreasing, we have that for all $\zeta_{0}\in A$ , $\zeta_{m,l}\leq\zeta_{l}\leq\zeta_{M,l}$ . Moreover, by assumption, there exists $M_{1},M_{2}>0$ such that

|\zeta_{m,l}-\alpha_{l}|\leq M_{1}|\beta_{l}|

and

|\zeta_{M,l}-\alpha_{l}|\leq M_{2}|\beta_{l}|

therefore,

|\zeta_{l}-\alpha_{l}|\leq\max(|\zeta_{m,l}-\alpha_{l}|,|\zeta_{M,l}-\alpha_{l}|)\leq\max(M_{1},M_{2})|\beta_{l}|

which concludes the proof. ∎

Note that Appendix Lemma 1 can be easily extended to Taylor expansions with ‘ $o$ ’ instead of ‘ $\mathcal{O}$ ’. We will use this result in the proofs, by refereeing to Appendix Lemma 1.

1.2 On the convergence of sequences under recursive formulations

In this section we describe three types of convergence of sequences $(a_{l})_{l}$ verifying some recursive inequalities.

The next lemma is used in the proof of Proposition 1.

Appendix Lemma 2.

Let $(a_{l})$ be a sequence of non-negative real numbers such that $\forall l\geq 0,a_{l+1}\leq\alpha a_{l}+ke^{-\beta l}$ , where $\alpha\in(0,1)$ and $k,\beta>0$ . Then there exists $\gamma>0$ such that $\forall l\geq 0,\,a_{l}\leq e^{-\gamma l}$ .

Proof.

Using the inequality on $a_{l}$ , we can easily see that

	$\displaystyle a_{l}$	$\displaystyle\leq a_{0}\alpha^{l}+k\sum_{j=0}^{l-1}\alpha^{j}e^{-\beta(l-j)}$
		$\displaystyle\leq a_{0}\alpha^{l}+k\frac{l}{2}e^{-\beta l/2}+k\frac{l}{2}\alpha^{l/2}$

where we divided the sum into two parts separated by index $l/2$ and upper-bounded each part. The existence of $\gamma$ is straightforward. ∎

The next lemma gives uniform bounds for a special type of sequences where the uniform bound here is over the initial point in the sequence.

Appendix Lemma 3.

Let $A,B,\Lambda\subset\mathbb{R+}$ be three compact sets, and $(a_{l}),(b_{l}),(\lambda_{l})$ be three sequences of non-negative real numbers such that for all $(a_{0},b_{0},\lambda_{0})\in A\times B\times\Lambda$

a_{l}=a_{l-1}\lambda_{l}+b_{l},\quad\lambda_{l}=1-\frac{\alpha}{l}+\mathcal{O}(l^{-1-\beta}),\quad b_{l}=q(b_{0})+o(l^{-1}),

where $\alpha\in\mathbb{N}^{*}$ independent of $a_{0},b_{0},\lambda_{0}$ , $q(b_{0})\geq 0$ is a limit that depends on $b_{0}$ , and $\beta\in(0,1)$ .
Assume the ‘ $\mathcal{O}$ ’ and ‘ $o$ ’ depend only on $A,B,\Lambda\subset\mathbb{R}$ . Then, we have

\sup_{(a_{0},b_{0},\lambda_{0})\in A\times B\times\Lambda}\left|\frac{a_{l}}{l}-\frac{q}{1+\alpha}\right|=\mathcal{O}(l^{-\beta}).

Proof.

Let $A,B,\Lambda\subset\mathbb{R}$ be three compact sets and $(a_{0},b_{0},\lambda_{0})\in A\times B\times\Lambda$ . It is easy to see that there exists a constant $G>0$ independent of $a_{0},b_{0},\lambda_{0}$ such that $|a_{l}|\leq G\times l+|a_{0}|$ for all $l\geq 0$ . Letting $r_{l}=\frac{a_{l}}{l}$ , we have that for $l\geq 2$

	$\displaystyle r_{l}$	$\displaystyle=r_{l-1}(1-\frac{1}{l})(1-\frac{\alpha}{l}+\mathcal{O}(l^{-1-\beta}))+\frac{q}{l}+o(l^{-2})$
		$\displaystyle=r_{l-1}(1-\frac{1+\alpha}{l})+\frac{q}{l}+\mathcal{O}(l^{-1-\beta}).$

where $\mathcal{O}$ bound depends only on $A,B,\Lambda$ . Letting $x_{l}=r_{l}-\frac{q}{1+\alpha}$ , there exists $M>0$ that depends only on $A,B,\Lambda$ , and $l_{0}>0$ that depends only on $\alpha$ such that for all $l\geq l_{0}$

\displaystyle x_{l-1}(1-\frac{1+\alpha}{l})-\frac{M}{l^{1+\beta}}\leq x_{l}

\displaystyle\leq x_{l-1}(1-\frac{1+\alpha}{l})+\frac{M}{l^{1+\beta}}.

Let us deal with the right hand inequality first. By induction, we have that

x_{l}\leq x_{l_{0}-1}\prod_{k=l_{0}}^{l}(1-\frac{1+\alpha}{k})+M\sum_{k=l_{0}}^{l}\prod_{j=k+1}^{l}(1-\frac{1+\alpha}{j})\frac{1}{k^{1+\beta}}.

By taking the logarithm of the first term in the right hand side and using the fact that $\sum_{k=l_{0}}^{l}\frac{1}{k}=\log(l)+O(1)$ , we have

\prod_{k=l_{0}}^{l}(1-\frac{1+\alpha}{k})=\Theta(l^{-1-\alpha}).

where the bound $\Theta$ does not depend on $l_{0}$ . For the second part, observe that

\displaystyle\prod_{j=k+1}^{l}(1-\frac{1+\alpha}{j})=\frac{(l-\alpha-1)!}{l!}\frac{k!}{(k-\alpha-1)!}

and

\frac{k!}{(k-\alpha-1)!}\frac{1}{k^{1+\beta}}\sim_{k\rightarrow\infty}k^{\alpha-\beta}.

Since $\alpha\geq 1$ ( $\alpha\in\mathbb{N}^{*}$ ), then the serie with term $k^{\alpha-\beta}$ is divergent and we have that

	$\displaystyle\sum_{k=l_{0}}^{l}\frac{k!}{(k-\alpha-1)!}\frac{1}{k^{2}}$	$\displaystyle\sim\sum_{k=1}^{l}k^{\alpha-\beta}$
		$\displaystyle\sim\int_{1}^{l}t^{\alpha-\beta}dt$
		$\displaystyle\sim\frac{1}{\alpha-\beta+1}l^{\alpha-\beta+1}.$

Therefore, it follows that

	$\displaystyle\sum_{k=l_{0}}^{l}\prod_{j=k+1}^{l}(1-\frac{1+\alpha}{j})\frac{1}{k^{1+\beta}}$	$\displaystyle=\frac{(l-\alpha-1)!}{l!}\sum_{k=l_{0}}^{l}\frac{k!}{(k-\alpha-1)!}\frac{1}{k^{1+\beta}}$
		$\displaystyle\sim\frac{1}{\alpha}l^{-\beta}.$

This proves that

x_{l}\leq\frac{M}{\alpha}l^{-\beta}+o(l^{-\beta}).

where the ‘ $o$ ’ bound depends only on $A,B,\Lambda$ . Using the same approach for the left-hand inequality, we prove that

x_{l}\geq-\frac{M}{\alpha}l^{-\beta}+o(l^{-\beta}).

This concludes the proof.

∎

The next lemma is a different version of the previous lemma and will be useful for other applications.

Appendix Lemma 4.

	$\displaystyle a_{l}$	$\displaystyle=a_{l-1}\lambda_{l}+b_{l},\quad b_{l}=q(b_{0})+\mathcal{O}(l^{-1}),$
	$\displaystyle\lambda_{l}$	$\displaystyle=1-\frac{\alpha}{l}+\kappa\frac{\log(l)}{l^{2}}+\mathcal{O}(l^{-2}),$

where $\alpha\in\mathbb{N}^{*},\kappa\neq 0$ both do not depend on $a_{0},b_{0},\Lambda_{0}$ , $q(b_{o})\in\mathbb{R}^{+}$ is a limit that depends on $b_{0}$ .
Assume the ‘ $\mathcal{O}$ ’ and ‘ $o$ ’ depend only on $A,B,\Lambda\subset\mathbb{R}$ . Then, we have

\sup_{(a_{0},b_{0},\lambda_{0})\in A\times B\times\Lambda}\left|\frac{a_{l}}{l}-\frac{q}{1+\alpha}\right|=\Theta(\log(l)l^{-1})

Proof.

Let $A,B,\Lambda\subset\mathbb{R}$ be three compact sets and $(a_{0},b_{0},\lambda_{0})\in A\times B\times\Lambda$ . Similar to the proof of Appendix Lemma 3, there exists a constant $G>0$ independent of $a_{0},b_{0},\lambda_{0}$ such that $|a_{l}|\leq G\times l+|a_{0}|$ for all $l\geq 0$ , therefore $(a_{l}/l)$ is bounded. Let $r_{l}=\frac{a_{l}}{l}$ . We have

	$\displaystyle r_{l}$	$\displaystyle=r_{l-1}(1-\frac{1}{l})(1-\frac{\alpha}{l}+\kappa\frac{\log(l)}{l^{2}}+\mathcal{O}(l^{-2}))+\frac{q}{l}+\mathcal{O}(l^{-2})$
		$\displaystyle=r_{l-1}(1-\frac{1+\alpha}{l})+r_{l-1}\kappa\frac{\log(l)}{l^{2}}+\frac{q}{l}+\mathcal{O}(l^{-2}).$

Let $x_{l}=r_{l}-\frac{q}{1+\alpha}$ . It is clear that $\lambda_{l}=1-\alpha/l+\mathcal{O}(l^{-3/2})$ . Therefore, using Appendix Lemma 3 with $\beta=1/2$ , we have $r_{l}\rightarrow\frac{q}{1+\alpha}$ uniformly over $a_{0},b_{0},\lambda_{0}$ . Thus, assuming $\kappa>0$ (for $\kappa<0$ , the analysis is the same), there exists $\kappa_{1},\kappa_{2},M,l_{0}>0$ that depend only on $A,B,\Lambda$ such that for all $l\geq l_{0}$

\displaystyle x_{l-1}(1-\frac{1+\alpha}{l})+\kappa_{1}\frac{\log(l)}{l^{2}}-\frac{M}{l^{2}}\leq x_{l}\leq x_{l-1}(1-\frac{1+\alpha}{l})+\kappa_{2}\frac{\log(l)}{l^{2}}+\frac{M}{l^{2}}.

It follows that

x_{l}\leq x_{l_{0}}\prod_{k=l_{0}}^{l}(1-\frac{1+\alpha}{k})+\sum_{k=l_{0}}^{l}\prod_{j=k+1}^{l}(1-\frac{1+\alpha}{j})\frac{\kappa_{2}\log(k)+M}{k^{2}}

and

x_{l}\geq x_{l_{0}}\prod_{k=l_{0}}^{l}(1-\frac{1+\alpha}{k})+\sum_{k=l_{0}}^{l}\prod_{j=k+1}^{l}(1-\frac{1+\alpha}{j})\frac{\kappa_{1}\log(k)-M}{k^{2}}.

Recall that we have

\prod_{k=l_{0}}^{l}(1-\frac{1+\alpha}{k})=\Theta(l^{-1-\alpha})

and

\displaystyle\prod_{j=k+1}^{l}(1-\frac{1+\alpha}{j})=\frac{(l-\alpha-1)!}{l!}\frac{k!}{(k-\alpha-1)!}

so that

\frac{k!}{(k-\alpha-1)!}\frac{\kappa_{1}\log(k)-M}{k^{2}}\sim_{k\rightarrow\infty}\log(k)k^{\alpha-1}.

Therefore, we obtain

	$\displaystyle\sum_{k=l_{0}}^{l}\frac{k!}{(k-\alpha-1)!}\frac{\kappa_{1}\log(k)-M}{k^{2}}$	$\displaystyle\sim\sum_{k=1}^{l}\log(k)k^{\alpha-1}$
		$\displaystyle\sim\int_{1}^{l}\log(t)t^{\alpha-1}dt$
		$\displaystyle\sim C_{1}l^{\alpha}\log(l),$

where $C_{1}>0$ is a constant. Similarly, there exists a constant $C_{2}>0$ such that

\displaystyle\sum_{k=1}^{l}\frac{k!}{(k-\alpha-1)!}\frac{\kappa_{2}\log(k)+M}{k^{2}}

\displaystyle\sim C_{2}l^{\alpha}\log(l).

Moreover, having that $\frac{(l-\alpha-1)!}{l!}\sim l^{-1-\alpha}$ yields

x_{l}\leq C^{\prime}l^{-1}\log(l)+o(l^{-1}\log(l))

where $C^{\prime}$ and ‘ $o$ ’ depend only on $A,B,\Lambda$ . Using the same analysis, we get

x_{l}\geq C^{\prime\prime}l^{-1}\log(l)+o(l^{-1}\log(l))

where $C^{\prime\prime}$ and ‘ $o$ ’ depend only on $A,B,\Lambda$ , which concludes the proof.

∎

1.3 Technical Lemmas for FFNN and CNN

Appendix Lemma 5 (Asymptotic behaviour of $c^{l}$ for ReLU).

Let $(\sigma_{b},\sigma_{w})\in EOC$ and $\epsilon\in(0,1)$ . There exist universal constants $\kappa,\kappa^{\prime},\kappa^{\prime\prime}>0$ (that do not depend on any parameter) such that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|c^{l}(x,x^{\prime})-1+\frac{\kappa}{l^{2}}-\kappa^{\prime}\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

and,

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|f^{\prime}(c^{l}(x,x^{\prime}))-1+\frac{3}{l}-\kappa^{\prime\prime}\frac{\log(l)}{l^{2}}\right|=\mathcal{O}(l^{-2}).

Proof.

Let $(x,x^{\prime})\in B_{\epsilon}$ and $s=\frac{2\sqrt{2}}{3\pi}$ . From the preliminary results, we have that $\lim\limits_{l\rightarrow\infty}\sup_{x,x^{\prime}\in\mathbb{R}^{d}}1-c^{l}(x,x^{\prime})=0$ (fact 13). Using fact 14, we have uniformly over $B_{\epsilon}$ ,

\gamma_{l+1}=\gamma_{l}-s\gamma^{3/2}_{l}-b\gamma^{5/2}_{l}+O(\gamma^{7/2}_{l})

where $s,b>0$ , this yields

\displaystyle\gamma^{-1/2}_{l+1}=\gamma^{-1/2}_{l}+\frac{s}{2}+\frac{3s^{2}}{8}\gamma_{l}^{1/2}+(\frac{b}{2}+\frac{5}{16}s^{3})\gamma_{l}+O(\gamma_{l}^{3/2}).

Thus, letting $b^{\prime}=\frac{b}{2}+\frac{5}{16}s^{3}$ , as $l$ goes to infinity

\gamma^{-1/2}_{l+1}-\gamma^{-1/2}_{l}\sim\frac{s}{2},

and by summing and equivalence of positive divergent series

\gamma^{-1/2}_{l}\sim\frac{s}{2}l.

Moreover, since $\gamma^{-1/2}_{l+1}=\gamma^{-1/2}_{l}+\frac{s}{2}+\frac{3s^{2}}{8}\gamma_{l}^{1/2}+b^{\prime}\gamma_{l}+O(\gamma_{l}^{3/2})$ , using the same argument multiple times and inverting the formula yields

c^{l}(x,x^{\prime})=1-\frac{\kappa}{l^{2}}+\kappa^{\prime}\frac{\log(l)}{l^{3}}+\mathcal{O}(l^{-3})

where $\kappa=\frac{9\pi^{2}}{2}$ . Note that, by Appendix Lemma 1 (Section 1.1), the $\mathcal{O}$ bound can be chosen in a way that it does not depend on $(x,x^{\prime})$ , it depends only on $\epsilon$ ; this concludes the proof for the first part of the result.
Using fact 12, we have that

	$\displaystyle f^{\prime}(x)$	$\displaystyle=\frac{1}{\pi}\arcsin(x)+\frac{1}{2}$
		$\displaystyle=1-\frac{\sqrt{2}}{\pi}(1-x)^{1/2}+O((1-x)^{3/2}).$

Thus, it follows that

f^{\prime}(c^{l}(x,x^{\prime}))=1-\frac{3}{l}+\kappa^{\prime\prime}\frac{\log(l)}{l^{2}}+\mathcal{O}(l^{-2}).

for some universal constant $\kappa^{\prime\prime}$ uniformly over the set $B_{\epsilon}$ , which concludes the proof.
∎

We prove a similar result for an FFNN with Tanh activation.

Appendix Lemma 6 (Asymptotic behaviour of $c^{l}$ for Tanh).

Let $(\sigma_{b},\sigma_{w})\in EOC$ and $\epsilon\in(0,1)$ . We have

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|c^{l}(x,x^{\prime})-1+\frac{\kappa}{l}-\kappa(1-\kappa^{2}\zeta)\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

where $\kappa=\frac{2}{f^{\prime\prime}(1)}>0$ and $\zeta=\frac{f^{3}(1)}{6}>0$ . Moreover, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|f^{\prime}(c^{l}(x,x^{\prime}))-1+\frac{2}{l}-2(1-\kappa^{2}\zeta)\frac{\log(l)}{l^{2}}\right|=\mathcal{O}(l^{-2}).

Proof.

Let $(x,x^{\prime})\in B_{\epsilon}$ and $\lambda_{l}:=1-c^{l}(x,x^{\prime})$ . Using a Taylor expansion of $f$ near 1 (fact 7), there exist $\alpha,\zeta>0$ such that

\displaystyle\lambda_{l+1}

\displaystyle=\lambda_{l}-\alpha\lambda_{l}^{2}+\zeta\lambda_{l}^{3}+O(\lambda_{l}^{4})

Here also, we use the same technique as in the previous lemma. We have that

	$\displaystyle\lambda_{l+1}^{-1}$	$\displaystyle=\lambda_{l}^{-1}(1-\alpha\lambda_{l}+\zeta\lambda^{2}+O(\lambda_{l}^{3}))^{-1}=\lambda_{l}^{-1}(1+\alpha\lambda_{l}+(\alpha^{2}-\zeta)\lambda_{l}^{2}+O(\lambda_{l}^{3}))$
		$\displaystyle=\lambda_{l}^{-1}+\alpha+(\alpha^{2}-\zeta)\lambda_{l}+O(\lambda_{l}^{2}).$

By summing (divergent series), we have that $\lambda_{l}^{-1}\sim\alpha l$ . Therefore,

\displaystyle\lambda_{l+1}^{-1}-\lambda_{l}^{-1}-\alpha

\displaystyle=(\alpha^{2}-\beta)\alpha^{-1}l^{-1}+o(l^{-1})

By summing a second time, we obtain

\lambda_{l}^{-1}=\alpha l+(\alpha-\beta\alpha^{-1})\log(l)+o(\log(l)),

Using the same technique once again, we obtain

\lambda_{l}^{-1}=\alpha l+(\alpha-\beta\alpha^{-1})\log(l)+O(1).

This yields

\lambda_{l}=\alpha^{-1}l^{-1}-\alpha^{-1}(1-\alpha^{-2}\beta)\frac{\log(l)}{l^{2}}+O(l^{-2}).

In a similar fashion to the previous proof, we can force the upper bound in $\mathcal{O}$ to be independent of $x$ using Appendix Lemma 1. This way, the bound depends only on $\epsilon$ . This concludes the first part of the proof.

For the second part, observe that $f^{\prime}(x)=1+(x-1)f^{\prime\prime}(1)+O((x-1)^{2})$ , hence

f^{\prime}(c^{l}(x,x^{\prime}))=1-\frac{2}{l}+2(1-\alpha^{-2}\zeta)\frac{\log(l)}{l^{2}}+O(l^{-2})

which concludes the proof. ∎

1.4 Large depth behaviour of the correlation in CNNs

For CNNs, the infinite-width will always mean the limit of infinite number of channels. Recall that, by definition, $\hat{q}^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\sigma_{b}^{2}+\sigma_{w}^{2}\mathbb{E}[\phi(y^{l-1}_{1,\alpha}(x))\phi(y^{l-1}_{1,\alpha^{\prime}}(x^{\prime}))]$ and $q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\mathbb{E}[y^{l}_{i,\alpha}(x)y^{l}_{i,\alpha^{\prime}}(x^{\prime})]$ .

Unlike FFNN, neurons in the same channel are correlated since they share the same filters. Let $x,x^{\prime}$ be two inputs and $\alpha,\alpha^{\prime}$ two nodes in the same channel $i$ . Using Central Limit Theorem in the limit of large $n_{l}$ (number of channels), we have

q^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\mathbb{E}[y^{l}_{i,\alpha}(x)y^{l}_{i,\alpha^{\prime}}(x^{\prime})]=\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta\in ker}\mathbb{E}[\phi(y^{l-1}_{1,\alpha+\beta}(x))\phi(y^{l-1}_{1,\alpha^{\prime}+\beta}(x^{\prime}))]+\sigma_{b}^{2}

Let $c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ be the corresponding correlation. Since $q^{l}_{\alpha,\alpha}(x,x)$ converges exponentially to $q$ which depends neither on $x$ nor on $\alpha$ , the mean-field correlation as in [32, 16] is given by

c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\frac{1}{2k+1}\sum_{\beta\in ker}f(c^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}))

where $f(c)=\frac{\sigma_{w}^{2}\mathbb{E}[\phi(\sqrt{q}Z_{1})\phi(\sqrt{q}(cZ_{1}+\sqrt{1-c^{2}}Z_{2}))]+\sigma_{b}^{2}}{q}$ and $Z_{1},Z_{2}$ are independent standard normal variables. The dynamics of $c^{l}_{\alpha,\alpha^{\prime}}$ become similar to those of $c^{l}$ in an FFNN under assumption 1. We show this in the proof of Appendix Lemma 7.
In [33], authors studied only the limiting behaviour of correlations $c^{l}_{\alpha,\alpha^{\prime}}(x,x)$ (same input $x$ ), however, they do not study $c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ when $x\neq x^{\prime}$ . We do this in the following lemma, which will prove also useful for the main results of the paper.

Appendix Lemma 7 (Asymptotic behaviour of the correlation in CNN with Tanh).

We consider a CNN with Tanh activation function. Let $(\sigma_{b},\sigma_{w})\in(\mathbb{R}^{+})^{2}$ and $\epsilon\in(0,1)$ . Let $B_{\epsilon}=\{(x,x^{\prime})\in\mathbb{R}^{d}:\sup_{\alpha,\alpha^{\prime}}c^{1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})<1-\epsilon\}$ . The following statements hold

If $(\sigma_{b},\sigma_{w})$ are in the Ordered phase, then there exists $\beta>0$ such that

\sup_{(x,x^{\prime})\in\mathbb{R}^{d}}\sup_{\alpha,\alpha^{\prime}}|c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})-1|=\mathcal{O}(e^{-\beta l})

If $(\sigma_{b},\sigma_{w})$ are in the Chaotic phase, then for all $\epsilon>0$ there exists $\beta>0$ and $c\in(0,1)$ such that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\sup_{\alpha,\alpha^{\prime}}|c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})-c|=\mathcal{O}(e^{-\beta l})

Under Assumption 1, if $(\sigma_{b},\sigma_{w})\in EOC$ , then we have

\sup_{(x,x^{\prime})\in B_{\epsilon}}\sup_{\alpha,\alpha^{\prime}}\left|c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})-1+\frac{\kappa}{l}-\kappa(1-\kappa^{2}\zeta)\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

where $\kappa=\frac{2}{f^{\prime\prime}(1)}>0$ , $\zeta=\frac{f^{3}(1)}{6}>0$ , and $f$ is the correlation function given in Fact 5.

We prove statements $1$ and $2$ for general inputs, i.e. without using Assumption 1. The third statement requires Assumption 1.

Proof.

Let $(x,x^{\prime})\in\mathbb{R}^{d}$ . Without using assumption 1, we have that

c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=\frac{1}{2k+1}\sum_{\beta\in ker}f(c^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}))

Writing this in matrix form yields

C_{l}=\frac{1}{2k+1}Uf(C_{l-1})

where $C_{l}=((c^{l}_{\alpha,\alpha+\beta}(x,x^{\prime}))_{\alpha\in[0:N-1]})_{\beta\in[0:N-1]}$ is a vector in $\mathbb{R}^{N^{2}}$ , $U$ is a convolution matrix and $f$ is applied element-wise. As an example, for $k=1$ , $U$ is given by

U=\begin{bmatrix}1&1&0&...&0&1\\ 1&1&1&0&\ddots&0\\ 0&1&1&1&\ddots&0\\ 0&0&1&1&\ddots&0\\ &\ddots&\ddots&\ddots&\ddots&\\ 1&0&\ldots&0&1&1\\ \end{bmatrix}

For general $k$ , $U$ is a Circulant symmetric matrix with eigenvalues $\lambda_{1}>\lambda_{2}\geq\lambda_{3}...\geq\lambda_{N^{2}}$ . The largest eigenvalue of $U$ is given by $\lambda_{1}=2k+1$ and its equivalent eigenspace is generated by the vector $e_{1}=\frac{1}{N}(1,1,...,1)\in\mathbb{R}^{N^{2}}$ . This yields

(1+2k)^{-l}U^{l}=e_{1}e_{1}^{T}+O(e^{-\beta l})

where $\beta=\log(\frac{\lambda_{1}}{\lambda_{2}})$ .
This provides another justification to Assumption 1; as $l$ grows, and assuming that $C_{l}\rightarrow e_{1}$ (which we show in the remainder of this proof), $C_{l}$ exhibits a self-averaging property since $C_{l}\approx\frac{1}{2k+1}UC_{l-1}$ . This system concentrates around the average value of the entries of $C_{l}$ as $l$ grows. Since the variances converge to a constant $q$ as $l$ goes to infinity (fact 15), this approximation implies that the entries of $C_{l}$ become almost equal as $l$ goes to infinity, thus making assumption 1 almost satisfied in deep layers. Let us now prove the statements.

Let $(\sigma_{b},\sigma_{w})$ be in the Ordered phase, $(x,x^{\prime})\in\mathbb{R}^{d}$ and $c^{l}_{m}=\min_{\alpha,\alpha^{\prime}}c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ . Using the fact that $f$ is non-decreasing, we have that $c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})\geq\frac{1}{2k+1}\sum_{\beta\in ker}c^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}))\geq c^{l-1}_{m}$ . Taking the minimum again over $\alpha,\alpha^{\prime}$ , we have $c^{l}_{m}\geq c^{l-1}_{m}$ , therefore $c^{l}_{m}$ is non-decreasing and converges to the unique fixed point of $f$ which is $c=1$ . This proves that $\sup_{\alpha,\alpha^{\prime}}|c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})-1|\rightarrow 0$ . Moreover, the convergence rate is exponential using the fact that (fact 16) $0<f^{\prime}(1)<1$ . To see this, observe that

\sup_{\alpha,\alpha^{\prime}}|1-c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})|\leq\left(\sup_{\zeta\in[c^{l-1}_{m},1]}f^{\prime}(\zeta)\right)\times\sup_{\alpha,\alpha^{\prime}}|1-c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})|

Knowing that $\sup_{\zeta\in[c^{l-1}_{m},1]}f^{\prime}(\zeta)\rightarrow f^{\prime}(1)<1$ , we conclude. Moreover, the convergence is uniform in $(x,x^{\prime})$ since the convergence rate depends only on $f^{\prime}(1)$ .

2.

Let $\epsilon\in(0,1)$ . In the chaotic phase, the only difference is the limit $c=c_{1}<1$ and the Supremum is taken over $B_{\epsilon}$ to avoid points where $c^{1}(x,x^{\prime})=1$ . In the Chaotic phase (fact 16), $f$ has two fixed points, 1 is an unstable fixed point and $c_{1}\in(0,1)$ which is the unique stable fixed point. We conclude by following the same argument.
3.

Let $\epsilon\in(0,1)$ and $(\sigma_{b},\sigma_{w})\in$ EOC. Using the same argument of monotony as in the previous cases and that $f$ has 1 as unique fixed point, we have that $\lim_{l\rightarrow\infty}\sup_{x,x^{\prime}}\sup_{\alpha,\alpha^{\prime}}|1-c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})|=0$ .
From fact 7, the Taylor expansion of $f$ near 1 is given by

$f(c)=c+\alpha(1-c)^{2}-\zeta(1-c)^{3}+\mathcal{O}((1-c)^{4}).$

where $\alpha=\frac{f^{\prime\prime}(1)}{2}$ and $\zeta=\frac{f^{(3)}(1)}{6}$ . Using fact 6, we know that $f^{(k)}(1)=\sigma_{w}^{2}q^{k-1}\mathbb{E}[\phi^{(k)}(\sqrt{q}Z)^{2}]$ . Therefore, we have $\alpha>0$ , and $\zeta<0$ .
Under assumption 1, it is straightforward that for all $\alpha,\alpha^{\prime}$ , and $l\geq 1$

$c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})=c^{l}(x,x^{\prime})$

i.e. $c^{l}_{\alpha,\alpha^{\prime}}$ are equal for all $\alpha,\alpha^{\prime}$ . The dynamics of $c^{l}(x,x^{\prime})$ are exactly the dynamics of the correlation in an FFNN. We conclude using Appendix Lemma 6.

∎

It is straightforward that the previous Appendix Lemma extend to ReLU activation, with slightly different dynamics. In this case, we use Appendix Lemma 5 to conclude for the third statement.

Appendix Lemma 8 (Asymptotic behaviour of the correlation in CNN with ReLU-like activation functions).

We consider a CNN with ReLU activation. Let $(\sigma_{b},\sigma_{w})\in(\mathbb{R}^{+})^{2}$ . Let $(\sigma_{b},\sigma_{w})\in(\mathbb{R}^{+})^{2}$ and $\epsilon\in(0,1)$ . The following statements hold

If $(\sigma_{b},\sigma_{w})$ are in the Ordered phase, then there exists $\beta>0$ such that

\sup_{(x,x^{\prime})\in\mathbb{R}^{d}}\sup_{\alpha,\alpha^{\prime}}|c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})-1|=\mathcal{O}(e^{-\beta l})

If $(\sigma_{b},\sigma_{w})$ are in the Chaotic phase, then there exists $\beta>0$ and $c\in(0,1)$ such that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\sup_{\alpha,\alpha^{\prime}}|c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})-c|=\mathcal{O}(e^{-\beta l})

Under Assumption 1, if $(\sigma_{b},\sigma_{w})\in EOC$ , then

\sup_{(x,x^{\prime})\in B_{\epsilon}}\sup_{\alpha,\alpha^{\prime}}\left|c^{l}(x,x^{\prime})-1+\frac{\kappa}{l^{2}}-\kappa^{\prime}\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

where $\kappa,\kappa^{\prime}>0$ are universal constants.

Proof.

The proof is similar to the case of Tanh in Appendix Lemma 7. The only difference is that we use Appendix Lemma 5 to conclude for the third statement. ∎

1.5 A technical lemma for ResNet

Now we prove a result on the asymptotic behaviour of $c^{l}$ for a ResNet architecture.

Appendix Lemma 9 (Asymptotic expansion of $c^{l}$ for ResNet).

Let $\epsilon\in(0,1)$ and $\sigma_{w}>0$ . We have for FFNN

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|c^{l}(x,x^{\prime})-1+\frac{\kappa_{\sigma_{w}}}{l^{2}}-\kappa_{\sigma_{w}}^{\prime}\frac{\log(l)}{l^{3}}\right|=\mathcal{O}(l^{-3})

where $\kappa_{\sigma_{w}},\kappa_{\sigma_{w}}^{\prime}>0$ are two constants that depend on $\sigma_{w}$ .
Moreover, we have that

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|f^{\prime}(c^{l}(x,x^{\prime}))-1+\frac{3(1+\frac{2}{\sigma_{w}^{2}})}{l}-\kappa_{\sigma_{W}}^{\prime\prime}\frac{\log(l)}{l^{2}}\right|=\mathcal{O}(l^{-2}).

where $f$ is the ReLU correlation function given in fact 12 and $\kappa_{\sigma_{W}}^{\prime\prime}>0$ is a constant that depends on $\sigma_{w}$ .
Moreover, this result holds also for CNNs where the supremum should be replaced by $\sup_{(x,x^{\prime})\in B_{\epsilon}}\sup_{\alpha,\alpha^{\prime}}$ .

Proof.

We first prove the result for ResNet with fully connected layers, the extension to convolutional layers is straightforward. Let $\epsilon\in(0,1)$ .

•

Let $x\neq x^{\prime}\in\mathbb{R}^{d}$ , and $c^{l}:=c^{l}(x,x^{\prime})$ . It is straightforward that the variance terms follow the recursive form

q^{l}(x,x)=q^{l-1}(x,x)+\sigma_{w}^{2}/2q^{l-1}(x,x)=(1+\sigma_{w}^{2}/2)^{l-1}q^{1}(x,x)

Leveraging this observation, we have that

c^{l+1}=\frac{1}{1+\alpha}c^{l}+\frac{\alpha}{1+\alpha}f(c^{l}),

where $f$ is the ReLU correlation function given in fact 12 and $\alpha=\frac{\sigma_{w}^{2}}{2}$ . Recall that

f(c)=\frac{1}{\pi}c\,\arcsin(c)+\frac{1}{\pi}\sqrt{1-c^{2}}+\frac{1}{2}c.

As in the proof of Appendix Lemma 5, let $\gamma_{l}=1-c^{l}$ , therefore, using Taylor expansion of $f$ near 1 given in fact 14 yields

\gamma_{l+1}=\gamma_{l}-\frac{\alpha s}{1+\alpha}\gamma_{l}^{3/2}-\frac{\alpha b}{1+\alpha}\gamma_{l}^{5/2}+O(\gamma_{l}^{7/5}).

This asymptotic expansion is similar to the one in the proof of Appendix Lemma 5 with different coefficients $s^{\prime}=\frac{\alpha s}{1+\alpha}$ and $b^{\prime}=\frac{\alpha b}{1+\alpha}$ . We conclude by following the same machinery. The second result also follows from this similarity as it is also a result of this asymptotic expansion.

•

Under Assumption 1, the result holds for CNN.

∎

The next theorem shows that no matter what the choice of $\sigma_{w}>0$ , the normalized NTK of a ResNet will always have a subexponential convergence rate to a limiting $\bar{K}^{\infty}_{res}$ .

1.6 A technical lemma for scaled ResNet

Appendix Lemma 10.

Consider a Residual Neural Network with the following forward propagation equations

y^{l}(x)=y^{l-1}(x)+\frac{1}{\sqrt{l}}\mathcal{F}(w^{l},y^{l-1}(x)),\quad l\geq 2.

(6)

where $\mathcal{F}$ is either a convolutional or dense layer (equations 10 and 11) with ReLU activation. Then there exists $\zeta,\nabla>0$ such that for all $\epsilon\in(0,1)$

\sup_{(x,x^{\prime})\in B_{\epsilon}}\left|1-c^{l}(x,x^{\prime})-\frac{\zeta}{\log(l)^{2}}+\frac{\nabla}{\log(l)^{3}}\right|=o\left(\frac{1}{\log(l)^{3}}\right)

where the bound ‘ $o$ ’ depends only on $\epsilon$ .
For CNN, under Assumption 1, the result holds and the supremum is taken also over $\alpha,\alpha^{\prime}$ , i.e.

\sup_{(x,x^{\prime})\in B_{\epsilon}}\sup_{\alpha,\alpha^{\prime}}\left|1-c^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})-\frac{\zeta}{\log(l)^{2}}+\frac{\nabla}{\log(l)^{3}}\right|=o\left(\frac{1}{\log(l)^{3}}\right)

Proof.

As for the previous results, we only prove the result for a ResNet with fully-connected layers, the proof is similar for convolutional layers under 1.

Let $\epsilon\in(0,1)$ and $(x,x^{\prime})\in B_{\epsilon}$ be two inputs and denote by $c^{l}:=c^{l}(x,x^{\prime})$ . Following the same machinery as in the proof of Appendix Lemma 9, we have that

c^{l}=\frac{1}{1+\alpha_{l}}c^{l-1}+\frac{\alpha_{l}}{1+\alpha_{l}}f(c^{l-1})

where $\alpha_{l}=\frac{\sigma_{w}^{2}}{2l}$ . Using Fact 12, it is straightforward that $f^{\prime}\geq 0$ , hence $f$ is non-decreasing. Hence, $c^{l}\geq c^{l-1}$ and $c^{l}$ converges to a fixed point $c$ . Let us prove that $c=1$ . By contradiction, suppose $c<1$ so that $f(c)-c>0$ ( $f$ has a unique fixed point which is $1$ ). This yields

c^{l}-c=c^{l-1}-c+\frac{f(c)-c}{l}+\mathcal{O}\left(\frac{c^{l}-c}{l}\right)+\mathcal{O}\left(l^{-2}\right)

by summing, this leads to $c^{l}-c\sim(f(c)-c)\log(l)$ which is absurd since $f(c)\neq c$ ( $f$ admits only 1 as a fixed point). We conclude that $c=1$ . Using the fact that $f$ is non-decreasing, it is easy to conclude that the convergence is uniform over $B_{\epsilon}$ .

Now let us find the asymptotic expansion of $1-c^{l}$ . Recall the Taylor expansion of the correlation function $f$ near 1 given in Fact 14

f(c)\underset{c\rightarrow 1-}{=}c+s(1-c)^{3/2}+b(1-c)^{5/2}+\mathcal{O}((1-c)^{7/2})

(7)

where $s=\frac{2\sqrt{2}}{3\pi}$ and $b=\frac{\sqrt{2}}{30\pi}$ . Letting $\gamma_{l}=1-c^{l}$ and $\delta_{l}=\frac{\alpha_{l}}{1+\alpha_{l}}$ , we obtain

\gamma_{l}=\gamma_{l-1}-s\delta_{l}\gamma_{l-1}^{3/2}-b\delta_{l}\gamma_{l-1}^{5/2}+\mathcal{O}(\delta_{l}\gamma_{l-1}^{7/5}).

which yields

\gamma^{-1/2}_{l}=\gamma^{-1/2}_{l-1}+\frac{s}{2}\delta_{l}+\frac{3}{8}s^{2}\delta_{l}^{2}\gamma_{l-1}^{1/2}+\left(\frac{b}{2}\delta_{l}+\frac{5}{16}\delta_{l}^{3}s^{3}\right)\gamma_{l-1}+O(\delta_{l}\gamma_{l-1}^{3/2}).

(8)

therefore, we have that

\gamma_{l}^{-1/2}\sim\frac{s\sigma_{w}^{2}}{4}\log(l)

and $1-c^{l}\sim\frac{\zeta}{\log(l)^{2}}$ where $\zeta=16/s^{2}\sigma_{w}^{4}$ .

By pushing the asymptotic expansion to the next order, we obtain

1-c^{l}=\frac{\zeta}{\log(l)^{2}}-\frac{\nabla}{\log(l)^{3}}+o\left(\frac{1}{\log(l)^{3}}\right)

where $\nabla>0$ . the ‘ $o$ ’ holds uniformly for $(x,x^{\prime})\in B_{\epsilon}$ as in the proof of Appendix Lemma 5.

This result holds for a ResNet with CNN layers under Assumption 1 since the dynamics are the same in this case.

∎

2 Proofs of the lemmas 1, 2, 3 4

In this section, we provide proofs for for the recursive formulas satisfied by the NTK, i.e. lemmas 1, 2, 3 4.

2.1 Proofs of non-ResNet lemmas

Recall that lemma 1 in the paper is a generalization of theorem 1 in [21] and is reminded here. The proof is simple and follows similar induction techniques as in [21].

Lemma 1 (Generalization of Th. 1 in [21]).

Consider an FFNN of the form (10). Then, as $n_{1},n_{2},...,n_{L-1}\rightarrow\infty$ , we have for all $x,x^{\prime}\in\mathbb{R}^{d}$ , $i,i^{\prime}\leq n_{L}$ , $K^{L}_{ii^{\prime}}(x,x^{\prime})=\delta_{ii^{\prime}}K^{L}(x,x^{\prime})$ , where $K^{L}(x,x^{\prime})$ is given by the recursive formula

K^{L}(x,x^{\prime})=\dot{q}^{L}(x,x^{\prime})K^{L-1}(x,x^{\prime})+q^{L}(x,x^{\prime}),

where $q^{l}(x,x^{\prime})=\sigma_{b}^{2}+\sigma_{w}^{2}\mathbb{E}[\phi(y_{1}^{l-1}(x))\phi(y_{1}^{l-1}(x^{\prime}))]$ and $\dot{q}^{l}(x,x^{\prime})=\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(y_{1}^{l-1}(x))\phi^{\prime}(y_{1}^{l-1}(x^{\prime}))]$ .

Proof.

The proof for general $\sigma_{w}$ is analogous to the case when $\sigma_{w}=1$ ([21]). The result is proved by by induction. We denote by $\partial_{\theta}y$ the gradient of $y$ with respect to $\theta$ .

It is straightforward that

K^{1}_{ii^{\prime}}(x,x^{\prime})=\delta_{ii^{\prime}}K^{1}(x,x^{\prime})

where $K^{1}(x,x^{\prime})=\frac{\sigma_{w}^{2}}{d}x\cdot x^{\prime}+\sigma_{b}^{2}$ . For $l\geq 2$ and $i\in[1:n_{l}]$

\displaystyle\partial_{\theta_{1:l}}y^{l+1}_{i}(x)

\displaystyle=\frac{\sigma_{w}}{\sqrt{n_{l}}}\sum_{j=1}^{n_{l}}w^{l+1}_{ij}\phi^{\prime}(y^{l}_{j}(x))\partial_{\theta_{1:l}}y^{l}_{j}(x).

and,

\displaystyle(\partial_{\theta_{1:l}}y^{l+1}_{i}(x))(\partial_{\theta_{1:l}}y^{l+1}_{i^{\prime}}(x^{\prime}))^{t}

\displaystyle=\frac{\sigma_{w}^{2}}{n_{l}}\sum_{j,j^{\prime}}^{n_{l}}w^{l+1}_{ij}w^{l+1}_{i^{\prime}j^{\prime}}\phi^{\prime}(y^{l}_{j}(x))\phi^{\prime}(y^{l}_{j^{\prime}}(x^{\prime}))\partial_{\theta_{1:l}}y^{l}_{j}(x)(\partial_{\theta_{1:l}}y^{l}_{j^{\prime}}(x^{\prime}))^{t}

Therefore, when $l=2$ , we have that

	$\displaystyle(\partial_{\theta_{1}}y^{2}_{i}(x))(\partial_{\theta_{1}}y^{2}_{i^{\prime}}(x^{\prime}))^{t}$	$\displaystyle=\frac{\sigma_{w}^{2}}{n_{1}}\sum_{j,j^{\prime}}^{n_{1}}w^{2}_{ij}w^{2}_{i^{\prime}j^{\prime}}\phi^{\prime}(y^{1}_{j}(x))\phi^{\prime}(y^{1}_{j^{\prime}}(x^{\prime}))\partial_{\theta_{1}}y^{1}_{j}(x)(\partial_{\theta_{1}}y^{1}_{j^{\prime}}(x^{\prime}))^{t}$
		$\displaystyle=\frac{\sigma_{w}^{2}}{n_{1}}K^{1}(x,x^{\prime})\sum_{j}^{n_{1}}w^{2}_{ij}w^{2}_{i^{\prime}j}\phi^{\prime}(y^{1}_{j}(x))\phi^{\prime}(y^{1}_{j^{\prime}}(x^{\prime}))$

Taking $n_{1}$ to infinity, the law of large numbers yields

\displaystyle(\partial_{\theta_{1}}y^{2}_{i}(x))(\partial_{\theta_{1}}y^{2}_{i^{\prime}}(x^{\prime}))^{t}\to\delta_{ii^{\prime}}K^{1}(x,x^{\prime})\dot{q}^{2}(x,x^{\prime})

We also have that for all $l\geq 2$

	$\displaystyle(\partial_{w^{l+1}}y^{l+1}_{i}(x))(\partial_{w^{l+1}}y^{l+1}_{i}(x^{\prime}))^{t}$	$\displaystyle+(\partial_{b^{l+1}}y^{l+1}_{i}(x))(\partial_{b^{l+1}}y^{l+1}_{i}(x^{\prime}))^{t}=\frac{\sigma_{w}^{2}}{n_{l}}\sum_{j}\phi(y^{l}_{j}(x))\phi(y^{l}_{j}(x^{\prime}))+\sigma_{b}^{2}$
		$\displaystyle\underset{n_{l}\rightarrow\infty}{\rightarrow}\sigma_{w}^{2}\mathbb{E}[\phi(y^{l}_{i}(x))\phi(y^{l}_{i}(x^{\prime}))]+\sigma_{b}^{2}=q^{l+1}(x,x^{\prime}).$

we conclude that the statement is true for $l=2$ . Now assume that the result is true for $l\in{2,3,\dots,L}$ , let us prove it for $L+1$ . Using the induction hypothesis, namely that as $n_{0},n_{1},...,n_{L-1}\rightarrow\infty$ sequentially, for all $j,j^{\prime}\leq n_{l}$ and all $x,x^{\prime}$

\partial_{\theta_{1:L}}y^{L}_{j}(x)(\partial_{\theta_{1:L}}y^{L}_{j^{\prime}}(x^{\prime}))^{t}\rightarrow K^{L}(x,x^{\prime})\mathbf{1}_{j=j^{\prime}}

Hence, given $n_{L}$ , as $n_{0},n_{1},...,n_{l-1}\rightarrow\infty$ sequentially, we have that

	$\displaystyle\frac{\sigma_{w}^{2}}{n_{L}}\sum_{j,j^{\prime}}^{n_{L}}w^{L+1}_{ij}w^{L+1}_{ij^{\prime}}\phi^{\prime}(y^{L}_{j}(x))\phi^{\prime}(y^{L}_{j^{\prime}}(x^{\prime}))$	$\displaystyle\partial_{\theta_{1:L}}y^{L}_{j}(x)(\partial_{\theta_{1:L}}y^{L}_{j^{\prime}}(x^{\prime}))^{t}\rightarrow$
		$\displaystyle\frac{\sigma_{w}^{2}}{n_{L}}\sum_{j}^{n_{L}}(w^{L+1}_{ij})^{2}\phi^{\prime}(y^{L}_{j}(x))\phi^{\prime}(y^{L}_{j}(x^{\prime}))K^{L}(x,x^{\prime})$

and letting $n_{L}$ go to infinity, the law of large numbers implies that

\frac{\sigma_{w}^{2}}{n_{L}}\sum_{j}^{n_{L}}(w^{L+1}_{ij})^{2}\phi^{\prime}(y^{L}_{j}(x))\phi^{\prime}(y^{L}_{j}(x^{\prime}))K^{L}(x,x^{\prime})\rightarrow\dot{q}^{L+1}(x,x^{\prime})K^{L}(x,x^{\prime}).

Moreover, we have that

	$\displaystyle(\partial_{w^{L+1}}y^{L+1}_{i}(x))(\partial_{w^{L+1}}y^{L+1}_{i}(x^{\prime}))^{t}$	$\displaystyle+(\partial_{b^{L+1}}y^{L+1}_{i}(x))(\partial_{b^{L+1}}y^{L+1}_{i}(x^{\prime}))^{t}=\frac{\sigma_{w}^{2}}{n_{L}}\sum_{j}\phi(y^{L}_{j}(x))\phi(y^{L}_{j}(x^{\prime}))+\sigma_{b}^{2}$
		$\displaystyle\underset{n_{L}\rightarrow\infty}{\rightarrow}\sigma_{w}^{2}\mathbb{E}[\phi(y^{L}_{i}(x))\phi(y^{L}_{i}(x^{\prime}))]+\sigma_{b}^{2}=q^{L+1}(x,x^{\prime}).$

which completes the proof.

∎

We now provide the proof of recursive formula satisfied by the NTK of a CNN. The proof techniques are similar to Lemma 1.

Lemma 2 (Infinite-width dynamics of the NTK of a CNN).

Consider a CNN of the form (11), then we have that for all $x,x^{\prime}\in\mathbb{R}^{d}$ , $i,i^{\prime}\leq n_{1}$ and $\alpha,\alpha^{\prime}\in[0:M-1]$

K^{1}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}\big(\frac{\sigma_{w}^{2}}{n_{0}(2k+1)}[x,x^{\prime}]_{\alpha,\alpha^{\prime}}+\sigma_{b}^{2}\big)

For $l\geq 2$ , as $n_{1},n_{2},...,n_{l-1}\rightarrow\infty$ recursively, we have for all $i,i^{\prime}\leq n_{l}$ , $\alpha,\alpha^{\prime}\in[0:M-1]$ , $K^{l}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}K^{l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ , where $K^{l}_{\alpha,\alpha^{\prime}}$ is given by the recursive formula

\displaystyle K^{l}_{\alpha,\alpha^{\prime}}

\displaystyle=\frac{1}{2k+1}\sum_{\beta\in ker_{l}}\Psi^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}

where $\Psi^{l-1}_{\alpha,\alpha^{\prime}}=\dot{q}^{l}_{\alpha,\alpha^{\prime}}K^{l-1}_{\alpha,\alpha^{\prime}}+\hat{q}^{l}_{\alpha,\alpha^{\prime}}$ , and $\hat{q}^{l}_{\alpha,\alpha},\dot{q}^{l}_{\alpha,\alpha^{\prime}}$ are defined in lemma 1, with $y_{1,\alpha}^{l-1}(x),y_{1,\alpha^{\prime}}^{l-1}(x^{\prime})$ in place of $y_{1}^{l-1}(x),y_{1}^{l-1}(x^{\prime})$ .

Proof.

Here we omit the first step in the induction argument, i.e. to show that the result holds for $l=2$ . This is straightforward and analogous to the case of $l=2$ in the proof of Lemma 1. We just illustrate small differences in the induction hypothesis for CNNs.

Let $x,x^{\prime}$ be two inputs. We have that

	$\displaystyle y^{1}_{i,\alpha}(x)$	$\displaystyle=\frac{\sigma_{w}}{\sqrt{v_{1}}}\sum_{j=1}^{n_{0}}\sum_{\beta\in ker_{1}}w^{1}_{i,j,\beta}x_{j,\alpha+\beta}+\sigma_{b}b^{1}_{i}$
	$\displaystyle y^{l}_{i,\alpha}(x)$	$\displaystyle=\frac{\sigma_{w}}{\sqrt{v_{l}}}\sum_{j=1}^{n_{l-1}}\sum_{\beta\in ker_{l}}w^{l}_{i,j,\beta}\phi(y^{l-1}_{j,\alpha+\beta}(x))+\sigma_{b}b^{l}_{i}$

therefore

	$\displaystyle K^{1}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})$	$\displaystyle=\sum_{r}\left(\sum_{j}\sum_{\beta}\frac{\partial y^{1}_{i,\alpha}(x)}{\partial w^{1}_{r,j,\beta}}\frac{\partial y^{1}_{i^{\prime},\alpha^{\prime}}(x)}{\partial w^{1}_{r,j,\beta}}\right)+\frac{\partial y^{1}_{i,\alpha}(x)}{\partial b^{1}_{r}}\frac{\partial y^{1}_{i^{\prime},\alpha^{\prime}}(x)}{\partial b^{1}_{r}}$
		$\displaystyle=\delta_{ii^{\prime}}\left(\frac{\sigma_{w}^{2}}{n_{0}(2k+1)}\sum_{j}\sum_{\beta}x_{j,\alpha+\beta}x_{j,\alpha^{\prime}+\beta}+\sigma_{b}^{2}\right)$

Assume the result is true for $l-1$ , let us prove it for $l$ . Let $\theta_{1:l-1}$ be model weights and bias in the layers 1 to $l-1$ . Let $\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)=\frac{\partial y^{l}_{i,\alpha}(x)}{\partial\theta_{1:l-1}}$ . We have that

\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)=\frac{\sigma_{w}}{\sqrt{n_{l-1}(2k+1)}}\sum_{j}\sum_{\beta}w^{l}_{i,j,\beta}\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha+\beta}(x)

this yields

		$\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}=$
		$\displaystyle\frac{\sigma_{w}^{2}}{n_{l-1}(2k+1)}\sum_{j,j^{\prime}}\sum_{\beta,\beta^{\prime}}w^{l}_{i,j,\beta}w^{l}_{i^{\prime},j^{\prime},\beta^{\prime}}\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})\phi^{\prime}(y^{l-1}_{j^{\prime},\alpha^{\prime}+\beta})\partial_{\theta_{1:l-1}}y^{l-1}_{j,\alpha+\beta}(x)\partial_{\theta_{1:l-1}}y^{l-1}_{j^{\prime},\alpha^{\prime}+\beta}(x)^{T}$

as $n_{1},n_{2},...,n_{l-2}\rightarrow\infty$ and using the induction hypothesis, we have

		$\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}\rightarrow$
		$\displaystyle\frac{\sigma_{w}^{2}}{n_{l-1}(2k+1)}\sum_{j}\sum_{\beta,\beta^{\prime}}w^{l}_{i,j,\beta}w^{l}_{i^{\prime},j,\beta^{\prime}}\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})\phi^{\prime}(y^{l-1}_{j,\alpha^{\prime}+\beta})K^{l-1}_{(j,\alpha+\beta),(j,\alpha^{\prime}+\beta)}(x,x^{\prime})$

note that $K^{l-1}_{(j,\alpha+\beta),(j,\alpha^{\prime}+\beta)}(x,x^{\prime})=K^{l-1}_{(1,\alpha+\beta),(1,\alpha^{\prime}+\beta)}(x,x^{\prime})$ for all $j$ since the variables are iid across the channel index $j$ .

Now letting $n_{l-1}\rightarrow\infty$ , we have that

		$\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}\rightarrow$
		$\displaystyle\delta_{ii^{\prime}}\big(\frac{1}{(2k+1)}\sum_{\beta,\beta^{\prime}}\dot{q}^{l}_{\alpha+\beta,\alpha^{\prime}+\beta}K^{l-1}_{(1,\alpha+\beta),(1,\alpha^{\prime}+\beta)}(x,x^{\prime})\big)$

We conclude using the fact that

\partial_{\theta_{l}}y^{l}_{i,\alpha}(x)\partial_{\theta_{l}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}\rightarrow\delta_{ii^{\prime}}(\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta}\mathbb{E}[\phi(y^{l-1}_{\alpha+\beta}(x))\phi(y^{l-1}_{\alpha^{\prime}+\beta}(x^{\prime}))]+\sigma_{b}^{2})

∎

2.2 Lemmas for ResNet NTK

Here we provide the proofs for the recursive formulas of the NTK of a ResNet. The techniques are the same, and our goal here is to show the role of the residual term in the induction argument.

Lemma 3 (NTK of a ResNet with Fully Connected layers in the infinite-width limit).

Let $x,x^{\prime}$ be two inputs and $K^{res,1}$ be the exact NTK for the Residual Network with 1 layer. Then, we have

•

For the first layer (without residual connections), we have for all $x,x^{\prime}\in\mathbb{R}^{d}$

K^{res,1}_{ii^{\prime}}(x,x^{\prime})=\delta_{ii^{\prime}}\left(\sigma_{b}^{2}+\frac{\sigma_{w}^{2}}{d}x\cdot x^{\prime}\right),

where $x\cdot x^{\prime}$ is the inner product in $\mathbb{R}^{d}$ .

•

For $l\geq 2$ , as $n_{1},n_{2},...,n_{L-1}\rightarrow\infty$ , we have for all $i,i^{\prime}\in[1:n_{l}]$ , $K^{res,l}_{ii^{\prime}}(x,x^{\prime})=\delta_{ii^{\prime}}K^{l}_{res}(x,x^{\prime})$ , where $K^{l}_{res}(x,x^{\prime})$ is given by the recursive formula have for all $x,x^{\prime}\in\mathbb{R}^{d}$ and $l\geq 2$ , as $n_{1},n_{2},...,n_{l}\rightarrow\infty$ recursively, we have

K_{res}^{l}(x,x^{\prime})=K_{res}^{l-1}(x,x^{\prime})(\dot{q}^{l}(x,x^{\prime})+1)+\hat{q}^{l}(x,x^{\prime}).

Proof.

The first result is the same as in the FFNN case since we assume there is no residual connections between the first layer and the input. We prove the second result by induction.

•

Let $x,x^{\prime}\in\mathbb{R}^{d}$ . We have

K^{1}_{res}(x,x^{\prime})=\sum_{j}\frac{\partial y^{1}_{1}(x)}{\partial w^{1}_{1j}}\frac{\partial y^{1}_{1}(x)}{\partial w^{1}_{1j}}+\frac{\partial y^{1}_{1}(x)}{\partial b^{1}_{1}}\frac{\partial y^{1}_{1}(x)}{\partial b^{1}_{1}}=\frac{\sigma_{w}^{2}}{d}x\cdot x^{\prime}+\sigma_{b}^{2}.

•

The proof is similar to the FeedForward network NTK. For $l\geq 2$ and $i\in[1:n_{l}]$

\displaystyle\partial_{\theta_{1:l}}y^{l+1}_{i}(x)

\displaystyle=\partial_{\theta_{1:l}}y^{l}_{i}(x)+\frac{\sigma_{w}}{\sqrt{n_{l}}}\sum_{j=1}^{n_{l}}w^{l+1}_{ij}\phi^{\prime}(y^{l}_{j}(x))\partial_{\theta_{1:l}}y^{l}_{j}(x).

Therefore, we obtain

	$\displaystyle(\partial_{\theta_{1:l}}y^{l+1}_{i}(x))$	$\displaystyle(\partial_{\theta_{1:l}}y^{l+1}_{i}(x^{\prime}))^{t}=(\partial_{\theta_{1:l}}y^{l}_{i}(x))(\partial_{\theta_{1:l}}y^{l}_{i}(x^{\prime}))^{t}$
		$\displaystyle+\frac{\sigma_{w}^{2}}{n_{l}}\sum_{j,j^{\prime}}^{n_{l}}w^{l+1}_{ij}w^{l+1}_{ij^{\prime}}\phi^{\prime}(y^{l}_{j}(x))\phi^{\prime}(y^{l}_{j^{\prime}}(x^{\prime}))\partial_{\theta_{1:l}}y^{l}_{j}(x)(\partial_{\theta_{1:l}}y^{l}_{j^{\prime}}(x^{\prime}))^{t}+I$

where

I=\frac{\sigma_{w}}{\sqrt{n_{l}}}\sum_{j=1}^{n_{l}}w^{l+1}_{ij}(\phi^{\prime}(y^{l}_{j}(x))\partial_{\theta_{1:l}}y^{l}_{i}(x)(\partial_{\theta_{1:l}}y^{l}_{j}(x^{\prime}))^{t}+\phi^{\prime}(y^{l}_{j}(x^{\prime}))\partial_{\theta_{1:l}}y^{l}_{j}(x)(\partial_{\theta_{1:l}}y^{l}_{i}(x^{\prime}))^{t}).

Using the induction hypothesis, as $n_{0},n_{1},...,n_{l-1}\rightarrow\infty$ , we have that

		$\displaystyle(\partial_{\theta_{1:l}}y^{l+1}_{i}(x))(\partial_{\theta_{1:l}}y^{l+1}_{i}(x^{\prime}))^{t}+\frac{\sigma_{w}^{2}}{n_{l}}\sum_{j,j^{\prime}}^{n_{l}}w^{l+1}_{ij}w^{l+1}_{ij^{\prime}}\phi^{\prime}(y^{l}_{j}(x))\phi^{\prime}(y^{l}_{j^{\prime}}(x^{\prime}))\partial_{\theta_{1:l}}y^{l}_{j}(x)(\partial_{\theta_{1:l}}y^{l}_{j^{\prime}}(x^{\prime}))^{t}+I$
		$\displaystyle\rightarrow K^{l}_{res}(x,x^{\prime})+\frac{\sigma_{w}^{2}}{n_{l}}\sum_{j}^{n_{l}}(w^{l+1}_{ij})^{2}\phi^{\prime}(y^{l}_{j}(x))\phi^{\prime}(y^{l}_{j}(x^{\prime}))K^{l}_{res}(x,x^{\prime})+I^{\prime},$

where $I^{\prime}=\frac{\sigma_{w}^{2}}{n_{l}}w^{l+1}_{ii}(\phi^{\prime}(y^{l}_{i}(x))+\phi^{\prime}(y^{l}_{i}(x^{\prime})))K^{l}_{res}(x,x^{\prime}).$

As $n_{l}\rightarrow\infty$ , we have that $I^{\prime}\rightarrow 0$ . Using the law of large numbers, as $n_{l}\rightarrow\infty$

\frac{\sigma_{w}^{2}}{n_{l}}\sum_{j}^{n_{l}}(w^{l+1}_{ij})^{2}\phi^{\prime}(y^{l}_{j}(x))\phi^{\prime}(y^{l}_{j}(x^{\prime}))K^{l}_{res}(x,x^{\prime})\rightarrow\dot{q}^{l+1}(x,x^{\prime})K^{l}_{res}(x,x^{\prime}).

Moreover, we have that

	$\displaystyle(\partial_{w^{l+1}}y^{l+1}_{i}(x))(\partial_{w^{l+1}}y^{l+1}_{i}(x^{\prime}))^{t}$	$\displaystyle+(\partial_{b^{l+1}}y^{l+1}_{i}(x))(\partial_{b^{l+1}}y^{l+1}_{i}(x^{\prime}))^{t}=$
		$\displaystyle\frac{\sigma_{w}^{2}}{n_{l}}\sum_{j}\phi(y^{l}_{j}(x))\phi(y^{l}_{j}(x^{\prime}))+\sigma_{b}^{2}$
		$\displaystyle\underset{n_{l}\rightarrow\infty}{\rightarrow}\sigma_{w}^{2}\mathbb{E}[\phi(y^{l}_{i}(x))\phi(y^{l}_{i}(x^{\prime}))]+\sigma_{b}^{2}=q^{l+1}(x,x^{\prime}).$

∎

In a similar fashion, we prove the recursive formula for ResNets with Convolutional layers.

Lemma 4 (NTK of a ResNet with Convolutional layers in the infinite-width limit).

Let $K^{res,1}$ be the exact NTK for the ResNet with 1 layer. Then
$\bullet$ For the first layer (without residual connections), we have for all $x,x^{\prime}\in\mathbb{R}^{d}$

K^{res,1}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}\Big(\frac{\sigma_{w}^{2}}{n_{0}(2k+1)}[x,x^{\prime}]_{\alpha,\alpha^{\prime}}+\sigma_{b}^{2}\Big)

$\bullet$ For $l\geq 2$ , as $n_{1},n_{2},...,n_{l-1}\rightarrow\infty$ recursively, we have for all $i,i^{\prime}\in[1:n_{l}]$ , $\alpha,\alpha^{\prime}\in[0:M-1]$ , $K^{res,l}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})=\delta_{ii^{\prime}}K^{res,l}_{\alpha,\alpha^{\prime}}(x,x^{\prime})$ , where $K^{res,l}_{\alpha,\alpha^{\prime}}$ is given by the recursive formula for all $x,x^{\prime}\in\mathbb{R}^{d}$ , using the same notations as in lemma 2,

K^{res,l}_{\alpha,\alpha^{\prime}}=K^{res,l-1}_{\alpha,\alpha^{\prime}}+\frac{1}{2k+1}\sum_{\beta}\Psi^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}.

where $\Psi^{l}_{\alpha,\alpha^{\prime}}=\dot{q}^{l}_{\alpha,\alpha^{\prime}}K^{res,l}_{\alpha,\alpha^{\prime}}+\hat{q}^{l}_{\alpha,\alpha^{\prime}}$ .

Proof.

Let $x,x^{\prime}$ be two inputs. We have that

	$\displaystyle K^{1}_{(i,\alpha),(i^{\prime},\alpha^{\prime})}(x,x^{\prime})$	$\displaystyle=\sum_{j}\left(\sum_{\beta}\frac{\partial y^{1}_{i,\alpha}(x)}{\partial w^{1}_{i,j,\beta}}\frac{\partial y^{1}_{i^{\prime},\alpha^{\prime}}(x)}{\partial w^{1}_{i^{\prime},j,\beta}}+\frac{\partial y^{1}_{i,\alpha}(x)}{\partial b^{1}_{j}}\frac{\partial y^{1}_{i^{\prime},\alpha^{\prime}}(x)}{\partial b^{1}_{j}}\right)$
		$\displaystyle=\delta_{ii^{\prime}}\left(\frac{\sigma_{w}^{2}}{n_{0}(2k+1)}\sum_{j}\sum_{\beta}x_{j,\alpha+\beta}x_{j,\alpha^{\prime}+\beta}+\sigma_{b}^{2}\right).$

\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)=\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha}(x)+\frac{\sigma_{w}}{\sqrt{n_{l-1}(2k+1)}}\sum_{j}\sum_{\beta}w^{l}_{i,j,\beta}\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha+\beta}(x)

this yields

		$\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}=\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l-1}_{i^{\prime},\alpha^{\prime}}(x)^{T}+$
		$\displaystyle\frac{\sigma_{w}^{2}}{n_{l-1}(2k+1)}\sum_{j,j^{\prime}}\sum_{\beta,\beta^{\prime}}w^{l}_{i,j,\beta}w^{l}_{i^{\prime},j^{\prime},\beta^{\prime}}\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})\phi^{\prime}(y^{l-1}_{j^{\prime},\alpha^{\prime}+\beta})\partial_{\theta_{1:l-1}}y^{l-1}_{j,\alpha+\beta}(x)\partial_{\theta_{1:l-1}}y^{l-1}_{j^{\prime},\alpha^{\prime}+\beta}(x)^{T}+I,$

where

I=\frac{\sigma_{w}}{\sqrt{n_{l-1}(2k+1)}}\sum_{j,\beta}w^{l}_{i,j,\beta}\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})(\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha+\beta}(x)^{T}+\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha+\beta}(x)\partial_{\theta_{1:l-1}}y^{l-1}_{i,\alpha}(x)^{T}).

As $n_{1},n_{2},...,n_{l-2}\rightarrow\infty$ and using the induction hypothesis, we have

		$\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}\rightarrow\delta_{ii^{\prime}}K^{l-1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})+$
		$\displaystyle\frac{\sigma_{w}^{2}}{n_{l-1}(2k+1)}\sum_{j}\sum_{\beta,\beta^{\prime}}w^{l}_{i,j,\beta}w^{l}_{i^{\prime},j,\beta^{\prime}}\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})\phi^{\prime}(y^{l-1}_{j,\alpha^{\prime}+\beta})K^{l-1}_{(j,\alpha+\beta),(j,\alpha^{\prime}+\beta)}(x,x^{\prime}).$

Note that $K^{l-1}_{(j,\alpha+\beta),(j,\alpha^{\prime}+\beta)}(x,x^{\prime})=K^{l-1}_{(1,\alpha+\beta),(1,\alpha^{\prime}+\beta)}(x,x^{\prime})$ for all $j$ since the variables are iid across the channel index $j$ . Now letting $n_{l-1}\rightarrow\infty$ , we have that

		$\displaystyle\partial_{\theta_{1:l-1}}y^{l}_{i,\alpha}(x)\partial_{\theta_{1:l-1}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}\rightarrow$
		$\displaystyle\delta_{ii^{\prime}}K^{l-1}_{\alpha,\alpha^{\prime}}(x,x^{\prime})+\delta_{ii^{\prime}}\left(\frac{1}{(2k+1)}\sum_{\beta,\beta^{\prime}}f^{\prime}(c^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}))K^{l-1}_{(1,\alpha+\beta),(1,\alpha^{\prime}+\beta)}(x,x^{\prime})\right),$

where $f^{\prime}(c^{l-1}_{\alpha+\beta,\alpha^{\prime}+\beta}(x,x^{\prime}))=\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(y^{l-1}_{j,\alpha+\beta})\phi^{\prime}(y^{l-1}_{j,\alpha^{\prime}+\beta})]$ .
We conclude using the fact that

\partial_{\theta_{l}}y^{l}_{i,\alpha}(x)\partial_{\theta_{l}}y^{l}_{i^{\prime},\alpha^{\prime}}(x)^{T}\rightarrow\delta_{ii^{\prime}}\left(\frac{\sigma_{w}^{2}}{2k+1}\sum_{\beta}\mathbb{E}[\phi(y^{l-1}_{\alpha+\beta}(x))\phi(y^{l-1}_{\alpha^{\prime}+\beta}(x^{\prime}))]+\sigma_{b}^{2}\right).

∎

References

Arora et al. [2019a] S. Arora, S.S. Du, W. Hu, , Z. Li, and R. Wand. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In ICML, 2019a.
Arora et al. [2019b] S. Arora, S.S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In NeurIPS, 2019b.
Bietti and Bach [2021] A. Bietti and F. Bach. Deep equals shallow for reLU networks in kernel regimes. In ICLR, 2021.
Bietti and Mairal [2019] A. Bietti and J. Mairal. On the inductive bias of neural tangent kernels. In NeurIPS, 2019.
Cao and Gu [2019] Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In NeurIPS, 2019.
Cao et al. [2021] Y. Cao, Z. Fang, Y. Wu, D. Zhou, and Q. Gu. Towards understanding the spectral bias of deep learning. In IJCAI, 2021.
Chen and Xu [2021] L. Chen and S. Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In ICLR, 2021.
Chizat and Bach [2019] L. Chizat and F. Bach. A note on lazy training in supervised differentiable programming. In NeurIPS, 2019.
Du et al. [2018] S.S. Du, J.D. Lee, Y. Tian, B. Poczos, and A Singh. Gradient descent learns one-hidden-layer CNN: Don’t be afraid of spurious local minima. In ICML, 2018.
Du et al. [2019a] S.S. Du, J.D. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In ICML, 2019a.
Du et al. [2019b] S.S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR, 2019b.
Geifman et al. [2020] A. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and R. Basri. On the similarity between the laplace and neural tangent kernels. In NeurIPS, 2020.
Ghorbani et al. [2021] B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029–1054, 2021.
Hanin and Nica [2020] B. Hanin and M. Nica. Finite depth and width corrections to the neural tangent kernel. In ICLR, 2020.
Hayase and Karakida [2021] T. Hayase and R. Karakida. The spectrum of Fisher information of deep networks achieving dynamical isometry. In AISTATS, 2021.
Hayou et al. [2019a] S. Hayou, A. Doucet, and J. Rousseau. On the impact of the activation function on deep neural networks training. In ICML, 2019a.
Hayou et al. [2019b] S. Hayou, A. Doucet, and J. Rousseau. Mean-field behaviour of neural tangent kernel for deep neural networks. arXiv:1905.13654, 2019b.
Hayou et al. [2021] S. Hayou, E. Clerico, B. He, G. Deligiannidis, A. Doucet, and J. Rousseau. Stable resnet. In AISTATS, 2021.
Huang and Yau [2020] J. Huang and H.T Yau. Dynamics of deep neural networks and neural tangent hierarchy. In ICML, 2020.
Huang et al. [2020] K. Huang, Y. Wang, M. Tao, and T. Zhao. Why do deep residual networks generalize better than deep feedforward networks? – a neural tangent kernel perspective. In NeurIPS, 2020.
Jacot et al. [2018] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In NeurIPS, 2018.
Karakida et al. [2019] R. Karakida, S. Akaho, and S. Amari. Universal statistics of Fisher information in deep neural networks: Mean field approach. In AISTATS, 2019.
Lee et al. [2018] J. Lee, Y. Bahri, R. Novak, S.S. Schoenholz, J. Pennington, and J. Sohl-Dickstein. In ICLR, 2018.
Lee et al. [2019] J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In NeurIPS, 2019.
Lillicrap et al. [2016] T. Lillicrap, D. Cownden, D. Tweed, and C. Akerman. Random synaptic feedback weights support error backpropagation for deep learning. Nature Communications, 7(13276), 2016.
MacRobert [1967] T.M. MacRobert. Spherical Harmonics: An Elementary Treatise on Harmonic Functions, with Applications. Pergamon Press, 1967.
Matthews et al. [2018] A.G. Matthews, J. Hron, M. Rowland, R.E. Turner, and Z. Ghahramani. Gaussian process behaviour in wide deep neural networks. In ICLR, 2018.
Neal [1995] R.M. Neal. Bayesian learning for neural networks. Springer Science & Business Media, 118, 1995.
Nguyen and Hein [2018] Q. Nguyen and M. Hein. Optimization landscape and expressivity of deep CNNs. In ICML, 2018.
Novak et al. [2020] Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In ICLR, 2020. URL https://github.com/google/neural-tangents.
Poole et al. [2016] B. Poole, S. Lahiri, M. Raghu, J. Sohl-Dickstein, and S. Ganguli. Exponential expressivity in deep neural networks through transient chaos. In NeurIPS, 2016.
Schoenholz et al. [2017] S.S. Schoenholz, J. Gilmer, S. Ganguli, and J. Sohl-Dickstein. Deep information propagation. In ICLR, 2017.
Xiao et al. [2018] L. Xiao, Y. Bahri, J. Sohl-Dickstein, S. S. Schoenholz, and P. Pennington. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. In ICML, 2018.
Xiao et al. [2020] Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and generalization in deep neural networks. In ICML, 2020.
Yang [2019] G. Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04760, 2019.
Yang [2020] G. Yang. Tensor programs iii: Neural matrix laws. arXiv preprint arXiv:2009.10685, 2020.
Yang and Schoenholz [2017] G. Yang and S. Schoenholz. Mean field residual networks: On the edge of chaos. In NeurIPS, 2017.
Zhang et al. [2017] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Zou et al. [2018] D. Zou, Y. Cao, D. Zhou, and Q. Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. arXiv preprint arXiv:1811.08888, 2018.

Exact Convergence Rates of the Neural Tangent Kernel in the Large Depth Limit

Abstract

keywords

1 Introduction

Neural Tangent Kernel.

Information propagation.

NTK training and SGD training.

Contributions.

Related work.

2 Neural Networks and Neural Tangent Kernel

3 Asymptotic Neural Tangent Kernel

3.1 NTK parameterization and the Edge of Chaos: FFNN and CNN architectures

Feedforward Fully-connected Neural Network (FFNN).

Convolutional Neural Network (CNN).

Lemma 0 (Generalization of Theorem 1 in Jacot et al. 2018).

Lemma 0 (Infinite-width NTK of a CNN).

Edge of Chaos (EOC).

Proposition 1 (NTK with Ordered/Chaotic Initialization).

Assumption 1.

Theorem 1 (NTK in the EOC).

3.2 Residual Neural Networks (ResNet)

Lemma 0 (NTK of a ResNet with fully connected layers in the infinite-width limit).

Lemma 0 (NTK of a ResNet with convolutional layers in the infinite-width limit).

Theorem 2 (NTK for ResNet).

3.3 Spectral decomposition of the limiting NTK

Proposition 2 (Spectral decomposition on 𝕊d−1\mathbb{S}^{d-1}).

3.4 Scaled ResNet

Theorem 3 (Scaled ResNet).

4 Learning Rate Passband

5 Experiments

5.1 Behaviour of KLK^{L} as LL goes to infinity

5.2 Can NTK regime explain DNN performance?

SGD training.

NTK training.

5.3 Does Scaled ResNet outperform ResNet with SGD?

6 Conclusion and Limitations

7 Proof techniques

Lemmas 1, 2, 3, 4.

Proposition 1, Theorems 1, 2, 3.

Proposition 2.

8 Proofs

8.1 Proofs on the limiting NTK: 1, Theorems 1, 2 and 3

8.1.1 Proof of 1: NTK in the ordered/chaotic phase

8.1.2 Proof of Theorem 1 : FFNN and CNN in the EOC

8.1.3 Proof of Theorem 2: NTK for ResNET

8.1.4 Proof of Theorem 3: NTK for Scaled ResNet

8.2 Proof of Proposition 2: Spectral analysis of the NTK

8.2.1 Some facts on Spherical harmonics

8.2.2 Proof of Proposition 2

Acknowledgements

References

Appendix

0 Some facts on the infinite-width regime and on NTKs

0.1 Gaussian process limit

0.1.1 Forward propagation

FeedForward Neural Network.

Convolutional Neural Networks.

Residual Neural Networks.

0.1.2 Gradient Independence

Gradient Covariance back-propagation.

Neural Tangent Kernel.

0.2 On the theory of signal propagation in DNNs

0.2.1 Covariance propagation and the Edge of Chaos

Covariance propagation for FFNN.

Covariance propagation for CNN.

Covariance propagation for ResNet with ReLU.

Edge of Chaos (EOC)

0.2.2 Gradient Covariance back-propagation

Gradient back-propagation for FFNN.

Gradient Covariance back-propagation for CNN.

0.2.3 Some facts on the theory of information propagation

Results for FFNN with Tanh activation.

Fact 1.

Fact 2.

Fact 3.

Fact 4.

Fact 5 (Correlation function).

Fact 6.

Fact 7.

Proof.

Proposition 2 (Spectral decomposition on $\mathbb{S}^{d-1}$ ).

5.1 Behaviour of $K^{L}$ as $L$ goes to infinity

Appendix Lemma 5 (Asymptotic behaviour of $c^{l}$ for ReLU).

Appendix Lemma 6 (Asymptotic behaviour of $c^{l}$ for Tanh).

Appendix Lemma 9 (Asymptotic expansion of $c^{l}$ for ResNet).