# Weak Correlations as the Underlying Principle for Linearization of Gradient-
Based Learning Systems

Ori Shem-Ur  Raymond and Beverly Sackler School of Physics and Astronomy, Tel-
Aviv University, Tel-Aviv 69978, Israel<EMAIL_ADDRESS>,
<EMAIL_ADDRESS> Yaron Oz  Raymond and Beverly Sackler School of
Physics and Astronomy, Tel-Aviv University, Tel-Aviv 69978, Israel.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Deep learning models, such as wide neural networks, can be conceptualized as
nonlinear dynamical physical systems characterized by a multitude of
interacting degrees of freedom. Such systems in the infinite limit, tend to
exhibit simplified dynamics. This paper delves into gradient descent-based
learning algorithms, that display a linear structure in their parameter
dynamics, reminiscent of the neural tangent kernel. We establish this apparent
linearity arises due to weak correlations between the first and higher-order
derivatives of the hypothesis function, concerning the parameters, taken
around their initial values. This insight suggests that these weak
correlations could be the underlying reason for the observed linearization in
such systems. As a case in point, we showcase this weak correlations structure
within neural networks in the large width limit. Exploiting the relationship
between linearity and weak correlations, we derive a bound on deviations from
linearity observed during the training trajectory of stochastic gradient
descent. To facilitate our proof, we introduce a novel method to characterise
the asymptotic behavior of random tensors.

##  1 Introduction

Deep learning in general, and particularly over-parameterized neural networks,
revolutionized various fields [1, 2, 3, 4], and they are likely to do much
more. Yet, the underlying reason for their unprecedented success remains
elusive. These systems can be interpreted as non-linear dynamical physical
systems, characterized by a multitude of interacting degrees of freedom, which
makes an exact description of their behavior exceedingly hard. However, it is
well established that dynamical physical systems when expanded to an infinite
number of degrees of freedom tend to exhibit a simplified form of dynamics
[5], therefore, it seems plausible to consider such a limit in the context of
deep learning systems.

A seminal study in 2018 [6], demonstrated that wide, fully connected neural
networks, undergoing deterministic gradient descent, behave as though they
were linear with respect to their parameters, (while maintaining a highly non-
linear structure in their inputs). This structure has been denoted as the
neural tangent kernel (NTK). The result sparked a plethora of subsequent
research, generalizing it to other architectures, investigating the rate of
convergence towards this linear limit, exploring the deviation of the
parameters themselves from their initial configuration, decoding the structure
of the kernels, and leveraging this knowledge to enhance our understanding of
wide neural networks in general [7, 8, 9, 10, 11, 12].

Subsequent discussions arose regarding the role of this limit in the exemplary
performance of wide neural networks. Several studies have demonstrated that in
certain contexts, infinitely wide neural networks converge to their global
minimum at an exponential rate [6, 7, 13, 14, 15, 16, 17, 18, 19]. Moreover,
wide neural networks have been posited as effective tools for generalization,
with connections drawn to the double descent phenomenon [20, 21, 22]. However,
these conclusions encounter some contention when juxtaposed with empirical
evidence. Notably, several experiments indicate that for real-world data, NTK-
based learning is less effective than its wide (albeit finite) neural network
counterparts [23, 24]. This apparent ”NTK inferiority paradox” suggests that
the relationship between the NTK limit and the success of finite neural
networks may be more intricate than initially presumed.

An under-explored area within the realm of the neural tangent kernel limit
pertains to the foundational principles responsible for this linearization.
[25] proposed that any learning system, under a gradient-based algorithm,
embodies an intrinsic scale that directs the system’s linearization.
Furthermore, the introduction of an external parameter, can modulate this
inherent scale, thereby influencing the system’s tendency towards
linearization. [26] demonstrated that the related ratio between the
subordinate/spectral norm of the Hessian, and the euclidean norm of the
Gradient that governs linearization. Their work also elucidated that in wide
neural networks this ratio tends to be small.

###  1.1 Our Contributions

  1. 1.

We establish that for gradient descent-based learning, linearity is equivalent
to weak correlations between the first and subsequent derivatives of the
hypothesis function, concerning its parameters at their initial values (3.3).
This equivalence is suggested as the fundamental cause for the linearization
observed in wide neural networks.

  2. 2.

We prove directly that wide neural networks display this weak derivative
correlations structure. By relying and extending the tensor programs formalism
[27], our approach uniformly addresses a broader spectrum of architectures at
once than any other proof we are aware of (4.2).

  3. 3.

Drawing from the same concepts, we demonstrate how modifications in the
architecture of linearizing learning systems, and more specifically, wide
neural networks, affect the rate of linearization. This finding is juxtaposed
[25]’s result, regarding the implications of the introduction of an external
scale (3.3.2,4.2).

  4. 4.

Harnessing the formalism of weak derivatives correlations, we derive a bound
on the deviation from linearization over time during learning, when utilizing
stochastic gradient descent (4.1). This is a generalisation of the traditional
result for deterministic gradient descent [7]. This is crucial, as in most
practical scenarios, stochastic gradient descent generalize better than
deterministic gradient descent [23, 24].

  5. 5.

We introduce the notion of random tensor asymptotic behavior, as an effective
analytical tool to describe the asymptotic behavior of random tensors (2).
Such tensors are not only integral to machine learning, but also serve a
pivotal role in diverse mathematical and physical frameworks. Understanding
the evolution of these tensors typical asymptotic behavior is relevant for
addressing many questions across these fields.

The overarching simplicity and broad applicability of our findings suggest
that weak derivatives correlations could very well be the foundational cause
for the prevalent linearization attributes observed in wide neural networks,
and possibly for other linearizing systems.

##  2 Random Tensor Asymptotic Behavior

Random tensors play a fundamental role in machine learning in general, and in
this work in particular. In this section, we demonstrate the effectiveness of
employing the stochastic big $O$ notation of the subordinate norm to
characterize the asymptotic behavior of a general random tensor series
(hereinafter referred to as a random tensor). Addressing the asymptotic
behavior of such tensors involves two inherent challenges: the complexity
arising from their multitude of components, and the stochastic nature of these
components.

  1. 1.

To avoid the first challenge, we focus on the tensor’s subordinate norm, as
elucidated in Section 2.1. This norm exhibits a wide array of useful
properties, rendering it highly effective for working with random tensors,
particularly concerning linear products.

  2. 2.

In Section 2.2, we argue that the stochastic big $O$ notation is the most
effective tool for characterizing the asymptotic behavior of random variables,
surpassing other measures such as the standard big $O$ notation of the
variance. We further demonstrate how its properties seamlessly synergize with
those of the subordinate norm.

  3. 3.

Finally, in Section 2.3, we establish that every random variable possesses a
unique, tight asymptotic bound, termed the definite asymptotic bound. This
allows us to use the stochastic big $O$ notation not merely as a tool to bound
the asymptotic behavior of random tensors, but also as a way to fully
characterize it. Consequently, we define the asymptotic behavior of a tensor
${M}$ as the definite asymptotic bound of the tensor’s subordinate norm.

###  2.1 The Subordinate Tensor Norm

Let $M$ be a tensor of rank $r\in\mathbb{N}_{0}$. Denote all its indices using
the vector $\vec{i}$, such that each $i_{e}$ for $e=1...r$ can assume values
$i_{e}=1...N_{e}$. Consequently, the tensor comprises a total of
$N=N_{1}\cdots N_{r}$ elements.

We will use the subordinate norm, defined as [28]:

$\begin{split}\left\|{M}\right\|=\sup\left\\{\left.{M}\cdot\left(v^{1}\times\ldots\times
v^{r}\right)\right|v^{1}\in S_{N_{1}}\ldots v^{r}\in S_{N_{r}}\right\\}=\\\
\sup\left\\{\left.\sum_{i_{1}\ldots i_{r}=1}^{N_{1}\ldots
N_{r}}\left({M}_{i_{1}\ldots i_{r}}v_{i_{1}}^{1}\cdots
v_{i_{r}}^{r}\right)\right|v^{1}\in S_{N_{1}}\ldots v^{r}\in
S_{N_{r}}\right\\}\ ,\end{split}$ (1)

where $S_{N_{k}}=\left\\{v\in\mathbb{R}^{N_{k}}:v\cdot v=1\right\\}$
represents the unit vectors of the appropriate dimensions. This norm satisfies
certain algebraic properties outlined in lemma A.1, including: [i] the
triangle inequality; [ii] for a tensor $M$ and vectors $v_{1}\ldots v_{q}$
with appropriately defined product, the condition
$\left\|M\cdot\left(v^{1}\times\ldots\times
v^{r}\right)\right\|\leq\left\|M\right\|\left\|v^{1}\right\|\cdots\left\|v^{r}\right\|$
holds; [iii] Given two tensors $M^{(1)}_{\vec{i}_{1}},M^{(2)}_{\vec{i}_{2}}$
defining
$M_{\vec{i}_{1},\vec{i}_{2}}=M_{\vec{i}_{1}}^{\left(1\right)}M_{\vec{i}_{2}}^{\left(2\right)}$
then,
$\left\|M\right\|=\left\|M^{\left(1\right)}\right\|\left\|M^{\left(2\right)}\right\|$.

Also, one has $\left\|M\right\|\leq\left\|M\right\|_{F}$ (with equality for
vectors) (A.2) where the Frobenius norm is:

$\left\|M\right\|_{F}^{2}=\sum_{\vec{i}}M_{\vec{i}}^{2}\ .$ (2)

###  2.2 Effectiveness of the Stochastic ”Big O” Notation

Consider a general random tensor series, denoted by
$M\equiv\left\\{M_{n}\right\\}_{n=1}^{\infty}$, which henceforth we will
consider as a random tensor that depend on a limiting parameter
$n\in\mathbb{N}$111The results are applicable not only for $\mathbb{N}$, but
for any other set possessing an absolute order above it.

Our objective in this section is to identify a method to describe and bound
the asymptotic behavior of such a tensor, which adheres to elementary
algebraic properties. Specifically, we aim for the product of multiple bounded
random tensors to be constrained by the product of their respective bounds.

Employing our defined norm (1), we can simplify our problem from general
random tensors to positive random variables (rank zero tensors), as our norm
satisfies the elementary algebraic properties established in Lemma A.1. This
reduction is substantial; however, the challenge of addressing the non-
deterministic nature of our variable remains.

One might initially consider the expectation value of the tensor’s norm as a
solution. This approach, unfortunately falls short, because that for two
positive random variables $M_{1},M_{2}$ their product variance is not bounded
by the product of their variance. In fact, generally, the converse is true:

$\text{Var}\left(M_{1}M_{2}\right)\geq\text{Var}\left(M_{2}\right)\text{Var}\left(M_{1}\right)$
(3)

This issue becomes more pronounced when considering the product of multiple
such variables, a frequent occurrence in this work. For instance, even with a
basic zero-mean normal distribution with standard deviation $\sigma$, the
higher moments of this distribution factor as $p!!=p(p-2)(p-4)\cdots$:

$\forall p\in\mathbb{N}:\left\langle M^{p}\right\rangle=p!!\sigma^{p}\ .$ (4)

When multiplying multiple such variables, these factors can accumulate in the
lower moments, rendering this definition impractical for our purposes.
Similarly, any attempt to define asymptotic behavior using the variable’s
moments will encounter similar difficulties.

To circumvent these challenges, we adopt the stochastic big $O$ notation [29,
30]222Our definition slightly differs from the standard definition for big $O$
in probability notation, but it is straightforward to show its equivalence. We
denote $\mathcal{N}=\left\\{f:\mathbb{N}\rightarrow\mathbb{R}^{0+}\right\\}$
as the set of all functions from $\mathbb{N}$ to $\mathbb{R}^{0+}$.

######  Definition 2.1 (Asymptotic Upper Bound of Random Tensors).

A random tensor $M$, as defined above, is said to be asymptotically upper
bounded by $f\in\mathcal{N}$ as follows:

$M=O\left(f\right)\ ,$ (5)

if and only if:

$\forall
g\in\mathcal{N}\,s.t\,f=o\left(g\right):\lim_{n\rightarrow\infty}P\left(\left\|M_{n}\right\|\leq
g\left(n\right)\right)=1\ .$ (6)

The lower asymptotic bound, $f=\Omega(M)$, is defined analogously but with the
inequality reversed and $g=o(f)$.

Like with an infinite number of deterministic series, where pointwise
convergence often falls short and uniform convergence is required, we demand a
definition of a uniform asymptotic bound for discussing an infinite number of
random tensors. This concept is rigorously defined in appendix A.1.

######  Remark 2.1.

For a finite number of tensors, it can simply be demonstrated that the uniform
bound aligns with the pointwise asymptotic bound, analogous to series
convergence..

We demonstrate in lemma A.6 that this notation inherits many of the norm’s
properties it is defined above, including all of the properties of the
subordinate norm, delineated in lemma A.1. Furthermore, it satisfies several
other useful properties, outlined in appendix A.3.

###  2.3 The Definite Random Tensor Asymptotic Bound

######  Remark 2.2.

We denote $f\leq g$ or $(f)\leq O(g)$ iff $f=O(g)$. We also denote $f<g$ or
$O(f)<O(g)$ iff $f=O(g)$ and $f\not\sim g$, where $f\sim g\Leftrightarrow
O\left(f\right)=O\left(g\right)\Leftrightarrow f=O\left(g\right)\land
g=O\left(f\right)$. It is important to note that $f<g$ can hold even without
necessitating $f=o(g)$.

It can be readily shown that for any random tensor $M$, there exist upper and
lower bounds such that $O\left(h_{-}\right)\leq O\left(M\right)\leq
O\left(h_{+}\right)$, and that they satisfy $h_{-}\leq h_{+}$. Furthermore, if
$h_{+}$ and $h_{-}$ satisfy $h_{+}\sim h_{-}$, their asymptotic behavior is
unique. Meaning that for any other pair $h_{+}^{\prime},h_{-}^{\prime}$, the
relationship $h_{+}\sim h_{+}^{\prime}\sim h_{-}^{\prime}\sim h_{-}$ still
holds (A.5). In such scenarios, we assert that $M$ possesses an exact
asymptotic behavior, denoted as $O\left(h_{+}\right)=O\left(h_{-}\right)$.

The existence of such a pair however is not guaranteed, as illustrated by a
random variable that for every $n\in\mathbb{N}$, has equal probability of one-
half to yield either $1$ or $n$. For this variable, the optimal upper bound is
$n$, and the optimal lower bound is $1$, but these do not exhibit the same
limiting behavior. Analogously, deterministic series may exhibit similar
behavior, featuring multiple distinct partial limits. However, in the
deterministic case, the limsup and liminf serve as the appropriate upper and
lower limits respectively. This observation leads to the question of whether
an appropriate asymptotic bound exists for the random case. It turns out, it
does.

######  Theorem 2.1 (Definite Asymptotic Bounds for Tensors).

Consider a random tensor $M$ with a limiting parameter $n$ as described
earlier. There exists $f\in\mathcal{N}$ serving as a tight/definite upper
bound for $M$, satisfying:

$M=O\left(f\right)\land\forall f\not<g:M\neq O\left(g\right)\ .$ (7)

Furthermore, the asymptotic behavior of $f$ is unique.

###### Explanation.

Although the theorem may appear intuitive, the challenge arises from the fact
that our order above $\mathcal{N}$ is not a total one, even when considering
only the asymptotic behavior of the functions. For example, none of the
following equations hold true:

$\sin\left(\pi n\right)<\cos\left(\pi n\right),\cos\left(\pi
n\right)<\sin\left(\pi n\right),\sin\left(\pi n\right)\sim\cos\left(\pi
n\right)\ .$ (8)

We address this issue by employing Zorn’s lemma, as demonstrated in appendix
A.2. ∎

Since every such random tensor $M$ has precisely one definite asymptotic bound
$f$, we can consider this bound as the random tensor’s asymptotic behavior,
represented as:

$O(M)=O(f)\ .$ (9)

##  3 Weak Correlations and Linearization

###  3.1 Notations for Supervised Learning

####  3.1.1 General notations

Supervised learning involves learning a classifier: a function
$\hat{y}:X\rightarrow Y$ that maps an input set (here
$X\subseteq\mathbb{R}^{d_{X}}$), to an output set (here
$Y\subseteq\mathbb{R}^{d_{Y}}$), given a dataset of its values
$X^{\prime}\subseteq X$, denoted as the ”target function”. This is achieved by
using an hypothesis function, in our case of the form
$F:\mathbb{R}^{N}\rightarrow\left\\{f:X\rightarrow Y\right\\}$ which depends
on certain parameters $\theta\in\mathbb{R}^{N}$ (in the case of fully
connected neural networks for example, the weights and biases). The objective
of supervised learning is to find the optimal values for these parameters,
such that $F$ captures $\hat{y}$ best, with respect to a cost function
$\mathcal{C}$ assumed here convex. We use $x\in X$ to denote elements in the
input set, and $i,j=1...d_{Y}$ to denote the output vector indices. The
parameters $\theta$ are enumerated as
$\theta_{\alpha},\alpha=1,...,|\theta|=N$, and their initial values are
denoted by $\theta_{0}=\theta(0)$.

We work within the optimization framework of single input batches gradient
descent-based training, which is defined such that for every learning step
$s\in\mathbb{N}$:

$\begin{array}[]{c}\Delta^{x_{s}}\theta\left(s\right)=\theta\left(s+1\right)-\theta\left(s\right)=\left.-\eta\nabla\mathcal{C}\left(F\left(\theta\right)\left(x_{s}\right),\hat{y}\left(x_{s}\right)\right)\right|_{\theta=\theta\left(s\right)}=\\\
=-\eta\nabla
F\left(\theta\left(s\right)\right)\left(x_{s}\right)\mathcal{C}^{\prime}\left(F\left(\theta\left(s\right)\right)\left(x_{s}\right),\hat{y}\left(x_{s}\right)\right)\
.\end{array}$ (10)

Here, $\nabla_{\alpha}=\frac{\partial}{\partial\theta_{\alpha}}$ represents
the gradient operator, $x_{s}$ denotes the $s\in\mathbb{N}$th input data, and
$\mathcal{C}^{\prime}(x)=\frac{d\mathcal{C}(x)}{dx}$ refers to the derivative
of the cost function. The derivative matrix/the Jacobian $\nabla F$ is defined
such that for every indices ${i,\alpha}$, ${\left(\nabla F\right)}_{\alpha
i}=\nabla_{\alpha}F_{i}$. We denote $\eta$ as the learning rate and
$\left(x_{s},\hat{y}\left(x_{s}\right)\right)$ as the images and labels,
respectively. The training path is defined as the sequence of inputs upon
which we trained our system, represented by $\left\\{x_{s}\in
A\right\\}_{s=0}^{\infty}$. We assume that each input along this path is drawn
from the same random distribution $\mathcal{P}$, neglecting the possibility of
drawing the same input multiple times. The same distribution will be used for
both training and testing. Moreover, we assume that the hypothesis function
and the cost function $F,\mathcal{C}$ are analytical in their parameters. We
study learning in the limit where the number of parameters
$N\equiv|\theta|\rightarrow\infty$, with $N\equiv N(n)$ being a function of
some other parameter $n\in\mathbb{N}$, denoted as the ”limiting parameter”.
For neural networks, $n$ is typically chosen as the width of the smallest
layer, but we can choose any parameter governs the system’s linearization.

######  Remark 3.1.

This framework can be greatly generalised, as we discussed in appendix F.

####  3.1.2 Neural Tangent Kernel Notations

Numerous gradient descent learning systems (GDML) with different neural
network architectures, display a linear-like structure in their parameters in
the large width limit. In this linear limit, the hypothesis function takes the
following form:

$\begin{array}[]{c}F_{lin}\left(0\right)=F\left(\theta_{0}\right),\\\ \forall
s\in\mathbb{N}_{0}:F_{lin}\left(s+1\right)=F_{lin}\left(s\right)-\Theta_{0}\left(\cdot,x_{s}\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right)\left(x_{s}\right),\hat{y}\left(x_{s}\right)\right)\
,\end{array}$ (11)

with the kernel $\Theta$ defined such as:

$\forall x,x^{\prime}\in
X:\Theta\left(\theta\right)\left(x,x^{\prime}\right)=\eta\nabla
F\left(\theta\right)\left(x\right)^{T}\nabla
F\left(\theta\right)\left(x^{\prime}\right),\quad\Theta_{0}\equiv\Theta\left(\theta_{0}\right)\
,$ (12)

where $\nabla F^{T}$ is the transpose of $\nabla F$ the Jacobian.

###  3.2 The Derivatives Correlations

####  3.2.1 The Derivatives Correlations Definition

In the following, we prove that linearization is equivalent to having weak
correlations between the first, and higher derivatives of the hypothesis
function, with respect to the initial parameters. We define the derivative
correlations as follows:

######  Definition 3.1 (Derivatives Correlations).

We define the derivatives correlations of the hypothesis function for any
positive integer $d\in\mathbb{N}$ and non-negative integer
$D\in\mathbb{N}^{0}$ as:

$\mathfrak{C}^{D,d}\left(\theta\right)=\frac{\eta^{\frac{D}{2}+d}}{D!d!}\nabla^{\times
D+d}F\left(\theta\right)^{T}\left(\nabla F\left(\theta\right)\right)^{\times
d}\ ,$ (13)

where the higher order derivatives defined such that for every
$d\in\mathbb{N}$ and indices $i,\alpha_{1}...\alpha_{d}$,
$\left(\nabla^{\times
D}F\right)_{\alpha_{1}...\alpha_{d},i}=\nabla_{\alpha_{1}}\cdots\nabla_{\alpha_{d}}F_{i}$.

More explicitly, we present the inputs and indices of these tensors as
follows:

$\begin{array}[]{c}\mathfrak{C}^{D,d}\left(\theta\right)_{i_{0},i_{1}\ldots
i_{d}}^{\alpha_{1+d}\ldots\alpha_{D+d}}\left(x_{0},x_{1}\ldots
x_{d}\right)=\\\
\frac{\eta^{\frac{D}{2}+d}}{D!d!}\sum_{\alpha_{1}\ldots\alpha_{d}=1}^{N}\nabla_{\alpha_{1}\ldots\alpha_{D+d}}^{\times
D+d}F_{i_{0}}\left(\theta\right)\left(x_{0}\right)\left(\nabla_{\alpha_{1}}F_{i_{1}}\left(\theta\right)\left(x_{1}\right)\cdots\nabla_{\alpha_{d}}F_{i_{d}}\left(\theta\right)\left(x_{d}\right)\right)\
,\end{array}$ (14)

The objects in (13) are the correlation of the derivatives in the sense that
$\alpha_{1}\ldots\alpha_{d}$ can be viewed as random variables, drawn from a
uniform distribution of $\\{1...N\\}$, while $\theta$ and all other indices
are fixed instances and hence deterministic. In this context, $\nabla^{\times
D+d}F$ and $\nabla F\times\ldots\times\nabla F$ in (13) can be viewed as
random vectors of the variables $\alpha_{1}\ldots\alpha_{d}$, and the
summation in (13) represents the (unnormalized) form of the ”Pearson
correlation” between the two random vectors. The overall coefficient of the
learning rate $\eta^{\frac{D}{2}+d}$ serves as the appropriate normalization,
as we will demonstrate in appendix C and D. We will also denote:
$\mathfrak{C}^{d}\left(\theta\right)\equiv\mathfrak{C}^{0,d}\left(\theta\right),\mathfrak{C}^{D,d}\equiv\mathfrak{C}^{D,d}\left(\theta_{0}\right),\mathfrak{C}^{d}\equiv\mathfrak{C}^{d}\left(\theta_{0}\right)$.

An example for these correlations is the $D=0,d=1$ correlation, the
correlation of the first derivative with itself, the kernel:

$\mathfrak{C}^{1}\left(\theta\right)=\eta\nabla^{T}F\left(\theta\right)\nabla
F\left(\theta\right)=\Theta\left(\theta\right)\ .$ (15)

The definition for the asymptotic behavior for these derivative correlations
is slightly nuanced due to the many different potential combinations of
distinct inputs. We rigorously define it in appendix B.1.

###  3.3 Equivalence of Linearity and Weak Derivatives Correlations

Our main theorems concern the equivalence of linearity and weak derivative
correlations. In other words, weak correlations can be regarded as the
fundamental reason for the linear structure of wide neural networks. These
theorems are applicable for systems that are properly scaled in the initial
condition, meaning that when taking $n\rightarrow\infty$ the different
components of the system remain finite. We define in rigour exactly what it
means in appendix B.2. We denote such systems as properly normalised GDMLs or
PGDMLs.

####  3.3.1 Our Main Theorems

In the following theorems, we describe two distinct manifestations of the
equivalence between linearization and weak derivatives correlations for a
PGDMLs. We denote by $m(n)$ as the parameter of the linearization/correlation
decay where $m(n)\rightarrow\infty$. $m(n)$ is an intrinsic parameter of the
system, and is defined by the linearization rate or the correlation structure.
For wide neural networks for example, $m(n)=\sqrt{n}$.

######  Theorem 3.1 (Fixed Weak Correlations and Linearization Equivalence).

Under the conditions described above, for a sufficiently small learning rate
$\eta<\eta_{the}$, the two properties are equivalent:

  1. 1.

$m(n)$ \- fixed weak derivatives correlation:

$\forall
d,D\in\mathbb{N}:\mathfrak{C}^{d}=O\left(\frac{1}{m\left(n\right)}\right),\mathfrak{C}^{D,d}=O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)\quad\text{Uniformly.}$
(16)

  2. 2.

Simple linearity: For every fixed training step $s\in\mathbb{N}$:

$\begin{array}[]{c}F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)=O\left(\frac{1}{m\left(n\right)}\right)\
,\\\ \forall D\in\mathbb{N}:\eta^{\frac{D}{2}}\left(\nabla^{\times
D}F\left(\theta\left(s\right)\right)-\nabla^{\times
D}F\left(\theta_{0}\right)\right)=O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)\quad\text{Uniformly.}\end{array}$
(17)

$\eta_{the}$ is defined such as all the correlations are uniformly bounded by
$O(1)$, to ensure the sum converges, as shown in appendix C.2.

The next theorem delineates an even stronger equivalence, which is also
relevant for wide neural networks. It also encompasses the scaling of the
learning rate.

######  Theorem 3.2 (Exponential Weak Correlations and Linearization
Equivalence).

For the conditions described above, the two properties are equivalent:

  1. 1.

$m(n)$ \- power weak derivatives correlation:

$\forall\left(D,\in\mathbb{N}^{0},d\in\mathbb{N}\right)\neq\left(0,1\right):\text{$\mathfrak{C}$}^{D,d}=O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)^{d}\quad\text{Uniformly.}$
(18)

  2. 2.

Strong linearity: For every reparametrisation of the learning rate
$\eta\rightarrow r(n)\eta$, $r(n)>0$ and for every fixed training step
$s\in\mathbb{N}$:

$\begin{array}[]{c}F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)=O\left(\frac{r\left(n\right)}{m\left(n\right)}\right)\
,\\\ \forall
D\in\mathbb{N}:\left(\frac{\eta}{r\left(n\right)}\right)^{\frac{D}{2}}\left(\nabla^{\times
D}F\left(\theta\left(s\right)\right)-\nabla^{\times
D}F\left(\theta_{0}\right)\right)=O\left(\frac{r\left(n\right)}{\sqrt{m\left(n\right)}}\right)\
.\end{array}$ (19)

###### Explanation.

We prove the theorems by considering for a general learning step
$s\in\mathbb{N}$, the hypothesis function and its derivatives’ Taylor series
expansion around the $s-1$ step. Utilizing equation 10, we can find that the
evolution of the derivatives of $F$ and its derivatives during learning, is
governed by a linear combination of the correlations of the form:

$\forall D\in\mathbb{N}^{0}:\Delta\frac{\eta^{\frac{D}{2}}}{D!}\nabla^{\times
D}F\left(\theta\right)=\sum_{d=1}^{\infty}\mathfrak{C}^{D,d}\left(\theta\right)\left(-\mathcal{C}^{\prime}\left(F\left(\theta\right),\hat{y}\right)\right)^{\times
d}\ ,$ (20)

where $\Delta\nabla^{\times D}F$ in the change of $\nabla^{\times D}F$. For
deterministic functions it is straightforward to prove the equivalences by
employing the arithmetic properties of the big $O$ notation, and that [i] One
can choose any $F-\hat{y}$ (as long as its asymptotic behavior is
appropriate). [ii] Different components in our sum cannot cancel each other,
since we can change $\eta$ continuously; thus, for the sum stay small, all of
the components must be small. The adjustments needed for our case of
stochastic functions are minor, as, as we show in appendix A.3, our tensor
asymptotic behavior notation satisfies many of the same properties of the
deterministic big $O$ notation. The complete proofs are in appendix C. ∎

####  3.3.2 External Scale and Hessian Spectral Norm

We see in theorem 3.2, that a rescaling of $\eta$ such as $\eta\rightarrow
r(n)\eta$ can either promote or impede the process of linearization. This
observation also holds for theorem (3.2) as long as $\eta<\eta_{the}$. This
insight offers a deeper understanding of the findings presented by [25].
Specifically, it elucidates that an alteration of an external scale influences
linearization by affecting the scale of the higher correlations differently
than of the lower ones.

A notable connection to another principal research [26], is the definition of
derivatives correlations themselves. In [26], the authors established that
linearization, results from a small ratio between the spectral norm of the
Hessian and the norm of the gradient. The derivative correlations can be
interpreted as a spectral norm, but concerning solely the gradient, when
considered as a vector. This interpretation serves as a refinement of the
results presented in [26]. Unlike in [26] approach, which required this ratio
to be small within a ball, our approach demands its minimization at the
initialization point itself. Because of that it necessitates the decay of
higher-order correlations.

####  3.3.3 The Chicken and the Egg of Linearization and Weak Correlations

The relationship between linearization and weak correlations in over-
parameterized systems can be comprehended from two different viewpoints. The
first perspective suggests that effective learning in such systems
necessitates a form of implicit regularization, which inherently favors
simplicity [20]. This preference can be directly incorporated by imposing a
linear (or at least approximately linear), structure in highly over-
parameterized regimes. Notably, in certain scenarios, linearization can
facilitate exponential convergence rates, especially with respect to the
training datasets and, but in some instances, even with respect to the testing
datasets [6, 7, 13, 15, 16, 17, 18, 19, 14]. Hence, weak derivative
correlations can be interpreted as a pragmatic approach for achieving
linearization.

An alternative interpretation, aligning more closely with the spirit of this
paper, suggests that weak derivative correlations do not primarily serve as a
dynamic mechanism for linearization, but rather, as its underlying cause. In
this context, persisting derivative correlations may indicate an inherent bias
within the system, typically undesirable. Therefore, linearization can be
viewed as a consequence of our attempt to avoid counterproductive biases, by
demanding weak correlations.

Moreover, if we possess some prior knowledge about an inherent biases in our
problem, it might be advantageous to allow some non-decaying correlations,
counteracting the process of linearization. Furthermore, as certain biases can
enhance general learning algorithms (in the form of implicit and explicit
regularization), this perspective might provide valuable insights into the
”NTK inferiority paradox” introduced in the introduction (1). The reason why
linear learning underperforms in comparison to finite neural networks, might
be that it lack some beneficial biases, in the form of non vanishing
correlations.

##  4 Properties of Weakly Correlated PGDMLs

###  4.1 Application: Deviation from Linearity During Learning

Multiple studies have examined the deviation of the hypothesis function $F$
from its linear approximation, $F_{lin}$ (11), as a function of $n$ for a
fixed learning step (especially in the context of wide neural networks). Yet,
it seems that no research has explored the deviation between these functions
with respect to the learning step for stochastic GD (10). This aspect is
crucial since even if $F-F_{lin}$ vanished for a given learning step, if it
deviates too fast during learning, the linearization may not be evident for
realistic large $n$.

We address single-input batches stochastic GD in our study. However, as we
explained in appendix F, this result can be greatly generalized. Notably, the
analysis for stochastic GD may be even more relevant even for deterministic
GD, than the conventional approaches that presuppose a training dataset. This
is because, while the batch might be fixed, its initial selection is from a
stochastic distribution.

######  Corollary 4.0.1 (Weakly Correlated PGDML Deviation Over Time).

For an exponentially $m(n)$-weakly correlated PGDML, given $\eta<\eta_{cor}$,
and some $S\in\mathbb{N}$, that for every $s=1\dots S$, if:

$\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)=O\left(e^{-\frac{s}{T}}\right),\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s\right),\hat{y}\right)=O\left(1\right)\quad\text{Uniformly,}$
(21)

than:

$F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)=O\left(\frac{s^{0}}{m\left(n\right)}\right)\quad\text{Uniformly.}$
(22)

$\eta_{cor}$ is the standard critical learning rate ensuring our system’s
effectively learns in the NTK limit (D). It’s typically from the same order of
magnitude as $\eta_{the}$.

###### Explanation.

We prove the corollary by using a similar induction process as in theorems
(3.1,3.2). However, here we also consider the dependency in the learning step,
as detailed in appendix D. We are able to bound the deviation over time, by
leveraging the fact that in the NTK limit during the initial phases of the
learning process, the system converges towards the target function
exponentially fast333The known bounds for
$\mathcal{C}^{\prime}\left(F_{lin},\hat{y}\right)$ are typically bounds over
the variance. In appendix A.4, we discuss how an average exponential bound can
be translated into a uniform probabilistic bound. [6, 7, 13, 15, 16, 17, 18,
19, 14]. We believe that subsequent research will be able to produce more
refined bounds. ∎

###  4.2 Example: Wide Neural Networks

Numerous studies have demonstrated that a wide range of neural networks
architectures exhibit linearization as they approach the infinite width limit,
including any combination of FCNNs, convolutional neural network, recurrent
neural networks, attention, and others. However, the existing proofs tend to
be specific to particular architectures, and are often intricate in nature.
The most comprehensive proof we aware of that uniformly encompasses a diverse
set of architectures, is presented in [27, 31]. These works employed the
tensor product formalism [32], which can describe most relevant variants of
wide neural network architectures, as the composition of global linear
operations, and point-wise non linear functions.

  1. 1.

Relying on the semi-linear structure of FCNNs we were able show explicitly by
induction that for appropriate activation functions wide neural networks are
$n$-fixed weakly correlated, and $n^{\frac{3}{2}}$-exponential weakly
correlated, (and in most practical seance can be considered as
$n$-exponentially weakly correlated as well), (E).

  2. 2.

The framework of low correlations proves effective in discerning how
modifications to our network influence its linearization. For instance, it is
evident that $\sup_{n\in\mathbb{N}}\frac{\phi^{\left[n\right]}}{(n+1)!}$,
govern the rate of linearization in FCNNs (E). This observation is why we
demand for FCNNs, that over the relevant domain, the activation function
satisfy:

$\phi^{\left[n\right]}\leq O\left(\left(n+1\right)!\right)\ ,$ (23)

where $\phi^{[n]}$ is the $n$-th derivative of the network’s activation
function - $\phi$.

  3. 3.

Our proof for FCNNs can simply be generalised for any wide network, described
by the tensor programs formalism (E.5.1). This is because, similarly to FCNNs,
all such systems exhibit a wide semi-linear form by definition. Demonstrating
that the linearization of these systems arises from weak correlations, allows
us to utilize all of the insights we’ve found for weakly correlated systems in
general. We were also been able to conceive linearizing network-based systems,
that fall outside the scope of the tensor programs formalism (E.5.2).

Leveraging the notation of the asymptotic tensor behavior, our proof
accommodates a broad spectrum of initialization schemes, extending beyond the
Gaussian initialization predominantly employed in other studies.

##  5 Discussion and Outlook

The linearization of large and complex learning systems is a widespread
phenomenon, but our comprehension of it remains limited. We propose the weak
derivatives correlations (3.1), is the underlying structure behind this
phenomenon. We demonstrated that this formalism is natural for analyzing this
linearization: [i] It allows for the determination of if, and how fast a
general system undergoes linearization (3.3.1,4.2). [ii] It aids us in
analyzing the deviations from linearization during learning (4.0.1).

These insights raise a pivotal question (3.3.3): Is the emergence of the weak
correlations structure simply a tool to ensure a linear limit for
overparameterized systems? Or does weak correlations indicate an absence of
inherent biases, leading to linearization? If the latter is true, it suggests
that in systems with pre-existing knowledge, specific non-linear learning
methodologies reflecting those biases might be beneficial. That could
partially explain why the NTK limit falls short in comparison to finite neural
networks.

At the core of our weak derivatives correlation framework, is the random
tensor asymptotic behavior formalism, outlined in section 2. We have showcased
its efficacy in characterizing the asymptotic behavior of random tensors, and
we anticipate its utility to extend across disciplines that involve such
tensors.

We further discuss generalisations and limitations in appendix F.

## Acknowledgements

This work is supported in part by Israeli Science Foundation excellence
center, the US-Israel Binational Science Foundation, and the Israel Ministry
of Science.

## References

  * [1] Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton.  Speech recognition with deep recurrent neural networks.  In 2013 IEEE international conference on acoustics, speech and signal processing, pages 6645–6649. Ieee, 2013.
  * [2] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [3] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25, 2012.
  * [4] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484–489, 2016.
  * [5] Philip W Anderson.  More is different: broken symmetry and the nature of the hierarchical structure of science.  Science, 177(4047):393–396, 1972.
  * [6] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  Advances in neural information processing systems, 31, 2018.
  * [7] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  Advances in neural information processing systems, 32, 2019.
  * [8] Sanjeev Li, Arora, Simon S Du, Zhiyuan Hu, Wei, Russ R Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  Advances in neural information processing systems, 32, 2019.
  * [9] Yuan Cao and Quanquan Gu.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  Advances in neural information processing systems, 32, 2019.
  * [10] George Em Karniadakis, Ioannis G Kevrekidis, Lu Lu, Paris Perdikaris, Sifan Wang, and Liu Yang.  Physics-informed machine learning.  Nature Reviews Physics, 3(6):422–440, 2021.
  * [11] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean.  Power of data in quantum machine learning.  Nature communications, 12(1):2631, 2021.
  * [12] Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin.  Deep learning: a statistical viewpoint.  Acta numerica, 30:87–201, 2021.
  * [13] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In International conference on machine learning, pages 1675–1685. PMLR, 2019.
  * [14] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang.  Learning and generalization in overparameterized neural networks, going beyond two layers.  Advances in neural information processing systems, 32, 2019.
  * [15] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International conference on machine learning, pages 242–252. PMLR, 2019.
  * [16] Amit Daniely.  Sgd learns the conjugate kernel class of the network.  Advances in Neural Information Processing Systems, 30, 2017.
  * [17] Yuanzhi Li and Yingyu Liang.  Learning overparameterized neural networks via stochastic gradient descent on structured data.  Advances in neural information processing systems, 31, 2018.
  * [18] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  arXiv preprint arXiv:1810.02054, 2018.
  * [19] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  How neural networks extrapolate: From feedforward to graph neural networks.  arXiv preprint arXiv:2009.11848, 2020.
  * [20] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  Proceedings of the National Academy of Sciences, 116(32):15849–15854, 2019.
  * [21] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.  Deep double descent: Where bigger models and more data hurt.  Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.
  * [22] Song Mei and Andrea Montanari.  The generalization error of random features regression: Precise asymptotics and the double descent curve.  Communications on Pure and Applied Mathematics, 75(4):667–766, 2022.
  * [23] Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein.  Finite versus infinite neural networks: an empirical study.  Advances in Neural Information Processing Systems, 33:15156–15172, 2020.
  * [24] Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli.  Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel.  Advances in Neural Information Processing Systems, 33:5850–5861, 2020.
  * [25] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  Advances in neural information processing systems, 32, 2019.
  * [26] Chaoyue Liu, Libin Zhu, and Misha Belkin.  On the linearity of large non-linear models: when and why the tangent kernel is constant.  Advances in Neural Information Processing Systems, 33:15954–15964, 2020.
  * [27] Greg Yang and Etai Littwin.  Tensor programs iib: Architectural universality of neural tangent kernel training dynamics.  In International Conference on Machine Learning, pages 11762–11772. PMLR, 2021.
  * [28] Erwin Kreyszig.  Introductory functional analysis with applications, volume 17.  John Wiley & Sons, 1991.
  * [29] Yadolah Dodge.  The Oxford dictionary of statistical terms.  OUP Oxford, 2003.
  * [30] Yvonne M Bishop, Stephen E Fienberg, and Paul W Holland.  Discrete multivariate analysis: Theory and practice.  Springer Science & Business Media, 2007.
  * [31] Greg Yang.  Tensor programs ii: Neural tangent kernel for any architecture.  arXiv preprint arXiv:2006.14548, 2020.
  * [32] Greg Yang.  Wide feedforward or recurrent neural networks of any architecture are gaussian processes.  Advances in Neural Information Processing Systems, 32, 2019.

##  Appendix A Random Tensors Asymptotic Behavior

In the following sections, we utilize the results of this section throughout
our analyses repeatedly. Due to their intuitive nature, we may not
consistently specify when we do so, and which lemma/theorem we are employing.

###  A.1 Properties of our Norm

In this subsection, we explore the properties satisfied by the subordinate
norm. We omit the proofs as these properties are either well-known, or
straightforward to prove, (and also enjoyable to derive).

######  Lemma A.1 (Algebraic properties of the subordinate norm).

The subordinate tensor norm (1) satisfies the following algebraic properties:

  1. 1.

Given a tensor series $\left\\{M^{\left(d\right)}\right\\}_{d=1}^{D}$ where
$D\in\mathbb{N}\cup\left\\{\infty\right\\}$, it satisfies the triangle
inequality:

$\left\|\sum_{d=1}^{D}M^{\left(d\right)}\right\|\leq\sum_{d=1}^{D}\left\|M^{\left(d\right)}\right\|\
,$ (24)

where equality holds when the tensors are identical.

  2. 2.

Given a tensor $M_{i_{1}\ldots i_{r}}$, $1\leq i_{k}\leq N_{k}$ for $1\leq
k\leq r$, and $q\leq r\in\mathbb{N}$ vectors $v^{1}_{i_{1}}\ldots
v^{q}_{i_{q}}$ (with the same range of indices), then:

$\left\|M\cdot v^{1}\times\cdots\times
v^{q}\right\|\leq\left\|M\right\|\left\|v^{1}\right\|\cdots\left\|v^{q}\right\|\
.$ (25)

  3. 3.

Given two tensors $M_{\vec{i}_{1}}^{\left(1\right)}$ and
$M_{\vec{i}_{2}}^{\left(2\right)}$, their direct product
$M_{\vec{i}_{1}\vec{i}_{2}}=\left(M^{\left(1\right)}*M^{\left(2\right)}\right)_{\vec{i}_{1}\vec{i}_{2}}=M_{\vec{i}_{1}}^{\left(1\right)}M_{\vec{i}_{2}}^{\left(2\right)}$,
satisfies:

$\left\|M\right\|=\left\|M^{\left(1\right)}\right\|\left\|M^{\left(2\right)}\right\|\
.$ (26)

The generalization an arbitrary finite number of tensors is trivial.

######  Remark A.1.

Parts 1 and 3 are also satisfied by the Frobenius norm.

######  Lemma A.2 (Relation to the Frobenius Norm).

Given a tensor $M$ of rank $r\in\mathbb{N}$, the following holds:

  1. 1.

For any tensor $M$:

$\left\|M\right\|\leq\left\|M\right\|_{F}\ ,$ (27)

and if $r=1$ (i.e., the tensor is a vector), then:

$\left\|M\right\|=\left\|M\right\|_{F}=\sqrt{\sum_{i}M_{i}^{2}}\ .$ (28)

  2. 2.

For every $r^{\prime}=1...r$:

$\left\|M\right\|=\sup\left\\{\left\|M\cdot\left(\begin{array}[]{c}v^{1}\times\ldots\times
v^{r^{\prime}-1}\times\\\ v^{r^{\prime}+1}\times\ldots\times
v^{r}\end{array}\right)\right\|_{F}\left|\begin{array}[]{c}v^{1}\in
S_{N_{1}}\ldots v^{r^{\prime}-1}\in S_{N_{r^{\prime}-1}}\\\
v^{r^{\prime}+1}\in S_{N_{r^{\prime}+1}}\ldots v^{r}\in
S_{N_{r}}\end{array}\right.\right\\}\ .$ (29)

The first part of the lemma demonstrates that our norm is always bounded by
the Frobenius norm, and the two norms coincide for vectors. The second part
generalizes the first, indicating that when reducing any tensor to a vector,
the two norms once again agree.

######  Lemma A.3 (Properties of the Maximizing Vectors).

Given a tensor $M$ of rank $r\in\mathbb{N}$, there exist vectors $v^{1}\ldots
v^{r}$ of norm $1$ such that:

$\left\|M\right\|=M\cdot v^{1}\times\cdots\times v^{r}\ .$ (30)

This result indicates that the supremum is indeed a maximum. The vectors
$v^{1}\ldots v^{r^{\prime}-1},v^{r^{\prime}+1}\ldots v^{r}$ are also the ones
that maximize the cases demonstrated in the previous lemma.

Moreover, if the tensor is symmetric with respect to the permutation of the
indices $i_{1},i_{2},\ldots,i_{q}$ and is non-zero, then:

$v^{i_{1}}=v^{i_{2}}=\cdots=v^{i_{q}}\ .$ (31)

######  Remark A.2.

For $M=0$, any set of vectors maximizes our result, irrespective of whether
the vectors are identical or distinct.

###  A.2 Existence and Uniqueness of the Tensor Asymptotic Behavior

In this section, we discuss some of the more general properties that the
tensor asymptotic behavior notation satisfies, regardless of the norm it is
defined with respect to. The first lemma we present is a useful equivalent
definition for bounding tensor asymptotic behavior. This equivalent definition
will be beneficial for our later discussion:

######  Lemma A.4 (Equivalent Definitions for Tensor’s Asymptotic Bound).

For any random tensor $M$ and $f\in\mathcal{N}$, the two definitions for
bounding the tensor’s asymptotic behavior $O(M)\leq O(f)$ are equivalent (the
first is the original definition, (2.1)):

  1. 1.

$\forall
g\in\mathcal{N}\,s.t\,f=o\left(g\right):\lim_{n\rightarrow\infty}P\left(\left\|M_{n}\right\|\leq
g\left(n\right)\right)=1\ .$ (32)

  2. 2.

$\lim_{c\rightarrow\infty}\lim_{n\rightarrow\infty}P\left(\left\|M_{n}\right\|\leq
cf\left(n\right)\right)=1\ .$ (33)

(The same applies for $O(f)\leq O(M)$).

The order in which we take the limits in equation 33 is crucial, as any random
tensor satisfies the equation for any $f$, if we take first the limit of $c$.

It is straightforward to show that any random tensor $M$ has lower and upper
bounds:

######  Lemma A.5 (Bounding Tensor Asymptotic Behavior).

Given a random tensor $M$, there exist $h_{-},h_{+}\in\mathcal{N}$ such that:

$O\left(h_{-}\right)\leq O\left(M\right)\leq O\left(h_{+}\right)\ .$ (34)

To prove the asymptotic tensor behavior has meaning, we need to show that
bounds not only always exist, but that there is always one well-defined ”best”
upper bound - theorem 2.1. We prove this theorem after lemma A.5 by using
Zorn’s lemma.

######  Remark A.3.

It is simple to show that if there exist lower and upper bounds such that
$h_{+}=h_{-}$ and the exact asymptotic behavior is well defined, they are the
”definite bound” of theorem 2.1.

###### Proof - Lemma A.4.

We will prove the two directions of the lemma separately.

Assuming the second condition in equation 33 is satisfied:

Given some $0<p<1$, we know using equation 33 that there is some $0<c$ such
that for sufficiently large $n\in\mathbb{N}$:

$p\leq P\left(\left\|M_{n}\right\|\leq cf\left(n\right)\right)\ .$ (35)

Given some $g\in\mathcal{N}$ such that $f=o(g)$, we know that for sufficiently
large $n\in\mathbb{N}$:

$cf\left(n\right)\leq g\left(n\right)\ ,$ (36)

which means that for sufficiently large $n\in\mathbb{N}$:

$p\leq P\left(\left\|M_{n}\right\|\leq cf\left(n\right)\right)\leq
P\left(\left\|M_{n}\right\|\leq g\left(n\right)\right)\ .$ (37)

As we proved that for any $0<p<1$ we get that:

$\lim_{n\rightarrow\infty}\left(P\left(\left\|M_{n}\right\|\leq
g\left(n\right)\right)\right)=1\ .$ (38)

And as we proved that for any arbitrary $g\in\mathcal{N}$ such that $f=o(g)$,
we proved the first part of the lemma.

Assuming the first condition in equation 32, is satisfied:

If we assume in contradiction that equation 33 is not satisfied, we get that
there is some $0<p<1$ such as:

$\forall n_{0}\in\mathbb{N}\,0<c\,\exists n_{0}\leq
n\in\mathbb{N}:P\left(\left\|M_{n}\right\|\leq cf\left(n\right)\right)<p\ .$
(39)

In particular that means that if we choose the series
$\left\\{c_{i}=i\right\\}_{i=1}^{\infty}$, there are
$\tilde{n}_{1}<\tilde{n}_{2}<\tilde{n}_{3}...\in\mathbb{N}$ such as:

$\forall i\in\mathbb{N}:P\left(\left\|M_{\tilde{n}_{i}}\right\|\leq
if\left(\tilde{n}_{i}\right)\right)<p\ .$ (40)

The reason that we can require that
$\left\\{\tilde{n}_{i}\right\\}_{i=1}^{\infty}$ is rising, is that we know
that we can find such $n$-s for any sufficiently large $n_{0}$ and for any
$c$. So by induction we can require every time that every $\tilde{n}_{i}$ is
bigger than all previous $\tilde{n}$-s.

Assuming the first condition of equation 32 is satisfied:

Suppose, by contradiction, that equation 33 is not satisfied. Then, there
exists some $0<p<1$ such that:

$\forall n_{0}\in\mathbb{N},\,0<c,\,\exists n_{0}\leq
n\in\mathbb{N}:P\left(\left\|M_{n}\right\|\leq cf\left(n\right)\right)<p\ .$
(41)

In particular, if we choose the series $\forall i\in\mathbb{N}:c_{i}=i$, there
exist $\tilde{n}_{1}<\tilde{n}_{2}<\tilde{n}_{3}\dots\in\mathbb{N}$ such that:

$\forall i\in\mathbb{N}:P\left(\left\|M_{\tilde{n}_{i}}\right\|\leq
if\left(\tilde{n}_{i}\right)\right)<p\ .$ (42)

Since we can find such $n$-values for any sufficiently large $n_{0}$ and any
$c$, and we can require by induction that each $\tilde{n}_{i}$ is greater than
all previous $\tilde{n}$-values. .

We can now define the function:

$\forall
n\in\mathbb{N}:g\left(n\right)=\left(\min\left\\{i\in\mathbb{N}\mid\tilde{n}_{i}\leq
n\right\\}\right)f\left(n\right)\ .$ (43)

Since $\left\\{\tilde{n}_{i}\right\\}_{i=1}^{\infty}$ is increasing, we know
by the Archimedean property that
$\min\left\\{i\in\mathbb{N}\mid\tilde{n}_{i}\leq n\right\\}$ is also
increasing and unbounded, which implies:

$\lim_{n\rightarrow\infty}\frac{g\left(n\right)}{f\left(n\right)}=\lim_{n\rightarrow\infty}\min\left\\{i\in\mathbb{N}\mid\tilde{n}_{i}\leq
n\right\\}=\infty\ .$ (44)

However, by using equations 40 and 43, we also have:

$\forall n_{0}\in\mathbb{N},\,\exists n_{0}\leq
n\in\mathbb{N}:P\left(\left\|M_{n}\right\|\leq g\left(n\right)\right)<p\ ,$
(45)

which means that:

$\lim_{n\rightarrow\infty}P\left(\left\|M_{n}\right\|\leq
g\left(n\right)\right)\neq 1\ .$ (46)

This contradicts our assumption in equation 32. Therefore, by reductio ad
impossibile, equation 33 must be satisfied, completing the proof for the
second direction. ∎

###### Proof - Lemma A.5.

For a trivial lower bound, we choose $h_{-}$ such that $\forall
n\in\mathbb{N}:h_{-}(n)=0$.

We define $h_{+}$ as follows:

$\forall
n\in\mathbb{N}:h_{+}\left(n\right)=\inf\left\\{m\in\mathbb{R}\left|1-\frac{1}{n}\leq
P\left(\left\|M_{n}\right\|\leq m\right)\right.\right\\}\ .$ (47)

The infimum and the function are well defined because:

  1. 1.

The set is well defined.

  2. 2.

The set is non-empty; if it were empty, it would imply that there is some
probability that $\left\|M\right\|$, which is a positive number, is larger
than any real number, which is impossible.

  3. 3.

The set is defined with a total order $"<"$ and has a lower bound, $m=0$.

Since for any $0<p<1$, there exists some $n_{0}\in\mathbb{N}$ such that:

$\forall n_{0}\leq n\in\mathbb{N}:p\leq P\left(\left\|M_{n}\right\|\leq
m\right),$ (48)

we know that for any $h_{+}<g\in\mathcal{N}$, this is also true, which
implies:

$O(M)\leq O\left(h_{+}\right),$ (49)

completing the proof. ∎

###### Proof - Theorem 2.1.

General Idea of the Proof:

The proof proceeds as follows:

  * •

We consider the set of all upper bounds for $M$, denoted by $\mathcal{Z}$, and
use Zorn’s lemma to show that every chain444A chain, as defined in set theory,
is a subset for which the given partial order becomes a total order. in this
set has a lower bound within $\mathcal{Z}$.

  * •

Applying Zorn’s lemma again, we demonstrate that $\mathcal{Z}$ has a minimum.

  * •

We then show that the limiting behavior of this minimum is unique.

Existence of an Infimum for the Upper Bound Set:

We begin by defining the set:

$\mathcal{Z}=\left\\{h\in\mathcal{N}\left|O\left(M\right)\leq
O\left(h\right)\right.\right\\}\ .$ (50)

This set is:

  1. 1.

Well defined.

  2. 2.

Non-empty (as proven in lemma A.5).

  3. 3.

Defined with a partial order $h_{1}<h_{2}\leftrightarrow
O\left(h_{1}\right)<O\left(h_{2}\right)$.

According to Zorn’s lemma, if all chains in this set have a lower bound in
$\mathcal{Z}$, then $\mathcal{Z}$ has at least one minimum.

Given some chain in the set, $\mathcal{C}\subseteq\mathcal{Z}$, we know it is
lower bounded by the function $h_{-}$, which means (by using Zorn’s lemma) it
has at least one infimum (a lower bound without any smaller lower bounds). We
will choose such an infimum and denote it by $I\in\mathcal{N}$.

Proving that the Infimum is in $\mathcal{Z}$:

We assume, by contradiction, that this infimum is not in $\mathcal{Z}$, which
means there exists some $g\in\mathcal{N}$ such that $I=o(g)$ and for every
$0<p<1,n_{0}\in\mathbb{N}$, there exists $n_{0}\leq n\in\mathbb{N}$ such that:

$P\left(\left\|M_{n}\right\|\leq g\left(n\right)\right)<p\ .$ (51)

Since $I=o(g)$, we know that for any $c\in\mathbb{R}$ and sufficiently large
$n\in\mathbb{N}$:

$cI\left(n\right)\leq g\left(n\right)\ .$ (52)

Combining these equations, we obtain:

$\forall 0<c,\,n_{0}\in\mathbb{N}\,\exists n_{0}\leq
n\in\mathbb{N}:P\left(\left\|M_{n}\right\|\leq cI\left(n\right)\right)<p\ .$
(53)

In particular, if we choose the series $\forall i\in\mathbb{N}:c_{i}=i^{2}$,
there exist $\tilde{n}_{1}<\tilde{n}_{2}<\tilde{n}_{3}...\in\mathbb{N}$ such
that:

$\forall i\in\mathbb{N}:P\left(\left\|M_{\tilde{n}_{i}}\right\|\leq
i^{2}I\left(\tilde{n}_{i}\right)\right)<p\ .$ (54)

We can require that $\left\\{\tilde{n}_{i}\right\\}_{i=1}^{\infty}$ is
increasing for the same reason as before, as we know that we can find such
arbitrarily large $n$-values for any sufficiently large $n_{0}$ and for any
$c$, so we can, by induction, demand that each $\tilde{n}_{i}$ is greater than
all previous $\tilde{n}_{1}...\tilde{n}_{i-1}$.

Now, we define the function:

$J\left(n\right)=\left\\{\begin{array}[]{c}iI\left(n\right):\exists
i\in\mathbb{N}:n=\tilde{n}_{i}\\\
I\left(n\right):\text{else}\end{array}\right.\ .$ (55)

This function is well defined because there is only one $i$ for any $n$ such
that $n=\tilde{n}_{i}$, as it is an increasing series.

Using equations 54,55, we find that the subseries
$\left\\{\tilde{n}_{i}\right\\}_{i=1}^{\infty}$ satisfies:

$\forall
i\in\mathbb{N}:P\left(\left\|M\left(q\right)_{\tilde{n}_{i}}\right\|\leq
iJ\left(\tilde{n}_{i}\right)\right)<p\ .$ (56)

Applying lemma A.4 for the equivalency of the asymptotic bound definition, we
conclude that above this subseries $J\notin\mathcal{Z}$, which implies that
above this subseries $J$ is a lower bound of $\mathcal{Z}$ and consequently,
also of $\mathcal{C}$. Moreover, for all other $n$, we have $J=I$, and since
$I$ is a lower bound of $\mathcal{C}$, so is $J$. Since every $n\in\mathbb{N}$
belongs to one of these subseries, we conclude that $J$ is a lower bound of
$\mathcal{C}$ in general.

Furthermore, for every $i\in\mathbb{N}$ as $1\leq c_{i}$, we have:

$\forall n:I(n)\leq J(n)\rightarrow O(I)\leq O(J)\ .$ (57)

However, since $\left\\{\tilde{n}_{i}\right\\}_{i=1}^{\infty}$ is increasing
and unbounded, we know that there exists at least one subseries such that:

$\lim_{\tilde{n}_{i}\rightarrow\infty}\frac{J\left(\tilde{n}_{i}\right)}{I\left(\tilde{n}_{i}\right)}=\lim_{i\rightarrow\infty}c_{i}=\infty\rightarrow
O\left(J\right)\neq O\left(I\right)\ .$ (58)

This implies:

$O\left(I\right)<O\left(J\right)\rightarrow I<J\ .$ (59)

We have discovered that $J$ is greater than $I$, but smaller than all
functions in $\mathcal{C}$, which implies that it is a larger lower bound than
the infimum, which is impossible! and implies by ”reductio ad impossibile”
that every chain in $\mathcal{Z}$, has a lower bound in $\mathcal{Z}$.

Existence and Uniqueness of the Minimum:

Using Zorn’s lemma, we now know that $\mathcal{Z}$ has at least one minimum,
denoted by $f\in\mathcal{N}$. Our remaining task is to show that all other
minima in $\mathcal{Z}$ exhibit the same limiting behavior as $f$, which
implies the uniqueness of the minimal limiting behavior.

Let $g\in\mathcal{N}$ be another minimum. We define:

$\forall
n\in\mathbb{N}:h\left(n\right)=\min\left\\{f\left(n\right),g\left(n\right)\right\\}\
.$ (60)

We know that $h\leq f,g$ (as all of its elements are smaller or equal to those
of $f,g$), and we also know that $h\in\mathcal{Z}$ since $f,g\in\mathcal{Z}$
and for every $0<p<1$ we can choose the maximal $n_{0}$ from $f$ and $g$.
Thus, $h\in\mathcal{Z}$, but $h\leq f,g$ as well, where $f,g$ are minima
themselves. This implies:

$O\left(f\right)=O\left(h\right)=O\left(g\right)\rightarrow
O\left(f\right)=O\left(g\right)\ .$ (61)

Therefore, there exists a unique minimal limiting behavior, which implies that
the tensor’s asymptotic behavior is always well-defined. ∎

######  Remark A.4.

In our proof, we employed Zorn’s lemma twice. First, we used it to demonstrate
the existence of an infimum for every chain, and then, after showing that
these infima belong to $\mathcal{Z}$, we employed it again to establish that
$\mathcal{Z}$ has a minimum. At first glance, it may seem perplexing that we
needed to rely on Zorn’s lemma, an incredibly abstract and powerful tool
equivalent to the somewhat controversial axiom of choice, to prove that the
tensor’s asymptotic behavior, which has a much more grounded and intuitive
meaning, is well-defined.

One possible explanation for this discrepancy is that we may not have actually
required the full power of the axiom of choice, and our structures could be
simple enough that an alternative approach could have been taken to prove our
theorem without using Zorn’s lemma. We believe, however, that in the most
general case, Zorn’s lemma was indeed necessary, but it was only relevant for
extreme distributions lacking any tangible ”physical meaning.” For any well-
defined set of distributions with a clear underlying meaning, one could
potentially find an alternative method for demonstrating the existence of a
tight bound without invoking Zorn’s lemma.

In any case, as we demonstrated in Lemma A.5, there is no need for any of
these high-level tools to prove the existence of an upper bound.

###  A.3 Properties of the Asymptotic Behavior Notation

Having established that our notation is meaningful, we now aim to demonstrate
its usefulness. First, we need to address our earlier issue and define
”uniform asymptotic bound.” Once again, we omit the proofs in this (and next)
sections.

######  Definition A.1 (Uniform Tensors Asymptotic Bound).

Given a series of random tensors
$\left\\{M^{\left(d\right)}\right\\}_{d=1}^{D}$, where
$D\in\mathbb{N\cup\left\\{\infty\right\\}}$ (or, more precisely, a series of
random tensor series) with a limiting parameter $n$, we say that it is
uniformly asymptotically upper bounded by $f\in\mathbb{N}$ under some rising
monotonic function $\mathcal{K}^{1...D}:\mathbb{R}\rightarrow\mathbb{R}$:

$\forall d=1...D:O\left(M^{\left(d\right)}\right)\leq
O\left(\mathcal{K}^{d}\circ f\right)\quad\text{Uniformly}\ ,$ (62)

if and only if:

$\forall
g\in\mathcal{N}\,s.t\,f=o\left(g\right):\lim_{n\rightarrow\infty}P\left(\forall
d=1...D:\left\|M_{n}^{\left(d\right)}\right\|\leq\mathcal{K}^{d}\circ
g\left(n\right)\right)=1\ .$ (63)

The definition for a uniform lower asymptotic bound is analogous with reversed
directions.

######  Remark A.5.

As discussed in definition 2.1, it is clear that if $D$ is finite, then a
uniform bound is equivalent to a point-wise bound.

######  Lemma A.6 (Asymptotic Notation Inherits its Norm Properties).

Given a random tensor $M$ and a series of jointly distributed random tensors
$\left\\{M^{\left(d\right)}\right\\}_{d=1}^{D}$ (with $M$ as well), where
$D\in\mathbb{N}\cup\left\\{\infty\right\\}$, such that they are all uniformly
bounded:

$\forall d=1...D:O\left(M^{(d)}\right)\leq O\left(\mathcal{K}^{d}\circ
f\right)\quad\text{Uniformly}\ ,$ (64)

then:

  1. 1.

If some positive linear combination of $M^{(d)}$’s norms satisfies an
inequality of the form:

$\left\|M\right\|\leq\sum_{\tilde{d}=1}^{\tilde{D}}\lambda_{\tilde{d}}\prod_{d=D_{\tilde{d}-1}+1}^{D_{\tilde{d}}}\left\|M_{d}\right\|\
,$ (65)

where all of the coefficients are positive: $\forall
d=1...\tilde{D}:0\leq\lambda_{\tilde{d}}$ and we divided $1...D$ into a series
of finite intervals: $0=D_{1}<D_{2}<...<D_{\tilde{D}}=D$. Then the asymptotic
behavior of all the tensors satisfies the same inequality as well for every
$h\sim f$:

$O\left(M\right)\leq
O\left(\sum_{\tilde{d}=1}^{\tilde{D}}\lambda_{\tilde{d}}\prod_{d=D_{\tilde{d}-1}+1}^{D_{\tilde{d}}}\mathcal{K}^{d}\circ
h\right)\ ,$ (66)

and if the inequality is an equality for the norm, it is also an equality for
the ”large $O$-s.”

  2. 2.

Our asymptotic notation inherits all of the properties presented in lemma A.1.

######  Remark A.6.

The lemma still holds even if the tensor have additional indices, as we will
see in section (E.4), provided the number of additional index possibilities
remains finite in $n$.

###  A.4 Exploring the Relationship Between Asymptotic Behavior Notation and
the Tensors’ Moments

The final aspect of the asymptotic behavior notation we wish to explore is the
relationship between this notation and the moments of our tensors’ norm or
variables. This relationship is relatively intuitive and straightforward, and
will be useful in Section (E). We first need to introduce a simple notation
for every tensor $M_{\vec{i}}$ that will assist in examining tensor moments,
the norm expectation value, defined as:

$\left[M\right]=\sqrt{\frac{1}{N}\left\langle\left\|M\right\|^{2}\right\rangle}\
,$ (67)

######  Lemma A.7 (Asymptotic Behavior and Tensor Moments Equivalency).

Given a random tensor $M$ and a function $f\in\mathcal{N}$, then:

$O(M)\leq O(f)\ ,$ (68)

if and only if with probability arbitrarily close to 1:

$\left[M\right]=O\left(f\right)\ .$ (69)

The lemma is also applicable for the uniform bound in the case of infinite
number random tensors.

In (4.1), we highlighted that most assertions concerning the convergence of
$\mathcal{C}^{\prime}(F-\hat{y})$ relates to its expected value. However, we
can now also associate it with its asymptotic behavior throughout the entire
training trajectory. This association stems from the understanding that, if
our system exhibits a known average decay, the likelihood of significant
deviations from this typical variance range must also decrease, and
exponentially (at any decaying rate that is slower then our original rate).
Given that decaying geometric sums are convergent, we can infer that the
overall probability of the system defying our predicted asymptotic behavior is
likewise convergent. Given that we can choose the scaling of this probability
arbitrarily, we can set conditions such that the cumulative probability of any
deviation is arbitrary small. We introduce this notion for the reader’s
consideration and propose a detailed formulation as a future exercise.

##  Appendix B Additional Definitions

###  B.1  Derivatives Correlations Asymptotic Behavior

In our main text (3.2.1), we discussed that the definition for the asymptotic
behavior of the derivatives correlations is slightly nuanced, due to the many
different potential combinations of distinct inputs. Here we define it
rigorously.

######  Definition B.1 (Derivatives Correlations Asymptotic Behavior).

For every $D\in\mathbb{N}^{0}$, $d\in\mathbb{N}$, and $d_{1}\leq
d_{2}\leq...\leq d_{\tilde{d}}\in\mathbb{N}$ such that
$d_{1}+\ldots+d_{\tilde{d}}=d$:

$O_{d_{1}\ldots d_{\tilde{d}}}\left(\mathfrak{C}^{D,d}\right)\equiv
O_{x_{0},x_{1}\ldots
a_{\tilde{d}}\in\mathcal{P}}\left(\mathfrak{C}^{D,d}\left(x_{0},x_{1}^{\times
d_{1}}\ldots a_{\tilde{d}}^{\times d_{\tilde{d}}}\right)\right)\ .$ (70)

Inputs order doesn’t matter as correlations are symmetric concerning their
first derivatives. The factor $\frac{d!}{d_{1}!\cdots d_{\tilde{d}}!}$
accounts for the possible combinations. If $f\in\mathcal{N}$, we say:

$\mathfrak{C}^{D,d}=O\left(f\right)\ ,$ (71)

if and only if all combinations are uniformly bound by $f$. In the continuous
limit (extended training time), only $d_{1}=\ldots=d_{d}=1$ remains relevant.

###  B.2 Properly normalised GDML

Our main theorems (3.1,3.2 ) and corollary (4.0.1) are applicable for systems
that are properly scaled in the initial condition where $n\rightarrow\infty$,
defined as follows.

######  Definition B.2 (PGDML).

Given a GDML as described in section 3.1, we will say it is properly
normalized and denote it as PGDML if and only if:

$F\left(\theta_{0}\right)=O\left(n^{0}\right)$ (72) $\Delta
F\left(\theta_{0}\right)=F\left(\theta\left(1\right)\right)-F\left(\theta_{0}\right)=O\left(n^{0}\right)$
(73) $\mathfrak{C}^{1}=\left(N\eta\right)O\left(\nabla
F\left(\theta_{0}\right)\right)^{2}$ (74) $\forall
d\in\mathbb{N}:O\left(\nabla^{\times d}F\left(\theta_{0}\right)\right)\leq
O\left(\nabla F\left(\theta_{0}\right)\right)^{d}\quad\text{Uniformly.}$ (75)

The first two conditions (72,73) ensure that our system scale remains finite
for the initial condition. Condition 74 stipulates that the asymptotic
behavior of the kernel is maximal, given the asymptotic behavior of the first
derivative. This condition ensures that our system is genuinely learning and
not only memorizing. This is because the kernel for different inputs is
responsible for extrapolation, while the kernel with the same input twice
responsible for memorization. Condition 75 asserts that none of the higher
derivatives dominate the first for $n\rightarrow\infty$, a property that most
realistic scalable GDMLs satisfy, because if it is not satisfied, gradient
descent becomes irrelevant. We show that wide neural networks in general
satisfy that property in appendix E.5.

##  Appendix C Proof of Theorems 3.1,3.2

We can now proceed with the proofs of theorems 3.1 and 3.2. The general idea
has been outlined at the end of section 3.3.1.

###  C.1 First Direction of Theorems 3.1,3.2

Now that we understand how to work with the asymptotic behavior of random
tensors, we can proceed to prove our main theorems and corollary. We will
begin with the first direction of the theorems.

######  Lemma C.1 (Linearization Requires Weak Correlation).

  1. 1.

In theorem 3.1, if condition 1 is satisfied, then condition 2 is satisfied as
well.

  2. 2.

In theorem 3.2, if condition 1 is satisfied, then condition 2 is satisfied as
well.

###### Proof.

We only demonstrate that the $O_{1}\left(\mathfrak{C}\right)$ are bounded; The
proof the rest are bounded is the same, by considering more learning steps
after the initial condition.

For the initial condition, we know that any reparameterization $0<r$ satisfies
(11,20):

$\begin{array}[]{c}F\left(\theta\left(1\right)\right)-F_{lin}\left(1\right)=\\\
\sum_{d=1}^{\infty}\frac{\left(r\eta\right)^{d}}{d!}\left(\nabla^{\times
d}F\left(\theta_{0}\right)\left(\nabla
F\left(\theta_{0}\right)\left(x_{1}\right)^{T}\right)^{\times
d}\right)\left(-\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right)\left(x_{1}\right),\hat{y}\left(x_{1}\right)\right)\right)^{\times
d}-\\\ \left(-\left(r\eta\right)\nabla F\left(\theta_{0}\right)\nabla
F\left(\theta_{0}\right)\left(x_{1}\right)^{T}\left(-\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right)\left(x_{1}\right),\hat{y}\left(x_{1}\right)\right)\right)\right)=\\\
\sum_{d=2}^{\infty}r^{d}\left(\frac{\eta^{d}}{d!}\nabla^{\times
d}F\left(\theta_{0}\right)\left(\nabla
F\left(\theta_{0}\right)\left(x_{1}\right)^{T}\right)^{\times
d}\right)\left(-\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right)\left(x_{1}\right),\hat{y}\left(x_{1}\right)\right)\right)^{\times
d}=\\\
\sum_{d=2}^{\infty}r^{d}\left(\mathfrak{C}^{d}\right)^{\cdot,x_{1}^{\times
d}}\left(-\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right)\left(x_{1}\right),\hat{y}\left(x_{1}\right)\right)\right)^{\times
d}\ ,\end{array}$ (76)

and in the same way for every $D\in\mathbb{N}$:

$\begin{array}[]{c}\frac{\left(r\eta\right)^{\frac{D}{2}}}{D!}\nabla^{\times
D}F\left(\theta\left(1\right)\right)-\frac{\left(r\eta\right)^{\frac{D}{2}}}{D!}\nabla^{\times
D}F_{lin}\left(\theta_{0}\right)=\\\
\sum_{d=1}^{\infty}r^{\frac{D}{2}+d}\left(\mathfrak{C}^{D,d}\right)^{\cdot,x_{1}^{\times
d}}\left(-\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right)\left(x_{1}\right),\hat{y}\left(x_{1}\right)\right)\right)^{\times
d}\ .\end{array}$ (77)

Utilizing lemma A.6, it becomes evident that for properly normalized gradient
descent-based systems:

$O\left(\mathfrak{C}^{D,d}\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right),\hat{y}\right)^{\times
d}\right)\leq
O\left(\mathfrak{C}^{D,d}\right)O\left(\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right),\hat{y}\right)^{\times
d}\right)=O\left(\mathfrak{C}^{D,d}\right)\ .$ (78)

However, since our theorem should work for any $\hat{y}$, we can choose
$U=F\left(\theta_{0}\right)+c$, and obtain:

$O\left(\mathfrak{C}^{D,d}\mathcal{C}^{\prime}\left(F\left(\theta_{0}\right),\hat{y}\right)^{\times
d}\right)\propto
O\left(\mathfrak{C}^{D,d}\mathcal{C}^{\prime}\left(c\right)^{\times
d}\right)=O\left(\mathfrak{C}^{D,d}\right)\ ,$ (79)

as we can choose $c$ such that $\mathcal{C}^{\prime}(c)$ is the vector that
maximizes the correlation, as $\mathcal{C}^{\prime}$ is convex and the
correlations are symmetrical.

Given that we can choose an open set of different scalings of $r$, we know the
different elements in the series cannot cancel each other out. Consequently,
for $F-F_{lin}$ to decay, all the distinct elements must decay.

Assuming condition 1 in theorem 3.1:

Given that
$O\left(F\left(\theta\left(1\right)\right)-F_{lin}\left(1\right)\right)=O\left(\frac{1}{m\left(n\right)}\right)$
and for every $D\in\mathbb{N}$ we have
$O\left(\eta^{\frac{D}{2}}\nabla^{\times
D}F\left(\theta\left(1\right)\right)-\eta^{\frac{D}{2}}\nabla^{\times
D}F\left(\theta_{0}\right)\right)=O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)$,
it follows that each correlation must decay at least like:

$\forall 2\leq d\in\mathbb{N}:O\left(\mathfrak{C}^{d}\right)\leq
O\left(\frac{1}{m\left(n\right)}\right)\quad\text{Uniformly,}$ (80)

and

$\forall D,d\in\mathbb{N}:O\left(\mathfrak{C}^{D,d}\right)\leq
O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)\quad\text{Uniformly.}$ (81)

This completes the first part of the proof.

Assuming condition 1 in theorem 3.2:

By taking $r(n)$ arbitrarily close to ${m(n)}$, we find that for
$F\left(\theta\left(1\right)\right)-F_{lin}\left(1\right)$ to decay,
$r^{d}\mathfrak{C}^{d}$ must decay as well, which implies that:

$\forall d\in\mathbb{N}:O\left(\mathfrak{C}^{d}\right)\leq
O\left(\frac{1}{{m\left(n\right)}}\right)^{d}\ ,$ (82)

and

$\forall
D\in\mathbb{N}^{0},d\in\mathbb{N}:O\left(\mathfrak{C}^{D,d}\right)\leq
O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)^{d}\ .$ (83)

This concludes our proof.

∎

###  C.2 Second Direction of Theorems 3.1,3.2

We will now prove the other direction of the theorems, focusing on theorem 3.1
since the proofs for the other theorems are essentially the same. It should
also be noted that the corollary 4.0.1, which will be proven next, is almost a
generalization of this direction, except that it is only applicable for
sufficiently small learning rates.

######  Lemma C.2 (Asymptotic Behavior Normalization for weakly Correlated
PGDML).

Consider a weakly correlated PGDML as described in theorems 3.1,3.2 then we
have:

$\forall D\in\mathbb{N}:\eta^{D}O\left(\nabla^{\times
D}F\left(\theta_{0}\right)\right)^{2}\leq
O\left(1\right)\quad\text{Uniformly.}$ (84)

With Lemma C.2 at hand, we can now demonstrate the second direction of the
theorem by proving a slightly stronger version of it.

######  Lemma C.3 (Weak Correlations Create Linearization - First Theorem).

Assuming the conditions of theorem 3.1 part 1, then for every $s=1...S$:

  1. 1.

$O\left(F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)\right)\leq
O\left(\frac{1}{m\left(n\right)}\right)\ .$ (85)

  2. 2.

$O\left(\eta^{\frac{1}{2}}\nabla
F\left(\theta\left(s\right)\right)-\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)\right)\leq\gamma\ .$ (86)

  3. 3.

For every $2\leq D\in\mathbb{N}$

$O\left(\eta^{\frac{D}{2}}\nabla^{\times
D}F\left(\theta\left(s\right)\right)-\eta^{\frac{D}{2}}\nabla^{\times
D}F\left(\theta_{0}\right)\right)\leq
O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)\quad\text{uniformly.}$ (87)

Here, $\gamma$ is an asymptotic notation such that
$\gamma=O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)$, and when multiplied
with a first derivative of the hypothesis function in its initial condition,
it exhibits an asymptotic behavior of
$O\left(\gamma_{t}\eta^{\frac{1}{2}}\nabla F\left(\theta_{0}\right)\right)\leq
O\left(\frac{1}{m\left(n\right)}\right)$.

From proving lemmas C.1,C.3, we can conclude that theorems 3.1,3.2 have been
proven.

###### Proof of Lemma C.2.

Assume that the lemma is not satisfied, i.e.,

$\eta O\left(\nabla F\left(\theta_{0}\right)\right)^{2}\not\leq
O\left(1\right)\ ,$ (88)

then for some probability $0<p<1$, we have:

$O\left(1\right)<\eta O\left(\nabla F\left(\theta_{0}\right)\right)^{2}\ .$
(89)

Utilizing the third property of PGDML systems (74), we conclude that for some
relevant probability:

$O\left(1\right)<O\left(\mathfrak{C}^{1}\right)\ .$ (90)

However, for the reasons discussed earlier, the different elements in the
equation of motion cannot cancel each other out, as $\eta$ can be chosen from
an open set. This implies that the second property of PGDML systems (73)
cannot be satisfied, leading to the conclusion that:

$\eta O\left(\nabla F\left(\theta_{0}\right)\right)^{2}\leq O\left(1\right)\
,$ (91)

must hold.

By employing the fourth property (75) of PGDML systems, we obtain the desired
result.

∎

###### Proof of Lemma C.3.

We will prove the lemma using induction over the learning steps (of course).
The induction base for the ”zero” step, where $\theta=\theta_{0}$, is trivial.
Assuming the lemma holds for $s\in\mathbb{N}^{0}$, we observe that for every
$\left(D\in\mathbb{N}^{0},d\in\mathbb{N}\right)\neq\left(0,1\right)$, the
$d,D$ correlation satisfies the following for sufficiently small learning rate
$\eta$:

$\begin{array}[]{c}\mathfrak{C}^{D,d}\left(\theta\left(s\right)\right)=\eta^{\frac{D}{2}+d}\nabla^{\times
D+d}F\left(\theta\left(s\right)\right)^{T}\nabla
F\left(\theta\left(s\right)\right)^{\times d}\\\ =\\\
\left(\eta^{\frac{D+d}{2}}\nabla^{\times
D+d}F\left(\theta_{0}\right)+\gamma\right)^{T}\left(\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)+\gamma\right)^{\times d}\\\ =\\\
\mathfrak{C}^{D,d}+\gamma^{T}\left(\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)\right)^{\times
d}+\gamma^{T}\left(\gamma\times\left(\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)\right)^{\times d-1}\right)+\\\
\eta^{\frac{D+d}{2}}\nabla^{\times
D+d}F\left(\theta_{0}\right)\left(\gamma\times\left(\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)\right)^{\times
d-1}\right)+\text{comb}+O\left(\frac{1}{m\left(n\right)}\right)\\\ =\\\
\mathfrak{C}^{D,d}+O\left(\frac{1}{m\left(n\right)}\right)+O\left(\frac{1}{m\left(n\right)}\right)+d\mathfrak{C}^{D+1,d-1}\times\gamma+O\left(\frac{1}{m\left(n\right)}\right)\\\
=\\\ \mathfrak{C}^{D,d}+O\left(\frac{1}{m\left(n\right)}\right)\ .\end{array}$
(92)

Here, we used the derivatives correlation definition, lemmas, the induction
hypothesis, the bound of the correlations from condition 1, and the definition
of $\gamma$.

By employing the derivative’s correlation definition and condition 1, we
observe that:

$\begin{array}[]{c}\forall 2\leq
d\in\mathbb{N}:O\left(\mathfrak{C}^{d}\right)=O\left(\frac{1}{m\left(n\right)}\right)\
,\\\ \forall d\in\mathbb{N}:O\left(\mathfrak{C}^{1,d}\right)=\gamma\ ,\\\
\forall 2\leq
D\in\mathbb{N},d\in\mathbb{N}:O\left(\mathfrak{C}^{D,d}\right)=O\left(\frac{1}{\sqrt{m\left(n\right)}}\right)\
.\end{array}$ (93)

Furthermore:

$\begin{array}[]{c}\mathfrak{C}^{1,d}\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)=\eta^{\frac{1}{2}+d}\nabla^{\times
d+1}F\left(\theta_{0}\right)^{T}\left(\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)\right)^{\times d}=\\\ \eta^{d+1}\nabla^{\times
d+1}F\left(\theta_{0}\right)^{T}\left(\nabla
F\left(\theta_{0}\right)\right)^{\times d+1}=\mathfrak{C}^{d+1}\ .\end{array}$
(94)

Hence, using this equation, we can deduce that
$\mathfrak{C}^{D,d}\left(\theta\left(s+1\right)\right)$ satisfies the given
conditions as well. By incorporating this equation into our equation of motion
and employing the lemmas, we find that for a sufficiently small learning rate,
$F\left(\theta\left(s+1\right)\right)$ also satisfies the lemma. Consequently,
by induction, the lemma holds for all $s\in\mathbb{N}$. ∎

##  Appendix D Proof of Corollary 4.0.1

In this section, we prove corollary 4.0.1. The general approach for this proof
is akin to that of the first direction of theorems 3.1 and 3.2, albeit with an
additional focus on the evolution of the deviation throughout the induction
process.

Given the complexity of tracking all the derivatives simultaneously, our
strategy involves monitoring the difference between the parameters and their
linearization, as expressed in Equation (101). A significant challenge arises
in solving the equation of motion that these parameters must satisfy.

To circumvent this issue, we establish a link between this deviation and the
deviation of the generalization function from its linearization (101) up to
the highest order, as outlined in equation 106. By considering only the lowest
order terms, we obtain an equation of motion (113). In cases where the cost
function decays exponentially, and we are able to bound the deviation of this
equation.

###  D.1 Relations between Different Linearizations

In the main text, we linearised $F$ as $F_{lin}$ (11), by first considering
only the linear part of $F$, and then examining how it changes over time for a
given training path. However, there are alternative ways to linearise $F$ that
can be useful to consider. One such method involves taking only the linear
part of $F$, without considering the training path:

$\hat{F}(\theta)=F\left(\theta_{0}\right)+\nabla
F\left(\theta_{0}\right)^{T}\left(\theta-\theta_{0}\right)\ .$ (95)

Another useful definition is to examine how $\theta$ would develop over time
under the linear approximation for our training path:

$\begin{array}[]{c}\theta_{lin}\left(0\right)=\theta_{0}\quad\forall
s\in\mathbb{N}:\\\
\theta_{lin}\left(s+1\right)=\theta_{lin}\left(s\right)-\nabla
F\left(\theta_{0}\right)\left(x_{s}\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right)\left(x_{s}\right)-\hat{y}\left(x_{s}\right)\right)\
.\end{array}$ (96)

It can be observed that $F_{lin},\hat{F},\theta_{lin}$ satisfy the following
relation:

$\forall
s\in\mathbb{N}^{0}:F_{lin}\left(s\right)=\hat{F}\left(\theta_{lin}\left(s\right)\right)\
.$ (97)

A more refined relation is the one between $F\left(\theta_{lin}\right)$ and
$F_{lin}\left(\theta\right)$, defined for every $s=0...S$ as follows:

$O\left(F\left(\theta_{lin}(s)\right)-F_{lin}\left(s\right)\right)\leq
O\left(\frac{\varrho^{2}\left(s\right)}{{m\left(n\right)}}\right)\ ,$ (98)

where $\varrho$ is defined as:

######  Definition D.1 (Typical Linear Cumulative Deviation).

We define the typical linear cumulative deviation as the bound of the
cumulative deviation of $F_{lin}$ from $\hat{y}$:

$O\left(\varrho\left(s\right)\right)=\sum_{s^{\prime}=0}^{s-1}O\left(\mathcal{C}^{\prime}\left(F_{lin}\left(s_{1}\right)-\hat{y}\right)\right)\
,$ (99)

and in our case:

$O\left(\varrho\left(s\right)\right)\leq
O\left(\frac{1-e^{-\frac{s}{T}}}{1-e^{-\frac{1}{T}}}\right)\leq
O\left(1\right)\ .$ (100)

This implies that $\varrho(s)=o(m(n))$, which is essential for proving (98).
We will not provide this proof here, as we will not use it directly in the
remainder of this paper, and we will soon prove many similar identities.

###  D.2 Small Perturbation from the Linear Solution

The initial approach of the proof aimed to demonstrate that $F$ only deviates
slightly from $F_{lin}$, and that also its derivatives deviate slightly at the
initial conditions. The intention was to use induction to show that this holds
at each time step. This method is effective if the goal is merely to prove
that $F$ converges to $F_{lin}$ at a rate of $O\left(\frac{1}{m(n)}\right)$
for a fixed time step. However, it poses challenges when attempting to
understand how the two functions deviate from each other over time. This is
due to the necessity of simultaneously tracking the evolution of all
derivatives and the changes in correlations over time, which is nearly
impossible.

To circumvent this issue, rather than tracking all derivatives, we will
calculate how $F\left(\theta\left(s\right)\right)$ deviates from
$F_{lin}\left(s\right)$ by utilizing a similar relationship to the one we
discovered between $\theta_{lin}$ and $F_{lin}$. This will allow us to
establish bounds on $F-F_{lin}$. Although the two approaches are equivalent,
and the first one is more intuitively clear, the second approach simplifies
accurate and simple calculations by focusing on a single object, $F-F_{lin}$.

In the following lemma, we demonstrate how a small perturbation at a given
step ($s=0...S-1$) results in a small perturbation at the subsequent step
($s+1$). Then, we will use these results to inductively show the deviation in
time between the hypothesis function and its linear approximation.

We denote:

$\delta(s)=F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)\,,\,\eta^{\frac{1}{2}}\zeta(s)=\theta(s)-\theta_{lin}(s)\
,$ (101)

and assume that the deviation from linearity is small, hence:

$O\left(\delta(s)\right)\leq
O\left(\frac{f(s)}{m(n)}\right)\,,\,O\left(\zeta\left(s\right)\right)\leq
O\left(g\left(s\right)\right)\gamma\ ,$ (102)

where

$f\left(s\right),g\left(s\right)^{2},\varrho\left(s\right)^{2}=o\left(m\left(n\right)\right)\
.$ (103)

For some parts of our lemma, it will also be relevant to separate the
deviation of the parameters into two components:

$\zeta\left(s\right)=\zeta_{\gamma}\left(s\right)+\zeta_{m}\left(s\right)\ ,$
(104)

such that:

$O\left(\zeta_{\gamma}\left(s\right)\right)\leq
O\left(g_{\gamma}\left(s\right)\right)\gamma\,,\,O\left(\zeta_{m}\left(s\right)\right)\leq
O\left(\frac{g_{m}\left(s\right)}{m\left(n\right)}\right)\ .$ (105)

######  Remark D.1.

Here, we consider the case of a general rate of convergence for
$\mathcal{C}^{\prime}\left(F_{lin},\hat{y}\right)$, rather than exclusively
focusing on an exponential one. This is done to simplify the generalization of
our results for reader.

######  Lemma D.1 (Deviation of the parameters and of the hypothesis function
relations).

Given the conditions described above, then up to the leading order:

  1. 1.

$\begin{array}[]{c}\delta\left(s\right)=F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)\simeq\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta_{m}\left(s\right)+\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta_{\gamma}\left(s\right)+\\\
\begin{array}[]{c}\\\ \\\
\end{array}\sum_{s_{1},s_{2}=0}^{s-1}\mathfrak{C}^{2}\mathcal{C}^{\prime}\left(F_{lin}\left(s_{1}\right),\hat{y}\right)\times\mathcal{C}^{\prime}\left(F_{lin}\left(s_{2}\right),\hat{y}\right)+\\\
2\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\zeta_{\gamma}\left(s\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\zeta_{\gamma}\left(s\right)^{\times 2}\
,\end{array}$ (106)

which means:

$\begin{array}[]{c}O\left(\delta\left(s\right)\right)=O\left(F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)\right)\leq\\\
O\left(\frac{g_{m}\left(s\right)}{m\left(n\right)}\right)+O\left(\frac{\left(g_{\gamma}\left(s\right)+\varrho\left(s\right)\right)^{2}}{m\left(n\right)}\right)\leq
O\left(\frac{\left(g\left(s\right)+\varrho\left(s\right)\right)^{2}}{m\left(n\right)}\right)\
.\end{array}$ (107)

  2. 2.

$O\left(\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}-\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\right)\leq
O\left(g\left(s\right)+\varrho\left(s\right)\right)\gamma\ .$ (108)

  3. 3.

$\mathcal{\mathcal{C}}^{\prime}\left(F\left(\theta\left(s\right)\right),\hat{y}\right)-\mathcal{\mathcal{C}}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\simeq\mathcal{\mathcal{C}}^{\prime\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\delta\left(s\right)\
.$ (109)

where $\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s\right),\hat{y}\right)$
is a positive random matrix such as if the asymptotic behavior of
$\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)$ is bound (as
in our case), so is
$\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s\right),\hat{y}\right)$.

  4. 4.

$\begin{array}[]{c}\eta^{\frac{1}{2}}\zeta\left(s+1\right)-\eta^{\frac{1}{2}}\zeta\left(s\right)=\theta\left(s+1\right)-\theta_{lin}\left(s+1\right)-\eta^{\frac{1}{2}}\zeta\left(s\right)\simeq\\\
\begin{array}[]{c}\\\ \\\ \end{array}-\eta\nabla
F\left(\theta_{0}\right)\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)\delta\left(s\right)+O\left(g\left(s\right)+\varrho\left(s\right)\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\eta^{\frac{1}{2}}\gamma\
,\end{array}$ (110)

which means:

$O\left(\zeta\left(s+1\right)-\zeta\left(s\right)\right)\leq
O\left(\frac{f\left(s\right)}{m\left(n\right)}\right)+O\left(\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\right)O\left(g\left(s\right)+\varrho\left(s\right)\right)\gamma\
.$ (111)

  5. 5.

$\begin{array}[]{c}O\left(\delta\left(s+1\right)-\delta\left(s\right)+\Theta_{0}\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\delta\left(s\right)\right)\leq\\\
\begin{array}[]{c}\\\ \\\
\end{array}O\left(\frac{\left(g\left(s\right)+\varrho\left(s\right)\right)^{2}}{m\left(n\right)}\right)O\left(\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\right)\
.\end{array}$ (112)

######  Remark D.2.

An important note for our proofs is that all of these components can be
generalized to the case where $\zeta(s),\delta(s)$ are not the ”original”
deviations, as long as they satisfy equation 102.

We can now use this result to prove corollary 4.0.1 by induction. In fact, for
the conditions of the corollary at $s=0$, the induction hypothesis is
trivially satisfied as $F(\theta)(0)=F_{lin}(0),\theta(0)=\theta_{lin}(0)$. It
is straightforward to show that the contributions of the part multiplied by
$O\left(\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\right)$
are irrelevant for the possible deviation, as
$\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\rightarrow
0\,,\,O\left(\varrho\left(s\right)\right)\leq O\left(1\right)$. Consequently,
we are left with equations of motion for the asymptotic behavior of the form:

$O\left(\zeta\left(s+1\right)-\zeta\left(s\right)\right)\leq
O\left(\frac{f\left(s\right)}{m\left(n\right)}\right)\quad\delta\left(s+1\right)-\delta\left(s\right)+\Theta_{0}\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\delta\left(s\right)\simeq
0\ .$ (113)

However, $\Theta_{0},\mathcal{C}^{\prime\prime}$ are positively defined bound
matrices, so for a learning rate that is sufficiently small (which would be of
the same order of magnitude as the learning rate needed for our system to
consistently learning, and for the case where
$\mathcal{C}(x)=\frac{1}{2}x^{2}$, exactly the same), we find that on average
this term can only contribute to the shrinkage of $\delta(s)$. This means that
neglecting this term for large $s$ would provide an upper bound for the rate
of deviation. Thus, we have discovered that the asymptotic behavior of
$\delta$ (and consequently, $\zeta$) with respect to time is for large $s$ is
bounded by:

$\delta\left(s+1\right)-\delta\left(s\right)\simeq 0\ .$ (114)

This proves our corollary.

###### Proof.

Part - (1):

$\begin{array}[]{c}F\left(\theta\left(s\right)\right)=F\left(\theta_{lin}\left(s\right)+\eta^{\frac{1}{2}}\zeta\left(s\right)\right)=_{1}\\\
\begin{array}[]{c}\\\ \\\
\end{array}F\left(\theta_{0}-\eta\sum_{s^{\prime}=0}^{s-1}\nabla
F\left(\theta_{0}\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta^{\frac{1}{2}}\zeta\left(s\right)\right)=_{2}\\\
F\left(\theta_{0}\right)-\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1}\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta\left(s\right)+\\\ \begin{array}[]{c}\\\ \\\
\end{array}\sum_{s_{1},s_{2}=0}^{s-1}\mathfrak{C}^{2}\mathcal{C}^{\prime}\left(F_{lin}\left(s_{1}\right),\hat{y}\right)\times\mathcal{C}^{\prime}\left(F_{lin}\left(s_{2}\right),\hat{y}\right)+\\\
2\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\zeta\left(s\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\zeta\left(s\right)^{\times
2}+\ldots\simeq_{3}\\\ \begin{array}[]{c}\\\ \\\
\end{array}F_{lin}\left(s\right)+\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta\left(s\right)+\sum_{s_{1},s_{2}=0}^{s-1}\mathfrak{C}^{2}\mathcal{C}^{\prime}\left(F_{lin}\left(s_{1}\right),\hat{y}\right)\times\mathcal{C}^{\prime}\left(F_{lin}\left(s_{2}\right),\hat{y}\right)+\\\
2\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\zeta\left(s\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\zeta\left(s\right)^{\times 2}\ ,\end{array}$
(115)

where in (1) we used equation the definition of $\theta_{lin}$ (96), in (2) we
expanded our generalisation function as a Taylor sires, and the definition of
the derivatives correlations (3.1). In (3) we used the fact that under our
assumptions our system is exponentially weakly correlated. Using this result
we get our desired identity.

Subtracting $F_{lin}$ we get using the weak derivatives correlations property
that up to the leading order:

$\begin{array}[]{c}F\left(\theta\left(s\right)\right)-F_{lin}\left(s\right)\simeq\\\
\begin{array}[]{c}\\\ \\\ \end{array}\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta\left(s\right)+\sum_{s_{1},s_{2}=0}^{s-1}\mathfrak{C}^{2}\mathcal{C}^{\prime}\left(F_{lin}\left(s_{1}\right),\hat{y}\right)\times\mathcal{C}^{\prime}\left(F_{lin}\left(s_{2}\right),\hat{y}\right)+\\\
2\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\zeta\left(s\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\zeta\left(s\right)^{\times 2}\simeq\\\
\begin{array}[]{c}\\\ \\\ \end{array}\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta_{m}\left(s\right)+\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta_{\gamma}\left(s\right)+\\\
\sum_{s_{1},s_{2}=0}^{s-1}\mathfrak{C}^{2}\mathcal{C}^{\prime}\left(F_{lin}\left(s_{1}\right),\hat{y}\right)\times\mathcal{C}^{\prime}\left(F_{lin}\left(s_{2}\right),\hat{y}\right)+\\\
\begin{array}[]{c}\\\ \\\
\end{array}2\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\zeta_{\gamma}\left(s\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\zeta_{\gamma}\left(s\right)^{\times 2}=\\\
O\left(\frac{g_{m}\left(s\right)+g_{\gamma}\left(s\right)}{m\left(n\right)}\right)+O\left(\frac{\varrho\left(s\right)^{2}}{m\left(n\right)}\right)+2O\left(\frac{\varrho\left(s\right)g_{\gamma}\left(s\right)}{m\left(n\right)}\right)+O\left(\frac{g_{\gamma}^{2}\left(s\right)}{m\left(n\right)}\right)=\\\
\begin{array}[]{c}\\\ \\\
\end{array}O\left(\frac{g_{m}\left(s\right)}{m\left(n\right)}\right)+O\left(\frac{\left(g_{\gamma}\left(s\right)+\varrho\left(s\right)\right)^{2}}{m\left(n\right)}\right)\leq
O\left(\frac{\left(g\left(s\right)+\varrho\left(s\right)\right)^{2}}{m\left(n\right)}\right)\
,\end{array}$ (116)

which finishes our proof.

Part 2:

Using the same ideas we get:

$\begin{array}[]{c}\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}=\eta^{\frac{1}{2}}\nabla
F\left(\theta_{lin}\left(s\right)+\eta^{\frac{1}{2}}\zeta\left(s\right)\right)^{T}=\\\
\begin{array}[]{c}\\\ \\\
\end{array}\eta^{\frac{1}{2}}\nabla_{T}F\left(\theta_{0}-\eta\sum_{s^{\prime}=0}^{s-1}\nabla
F\left(\theta_{0}\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta^{\frac{1}{2}}\zeta\left(s\right)\right)=\\\
\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}-\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\zeta\left(s\right)+\ldots=\\\
\begin{array}[]{c}\\\ \\\ \end{array}\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}+O\left(\varrho\left(s\right)\right)\gamma_{t}+O\left(g\left(s\right)\right)\gamma_{t}\
.\end{array}$ (117)

Taking transpose on both sides we get finish our proof.

Part 3:

Using the definition of $\delta$ and the fact that $\mathcal{C}$ is analytical
we know that up to the highest order:

$\mathcal{\mathcal{C}}^{\prime}\left(F\left(\theta\left(s\right)\right),\hat{y}\right)=\mathcal{\mathcal{C}}^{\prime}\left(F_{lin}\left(s\right)+\delta\left(s\right),\hat{y}\right)\simeq\mathcal{\mathcal{C}}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)+\mathcal{\mathcal{C}}^{\prime\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\delta\left(s\right)$
(118)

and as $\mathcal{C}$ is convex (3), we know that it’s second derivative is
always a positive matrix. And that if the first derivative is bound, so is the
second one.

Part 4:

Using the equation of motion for $\theta$ (96), and parts 2,3 of this lemma we
get that up to leading order:

$\begin{array}[]{c}\begin{array}[]{c}\\\ \\\
\end{array}\theta\left(s+1\right)=\theta\left(s\right)-\eta\nabla
F\left(\theta\left(s\right)\right)\mathcal{C}^{\prime}\left(F\left(\theta\left(s\right)\right),\hat{y}\right)\simeq\\\
\theta\left(s\right)-\eta\left(\begin{array}[]{c}\nabla
F\left(\theta_{0}\right)+\\\
O\left(g\left(s\right)+\varrho\left(s\right)\right)\eta^{\frac{1}{2}}\gamma\end{array}\right)\left(\begin{array}[]{c}\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)+\\\
\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)\delta\left(s\right)\end{array}\right)\simeq\\\
\begin{array}[]{c}\\\ \\\ \end{array}\theta\left(s\right)-\eta\nabla
F\left(\theta_{0}\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)-\eta\nabla
F\left(\theta_{0}\right)\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)\delta\left(s\right)+\\\
O\left(g\left(s\right)+\varrho\left(s\right)\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\eta^{\frac{1}{2}}\gamma\end{array}$
(119)

and as:

$\begin{array}[]{c}\theta\left(s\right)-\eta\nabla
F\left(\theta\left(s\right)\right)\mathcal{C}^{\prime}\left(F\left(\theta\left(s\right)\right),\hat{y}\right)=\\\
\begin{array}[]{c}\\\ \\\
\end{array}\theta_{lin}\left(s\right)+\eta^{\frac{1}{2}}\zeta\left(s\right)-\eta\nabla
F\left(\theta\left(s\right)\right)\mathcal{C}^{\prime}\left(F\left(\theta\left(s\right)\right),\hat{y}\right)=\theta_{lin}\left(s+1\right)+\eta^{\frac{1}{2}}\zeta\left(s\right)\
,\end{array}$ (120)

we get the desired result.

Part 5:

Using the equation of motion for $\theta$, one can see that:

$\begin{array}[]{c}F\left(\theta\left(s+1\right)\right)=F\left(\begin{array}[]{c}\theta_{lin}\left(s+1\right)-\eta\nabla
F\left(\theta_{0}\right)\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)\delta\left(s\right)+\\\
\eta^{\frac{1}{2}}\zeta\left(s\right)+O\left(g\left(s\right)+\varrho\left(s\right)\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\eta^{\frac{1}{2}}\gamma\end{array}\right)\\\
\simeq_{1}\\\ F_{lin}\left(s+1\right)-\eta\nabla
F\left(\theta_{0}\right)^{T}\nabla
F\left(\theta_{0}\right)\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)\delta\left(s\right)+\\\
\begin{array}[]{c}\\\ \\\ \end{array}\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\zeta\left(s\right)+O\left(g\left(s\right)+\varrho\left(s\right)\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\eta^{\frac{1}{2}}\nabla
F\left(\theta_{0}\right)^{T}\gamma+\\\
\sum_{s_{1},s_{2}=0}^{s-1}\mathfrak{C}^{2}\mathcal{C}^{\prime}\left(F_{lin}\left(s_{1}\right),\hat{y}\right)\times\mathcal{C}^{\prime}\left(F_{lin}\left(s_{2}\right),\hat{y}\right)+\\\
\begin{array}[]{c}\\\ \\\
\end{array}2\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\zeta\left(s\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\\\
2O\left(g\left(s\right)+\varrho\left(s\right)\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\sum_{s^{\prime}=0}^{s-1}\mathfrak{C}^{1,1}\gamma\mathcal{C}^{\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)+\\\
\begin{array}[]{c}\\\ \\\ \end{array}\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\zeta\left(s\right)^{\times
2}+O\left(g\left(s\right)+\varrho\left(s\right)\right)^{2}\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)^{2}\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\gamma^{\times 2}+\\\
2O\left(g\left(s\right)+\varrho\left(s\right)\right)\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\eta\nabla^{\times
2}F\left(\theta_{0}\right)^{T}\left(\gamma\times\zeta\left(s\right)\right)\\\
\simeq_{2}\\\
F_{lin}\left(s+1\right)-\Theta_{0}\mathcal{C}^{\prime\prime}\left(F_{lin}\left(s^{\prime}\right),\hat{y}\right)\delta\left(s\right)+\delta\left(s\right)+\\\
\begin{array}[]{c}\\\ \\\
\end{array}2O\left(\frac{g\left(s\right)+\varrho\left(s\right)}{m\left(n\right)}\right)O\left(\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\right)+O\left(\frac{\left(g\left(s\right)+\varrho\left(s\right)\right)^{2}}{m\left(n\right)}\right)O\left(\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\right)^{2}+\\\
2O\left(\frac{g^{2}\left(s\right)+\varrho\left(s\right)g\left(s\right)}{m\left(n\right)}\right)O\left(\mathcal{C}^{\prime}\left(F_{lin}\left(s\right),\hat{y}\right)\right)\
.\end{array}$ (121)

where in (1) We use part 1 of the lemma, when we remembered that
$O(\delta)\leq O\left(\frac{1}{m(n)}\right)$ so it can be consider as
$\zeta_{m}$. In part (2) we use the definition of $F_{lin}$, $\Theta_{0}$ and
part 1 once again where we gathered all of the components that have only
$\zeta(s)$ to get $\delta(s)$. Then we just used the asymptotic behavior of
all of the components and took the ”worst case scenario” to get equation 112.
∎

##  Appendix E Wide Neural Networks are weakly correlated PGDML Systems

###  E.1 General Idea

We start with fully connected neural networks. Although the proof is
technically intricate, its underlying concept is straightforward: For the
first layer, we observe that all higher correlations exhibit the appropriate
asymptotic behavior. We then proceed to prove by induction that all layers
manifest the same asymptotic behavior. Consider the second correlation, for
instance, which we analyze as follows:

For any general layer $l=1,\ldots,L$, defining $\nabla_{-l}$ as the
derivatives with respect to parameters from layers $1$ to $l-1$ (E.2), we
employ the equation for fully connected neural networks (127):

$\begin{array}[]{c}l=0,\ldots,L:F^{(l)}=\theta^{(l,l-1)}\phi\left(F^{(l-1)}\right)+\theta^{(l)}\
,\\\ \forall x\in X:F(\theta)\left(x\right)=F^{(L)}\left(x\right),\quad
F^{(0)}\left(x\right)=a\ ,\end{array}$ (122)

to demonstrate that:

$\begin{array}[]{c}\begin{array}[]{c}\\\ \\\
\end{array}\nabla_{\left(-l\right)}^{\times
2}F^{\left(l\right)}=\nabla_{\left(-l\right)}^{\times
2}\left(\theta^{\left(l,l-1\right)}\phi\left(F^{\left(l-1\right)}\right)+\theta^{(l)}\right)=\\\
\nabla_{\left(-l\right)}\times\nabla_{\left(-l\right)}\left(\theta^{\left(l,l-1\right)}\phi\left(F^{\left(l-1\right)}\right)+\theta^{(l)}\right)=\nabla_{\left(-l\right)}\times\left(\theta^{\left(l,l-1\right)}\nabla_{\left(-l\right)}\phi\left(F^{\left(l-1\right)}\right)\right)=\\\
\begin{array}[]{c}\\\ \\\
\end{array}\nabla_{\left(-l\right)}\times\left(\theta^{\left(l,l-1\right)}\phi^{\prime}\left(F^{\left(l-1\right)}\right)\nabla_{\left(-l\right)}F^{\left(l-1\right)}\right)=\\\
\theta^{\left(l,l-1\right)}\phi^{\prime\prime}\left(F^{\left(l-1\right)}\right)\nabla_{\left(-l\right)}F^{\left(l-1\right)}\times\nabla_{\left(-l\right)}F^{\left(l-1\right)}+\theta^{\left(l,l-1\right)}\phi^{\prime}\left(F^{\left(l-1\right)}\right)\nabla_{\left(-l\right)}^{\times
2}F^{\left(l-1\right)}\end{array}$ (123)

Consequently, the contribution to the $l$-th correlation (13) from this part
is proportional to:

$\theta^{\left(l,l-1\right)}\phi^{\prime\prime}\left(F^{\left(l-1\right)}\right)\mathfrak{C}_{\left(l-1\right)}^{1}\times\mathfrak{C}_{\left(l-1\right)}^{1}+\theta^{\left(l,l-1\right)}\phi^{\prime}\left(F^{\left(l-1\right)}\right)\mathfrak{C}_{\left(l-1\right)}^{2}\
.$ (124)

Here we have two terms. We can show the right-hand term is small simply by
induction. The proof that the left-hand term is also small is more complex,
involving the demonstration that for all hidden layers, the relevant
contribution from the first correlation originates from its diagonal terms,
i.e., $(\mathfrak{C}_{(-l)}^{1})_{ii}$.

We can now show that in the term, the left index is identical for both
correlations, which follows that for most indices, the relevant terms are
offset by the irrelevant ones, keeping our expression small.

For the case that one of the derivative does not belong to layers $l=1$ to
$l-1$, we explicitly show this term to be negligible, as for most indices it
simply resets:

$\nabla_{i^{l}i^{l-1}}F_{i}^{\left(l\right)}\propto\delta_{i^{l}i}$ (125)

In the general case of the $D$-th correlation, while there is some complexity
in tracing the combinatorial terms from various combinations of derivatives,
the fundamental principle remains consistent.

The generalization of this approach for other architectures is discussed in
Section E.5.

###  E.2 Asymptotic Behavior of Wide FCN at Initialisation

######  Remark E.1.

Throughout this paper we considered $\left\|M\right\|$ or $O(M)$ as our way to
evaluate the size of our random tensors. But here we mainly consider the
normalised terms instead:

$\frac{1}{\sqrt{N}}\left\|M\right\|\quad\text{and}\quad\frac{1}{\sqrt{N}}O\left(M\right)\
.$ (126)

This is because, in practice, what we are interested of is the average
asymptotic behavior of a tensor, and not the accumulative one.

Fully connected neural networks of depth $2\leq L\in\mathbb{N}$, characterized
by $L$ parameter vectors (the biases $\theta^{(1)},\ldots,\theta^{(L)}$), and
$L$ parameter matrices (the weights $\theta^{(L,L-1)},\ldots,\theta^{(1,0)}$),
such as:

$\begin{array}[]{c}l=0,...,L:F^{(l)}=\theta^{(l,l-1)}\phi\left(F^{(l-1)}\right)+\theta^{(l)}\
,\\\ \forall x\in X:F(\theta)\left(x\right)=F^{(L)}\left(x\right),\quad
F^{(0)}\left(x\right)=a\ .\end{array}$ (127)

In this representation, $F^{(0)},F^{(1)},\ldots,F^{(L-1)},$ and $F^{(L)}$
constitute the input, inner, and output layers, respectively. The activation
function $\phi$ is analytical, and all of its derivatives are bounded as
described in (23).

######  Remark E.2.

Generally when working with FCNN we do not operate the activation function
over the zero layer, the input. But to make the induction slightly easier, we
will simplify our expression such as $\phi$ operates over all layers. It makes
no real difference

We focus on ”wide” neural networks where the depth $L$ is fixed. As long as
$L=O(\log(n))$, we can expect an NTK-like behavior for large $n$, but for
simplicity, we focus on the scenario where $L$ remains constant in $n$. We
introduce a limiting parameter $n\in\mathbb{N}$ such that the width of all the
hidden layers satisfies $n\leq n_{1},\ldots,n_{L-1}$. To simplify our work, we
will amend this assumption by postulating that all layers exhibit the same
asymptotic behavior of $n$ \- $n_{1},\ldots,n_{L-1}\sim n$. This modification
does not affect our theorems and lemmas, as it merely establishes a lower
bound of our original assumption. As the sizes of the zeroth and last layer
are constant (the dimensions of the input and output layers stay fixed in $n$
of course), we arrive at:

$n_{1},\ldots,n_{L-1}\sim n\quad\text{and}\quad n_{0},n_{L}\sim 1\ .$ (128)

Back in the 1960s, it was demonstrated that with Gaussian initialization, we
can keep our layers normalised by selecting initial parameters as follows:

$\forall
l=1,\ldots,L:\theta_{0}^{(l,l-1)}\sim\mathcal{N}\left(0,\frac{1}{{n_{l}}}\right),\,\theta_{0}^{(l)}\sim\mathcal{N}\left(0,1\right)\
.$ (129)

Despite the specificity of this initialization algorithm, it contradicts the
broader spirit of this paper. It’s not only overly restrictive but also
complicates our work by colliding with our framework of tensor’s asymptotic
behavior. Rather than focusing on a particular initialization scheme like the
normal distribution, we will identify and utilize the relevant properties
inherent in the distribution.

######  Definition E.1 (Appropriate Initialization scheme for Wide Neural
Networks).

Given a wide neural network as defined above, we characterize the distribution
for the initial condition $\theta$ as appropriate if and only if for every
probability arbitrarily close to 1, the following properties hold:

  1. 1.

Different elements of $\theta$ are independent. And for each layer
$l=1,...,L$, $\theta^{(l,l-1)}$’s and $\theta^{(l)}$’s elements share the same
distribution.

  2. 2.

$\theta$ is symmetric around 0 (implying that all odd moments are nullified):

$\forall D\in\mathbb{N}\setminus 2\mathbb{N}:\left\langle\theta^{\cdot
D}\right\rangle=0\ .$ (130)

  3. 3.

For every layer $l=1,...,L$, all moments of $\theta$ are uniformly normalized:

$\forall
D\in\mathbb{N}:\begin{array}[]{c}O\left(1\right)^{D}\leq\frac{1}{\sqrt{n_{l}}}O\left(\left(\theta^{\left(l\right)}\right)^{\cdot
D}\right)\leq D!O\left(1\right)^{D},\\\
O\left(\frac{1}{\sqrt{n_{l-1}}}\right)^{D}\leq\frac{1}{\sqrt{N_{l}}}O\left(\left(\theta^{\left(l,l-1\right)}\right)^{\cdot
D}\right)\leq
D!O\left(\frac{1}{\sqrt{n_{l-1}}}\right)^{D},\end{array}\quad\text{Uniformly}$
(131)

where $N_{l}=n_{l}n_{l-1}$ is the total number of parameters in the $l$-th
layer.

where the elemental tensor power defined such as:

$\forall D\in\mathbb{N}:\left(M^{\cdot D}\right)_{\vec{i}}=M^{D}_{\vec{i}}\ .$
(132)

The first two conditions ensure that our system is unbiased, while the third
condition guarantees that our system will not be dominated by a
disproportionate probabilistic ”tail.”

We delegate to the reader the verification that Gaussian initialization
qualifies as an appropriate initialization.

######  Remark E.3.

Conditions 1,2 can be generalized to be fulfilled in the limit of large $n$,
provided this convergence occurs rapidly enough. Nevertheless, any
complexities arising from this generalization are technical and do not affect
our analysis.

For the remainder of this section, we will omit the biases from our
discussion, as they do not add any substantial insights or implications for
the points under consideration and won’t change any of our results.

######  Lemma E.1 (Normalization of Layers in Proper Wide Neural Networks).

Given a wide neural network, if the initial condition is appropriately set,
then all the moments across every layer $l=1...L$ are well normalized:

$\frac{1}{\sqrt{n_{l}}}O\left(F^{(l)}\right)=O\left(1\right)\ .$ (133)

The final parameter that we need to normalize in our system is the dynamic one
- the learning rate, denoted by $\eta$. In an attempt to generalize Gaussian
initialization, we will adopt the standard method of normalization for $\eta$:

$\eta\sim\frac{1}{n}\ .$ (134)

This condition, coupled with the demand for an appropriate initialization
strategy, is sufficient to demonstrate that wide neural networks are
exponentially weakly correlated PGDML-s.

In the remainder of this section, we will proceed under the assumption that
our parameters are initialized appropriately and that $\eta\sim\frac{1}{n}$.

We can now use this result to find the asymptotic behavior of the layers
derivatives:

######  Lemma E.2 (Asymptotic Behavior of Layer’s Derivatives).

Given our established conditions and initialisation, all derivatives are
uniformly bound for each natural number $D$ and layer $l=1...L$. Specifically,
we have:

$\frac{\eta^{\frac{D}{2}}}{\sqrt{N_{D}}}O\left(\nabla^{\times
D}F^{(l)}\right)\leq O\left(1\right)\quad\text{Uniformly}$ (135)

Here, $N_{D}=n_{l}n_{l-1}^{D}n^{D}$ represents the asymptotic behavior of the
number of elements in the derivatives.

###### Proof of lemma E.1.

We approach the proof by induction, across the entire proof we use lemma A.7
to show equivalence between the asymptotic behavior of the system and its
tensorial average (67). It is known that the base case, the zeroth layer,
naturally satisfies the lemma. By inductive assumption, let us presume that
the $l-1$ layer adheres to the lemma. Our task is to establish the lemma’s
validity for the $l$-th layer for all $l=1...L$:

$\begin{array}[]{c}\left[F^{(l)}\right]^{2}=_{1}\frac{1}{n_{l}}\sum_{i}\left\langle\left(\sum_{j}\theta_{ij}^{\left(l,l-1\right)}F_{j}^{\left(l-1\right)}\right)\left(\sum_{k}\theta_{ik}^{\left(l,l-1\right)}F_{k}^{\left(l-1\right)}\right)\right\rangle=\\\
\frac{1}{n_{l}}\sum_{i}\left\langle\left(\sum_{j,k}\theta_{ij}^{\left(l,l-1\right)}\theta_{ik}^{\left(l,l-1\right)}F_{j}^{\left(l-1\right)}F_{k}^{\left(l-1\right)}\right)\right\rangle=_{2}\\\
\frac{1}{n_{l}}\sum_{i}\sum_{j,k}\left\langle\theta_{ij}^{\left(l,l-1\right)}\theta_{ik}^{\left(l,l-1\right)}\right\rangle\left\langle
F_{j}^{\left(l-1\right)}F_{k}^{\left(l-1\right)}\right\rangle=\\\
\frac{1}{n_{l}}\sum_{i}\sum_{j\neq
k}\left\langle\theta_{ij}^{\left(l,l-1\right)}\theta_{ik}^{\left(l,l-1\right)}\right\rangle\left\langle
F_{j}^{\left(l-1\right)}F_{k}^{\left(l-1\right)}\right\rangle+\frac{1}{n_{l}}\sum_{i}\sum_{j}\left\langle\left(\theta_{ij}^{\left(l,l-1\right)}\right)^{2}\right\rangle\left\langle\left(F_{j}^{\left(l-1\right)}\right)^{2}\right\rangle=_{3}\\\
\sum_{i}\sum_{j}\frac{1}{n_{l}}\left\langle\left(\theta_{ij}^{\left(l,l-1\right)}\right)^{2}\right\rangle\left\langle\left(F_{j}^{\left(l-1\right)}\right)^{2}\right\rangle=_{4}\sum_{i,j}\frac{1}{n_{l}}\left\langle\left(\theta_{ij}^{\left(l,l-1\right)}\right)^{2}\right\rangle\sum_{k}\frac{1}{n_{l-1}}\left\langle\left(F_{k}^{\left(l-1\right)}\right)^{2}\right\rangle=_{5}\\\
n_{l-1}\left[\theta^{\left(l,l-1\right)}\right]^{2}\left[F^{(l-1)}\right]^{2}=_{6}O\left(1\right)O\left(1\right)=O\left(1\right)\
.\end{array}$ (136)

Throughout these equalities, we rely on the premise of a proper
initialization. Specifically:

  * •

In ”1” and ”5”, we employ the structure of neural networks and the definition
of the moment’s norm.

  * •

In ”2” and ”4”, we note that $F^{(l-1)}$ is dependent only on the inner
parameters of $l$, which are independent of $\theta^{(l,l-1)}$. This is
enabled by the proper initialization ensuring $\theta^{(l,l-1)}$ is uniformly
distributed.

  * •

In ”3”, we invoke the fact that different elements of $\theta^{(l,l-1)}$ are
independent and symmetric. Hence, for every $i,j\neq k$:

$\left\langle\theta_{ij}^{\left(l,l-1\right)}\theta_{ik}^{\left(l,l-1\right)}\right\rangle=\left\langle\theta_{ij}^{\left(l,l-1\right)}\right\rangle\left\langle\theta_{ik}^{\left(l,l-1\right)}\right\rangle=0\
.$ (137)

  * •

In ”6”, we apply the induction hypothesis and observe that for a proper
initialization (E.1-3):

$\forall
l=1...L:\left[\theta^{\left(l,l-1\right)}\right]=O\left(\frac{1}{\sqrt{n_{l-1}}}\right)\
.$ (138)

Through the application of the principle of mathematical induction, we
conclude the lemma holds for all $l=1...L$.

Using lemma A.7 again, we get that $O\left(F^{l}\right)\leq O\left(1\right)$,
but as we know that even if we neglect a small part of the probability
distribution the proof should still hold, we get that:

$O\left(F^{l}\right)=O\left(1\right)\ .$ (139)

exactly.

∎

###### Proof of lemma E.2.

Given $\omega$, drawn from another proper initialisation, we can observe that
$\theta+\omega$ is also properly initialised or sub-properly initialised.
Hence, assuming we initialise $F^{(l)}$ accordingly, we find:

$\frac{1}{\sqrt{n_{l}}}O\left(F^{(l)}\right)\leq O\left(1\right)\ .$ (140)

Since $F^{(l)}$ is analytical, we can apply its Taylor expansion around
$\theta$ to get:

$\frac{1}{\sqrt{n_{l}}}O\left(\sum_{D=0}^{\infty}\nabla^{\times
D}F^{(l)}\left(\theta\right)\omega^{\times D}\right)\leq O\left(1\right)\ .$
(141)

By continuously rescaling $\theta,\omega$ without violating the proper
property, we see that all of the component of the expression must be uniformly
bounded:

$\forall D\in\mathbb{N}:\frac{1}{\sqrt{n_{l}}}O\left(\nabla^{\times
D}F^{(l)}\left(\theta\right)\omega^{\times D}\right)\leq
O\left(1\right)\quad\text{Uniformly.}$ (142)

Considering the symmetry of the derivative in its components, and by invoking
lemma A.3, we can identify a vector of size $1$ that maximises it, yielding a
vector with a size equal to its norm. By setting $\omega$ as this vector and
rescaling it to be proper, we obtain using lemma A.7 that:

$\forall D\in\mathbb{N}:\frac{1}{\sqrt{n_{l}}}O\left(\nabla^{\times
D}F^{(l)}\left(\theta\right)\right)=\frac{1}{\sqrt{n_{l}}}\frac{1}{\sqrt{n_{l-1}^{D}}}O\left(\nabla^{\times
D}F^{(l)}\left(\theta\right)\omega^{\times D}\right)\leq
O\left(1\right)\quad\text{Uniformly.}$ (143)

Given that:

$\frac{1}{\sqrt{n_{l}}}\frac{1}{\sqrt{n_{l-1}^{D}}}=\frac{1}{\sqrt{n_{l}n_{l-1}^{D}}}\sim\frac{\eta^{\frac{D}{2}}}{\sqrt{n_{l}n_{l-1}^{D}n^{D}}}=\frac{\eta^{\frac{D}{2}}}{\sqrt{N_{D}}}\
,$ (144)

we arrive at the desired result. ∎

###  E.3 Representation of the Network’s Layers as a Composition of Previous
Layer Components

In this part we use the semilinear structure of wide neural network to
establish a linear relation between the correlations of the $l$-th layer to
the one of the $l-1$ layer. We will then use this relation next part to show
by induction the correlations are weak. For that will define the following
useful notation:

######  Definition E.2 (Inner and Outer Derivatives).

Given a layer $l=1...L$. We denote the $l$-th layer’s outer parameters, which
includes its weights (and biases), as follows:

$\theta_{i^{l},i^{l-1}}^{\left(l,l-1\right)}\ .$ (145)

Meanwhile, the inner parameters are defined as any of the weights (and biases)
from the layers spanning $1...l-1$, and are denoted by:

$\theta\in\theta^{(-l)}\ .$ (146)

Following the same notation, we denote the gradient of the outer parameters as
$\nabla_{(l)}$, and the gradient of the inner parameters as $\nabla_{(-l)}$.
The same applies for the correlations, denoted as
$\mathfrak{C}_{\left(l\right)},\mathfrak{C}_{\left(-l\right)}$.

######  Remark E.4.

It is important to note that, as $F^{(l-1)}$ depends only in the inner
parameters of the $l$-th layer, the following relationship holds:

$\nabla_{\left(-l\right)}F^{(l-1)}=\nabla F^{(l-1)}\ .$ (147)

This notation can be employed to express the derivative of the $l$-th layer as
a combination of derivatives from the $l-1$-th layer.

######  Lemma E.3 (Representation of the $l$-th layer derivative, as a
combination of its previous layer’s derivatives).

Given a fully connected wide neural network as specified above, for each
$l=1...L$ layer, the $D\in\mathbb{N}$-th derivative can be presented as
follows:

  1. 1.

When all the derivatives are inner, the expression is:

$\left(\nabla^{\left(-l\right)}\right)^{\times
D}F^{(l)}=\theta^{\left(l,l-1\right)}\tilde{\nabla}^{\times D}F^{(l-1)}\ .$
(148)

  2. 2.

When one derivative is outer, and the rest are inner, the expression becomes:

$\nabla_{i_{l}i_{l-1}}^{\left(l\right)}\times\left(\nabla^{\left(-l\right)}\right)^{\times
D-1}F_{i}^{\left(l\right)}=\delta_{ii_{l}}\tilde{\nabla}^{\times
D-1}F_{i_{l-1}}^{\left(l-1\right)}\ .$ (149)

  3. 3.

When $2\leq D$, and for $2\leq d\in\mathbb{N}\leq D$ where the derivatives are
outer, the expression simplifies to:

$\left(\nabla^{\left(l\right)}\right)^{\times
d}\times\left(\nabla^{\left(-l\right)}\right)^{\times D-d}F^{(l)}=0\ .$ (150)

Here, $\tilde{\nabla}^{\times D}F^{(l-1)}$ is the compound derivative, defined
such as for $D\in\mathbb{N}$:

$\tilde{\nabla}^{\times D}F^{(l)}=\sum_{d=1}^{D}\sum_{d_{1}\ldots
d_{d}\in\mathbb{N}}^{d_{1}+\ldots+d_{d}=D}\phi^{\left[d\right]}\left(F^{(l)}\right)\left(\nabla^{\times
d_{1}}F^{(l)}\times\cdots\times\nabla^{\times
d_{d}}F^{(l)}\right)+\text{comb}$ (151)

and for $D=0$:

$\tilde{\nabla}_{ij}^{\times
0}F_{k}^{\left(l\right)}=\delta_{ik}\phi\left(F_{j}\right)\ .$ (152)

The ”comb” term refers to all possible combinations of the derivatives’
indices. For instance, if we consider one term of the third derivative as
follows:

$\theta^{\left(l,l-1\right)}\left(\phi^{\left[2\right]}\left(F^{(l-1)}\right)\left(\nabla
F^{(l-1)}\times\nabla^{\times 2}F^{(l-1)}\right)\right)$ (153)

then, for every three distinct derivative indices
$\alpha_{1},\alpha_{2},\alpha_{3}$, there are three unique ways to arrange the
indices, disregarding irrelevant parts:

$\nabla_{\alpha_{1}}F^{(l-1)}\times\nabla_{\alpha_{2}\alpha_{3}}^{\times
2}F^{(l-1)},\nabla_{\alpha_{2}}F^{(l-1)}\times\nabla_{\alpha_{1}\alpha_{3}}^{\times
2}F^{(l-1)},\nabla_{\alpha_{3}}F^{(l-1)}\times\nabla_{\alpha_{1}\alpha_{2}}^{\times
2}F^{(l-1)}\ .$ (154)

While the first combination naturally arises from our expression, the ”comb”
term accounts for the other two.

It should be mentioned that only unique terms are counted, even if they
originate from different orders of the derivatives. Therefore, for another
component of the third derivative,
$\theta^{\left(l,l-1\right)}\left(\phi^{\left[3\right]}\left(F^{(l-1)}\right)\nabla
F^{(l-1)}\times\nabla F^{(l-1)}\times\nabla F^{(l-1)}\right)$, and distinct
$\alpha_{1},\alpha_{2},\alpha_{3}$:

$\nabla_{\alpha_{1}}F^{(l-1)}\nabla_{\alpha_{2}}F^{(l-1)}\nabla_{\alpha_{3}}F^{(l-1)},\nabla_{\alpha_{1}}F^{(l-1)}\nabla_{\alpha_{3}}F^{(l-1)}\nabla_{\alpha_{2}}F^{(l-1)}\ldots$
(155)

are identical, hence should only be counted once.

We can use this result to construct the $l$-th layer correlations using the
correlations from the $l-1$ layer:

######  Lemma E.4 (Representation of the $l$-th layer correlations, as a
combination of its previous layer’s correlations).

Given the same condition as in lemma E.3, then:

$\begin{array}[]{c}\mathfrak{C}_{\left(l\right)}^{D,d}=\theta^{\left(l,l-1\right)}\times\left(\tilde{\theta}^{\left(l,l-1\right)}\right)^{\times
d}\tilde{\mathfrak{C}}_{\left(l-1\right)}^{D,d}+\\\
\eta^{\frac{1}{2}}I\times\eta^{\frac{1}{2}}\phi\left(F^{(l-1)}\right)\times\left(\tilde{\theta}^{\left(l,l-1\right)}\right)^{\times
d-1}\tilde{\mathfrak{C}}_{\left(l-1\right)}^{D,d-1}+\text{comb}+\begin{array}[]{c}\\\
\\\ \end{array}\\\ \left(\tilde{\theta}^{\left(l,l-1\right)}\right)^{\times
d}\hat{\mathfrak{C}}_{\left(l-1\right)}^{D-1,d}+\text{comb}\ .\end{array}$
(156)

or when showing the indices explicitly, using Einstein’s notation for
summation:

$\begin{array}[]{c}\left(\mathfrak{C}_{\left(l\right)}^{D,d}\right)_{i_{0}i_{1}\ldots
i_{d}}=\theta_{i_{0}j_{0}}^{\left(l,l-1\right)}\tilde{\theta}_{i_{1}j_{1}}^{\left(l,l-1\right)}\cdots\tilde{\theta}_{i_{d}j_{d}}^{\left(l,l-1\right)}\left(\tilde{\mathfrak{C}}_{\left(l-1\right)}^{D,d}\right)_{j_{0},j_{1}\ldots
j_{d}}+\\\
\eta^{\frac{1}{2}}\delta_{i_{0}i_{1}}\eta^{\frac{1}{2}}\phi\left(F_{j_{0}}^{\left(l-1\right)}\right)\tilde{\theta}_{i_{2}j_{2}}^{\left(l,l-1\right)}\cdots\tilde{\theta}_{i_{d}j_{d}}^{\left(l,l-1\right)}\left(\tilde{\mathfrak{C}}_{\left(l-1\right)}^{D,d-1}\right)_{j_{0},j_{2}\ldots
j_{d}}+\text{comb}+\begin{array}[]{c}\\\ \\\ \end{array}\\\
\tilde{\theta}_{i_{1}j_{1}}^{\left(l,l-1\right)}\cdots\tilde{\theta}_{i_{d}j_{d}}^{\left(l,l-1\right)}\left(\hat{\mathfrak{C}}_{\left(l-1\right)}^{D-1,d}\right)_{i_{0},j_{1}\ldots
j_{d}}\ ,\end{array}$ (157)

where the ”comb” term includes all index pairings with the zero index, i.e.,
$\left(i_{0},i_{2}\right)\ldots\left(i_{0},i_{D}\right)$, and the $\theta$
defined as:

$\tilde{\theta}_{ij}^{\left(l,l-1\right)}=\theta_{ij}^{\left(l,l-1\right)}\phi^{\prime}\left(F_{j}^{\left(l-1\right)}\right)\
.$ (158)

The first compound derivative defined such as for
$D\in\mathbb{N}_{0},d\in\mathbb{N}$:

$\tilde{\mathfrak{C}}_{\left(l\right)}^{D,d}=\sum_{d^{\prime}=1}^{D+d}\left\\{C_{\vec{d},\vec{D}}\phi^{\left[d^{\prime}\right]}\left(F^{(l)}\right)\mathfrak{C}_{\left(l\right)}^{D_{1},d_{1}}\times\cdots\times\mathfrak{C}_{\left(l\right)}^{D_{d^{\prime}},d_{d^{\prime}}}\left|\begin{array}[]{c}d_{1}+\ldots+d_{d^{\prime}}=d\\\
D_{1}+\ldots+D_{d^{\prime}}=D\end{array}\right.\right\\}+\text{Comb}$ (159)

where:

$C_{\vec{d},\vec{D}}=\frac{\left(D_{1}!\cdots
D_{d^{\prime}}!\right)\left(d_{1}!\cdots d_{d^{\prime}}!\right)}{D!d!}\ .$
(160)

Also for $D\in\mathbb{N}_{0},d=0$:

$\tilde{\mathfrak{C}}_{\left(l\right)}^{D,0}=\eta^{\frac{D}{2}}\tilde{\nabla}_{t}^{\times
D}F^{(l)}\ .$ (161)

The second compound derivative defined such as for
$D\in\mathbb{N},d\in\mathbb{N}$:

$\left(\mathfrak{\hat{C}}_{\left(l\right)}^{D-1,d}\right)_{i_{0},j_{1}\ldots
j_{d}}^{\alpha_{d+1}\ldots\alpha_{d+D}}=\eta^{\frac{1}{2}}\delta_{\left(i_{0}j_{0}\right)}^{\alpha_{d+1}}\left(\tilde{\mathfrak{C}}_{\left(l\right)}^{D-1,d}\right)_{j_{0},j_{1}\ldots
j_{d}}^{\alpha_{d+2}\ldots\alpha_{d+D}}+\text{comb}\ ,$ (162)

where the ”comb” term is defined as before. For $D=0$ this compound derivative
vanishes.

######  Remark E.5.

For the following lemma and the subsequent section, we make the assumption
that $D<<n$. This assumption is permissible even though, in considering the
limit, the limit of $D$ should technically be taken prior to that over $n$.
This is because higher order derivatives typically exert a decreasing
influence over system behavior, leading us to essentially consider them
negligible beyond a certain point.

It is important to note that this assumption is not strictly necessary. We
could directly address the intricate combinatorial factors without it. Despite
this, we prefer to make this assumption to avoid introducing unnecessary
complications into our analysis.

######  Lemma E.5 (Counting combinations of the derivatives and correlations).

  1. 1.

For the conditions of lemma E.3, for every $d_{1}...d_{d}$, the number of
combinations of the derivatives indices is:

$\frac{1}{d!}\frac{D!}{d_{1}!\cdots d_{d}!}\ ,$ (163)

and the total number of combinations above all possible $d=1...D$-s is the
$D$-th ”bell number” (which is very close to $D!$).

  2. 2.

For the conditions of lemma E.4, for every $d_{1}...d_{d^{\prime}}$ and
$D_{1}...D_{d^{\prime}}$, the number of combinations of the compound
correlations is:

$\frac{1}{d^{\prime}!}\frac{d!}{d_{1}!\cdots
d_{d^{\prime}}!}\frac{D!}{D_{1}!\cdots D_{d^{\prime}}!}\ .$ (164)

We assume for this lemma the indices are different, as $D\ll n$.

###### Proof - lemmas E.3,E.4.

We will prove the lemma by induction for a general layer $l=1...L-1$ starting
with $l=1$.

The induction base is simple, a this is a direct consequence of taking a
derivative over our equation for neural networks (127). This calculation
hinges on the concept that, by definition, the inner derivatives are
independent of the outer parameters.

$\begin{array}[]{c}\nabla_{\left(l\right)}F^{(l)}=\nabla_{\left(l\right)}\theta^{\left(l,l-1\right)}\phi\left(F^{(l-1)}\right)=\theta^{\left(l,l-1\right)}\nabla_{\left(l\right)}\phi\left(F^{(l-1)}\right)=\\\
\theta^{\left(l,l-1\right)}\left(\phi^{\left[1\right]}\left(F^{(l-1)}\right)\nabla_{\left(l\right)}F^{(l-1)}\right)\
,\end{array}$ (165)

which gives us the induction base.

Assuming by induction our lemma is satisfied for some $D-1\in\mathbb{N}$: the
inner $D$-th derivative satisfies:

$\begin{array}[]{c}\nabla_{\left(-l\right)}^{\times
D}F^{(l)}=\nabla_{\left(-l\right)}\times\nabla_{\left(-l\right)}^{\times
D-1}F^{(l)}=\\\
\nabla_{\left(-l\right)}\times\theta^{\left(l,l-1\right)}\sum_{d=1}^{D-1}\sum_{d_{1}\ldots
d_{d}\in\mathbb{N}}^{d_{1}+\ldots+d_{d}=D-1}\phi^{\left[d\right]}\left(F^{(l-1)}\right)\left(\nabla^{\times
d_{1}}F^{(l-1)}\times\cdots\times\nabla^{\times d_{d}}F^{(l-1)}\right)\\\
+\text{comb}\\\ =\\\
\theta^{\left(l,l-1\right)}\sum_{d=1}^{D-1}\sum_{d_{1}\ldots