# Memorization and Optimization in Deep Neural Networks with Minimum Over-
parameterization

Simone Bombari , Mohammad Hossein Amani , Marco Mondelli11footnotemark: 1
Institute of Science and Technology Austria (ISTA). Emails: {simone.bombari,
<EMAIL_ADDRESS>Switzerland. Email<EMAIL_ADDRESS>
###### Abstract

The Neural Tangent Kernel (NTK) has emerged as a powerful tool to provide
memorization, optimization and generalization guarantees in deep neural
networks. A line of work has studied the NTK spectrum for two-layer and deep
networks with at least a layer with $\Omega(N)$ neurons, $N$ being the number
of training samples. Furthermore, there is increasing evidence suggesting that
deep networks with sub-linear layer widths are powerful memorizers and
optimizers, as long as the number of parameters exceeds the number of samples.
Thus, a natural open question is whether the NTK is well conditioned in such a
challenging sub-linear setup. In this paper, we answer this question in the
affirmative. Our key technical contribution is a lower bound on the smallest
NTK eigenvalue for deep networks with the _minimum possible over-
parameterization_ : the number of parameters is roughly $\Omega(N)$ and,
hence, the number of neurons is as little as $\Omega(\sqrt{N})$. To showcase
the applicability of our NTK bounds, we provide two results concerning
memorization capacity and optimization guarantees for gradient descent
training.

##  1 Introduction

Training a neural network is a non-convex problem that exhibits disconnected
local minima [8, 55, 68]. Yet, in practice gradient descent (GD) and its
variants routinely find solutions with zero training loss [70]. A framework to
understand this phenomenon comes from the Neural Tangent Kernel (NTK). This
quantity was introduced in [32], where it was proved that, during GD training,
the network follows the kernel gradient of the functional cost with respect to
the NTK. Furthermore, as the layer widths go large, the NTK converges to a
deterministic limit which stays constant during training. Hence, in this
infinite-width limit, it suffices that the smallest eigenvalue of the NTK is
bounded away from $0$ for gradient descent to reach zero loss. Going to finite
widths, a recipe to prove GD convergence can be summarized as follows: show
that _(i)_ the NTK is well conditioned at initialization, and _(ii)_ the NTK
has not changed significantly by the time GD has reached zero loss (see e.g.
[47, 16, 11]). A number of papers have exploited this recipe for networks with
progressively smaller over-parameterization: two-layer networks [21, 48, 61,
67, 60], deep networks with polynomially wide layers [5, 20, 71, 72], and deep
networks with a single wide layer [45, 41]. Besides optimization, showing that
the NTK is well conditioned directly implies a result on memorization capacity
[40, 46], and the smallest eigenvalue of the NTK has also been related to
generalization [6].

In [46], it is shown that, given $N$ training samples, a single layer with
$\Omega(N)$ neurons suffices for the NTK to be well conditioned in networks of
arbitrary depth. However, there is increasing evidence that, in the
challenging setup in which the layer widths are _sub-linear_ in $N$, neural
networks still memorize the training data [14, 69, 64], reach zero loss under
GD training in the two-layer setting [59, 48, 40], and in the deep case, GD
explores a nicely behaved region of the loss landscape [42]. We also note
that, by counting degrees of freedom or bounding the VC dimension [10],
$\Omega(N)$ parameters (and, therefore, $\Omega(\sqrt{N})$ neurons) are in
general necessary to fit $N$ data points. This naturally brings forward the
following open question:

Is the NTK well conditioned for deep networks with the minimum possible over-
parameterization (i.e., containing $\Omega(N)$ parameters corresponding to
$\Omega(\sqrt{N})$ neurons)?

#### Main contributions.

In this paper, _we settle this open question_ for a large class of deep
networks. We consider _(i)_ a smooth activation function, _(ii)_ i.i.d. data
satisfying Lipschitz concentration (e.g., data with a Gaussian distribution,
uniform on the sphere/hypercube, or obtained via a Generative Adversarial
Network), _(iii)_ a standard initialization of the weights (e.g., He’s or
LeCun’s initialization), and _(iv)_ a loose pyramidal topology in which the
layer widths can increase by at most a multiplicative constant as the network
gets deep. Then, in Theorem 1 we show that the NTK is well conditioned under
the _minimum possible over-parameterization_ requirement: the number of
parameters between the last two layers has to be roughly $\Omega(N)$ or,
equivalently, the number of neurons has to be $\Omega(\sqrt{N})$. We achieve
this goal by giving a lower bound on the smallest eigenvalue of the NTK. This
lower bound is tight when all the layer widths are of the same order.

Our NTK bounds open the way towards understanding the behavior of deep
networks with minimum over-parameterization. In particular, an immediate
consequence of the fact that the NTK is well conditioned is a result on the
memorization capacity (Corollary 4.1). Furthermore, by suitably choosing the
initialization, we provide convergence guarantees for gradient descent
training (Theorem 4). Finally, we highlight that, in order to obtain our
bounds on the smallest NTK eigenvalue, we give a number of tight estimates on
the $\ell_{2}$ norms of feature vectors and of their centered counterparts,
which may be of independent interest.

#### Proof ideas.

To prove Theorem 1, we restrict to the kernel $K_{L-2}=J_{L-2}J_{L-2}^{\top}$,
where $J_{L-2}$ is the Jacobian of the output w.r.t. the parameters between
the last two hidden layers (this suffices as $K_{L-2}$ is a lower bound on the
NTK in the PSD sense). We note that the $i$-th row ($i\in\\{1,\ldots,N\\}$) of
$J_{L-2}$ is given by the Kronecker product $\otimes$ between the feature
vector at layer $L-2$ and the backpropagation term from the same layer. One
key technical hurdle is to center $J_{L-2}$, so that its rows have the form
$u\otimes v-\mathbb{E}\left[u\otimes v\right]$, where
$\mathbb{E}[u]=\mathbb{E}[v]=0$, and all expectations are taken with respect
to the (random) training data. To do so, we perform three steps of centering:
_(i)_ we center the feature vectors (corresponding to $u$), _(ii)_ we center
the backpropagation terms (corresponding to $v$), and _(iii)_ we center again
the whole row (corresponding to $u\otimes v$). These centering steps are
approximate in the sense that the centered matrix is _not necessarily_ a lower
bound (in the PSD sense) on the original one. However, we are able to control
the operator norm of the difference, and show that it scales slower than the
smallest eigenvalue of the centered kernel. At this point, we leverage the
structure of the rows of the centered Jacobian to bound their sub-exponential
norm via a version of the Hanson-Wright inequality for (weakly) correlated
random vectors [1]. Finally, after providing also a tight estimate on the
$\ell_{2}$ norms of such rows, we can exploit a result from [2] to lower bound
the smallest singular value of a matrix whose rows are independent random
vectors with well controlled sub-exponential and $\ell_{2}$ norms.

Existing work bounds the smallest NTK eigenvalue for networks with two layers
[59, 40], or deep networks with a layer containing $\Omega(N)$ _neurons_ [46].
In particular, [59] also exploits the results [1, 2]. However, the centering
of the Jacobian is achieved via a combination of whitening and dropping rows,
which appears to be difficult to generalize to deep networks. In contrast, the
3-step centering we described above applies to networks of arbitrary depth
$L$. A different approach is put forward in [40], and it is based on a
decomposition of the kernel via spherical harmonics. This technique allows to
obtain the exact limit of the smallest NTK eigenvalue, it has been used to
analyze random feature models [25, 39, 24, 38] and to obtain generalization
bounds for two-layer networks (see again [40]). However, understanding how to
carry out such a decomposition in the multi-layer setup is an open problem.
Finally, [46] considers the deep case, and it relates the smallest eigenvalue
of the NTK to the smallest singular value of a feature matrix. As feature
matrices are full rank only when the number of neurons is $\Omega(N)$, this
approach is inherently limited to networks with a linear-width layer.

The rest of the paper is organized as follows: Section 2 discusses the problem
setup and our model assumptions; Section 3 presents our main result on the
smallest NTK eigenvalue and gives a roadmap of the argument; Section 4
provides two applications of our NTK bounds: memorization capacity and
gradient descent training; Section 5 discusses additional related work, and
Section 6 provides some concluding remarks. The details of the proofs are
deferred to the appendices.

##  2 Preliminaries

#### Neural network setup.

We consider an $L$-layer neural network with feature maps
$f_{l}:\mathbb{R}^{d}\to\mathbb{R}^{n_{l}}$ defined for every
$x\in\mathbb{R}^{d}$ as

$\displaystyle f_{l}(x)=\begin{cases}x,&l=0,\\\
\phi(W_{l}^{\top}f_{l-1}),&l\in[L-1],\\\ W_{L}^{\top}f_{L-1},&l=L.\end{cases}$
(2.1)

Here, $W_{l}\in\mathbb{R}^{n_{l-1}\times n_{l}}$ is the weight matrix at layer
$l$, $\phi$ is the activation function and, given an integer $n$, we use the
shorthand $[n]=\\{1,\ldots,n\\}$. We assume that the network has a single
output, i.e. $n_{L}=1$ and $W_{L}\in\mathbb{R}^{n_{L-1}}$, and for consistency
we have $n_{0}=d$. Let $g_{l}:\mathbb{R}^{d}\to\mathbb{R}^{n_{l}}$ be the pre-
activation feature map so that $f_{l}(x)=\phi(g_{l}(x))$ for $l\in[L]$. We
define $g_{0}(x)=f_{0}(x)=x$. Let
$X=[x_{1},\ldots,x_{N}]^{\top}\in\mathbb{R}^{N\times d}$ be the data matrix
containing $N$ samples in $\mathbb{R}^{d}$,
$\theta=[\operatorname{\mathop{vec}}(W_{1}),\ldots,\operatorname{\mathop{vec}}(W_{L})]$
be the vector of the parameters of the network, and
$F_{L}(\theta)=[f_{L}(x_{1}),\ldots,f_{L}(x_{N})]^{\top}$ be the network
output. We denote by $J$ the Jacobian of $F_{L}$ with respect to all the
parameters of the network:

$J=\left[\frac{\partial
F_{L}}{\partial\operatorname{\mathop{vec}}(W_{1})},\ldots,\frac{\partial
F_{L}}{\partial\operatorname{\mathop{vec}}(W_{L})}\right]\in\mathbb{R}^{N\times\sum_{l=1}^{L}n_{l-1}n_{l}}.$
(2.2)

Our key object of interest is the _empirical Neural Tangent Kernel (NTK) Gram
matrix_ , denoted by $K\in\mathbb{R}^{N\times N}$ and defined as:

$K=JJ^{T}=\sum_{l=1}^{L}\left[\frac{\partial
F_{L}}{\partial\operatorname{\mathop{vec}}(W_{l})}\right]\left[\frac{\partial
F_{L}}{\partial\operatorname{\mathop{vec}}(W_{l})}\right]^{\top}.$ (2.3)

In [32], it is shown that, as $n_{l}\to\infty$ for all $l\in[L-1]$, $K$
converges to a deterministic _limit_ , which stays constant during gradient
descent training. The focus of this paper is on the _finite-width_ behavior of
the empirical NTK (2.3). Quantitative bounds for the NTK convergence rate can
be obtained from [7, 15]. However, these bounds lead to a significant over-
parameterization requirement, see the discussion at the end of Section 3 in
[46]. Here, our main result consists in showing that the NTK is well
conditioned for a class of neural networks with the _minimum possible over-
parameterization_ , i.e., $\Omega(N)$ parameter or, equivalently,
$\Omega(\sqrt{N})$ neurons.

#### Weight and data distribution.

We consider the following initialization of the weight matrices:
$(W_{l})_{i,j}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta_{l}^{2}/n_{l-1})$ for
$l\in[L-1],i\in[n_{l-1}],j\in[n_{l}]$, where $\beta_{l}$ is a numerical
constant independent of the layer widths. This covers the popular cases of
He’s and LeCun’s initialization [26, 29, 34]. For the last layer, we assume
that $(W_{L})_{i}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta_{L}^{2})$ for $i\in[n_{L-1}]$. Throughout the
paper, we let $(x_{1},\ldots,x_{N})$ be $N$ i.i.d. samples from the data
distribution $P_{X}$, which satisfies the conditions below.

######  Assumption 1 (Data scaling).

The data distribution $P_{X}$ satisfies the following properties:

  1. 1.

$\int\left\|x\right\|_{2}dP_{X}(x)=\Theta(\sqrt{d}).$

  2. 2.

$\int\left\|x\right\|_{2}^{2}dP_{X}(x)=\Theta(d).$

  3. 3.

$\int\left\|x-\int
x^{\prime}\,dP_{X}(x^{\prime})\right\|_{2}^{2}dP_{X}(x)=\Omega\left(d\right).$

######  Assumption 2 (Lipschitz concentration).

The data distribution $P_{X}$ satisfies the _Lipschitz concentration
property_. Namely, there exists an absolute constant $c>0$ such that, for
every Lipschitz continuous function $\varphi:\mathbb{R}^{d}\to\mathbb{R}$, we
have $\mathbb{E}|\varphi(X)|<+\infty$, and for all $t>0$,

$\mathbb{P}\left(\left|\varphi(x)-\int\varphi(x^{\prime})\,dP_{X}(x^{\prime})\right|>t\right)\leq
2e^{-ct^{2}/\left\|\varphi\right\|_{\mathrm{Lip}}^{2}}.$

Assumption 1 is simply a scaling of the training data points and their
centered counterparts. Assumption 2 covers a number of important cases, e.g.,
standard Gaussian distribution [63], uniform distributions on the sphere and
on the unit (binary or continuous) hypercube [63], data produced via a
Generative Adversarial Network (GAN)111By applying a Lipschitz map to a
standard Gaussian distribution, the map output satisfies Assumption 2. [57],
and more generally any distribution satisfying the log-Sobolev inequality with
a dimension-independent constant. We also remark that Assumption 2 is rather
common in the related literature [46], or it is even replaced by a stronger
requirement (e.g., Gaussian distribution or uniform on the sphere) [40].

######  Assumption 3 (Activation function).

The activation function $\phi$ satisfies the following properties:

  1. 1.

$\phi$ is a non-linear (and therefore also non-constant) $M$-Lipschitz
function;

  2. 2.

its derivative $\phi^{\prime}$ is a $M^{\prime}$-Lipschitz function;

These requirements are satisfied by commonly used activations, such as
smoothed ReLU, sigmoid, or hyperbolic tangent.

######  Assumption 4 (Network topology).

The network satisfies a loose pyramidal topology condition, i.e.
$n_{l}=\mathcal{O}\left(n_{l-1}\right)$, for all $l\in[L-1]$.

A _strict_ pyramidal topology (namely, non-increasing layer widths) has been
considered in prior work concerning the loss landscape [43, 44] and gradient
descent training [45]. Our Assumption 4 requires a _loose_ pyramidal topology
in the sense that, as we go deep, the layer widths are allowed to increase by
a constant multiplicative factor. We also note that the widths of neural
networks used in practice are often large in the first layers and then start
decreasing [27, 58].

######  Assumption 5 (Over-parameterization).

There exists $\alpha>0$ such that

$N^{1+\alpha}=o(n_{L-2}n_{L-1}).$ (2.4)

Furthermore, there exists $\gamma>0$ such that

$N^{\gamma}=\mathcal{O}\left(n_{L-1}\right).$ (2.5)

In words, condition (2.4) requires that the number of parameters between the
last two hidden layers is (slightly larger than) linear in the number of
samples. This represents our _key over-parameterization condition_. The second
requirement (2.5) is rather mild, as $\gamma$ can be taken to be arbitrarily
small, and it avoids an exponential bottleneck in the last hidden layer.

#### Notation.

The feature matrix at layer $l$ is
$F_{l}=[f_{l}(x_{1}),\ldots,f_{l}(x_{N})]^{\top}\in\mathbb{R}^{N\times
n_{l}}$, and
$\Sigma_{l}(x)=\operatorname{\mathop{diag}}([\phi^{\prime}(g_{l,j}(x))]_{j=1}^{n_{l}})$
for $l\in[L-1]$, where $g_{l,j}(x)$ is the pre-activation neuron. Given two
matrices $F,B\in\mathbb{R}^{m\times n}$, we denote by $F\circ B$ their
Hadamard product, and by $F\ast B=[(F_{1:}\otimes
B_{1:}),\ldots,(F_{m:}\otimes B_{m:})]^{T}\in\mathbb{R}^{m\times n^{2}}$ their
row-wise Kronecker product (also known as Khatri-Rao product). Given a random
vector $v$, let $\left\|v\right\|_{\psi_{2}}$ and
$\left\|v\right\|_{\psi_{1}}$ denote its sub-Gaussian and sub-exponential
norm, respectively (see also Appendix A for a detailed definition). Given a
matrix $A$, let $\left\|A\right\|_{\mathrm{op}}$ be its operator norm,
$\left\|A\right\|_{F}$ its Frobenius norm, $\lambda_{\rm min}\left(A\right)$
its smallest eigenvalue, and $\sigma_{\rm min}\left(A\right)$ its smallest
singular value. We denote by $\left\|\varphi\right\|_{\mathrm{Lip}}$ the
Lipschitz constant of the function $\varphi$. All the complexity notations
$\Omega(\cdot)$, $\mathcal{O}(\cdot)$, $o(\cdot)$ and $\Theta(\cdot)$ are
understood for sufficiently large $N,d,n_{1},n_{2},\ldots,n_{L-1}$.

##  3 NTK Bounds with Minimum Over-parameterization

Our main technical contribution on the smallest eigenvalue of the empirical
NTK (2.3) is stated below.

######  Theorem 1 (Smallest NTK eigenvalue under minimum over-
parameterization).

Consider an $L$-layer neural network (2.1), where the activation function
satisfies Assumption 3 and the layer widths satisfy Assumptions 4 and 5. Let
$\left\\{x_{i}\right\\}_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$, where $P_{X}$
satisfies the Assumptions 1-2, and let $K$ be the empirical NTK Gram matrix
(2.3). Assume that the weights of the network are initialized as
$(W_{l})_{i,j}\sim_{\rm i.i.d.}\mathcal{N}(0,\beta_{l}^{2}/n_{l-1})$ for
$l\in[L-1]$, $i\in[n_{l-1}]$, $j\in[n_{l}]$ and $(W_{L})_{i}\sim_{\rm
i.i.d.}\mathcal{N}(0,\beta_{L}^{2})$ for $i\in[n_{L-1}]$. Then, we have

$\lambda_{\rm min}\left(K\right)=\Omega(n_{L-2}n_{L-1}),$ (3.1)

with probability at least $1-C\,Ne^{-c\log^{2}n_{L-1}}-Ce^{-c\log^{2}N}$ over
$(x_{i})_{i=1}^{N}$ and $(W_{k})_{k=1}^{L}$, where $c$ and $C$ are numerical
constants. Moreover, we have that

$\lambda_{\rm min}\left(K\right)=\mathcal{O}\left(dn_{L-1}\right),$ (3.2)

with probability at least $1-Ce^{-cn_{L-1}}$, over $(x_{i})_{i=1}^{N}$ and
$(W_{k})_{k=1}^{L}$.

Figure 1: $\lambda_{\rm min}\left(K\right)$ as a function of $d^{2}$ in a
3-layer neural network, with sigmoid activation and $d=n_{1}=n_{2}$.

This result implies that the NTK is well conditioned for a class of networks
in which the number of parameters $n_{L-2}n_{L-1}$ between the last two hidden
layers is roughly linear in the number of data samples $N$. This means that
the total number of neurons of the network can be as little as
$\Omega(\sqrt{N})$, which meets the _minimum possible amount of over-
parameterization_. The lower bound (3.1) and the upper bound (3.2) match when
all the widths (up to layer $L-2$) have the same scaling, i.e.,
$d=\Theta(n_{L-2})$. Throughout the paper, we do not explicitly track the
dependence of our bounds on $L$, in the sense that the numerical constants
$c,C$ may depend on $L$.

In Figure 1, we consider a 3-layer neural network with $d=n_{1}=n_{2}$, and we
plot $\lambda_{\rm min}\left(K\right)$ as a function of $d^{2}$, for three
different values of $N$. The inputs are sampled from a standard Gaussian
distribution, the activation function is the sigmoid
$\sigma(x)=(1+e^{-x})^{-1}$, and we set $\beta_{l}=1$ for all $l\in[L]$. We
repeat the experiment 10 times, and report average and confidence interval at
1 standard deviation. The linear scaling of $\lambda_{\rm min}\left(K\right)$
in $d^{2}$ is in agreement with the result of Theorem 1.

###  3.1 Roadmap of the proof of Theorem 1

After an application of the chain rule and some standard manipulations, we
have

$JJ^{\top}=\sum_{k=0}^{L-1}K_{k},\qquad\mbox{ with
}K_{k}=F_{k}F_{k}^{\top}\circ B_{k+1}B_{k+1}^{\top}\in\mathbb{R}^{N\times N},$
(3.3)

where $B_{k}\in\mathbb{R}^{N\times n_{k}}$ is a matrix whose $i$-th row is
given by

$(B_{k})_{i:}=\begin{cases}\Sigma_{k}(x_{i})\left(\prod_{l=k+1}^{L-1}W_{l}\Sigma_{l}(x_{i})\right)W_{L},&k\in[L-2],\\\
\Sigma_{L-1}(x_{i})W_{L},&k=L-1,\\\ 1,&k=L.\end{cases}$ (3.4)

From the decomposition (3.3), one readily obtains that $K\succeq K_{L-2}$,
since $K_{k}$ is PSD for all $k\in\\{0,\ldots,L-1\\}$. Hence, it suffices to
prove a lower bound on $\lambda_{\rm min}\left(K_{L-2}\right)$. We denote by
$J_{L-2}$ the Jacobian obtained by computing the gradient only over the
parameters between layer $L-2$ and layer $L-1$. Then,
$K_{L-2}=J_{L-2}J_{L-2}^{\top}$ and, by using (3.3) and (3.4), the $i$-th row
of $J_{L-2}$ can be expressed as

$(J_{L-2})_{i:}=f_{L-2}(x_{i})\otimes(D_{L}\phi^{\prime}(W^{\top}_{L-1}f_{L-2}(x_{i}))),\qquad
i\in[N],$ (3.5)

where $D_{L}$ is a diagonal matrix with the entries of $W_{L}$ on its
diagonal. Note that, if we fix the weight matrices $(W_{l})_{l=1}^{L}$, the
rows $((J_{L-2})_{i:})_{i=1}^{N}$ are i.i.d., as the training data
$(x_{i})_{i=1}^{N}$ are i.i.d. too.

The proof consists of two main parts. First, we construct the centered
Jacobian $\tilde{J}_{L-2}$, which is obtained from $J_{L-2}$ by iteratively
removing expectations with respect to $X$ to its parts, and we show that its
smallest singular value is _close_ to the smallest singular value of
$J_{L-2}$. The details of this part are contained in Appendix D. Second, we
bound the smallest eigenvalue of the kernel obtained from the centered
Jacobian $\tilde{J}_{L-2}$ by providing an accurate estimate of the $\ell_{2}$
and sub-exponential norms of its rows. The details of this part are contained
in Appendix E. In order to carry out this program, we exploit a number of
concentration results on the $\ell_{2}$ norms of feature and backpropagation
vectors, and on the $\ell_{2}$ norms of their centered counterparts. These
results are contained in Appendix C, and they could be of independent
interest. In particular, we provide tight high-probability estimates on _(i)_
$\left\|f_{l}(x)\right\|_{2}$, _(ii)_
$\mathbb{E}_{x}[\left\|f_{l}(x)\right\|_{2}^{2}]$, _(iii)_
$\mathbb{E}_{x}[\left\|f_{l}(x)\right\|_{2}]$, _(iv)_
$\mathbb{E}_{x}[\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}^{2}]$,
$\mathbb{E}_{x}[\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}]$, and
$\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}$, and _(v)_
$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}[D_{L}\phi^{\prime}(g_{L-1}(x))]\right\|_{2}$.
Some preliminary calculations are also contained in Appendix B.

#### Part 1: Centering.

We consider the centered Jacobian $\tilde{J}_{L-2}$, whose $i$-th row is
defined as

$(\tilde{J}_{L-2})_{i:}=\tilde{f}_{L-2}(x_{i})\otimes(D_{L}\tilde{\phi^{\prime}}(g_{L-1}(x_{i})))-\mathbb{E}_{x_{i}}\left[\tilde{f}_{L-2}(x_{i})\otimes
D_{L}\tilde{\phi^{\prime}}(g_{L-1}(x_{i}))\right],\quad i\in[N],$ (3.6)

where $\tilde{f}_{L-2}(x_{i})=\tilde{\phi}(g_{L-2}(x_{i}))$, with
$\tilde{\phi}(g_{L-2}(x_{i}))=\phi(g_{L-2}(x_{i}))-\mathbb{E}_{x_{i}}[\phi(g_{L-2}(x_{i}))]$
and
$\tilde{\phi}^{\prime}(g_{L-1}(x_{i}))=\phi^{\prime}(g_{L-1}(x_{i}))-\mathbb{E}_{x_{i}}[\phi^{\prime}(g_{L-1}(x_{i}))]$
being the centered versions of the activation function and of its derivative,
respectively. Our strategy is to relate $\lambda_{\rm
min}(J_{L-2}J_{L-2}^{\top})$ to $\lambda_{\rm
min}(\tilde{J}_{L-2}\tilde{J}_{L-2}^{\top})$ via the following two steps.

_Step (a): Centering $F_{L-2}$ and $B_{L-1}$._ We show that $\lambda_{\rm
min}(J_{L-2}J_{L-2}^{\top})\geq\lambda_{\rm
min}(\tilde{J}_{FB}\tilde{J}_{FB}^{\top})-o(n_{L-2}n_{L-1})$, where
$\tilde{J}_{FB}\tilde{J}_{FB}^{\top}=\tilde{F}_{L-2}\tilde{F}_{L-2}^{\top}\circ\tilde{B}_{L-1}\tilde{B}_{L-1}^{\top}$
and $\tilde{F}_{L-2}=F_{L-2}-\mathbb{E}_{X}[F_{L-2}]$ and
$\tilde{B}_{L-1}=B_{L-1}-\mathbb{E}_{X}[B_{L-1}]$ (Lemma D.1 in Appendix D.1).
Our strategy differs from existing work (e.g., [59, 46]), where either only
the backpropagation term is centered (cf. Proposition 7.1 of [59]) or only the
features are centered (cf. Lemma 5.4 of [46]). We remark that, in order to
handle deep networks with minimum overparameterization222In contrast, [59]
considers shallow networks, and [46] requires the existence of a layer with
roughly $\Omega(N)$ neurons., the centering of $F_{L-2}$ and $B_{L-1}$ is
crucially performed _at the same time_. In fact, by doing so, certain terms
containing an eigenvalue which is negative and large in modulus suitably
cancel. As a result, the difference between the original kernel
$J_{L-2}J_{L-2}^{\top}$ and the centered one
$\tilde{J}_{FB}\tilde{J}_{FB}^{\top}$ can be bounded by a matrix whose
operator norm is $o(n_{L-2}n_{L-1})$.

_Step (b): Centering everything._ We show that $\lambda_{\rm
min}(\tilde{J}_{FB}\tilde{J}_{FB}^{\top})\geq\lambda_{\rm
min}(\tilde{J}_{L-2}\tilde{J}_{L-2}^{\top})-o(n_{L-2}n_{L-1})$, where the rows
of $\tilde{J}_{L-2}$ are given by (3.6) (Lemma D.2 in Appendix D.2). The idea
is to decompose the difference
$\tilde{J}_{FB}\tilde{J}_{FB}^{\top}-\tilde{J}_{L-2}\tilde{J}_{L-2}^{\top}$
into a rank-1 matrix plus a PSD matrix. Then, in order to bound the operator
norm of the rank-1 term, we leverage the general version of the Hanson-Wright
inequality given by Theorem 2.3 in [1] (see the tail bound on quadratic forms
that we provide in Lemma B.5). This strategy avoids whitening and dropping
rows (as done in [59]) and, hence, appears to be better suited to the deep
case.

The main result of this part is stated below, and it is proved by combining
Lemmas D.1 and D.2.

######  Theorem 2 (Jacobian centering).

Consider the setting of Theorem 1, and let the rows of $J_{L-2}$ and
$\tilde{J}_{L-2}$ be given by (3.5) and (3.6), respectively. Then, we have

$\lambda_{\rm min}\left(J_{L-2}J_{L-2}^{\top}\right)\geq\lambda_{\rm
min}\left(\tilde{J}_{L-2}\tilde{J}_{L-2}^{\top}\right)-o(n_{L-2}n_{L-1}),$
(3.7)

with probability at least $1-C\exp(-c\log^{2}n_{L-1})-C\exp(-c\log^{2}N)$ over
$(x_{i})_{i=1}^{N}$ and $(W_{k})_{k=1}^{L}$, where $c,C$ are numerical
constants.

#### Part 2: Bounding the centered Jacobian.

If we fix the weight matrices $(W_{l})_{l=1}^{L}$, the rows of
$\tilde{J}_{L-2}$ are i.i.d. vectors of the form $u\otimes
v-\mathbb{E}\left[u\otimes v\right]$, where both $u$ and $v$ are centered. By
exploiting this structure, in Appendix E.1 we bound the $\ell_{2}$ and sub-
exponential norms of these rows. The $\ell_{2}$ norm is bounded in Lemma E.2,
and this result relies on the tight estimates on the $\ell_{2}$ norms of
centered features and centered backpropagation terms given by Lemma C.4 and
C.5, respectively. The sub-exponential norm is bounded in Lemma E.3, and we
use again the tail bound of Lemma B.5, which exploits the version of the
Hanson-Wright inequality in [1]. At this point, the problem is reduced to
bounding the smallest eigenvalue of a matrix such that its rows are i.i.d. and
we have a good control on their $\ell_{2}$ and sub-exponential norms. This
goal can be achieved via the following result, whose proof follows from
Theorem 3.2 in [2] and it is presented for completeness in Appendix E.2.

######  Proposition 3.1.

Let $\tilde{J}$ be a matrix with rows
$\tilde{J}_{i:}\in\mathbb{R}^{n_{L-2}n_{L-1}}$, for $i\in[N]$. Assume that
$\\{\tilde{J}_{i:}\\}_{i\in[N]}$ are independent sub-exponential random
vectors with $\psi=\mathop{\rm
max}\nolimits_{i}\|\tilde{J}_{i:}\|_{\psi_{1}}$. Let
$\eta_{\textup{min}}=\mathop{\rm min}\nolimits_{i}\|\tilde{J}_{i:}\|_{2}$ and
$\eta_{\textup{max}}=\mathop{\rm max}\nolimits_{i}\|\tilde{J}_{i:}\|_{2}$. Set
$\xi=\psi K+K^{\prime}$, and $\Delta:=C\xi^{2}N^{1/4}(n_{L-1}n_{L-2})^{3/4}$.
Then, we have that

$\lambda_{\rm
min}\left(\tilde{J}\tilde{J}^{\top}\right)\geq\eta_{\textup{min}}^{2}-\Delta$
(3.8)

holds with probability at least

$1-\exp\left(-cK\sqrt{N}\log\left(\frac{2n_{L-1}n_{L-2}}{N}\right)\right)-\mathbb{P}\left(\eta_{\text{max}}\geq
K^{\prime}\sqrt{n_{L-1}n_{L-2}}\right),$ (3.9)

where $c$ and $C$ are numerical constants.

The main result of this part is stated below, and it is proved in Appendix
E.3.

######  Theorem 3 (Bounding the centered Jacobian).

Consider the setting of Theorem 1, and let the rows of $\tilde{J}_{L-2}$ be
given by (3.6). Then, we have

$\lambda_{\rm
min}\left(\tilde{J}_{L-2}\tilde{J}_{L-2}^{\top}\right)=\Omega(n_{L-2}n_{L-1}),$
(3.10)

with probability at least $1-Ce^{-c\sqrt{N}}-C\,Ne^{-c\log^{2}n_{L-1}}$ over
$(x_{i})_{i=1}^{N}$ and $(W_{k})_{k=1}^{L}$, where $c$ and $C$ are numerical
constants.

Recall that $K\succeq K_{L-2}$, hence $\lambda_{\rm
min}\left(K\right)\geq\lambda_{\rm min}\left(K_{L-2}\right)=\lambda_{\rm
min}\left(J_{L-2}J_{L-2}^{\top}\right)$. Thus, the lower bound (3.1) follows
by combining the results from Theorem 2 and Theorem 3.

Finally, the upper bound (3.2) is rather straightforward. First, we write

$\lambda_{\rm min}\left(K\right)=\lambda_{\rm
min}\left(JJ^{\top}\right)\leq(JJ^{\top})_{11}=\sum_{l=0}^{L-1}\left\|(F_{l})_{1:}\right\|_{2}^{2}\left\|(B_{l+1})_{1:}\right\|_{2}^{2}.$
(3.11)

Then, by combining the bound on $\left\|(F_{l})_{1:}\right\|_{2}^{2}$ of Lemma
C.1 with a direct calculation for $\left\|(B_{l+1})_{1:}\right\|_{2}^{2}$, the
desired result (3.2) follows. The details are contained in Appendix F.

##  4 Two Applications: Memorization and Optimization

#### Memorization capacity.

The fact that the NTK Gram matrix (2.3) is well conditioned readily implies a
result on memorization capacity. This was already observed in [40] for two-
layer networks and in [46] for deep networks with a layer containing
$\Omega(N)$ neurons. Here, by using Theorem 1, we show that $\Omega(N)$
parameters between the last pair of hidden layers are enough for the network
to fit $N$ real-valued labels up to an arbitrarily small error. The result is
stated below and, for completeness, we give the proof in Appendix G.

######  Corollary 4.1 (Memorization).

Consider an $L$-layer neural network (2.1), where the activation function
satisfies Assumption 3 and the layer widths satisfy Assumptions 4 and 5. Let
$\left\\{x_{i}\right\\}_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$, where $P_{X}$
satisfies the Assumptions 1-2. Then, it holds that for every
$Y\in\mathbb{R}^{N}$, and for every $\varepsilon>0$, there exists a set of
parameters $\theta$ such that

$\left\|F_{L}(\theta)-Y\right\|_{2}\leq\varepsilon,$ (4.1)

with probability at least $1-C\,Ne^{-c\log^{2}n_{L-1}}-Ce^{-c\log^{2}N}$ over
$(x_{i})_{i=1}^{N}$, where $c$ and $C$ are numerical constants.

#### Gradient descent training.

Theorem 1 has implications on the convergence of gradient descent algorithms.
In particular, by choosing carefully the initialization, we show that gradient
descent trained on the $N$ samples $\\{x_{i}\\}_{i=1}^{N}$ with labels
$Y=(Y_{1},\ldots,Y_{N})$ converges to zero loss. This is – at the best of our
knowledge – the _first result of this kind for deep networks with minimum
over-parameterization_.

To define our initialization, let us assume that the $(L-1)$-th layer has an
even number of neurons. With a slight abuse of notation, we indicate its width
as $2n_{L-1}$. Thus, $W_{L-1}$ can be written in the form
$\left[W_{L-1}^{(1)},W_{L-1}^{(2)}\right]$, where
$W_{L-1}^{(1)},W_{L-1}^{(2)}\in\mathbb{R}^{n_{L-2}\times n_{L-1}}$. Similarly,
$W_{L}\in\mathbb{R}^{2n_{L-1}}$ is the concatenation of
$W_{L}^{(1)},W_{L}^{(2)}\in\mathbb{R}^{n_{L-1}}$. Then, we define the
initialization
$\theta_{0}=[\operatorname{\mathop{vec}}(W_{1,0}),\ldots,\operatorname{\mathop{vec}}(W_{L,0})]$
as follows:

$\begin{split}(W_{l,0})_{i,j}&\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta_{l}^{2}/n_{l-1}),\,\,l\in[L-2],\,i\in[n_{l-1}],\,j\in[n_{l}],\\\
(W_{L-1,0}^{(1)})_{i,j}&\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta_{L-1}^{2}/n_{L-2}),\,\,i\in[n_{L-2}],\,j\in[n_{L-1}],\,\,\mbox{and}\,\,W_{L-1,0}^{(2)}=W_{L-1,0}^{(1)},\\\
(W_{L,0}^{(1)})_{i}&\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta_{L}^{2}\gamma),\,\,i\in[n_{L-1}],\,\,\mbox{and}\,\,W_{L,0}^{(2)}=-W_{L,0}^{(1)}.\end{split}$
(4.2)

As usual, $(\beta_{l})_{l=1}^{L}$ are numerical constants independent of the
layer widths. In contrast, the quantity $\gamma$ will be set to a suitably
large value depending on the number of training samples and on the layer
widths. In words, the initialization is standard for
$W_{1,0},\ldots,W_{L-2,0}$ and $W_{L-1,0}^{(1)}$; the variance of
$W_{L,0}^{(1)}$ is boosted up by a factor $\gamma$; and we duplicate the
neurons of layer $L-1$ so that $W_{L-1,0}^{(2)}=W_{L-1,0}^{(1)}$ and
$W_{L,0}^{(2)}=-W_{L,0}^{(1)}$. At this point, we are ready to state our
optimization result.

######  Theorem 4 (Optimization via gradient descent).

Consider an $L$-layer neural network (2.1), where the activation function
satisfies Assumption 3 and the layer widths satisfy Assumptions 4 and 5.
Consider training data $\left\\{x_{i}\right\\}_{i=1}^{N}\sim_{\rm
i.i.d.}P_{X}$, where $P_{X}$ satisfies the Assumptions 1-2, with labels
$Y\in\mathbb{R}^{N}$ such that $\left\|Y\right\|_{2}=\Theta(\sqrt{N})$. We
consider solving the least-squares optimization problem

$\mathop{\rm min}\nolimits_{\theta}\mathcal{L}(\theta):=\frac{1}{2}\mathop{\rm
min}\nolimits_{\theta}\left\|F_{L}(\theta)-Y\right\|_{2}^{2},$ (4.3)

by running gradient descent updates of the form
$\theta_{t+1}=\theta_{t}-\eta\nabla\mathcal{L}(\theta_{t})$, where the
initialization $\theta_{0}$ is defined in (4.2) with $\gamma=d^{3}N^{2}$ and
$\eta\leq C(\gamma Ndn_{L-1})^{-1}$. Then, for all $t\geq 1$,

$\mathcal{L}(\theta_{t})\leq\left(1-c\eta\gamma
n_{L-2}n_{L-1}\right)^{t}\mathcal{L}(\theta_{0}),$ (4.4)

with probability at least $1-C\,Ne^{-c\log^{2}n_{L-1}}-Ce^{-c\log^{2}N}$ over
$(x_{i})_{i=1}^{N}$ and the initialization $\theta_{0}$, where $c$ and $C$ are
numerical constants.

Figure 2: Value of the loss $\mathcal{L}(\theta_{f})$ once gradient descent
has converged for a 4-layer ReLU network with $d=n_{1}=n_{2}=n_{3}$.

In words, (4.4) guarantees that gradient descent _linearly_ converges to a
point with zero loss. We also note that (our upper bound on) the convergence
rate can be expressed as a simple function of the learning rate $\eta$, the
number of training samples $N$, and the layer widths
$\\{n_{i}\\}_{i=0}^{L-1}$.

In Figure 2, we give an illustrative example that 4-layer networks achieve $0$
loss when the number of parameters is at least linear in the number of
training samples, i.e., under minimum over-parameterization. To ease the
experimental setup, we use a ReLU activation, with Adam optimizer. We
initialize the network as in the setting of Theorem 1, picking $\beta_{l}=1$
for all $l\in[L]$. The inputs, as well as the targets, are sampled from a
standard Gaussian distribution. The plot is averaged over $10$ independent
trials. As predicted by Theorem 4, the loss experiences a phase transition and
it goes from $1$ to $0$ when the layer widths are of order $\sqrt{N}$.

We now provide a sketch of the argument of Theorem 4, deferring the detailed
proof to Appendix H. As a consequence of Theorem 1, the NTK is well
conditioned at the initialization $\theta_{0}$, which implies that gradient
descent makes progress at the beginning. The idea is that the NTK remains
sufficiently well conditioned also during training and, hence, the loss
vanishes with the linear rate in (4.4), since the trained weights remain
confined in a ball of sufficiently small radius centered at $\theta_{0}$. More
specifically, we exploit the optimization framework developed in [47]. There,
a convergence result is proved if the following condition holds: there exists
$\alpha,\beta$ such that

$\begin{split}&\alpha\leq\sigma_{\textup{min}}(J(\theta))\leq\left\lVert
J(\theta)\right\rVert_{\textup{op}}\leq\beta,\quad\mbox{ and }\quad\left\lVert
J(\theta_{1})-J(\theta_{2})\right\rVert_{\textup{op}}\leq\frac{\alpha^{2}}{2\beta},\end{split}$
(4.5)

for all
$\theta,\theta_{1},\theta_{2}\in\mathcal{D}=\mathcal{B}(\theta_{0},R)$, where
$\mathcal{D}$ denotes a ball centered at $\theta_{0}$ of radius
$R:=4\|F_{L}(\theta_{0})-Y\|_{2}/\alpha$ (cf. Proposition H.1). In order to
control the radius $R$, we take advantage of the form (4.2) of the
initialization $\theta_{0}$. In particular, the spectrum of the Jacobian $J$
(and, hence, $\alpha$) scales linearly in $\sqrt{\gamma}$, and the network
output at initialization $F_{L}(\theta_{0})$ is equal to $0$ (cf. Lemma H.2).
Thus, as $\left\|Y\right\|_{2}=\Theta(\sqrt{N})$, we have that
$R=\Theta(\sqrt{N}/\alpha)$, which can be controlled by choosing suitably
$\gamma$. At this point, the argument consists in providing a number of
estimates on feature vectors, backpropagation terms, and finally the Jacobian
$J(\theta)$ for all $\theta\in\mathcal{D}$ (cf. Lemmas H.3-H.9). This allows
us to find $\alpha,\beta$ such that (4.5) holds and conclude.

##  5 Related Work and Discussion

#### Random matrices in deep learning.

The limiting spectra of several random matrices related to neural networks
have been the subject of a recent line of work. In particular, the Conjugate
Kernel (CK) – namely, the Gram matrix of the features from the last hidden
layer – has been studied for models with two layers [52, 35, 37, 49], with a
bias term [3, 54], and with multiple layers [13]. The Hessian matrix has been
considered in [50], and the closely related Fisher information matrix in [53].
Using tools from free probability, the input-output Jacobian (as opposed to
the parameter-output Jacobian considered in this work) of deep networks is
studied in [51] and the NTK of a two-layer model in [4]. In [22], the spectrum
of NTK and CK for deep networks is characterized via an iterated Marchenko-
Pastur map. The generalization error has also been studied via the spectrum of
suitable random matrices, see [28, 39, 36, 40] and Section 6 of the review
[11]. Most of the existing results focus on the linear-width asymptotic
regime, where the widths of the various layers are linearly proportional. An
exception is [66], which focuses on the ultra-wide two-layer case ($n_{1}\gg
N$).

#### Smallest eigenvalue of empirical kernels.

In the line of work mentioned above, the limiting spectrum of the random
matrix is characterized in terms of weak convergence, which does not lead to a
direct implication on the behavior of its smallest eigenvalue. In fact, lower
bounding the smallest eigenvalue often requires understanding the speed of
convergence to the limit spectrum. Quantitative bounds for random Fourier
features are obtained in [9]. In the two-layer setting, the smallest NTK
eigenvalue is lower bounded in [59, 40, 66], and concentration bounds can also
be obtained from [4, 61, 30]. In particular, [40] establishes a tight bound
for two-layer networks with roughly as many parameters as training samples
(hence, under minimum over-parameterization), and for a wide class of
activations. However, this result still requires that $n_{1}=\Omega(d)$. For
deep networks, a convergence rate on the NTK can be obtained from [7] and
potentially from [15], however these results require all the layers to be
wide. In [46], it is proved that a single layer of linear width suffices for
the NTK to be well conditioned. Here, Theorem 1 provides the first result for
deep networks under minimum over-parameterization, therefore allowing for sub-
linear layer widths.

#### Memorization capacity and gradient descent training.

For binary classification, the memorization capacity of neural networks was
first studied by Cover [17], who solved the single-neuron case. Later, Baum
[12] proved that, for two-layer networks, the memorization capacity is lower
bounded by the number of parameters, and upper bounds of the same order were
given in [33, 56]. Recently, tight results for two-layer networks in the
regression setting333As pointed out in [40], achieving memorization for
regression is harder than for classification, where it suffices to satisfy
inequality constraints. have been provided [14, 40]. In particular, [14]
generalizes the construction of [12], while the memorization result of [40]
comes from a bound on the smallest NTK eigenvalue. This same route is also
followed to analyze deep networks in [46] and in this work. Results for
multiple layers have been provided in [10, 69, 64, 23]. As concerns efficient
algorithms achieving memorization, [18, 19] study classification with two-
layer networks. A popular line of research has exploited the NTK view to give
optimization guarantees on gradient descent. Existing work has focused on the
two-layer case [59, 21, 48, 61, 67, 60], and optimal results in terms of over-
parameterization have been obtained [40]. For deep networks, [20] assumes a
lower bound on the smallest NTK eigenvalue, [5, 71, 72] require all the layer
widths to be (rather large) polynomials in the number of samples, and [45, 41]
reduce the over-parameterization to a single layer of linear width. In
particular, in these last two papers, the analysis of the NTK is reduced to
that of a certain feature matrix (the first one in [45] and the last one in
[41]). Hence, these approaches do not seem suitable to tackle networks with
sub-linear layer widths444If the width is sub-linear, then the feature matrix
is low-rank and, hence, its smallest eigenvalue is $0$..

##  6 Concluding Remarks

In this paper, we show that the NTK is well conditioned for deep networks with
sub-linear layer widths. As consequences of our NTK bounds, we also prove
results on the memorization capacity and the optimization via gradient descent
of such a class of networks. Our approach requires smooth activations and
layer widths which do not significantly grow in size with the depth. We
believe such assumptions to be purely technical, and we leave as an open
question their removal. Our novel NTK analysis paves the way for the study of
deep networks with minimum over-parameterization, and it could potentially be
applied beyond standard gradient descent, e.g., for optimization with momentum
[65], or federated learning [31].

## Acknowledgements

The authors were partially supported by the 2019 Lopez-Loreta prize, and they
would like to thank Quynh Nguyen, Mahdi Soltanolkotabi and Adel Javanmard for
helpful discussions.

## References

  * [1] Radoslaw Adamczak.  A note on the Hanson-Wright inequality for random vectors with dependencies.  Electronic Communications in Probability, 20:1–13, 2015.
  * [2] Radoslaw Adamczak, Alexander E Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann.  Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling.  Constructive Approximation, 34(1):61–88, 2011.
  * [3] Ben Adlam, Jake Levinson, and Jeffrey Pennington.  A random matrix perspective on mixtures of nonlinearities for deep learning, 2019.  arXiv:1912.00827.
  * [4] Ben Adlam and Jeffrey Pennington.  The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization.  In International Conference on Machine Learning (ICML), 2020.
  * [5] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International Conference on Machine Learning (ICML), 2019.
  * [6] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In International Conference on Machine Learning (ICML), 2019.
  * [7] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Rousong Wang.  On exact computation with an infinitely wide neural net.  In Neural Information Processing Systems (NeurIPS), 2019.
  * [8] P. Auer, M. Herbster, and M. Warmuth.  Exponentially many local minima for single neurons.  In Neural Information Processing Systems (NIPS), 1996.
  * [9] Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh.  Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees.  In International Conference on Machine Learning (ICML), 2017.
  * [10] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian.  Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks.  Journal of Machine Learning Research (JMLR), 20(63):1–17, 2019\.
  * [11] Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin.  Deep learning: a statistical viewpoint.  Acta numerica, 30:87–201, 2021.
  * [12] Eric B. Baum.  On the capabilities of multilayer perceptrons.  Journal of Complexity, 4, 1988.
  * [13] Lucas Benigni and Sandrine Péché.  Eigenvalue distribution of some nonlinear models of random matrices.  Electronic Journal of Probability, 26:1 – 37, 2021.
  * [14] Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer.  Network size and weights size for memorization with two-layers neural networks.  In Neural Information Processing Systems (NeurIPS), 2020.
  * [15] Sam Buchanan, Dar Gilboa, and John Wright.  Deep networks and the multiple manifold problem.  In International Conference on Learning Representations (ICLR), 2021\.
  * [16] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In Neural Information Processing Systems (NeurIPS), volume 32, 2019\.
  * [17] Thomas M. Cover.  Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition.  IEEE Transactions on Electronic Computers, (3):326–334, 1965.
  * [18] Amit Daniely.  Memorizing gaussians with no over-parameterizaion via gradient decent on neural networks, 2020.  arXiv:2003.12895.
  * [19] Amit Daniely.  Neural networks learning and memorization with (almost) no over-parameterization.  In Neural Information Processing Systems (NeurIPS), 2020.
  * [20] Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In International Conference on Machine Learning (ICML), 2019.
  * [21] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In International Conference on Learning Representations (ICLR), 2019\.
  * [22] Zhou Fan and Zhichao Wang.  Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks.  In Neural information processing systems (NeurIPS), 2020.
  * [23] Rong Ge, Runzhe Wang, and Haoyu Zhao.  Mildly overparametrized neural nets can memorize training data efficiently, 2019.  arXiv:1909.11837.
  * [24] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  When do neural networks outperform kernel methods?  In Neural Information Processing Systems (NeurIPS), 2020.
  * [25] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Linearized two-layers neural networks in high dimension.  The Annals of Statistics, 49(2):1029–1054, 2021.
  * [26] Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In International Conference on Machine Learning (ICML), 2010.
  * [27] Dongyoon Han, Jiwhan Kim, and Junmo Kim.  Deep pyramidal residual networks.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5927–5935, 2017.
  * [28] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  The Annals of Statistics, 50(2):949–986, 2022.
  * [29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
  * [30] Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington.  The surprising simplicity of the early-time learning dynamics of neural networks.  In Neural Information Processing Systems (NeurIPS), 2020.
  * [31] Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang.  Fl-ntk: A neural tangent kernel-based framework for federated learning analysis.  In International Conference on Machine Learning (ICML), 2021.
  * [32] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In Neural Information Processing Systems (NeurIPS), 2018.
  * [33] Adam Kowalczyk.  Counting function theorem for multi-layer networks.  In Neural Information Processing Systems (NIPS), 1994.
  * [34] Yann LeCun, Léon Bottou, Genevieve Orr, and Klaus-Robert Müller.  Efficient backprop.  In Neural networks: Tricks of the trade, pages 9–48. Springer, 2012\.
  * [35] Zhenyu Liao and Romain Couillet.  On the spectrum of random features maps of high dimensional data.  In International Conference on Machine Learning (ICML), 2018.
  * [36] Zhenyu Liao, Romain Couillet, and Michael W. Mahoney.  A random matrix analysis of random Fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent.  In Neural Information Processing Systems (NeurIPS), 2020.
  * [37] Cosme Louart, Zhenyu Liao, and Romain Couillet.  A random matrix approach to neural networks.  The Annals of Applied Probability, 28(2):1190–1248, 2018.
  * [38] Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration.  Applied and Computational Harmonic Analysis, 2021.
  * [39] 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\.
  * [40] Andrea Montanari and Yiqiao Zhong.  The interpolation phase transition in neural networks: Memorization and generalization under lazy training, 2020.  arXiv:2007.12826.
  * [41] Quynh Nguyen.  On the proof of global convergence of gradient descent for deep relu networks with linear widths.  In International Conference on Machine Learning (ICML), 2021.
  * [42] Quynh Nguyen, Pierre Bréchet, and Marco Mondelli.  When are solutions connected in deep networks?  In Neural Information Processing Systems (NeurIPS), 2021.
  * [43] Quynh Nguyen and Matthias Hein.  The loss surface of deep and wide neural networks.  In International Conference on Machine Learning (ICML), 2017.
  * [44] Quynh Nguyen and Matthias Hein.  Optimization landscape and expressivity of deep CNNs.  In International Conference on Machine Learning (ICML), 2018.
  * [45] Quynh Nguyen and Marco Mondelli.  Global convergence of deep networks with one wide layer followed by pyramidal topology.  In Neural Information Processing Systems (NeurIPS), 2020.
  * [46] Quynh Nguyen, Marco Mondelli, and Guido Montufar.  Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks.  In International Conference on Machine Learning (ICML), 2021.
  * [47] Samet Oymak and Mahdi Soltanolkotabi.  Overparameterized nonlinear learning: Gradient descent takes the shortest path?  In International Conference on Machine Learning (ICML), 2019.
  * [48] Samet Oymak and Mahdi Soltanolkotabi.  Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks.  IEEE Journal on Selected Areas in Information Theory, 1(1):84–105, 2020.
  * [49] Sandrine Péché.  A note on the Pennington-Worah distribution.  Electronic Communications in Probability, 24:1–7, 2019.
  * [50] Jeffrey Pennington and Yasaman Bahri.  Geometry of neural network loss surfaces via random matrix theory.  In International Conference on Machine Learning (ICML), 2017.
  * [51] Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli.  The emergence of spectral universality in deep networks.  In International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
  * [52] Jeffrey Pennington and Pratik Worah.  Nonlinear random matrix theory for deep learning.  In Neural Information Processing Systems (NeurIPS), 2017.
  * [53] Jeffrey Pennington and Pratik Worah.  The spectrum of the fisher information matrix of a single-hidden-layer neural network.  In Neural Information Processing Systems (NeurIPS), 2018.
  * [54] Vanessa Piccolo and Dominik Schröder.  Analysis of one-hidden-layer neural networks via the resolvent method.  In Neural Information Processing Systems (NeurIPS), 2021.
  * [55] Itay Safran and Ohad Shamir.  Spurious local minima are common in two-layer ReLU neural networks.  In International Conference on Machine Learning (ICML), 2018.
  * [56] Akito Sakurai.  nh-1 networks store no less n* h+ 1 examples, but sometimes no more.  In IJCNN International Joint Conference on Neural Networks, 1992\.
  * [57] Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet.  Random matrix theory proves that deep learning representations of GAN-data behave as gaussian mixtures.  In International Conference on Machine Learning (ICML), 2020.
  * [58] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations (ICLR), 2015\.
  * [59] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee.  Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.  IEEE Transactions on Information Theory, 65(2):742–769, 2018.
  * [60] Chaehwan Song, Ali Ramezani-Kebrya, Thomas Pethick, Armin Eftekhari, and Volkan Cevher.  Subquadratic overparameterization for shallow neural networks.  In Neural Information Processing Systems (NeurIPS), 2021.
  * [61] Zhao Song and Xin Yang.  Quadratic suffices for over-parametrization via matrix chernoff bound, 2020.  arXiv:1906.03593.
  * [62] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices, page 210–268.  Cambridge University Press, 2012.
  * [63] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science.  Cambridge university press, 2018.
  * [64] Roman Vershynin.  Memory capacity of neural networks with threshold and rectified linear unit activations.  SIAM Journal on Mathematics of Data Science, 2(4):1004–1033, 2020\.
  * [65] Jun-Kun Wang, Chi-Heng Lin, and Jacob D Abernethy.  A modular analysis of provable acceleration via Polyak’s momentum: Training a wide ReLU network and a deep linear network.  In International Conference on Machine Learning (ICML), 2021.
  * [66] Zhichao Wang and Yizhe Zhu.  Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks, 2021.  arXiv:2109.09304.
  * [67] Xiaoxia Wu, Simon S. Du, and Rachel Ward.  Global convergence of adaptive gradient methods for an over-parameterized neural network, 2019.  arXiv:1902.07111.
  * [68] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie.  Small nonlinearities in activation functions create bad local minima in neural networks.  In International Conference on Learning Representations (ICLR), 2019\.
  * [69] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie.  Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity.  In Neural Information Processing Systems (NeurIPS), 2019.
  * [70] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires re-thinking generalization.  In International Conference on Learning Representations (ICLR), 2017\.
  * [71] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu.  Gradient descent optimizes over-parameterized deep relu networks.  Machine Learning, 109(3):467–492, 2020.
  * [72] Difan Zou and Quanquan Gu.  An improved analysis of training over-parameterized deep neural networks.  In Neural Information Processing Systems (NeurIPS), 2019.

##  Appendix A Additional Notations

Given a sub-exponential random variable $X$, let
$\|X\|_{\psi_{1}}=\inf\\{t>0\,\,:\,\,\mathbb{E}[\exp(|X|/t)]\leq 2\\}$.
Similarly, for a sub-Gaussian random variable, let
$\|X\|_{\psi_{2}}=\inf\\{t>0\,\,:\,\,\mathbb{E}[\exp(X^{2}/t^{2})]\leq 2\\}$.

We use the analogous definitions for vectors. In particular, let
$X\in\mathbb{R}^{n}$ be a random vector, then
$\left\|X\right\|_{\psi_{2}}:=\sup_{\left\|u\right\|_{2}=1}\left\|u^{\top}X\right\|_{\psi_{2}}$
and
$\left\|X\right\|_{\psi_{1}}:=\sup_{\left\|u\right\|_{2}=1}\left\|u^{\top}X\right\|_{\psi_{1}}$.

We indicate with $C$ and $c$ absolute, strictly positive, numerical constants,
that do not depend on the layer widths of the network
$\\{n_{l}\\}_{l=0}^{L-1}$ or the number of training samples $N$. Their value
may change from line to line.

##  Appendix B Some Useful Estimates

######  Lemma B.1.

Let $\beta:=1-1/(1+\alpha)$, with $\alpha$ being the constant defined in
Assumption 5. Then, we have

$Nn_{L-1}^{\beta}=o(n_{L-1}n_{L-2}),$ (B.1)
$n_{L-2}\cdot\log^{2}N\cdot\log^{2}n_{L-1}=o(n_{L-1}n_{L-2}),$ (B.2)
$n_{L-1}\cdot\log^{2}N\cdot\log^{2}n_{L-1}=o(n_{L-1}n_{L-2}),$ (B.3)

and, for all $k\in\mathbb{N}$,

$N\cdot\log^{2}n_{L-1}\cdot\log^{k}N=o(n_{L-1}n_{L-2}).$ (B.4)

###### Proof.

From Assumption 5, we have

$N=o((n_{L-1}n_{L-2})^{1/(1+\alpha)})=o(n_{L-2}n_{L-1}^{1/(1+\alpha)})=o(n_{L-2}n_{L-1}^{1-\beta}),$
(B.5)

which gives (B.1).

To obtain (B.4), let’s introduce the quantity $\zeta:=(1+\alpha)^{-1/2}<1$.
Then, we have that

$N\cdot\log^{2}n_{L-1}\cdot\log^{k}N=\mathcal{O}\left(N^{(1+\alpha)\zeta}(n_{L-1}n_{L-2})^{1-\zeta}\right).$
(B.6)

This, together with Assumption 5, gives (B.4).

Finally, to obtain (B.2), we can exploit the second requirement of Assumption
5, which implies $\log^{2}N=o(\sqrt{n_{L-1}})$. This readily implies (B.2).
Notice that (B.3) naturally follows since
$n_{L-1}=\mathcal{O}\left(n_{L-2}\right)$ by Assumption 4. ∎

######  Lemma B.2 (Lipschitz constant of function of the features).

For all $l\in[L-1]$, and for every Lipschitz function $\varphi$, we have

$\left\|\varphi(g_{l}(x))\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right),$
(B.7)

with probability at least

$1-2l\exp{(-n_{L-1})},$ (B.8)

over $(W_{k})_{k=1}^{l}$. We recall that $\varphi$ is applied component-wise
to $g_{l}(x)$, and $\varphi(g_{l}(x)):\mathbb{R}^{d}\to\mathbb{R}^{n_{l}}$ is
intended as a function of $x$.

###### Proof.

Note that $\varphi(g_{l})$ is a composition of Lipschitz functions. Thus,

$\displaystyle\left\|\varphi(g_{l})\right\|_{\mathrm{Lip}}$
$\displaystyle\leq\left\|\varphi\right\|_{\mathrm{Lip}}\left\|g_{l}\right\|_{\mathrm{Lip}}\leq\left\|\varphi\right\|_{\mathrm{Lip}}\left\lVert
W_{l}\right\rVert_{\textup{op}}\prod_{k=1}^{l-1}\left(\left\lVert
W_{k}\right\rVert_{\textup{op}}\left\|\phi\right\|_{\mathrm{Lip}}\right)$
(B.9) $\displaystyle\leq\left\|\varphi\right\|_{\mathrm{Lip}}\left\lVert
W_{l}\right\rVert_{\textup{op}}M^{l-1}\prod_{k=1}^{l-1}\left\lVert
W_{k}\right\rVert_{\textup{op}},$

where the last step is justified by Assumption 3.

Recall that, by the assumption on the initialization of the weights,
$(W_{k})_{i,j}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta^{2}_{k}/n_{k-1})$, for some constant $\beta_{k}$
which does not depend on the layer widths. Then, by Theorem 4.4.5 of [63], we
have that, for any $k\in[l]$,

$\left\lVert W_{k}\right\rVert_{\textup{op}}\leq
C\frac{\beta_{k}}{\sqrt{n_{k-1}}}(\sqrt{n_{k-1}}+2\sqrt{n_{k}}),$ (B.10)

with probability at least $1-2\exp{(-n_{k})}$, $C$ being a numerical constant.
By Assumption 4 on the topology of the network, we can rewrite this result as

$\left\lVert W_{k}\right\rVert_{\textup{op}}=\mathcal{O}\left(1\right),$
(B.11)

with probability at least $1-2\exp{(-n_{L-1})}$. To conclude, using a union
bound over the layers up to layer $l$, we have that

$\left\|\varphi(g_{l})\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right),$
(B.12)

with probability at least $1-2l\exp{(-n_{L-1})}$ over $(W_{k})_{k=1}^{l}$. ∎

######  Lemma B.3.

We have that

$\left\lVert D_{L}\right\rVert_{\textup{op}}\leq\log{n_{L-1}},$ (B.13)

with probability at least $1-2\exp(-c\log^{2}n_{L-1})$ over $W_{L}$, where $c$
is a numerical constant.

###### Proof.

Recall that $D_{L}=\text{diag}(W_{L})$ contains on the diagonal $n_{L-1}$
independent Gaussian random variables
$(D_{L})_{ii}\sim\mathcal{N}(0,\beta^{2}_{L})$. Thus, for any $i\in[n_{L-1}]$,

$\mathbb{P}(|(D_{L})_{ii}|>\log
n_{L-1})<2\exp(-\log^{2}n_{L-1}/(2\beta^{2}_{L})),$ (B.14)

which gives

$\displaystyle\mathbb{P}(\left\lVert D_{L}\right\rVert_{\textup{op}}>\log
n_{L-1})=$ $\displaystyle\mathbb{P}(\mathop{\rm
max}\nolimits_{i\in[n_{L-1}]}|(D_{L})_{ii}|>\log n_{L-1})$ (B.15)
$\displaystyle\leq$ $\displaystyle n_{L-1}\mathbb{P}(|(D_{L})_{11}|>\log
n_{L-1})$ $\displaystyle<$ $\displaystyle 2\exp(\log
n_{L-1}-\log^{2}n_{L-1}/(2\beta^{2}_{L}))$ $\displaystyle<$ $\displaystyle
2\exp(-c\log^{2}n_{L-1}),$

where the second step is a union bound on the entries of $D_{L}$. This gives
the desired result. ∎

######  Lemma B.4.

We have that

$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))\right\|_{\mathrm{Lip}}=\mathcal{O}(\log
n_{L-1}),$ (B.16)

with probability at least $1-2\exp(-c\log^{2}n_{L-1})-C\exp{(-n_{L-1})}$ over
$(W_{k})_{k=1}^{L}$. We recall that $\phi^{\prime}$ is applied component-wise
to $g_{l}(x)$,
$D_{L}\phi^{\prime}(g_{L-1}(x)):\mathbb{R}^{d}\to\mathbb{R}^{n_{L-1}}$ is
intended as a function of $x$, and $c$ is a numerical constant.

###### Proof.

We know by composition of Lipschitz functions that

$\left\|D_{L}\phi^{\prime}(g_{L-1})\right\|_{\mathrm{Lip}}\leq\left\lVert
D_{L}\right\rVert_{\textup{op}}\left\|\phi^{\prime}(g_{L-1})\right\|_{\mathrm{Lip}}.$
(B.17)

By Assumption 3, $\phi^{\prime}$ is Lipschitz. Hence, by combining Lemma B.2
(where we use $\varphi=\phi^{\prime}$) and Lemma B.3, the result follows. ∎

######  Lemma B.5 (Exponential tails of quadratic forms).

Let $x\sim P_{X}$. Let $u:\mathbb{R}^{d}\to\mathbb{R}^{d_{u}}$ and
$v:\mathbb{R}^{d}\to\mathbb{R}^{d_{v}}$ be mean-0 Lipschitz functions with
respect to $x$, i.e., $\mathbb{E}_{x}[u(x)]=0$, $\mathbb{E}_{x}[v(x)]=0$,
$\left\|u\right\|_{\mathrm{Lip}}=c_{1}$ and
$\left\|v\right\|_{\mathrm{Lip}}=c_{2}$. Let $U$ be a $d_{u}\times d_{v}$
matrix, and

$\Gamma(x)=u(x)^{\top}Uv(x)-\mathbb{E}_{x}\left[u(x)^{\top}Uv(x)\right].$
(B.18)

Then,

$\left\|\Gamma\right\|_{\psi_{1}}<CK^{2}\left\|U\right\|_{F}.$ (B.19)

where $K=\sqrt{c_{1}^{2}+c_{2}^{2}}$, and $C$ is a numerical constant.

###### Proof.

Consider the function $z(x):\mathbb{R}^{d}\to\mathbb{R}^{d_{u}+d_{v}}$
obtained by concatenating the vectors $u$ and $v$, i.e.,

$z(x):=[u(x),v(x)]^{\top}.$ (B.20)

One can readily verify that
$\left\|z\right\|_{\mathrm{Lip}}\leq\sqrt{c_{1}^{2}+c_{2}^{2}}:=K$. Let us set

$M=\frac{1}{2}\left(\begin{array}[]{@{}c|c@{}}0&U\\\ \hline\cr
U^{\top}&0\end{array}\right).$ (B.21)

Then, we have that

$\Gamma=z^{\top}Mz-\mathbb{E}_{x}\left[z^{\top}Mz\right].$ (B.22)

Since $x$ satisfies Assumption 2 and $z(x)$ is Lipschitz, in order to obtain
tail bounds on $\Gamma$, we can apply the version of the Hanson-Wright
inequality given by Theorem 2.3 in [1]:

$\displaystyle\mathbb{P}(|\Gamma|>t)=$
$\displaystyle\mathbb{P}(|z^{\top}Mz-\mathbb{E}_{x}\left[z^{\top}Mz\right]|>t)$
(B.23) $\displaystyle<$ $\displaystyle 2\exp\left(-\frac{1}{C_{1}}\mathop{\rm
min}\nolimits\left(\frac{t^{2}}{K^{4}\left\|M\right\|^{2}_{F}},\frac{t}{K^{2}\left\lVert
M\right\rVert_{\textup{op}}}\right)\right)$ $\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{1}{C_{1}}\mathop{\rm
min}\nolimits\left(\frac{t^{2}}{K^{4}\left\|U\right\|^{2}_{F}},\frac{t}{K^{2}\left\lVert
U\right\rVert_{\textup{op}}}\right)\right),$

where $C_{1}$ is a numerical constant, and in the last step we use that
$\left\lVert M\right\rVert_{\textup{op}}=\left\lVert
U\right\rVert_{\textup{op}}$ and
$\left\|M\right\|_{F}^{2}=\left\|U\right\|_{F}^{2}/2\leq\left\|U\right\|_{F}^{2}$.
Thus, by Lemma 5.5 of [59], we conclude that

$\left\|\Gamma\right\|_{\psi_{1}}<C_{2}K^{2}\left\|U\right\|_{F},$ (B.24)

for some numerical constant $C_{2}$, which gives the desired result. ∎

######  Lemma B.6.

Let $u\in\mathbb{R}^{d_{u}}$ and $v\in\mathbb{R}^{d_{v}}$ be two mean-0 sub-
Gaussian vectors such that $\left\|u\right\|_{\psi_{2}}=c_{1}$ and
$\left\|v\right\|_{\psi_{2}}=c_{2}$. Set
$A_{uv}=\mathbb{E}\left[uv^{\top}\right]$. Then,

$\left\lVert A_{uv}\right\rVert_{\textup{op}}\leq C(c_{1}+c_{2})^{2},$ (B.25)

where $C$ is a numerical constant.

###### Proof.

Consider the vector

$z:=[u,v]^{\top}.$ (B.26)

Then, $z$ is sub-Gaussian and, by triangle inequality on the vectors $[u,0]$
and $[0,v]$, we have that $\left\|z\right\|_{\psi_{2}}\leq c_{1}+c_{2}$. Since
$u$ and $v$ are mean-0, then $z$ is also mean-0 and its covariance matrix can
be written as $A_{z}:=\mathbb{E}\left[zz^{\top}\right]$. Furthermore, we can
show that

$\left\lVert A_{z}\right\rVert_{\textup{op}}\leq C(c_{1}+c_{2})^{2}.$ (B.27)

In fact, let $w$ be the unitary eigenvector associated to the maximum
eigenvalue of $A_{z}$. Then,

$\left\lVert
A_{z}\right\rVert_{\textup{op}}=w^{\top}A_{z}w=\mathbb{E}\left[w^{\top}zz^{\top}w\right]=\mathbb{E}\left[(w^{\top}z)^{2}\right].$
(B.28)

Furthermore, we have that

$\left\|z\right\|_{\psi_{2}}:=\sup_{w^{\prime}\text{s.t.}\left\|w^{\prime}\right\|_{2}=1}\left\|(w^{\prime})^{\top}z\right\|_{\psi_{2}}\geq\left\|w^{\top}z\right\|_{\psi_{2}}\geq\frac{1}{C}\sqrt{\mathbb{E}\left[(w^{\top}z)^{2}\right]},$
(B.29)

where $C$ is a numerical constant, and the last inequality comes from Eq.
(2.15) of [63]. By combining (B.28) and (B.29) with
$\left\|z\right\|_{\psi_{2}}\leq c_{1}+c_{2}$, (B.27) readily follows.

Finally, we have that

$A_{z}=\left(\begin{array}[]{@{}c|c@{}}A_{u}&A_{uv}\\\ \hline\cr
A_{uv}^{\top}&A_{v}\end{array}\right),$ (B.30)

where $A_{u}:=\mathbb{E}\left[uu^{\top}\right]$ and
$A_{v}:=\mathbb{E}\left[vv^{\top}\right]$. As $A_{u}$ and $A_{v}$ are PSD, we
have that

$\left\lVert A_{uv}\right\rVert_{\textup{op}}\leq\left\lVert
A_{z}\right\rVert_{\textup{op}}.$ (B.31)

Hence, the desired result follows from (B.27) and (B.31). ∎

######  Lemma B.7.

Let $A$ be an $N\times n$ matrix whose rows $A_{i}$ are i.i.d. mean-0 sub-
Gaussian random vectors in $\mathbb{R}^{n}$. Let
$K=\left\|A_{i}\right\|_{\psi_{2}}$ the sub-Gaussian norm of each row. Then,
we have

$\left\lVert
AA^{\top}\right\rVert_{\textup{op}}=K^{2}\mathcal{O}\left(N+n\right),$ (B.32)

with probability at least $1-2\exp(-cn)$, for some numerical constant $c$.

###### Proof.

Without loss of generality, we can assume $K=1$ to simplify the proof. Let
$\Sigma$ be the second moment matrix of each of the rows of $A$. Then,
$\Sigma=\mathbb{E}\left[A_{i}A_{i}^{\top}\right]$, since the rows are mean-0.
Note that, as the rows of $A$ are i.i.d., $\Sigma$ is independent of $i$.
Furthermore, Lemma B.6 implies that the covariance matrix
$\mathbb{E}\left[A_{i}A_{i}^{\top}\right]$ has operator norm bounded by a
constant, since the sub-Gaussian norm of the rows is 1. Then, by using Remark
5.40 in [62], we have that

$\left\lVert\frac{A^{\top}A}{N}-\Sigma\right\rVert_{\textup{op}}\leq\mathop{\rm
max}\nolimits(\delta,\delta^{2}),\qquad\mbox{ where
}\delta=C\sqrt{\frac{n}{N}}+\frac{t}{\sqrt{N}},$ (B.33)

with probability at least $1-2\exp(-ct^{2})$, where $c$ and $C$ are numerical
constants. Setting $t=\sqrt{n}$ and using a triangular inequality gives that,
with probability at least $1-2\exp(-ct^{2})$,

$\left\lVert AA^{\top}\right\rVert_{\textup{op}}=\left\lVert
A^{\top}A\right\rVert_{\textup{op}}\leq
N\left\lVert\Sigma\right\rVert_{\textup{op}}+\mathop{\rm
max}\nolimits(C\sqrt{nN}+\sqrt{nN},(C\sqrt{n}+\sqrt{n})^{2})=\mathcal{O}\left(N+n\right),$
(B.34)

which implies the desired result (after re-scaling by $K$). ∎

######  Lemma B.8.

Let $\tilde{F}_{l}=F_{l}-\mathbb{E}_{x}[F_{l}]\in\mathbb{R}^{N\times n_{l}}$
be the centered features matrix at layer $l$. Then, we have

$\left\lVert\tilde{F}_{l}\tilde{F}_{l}^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left(N+n_{l}\right),$
(B.35)

with probability at least $1-C\exp{(-cn_{L-1})}$ over $(W_{k})_{k=1}^{l}$ and
$(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$.

###### Proof.

From Lemma B.2, we have that

$\left\|f_{l}(x)\right\|_{\mathrm{Lip}}=\Theta(1),$ (B.36)

with probability at least

$1-C^{\prime}\exp{(-n_{L-1})},$ (B.37)

over $(W_{k})_{k=1}^{l}$. We condition on this event in the rest of the proof.

Since $(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$ and $P_{X}$ satisfies
Assumption 2, all the rows of $\tilde{F}_{l}$ are mean-0 sub-Gaussian vectors,
with sub-Gaussian norm bounded by a numerical constant. Here, we fix
$(W_{k})_{k=1}^{l}$ s.t. (B.36) holds, and the “mean-0” and the “sub-Gaussian
norm” is intended w.r.t. the probability space of $(x_{i})_{i=1}^{N}$.

An application of Lemma B.7 gives that

$\left\lVert\tilde{F}_{l}\tilde{F}_{l}^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left(N+n_{l}\right),$
(B.38)

with probability at least $1-2\exp{(-cn_{l})}$ over
$(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$. Taking into account the previous
conditioning, we conclude that

$\left\lVert\tilde{F}_{l}\tilde{F}_{l}^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left(N+n_{l}\right),$
(B.39)

with probability at least $1-(C^{\prime}+2)\exp{(-cn_{L-1})}$ over
$(W_{k})_{k=1}^{l}$ and $(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$. ∎

######  Lemma B.9.

Let $\tilde{B}_{L-1}=B_{L-1}-\mathbb{E}_{x}[B_{L-1}]\in\mathbb{R}^{N\times
n_{L-1}}$ be the centered back-propagation matrix at layer $L-1$. Then, we
have

$\left\lVert\tilde{B}_{L-1}\tilde{B}_{L-1}^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left((N+n_{L-1})\log^{2}n_{L-1}\right),$
(B.40)

with probability at least $1-C\exp{(-cn_{L-1})}$ over $(W_{k})_{k=l}^{L}$ and
$(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$.

###### Proof.

From Lemma B.4, we have that

$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))\right\|_{\mathrm{Lip}}=\mathcal{O}(\log
n_{L-1}),$ (B.41)

with probability at least

$1-2\exp(-c\log^{2}n_{L-1})-C\exp{(-n_{L-1})},$ (B.42)

over $(W_{k})_{k=1}^{L}$. We condition on this event in the rest of the proof.

Since $(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$ and $P_{X}$ satisfies
Assumption 2, all the rows of $\tilde{B}_{L-1}$ are mean-0 sub-Gaussian
vectors, with sub-Gaussian norm $\mathcal{O}(\log n_{L-1})$. Here, we fix
$(W_{k})_{k=1}^{L}$ s.t. (B.41) holds, and the “mean-0” and the “sub-Gaussian
norm” is intended w.r.t. the probability space of $(x_{i})_{i=1}^{N}$.

An application of Lemma B.7 gives that

$\left\lVert\tilde{B}_{L-1}\tilde{B}_{L-1}^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left((N+n_{L-1})\log^{2}n_{L-1}\right),$
(B.43)

with probability at least $1-2\exp{(-cn_{L-1})}$ over
$(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$. Taking into account the previous
conditioning, we conclude that

$\left\lVert\tilde{B}_{L-1}\tilde{B}_{L-1}^{\top}\right\rVert_{\textup{op}}=\mathcal{O}\left((N+n_{L-1})\log^{2}n_{L-1}\right),$
(B.44)

with probability at least $1-(C^{\prime}+2)\exp{(-cn_{L-1})}$ over
$(W_{k})_{k=1}^{L}$ and $(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$. ∎

######  Lemma B.10.

Let $\rho$ be a standard Gaussian random variable, then we have that

$\varphi_{1}(c):=\mathbb{E}_{\rho}\left[\phi(c\rho)\right],$ (B.45)

and

$\varphi_{2}(c):=\mathbb{E}_{\rho}\left[\phi^{2}(c\rho)\right],$ (B.46)

are continuous functions in $c$. Furthermore, $\varphi_{1}(c)$ is Lipschitz in
$c$, and

$\left|\varphi_{2}(c_{1})-\varphi_{2}(c_{2})\right|\leq
C_{1}\left|c_{1}-c_{2}\right|+C_{2}|c_{1}^{2}-c_{2}^{2}|,$ (B.47)

where $C_{1}$ and $C_{2}$ are numerical constants (independent of
$c_{1},c_{2}$).

###### Proof.

Let $p(\rho)=\frac{1}{\sqrt{2\pi}}e^{-\rho^{2}/2}$. Then, we have

$\displaystyle\left|\varphi_{1}(c+\varepsilon)-\varphi_{1}(c)\right|$
$\displaystyle\leq\int
p(\rho)\left|\phi((c+\varepsilon)\rho)-\phi(c\rho)\right|d\rho$ (B.48)
$\displaystyle\leq\int p(\rho)\left|M\varepsilon\rho\right|d\rho$
$\displaystyle=M\varepsilon\mathbb{E}_{\rho}\left[|\rho|\right]$
$\displaystyle=C\varepsilon,$

where in the second line we use that $\phi$ is $M$-Lipschitz by Assumption 3.
Similarly, we have

$\displaystyle\left|\varphi_{2}(c+\varepsilon)-\varphi_{2}(c)\right|$
$\displaystyle\leq\int
p(\rho)\left|\phi^{2}((c+\varepsilon)\rho)-\phi^{2}(c\rho)\right|d\rho$ (B.49)
$\displaystyle=\int
p(\rho)\left|\phi((c+\varepsilon)\rho)-\phi(c\rho)\right|\left|\phi((c+\varepsilon)\rho)+\phi(c\rho)\right|d\rho$
$\displaystyle\leq\int
p(\rho)\left|M\varepsilon\rho\right|\left(2\left|\phi(0)\right|+M(|c+\varepsilon|+|\varepsilon|)|\rho|\right)d\rho$
$\displaystyle=C_{1}\varepsilon\mathbb{E}_{\rho}\left[|\rho|\right]+C_{2}\varepsilon|c|\mathbb{E}_{\rho}\left[\rho^{2}\right]+C_{3}\varepsilon^{2}\mathbb{E}_{\rho}\left[\rho^{2}\right]$
$\displaystyle=C_{4}\varepsilon+C_{2}|c|\varepsilon+C_{3}\varepsilon^{2}$
$\displaystyle\leq
C_{5}\varepsilon+C_{6}\left|(c+\varepsilon)^{2}-c^{2}\right|.$

∎

######  Lemma B.11.

Let $\rho$ be a standard Gaussian distribution, and $c\neq 0$ be an absolute
constant. Then, we have

$|\mathbb{E}_{\rho}\left[\phi(c\rho)\right]|=\mathcal{O}\left(1\right).$
(B.50)

It also holds

$|\mathbb{E}_{\rho}\left[\phi^{\prime}(c\rho)\right]|=\mathcal{O}\left(1\right).$
(B.51)

###### Proof.

For the first statement, we exploit the fact that $\phi$ is Lipschitz:

$|\mathbb{E}_{\rho}\left[\phi(c\rho)\right]|\leq\mathbb{E}_{\rho}\left[|\phi(0)|+M|c\rho|\right]=|\phi(0)|+M|c|\mathbb{E}_{\rho}\left[|\rho|\right]=C_{1}.$
(B.52)

The statement on $\phi^{\prime}$ is easily derived following the same proof
and using that $\left\|\phi^{\prime}\right\|_{\mathrm{Lip}}\leq M^{\prime}$. ∎

######  Lemma B.12.

Let $\rho$ be a standard Gaussian distribution, and $c\neq 0$ be an absolute
constant. Then, we have

$\mathbb{E}_{\rho}\left[\phi^{2}(c\rho)\right]=\Theta(1),$ (B.53)

and

$\mathbb{E}_{\rho}\left[(\phi^{\prime}(c\rho))^{2}\right]=\Theta(1).$ (B.54)

###### Proof.

For the upper-bound of the first statement, we exploit the fact that $\phi$ is
Lipschitz:

$\mathbb{E}_{\rho}\left[\phi^{2}(c\rho)\right]\leq\mathbb{E}_{\rho}\left[(|\phi(0)|+M|c\rho|)^{2}\right]=\phi^{2}(0)+2M|c||\phi(0)|\mathbb{E}_{\rho}\left[|\rho|\right]+M^{2}c^{2}\mathbb{E}_{\rho}\left[\rho^{2}\right]=C_{1}.$
(B.55)

For the lower bound, since $\phi$ is non-zero and continuous, we have that
there exist a strictly positive constant $c^{\prime}>0$ and an interval
$[c_{1},c_{2}]$ with $c_{2}>c_{1}$ such that $\phi^{2}(x)\geq c^{\prime}$ for
each $x\in[c_{1},c_{2}]$. Therefore, we have

$\mathbb{E}_{\rho}\left[\phi^{2}(c\rho)\right]\geq
c^{\prime}\mathbb{P}(c_{1}\leq c\rho\leq c_{2})=C_{2}.$ (B.56)

The second statements is proved in the same way, as $\phi^{\prime}$ is a non-
zero Lipschitz function. ∎

######  Lemma B.13.

Let $\varphi:\mathbb{R}^{d}\to\mathbb{R}$ a Lipschitz function, and let $x\sim
P_{X}$. Then,

$\mathbb{E}_{x}^{2}\left[\varphi(x)\right]\geq\mathbb{E}_{x}\left[\varphi(x)^{2}\right]-c\left\|\varphi\right\|_{\mathrm{Lip}}^{2},$
(B.57)

where $c$ is a numerical constant.

###### Proof.

We have

$\displaystyle\mathbb{E}_{x}^{2}\left[\varphi(x)\right]$
$\displaystyle=\mathbb{E}_{x}\left[(\varphi(x))^{2}\right]-\mathbb{E}_{x}\left[\left(\varphi(x)-\mathbb{E}_{x}\left[\varphi(x)\right]\right)^{2}\right]$
(B.58)
$\displaystyle=\mathbb{E}_{x}\left[\varphi(x)^{2}\right]-\int_{0}^{+\infty}\mathbb{P}\left(\left(\varphi(x)-\mathbb{E}_{x}\left[\varphi(x)\right]\right)^{2}>t\right)dt$
$\displaystyle=\mathbb{E}_{x}\left[\varphi(x)^{2}\right]-\int_{0}^{+\infty}\mathbb{P}\left(\left|\varphi(x)-\mathbb{E}_{x}\left[\varphi(x)\right]\right|>\sqrt{t}\right)dt$
$\displaystyle\geq\mathbb{E}_{x}\left[\varphi(x)^{2}\right]-\int_{0}^{+\infty}2\exp\left(-Ct/\left\|\varphi\right\|_{\mathrm{Lip}}^{2}\right)dt$
$\displaystyle=\mathbb{E}_{x}\left[\varphi(x)^{2}\right]-2\left\|\varphi\right\|_{\mathrm{Lip}}^{2}/C,$

where the inequality is a consequence of Assumption 2. ∎

######  Lemma B.14.

Let $x\sim P_{X}$, and define
$\tilde{c}_{l}(x)=\beta_{l}\left\|f_{l}(x)\right\|/\sqrt{n_{l}}$.

Then, we have

$\mathbb{E}_{x}\left[\left|\tilde{c}_{l}(x)-\mathbb{E}_{x}\left[\tilde{c}_{l}(x)\right]\right|\right]\leq
C\frac{\left\|f_{l}\right\|_{\mathrm{Lip}}}{\sqrt{n_{l}}},$ (B.59)

and

$\mathbb{E}_{x}\left[\left(\tilde{c}_{l}(x)-\mathbb{E}_{x}\left[\tilde{c}_{l}(x)\right]\right)^{2}\right]\leq
C\frac{\left\|f_{l}\right\|^{2}_{\mathrm{Lip}}}{n_{l}},$ (B.60)

where $C$ is a numerical constant.

###### Proof.

We have that

$\displaystyle\mathbb{E}_{x}\left[\left|\tilde{c}_{l}(x)-\mathbb{E}_{x}\left[\tilde{c}_{l}(x)\right]\right|\right]$
$\displaystyle=\int_{0}^{+\infty}\mathbb{P}\left(\left|\tilde{c}_{l}(x)-\mathbb{E}_{x}\left[\tilde{c}_{l}(x)\right]\right|>t\right)dt$
(B.61)
$\displaystyle=\int_{0}^{+\infty}\mathbb{P}\left(\left|\left\|f_{l}(x)\right\|-\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|\right]\right|>\sqrt{n_{l}}t/\beta_{l}\right)dt$
$\displaystyle\leq\int_{0}^{+\infty}2\exp\left(-cn_{l}t^{2}/\left\|f_{l}\right\|_{\mathrm{Lip}}^{2}\right)dt$
$\displaystyle=C\frac{\left\|f_{l}\right\|_{\mathrm{Lip}}}{\sqrt{n_{l}}},$

where $c$ and $C$ are numerical constants, and the third line is justified by
Assumption 2.

Similarly, we have

$\displaystyle\mathbb{E}_{x}\left[\left(\tilde{c}_{l}(x)-\mathbb{E}_{x}\left[\tilde{c}_{l}(x)\right]\right)^{2}\right]$
$\displaystyle=\int_{0}^{+\infty}\mathbb{P}\left(\left(\tilde{c}_{l}(x)-\mathbb{E}_{x}\left[\tilde{c}_{l}(x)\right]\right)^{2}>t\right)dt$
(B.62)
$\displaystyle=\int_{0}^{+\infty}\mathbb{P}\left(\left|\left\|f_{l}(x)\right\|-\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|\right]\right|>\sqrt{n_{l}t}/\beta_{l}\right)dt$
$\displaystyle\leq\int_{0}^{+\infty}2\exp\left(-cn_{l}t/\left\|f_{l}\right\|_{\mathrm{Lip}}^{2}\right)dt$
$\displaystyle=C\frac{\left\|f_{l}\right\|^{2}_{\mathrm{Lip}}}{n_{l}},$

where, again, $c$ and $C$ are numerical constants and the third line is
justified by Assumption 2. ∎

######  Lemma B.15.

Let $\rho_{1}$ and $\rho_{2}$ be two standard Gaussian random variables,
possibly correlated. Then, we have

$\displaystyle\left|\mathbb{E}_{\rho_{1}\rho_{2}}\left[\phi(\rho_{1}x_{1})\phi(\rho_{2}x_{2})-\phi(\rho_{1}y_{1})\phi(\rho_{2}y_{2})\right]\right|\leq$
(B.63) $\displaystyle\hskip 28.45274pt\leq
C_{1}\left|x_{1}-y_{1}\right|+C_{2}\left|x_{2}\right|\left|x_{1}-y_{1}\right|+C_{3}\left|x_{2}-y_{2}\right|+C_{4}\left|y_{1}\right|\left|x_{2}-y_{2}\right|,$

where $C_{1},C_{2},C_{3},C_{4}$ are numerical constants (which do not depend
on $x_{1},x_{2},y_{1},y_{2}$). Furthermore, the same result holds with
$\phi^{\prime}$ instead of $\phi$.

###### Proof.

We have

$\displaystyle\left|\mathbb{E}_{\rho_{1}\rho_{2}}\left[\phi(\rho_{1}x_{1})\phi(\rho_{2}x_{2})-\phi(\rho_{1}y_{1})\phi(\rho_{2}y_{2})\right]\right|$
(B.64)
$\displaystyle\leq\left|\mathbb{E}_{\rho_{1}\rho_{2}}\left[\phi(\rho_{1}x_{1})\phi(\rho_{2}x_{2})-\phi(\rho_{1}y_{1})\phi(\rho_{2}x_{2})\right]+\mathbb{E}_{\rho_{1}\rho_{2}}\left[\phi(\rho_{1}y_{1})\phi(\rho_{2}x_{2})-\phi(\rho_{1}y_{1})\phi(\rho_{2}y_{2})\right]\right|$
$\displaystyle\leq\mathbb{E}_{\rho_{1}\rho_{2}}\left[\left|\phi(\rho_{1}x_{1})-\phi(\rho_{1}y_{1})\right|\left|\phi(\rho_{2}x_{2})\right|\right]+\mathbb{E}_{\rho_{1}\rho_{2}}\left[\left|\phi(\rho_{2}x_{2})-\phi(\rho_{2}y_{2})\right|\left|\phi(\rho_{1}y_{1})\right|\right]$
$\displaystyle\leq\mathbb{E}_{\rho_{1}\rho_{2}}\left[\left|M\rho_{1}(x_{1}-y_{1})\right|\left(\left|\phi(0)\right|+M\left|\rho_{2}x_{2}\right|\right)\right]+\mathbb{E}_{\rho_{1}\rho_{2}}\left[\left|M\rho_{2}(x_{2}-y_{2})\right|\left(\left|\phi(0)\right|+M\left|\rho_{1}y_{1}\right|\right)\right]$
$\displaystyle\leq
C_{1}\left|x_{1}-y_{1}\right|\mathbb{E}\left[|\rho_{1}|\right]+C_{2}\left|x_{2}\right|\left|x_{1}-y_{1}\right|\mathbb{E}\left[|\rho_{1}||\rho_{2}|\right]$
$\displaystyle\hskip
28.45274pt+C_{3}\left|x_{2}-y_{2}\right|\mathbb{E}\left[|\rho_{2}|\right]+C_{4}\left|y_{1}\right|\left|x_{2}-y_{2}\right|\mathbb{E}\left[|\rho_{1}||\rho_{2}|\right]$
$\displaystyle\leq
C_{1}\left|x_{1}-y_{1}\right|+C_{2}\left|x_{2}\right|\left|x_{1}-y_{1}\right|+C_{3}\left|x_{2}-y_{2}\right|+C_{4}\left|y_{1}\right|\left|x_{2}-y_{2}\right|,$

where in third inequality we use that $\phi$ is $M$-Lipschitz, and in the last
inequality we use that the quantities $\mathbb{E}\left[|\rho_{1}|\right]$,
$\mathbb{E}\left[|\rho_{2}|\right]$ and
$\mathbb{E}\left[|\rho_{1}||\rho_{2}|\right]$ are all smaller than $1$
(regardless of the correlation between $\rho_{1}$ and $\rho_{2}$). Since we
only used the fact that $\phi$ is $M$-Lipschitz, the same result holds with
$\phi^{\prime}$ in place of $\phi$.

∎

##  Appendix C Concentration of $\ell_{2}$ Norms

In this appendix, we state and prove a number of high-probability estimates on
the $\ell_{2}$ norms of feature and backpropagation vectors. More
specifically, our results can be summarized as follows:

  * •

Lemma C.1 gives tight bounds on $\left\|f_{l}(x)\right\|_{2}$, i.e. the
$\ell_{2}$ norm of the feature vector at layer $l$. The statement holds with
high probability over $x$ and $(W_{k})_{k=1}^{l}$.

  * •

Lemmas C.2 and C.3 give tight bounds on
$\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}^{2}\right]$ and
$\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}\right]$, respectively. These
quantities represent the _expectation_ with respect to $x$ of the (squared)
$\ell_{2}$ norm of the feature vector at layer $l$. The statements hold with
high probability over $(W_{k})_{k=1}^{l}$.

  * •

Lemma C.4 focuses on the _centered_ feature vector
$f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]$, and it gives tight bounds on
_(i)_ its expected (w.r.t. $x$) squared $\ell_{2}$ norm
$\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}^{2}\right]$,
_(ii)_ its expected (w.r.t. $x$) $\ell_{2}$ norm
$\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}\right]$,
and _(iii)_ its $\ell_{2}$ norm
$\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}$. The first
two statements hold with high probability over $(W_{k})_{k=1}^{l}$, and the
probability in the last statement is also over $x$.

  * •

Lemma C.5 focuses on the _centered_ backpropagation vector at layer $L-1$, and
it gives tight bounds on its $\ell_{2}$ norm
$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}$.
This statement holds with high probability over $x$ and $(W_{k})_{k=1}^{l}$.

Throughout this appendix, we always assume that $P_{X}$ satisfies Assumptions
1 and 2, and that the layer widths satisfy Assumption 4. Furthermore, we use
that the activation $\phi$ and its derivative $\phi^{\prime}$ are Lipschitz
(see Assumption 3).

######  Lemma C.1 ($\ell_{2}$ norm of features).

Let $x\sim P_{X}$. Then, for every $0\leq l\leq L-1$,

$\left\|f_{l}(x))\right\|_{2}=\Theta(\sqrt{n_{l}}),$ (C.1)

with probability at least $1-C\exp(-cn_{L-1})$ over $x$ and
$(W_{k})_{k=1}^{l}$. As usual, $\phi$ is applied component-wise on $g_{l}(x)$,
and $c$ and $C$ are numerical constants.

###### Proof.

We prove this by induction over $l$, and we start with the base case ($l=0$).
Recall that we have defined $f_{0}(x):=x$. As the $\ell_{2}$ norm is a
1-Lipschitz function, by Assumption 2, we have that

$\mathbb{P}\left(\left|\left\|x\right\|_{2}-\mathbb{E}[\left\|x\right\|_{2}]\right|>t\right)\leq
2e^{-ct^{2}}.$ (C.2)

Furthermore, Assumption 1 implies that
$\mathbb{E}[\left\|x\right\|_{2}]=\Theta(\sqrt{d})$, hence setting
$t=\mathbb{E}[\left\|x\right\|_{2}]/2$ in (C.2) proves the desired result for
the base case (recalling that $n_{L-1}=\mathcal{O}\left(d\right)$ by
Assumption 4).

By inductive hypothesis, we have

$\left\|f_{l-1}(x))\right\|_{2}=\Theta(\sqrt{n_{l-1}}),$ (C.3)

with probability at least $1-C\exp(-cn_{L-1})$.

Define $\tilde{c}:=\beta_{l}\left\|f_{l-1}(x)\right\|_{2}/\sqrt{n_{l-1}}$.
From now on, we condition on a realization of $x$ and $(W_{k})_{k=1}^{l-1}$
such that $\tilde{c}=\Theta(1)$. By (C.3), this happens with probability at
least $1-C\exp(-cn_{L-1})$.

To ease the notation, we use the shorthands $f:=f_{l-1}(x)$ and $W:=W_{l}$.
Then, we can write

$\displaystyle\left\|f_{l}(x)\right\|_{2}$
$\displaystyle=\left\|\phi(W^{\top}f)\right\|_{2}=\sqrt{n_{l}}\sqrt{\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}\phi^{2}((W^{\top})_{i:}f)}.$
(C.4)

Recall that $(W_{l})_{i,j}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta^{2}_{l}/n_{l-1})$ and that the Gaussian
distribution is rotationally invariant. Thus, the RHS of (C.4) has the same
distribution as

$\displaystyle\sqrt{n_{l}}\sqrt{\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}\phi^{2}\left(\tilde{c}\rho_{i}\right)}=\sqrt{n_{l}}\sqrt{\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}\rho_{1}\right)\right]+\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}Z_{i}},$
(C.5)

where $(\rho_{i})_{i=1}^{n_{l}}\sim_{\rm i.i.d.}\mathcal{N}(0,1)$ and also
independent of $f$, and we have defined the independent, mean-0 random
variables

$Z_{i}=\phi^{2}\left(\tilde{c}\rho_{i}\right)-\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}\rho_{1}\right)\right].$
(C.6)

Note that, in the definition of $Z_{i}$, the randomness comes only from
$\rho_{i}$, since we are conditioning on $\tilde{c}$.

We have that

$\left\|\phi\left(\tilde{c}\rho_{i}\right)\right\|_{\psi_{2}}\leq\left\|\phi\left(\tilde{c}\rho_{i}\right)-\mathbb{E}_{\rho_{i}}\left[\phi\left(\tilde{c}\rho_{i}\right)\right]\right\|_{\psi_{2}}+\left\|\mathbb{E}_{\rho_{i}}\left[\phi\left(\tilde{c}\rho_{i}\right)\right]\right\|_{\psi_{2}}\leq
C_{1}+C_{2}=C_{3},$ (C.7)

where the first term is bounded by a constant by Theorem 5.2.2 in [63], and
the bound on the second term follows from Lemma B.11. As a consequence, we
have

$\displaystyle\left\|Z_{i}\right\|_{\psi_{1}}=$
$\displaystyle\left\|\phi^{2}\left(\tilde{c}\rho_{i}\right)-\mathbb{E}_{\rho_{i}}\left[\phi^{2}\left(\tilde{c}\rho_{i}\right)\right]\right\|_{\psi_{1}}$
(C.8) $\displaystyle\leq$ $\displaystyle
C_{4}\left\|\phi^{2}\left(\tilde{c}\rho_{i}\right)\right\|_{\psi_{1}}$
$\displaystyle=$ $\displaystyle
C_{4}\left\|\phi\left(\tilde{c}\rho_{i}\right)\right\|_{\psi_{2}}^{2}$
$\displaystyle\leq$ $\displaystyle C_{5},$

where the inequality in the second line follows from Exercise 2.7.10 of [63],
the equality in the third line follows from Lemma 2.7.6 of [63], and the
inequality in the last line follows from (C.7). Hence, the $Z_{i}$-s are
i.i.d. sub-exponential random variables, with sub-exponential norm bounded by
a numerical constant. An application of Bernstein inequality (cf. Corollary
2.8.3. in [63]) gives that

$\mathbb{P}\left(\left|\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}Z_{i}\right|>t\right)\leq
2\exp\left(-c\mathop{\rm
min}\nolimits\left(\frac{t^{2}}{C_{6}^{2}},\frac{t}{C_{6}}\right)n_{l}\right),$
(C.9)

where $c,C_{6}$ are numerical constants. Furthermore, by Lemma B.12, we have

$\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}\rho_{1}\right)\right]=\Theta(1).$
(C.10)

By setting
$t=\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}\rho_{1}\right)\right]/2$
into (C.9) and using (C.5) and (C.10), we conclude that

$\left\|\phi(W^{\top}f)\right\|_{2}=\Theta(\sqrt{n_{l}}),$ (C.11)

with probability at least $1-C\exp(-cn_{L-1})-2\exp(-cn_{l})\geq
1-C_{1}\exp(-cn_{L-1})$, for some numerical constant $c$ and $C_{1}$, which
concludes the proof. ∎

######  Lemma C.2 (Expected squared $\ell_{2}$ norm of features).

Let $x\sim P_{X}$. Then, for every $0\leq l\leq L-1$,

$\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}^{2}\right]=\Theta(n_{l}),$
(C.12)

with probability at least $1-C\exp(-cn_{L-1})$ over $(W_{k})_{k=1}^{l}$. As
usual, $c$ and $C$ are numerical constants.

###### Proof.

The argument is by induction over $l$. The base case is a direct consequence
of Assumption 1, since $f_{0}(x)=x$.

By inductive hypothesis, we have

$\mathbb{E}_{x}\left[\left\|f_{l-1}(x))\right\|^{2}_{2}\right]=\Theta(n_{l-1}),$
(C.13)

with probability at least $1-C\exp(-cn_{L-1})$. Define
$\tilde{c}(x):=\beta_{l}\left\|f_{l-1}(x)\right\|_{2}/\sqrt{n_{l-1}}$. From
now on, we condition on a realization of $(W_{k})_{k=1}^{l-1}$ such that
$\mathbb{E}_{x}\left[\tilde{c}^{2}(x)\right]=\Theta(1)$. By (C.13), this
happens with probability at least $1-C\exp(-cn_{L-1})$.

To ease the notation, we use the shorthands $f:=f_{l-1}(x)$, $W:=W_{l}$ and
$w_{i}=W_{:i}$. Then, we can write

$\displaystyle\mathbb{E}_{x}\left[\left\|f_{l}(x))\right\|^{2}_{2}\right]$
$\displaystyle=\mathbb{E}_{x}\left[\left\|\phi(W^{\top}f)\right\|^{2}_{2}\right]$
(C.14)
$\displaystyle=n_{l}\left(\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}\mathbb{E}_{x}\left[\phi^{2}((W^{\top})_{i:}f)\right]\right)$
$\displaystyle=n_{l}\left(\mathbb{E}_{w_{1}}\mathbb{E}_{x}\left[\phi^{2}(w_{1}^{\top}f)\right]+\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}Z_{i}\right),$

where we use that the $w_{i}$-s are equally distributed and we have defined
the independent, mean-0 random variables

$Z_{i}=\mathbb{E}_{x}\left[\phi^{2}\left(w_{i}^{\top}f(x)\right)\right]-\mathbb{E}_{w_{i}}\mathbb{E}_{x}\left[\phi^{2}\left(w_{i}^{\top}f(x)\right)\right].$
(C.15)

Note that, in the definition of $Z_{i}$, the randomness comes only from
$w_{i}$, since we are conditioning on $(W_{k})_{k=1}^{l-1}$.

We have that

$\displaystyle\left\|Z_{i}\right\|_{\psi_{1}}\leq$
$\displaystyle\mathbb{E}_{x}\left[\left\|\phi^{2}\left(w_{i}^{\top}f(x)\right)-\mathbb{E}_{w_{i}}\left[\phi^{2}\left(w_{i}^{\top}f(x)\right)\right]\right\|_{\psi_{1}}\right]$
(C.16) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{x}\left[C_{1}\left\|\phi^{2}\left(w_{i}^{\top}f(x)\right)\right\|_{\psi_{1}}\right]$
$\displaystyle=$ $\displaystyle
C_{1}\mathbb{E}_{x}\left[\left\|\phi\left(w_{i}^{\top}f(x)\right)\right\|_{\psi_{2}}^{2}\right],$

where the first line follows from Jensen’s inequality as
$\left\|\cdot\right\|_{\psi_{1}}$ is convex, the inequality in the second line
follows from Exercise 2.7.10 of [63], and the equality in the third line
follows from Lemma 2.7.6 of [63].

Recall that $(W_{l})_{i,j}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta^{2}_{l}/n_{l-1})$ and that the Gaussian
distribution is rotationally invariant. Thus,
$\phi\left(w_{i}^{\top}f(x)\right)$ has the same distribution as
$\phi\left(\tilde{c}(x)\rho_{i}\right)$, where
$(\rho_{i})_{i=1}^{n_{l}}\sim_{\rm i.i.d.}\mathcal{N}(0,1)$ and also
independent of $\tilde{c}(x)$. We now condition on a realization of $x$ and
$(W_{k})_{k=1}^{l-1}$ and provide an upper bound on the sub-Gaussian norm
$\left\|\phi\left(w_{i}^{\top}f(x)\right)\right\|_{\psi_{2}}$, where the only
randomness comes again from $w_{i}$ (and, hence, from $\rho_{i}$). We have
that

$\displaystyle\left\|\phi\left(w_{i}^{\top}f(x)\right)\right\|_{\psi_{2}}$
$\displaystyle=\left\|\phi\left(\tilde{c}(x)\rho_{i}\right)\right\|_{\psi_{2}}$
(C.17)
$\displaystyle\leq\left\|\phi\left(\tilde{c}(x)\rho_{i}\right)-\mathbb{E}_{\rho_{i}}\left[\phi\left(\tilde{c}(x)\rho_{i}\right)\right]\right\|_{\psi_{2}}+\left\|\mathbb{E}_{\rho_{i}}\left[\phi\left(\tilde{c}(x)\rho_{i}\right)\right]\right\|_{\psi_{2}}$
$\displaystyle\leq
C_{1}\tilde{c}(x)+C_{2}\tilde{c}(x)+C_{3}=C_{4}(\tilde{c}(x)+1).$

where the first term in the RHS in the second line is bounded by
$C_{1}\tilde{c}(x)$ by Theorem 5.2.2 in [63], and the second term is bounded
by $C_{2}\tilde{c}(x)+C_{3}$ by following the same proof of Lemma B.11 as
$\phi$ is Lipschitz. By combining (C.16) and (C.17), we get

$\left\|Z_{i}\right\|_{\psi_{1}}\leq
C_{4}^{2}\mathbb{E}_{x}\left[(\tilde{c}(x)+1)^{2}\right]\leq C_{5},$ (C.18)

where we use that $\mathbb{E}_{x}\left[\tilde{c}^{2}(x)\right]=\Theta(1)$.

Hence, the $Z_{i}$-s are i.i.d. sub-exponential random variables, with sub-
exponential norm bounded by a numerical constant. An application of Bernstein
inequality (cf. Corollary 2.8.3. in [63]) gives that

$\mathbb{P}\left(\left|\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}Z_{i}\right|>t\right)\leq
2\exp\left(-c\mathop{\rm
min}\nolimits\left(\frac{t^{2}}{C_{5}^{2}},\frac{t}{C_{5}}\right)n_{l}\right),$
(C.19)

where $c,C_{5}$ are numerical constants.

Let us consider the first term in (C.14):

$\mathbb{E}_{x}\mathbb{E}_{w_{1}}\left[\phi^{2}(w_{1}^{\top}f)\right]=\mathbb{E}_{x}\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}(x)\rho_{1}\right)\right],$
(C.20)

where the equality comes again from the rotational invariance of the Gaussian
distribution of $w_{1}$. We will show that

$\mathbb{E}_{x}\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}(x)\rho_{1}\right)\right]=\Theta(1),$
(C.21)

with probability at least $1-C\exp(-cn_{L-1})$ over $(W_{k})_{k=1}^{l-1}$.

The upper bound in (C.21) follows from the same passages in (B.55), as
$\mathbb{E}_{x}[\tilde{c}^{2}(x)]=\Theta(1)$. We now prove the lower bound. By
Lemma C.1, we have that there exist numerical constants $c_{2}>c_{1}>0$ such
that $\tilde{c}(x)\in[c_{1},c_{2}]$ with probability at least
$1-C\exp(-cn_{L-1})$ over $x$ and $(W_{k})_{k=1}^{l-1}$. Hence, with
probability at least $1-2C\exp(-cn_{L-1})$ over $(W_{k})_{k=1}^{l-1}$, we have
that

$\mathbb{P}_{x}(\tilde{c}(x)\in[c_{1},c_{2}])\geq 1/2,$ (C.22)

where we use the symbol $\mathbb{P}_{x}$ to highlight that this last
probability is taken over $x$. Let us condition on a realization of
$(W_{k})_{k=1}^{l-1}$ s.t. (C.22) holds. Then, we have

$\mathbb{E}_{x}\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}(x)\rho_{1}\right)\right]\geq\frac{1}{2}\inf_{c\in[c_{1},c_{2}]}\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(c\rho_{1}\right)\right].$
(C.23)

By Lemma B.10, we have that
$\varphi(c)=\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(c\rho_{1}\right)\right]$
is continuous in $c$. Therefore, by Weierstrass theorem, there exists a
strictly positive $c^{*}\in[c_{1},c_{2}]$ such that
$\inf_{c\in[c_{1},c_{2}]}\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(c\rho_{1}\right)\right]=\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(c^{*}\rho_{1}\right)\right]$.
Thus,

$\mathbb{E}_{x}\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(\tilde{c}(x)\rho_{1}\right)\right]\geq\frac{1}{2}\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(c^{*}\rho_{1}\right)\right]=\Theta(1),$
(C.24)

where the last equality is a consequence of Lemma B.12. This concludes the
proof of the lower bound in (C.21).

By setting
$t=\mathbb{E}_{\rho_{1}}\left[\phi^{2}\left(c^{*}\rho_{1}\right)\right]/4$
into (C.19) and using (C.21) and (C.14), we conclude that

$\mathbb{E}_{x}\left[\left\|f_{l}(x))\right\|^{2}_{2}\right]=\Theta(n_{l}),$
(C.25)

with probability at least $1-C\exp(-cn_{L-1})$, for some numerical constants
$C$ and $c$, which concludes the proof. ∎

######  Lemma C.3 (Expected $\ell_{2}$ norm of features).

Let $x\sim P_{X}$. Then, for every $0\leq l\leq L-1$,

$\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}\right]=\Theta(\sqrt{n_{l}}),$
(C.26)

with probability at least $1-C\exp(-cn_{L-1})$ over $(W_{k})_{k=1}^{l}$. As
usual, $c$ and $C$ are numerical constants.

###### Proof.

We condition on the events

$\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}^{2}\right]=\Theta(n_{l}),$
(C.27)

and

$\left\|\left\|f_{l}(x)\right\|_{2}\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right),$
(C.28)

which happen with probability at least $1-C\exp(-cn_{L-1})$ over
$(W_{k})_{k=1}^{l}$ by Lemma C.2 and B.2.

The upper bound is a direct consequence of Jensen’s inequality:

$\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}\right]\leq\sqrt{\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}^{2}\right]}=\Theta(\sqrt{n_{l}}).$
(C.29)

For the lower bound, we use Lemma B.13, and we obtain

$\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}\right]\geq\sqrt{\mathbb{E}_{x}\left[\left\|f_{l}(x)\right\|_{2}^{2}\right]-c\left\|\left\|f_{l}(x)\right\|_{2}\right\|_{\mathrm{Lip}}^{2}}=\Theta(\sqrt{n_{l}}).$
(C.30)

∎

######  Lemma C.4 ($\ell_{2}$ norms of centered features).

Let $x\sim P_{X}$. Then, for every $0\leq l\leq L-1$, the following results
hold.

  1. 1.

With probability at least $1-C\exp(-cn_{L-1})$ over $(W_{k})_{k=1}^{l}$, we
have that

$\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}^{2}\right]=\Theta(n_{l}).$
(C.31)

  2. 2.

With probability at least $1-C\exp(-cn_{L-1})$ over $(W_{k})_{k=1}^{l}$, we
have that

$\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}\right]=\Theta(\sqrt{n_{l}}).$
(C.32)

  3. 3.

With probability at least $1-C\exp(-cn_{L-1})$ over $(W_{k})_{k=1}^{l}$ and
$x$, we have that

$\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}=\Theta(\sqrt{n_{l}}).$
(C.33)

###### Proof.

The argument is by induction over $l$. The base case for (C.31) follows
directly from Assumption 1, since $f_{0}(x)=x$. Since the $\ell_{2}$ norm is a
1-Lipschitz function, from Jensen inequality and Lemma B.13 we readily obtain
the base case for (C.32). Note that
$\left\|\left\|x-\mathbb{E}_{x}[x]\right\|_{2}\right\|_{\mathrm{Lip}}\leq 1$.
Then, the base case for (C.33) is a direct consequence of Assumption 2 on $x$
and of the base case of (C.32), and it holds with probability at least
$1-C^{\prime}\exp(-cd)\geq 1-C^{\prime}\exp(-cn_{L-1})$ over $x$.

By inductive hypothesis, we assume the three statements to be true for layer
$l-1$, for $l\in[L-1]$. We will now prove (C.31) for layer $l$.

To ease the notation, we use the shorthands $f(x):=f_{l-1}(x)$,
$f=\mathbb{E}_{x}[f(x)]$, $\tilde{f}(x)=f(x)-f$, $W:=W_{l}$ and
$w_{i}=W_{:i}$. We also define
$\tilde{c}(x)=\beta_{l}\left\|f(x)\right\|/\sqrt{n_{l-1}}$ and
$\tilde{c}=\mathbb{E}_{x}[\tilde{c}(x)]$.

We condition on the following events in the probability space of
$(W_{k})_{k=1}^{l-1}$:

  1. (a)

$\left\|f(x)\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right)$, which happens
with probability at least $1-C^{\prime}\exp(-cn_{L-1})$ by Lemma B.2.

  2. (b)

$\tilde{c}=\Theta(1)$, which happens with probability at least
$1-C^{\prime}\exp(-cn_{L-1})$ by Lemma C.3. Notice that by Jensen inequality
this also implies $\left\|f\right\|_{2}^{2}=\mathcal{O}\left(n_{l-1}\right)$.

  3. (c)

By inductive hypothesis, we have that, with probability at least
$1-C^{\prime}\exp(-cn_{n-1})$ over $x$ and $(W_{k})_{k=1}^{l-1}$,

$\left\|\tilde{f}(x)\right\|_{2}^{2}=\Theta(n_{l-1}).$ (C.34)

Hence, with probability at least $1-2C^{\prime}\exp(-cn_{n-1})$ over
$(W_{k})_{k=1}^{l-1}$, we have that

$\mathbb{P}_{x}\left(c_{1}n_{l-1}\leq\left\|\tilde{f}(x)\right\|_{2}^{2}\leq
c_{2}n_{l-1}\right)\geq 1/2,$ (C.35)

for some numerical constants $c_{2}>c_{1}>0$. In (C.35), we use the symbol
$\mathbb{P}_{x}$ to highlight that this last probability is taken over $x$.
For the rest of the argument, we condition on a realization of
$(W_{k})_{k=1}^{l-1}$ s.t. (C.35) holds.

By taking a union bound, the events (a)-(c) happen with probability at least
$1-4C^{\prime}\exp(-cn_{n-1})$ over $(W_{k})_{k=1}^{l-1}$.

Now, we can write

$\displaystyle\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}_{x}\left[\left\|\phi(W^{\top}f(x))-\mathbb{E}_{x}\left[\phi(W^{\top}f(x))\right]\right\|_{2}^{2}\right]$
(C.36)
$\displaystyle=n_{l}\left(\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}\mathbb{E}_{x}\left[\left(\phi((W^{\top})_{i:}f(x))-\mathbb{E}_{x}\left[\phi((W^{\top})_{i:}f(x))\right]\right)^{2}\right]\right)$
$\displaystyle=n_{l}\left(\mathbb{E}_{xw_{1}}\left[\left(\phi(w_{1}^{\top}f(x))-\mathbb{E}_{x}\left[\phi(w_{1}^{\top}f(x))\right]\right)^{2}\right]+\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}Z_{i}\right),$

where we use that the $w_{i}$-s are identically distributed and we have
defined the independent, mean-0 random variables

$Z_{i}=\mathbb{E}_{x}\left[\left(\phi(w_{i}^{\top}f(x))-\mathbb{E}_{x}\left[\phi(w_{i}^{\top}f(x))\right]\right)^{2}\right]-\mathbb{E}_{w_{1}x}\left[\left(\phi(w_{1}^{\top}f(x))-\mathbb{E}_{x}\left[\phi(w_{1}^{\top}f(x))\right]\right)^{2}\right].$
(C.37)

As in the proof of Lemma C.2, in the definition of $Z_{i}$, the randomness
comes only from $w_{i}$, since we are conditioning on $(W_{k})_{k=1}^{l-1}$.

We have that

$\displaystyle\left\|Z_{i}\right\|_{\psi_{1}}$ $\displaystyle\leq
C_{0}\left\|\mathbb{E}_{x}\left[\left(\phi(w_{i}^{\top}f(x))-\mathbb{E}_{x}\left[\phi(w_{i}^{\top}f(x))\right]\right)^{2}\right]\right\|_{\psi_{1}}$
(C.38) $\displaystyle\leq
C_{0}\mathbb{E}_{x}\left[\left\|\left(\phi(w_{i}^{\top}f(x))-\mathbb{E}_{x}\left[\phi(w_{i}^{\top}f(x))\right]\right)^{2}\right\|_{\psi_{1}}\right]$
$\displaystyle=C_{0}\mathbb{E}_{x}\left[\left\|\phi(w_{i}^{\top}f(x))-\mathbb{E}_{x}\left[\phi(w_{i}^{\top}f(x))\right]\right\|_{\psi_{2}}^{2}\right]$
$\displaystyle\leq
C_{0}\mathbb{E}_{x}\left[\left(\left\|\phi(w_{i}^{\top}f(x))\right\|_{\psi_{2}}+\left\|\mathbb{E}_{x}\left[\phi(w_{i}^{\top}f(x))\right]\right\|_{\psi_{2}}\right)^{2}\right]$
$\displaystyle\leq
C_{0}\mathbb{E}_{x}\left[\left(\left\|\phi(w_{i}^{\top}f(x))\right\|_{\psi_{2}}+\mathbb{E}_{x}\left[\left\|\phi(w_{i}^{\top}f(x))\right\|_{\psi_{2}}\right]\right)^{2}\right],$

where $C_{0}$ is a numerical constant, the first inequality follows from
Exercise 2.7.10 of [63], the second line follows from Jensen’s inequality as
$\left\|\cdot\right\|_{\psi_{1}}$ is convex, the equality follows from Lemma
2.7.6 of [63], and the last line follows from Jensen’s inequality as
$\left\|\cdot\right\|_{\psi_{2}}$ is convex.

Recall that $(W)_{i,j}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta^{2}_{l}/n_{L-1})$ and that the Gaussian
distribution is rotationally invariant. Thus,
$\phi^{\prime}\left(w_{i}^{\top}f(x)\right)$ has the same distribution as
$\phi^{\prime}\left(\tilde{c}(x)\rho_{i}\right)$, where
$(\rho_{i})_{i=1}^{n_{L-1}}\sim_{\rm i.i.d.}\mathcal{N}(0,1)$ and also
independent of $\tilde{c}(x)$. Therefore,

$\displaystyle\left\|\phi\left(w_{i}^{\top}f(x)\right)\right\|_{\psi_{2}}$
$\displaystyle=\left\|\phi\left(\tilde{c}(x)\rho_{i}\right)\right\|_{\psi_{2}}$
(C.39)
$\displaystyle\leq\left\|\phi\left(\tilde{c}(x)\rho_{i}\right)-\mathbb{E}_{\rho_{i}}\left[\phi\left(\tilde{c}(x)\rho_{i}\right)\right]\right\|_{\psi_{2}}+\left\|\mathbb{E}_{\rho_{i}}\left[\phi\left(\tilde{c}(x)\rho_{i}\right)\right]\right\|_{\psi_{2}}$
$\displaystyle\leq C_{1}\tilde{c}(x)+C_{2}\tilde{c}(x)+C_{3}\leq
C_{4}(\tilde{c}(x)+1),$

where the first term in the RHS in the second line is bounded by
$C_{1}\tilde{c}(x)$ for Theorem 5.2.2 in [63], and the second term is bounded
by $C_{2}\tilde{c}(x)+C_{3}$ by following the same proof of Lemma B.11.

Merging together (C.39) and (C.38) we get

$\displaystyle\left\|Z_{i}\right\|_{\psi_{1}}\leq$ $\displaystyle
C_{0}\mathbb{E}_{x}\left[\left(C_{4}\tilde{c}(x)+C_{4}\tilde{c}+C_{5}\right)^{2}\right]$
(C.40) $\displaystyle=$ $\displaystyle
C_{6}\mathbb{E}_{x}[(\tilde{c}(x)-\tilde{c})^{2}]+C_{4}\tilde{c}^{2}+C_{7}\tilde{c}+C_{8}$
$\displaystyle=$ $\displaystyle
C_{6}\mathcal{O}\left(n_{l}^{-1}\right)+C_{4}\tilde{c}^{2}+C_{7}\tilde{c}+C_{8}$
$\displaystyle\leq$ $\displaystyle C_{9},$

where in the third line we use Lemma B.14.

Hence, the $Z_{i}$-s are i.i.d. sub-exponential random variables, with sub-
exponential norm bounded by a numerical constant. An application of Bernstein
inequality (cf. Corollary 2.8.3. in [63]) gives that

$\mathbb{P}\left(\left|\frac{1}{n_{l}}\sum_{i=1}^{n_{l}}Z_{i}\right|>t\right)\leq
2\exp\left(-c\mathop{\rm
min}\nolimits\left(\frac{t^{2}}{C^{2}},\frac{t}{C}\right)n_{l}\right),$ (C.41)

where $c,C$ are numerical constants. We recall that this probability is
intended over $W_{l}$.

Let’s now focus on the first term in the last line of (C.36), using the
shorthand $w=w_{1}$, to ease the notation. We can rewrite this term as

$\displaystyle\mathbb{E}_{w}\left[\mathbb{E}_{x}\left[\phi^{2}(w^{\top}f(x))\right]-\mathbb{E}_{xy}\left[\phi(w^{\top}f(x))\phi(w^{\top}f(y))\right]\right]$
(C.42) $\displaystyle\hskip
28.45274pt=\mathbb{E}_{x}\mathbb{E}_{w}\left[\phi^{2}(w^{\top}f(x))\right]-\mathbb{E}_{xy}\mathbb{E}_{w}\left[\phi(w^{\top}f(x))\phi(w^{\top}f(y))\right].$

The aim of this part of the proof is to show that the quantity in (C.42) is
$\Theta(1)$.

Recall that $(W_{l})_{i,j}\mathbin{\overset{}{\sim}}_{\rm
i.i.d.}\mathcal{N}(0,\beta^{2}_{l}/n_{l-1})$ and that the Gaussian
distribution is rotationally invariant. Thus, $\phi\left(w^{\top}f(x)\right)$
has the same distribution as $\phi\left(\tilde{c}(x)\rho\right)$, where
$\rho\sim\mathcal{N}(0,1)$ is independent of $\tilde{c}(x)$. We therefore have

$\displaystyle\left|\mathbb{E}_{x}\mathbb{E}_{w}\left[\phi^{2}\left(w^{\top}f(x)\right)-\phi^{2}\left(w^{\top}f(x)\frac{\tilde{c}}{\tilde{c}(x)}\right)\right]\right|$
(C.43)
$\displaystyle=\left|\mathbb{E}_{x}\mathbb{E}_{\rho}\left[\phi^{2}(\rho\tilde{c}(x))-\phi^{2}(\rho\tilde{c})\right]\right|$
$\displaystyle\leq\mathbb{E}_{x}\left[C_{1}|\tilde{c}-\tilde{c}(x)|+C_{2}\left|\tilde{c}^{2}-\tilde{c}(x)^{2}\right|\right]$
$\displaystyle\leq\mathbb{E}_{x}\left[C_{1}|\tilde{c}-\tilde{c}(x)|+C_{2}(\tilde{c}-\tilde{c}(x))^{2}+2C_{2}\tilde{c}\left|\tilde{c}-\tilde{c}(x)\right|\right]$
$\displaystyle=\mathcal{O}\left(n_{l-1}^{-1/2}\right),$

where the third line follows from Lemma B.10, and the last passage follows
from Lemma B.14. Similarly, we have

$\displaystyle\left|\mathbb{E}_{xy}\mathbb{E}_{w}\left[\phi(w^{\top}f(x))\phi(w^{\top}f(y))-\phi\left(w^{\top}f(x)\frac{\tilde{c}}{\tilde{c}(x)}\right)\phi\left(w^{\top}f(y)\frac{\tilde{c}}{\tilde{c}(y)}\right)\right]\right|$
(C.44)
$\displaystyle=\left|\mathbb{E}_{xy}\mathbb{E}_{\rho_{1}\rho_{2}}\left[\phi(\rho_{1}\tilde{c}(x))\phi(\rho_{2}\tilde{c}(y))-\phi(\rho_{1}\tilde{c})\phi(\rho_{2}\tilde{c})\right]\right|$
$\displaystyle\leq\mathbb{E}_{xy}\left[C_{1}\left|\tilde{c}(x)-\tilde{c}\right|+C_{2}\tilde{c}(y)\left|\tilde{c}(x)-\tilde{c}\right|+C_{3}\left|\tilde{c}(y)-\tilde{c}\right|+C_{4}\tilde{c}\left|\tilde{c}(y)-\tilde{c}\right|\right]$
$\displaystyle=\mathcal{O}\left(n_{l-1}^{-1/2}\right),$

where $\rho_{1}$ and $\rho_{2}$ indicate two standard Gaussian random
variables with correlation
$f(x)^{\top}f(y)/(\left\|f(x)\right\|\left\|f(y)\right\|)$, the third line
follows from B.15, and the last passage follows from Lemma B.14. By combining
(C.43) and (C.44), we have that

$\displaystyle\left|\mathbb{E}_{w}\left[\mathbb{E}_{x}\left[\phi^{2}(w^{\top}f(x))\right]-\mathbb{E}_{xy}\left[\phi(w^{\top}f(x))\phi(w^{\top}f(y))\right]\right]-\xi\right|=\mathcal{O}\left(n_{l-1}^{-1/2}\right),$
(C.45)

with

$\begin{split}\xi:=&\mathbb{E}_{x}\mathbb{E}_{w}\left[\phi^{2}\left(w^{\top}f(x)\frac{\tilde{c}}{\tilde{c}(x)}\right)\right]-\mathbb{E}_{xy}\mathbb{E}_{w}\left[\phi\left(w^{\top}f(x)\frac{\tilde{c}}{\tilde{c}(x)}\right)\phi\left(w^{\top}f(y)\frac{\tilde{c}}{\tilde{c}(y)}\right)\right]\\\
=&\mathbb{E}_{\rho_{1}}\left[\tilde{\phi}^{2}(\rho_{1})\right]-\mathbb{E}_{xy}\left[\mathbb{E}_{\rho_{1}\rho_{2}}\left[\tilde{\phi}(\rho_{1})\tilde{\phi}(\rho_{2})\right]\right],\end{split}$
(C.46)

where we have set $\tilde{\phi}(t)=\phi(\tilde{c}t)$. Hence, in order to
obtain that the quantity in (C.42) is $\Theta(1)$, it suffices to prove that
$\xi=\Theta(1)$.

As $\phi$ is Lipschitz and $\tilde{c}$ is $\Theta(1)$, $\tilde{\phi}$ is also
Lipschitz, which readily implies that $\xi=\mathcal{O}\left(1\right)$. We now
prove that $\xi=\Omega(1)$. By exploiting the Hermite expansion of
$\tilde{\phi}$, we have that

$\xi=\sum_{i=0}^{\infty}\mu^{2}_{i}\left(1-\mathbb{E}_{xy}\left[\left(\frac{f(x)^{\top}f(y)}{\left\|f(x)\right\|\left\|f(y)\right\|}\right)^{i}\right]\right),$
(C.47)

where $\mu_{i}$ is the $i$-th Hermite coefficient of $\tilde{\phi}$. Note
that, since we conditioned on $\tilde{c}=\Theta(1)$, these coefficients are
numerical constants. As $\phi$ (and therefore $\tilde{\phi}$) is non constant,
there exist $j>0$ such that $\mu_{j}\neq 0$. Furthermore, we have that the sum
in (C.47) contains only positive terms, as
$|f(x)^{\top}f(y)|\leq\left\|f(x)\right\|\cdot\left\|f(y)\right\|$ by Cauchy-
Schwarz. Therefore, in order to show that $\xi=\Omega(1)$, it suffices to
prove that, for all $j>0$,

$\mathbb{E}_{xy}\left[\left(\frac{\left|f(x)^{\top}f(y)\right|}{\left\|f(x)\right\|\left\|f(y)\right\|}\right)^{j}\right]\leq
C_{0}<1,$ (C.48)

where $C_{0}$ is an absolute constant strictly smaller than $1$. Furthermore,
(C.48) is implied by the following:

$\mathbb{P}_{xy}\left(\frac{\left|f(x)^{\top}f(y)\right|}{\left\|f(x)\right\|\left\|f(y)\right\|}\leq
C_{1}\right)\geq c_{1},$ (C.49)

where $C_{1}<1$ and $c_{1}>0$ are numerical constants.

By writing $f(x)$ as $\tilde{f}(x)+f$ and $f(y)$ as $\tilde{f}(y)+f$, we have

$\displaystyle\frac{\left|f(x)^{\top}f(y)\right|}{\left\|f(x)\right\|\left\|f(y)\right\|}$
$\displaystyle=\frac{\left|(\tilde{f}(x)+f)^{\top}(\tilde{f}(y)+f)\right|}{\left\|\tilde{f}(x)+f\right\|\left\|\tilde{f}(y)+f\right\|}$
(C.50)
$\displaystyle\leq\frac{\left|\tilde{f}(x)^{\top}(\tilde{f}(y)+f)\right|+\left|f^{\top}\tilde{f}(y)\right|+\left\|f\right\|^{2}}{\mathop{\rm
min}\nolimits_{z\in\\{x,y\\}}\left\|\tilde{f}(z)+f\right\|^{2}}$
$\displaystyle\leq\frac{\left|\tilde{f}(x)^{\top}f(y)\right|+\left|f^{\top}\tilde{f}(y)\right|+\left\|f\right\|^{2}}{\mathop{\rm
min}\nolimits_{z\in\\{x,y\\}}\left(\left\|\tilde{f}(z)\right\|^{2}-2\left|f^{\top}\tilde{f}(z)\right|\right)+\left\|f\right\|^{2}}.$

Let us provide bounds on the various terms appearing in (C.50):

  * (i)

Part (d) of the conditioning (cf. (C.35)) gives that

$\mathbb{P}_{xy}\left(\mathop{\rm
min}\nolimits_{z\in\\{x,y\\}}\left\|\tilde{f}(z)\right\|_{2}^{2}\geq
cn_{l-1}\right)\geq\frac{1}{4},$ (C.51)

for some numerical constant $c>0$.

  * (ii)

Part (b) of the conditioning gives that

$\left\|f\right\|_{2}^{2}\leq C^{\prime}n_{l-1}.$ (C.52)

  * (iii)

Part (a) of the conditioning gives that
$\left\|f_{l-1}(x)\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right)$, and part
(b) of the conditioning gives that
$\mathbb{E}_{y}\left[\left\|f_{l-1}(y)\right\|\right]=\Theta(\sqrt{n_{l-1}})$.
Hence, as $y\sim P_{X}$, Assumption 2 implies that

$\left\|f_{l-1}(y)\right\|=\Theta(\sqrt{n_{l-1}}),$ (C.53)

with probability at least $1-2\exp(-cn_{l-1})$ over $y$, where $c$ is a
numerical constant. Furthermore, by recalling that
$\mathbb{E}_{x}[\tilde{f}(x)]=0$ and using again Assumption 2, we have that,
for any fixed vector $u$,

$\mathbb{P}_{x}(|\tilde{f}(x)^{\top}u|>t)\leq
2e^{-c_{0}t^{2}/\left\|u\right\|_{2}^{2}},$ (C.54)

where $c_{0}$ is another numerical constant. Since $x$ and $y$ are
independent, (C.54) implies that

$\mathbb{P}_{x}(|\tilde{f}(x)^{\top}f(y)|>n_{l-1}^{3/4})\leq
2e^{-c_{0}n_{l-1}^{3/2}/\left\|f(y)\right\|_{2}^{2}}\leq
2e^{-c_{2}n_{l-1}^{1/2}},$ (C.55)

where the first inequality holds for every $y$, and the second inequality
holds with probability at least $1-2\exp(-cn_{l-1})$ over $y$ by (C.53). As a
result, we have

$\mathbb{P}_{xy}(|\tilde{f}(x)^{\top}f(y)|>n_{l-1}^{3/4})\leq
2e^{-c_{2}\sqrt{n_{l-1}}}+2e^{-cn_{l-1}}\leq 4e^{-c_{3}\sqrt{n_{l-1}}}.$
(C.56)

  * (iv)

By setting $t=n_{l-1}^{3/4}$ and $u=f$ into (C.54), we obtain

$\mathbb{P}_{y}(|\tilde{f}(y)^{\top}f|>n_{l-1}^{3/4})\leq
2e^{-c_{4}\sqrt{n_{l-1}}},$ (C.57)

where $c_{4}$ is a numerical constant and we have also used (C.52).

  * (v)

Finally, as $x$ and $y$ are independent, (C.57) implies that

$\mathbb{P}_{xy}(\mathop{\rm
max}\nolimits_{z\in\\{x,y\\}}|\tilde{f}(z)^{\top}f|>n_{l-1}^{3/4})\leq
4e^{-c_{4}\sqrt{n_{l-1}}}.$ (C.58)

By plugging into (C.50) the bounds (C.51), (C.56), (C.57) and (C.58), we
obtain that

$\mathbb{P}_{x,y}\left(\frac{\left|f(x)^{\top}f(y)\right|}{\left\|f(x)\right\|\left\|f(y)\right\|}\leq\frac{2n_{l-1}^{3/4}+\left\|f\right\|_{2}^{2}}{c\,n_{l-1}-2n_{l-1}^{3/4}+\left\|f\right\|_{2}^{2}}\right)\geq
1/4-10e^{-c_{5}\sqrt{n_{l-1}}}.$ (C.59)

By using also (C.52), we have that (C.49) readily follows from (C.59). From
(C.49), we have that $\xi=\Theta(1)$. Hence, the quantity in (C.42) is
$\Theta(1)$ and in particular it is lower bounded by a numerical constant,
call it $C_{0}$.

By setting $t=C_{0}/2$ in (C.41), we conclude that

$\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}\left[f_{l}(x)\right]\right\|_{2}^{2}\right]=\Theta(n_{l}),$
(C.60)

with probability at least $1-2\exp(-cn_{l-1})$ over $W_{l}$, where $c$ is an
absolute constant. By taking into account the conditioning made at the
beginning of the proof over the space $(W_{k})_{k=1}^{l-1}$, we obtain that
(C.60) holds with probability at least
$1-5C^{\prime}\exp(-cn_{n-1})-2\exp(-cn_{n-1})\geq 1-C\exp(-cn_{n-1})$ over
$(W_{k})_{k=1}^{l}$, where $C$ is a numerical constant, which concludes the
proof of (C.31).

Finally, we prove (C.32) and (C.33), again for layer $l$. By Lemma B.2, we
have that $\left\|f_{l}(x)\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right)$,
with probability at least $1-C^{\prime}\exp(-cn_{L-1})$ over
$(W_{k})_{k=1}^{l}$. By conditioning on this event, we also have that
$\left\|\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right)$.
Furthermore, we condition on a realization of $(W_{k})_{k=1}^{l}$ such that
(C.31) holds.

To obtain (C.32), we apply Jensen’s inequality and Lemma B.13, which give that

$\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}\right]=\Theta(\sqrt{n_{l}}),$
(C.61)

with probability at least
$1-C^{\prime}\exp(-cn_{L-1})-5C^{\prime}\exp(-cn_{n-1})-2\exp(-cn_{n-1})\geq
1-C\exp(-cn_{n-1})$ over $(W_{k})_{k=1}^{l}$.

To obtain (C.33), we condition on a realization of $(W_{k})_{k=1}^{l}$ such
that
$\left\|\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right)$
and (C.32) holds. Then, by Assumption 2, we have that

$\displaystyle\mathbb{P}_{x}\left(\left|\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}-\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}\right]\right|>\mathbb{E}_{x}\left[\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|_{2}\right]/2\right)$
(C.62) $\displaystyle\hskip 28.45274pt\leq 2\exp(-c_{1}n_{l})\leq
2\exp(-cn_{L-1}),$

where $c$ is a numerical constant. This gives that

$\left\|f_{l}(x)-\mathbb{E}_{x}[f_{l}(x)]\right\|=\Theta(\sqrt{n_{l}}),$
(C.63)

with probability at least
$1-6C^{\prime}\exp(-cn_{n-1})-2\exp(-cn_{n-1})-2\exp(-cn_{n-1})\geq
1-C\exp(-cn_{n-1})$ over $x$ and $(W_{k})_{k=1}^{l}$, which concludes the
proof. ∎

######  Lemma C.5 ($\ell_{2}$ norms of centered backpropagation).

Let $x\sim P_{X}$. Then, we have

$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}=\Theta(\sqrt{n_{L-1}}),$
(C.64)

with probability at least $1-10\exp(-c\log^{2}n_{L-1})-C\exp(-cn_{L-1})$ over
$x$ and $(W_{k})_{k=1}^{L}$ over $(W_{k})_{k=1}^{l}$ and $x$.

###### Proof.

An application of Lemma C.4 for $l=L-2$ gives that

$\left\|f_{L-2}(x)-\mathbb{E}_{x}\left[f_{L-2}(x)\right]\right\|_{2}=\Theta(\sqrt{n_{L-2}}).$
(C.65)

with probability at least $1-C^{\prime}\exp(-cn_{L-1})$ over
$(W_{k})_{k=1}^{L-2}$ and $x$.

To ease the notation, we use the shorthands $f(x):=f_{L-2}(x)$,
$f=\mathbb{E}_{x}[f(x)]$, $\tilde{f}(x)=f(x)-f$, $W:=W_{L-1}$ and
$w_{i}=W_{:i}$. We also define
$\tilde{c}(x)=\beta_{l}\left\|f(x)\right\|/\sqrt{n_{l-1}}$ and
$\tilde{c}=\mathbb{E}_{x}[\tilde{c}(x)]$.

As in Lemma C.4, we condition on the 3 events (a)-(c), which jointly happen
with probability at least $1-4C^{\prime}\exp(-cn_{L-1})$ over
$(W_{k})_{k=1}^{L-2}$. Note that, to condition on the event (c), we use
(C.65).

Now, we can write

$\displaystyle\mathbb{E}_{x}\left[\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}^{2}\right]$
(C.66)
$\displaystyle=\mathbb{E}_{x}\left[\left\|D_{L}\phi^{\prime}(W^{\top}f_{L-2}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(W^{\top}f_{L-2}(x))\right]\right\|_{2}^{2}\right]$
$\displaystyle=n_{L-1}\left(\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}(D_{L})_{ii}^{2}\mathbb{E}_{x}\left[\left(\phi^{\prime}(w_{i}^{\top}f(x))-\mathbb{E}_{x}\left[\phi^{\prime}(w_{i}^{\top}f(x))\right]\right)^{2}\right]\right)$
$\displaystyle=n_{L-1}\left(\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}(D_{L})_{ii}^{2}\mathbb{E}_{xw_{1}}\left[\left(\phi^{\prime}(w_{1}^{\top}f(x))-\mathbb{E}_{x}\left[\phi^{\prime}(w_{1}^{\top}f(x))\right]\right)^{2}\right]+\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}Z_{i}\right),$

where we use that the $w_{i}$-s are identically distributed and we have
defined the independent, mean-0 random variables

$\displaystyle Z_{i}=$
$\displaystyle(D_{L})_{ii}^{2}\mathbb{E}_{x}\left[\left(\phi^{\prime}(w_{i}^{\top}f(x))-\mathbb{E}_{x}\left[\phi^{\prime}(w_{i}^{\top}f(x))\right]\right)^{2}\right]$
(C.67)
$\displaystyle-(D_{L})_{ii}^{2}\mathbb{E}_{w_{1}x}\left[\left(\phi^{\prime}(w_{1}^{\top}f(x))-\mathbb{E}_{x}\left[\phi^{\prime}(w_{1}^{\top}f(x))\right]\right)^{2}\right].$

Note that in the definition of $Z_{i}$ the randomness comes only from $w_{i}$
and $(D_{L})_{ii}$, since we are conditioning on $(W_{k})_{k=1}^{L-2}$.

If we fix the $(D_{L})_{ii}$-s and follow the same argument in (C.38)-(C.40)
(cf. the proof of Lemma C.4), we have

$\left\|Z_{i}\right\|_{\psi_{1}}\leq C_{0}(D_{L})_{ii}^{2},$ (C.68)

where $C_{0}$ is a numerical constant and we have used that $\phi^{\prime}$ is
Lipschitz. Let $\mathcal{E}_{\rm bad}$ be the event s.t. $\mathop{\rm
max}\nolimits_{i}(D_{L})_{ii}^{2}>\log^{2}n_{L-1}$. Then, by following the
same argument as in Lemma B.3, we have that

$\mathbb{P}(\mathcal{E}_{\rm bad})\leq 2\exp(-c\log^{2}n_{L-1}).$ (C.69)

Hence, by conditioning on $\mathcal{E}_{\rm bad}^{c}$, we have that

$\mathop{\rm max}\nolimits_{i}\left\|Z_{i}\right\|_{\psi_{1}}\leq
C_{0}\log^{2}n_{L-1}.$ (C.70)

By applying Bernstein inequality (cf. Corollary 2.8.3. in [63]), we get

$\mathbb{P}\left(\left|\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}Z_{i}\right|>\frac{1}{\sqrt[4]{n_{L-1}}}\,\Bigg{|}\,\mathcal{E}_{\rm
bad}^{c}\right)\leq
2\exp\left(-c\frac{\sqrt{n_{L-1}}}{\log^{4}n_{L-1}}\right),$ (C.71)

for some numerical constant $c$. By combining (C.69) and (C.71), we obtain
that

$\begin{split}\mathbb{P}\left(\left|\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}Z_{i}\right|>\frac{1}{\sqrt[4]{n_{L-1}}}\right)&\leq
2\exp\left(-c\frac{\sqrt{n_{L-1}}}{\log^{4}n_{L-1}}\right)+2\exp\left(-c\log^{2}n_{L-1}\right)\\\
&\leq 4\exp\left(-c\log^{2}n_{L-1}\right),\end{split}$ (C.72)

where this probability is over $W_{L-1}$ and $W_{L}$.

Let’s now focus on the first term in the last line of (C.66). In particular,
we have that

$\xi=\mathbb{E}_{xw_{1}}\left[\left(\phi^{\prime}(w_{1}^{\top}f(x))-\mathbb{E}_{x}\left[\phi^{\prime}(w_{1}^{\top}f(x))\right]\right)^{2}\right]=\Theta(1).$
(C.73)

This can be proven by following the same argument in (C.43)-(C.59) (cf. the
proof of Lemma C.4), as $\phi^{\prime}$ is Lipschitz and non-constant.

Next, we re-write (C.66) as

$\displaystyle\mathbb{E}_{x}\left[\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}^{2}\right]$
(C.74)
$\displaystyle=n_{L-1}\left(\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}(D_{L})_{ii}^{2}\mathbb{E}_{xw_{1}}\left[\left(\phi^{\prime}(w_{1}^{\top}f(x))-\mathbb{E}_{x}\left[\phi^{\prime}(w_{1}^{\top}f(x))\right]\right)^{2}\right]+\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}Z_{i}\right)$
$\displaystyle=n_{L-1}\left(\xi\mathbb{E}_{W_{L}}\left[(D_{L})_{11}^{2}\right]+\xi\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}\tilde{Z}_{i}+\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}Z_{i}\right)$
$\displaystyle=n_{L-1}\left(\xi\beta_{L}^{2}+\xi\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}\tilde{Z}_{i}+\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}Z_{i}\right),$

where we have defined the independent, mean-0, sub-exponential random
variables

$\tilde{Z}_{i}=(D_{L})_{ii}^{2}-\mathbb{E}_{W_{L}}\left[(D_{L})_{11}^{2}\right].$
(C.75)

Since the $(D_{L})_{ii}$-s are standard Gaussian, we have

$\left\|\tilde{Z}_{i}\right\|_{\psi_{1}}\leq\left\|(D_{L})_{ii}^{2}\right\|_{\psi_{1}}=\left\|(D_{L})_{ii}\right\|_{\psi_{2}}^{2}=C_{1}.$
(C.76)

Hence, another application of Bernstein inequality (cf. Corollary 2.8.3. in
[63]) allows us to conclude that

$\left|\frac{1}{n_{L-1}}\sum_{i=1}^{n_{L-1}}\tilde{Z}_{i}\right|=\mathcal{O}\left(n_{L-1}^{-1/4}\right),$
(C.77)

with probability at least $1-2\exp(-c\sqrt{n_{L-1}})$ over $W_{L}$.

Thus, by using (C.72) and (C.77), and taking into account the initial
conditioning over $(W_{k})_{k=1}^{L-2}$, we conclude that

$\mathbb{E}_{x}\left[\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}^{2}\right]=\Theta(n_{L-1}),$
(C.78)

with probability at least
$1-6\exp(-c\log^{2}n_{L-1})-6C^{\prime}\exp(-cn_{L-1})$ over
$(W_{k})_{k=1}^{L}$.

Proceeding in a similar fashion as in Lemma C.4, we apply Lemma B.4, which
gives that
$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))\right\|_{\mathrm{Lip}}=\mathcal{O}\left(\log
n_{L-1}\right)$, with probability at least
$1-2\exp(-c\log^{2}n_{L-1})-C^{\prime}\exp{(-n_{L-1})}$ over
$(W_{k})_{k=1}^{L}$. By conditioning on this event, we also have that
$\left\|\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}\right\|_{\mathrm{Lip}}=\mathcal{O}\left(\log
n_{L-1}\right)$. Furthermore, we condition on a realization of
$(W_{k})_{k=1}^{L}$ such that (C.78) holds.

We can now apply Jensen’s inequality and Lemma B.13, to obtain that

$\mathbb{E}_{x}\left[\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}\right]=\Theta(\sqrt{n_{l}}),$
(C.79)

with probability at least
$1-8\exp(-c\log^{2}n_{L-1})-7C^{\prime}\exp(-cn_{L-1})$ over
$(W_{k})_{k=1}^{L}$.

Finally, we condition on a realization of $(W_{k})_{k=1}^{L}$ such that
$\left\|\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}\right\|_{\mathrm{Lip}}=\mathcal{O}\left(\log
n_{L-1}\right)$ and (C.79) hold. Then, by Assumption 2, we have that

$\displaystyle\mathbb{P}_{x}\big{(}\left|\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}-\mathbb{E}_{x}\left[\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}\right]\right|$
(C.80) $\displaystyle\hskip
142.26378pt>\mathbb{E}_{x}\left[\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}\right]/2\big{)}$
$\displaystyle\hskip 284.52756pt\leq 2\exp^{(}-cn_{L-1}).$

This gives that

$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))-\mathbb{E}_{x}\left[D_{L}\phi^{\prime}(g_{L-1}(x))\right]\right\|_{2}=\Theta(\sqrt{n_{L-1}}),$
(C.81)

with probability at least
$1-10\exp(-c\log^{2}n_{L-1})-8C^{\prime}\exp(-cn_{L-1})$ over $x$ and
$(W_{k})_{k=1}^{L}$. This concludes the proof. ∎

##  Appendix D Proofs for Part 1: Centering

###  D.1 Step (a): Centering $F_{L-2}$ and $B_{L-1}$

######  Lemma D.1 (Centering $F_{L-2}$ and $B_{L-1}$).

Consider the setting of Theorem 1, let $F_{L-2}\in\mathbb{R}^{N\times
n_{L-2}}$ be the feature matrix at layer $L-2$, and let $B_{L-1}$ contain the
backpropagation terms from layer $L-1$, i.e.
$(B_{L-1})_{i:}=D_{L}\phi^{\prime}(g_{L-1}(x_{i}))$. Let
$J_{L-2}J_{L-2}^{\top}=F_{L-2}F_{L-2}^{\top}\circ B_{L-1}B_{L-1}^{\top}$ and
$\tilde{J}_{FB}\tilde{J}_{FB}^{\top}=\tilde{F}_{L-2}\tilde{F}_{L-2}^{\top}\circ\tilde{B}_{L-1}\tilde{B}_{L-1}^{\top}$,
where $\tilde{F}_{L-2}=F_{L-2}-\mathbb{E}_{X}[F_{L-2}]$ and
$\tilde{B}_{L-1}=B_{L-1}-\mathbb{E}_{X}[B_{L-1}]$. Then, we have that

$\lambda_{\rm min}\left(J_{L-2}J_{L-2}^{\top}\right)\geq\lambda_{\rm
min}\left(\tilde{J}_{FB}\tilde{J}_{FB}^{\top}\right)-o(n_{L-1}n_{L-2}),$ (D.1)

with probability at least
$1-C\exp(-cn_{L-1})-4\exp(-c\log^{2}N)-8\exp(-c\log^{2}n_{L-1})$ over
$(W_{k})_{k=1}^{L}$ and $(x_{i})_{i=1}^{N}\sim_{\rm i.i.d.}P_{X}$, where $c$
and $C$ are numerical constants.

###### Proof.

By Lemma B.2 and Lemma B.4, we have that
$\left\|f_{L-2}\right\|_{\mathrm{Lip}}=\mathcal{O}\left(1\right)$ and
$\left\|D_{L}\phi^{\prime}(g_{L-1}(x))\right\|_{\mathrm{Lip}}=\mathcal{O}\left(\log
n_{L-1}\right)$ with probability $1-C\exp(-n_{L-1})-2\exp(-c\log^{2}n_{L-1})$
over $(W_{k})_{k=1}^{L}$. We will condition on these events for the rest of
the proof.

Let’s define
$\tilde{J}_{F}\tilde{J}_{F}^{\top}=\tilde{F}_{L-2}\tilde{F}_{L-2}^{\top}\circ
B_{L-1}B_{L-1}^{\top}$. We can now re-write the quantity
$J_{L-2}J_{L-2}^{\top}$ as follows:

$\displaystyle J_{L-2}J_{L-2}^{\top}$
$\displaystyle=\tilde{J}_{F}\tilde{J}_{F}^{\top}+\mathbb{E}[F_{L-2}]\mathbb{E}[F_{L-2}]^{\top}\circ
B_{L-1}B_{L-1}^{\top}$ (D.2)
$\displaystyle+\left((F_{L-2}-\mathbb{E}[F_{L-2}])\mathbb{E}[F_{L-2}]^{\top}+\mathbb{E}[F_{L-2}](F_{L-2}-\mathbb{E}[F_{L-2}])^{\top}\right)\circ
B_{L-1}B_{L-1}^{\top}$
$\displaystyle=\tilde{J}_{F}\tilde{J}_{F}^{\top}+\left\|\nu\right\|_{2}^{2}B_{L-1}B_{L-1}^{\top}+\left(\Lambda\mathbf{1}\mathbf{1}^{\top}+\mathbf{1}\mathbf{1}^{\top}\Lambda\right)\circ
B_{L-1}B_{L-1}^{\top}$
$\displaystyle=\tilde{J}_{F}\tilde{J}_{F}^{\top}+\left(\left\|\nu\right\|_{2}\mathbf{1}+\frac{\Lambda\mathbf{1}}{\left\|\nu\right\|_{2}}\right)\left(\left\|\nu\right\|_{2}\mathbf{1}+\frac{\Lambda\mathbf{1}}{\left\|\nu\right\|_{2}}\right)^{\top}\circ
B_{L-1}B_{L-1}^{\top}$ $\displaystyle\hskip
14.22636pt-\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\nu\right\|_{2}^{2}}\circ
B_{L-1}B_{L-1}^{\top}$
$\displaystyle\succeq\tilde{J}_{F}\tilde{J}_{F}^{\top}-\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\nu\right\|_{2}^{2}}\circ
B_{L-1}B_{L-1}^{\top},$

where $\nu=\mathbb{E}_{x_{i}}[(F_{L-2})_{i:}]\in\mathbb{R}^{n_{L-2}}$
(independent on $i$, since the $x_{i}$-s are i.i.d.), $\Lambda$ is a diagonal
matrix such that
$\Lambda_{ii}=\nu^{\top}(F_{L-2})_{i:}-\left\|\nu\right\|_{2}^{2}=:\mu(x_{i})$,
and $\mathbf{1}\in\mathbb{R}^{N}$ is a vector full of ones. The last step is
justified since the Hadamard product of PSD matrices is PSD by the Schur
product theorem. Notice that we are assuming $\left\|\nu\right\|_{2}\neq 0$.
In fact, if $\left\|\nu\right\|_{2}=0$, then we immediately have that
$J=\tilde{J}_{F}$.

Expanding in an analogous way the term $\tilde{J}_{F}\tilde{J}_{F}^{\top}$, we
get

$\displaystyle J_{L-2}J_{L-2}^{\top}$
$\displaystyle\succeq\tilde{J}_{F}\tilde{J}_{F}^{\top}-\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\nu\right\|_{2}^{2}}\circ
B_{L-1}B_{L-1}^{\top}$ (D.3)
$\displaystyle=\tilde{J}_{FB}\tilde{J}_{FB}^{\top}+\left(\left\|\eta\right\|_{2}\mathbf{1}+\frac{\Gamma\mathbf{1}}{\left\|\eta\right\|_{2}}\right)\left(\left\|\eta\right\|_{2}\mathbf{1}+\frac{\Gamma\mathbf{1}}{\left\|\eta\right\|_{2}}\right)^{\top}\circ\tilde{F}_{L-2}\tilde{F}_{L-2}^{\top}$
$\displaystyle\hskip
14.22636pt-\frac{\Gamma\mathbf{1}\mathbf{1}^{\top}\Gamma}{\left\|\eta\right\|_{2}^{2}}\circ\tilde{F}_{L-2}\tilde{F}_{L-2}^{\top}-\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\nu\right\|_{2}^{2}}\circ
B_{L-1}B_{L-1}^{\top}$
$\displaystyle\succeq\tilde{J}_{FB}\tilde{J}_{FB}^{\top}+\left(\left\|\eta\right\|_{2}\mathbf{1}+\frac{\Gamma\mathbf{1}}{\left\|\eta\right\|_{2}}\right)\left(\left\|\eta\right\|_{2}\mathbf{1}+\frac{\Gamma\mathbf{1}}{\left\|\eta\right\|_{2}}\right)^{\top}\circ\tilde{F}_{L-2}\left(\frac{\nu\nu^{\top}}{\left\|\nu\right\|_{2}^{2}}\right)\tilde{F}_{L-2}^{\top}$
$\displaystyle\hskip
14.22636pt-\frac{\Gamma\mathbf{1}\mathbf{1}^{\top}\Gamma}{\left\|\eta\right\|_{2}^{2}}\circ\tilde{F}_{L-2}\tilde{F}_{L-2}^{\top}-\frac{\Lambda\mathbf{1}\mathbf{1}^{\top}\Lambda}{\left\|\nu\right\|_{2}^{2}}\circ
B_{L-1}B_{L-1}^{\top}$

where $\eta=\mathbb{E}_{x_{i}}[(B_{L-1})_{i:}]\in\mathbb{R}^{n_{L-1}}$
(independent on $i$, since the $x_{i}$-s are i.i.d.), $\Gamma$ is a diagonal
matrix such that
$\Gamma_{ii}=\eta^{\top}(B_{L-1})_{i:}-\left\|\eta\right\|_{2}^{2}=:\zeta(x_{i})$.
The last step is justified by the fact that the following matrix is PSD

$\left(\left\|\eta\right\|_{2}\mathbf{1}+\frac{\Gamma\mathbf{1}}{\left\|\eta\right\|_{2}}\right)\left(\left\|\eta\right\|_{2}\mathbf{1}+\frac{\Gamma\mathbf{1}}{\left\|\eta\right\|_{2}}\right)^{\top}\circ\tilde{F}_{L-2}\left(I-\frac{\nu\nu^{\top}}{\left\|\nu\right\|_{2}^{2}}\right)\tilde{F}_{L-2}^{\top},$

since it is the Hadamard product of two PSD matrices. Notice that we are
assuming $\left\|\eta\right\|_{2}\neq 0$. In fact, if
$\left\|\eta\right\|_{2}=0$, then we immediately have that
$\tilde{J}_{F}=\tilde{J}_{FB}$.

Taking into account the following relations

$\Lambda\mathbf{1}=\tilde{F}_{L-2}\nu,\qquad\Gamma\mathbf{1}=\tilde{B}_{L-1}\eta,\qquad\mathbb{E}_{X}[B_{L-1}]=\mathbf{1}\eta^{\top},$
(D.4)

we can simplify the second and the fourth term of the RHS of equation (D.3) as
follows