# Robustness in deep learning: The good (width),
the bad (depth), and the ugly (initialization)

Zhenyu Zhu, Fanghui Liu, Grigorios G Chrysos, Volkan Cevher
EPFL, Switzerland
{[first<EMAIL_ADDRESS>
###### Abstract

We study the average robustness notion in deep neural networks in (selected)
wide and narrow, deep and shallow, as well as lazy and non-lazy training
settings. We prove that in the under-parameterized setting, width has a
negative effect while it improves robustness in the over-parameterized
setting. The effect of depth closely depends on the initialization and the
training mode. In particular, when initialized with LeCun initialization,
depth helps robustness with lazy training regime. In contrast, when
initialized with Neural Tangent Kernel (NTK) and He-initialization, depth
hurts the robustness. Moreover, under non-lazy training regime, we demonstrate
how the width of a two-layer ReLU network benefits robustness. Our theoretical
developments improve the results by Huang et al. (2021); Wu et al. (2021) and
are consistent with Bubeck and Sellke (2021); Bubeck et al. (2021).

##  1 Introduction

It is now well-known that deep neural networks (DNNs) are susceptible to
adversarially chosen, albeit imperceptible perturbations to their inputs
(Goodfellow et al., 2015; Szegedy et al., 2014). This lack of robustness is
worrying as DNNs are now deployed in many real-world applications (Eykholt et
al., 2018). As a result, new algorithms are more and more being developed to
defend against adversarial attacks to improve the DNN robustness. Among the
current defense methods, the most commonly used and arguably the most
successful method is adversarial training based minimax optimization (Athalye
et al., 2018; Croce and Hein, 2020; Madry et al., 2018).

The literature focuses on several aspects of the robustness issue, from
algorithms to their initialization as well as from width of neural networks to
their depth (i.e., the architecture). On the practical side, Madry et al.
(2018) advocate that adversarial training requires more parameters (e.g.,
width) for better performance in minimax optimization, which would fall into
the so-called over-parameterized regime111Over-parameterized regime works in
the setting that the number of parameters in DNN is (much) larger than the
number of training data. (Zhang et al., 2021). On the theory side, recent
works suggest that over-parameterization may damage the adversarial robustness
(Huang et al., 2021; Wu et al., 2021; Zhou and Schoellig, 2019). In stark
contrast, Bubeck and Sellke (2021); Bubeck et al. (2021) argue that the
robustness of DNNs needs enough parameters to be guaranteed.

Our work is motivated to investigate this apparent contradiction in theory,
and to close the gap as much as possible. We begin with a definition of
_perturbation stability_ of DNNs, which can be used to describe the
robustness, following the spirit of Wu et al. (2021); Dohmatob and Bietti
(2022). Mathematically,

######  Definition 1 (_perturbation stability_).

The perturbation stability of the neural network $\bm{f}$ under data
distrubution $\mathcal{D}_{X}$ and perturbation radius $\epsilon$ is defined
as follows:

$\mathscr{P}(\bm{f},\epsilon)=\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\nabla_{\bm{x}}\bm{f}(\bm{x})^{\top}(\bm{x}-\bm{\hat{x}})\right\|_{2}\,,\quad\forall\bm{x}\sim\mathcal{D}_{X},~{}~{}\hat{\bm{x}}\sim\text{Unif}(\mathbb{B}(\epsilon,\bm{x}))\,.$
(1)

where $\hat{\bm{x}}$ is uniformly sampled from an $\ell_{2}$ norm ball of
$\bm{x}$ with radius $\epsilon$, denoted as
$\text{Unif}(\mathbb{B}(\epsilon,\bm{x}))$. Since our definition of
_perturbation stability_ takes the expectation to clean and adversarial data
points, it is natural to describe the _average robustness_ of a neural
network. It can be noticed that the larger value of _perturbation stability_
means worse _average robustness_.

Figure 1: Schematic of our deep fully connected ReLU neural network. Table 1: Comparison of the _perturbation stability_ of a deep ReLU neural network (see Fig. 1) under three common Gaussian initializations with different variances. A formal definition of this neural network refers to Eq. 2.  Initialization name | Initialization form |  Our bound for $\mathscr{P}(\bm{f},\epsilon)/\epsilon$
---|---|---
LeCun et al. (2012) |  $\beta=\beta_{L}=\sqrt{\frac{1}{m}}$, $\beta_{1}=\sqrt{\frac{1}{d}}$, $\alpha=1$ | $\bigg{(}\sqrt{\frac{\pi L^{3}m}{8d}}e^{-m/L^{3}}+1\bigg{)}(\frac{\sqrt{2}}{2})^{L-2}$
He et al. (2015) |  $\beta=\beta_{L}=\sqrt{\frac{2}{m}}$, $\beta_{1}=\sqrt{\frac{2}{d}}$, $\alpha=1$ | $\sqrt{\frac{\pi L^{3}m}{2d}}e^{-m/L^{3}}+1$
Allen-Zhu et al. (2019a) |  $\beta=\beta_{1}=\sqrt{\frac{2}{m}}$, $\beta_{L}=\sqrt{\frac{1}{o}}$, $\alpha=1$ | $\sqrt{\frac{\pi L^{3}m}{4o}}e^{-m/L^{3}}+1$

Based on _perturbation stability_ , we study the _average robustness_ of
neural networks under different initializations in (selected) wide and narrow,
deep and shallow, as well as lazy and non-lazy222Here the lazy/non-lazy
training regime indicates that neural network parameters change little/much
during training. These two phases are determined by different initializations
(Woodworth et al., 2020; Luo et al., 2021). training settings. Generally, non-
lazy training makes the analysis of neural networks intractable as DNNs in
this regime cannot be simplified as a time-independent model (Chizat and Bach,
2018), and accordingly, the analysis in this regime is mainly restricted to
the two-layer setting (Mei et al., 2018, 2019).

Overall, our results suggest that the width (_good_) helps robustness in the
over-parameterized regime but the depth (_bad_) can help only under certain
initializations (_ugly_). To be specific, we make the following contributions
and findings under the lazy/non-lazy training regimes, see Table 1.

In the lazy training regime, we derive upper-bounds, suggesting that

  * •

along with the increase in width, the robustness first becomes worse in the
under-parameterized setting and then gets better, and finally tends to be a
constant in highly over-parameterized regions, which implies the existence of
phase transition.

  * •

the depth has more complex tendency on robustness , which largely depends on
the initialization and the training mode. It can be grouped into two main
classes (_cf._ , Table 1): depth helps robustness in an exponential order
under LeCun initialization (LeCun et al., 2012), whereas it hurts robustness
in a polynomial order under He-initialization (He et al., 2015) and under
Neural Tangent Kernel (NTK) initialization (Allen-Zhu et al., 2019a).

Surprisingly, standard tools on training dynamics of neural networks (Allen-
Zhu et al., 2019a; Du et al., 2018a) are sufficient to obtain our bounds,
which explain the relationship between robustness and the
structural/architectural parameters of neural network. Our theoretical
developments improve the results by Huang et al. (2021); Wu et al. (2021), and
are supported by empirical evidence.

In the non-lazy training regime, we derive upper-bounds for two-layer
networks, suggesting that

  * •

the width improves robustness under different initializations.

We also derive a sufficient condition to identify when DNNs enter in this
regime, as an initial but first attempt on understanding DNNs in this regime.
Our technical contribution lies in connecting robustness to changes of neural
network parameters during the early stages of training, which could expand the
application scope of deep learning theory beyond _lazy training_ analysis
(Jacot et al., 2018; Allen-Zhu et al., 2019b).

Notations:

We use the shorthand $[n]:=\\{1,2,\dots,n\\}$ for some positive integer $n$.
We denote by $a(n)\lesssim b(n)$: there exists a positive constant $c$
independent of $n$ such that $a(n)\leqslant cb(n)$. The standard Gaussian
distribution is $\mathcal{N}(\bm{0},1)$ with the zero-mean and the identity
variance. Uniform distribution inside the sphere is
$\text{Unif}(\mathbb{B}(\epsilon,\bm{x}))$ with the center $\bm{x}$ and radius
$\epsilon$. We follow the standard Bachmann–Landau notation in complexity
theory e.g., $\mathcal{O}$, $o$, $\Omega$, and $\Theta$ for order notation.

##  2 Related work

DNNs are demonstrated to be fragile, sensitive to adversarially chosen but
undetectable noise both empiricallySzegedy et al. (2014) and theoretically
Huang et al. (2021); Bubeck and Sellke (2021). Adversarial training (Athalye
et al., 2018; Croce and Hein, 2020; Zhang et al., 2020b) is a reliable way to
obtain adversarially robust neural network. Nevertheless, improving the
overall robustness of neural networks is still an unsolved problem in machine
learning, especially when coupling with initializations and parameters.

Over-parameterized neural networks under lazy/non-lazy training regimes:
Modern DNNs in practice (He et al., 2016) work under the setting where the
number of parameters is (much) larger than the number of training data.
Analysis of DNNs in terms of optimization (Safran et al., 2021; Zhou et al.,
2021) and generalization (Cao and Gu, 2019) has received great attention in
deep learning theory (Zhang et al., 2021), and further brings in new insights,
e.g., double descent (Hassani and Javanmard, 2022), implicit bias (You et al.,
2020).

In deep learning theory, neural tangent kernel (NTK) Jacot et al. (2018) and
mean field analysis are two powerful tools for neural network analysis. To be
specific, NTK builds an equivalence between training dynamics by gradient-
based algorithms of DNNs and kernel regression under a specific
initialization, and thus allows for deep networks analysis (Allen-Zhu et al.,
2019a; Du et al., 2019; Chen et al., 2020). However, this way actually
requires neural networks falling in a _lazy training_ regime (Chizat et al.,
2019), where neural networks are able to achieve zero training loss but the
parameters change little, or even remain unchanged during training. In
contrast, mean-field theory establishes global convergence by casting network
weights during training as an evolution in the space of probability
distributions under some certain initialization to results (Mei et al., 2018;
Chizat and Bach, 2018). This strategy goes beyond lazy training regime, which
allows for neural networks parameters changing in a constant order after
training.

If neural networks parameters changes a lot after training, or even tend to
infinity, then neural networks work in _non-lazy_ training regime. Analysis of
DNNs under this setting appears intractable and challenging, so current work
mainly focus on two-layer neural networks (Maennel et al., 2018; Luo et al.,
2021).

Robustness and over-parameterization Goodfellow et al. (2015) demonstrate that
adversarial learning helps robustness and reduces overfitting, and in the
following, many works focus on the trace the origin and influencing factors of
adversarial examples and robustness for neural network (Schmidt et al., 2018b;
Zhang et al., 2020a; Allen-Zhu and Li, 2022). The relation between model
capacity and robustness is empirically investigated by Madry et al. (2017),
i.e., neural network with insufficient capacity can seriously hurt the
robustness. Bubeck et al. (2021) theoretically study the inherent trade-off
between the size of neural networks and their robustness, and they claim that
over-parameterization is necessary for the robustness of two-layer neural
networks.

However, some recent works propose the opposite view. Under the lazy training
regime, Huang et al. (2021) demonstrate that when over-parameterized neural
networks get wider, the robustness will be hurted in a polynomial order. At
the same time, the depth hurts the robustness in an exponential order. Wu et
al. (2021) affirm the view of Huang et al. (2021) on the width. However for
depth, they derive a stronger bound that the robustness gets worse in a
polynomial decay as depth increases. In addition, Gao et al. (2019) also make
a similar view: more model capacity (i.e., wider width and deeper depth) leads
to the robustness of neural networks worse. These contradict the previous
results in theoretical and experimental. In this work, we adopt a
complementary view to these vast literature. We provide an in-depth
theoretical analysis to investigate this apparent contradiction in theory, and
to close the gap as much as possible.

##  3 Problem setting

Let $X\subseteq\mathbb{R}^{d}$ and $Y\subseteq\mathbb{R}^{o}$ be compact
metric spaces. We assume that the training set
$\mathcal{D}_{tr}=\\{(\bm{x}_{i},\bm{y}_{i})\\}_{i=1}^{n}$ with data dimension
$\bm{x}\in\mathbb{R}^{d}$ and label dimension $\bm{y}\in\mathbb{R}^{o}$ is
drawn from a probability measure $\mathcal{D}$ on $X\times Y$. Its marginal
data distribution is denoted by $\mathcal{D}_{X}$. The goal of the
classification task is to find a neural network $\bm{f}:X\rightarrow Y$ such
that $\bm{f}(\bm{x};\bm{W})$ parameterized by $\bm{W}$ is a good approximation
of the label $\bm{y}\in Y$ corresponding to a new sample $\bm{x}\in X$. In
this paper, we use the empirical risk
$L(\bm{W})=\frac{1}{2n}\sum_{i=1}^{n}\left\|\bm{f}(\bm{x}_{i};\bm{W})-\bm{y}_{i}\right\|_{2}^{2}$.
Then we make the following assumptions.

######  Assumption 1.

We assume that the data satisfy $\|\bm{x}\|_{2}=1$.

Remark: This is a standard assumption in theory on over-parameterized neural
networks and it is also commonly used in practice. (Du et al., 2018b, 2019;
Allen-Zhu et al., 2019a; Oymak and Soltanolkotabi, 2020; Malach et al., 2020).

###  3.1 Network

We focus on the typical depth-$L$ fully-connected ReLU neural networks with
the width of the $l$-th hidden layer $m_{l},~{}\forall l\in[L]$ (_cf._ , Fig.
1):

$\bm{h}_{i,0}=\bm{x}_{i};\quad\bm{h}_{i,l}=\phi(\bm{W}_{l}\bm{h}_{i,l-1});\quad\bm{f}(\bm{x}_{i};\bm{W})=\bm{f}_{i}=\frac{1}{\alpha}\bm{W}_{L}\bm{h}_{i,L-1};\quad\forall
l\in[L-1]\ i\in[n]\,,$ (2)

where the $\bm{x}\in\mathbb{R}^{d}$, $\bm{f}(\bm{x})\in\mathbb{R}^{o}$,
$\alpha$ is the scaling factor, weights
$\bm{W}:=\\{\bm{W}_{i}\\}_{i=1}^{L}\in\\{\mathbb{R}^{m\times
d}\times(\mathbb{R}^{m\times m})^{L-2}\times\mathbb{R}^{o\times m}\\}$
represent the tuple of weight matrices and $\phi=\max(0,x)$ is ReLU activation
function. According to the property $\phi(x)=x\phi^{\prime}(x)$ of ReLU, we
have $\bm{h}_{i,l}=\bm{D}_{i,l}\bm{W}_{l}\bm{h}_{i,l-1}$, where $\bm{D}_{i,l}$
is a diagonal matrix under the ReLU activation function defined as below.

######  Definition 2 (Diagonal sign matrix).

For each $i\in[n]$, $l\in[L-1]$ and $k\in[m]$, the diagonal sign matrix
$\bm{D}_{i,l}$ is defined as:
$(\bm{D}_{i,l})_{k,k}=1\left\\{(\bm{W_{l}}\bm{h}_{i,l-1})_{k}\geq 0\right\\}$.

Initialization: Let $m_{0}=d$, $m_{L}=o$ and $m_{2}=\cdots=m_{L-1}=m$, we make
the standard random initialization
$[\bm{W}_{l}]_{i,j}\sim\mathcal{N}(0,\beta_{l}^{2})$ for every
$(i,j)\in[m_{l}]\times[m_{l-1}]$ and $l\in[L]$. This work holds for three
commonly used Gaussian initializations, i.e., LeCun initialization (LeCun et
al., 2012), He-initialization (He et al., 2015) and Neural Tangent Kernel
(NTK) initialization (Allen-Zhu et al., 2019a). The formulation of these
intilization refer to Table 1.

###  3.2 Discussion on various robustness metrics

In Section 1, we have proposed the our robustness metric: perturbation
stability (_cf._ , Definition 1). This metric can be viewed as an expectation
of inner product of first-order approximation of adversarial risk (Madry et
al., 2017) and the perturbations with uniform distribution, which measures the
_average robustness_ of the neural network. As we mentioned before, under the
same perturbation radius $\epsilon$, smaller value of
$\mathcal{P}(\bm{f},\epsilon)$ implies better _perturbation stability_ , that
is better _average robustness_. Previous works (Hein and Andriushchenko, 2017;
Weng et al., 2018; Wu et al., 2021; Bubeck and Sellke, 2021) use Lipschitzness
to describe the robustness of the network, suggesting that smaller
Lipschitzness leads to robust models. However, Lipschitzness is only a worst-
case measure, and cannot reasonably describe the average changes of the entire
dataset. Instead, we follow the measure of Wu et al. (2021); Dohmatob and
Bietti (2022), that aims to comprehensively considers the overall distribution
of the data, not only the extreme case. Compared with the definition of
robustness in Schmidt et al. (2018a) relies on the misclassified error of an
adversarial data point, our perturbation stability measures the function value
changes at the clean data point via Taylor expansion which can exclude the
influence of the learning capacity of the network.

##  4 Main results

In this section, we state the main theoretical results. Firstly, in Section
4.1 we provide the upper bound of _perturbation stability_ in lazy training
regime for deep neural networks defined by Eq. 2. The sufficient condition
that the neural network Eq. 2 is under non-lazy training regime is given in
Section 4.2. Finally, in Section 4.3, we provide the upper bound on
_perturbation stability_ during early training of two-layer network under non-
lazy training regime. The proofs of our theoretical results are deferred to
Appendix B, C, and D, respectively.

###  4.1 Upper bound of perturbation stability of DNNs under the lazy training
regime

We are now ready to state the main results under the lazy training regime. The
following theorem provides the upper bound of _perturbation stability_ and
connects to depth and width of network and dimension of data for a deep fully-
connected neural network under standard Gaussian initialization.

######  Theorem 1.

Given an $L$-layer neural network $\bm{f}$ defined by Eq. 2 trained by
$\left\\{(\bm{x}_{i},\bm{y}_{i})\right\\}_{i=1}^{n}$ satisfying 1, for the
convenience of analysis, we set $\alpha=1$ and
$\beta:=\beta_{2}=\dots=\beta_{L-1}$, define a constant
$\gamma:=\beta/\sqrt{\frac{2}{m}}$, then under a small perturbation $\epsilon$
, we have the following:

$\frac{\mathscr{P}(\bm{f},\epsilon)}{\epsilon}\lesssim\bigg{(}\sqrt{\frac{\pi
L^{3}m^{2}\beta_{1}^{2}\beta_{L}^{2}}{8}}e^{-m/L^{3}}+1\bigg{)}\gamma^{L-2}\,.$
(3)

Remark: Our results cover the effect of the width and depth of neural network
on robustness under various common initializations depending on
$\gamma\gtreqqless 1$.

For the initializations used in practice, our theoretical results can be
mainly divided into two classes. 1) Depth helps robustness in an exponential
order under LeCun initialization: our Theorem 1 implies
$\bigg{(}\sqrt{\frac{\pi
L^{3}m}{8d}}e^{-m/L^{3}}+1\bigg{)}(\frac{\sqrt{2}}{2})^{L-2}$; 2) Depth hurts
robustness in a polynomial order under He-initialization
$\bigg{(}\sqrt{\frac{\pi L^{3}m}{2d}}e^{-m/L^{3}}+1\bigg{)}$ and under NTK
initialization $\bigg{(}\sqrt{\frac{\pi L^{3}m}{4o}}e^{-m/L^{3}}+1\bigg{)}$
derived by Theorem 1. When employing other initializations, robustness could
be hurted in a exponential order. Below, we elaborate on these three
initalizations:

  * •

LeCun initialization ($\gamma=\frac{\sqrt{2}}{2}$): The order has three main
parts $\sqrt{\frac{\pi L^{3}m}{8d}}$, $e^{-m/L^{3}}$ and
$(\frac{\sqrt{2}}{2})^{L-2}$. The first two parts implies a phase transition
phenomenon between _perturbation stability_ and over-parameterization for the
width $m$. Concretely, $\sqrt{\frac{\pi L^{3}m}{8d}}$ is an increasing
function with respect to $m$ and $e^{-m/L^{3}}$ is a decreasing function with
respect to $m$. In the under-parameterized region ($m$ is small),
$\sqrt{\frac{L^{3}m}{d}}$ plays a major role, so the stability will increase
as $m$ increases . After a critical point, $e^{-m/L^{3}}$ plays a major role,
so the stability will decrease as $m$ increases . When $m$ tends to infinity,
the first term of bound tends to $0$. Hence the _perturbation stability_ tends
to be a constant and independent with width $m$ as the width $m$ tends to
infinity. However, for depth $L$, it holds that $\gamma=\frac{\sqrt{2}}{2}$ .
So the third part has the faster increase/decrease speed than the first and
second part and play a major role in the tendency. The _perturbation
stability_ of the neural network exponentially decreases with respect to the
depth. That means that for LeCun initialization, the deeper the network, the
better robustness . Nevertheless, the energy of LeCun initialization decreases
with the increase of network depth, which means that training deep network
with LeCun initialization is very difficult. Hence we need a trade off between
robustness and training difficulty regarding network depth in practice for
LeCun initialization.

  * •

He initialization and NTK initialization ($\gamma=1$): here the bounds only
have the first two parts. From this, it is easy to see that for the network
width $m$, the two initializations have similar phase transition phenomena
with LeCun initialization. Regarding to the depth, when $L$ is large, the
first part $\sqrt{L^{3}}$ plays a major role in the _perturbation stability_.
So these two initializations hurt the robustness of the neural network
polynomially.

  * •

In addition, if the initialization admits $\gamma\geq 1$, then the depth $L$
of network will exponentially hurt robustness of the neural network.

Comparison with previous work: Theorem 1 provides a new relationship between
the robustness with width and depth of DNNs. We compare our result with (Wu et
al., 2021; Huang et al., 2021) using a basic NTK initialization Allen-Zhu et
al. (2019a) (suppose that $m\gg o$ and $m\gg d$). For better comparison, we
derive their results under our robustness metric _perturbation stability_ ,
reported by Table 2.

Table 2: Comparison of the orders of the proposed bound with other two recent works. Our results are general to cover both under- and over-parameterized regimes, which expands the application scope of previous results (Wu et al., 2021; Huang et al., 2021). (The original result of (Wu et al., 2021) contains the condition $\frac{m}{(\log m)^{6}}\geq L^{12}$, then the result is reduced to $\sqrt{mL}$). Metrics | Our result | Wu et al. (2021) | Huang et al. (2021)
---|---|---|---
$\mathscr{P}(\bm{f},\epsilon)/\epsilon$ | $\sqrt{\frac{\pi L^{3}m}{4o}}e^{-m/L^{3}}+1$ | $L^{2}m^{1/3}\sqrt{\log m}+\sqrt{mL}$ | $2^{\frac{3L-5}{2}}\sqrt{m}$

Our results indicate a behavior transition on the width. For the over-
parameterized regime, the robustness of neural network only depends on the
perturbation energy, and it is almost independent of the width $m$. The
results on width are significantly better than the previous results increasing
as the square root of $m$. For depth $L$, our results provide a tighter and
more precise estimate as compared to Wu et al. (2021) in a two-degree
polynomial increasing order and Huang et al. (2021) in an exponential
increasing order.

###  4.2 Sufficient condition for neural network under non-lazy training
regime

Beyond the lazy training regime, we turn our attention to non-lazy training
regime and present results about the sufficient condition for (well-chosen)
initialization of neural networks when entering into the non-lazy training
regime. This is a first attempt to understanding training dynamics of DNNs in
this regime.

Our result requires a further assumption on the data and the empirical risk as
follows.

######  Assumption 2.

For a single-output network defined in Eq. (2), we assume that
$\max_{i\in[n]}y_{i}\geq C_{1}\geq 0$. We also assume that the neural network
can be well-trained such that the empirical risk is
$\mathcal{O}(\frac{1}{n})$.

Remark: This is a common assumption in the field of optimization (Song et al.,
2021) in the under- and over-parameterized regime, and we can even assume zero
risk. Here we follow the specific assumption of Luo et al. (2021).

Now we are ready to present our result, a sufficient condition to identify
when deep ReLU neural networks fall into non-lazy training regime, as a
promising extension of Luo et al. (2021) on two-layer neural networks. To
avoid cluttering the analysis, we consider a single-output i.e., $o=1$.

######  Theorem 2.

Given an $L$-layer neural network $\bm{f}$ defined by Eq. 2 with one-
dimensional output, trained by
$\left\\{(\bm{x}_{i},\bm{y}_{i})\right\\}_{i=1}^{n}$ satisfy Assumptions 1 and
2. Suppose that $\alpha\gg(m^{3/2}\sum_{i=1}^{L}\beta_{i})^{L}$ and $m\gg d$
in Eq. 2, then for sufficiently large $m$, with probability at least
$1-(L-2)\exp(-\Theta(m^{2}))-\exp(-\Theta(md))-\exp(-\Theta(m))$ over the
initialization, we have:

$\sup_{t\in[0,+\infty)}\frac{\left\|\bm{W}_{l}(t)-\bm{W}_{l}(0)\right\|_{\mathrm{F}}}{\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}}\gg
1\,.$

Remark: The condition $\alpha\gg(m^{3/2}\sum_{i=1}^{L}\beta_{i})^{L}$ implies
that, a neural network falls in a non-lazy training regime when the variance
of the Gaussian initialization is very small. A typical case is, taking $m\gg
L^{2}$, choosing $\alpha=1$ and $\forall l\in[L];\ \beta_{l}=\frac{1}{m^{2}}$.
Commonly used initializations such as NTK initialization, LeCun
initialization, He’s initialization lead to lazy training.

###  4.3 Upper bound of perturbation stability for two-layer networks in non-
lazy training

Unlike lazy training, weights of non-lazy training concentrate on few
directions determined by the input data in the early stages of training. The
following theorem describes the neural network _perturbation stability_ in the
early training stage as a function of network width in the non-lazy training
regime. For ease of description, here we consider a special initialization
scheme under the non-lazy regime, more cases under this theorem and proof are
deferred to the Appendix D.

######  Theorem 3.

Given a two-layer neural network $\bm{f}$ defined by Eq. 2 and trained by
$\left\\{(\bm{x}_{i},y_{i})\right\\}_{i=1}^{n}$ satisfying 1, using gradient
descent under the squared loss, consider the following initialization in Eq. 2
: $L=2$, $\alpha\sim 1$, $\beta_{1}\sim\beta_{2}\sim\beta\sim\frac{1}{m^{c}}$
with $c\geq 1.5$, $m\gg n^{2}$ and $t\leq t^{\star}(n,m,\alpha)$, then for a
small range of perturbation $\epsilon$, with probability at least
$1-n\exp(-\frac{n}{2})-\frac{3}{n}$ over initialization, we have the
following:

$\frac{\mathscr{P}(\bm{f}_{t},\epsilon)}{\epsilon}\leq\Theta\bigg{(}\frac{\sqrt{n\log
m}+n}{m^{c-1}}\bigg{(}\frac{1}{\sqrt{n^{3}m}}+\frac{1}{m^{c-0.5}}\bigg{)}\bigg{)}\,.$
(4)

Remark: Under this setting of non-lazy training regime, the robustness and
width of the neural network are positively correlated in the early stages of
training. That is, as the width $m$ increases in the over-parameterized
regime, a Gaussian initialization with smaller variance results in the
robustness increasing in a faster decay. Our result holds for other
initialization schemes in the non-lazy training regime, e.g., $c=2$ leads to
$\mathscr{P}(\bm{f}_{t},\epsilon)/\epsilon\leq\Theta\bigg{(}\frac{\sqrt{n\log
m}+n}{m^{2.5}}\bigg{)}$; and $c=3$ leads to
$\mathscr{P}(\bm{f}_{t},\epsilon)/\epsilon\leq\Theta\bigg{(}\frac{\sqrt{n\log
m}+n}{m^{4.5}}\bigg{)}$.

##  5 Numerical evidence

We validate our theoretical results with a series of experiments. In Section
5.2 we first verify that our initialization settings belong in the lazy and
the non-lazy training regimes. In Section 5.3, we then explore the effect of
varying widths from under-parameterized to over-parameterized regions on the
_perturbation stability_ of neural networks. In Section 5.4, we finally
compare the effect of two different initializations and the network depth on
the _perturbation stability_. Additional experimental results can be found in
Appendix E.

###  5.1 Experimental settings

Here we present our experimental setting including models, hyper-parameters,
the choice of width and depth, and initialization schemes. We use the popular
datasets of MNIST (Lecun et al., 1998) and CIFAR-10 (Krizhevsky et al., 2014)
for experimental validation.

Models: We report results using the following models: fully connected ReLU
neural network named “FCN” in main paper and convolutional ReLU neural network
named “CNN” in Appendix E.

Hyper-parameters: Unless mentioned otherwise, all models are trained for 50
epochs with a batch size of $64$. The initial value of the learning rate is
$0.001$. After the first $25$ epochs, the learning rate is multiplied by a
factor of $0.1$ every $10$ epochs. The SGD is used to optimize all the models,
while the cross-entropy loss is used.

Width and depth: In order to verify our theoretical results, we conduct a
series of experiments with different depths and widths of the same type neural
network. Specifically, our experiments include $11$ different widths from
$2^{4}$ to $2^{14}$, and four different choices of depths, i.e., $2,4,6,8,10$.

Initialization: We report results using the following initializations: 1) He
initialization where $W_{ij}\sim\mathcal{N}(0,\frac{2}{m_{in}}$), 2) LeCun
initialization where $W_{ij}\sim\mathcal{N}(0,\frac{1}{m_{in}}$) and 3) An
initialization allows for non-lazy training regime on two-layer networks,
i.e., $\beta_{1}=\beta_{2}=1/m^{2}$ and $\alpha=1$.

###  5.2 Validation for lazy and non-lazy training regimes

Before verifying our results, we need identify the lazy and non-lazy training
regime under different initializations. To this end, we define a measure _lazy
training ratio_ , i.e.,
$\kappa=\frac{\sum_{l=1}^{L}\left\|\bm{W}_{l}(t)-\bm{W}_{l}(0)\right\|_{\mathrm{F}}}{\sum_{l=1}^{L}\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}}$
to measure whether the neural network is under the lazy training regime. A
smaller $\kappa$ implies that the neural network is more close to lazy
training.

According to the theory, we employ He initialization and non lazy training
initialization we state in Section 5.1 then conduct the experiment under two-
layer neural networks to verify that their lazy training ratio matches the
theoretical results of lazy training and non-lazy training (i.e. the
experiment is under the correct regime). Fig. 2 and Fig. 2 show the tendency
of ratio with respect to time (training epochs) and relationship between width
and lazy training ratio of neural networks under lazy training regime,
respectively. We can find that the ratio of lazy traing regime is almost a
constant that does not change with time, and this constant decreases with the
width of network increases. This is in line with what we know about lazy
training (Chizat et al., 2019).

Likewise, Fig. 3 shows the ratio tendency with time and width under non-lazy
training regime. The ratio increases almost linearly over time in Fig. 3. In
epoch $25$ we decrease the learning rate, which results in the increase rate
of $\kappa$ changes. At the same time Fig. 3 shows the similar tendency
between width and lazy training ratio as lazy training. However, the value of
$\kappa$ is much higher than that of lazy training regime. Combining the
results about tendency with time, the ratio will be expected to increase as
time at a slow decay and tend to infinity under highly wide width setting.

Figure 2: (a) Tendency with respect to time (training epochs) and (b)
relationship between width and lazy training ratio of neural networks. Fig. 2
shows that ratio $\kappa$ is small and almost unchanged, recognized as _lazy
training_. In Fig. 2, we can see that the $\kappa$ decreases with the
increasing width.

Figure 3: (a) Tendency with respect to time (training epochs) and relationship
with width of non-lazy training ratio of neural networks. Fig. 3 shows that
ratio $\kappa$ is changed a lot (increasing and then remains unchanged),
recognized as _non-lazy training_. The tendency of $\kappa$ for non-lazy
training is increasing with the width and then decreasing, i.e., a phase
transition in Fig. 3.

###  5.3 Validation for width

We verify the relationship between the _perturbation stability_ and the width
of network as illustrated by Eqs. (3) and (4). We conduct a series of
experiments on MNIST dataset using FCN with different widths. Fig. 4 shows the
relationship between _perturbation stability_ and width of FCN with different
depths and training regimes. Here for lazy training and non-lazy training we
use the same initialization as Section 5.2.

Fig. 4(a) exhibits the relationship between the _perturbation stability_ and
the width for neural networks with different depths of $L=2,4,6,8$, and $10$.
All of the five curves show the phase transition with width, and the
_perturbation stability_ first increases and then decreases with width, which
match our theoretical results. Fig. 4(b) shows the difference of the effect of
width on the _perturbation stability_ of lazy and non-lazy training for two-
layer neural networks. First, the _perturbation stability_ of non-lazy
training is significantly smaller than that of lazy training, which means non-
lazy training regime is more robust. Besides, the _perturbation stability_ of
non-lazy training decrease with the width of the neural network increases,
which coincides with our theoretical result, i.e., no phase transition
phenomenon.

(a) Lazy training with different widths and depths

(b) Lazy and non-lazy training under different widths

Figure 4: Influence of width of neural network on _perturbation stability_.
(a) phase transition of _perturbation stability_ _vs._ width with five
different depths under lazy training. (b) the difference between lazy training
and non-lazy training regimes for two layer neural networks.

###  5.4 Validation for depth and initialization

Here we explore the effect of depth on _perturbation stability_ under lazy
training regime with different initializations in Fig. 5 and Fig. 5. Our
results show the tendency of _perturbation stability_ for FCN with different
widths and depths under He initialization and LeCun initialization,
respectively. We observe a similar phase transition phenomenon, and find that,
the _perturbation stability_ under He initialization increases with depth,
while the LeCun initialization shows the opposite tendency, which verified our
theory.

Figure 5: Relationship between _perturbation stability_ and depth of FCN under
He initialization (a) and LeCun initialization (b) different depths of
$L=2,4,6,8$ and $10$.

##  6 Conclusions

In this work, we explore the interplay of the width, the depth and the
initialization of neural networks on their average robustness with new
theoretical bounds in an effort to address the apparent contradiction in the
literature. Our theoretical results hold in both under- and over-parameterized
regimes. Intriguingly, we find a change of behavior in average robustness with
respect to the depth, initially exacerbating robustness and then alleviating
it. We suspect that this could help explain the contradictory messages in the
literature. We also characterize the average robustness in the non-lazy
training regime for two layer neural networks and find that width always help,
coinciding the with the results (Bubeck and Sellke, 2021; Bubeck et al.,
2021). We also provide numerical evidence to support the theoretical
developments.

## Acknowledgements

We are thankful to the reviewers for providing constructive feedback. Research
was sponsored by the Army Research Office and was accomplished under Grant
Number W911NF-19-1-0404. This work was supported by Hasler Foundation Program:
Hasler Responsible AI (project number 21043). This work was supported by the
Swiss National Science Foundation (SNSF) under grant number $200021\\_205011$.
This work was supported by Zeiss. This project has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement n° 725594 - time-data).

## References

  * Allen-Zhu and Li (2022) Z. Allen-Zhu and Y. Li.  Feature purification: How adversarial training performs robust deep learning.  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 977–988. IEEE, 2022.
  * Allen-Zhu et al. (2019a) Z. Allen-Zhu, Y. Li, and Z. Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pages 242–252. PMLR, 2019a.
  * Allen-Zhu et al. (2019b) Z. Allen-Zhu, Y. Li, and Z. Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning (ICML)_ , 2019b.
  * Athalye et al. (2018) A. Athalye, N. Carlini, and D. Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples, 2018.
  * Bietti and Mairal (2019) A. Bietti and J. Mairal.  On the inductive bias of neural tangent kernels.  _Advances in neural information processing systems (NeurIPS)_ , 2019\.
  * Bubeck and Sellke (2021) S. Bubeck and M. Sellke.  A universal law of robustness via isoperimetry.  In _Advances in neural information processing systems (NeurIPS)_ , 2021.  URL https://openreview.net/forum?id=z71OSKqTFh7.
  * Bubeck et al. (2021) S. Bubeck, Y. Li, and D. M. Nagaraj.  A law of robustness for two-layers neural networks.  In _Conference on Learning Theory_ , 2021.
  * Cao and Gu (2019) Y. Cao and Q. Gu.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  _Advances in neural information processing systems (NeurIPS)_ , 32, 2019.
  * Chen and Xu (2021) L. Chen and S. Xu.  Deep neural tangent kernel and laplace kernel have the same {rkhs}.  In _International Conference on Learning Representations_ , 2021.
  * Chen et al. (2020) Z. Chen, Y. Cao, D. Zou, and Q. Gu.  How much over-parameterization is sufficient to learn deep ReLU networks?  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Chizat and Bach (2018) L. Chizat and F. Bach.  On the global convergence of gradient descent for over-parameterized models using optimal transport.  _Advances in neural information processing systems (NeurIPS)_ , 31, 2018.
  * Chizat et al. (2019) L. Chizat, E. Oyallon, and F. Bach.  On lazy training in differentiable programming.  _Advances in neural information processing systems (NeurIPS)_ , 32, 2019.
  * Croce and Hein (2020) F. Croce and M. Hein.  Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.  In _International Conference on Machine Learning (ICML)_ , pages 2206–2216. PMLR, 2020.
  * Dohmatob and Bietti (2022) E. Dohmatob and A. Bietti.  On the (non-)robustness of two-layer neural networks in different learning regimes, 2022.
  * Du et al. (2019) S. Du, J. Lee, H. Li, L. Wang, and X. Zhai.  Gradient descent finds global minima of deep neural networks.  In _International Conference on Machine Learning_ , pages 1675–1685. PMLR, 2019.
  * Du et al. (2018a) S. S. Du, W. Hu, and J. D. Lee.  Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced.  In _Advances in neural information processing systems (NeurIPS)_ , 2018a.
  * Du et al. (2018b) S. S. Du, X. Zhai, B. Poczos, and A. Singh.  Gradient descent provably optimizes over-parameterized neural networks, 2018b.
  * Eykholt et al. (2018) K. Eykholt, I. Evtimov, E. Fernandes, B. Li, A. Rahmati, C. Xiao, A. Prakash, T. Kohno, and D. Song.  Robust physical-world attacks on deep learning visual classification.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Gao et al. (2019) R. Gao, T. Cai, H. Li, C.-J. Hsieh, L. Wang, and J. D. Lee.  Convergence of adversarial training in overparametrized neural networks.  _Advances in neural information processing systems (NeurIPS)_ , 32, 2019.
  * Geifman et al. (2020) A. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and R. Basri.  On the similarity between the laplace and neural tangent kernels.  _Advances in neural information processing systems (NeurIPS)_ , 2020\.
  * Goodfellow et al. (2015) I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  In _International Conference on Learning Representations (ICLR)_ , 2015.
  * Hassani and Javanmard (2022) H. Hassani and A. Javanmard.  The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression, 2022.
  * He et al. (2015) K. He, X. Zhang, S. Ren, and J. Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _International Conference on Computer Vision (ICCV)_ , pages 1026–1034, 2015.
  * He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778, 2016.
  * Hein and Andriushchenko (2017) M. Hein and M. Andriushchenko.  Formal guarantees on the robustness of a classifier against adversarial manipulation.  In _Advances in neural information processing systems (NeurIPS)_ , volume 30, 2017.
  * Huang et al. (2021) H. Huang, Y. Wang, S. M. Erfani, Q. Gu, J. Bailey, and X. Ma.  Exploring architectural ingredients of adversarially robust deep neural networks.  In _Advances in neural information processing systems (NeurIPS)_ , 2021.
  * Jacot et al. (2018) A. Jacot, F. Gabriel, and C. Hongler.  Neural tangent kernel: Convergence and generalization in neural networks, 2018.
  * Krizhevsky et al. (2014) A. Krizhevsky, V. Nair, and G. Hinton.  The cifar-10 dataset.  _online: http://www. cs. toronto. edu/kriz/cifar. html_ , 55, 2014\.
  * Lecun et al. (1998) Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.  doi: 10.1109/5.726791.
  * LeCun et al. (2012) Y. A. LeCun, L. Bottou, G. B. Orr, and K.-R. Müller.  Efficient backprop.  In _Neural networks: Tricks of the trade_ , pages 9–48. Springer, 2012.
  * Luo et al. (2021) T. Luo, Z.-Q. J. Xu, Z. Ma, and Y. Zhang.  Phase diagram for two-layer relu neural networks at infinite-width limit.  _Journal of Machine Learning Research_ , 2021.
  * Madry et al. (2017) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks, 2017.
  * Madry et al. (2018) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Maennel et al. (2018) H. Maennel, O. Bousquet, and S. Gelly.  Gradient descent quantizes relu network features, 2018.
  * Malach et al. (2020) E. Malach, G. Yehudai, S. Shalev-Schwartz, and O. Shamir.  Proving the lottery ticket hypothesis: Pruning is all you need.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Mei et al. (2018) S. Mei, A. Montanari, and P.-M. Nguyen.  A mean field view of the landscape of two-layers neural networks, 2018\.
  * Mei et al. (2019) S. Mei, T. Misiakiewicz, and A. Montanari.  Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit.  In _Conference on Learning Theory_. PMLR, 2019.
  * Nguyen et al. (2021) Q. Nguyen, M. Mondelli, and G. F. Montufar.  Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Oymak and Soltanolkotabi (2020) S. Oymak and M. 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.
  * Safran et al. (2021) I. M. Safran, G. Yehudai, and O. Shamir.  The effects of mild over-parameterization on the optimization landscape of shallow relu neural networks.  In _Conference on Learning Theory_ , pages 3889–3934. PMLR, 2021\.
  * Schmidt et al. (2018a) L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry.  Adversarially robust generalization requires more data.  In _Advances in neural information processing systems (NeurIPS)_ , 2018a.
  * Schmidt et al. (2018b) L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry.  Adversarially robust generalization requires more data.  _Advances in neural information processing systems (NeurIPS)_ , 31, 2018b.
  * Song et al. (2021) C. Song, A. Ramezani-Kebrya, T. Pethick, A. Eftekhari, and V. Cevher.  Subquadratic overparameterization for shallow neural networks.  _Advances in neural information processing systems (NeurIPS)_ , 34, 2021.
  * Szegedy et al. (2014) C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus.  Intriguing properties of neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2014.
  * Vershynin (2018) R. Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_.  Cambridge University Press, 2018.
  * Weng et al. (2018) T.-W. Weng, H. Zhang, P.-Y. Chen, J. Yi, D. Su, Y. Gao, C.-J. Hsieh, and L. Daniel.  Evaluating the robustness of neural networks: An extreme value theory approach.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Woodworth et al. (2020) B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro.  Kernel and rich regimes in overparametrized models.  In _Conference on Learning Theory_. PMLR, 2020.
  * Wu et al. (2021) B. Wu, J. Chen, D. Cai, X. He, and Q. Gu.  Do wider neural networks really help adversarial robustness?  In _Advances in neural information processing systems (NeurIPS)_ , volume 34, 2021.
  * You et al. (2020) C. You, Z. Zhu, Q. Qu, and Y. Ma.  Robust recovery via implicit bias of discrepant learning rates for double over-parameterization.  _Advances in neural information processing systems (NeurIPS)_ , 33:17733–17744, 2020.
  * Zhang et al. (2021) C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning (still) requires rethinking generalization.  _Communications of the ACM_ , 64(3):107–115, 2021\.
  * Zhang et al. (2020a) X. Zhang, J. Chen, Q. Gu, and D. Evans.  Understanding the intrinsic robustness of image distributions using conditional generative models.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 3883–3893. PMLR, 2020a.
  * Zhang et al. (2020b) Y. Zhang, O. Plevrakis, S. S. Du, X. Li, Z. Song, and S. Arora.  Over-parameterized adversarial training: An analysis overcoming the curse of dimensionality.  _Advances in neural information processing systems (NeurIPS)_ , 33:679–688, 2020b.
  * Zhou et al. (2021) M. Zhou, R. Ge, and C. Jin.  A local convergence theory for mildly over-parameterized two-layer neural network.  In _Conference on Learning Theory_ , pages 4577–4632. PMLR, 2021\.
  * Zhou and Schoellig (2019) S. Zhou and A. P. Schoellig.  An analysis of the expressiveness of deep neural network architectures based on their lipschitz constants, 2019.

## Appendix introduction

The Appendix is organized as follows:

  * •

In Appendix A, we state the symbols and notation used in this paper.

  * •

In Appendix B, we provide the proofs and related lemmas of Theorem 1.

  * •

In Appendix C, we provide the proofs of Theorem 2.

  * •

In Appendix D, we provide the proofs and related lemmas of Theorem 3.

  * •

In Appendix E, we detail our experimental settings and exhibit additional
experimental results.

  * •

In Appendix F, we discuss several limitations of this work.

  * •

Finally, in Appendix G, we discuss the societal impact of this paper.

##  Appendix A Symbols and Notation

In the paper, vectors are indicated with bold small letters, matrices with
bold capital letters. To facilitate the understanding of our work, we include
the some core symbols and notation in Table 3.

Table 3: Core symbols and notations used in this project.  Symbol | Dimension(s) | Definition
---|---|---
$\mathcal{N}(\mu,\sigma)$ | - |  Gaussian distribution of mean $\mu$ and variance $\sigma$
$\mathrm{Ber}(m,p)$ | - |  Bernoulli (Binomial) distribution with $m$ trials and $p$ success rate.
$\chi^{2}(\omega)$ | - |  Chi-square distribution of order $\omega$.
$\left\|\bm{v}\right\|_{2}$ | - |  Euclidean norms of vectors $\bm{v}$
$\left\|\bm{M}\right\|_{2}$ | - |  Spectral norms of matrices $\bm{M}$
$\left\|\bm{M}\right\|_{\mathrm{F}}$ | - |  Frobenius norms of matrices $\bm{M}$
$\left\|\bm{M}\right\|_{\mathrm{\ast}}$ | - |  Nuclear norms of matrices $\bm{M}$
$\lambda(\bm{M})$ | - |  Eigenvalues of matrices $\bm{M}$
$\bm{M}^{[l]}$ | - |  $l$-th row of matrices $\bm{M}$
$\bm{M}_{i,j}$ | - |  $(i,j)$-th element of matrices $\bm{M}$
$\phi(x)=\max(0,x)$ | - | ReLU activation function for scalar
$\phi(\bm{v})=(\phi(v_{1}),\dots,\phi(v_{m}))$ | - | ReLU activation function for vectors
$1\left\\{\text{event}\right\\}$ | - | Indicator function for event
$n$ | - | Size of the dataset
$d$ | - | Input size of the network
$o$ | - | Output size of the network
$L$ | - | Depth of the network
$m$ | - | Width of intermediate layer
$\beta_{l}$ | - |  Standard deviation of Gaussian initialization of $l$-th intermediate layer
$\alpha$ | - | Scale factor for the output layer
$\bm{x}_{i}$ | $\mathbb{R}^{d}$ |  The $i$-th data point
$\bm{y}_{i}$ | $\mathbb{R}^{o}$ |  The $i$-th target vector
$\mathcal{D}_{X}$ | - | Input data distribution
$\mathcal{D}_{Y}$ | - | Target data distribution
$\bm{W}_{1}$ | $\mathbb{R}^{m\times d}$ | Weight matrix for the input layer
$\bm{W}_{l}$ | $\mathbb{R}^{m\times m}$ |  Weight matrix for the $l$-th hidden layer
$\bm{W}_{L}$ | $\mathbb{R}^{o\times m}$ | Weight matrix for the output layer
$\bm{h}_{i,l}$ | $\mathbb{R}^{m}$ |  The $l$-th layer activation for input $\bm{x}_{i}$
$\bm{f}_{i}$ | $\mathbb{R}^{o}$ |  Output of network for input $\bm{x}_{i}$
$\mathcal{O}$, $o$, $\Omega$ and $\Theta$ | - | Standard Bachmann–Landau order notation

##  Appendix B Proof of upper bound of Perturbation Stability in lazy training
regime for deep neural network

We present the details of our results from Section 4.1 in this section.
Firstly, we introduce some lemmas in Section B.1 to facilitate the proof of
theorems. Then, in Section B.2 we provide the proof of Theorem 1.

###  B.1 Relevant Lemmas

######  Lemma 1.

Let $w\sim\mathcal{N}(0,\sigma^{2})$. Then define two random variables
$X=(w\times 1\left\\{w\geq 0\right\\})^{2}$ and $Y=sw^{2}$, where
$s\sim\mathrm{Ber}(1,1/2)$ follows a Bernoulli distribution with $1$ trial and
$\frac{1}{2}$ success rate. Then $X$ and $Y$ have the same distribution.

###### Proof.

Firstly, we derive the cumulative distribution function (CDF) of $X$.
Obviously, $X$ is non-negative and $\mathbb{P}(X=0)=1/2$, which holds by $X=0$
iff $w<0$. Accordingly, for $x\geq 0$ , we have:

$\mathbb{P}(X\leq x)=P(w<0)+P(0\leq
w\leq\sqrt{x})=\frac{1}{2}+\int_{0}^{\sqrt{x}}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{t^{2}}{2\sigma^{2}}}dt\,.$

Then $X$ has the following cumulative distribution function:

$F(X\leq x)=\begin{cases}0&\text{ if }x<0\\\ \frac{1}{2}&\text{ if }x=0\\\
\frac{1}{2}+\int_{0}^{\sqrt{x}}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{t^{2}}{2\sigma^{2}}}dt&\text{
if }x>0\,.\end{cases}$ (5)

We then derive the CDF of $Y$. Obviously, $Y$ is non-negative and
$\mathbb{P}(Y=0)=1/2$, which holds by $Y=0$ iff $s=0$. Accordingly, for $x\geq
0$ , we have:

$\mathbb{P}(Y\leq x)=P(s=0)+P(s=1)P(-\sqrt{x}\leq
w\leq\sqrt{x})=\frac{1}{2}+\frac{1}{2}\int_{-\sqrt{x}}^{\sqrt{x}}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{t^{2}}{2\sigma^{2}}}dt\,.$

Then $Y$ has the following cumulative distribution function:

$F(Y\leq x)=\begin{cases}0&\text{ if }x<0\\\ \frac{1}{2}&\text{ if }x=0\\\
\frac{1}{2}+\frac{1}{2}\int_{-\sqrt{x}}^{\sqrt{x}}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{t^{2}}{2\sigma^{2}}}dt&\text{
if }x>0\end{cases}$ (6)

Comparing Eq. 5 to Eq. 6, we conclude that $X$ and $Y$ admit the same
distribution. ∎

######  Lemma 2.

Let $\bm{h}\in\mathbb{R}^{p}$ be a fixed non-zero vector,
$\bm{W}\in\mathbb{R}^{q\times p}$ be random matrix with i.i.d. entries
$\bm{W}_{i,j}\sim\mathcal{N}(0,2/q)$. The vector $\bm{v}\in\mathbb{R}^{q}$ is
defined as $\bm{v}=\phi(\bm{W}\bm{h})$. Then,
$\frac{q\left\|\bm{v}\right\|_{2}^{2}}{2\left\|\bm{h}\right\|_{2}^{2}}\sim\chi^{2}(\varrho)$,
where $\varrho\sim\mathrm{Ber}(q,1/2)$.

###### Proof.

According to the definition of $\bm{v}=\phi(\bm{W}\bm{h})$, we have:

$\left\|\bm{v}\right\|_{2}^{2}=\sum_{i=1}^{q}\bigg{(}\bm{D}_{i,i}\left\langle\bm{W}^{[i]},\bm{h}\right\rangle\bigg{)}^{2}\,,$

where $\bm{D}_{i,i}=1\left\\{\left\langle\bm{W}^{[i]},\bm{h}\right\rangle\geq
0\right\\}$.

Let
$\varpi_{i}=\left\langle\bm{W}^{[i]},\bm{h}\right\rangle/\bigg{(}\sqrt{\frac{2\left\|\bm{h}\right\|_{2}^{2}}{q}}\bigg{)}$,
then $\varpi_{i}\sim\mathcal{N}(0,1)$ independently. Accordingly, we have:

$\frac{q\left\|\bm{v}\right\|_{2}^{2}}{2\left\|\bm{h}\right\|_{2}^{2}}=\sum_{i=1}^{q}\bigg{(}1\left\\{\varpi_{i}\geq
0\right\\}\varpi_{i}\bigg{)}^{2}\,.$

By Lemma 1 and definition of chi-square distribution, we have
$\frac{q\left\|\bm{v}\right\|_{2}^{2}}{2\left\|\bm{h}\right\|_{2}^{2}}\sim\chi^{2}(\varrho)$,
where $\varrho\sim\mathrm{Ber}(q,1/2)$.

∎

######  Lemma 3.

Given an $L$-layer neural network $\bm{f}$ defined by Eq. 2, we have:

$\bm{f}(\bm{x})=\widehat{\bm{W}}_{L}\phi(\widehat{\bm{W}}_{L-1}\cdots\phi(\widehat{\bm{W}_{1}}\bm{x})\cdots)\,,$
(7)

where $[\widehat{\bm{W}}_{l}]_{i,j}$ satisfy the initialization in Section
3.1, i.e., $\beta:=\beta_{2}=\dots=\beta_{L-1}$.

Define another $L$-layer neural network $\bm{f}^{\prime}$ by Eq. 2, then we
have:

$\tilde{\bm{f}}(\bm{x})=\gamma^{L}\tilde{\bm{W}}_{L}\phi(\tilde{\bm{W}}_{L-1}\cdots\phi(\tilde{\bm{W}_{1}}\bm{x})\cdots)\,,$
(8)

where $[\tilde{\bm{W}}_{l}]_{i,j}=[\widehat{\bm{W}}_{l}]_{i,j}/\gamma$.

Then if we choose an appropriate learning rate, $\bm{f}$ and $\bm{f}^{\prime}$
will have the same dynamics.

###### Proof.

According to the chain rule, we have:

$\frac{\mathrm{d}\tilde{\bm{f}}}{\mathrm{d}\tilde{\bm{W}}_{l}}=\gamma\frac{\mathrm{d}\bm{f}}{\mathrm{d}\widehat{\bm{W}}_{l}}\,.$

If we choose learning rate $\tilde{\eta}:=\frac{\eta}{\gamma^{2}}$, then we
have:

$\frac{\mathrm{d}\tilde{\bm{W}}_{l}}{\mathrm{d}t}=\frac{1}{\gamma}\frac{\mathrm{d}\widehat{\bm{W}}_{l}}{\mathrm{d}t}\,.$

Consider that $\tilde{\bm{W}}_{l}(0)=\frac{1}{\gamma}\widehat{\bm{W}}_{l}(0)$,
then we have:

$\tilde{\bm{W}}_{l}(t)=\frac{1}{\gamma}\widehat{\bm{W}}_{l}(t)\,.$

That means $\bm{f}(t)=\tilde{\bm{f}}(t)$, which concludes the proof. ∎

######  Lemma 4.

Given an $L$-layer neural network $\bm{f}$ defined by Eq. 2 trained by
$\left\\{(\bm{x}_{i},\bm{y}_{i})\right\\}_{i=1}^{n}$, under a small
perturbation $\epsilon$, we have:

$\small\mathbb{E}_{\bm{x},\hat{\bm{x}},\bm{W}}\left\|\nabla_{\bm{x}}\bm{f}(\bm{x})^{\top}(\bm{x}-\bm{\hat{x}})-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}\leq\Theta\bigg{(}\epsilon\gamma^{L-2}\sqrt{\frac{\pi
L^{3}m^{2}\beta_{1}^{2}\beta_{L}^{2}}{8}}e^{-m/L^{3}}\bigg{)}\,,$ (9)

where $[\bm{W}_{l}]_{i,j}$ satisfy the initialization in Section 3.1,
$\bm{x}\sim\mathcal{D}_{X}$ and
$\hat{\bm{x}}\sim\text{Unif}(\mathbb{B}(\epsilon,\bm{x}))$.

###### Proof.

We set the network after training with the following form:

$\bm{f}(\bm{x})=\widehat{\bm{W}}_{L}\phi(\widehat{\bm{W}}_{L-1}\cdots\phi(\widehat{\bm{W}_{1}}\bm{x})\cdots)\,.$

According to the standard chain rule, we have:

$\nabla_{\bm{x}}\bm{f}(\bm{x})^{\top}=\bm{\widehat{W}}_{L}\bm{\widehat{D}}_{L-1}\cdots\bm{\widehat{D}}_{1}\bm{\widehat{W}}_{1}=\gamma^{L}\bm{\widehat{W}}^{\prime}_{L}\bm{\widehat{D}}_{L-1}\cdots\bm{\widehat{D}}_{1}\bm{\widehat{W}}^{\prime}_{1}\,.$

Assume that perturbation matrices satisfy
$\left\|\bm{\widehat{W}}_{l}-\bm{W}_{l}\right\|_{2}\leq\omega\,,\ \forall
l\in[L]$. Then by Allen-Zhu et al. [2019b, Lemma 7.4, Lemma 8.6, Lemma 8.7],
we obtain that for any integer
$s\in\left[\Omega(\frac{d}{\log{m}}),\mathcal{O}(\frac{m}{L^{3}\log{m}})\right]$,
for $d\leq\mathcal{O}(\frac{m}{L\log{m}})$, with probability at least
$1-\exp{\bigg{(}-\Omega(s\log m)\bigg{)}}$ over the randomness of
$\\{\bm{W}\\}_{l=1}^{L}$, it holds that:

$\left\|\bm{\widehat{W}}^{\prime}_{L}\bm{\widehat{D}}_{L-1}\cdots\bm{\widehat{D}}_{1}\bm{\widehat{W}}^{\prime}_{1}-\bm{W}^{\prime}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}^{\prime}_{1}\right\|_{2}\leq\mathcal{O}\bigg{(}\sqrt{\frac{L^{3}s\log{m}+\omega^{2}L^{3}m}{d}}\sqrt{\frac{dm}{2}}\frac{\beta_{1}\beta_{L}}{\gamma^{2}}\bigg{)}\,,$

which implies:

$\left\|\nabla_{\bm{x}}f(\bm{x})^{\top}-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}\right\|_{2}\leq\mathcal{O}\bigg{(}\sqrt{\frac{L^{3}s\log{m}+\omega^{2}L^{3}m}{d}}\sqrt{\frac{dm}{2}}\beta_{1}\beta_{L}\gamma^{L-2}\bigg{)}\,,$

with probability at least $1-\exp{\bigg{(}-\Omega(s\log m)\bigg{)}}$.

If we choose $s:=\frac{m}{L^{3}\log{m}}+\frac{\omega^{2}}{\log{m}}$, then we
have:

$\left\|\nabla_{\bm{x}}f(\bm{x})^{\top}-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}\right\|_{2}\leq\mathcal{O}\bigg{(}\sqrt{\frac{L^{3}\omega^{2}+m+\omega^{2}L^{3}m}{d}}\sqrt{\frac{dm}{2}}\beta_{1}\beta_{L}\gamma^{L-2}\bigg{)}\,,$

with probability at least
$1-\exp{\bigg{(}-\Omega(\frac{m}{L^{3}}+\omega^{2})\bigg{)}}$.

Let
$\delta:=\sqrt{\frac{L^{3}\omega^{2}+m+\omega^{2}L^{3}m}{d}}\sqrt{\frac{dm}{2}}\beta_{1}\beta_{L}\gamma^{L-2}$
, then $\omega^{2}=\frac{u\delta^{2}-m}{L^{3}(m+1)}$,
$u=\frac{2}{m\beta_{1}^{2}\beta_{L}^{2}\gamma^{2(L-2)}}$, then we have:

$\small\mathbb{P}\bigg{(}\left\|\nabla_{\bm{x}}f(\bm{x})^{\top}-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}\right\|_{2}>\delta\bigg{)}\leq\exp{\bigg{(}-\frac{u\delta^{2}-m}{L^{3}(m+1)}-\frac{m}{L^{3}}\bigg{)}}=\exp{\bigg{(}-\frac{\delta^{2}u+m^{2}}{L^{3}(m+1)}\bigg{)}}\,.$

Then we can compute the expectation:

$\small\begin{split}\mathbb{E}_{\bm{W}}\left\|\nabla_{\bm{x}}f(\bm{x})^{\top}-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}\right\|_{2}&=\int_{0}^{+\infty}\mathbb{P}\bigg{(}\left\|\nabla_{\bm{x}}f(\bm{x})^{\top}-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}\right\|_{2}>\delta\bigg{)}\mathrm{d}\delta\\\
&\leq\int_{0}^{+\infty}\exp{\bigg{(}-\frac{\delta^{2}u+m^{2}}{L^{3}(m+1)}\bigg{)}}\mathrm{d}\delta\\\
&=\sqrt{\frac{\pi
L^{3}(m+1)}{4u}}\exp{\bigg{(}-\frac{m^{2}}{(m+1)L^{3}}\bigg{)}}\\\
&=\Theta\bigg{(}\gamma^{L-2}\sqrt{\frac{\pi
L^{3}m^{2}\beta_{1}^{2}\beta_{L}^{2}}{8}}e^{-m/L^{3}}\bigg{)}\,,\end{split}$
(10)

where the first equality holds by the expectation integral equality Vershynin
[2018, Lemma 1.2.1].

Finally, by the definition of $\bm{\hat{x}}$, we have:

$\small\left\|\nabla_{\bm{x}}\bm{f}^{\top}(\bm{x})(\bm{x}-\bm{\hat{x}})-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}\leq\epsilon\left\|\nabla_{\bm{x}}f(\bm{x})^{\top}-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}\right\|_{2}\,.$
(11)

By Eq. 10 and Eq. 11, we finish the proof.

∎

######  Lemma 5.

Given an $L$-layer neural network $\bm{f}$ defined by Eq. 2 trained by
$\left\\{(\bm{x}_{i},\bm{y}_{i})\right\\}_{i=1}^{n}$, under a small
$\epsilon$, expectation over $\bm{W}$, we have:

$\mathbb{E}_{\bm{x},\hat{\bm{x}},\bm{W}}\left\|\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}^{2}\leq\frac{mo\beta_{1}^{2}\beta_{L}^{2}\gamma^{2(L-2)}}{2}\epsilon^{2}\,,$
(12)

where $[\bm{W}_{l}]_{i,j}$ satisfy the initialization in Section 3.1 and
$\bm{x}\sim\mathcal{D}_{X}$,
$\hat{\bm{x}}\sim\text{Unif}(\mathbb{B}(\epsilon,\bm{x}))$.

###### Proof.

Let $\bm{t}_{l}=\bm{D}_{l}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})$,
then:

$\mathbb{E}_{\bm{x},\hat{\bm{x}},\bm{W}}\left\|\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}^{2}=\mathbb{E}_{\bm{x},\hat{\bm{x}},\bm{W}}\left\|\bm{W}_{L}\bm{t}_{L-1}\right\|_{2}^{2}\,.$

By Lemma 2 we have
$\frac{\left\|\bm{t}_{l}\right\|_{2}^{2}}{\beta^{2}\left\|\bm{t}_{l-1}\right\|_{2}^{2}}\sim\chi^{2}(\varrho)$,
where $\varrho\sim\mathrm{Ber}(m,1/2),\forall l=2,\cdots,L-1$. This implies
that:

$\mathbb{E}_{\bm{W}}\frac{\left\|\bm{t}_{l}\right\|_{2}^{2}}{\left\|\bm{t}_{l-1}\right\|_{2}^{2}}=\beta^{2}\mathbb{E}_{\varrho}\chi^{2}(\varrho)=\beta^{2}\mathbb{E}\varrho=\frac{m\beta^{2}}{2}=\gamma^{2}\,,\
\forall l=2,\cdots,L-1\,.$

Similarly, we have:

$\mathbb{E}_{\bm{W}}\frac{\left\|\bm{t}_{1}\right\|_{2}^{2}}{\left\|\hat{\bm{x}}-\bm{x}\right\|_{2}^{2}}=\frac{m\beta_{1}^{2}}{2}\,.$

By the definition of chi-square distribution, we have
$\frac{\left\|\bm{W}_{L}\bm{t}_{L-1}\right\|_{2}^{2}}{\beta_{L}^{2}\left\|\bm{t}_{L-1}\right\|_{2}^{2}}\sim\chi^{2}(o)$,
which means
$\mathbb{E}_{\bm{W}}\left\|\bm{W}_{L}\bm{t}_{L-1}\right\|_{2}^{2}/\left\|\bm{t}_{L-1}\right\|_{2}^{2}=o\beta_{L}^{2}$.
Then we have:

$\begin{split}\mathbb{E}_{\bm{x},\hat{\bm{x}},\bm{W}}\left\|\bm{W}_{L}\bm{t}_{L-1}\right\|_{2}^{2}&=\mathbb{E}_{\bm{x},\hat{\bm{x}},\bm{W}}\frac{\left\|\bm{W}_{L}\bm{t}_{L-1}\right\|_{2}^{2}}{\left\|\bm{t}_{L-1}\right\|_{2}^{2}}\frac{\left\|\bm{t}_{L-1}\right\|_{2}^{2}}{\left\|\bm{t}_{L-2}\right\|_{2}^{2}}\cdots\frac{\left\|\bm{t}_{1}\right\|_{2}^{2}}{\left\|\hat{\bm{x}}-\bm{x}\right\|_{2}^{2}}\left\|\hat{\bm{x}}-\bm{x}\right\|_{2}^{2}\\\
&=\mathbb{E}_{\bm{W}}\frac{\left\|\bm{W}_{L}\bm{t}_{L-1}\right\|_{2}^{2}}{\left\|\bm{t}_{L-1}\right\|_{2}^{2}}\mathbb{E}_{\bm{W}}\frac{\left\|\bm{t}_{L-1}\right\|_{2}^{2}}{\left\|\bm{t}_{L-2}\right\|_{2}^{2}}\cdots\mathbb{E}_{\bm{W}}\frac{\left\|\bm{t}_{1}\right\|_{2}^{2}}{\left\|\hat{\bm{x}}-\bm{x}\right\|_{2}^{2}}\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\hat{\bm{x}}-\bm{x}\right\|_{2}^{2}\\\
&=\frac{mo\beta_{1}^{2}\beta_{L}^{2}\gamma^{2(L-2)}}{2}\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\hat{\bm{x}}-\bm{x}\right\|_{2}^{2}\,,\end{split}$

using the definition of $\bm{\hat{x}}$ which conclude the proof. ∎

###  B.2 Proof of Theorem 1

###### Proof.

According to the triangle inequality and the Jensen’s inequality, we have:

$\small\begin{split}\mathscr{P}(\bm{f},\epsilon)&=\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\nabla_{\bm{x}}\bm{f}(\bm{x})(\bm{x}-\bm{\hat{x}})\right\|_{2}\\\
&\leq\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\nabla_{\bm{x}}\bm{f}(\bm{x})(\bm{x}-\bm{\hat{x}})-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}+\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}\\\
&\leq\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\nabla_{\bm{x}}\bm{f}(\bm{x})(\bm{x}-\bm{\hat{x}})-\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}+\sqrt{\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left\|\bm{W}_{L}\bm{D}_{L-1}\cdots\bm{D}_{1}\bm{W}_{1}(\bm{x}-\bm{\hat{x}})\right\|_{2}^{2}}\\\
&\leq\epsilon\bigg{(}\sqrt{\frac{\pi
L^{3}m^{2}\beta_{1}^{2}\beta_{L}^{2}}{8}}e^{-m/L^{3}}+\frac{\sqrt{mo}\beta_{1}\beta_{L}}{\sqrt{2}}\bigg{)}\gamma^{L-2}\,,\end{split}$

where the last inequality using the results of Lemma 4 and Lemma 5.

Finally we analyze the $\frac{\sqrt{mo}\beta_{1}\beta_{L}}{\sqrt{2}}$ term,
for three common Gaussian initializations in Table 1 we have
$\frac{\sqrt{mo}\beta_{1}\beta_{L}}{\sqrt{2}}=\sqrt{\frac{o}{2d}}$ in LeCun
initialization,
$\frac{\sqrt{mo}\beta_{1}\beta_{L}}{\sqrt{2}}=\sqrt{\frac{2o}{d}}$ in He
initialization and $\frac{\sqrt{mo}\beta_{1}\beta_{L}}{\sqrt{2}}=1$ in NTK
initialization. Regarded $d$ and $o$ as constant order, then
$\frac{\sqrt{mo}\beta_{1}\beta_{L}}{\sqrt{2}}$ will be of constant order in
these three initializations, then we have:

$\mathscr{P}(\bm{f},\epsilon)\lesssim\epsilon\bigg{(}\sqrt{\frac{\pi
L^{3}m^{2}\beta_{1}^{2}\beta_{L}^{2}}{8}}e^{-m/L^{3}}+1\bigg{)}\gamma^{L-2}\,.$

∎

##  Appendix C Proof of sufficient condition for DNNs under the non-lazy
training regime

In this section, we provide the proof of Theorem 2.

###### Proof.

By 2 and by following the setting of Luo et al. [2021], without loss of
generality, we have that there exits a $T^{\star}>0$ such that
$L(\bm{W}(T^{\star}))\leq\frac{1}{32n}$ and $y_{1}\geq\frac{1}{2}$. Therefore,
we have:

$\frac{1}{2n}(f_{1}(T^{\star})-y_{1})^{2}\leq\frac{1}{2n}\sum_{i=1}^{n}(f_{i}(T^{\star})-y_{i})^{2}\leq
L(\bm{W}(T^{\star}))\leq\frac{1}{32n}\,,$

which means $\left|f_{1}(T^{\star})-y_{1}\right|\leq\frac{1}{4}$. Accordingly,
we conclude:

$\small\begin{split}\frac{1}{4}\leq y_{1}-\frac{1}{4}&\leq f_{1}(T^{\star})\\\
&=\frac{1}{\alpha}\bm{W}_{L}(T^{\star})\sigma(\bm{W}_{L-1}(T^{\star})\cdots\sigma(\bm{W}_{1}(T^{\star})\bm{x}_{1}))\\\
&=\frac{1}{\alpha}\bm{W}_{L}(T^{\star})\bm{D}_{1,L-1}(T^{\star})\bm{W}_{L-1}(T^{\star})\cdots\bm{D}_{1,1}(T^{\star})\bm{W}_{1}(T^{\star})\bm{x}_{1}\\\
&\leq\frac{1}{\alpha}\left\|\bm{W}_{L}(T^{\star})\right\|_{2}\left\|\bm{D}_{1,L-1}(T^{\star})\right\|_{2}\left\|\bm{W}_{L-1}(T^{\star})\right\|_{2}\cdots\left\|\bm{D}_{1,1}(T^{\star})\right\|_{2}\left\|\bm{W}_{1}(T^{\star})\right\|_{2}\left\|\bm{x}_{1}\right\|_{2}\\\
&\leq\frac{1}{\alpha}\left\|\bm{W}_{L}(T^{\star})\right\|_{2}\left\|\bm{W}_{L-1}(T^{\star})\right\|_{2}\cdots\left\|\bm{W}_{1}(T^{\star})\right\|_{2}\,,\end{split}$
(13)

where the last inequality uses 1 and 1-Lipschitz of ReLU.

According to Du et al. [2018a, Corollary 2.1] , we have:

$\frac{\mathrm{d}}{\mathrm{d}t}(\left\|\bm{W}_{1}\right\|_{\mathrm{F}}^{2})=\frac{\mathrm{d}}{\mathrm{d}t}(\left\|\bm{W}_{2}\right\|_{\mathrm{F}}^{2})=\cdots=\frac{\mathrm{d}}{\mathrm{d}t}(\left\|\bm{W}_{L}\right\|_{\mathrm{F}}^{2})\,.$

Then for any $l_{1},l_{2}\in[L]$, we have:

$\left\|\bm{W}_{l_{1}}(T^{\star})\right\|_{\mathrm{F}}^{2}-\left\|\bm{W}_{l_{1}}(0)\right\|_{\mathrm{F}}^{2}=\left\|\bm{W}_{l_{2}}(T^{\star})\right\|_{\mathrm{F}}^{2}-\left\|\bm{W}_{l_{2}}(0)\right\|_{\mathrm{F}}^{2}\,,$

which implies:

$\begin{split}\left\|\bm{W}_{l_{1}}(T^{\star})\right\|_{2}&\leq\left\|\bm{W}_{l_{1}}(T^{\star})\right\|_{\mathrm{F}}\\\
&=\sqrt{\left\|\bm{W}_{l_{1}}(T^{\star})\right\|_{\mathrm{F}}^{2}}\\\
&=\sqrt{\left\|\bm{W}_{l_{2}}(T^{\star})\right\|_{\mathrm{F}}^{2}-\left\|\bm{W}_{l_{2}}(0)\right\|_{\mathrm{F}}^{2}+\left\|\bm{W}_{l_{1}}(0)\right\|_{\mathrm{F}}^{2}}\\\
&\leq\sqrt{\left\|\bm{W}_{l_{2}}(T^{\star})\right\|_{\mathrm{F}}^{2}+\left\|\bm{W}_{l_{1}}(0)\right\|_{\mathrm{F}}^{2}}\\\
&\leq\left\|\bm{W}_{l_{2}}(T^{\star})\right\|_{\mathrm{F}}+\left\|\bm{W}_{l_{1}}(0)\right\|_{\mathrm{F}}\,.\end{split}$
(14)

According to Luo et al. [2021, Proposition 16] and the relationship between
$\ell_{2}$ norm and Frobenius norm, i.e.
$\left\|\cdot\right\|_{\mathrm{F}}\leq\sqrt{r}\left\|\cdot\right\|_{2}$, where
the $r$ is the rank of matrix, with probability at least
$1-(L-2)\exp(-\Theta(m^{2}))-\exp(-\Theta(md))-\exp(-\Theta(m))$ over the
initialization, we have
$\left\|\bm{W}_{1}(0)\right\|_{\mathrm{F}}\leq\sqrt{d}\left\|\bm{W}_{1}(0)\right\|_{2}\leq\sqrt{\frac{3md^{2}}{2}}\beta_{1}$,
$\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}\leq\sqrt{m}\left\|\bm{W}_{l}(0)\right\|_{2}\leq\sqrt{\frac{3m^{3}}{2}}\beta_{l},\
\forall l\in[L-1]$ and
$\left\|\bm{W}_{L}(0)\right\|_{\mathrm{F}}=\left\|\bm{W}_{L}(0)\right\|_{2}\leq\sqrt{\frac{3m}{2}}\beta_{L}$.

If we combine Eqs. (13) and (14), for any $l^{\star}\in[L]$, with probability
at least $1-(L-2)\exp(-\Theta(m^{2}))-\exp(-\Theta(md))-\exp(-\Theta(m))$ over
the initialization, we have:

$\begin{split}\frac{1}{4}&\leq\frac{1}{\alpha}\left\|\bm{W}_{L}(T^{\star})\right\|_{2}\left\|\bm{W}_{L-1}(T^{\star})\right\|_{2}\cdots\left\|\bm{W}_{1}(T^{\star})\right\|_{2}\\\
&=\frac{1}{\alpha}\prod_{l=1}^{L}\bigg{(}\left\|\bm{W}_{l^{\star}}(T^{\star})\right\|_{\mathrm{F}}+\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}\bigg{)}\\\
&\leq\frac{1}{\alpha}\bigg{(}\left\|\bm{W}_{l^{\star}}(T^{\star})\right\|_{\mathrm{F}}+\frac{1}{L}\sum_{l=1}^{L}\bigg{(}\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}\bigg{)}\bigg{)}^{L}\\\
&\leq\frac{1}{\alpha}\bigg{(}\left\|\bm{W}_{l^{\star}}(T^{\star})\right\|_{\mathrm{F}}+\sqrt{\frac{3m^{3}}{2L^{2}}}\sum_{l=1}^{L}\beta_{l}\bigg{)}^{L}\,.\end{split}$

Then with probability at least
$1-(L-2)\exp(-\Theta(m^{2}))-\exp(-\Theta(md))-\exp(-\Theta(m))$ over the
initialization, we have:

$\left\|\bm{W}_{l^{\star}}(T^{\star})\right\|_{\mathrm{F}}\geq\bigg{(}\frac{\alpha}{4}\bigg{)}^{1/L}-\sqrt{\frac{3m^{3}}{2L^{2}}}\sum_{l=1}^{L}\beta_{l}\,.$
(15)

Therefore, with probability at least
$1-(L-2)\exp(-\Theta(m^{2}))-\exp(-\Theta(md))-\exp(-\Theta(m))$ over the
initialization, we have:

$\begin{split}\sup_{t\in[0,+\infty)}\frac{\left\|\bm{W}_{l}(t)-\bm{W}_{l}(0)\right\|_{\mathrm{F}}}{\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}}&\geq\frac{\left\|\bm{W}_{l}(T^{\star})-\bm{W}_{l}(0)\right\|_{\mathrm{F}}}{\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}}\\\
&\geq\frac{\left\|\bm{W}_{l}(T^{\star})\right\|_{\mathrm{F}}}{\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}}-1\\\
&\geq\frac{(\frac{\alpha}{4})^{1/L}-\sqrt{\frac{3m^{3}}{2L^{2}}}\sum_{i=1}^{L}\beta_{i}}{\sqrt{\frac{3m^{3}}{2}}\beta_{l}}-1\\\
&\geq\frac{(\frac{\alpha}{4})^{1/L}-\sqrt{\frac{3m^{3}}{2L^{2}}}\sum_{i=1}^{L}\beta_{i}}{\sqrt{\frac{3m^{3}}{2}}\sum_{i=1}^{L}\beta_{i}}-1\\\
&=\frac{(\frac{\alpha}{4})^{1/L}}{\sqrt{\frac{3m^{3}}{2}}\sum_{i=1}^{L}\beta_{i}}-\frac{1}{L}-1\,,\end{split}$

where the second inequality uses triangle inequality and third inequality uses
Eq. 15.

If $\alpha\gg(m^{3/2}\sum_{i=1}^{L}\beta_{i})^{L}$, then with probability at
least $1-(L-2)\exp(-\Theta(m^{2}))-\exp(-\Theta(md))-\exp(-\Theta(m))$ over
the initialization, we have:

$\sup_{t\in[0,+\infty)}\frac{\left\|\bm{W}_{l}(t)-\bm{W}_{l}(0)\right\|_{\mathrm{F}}}{\left\|\bm{W}_{l}(0)\right\|_{\mathrm{F}}}\gg
1\,.$

∎

##  Appendix D Proof of perturbation stability in non-lazy training regime for
two-layer networks

Without loss of generality, we consider two-layer neural networks with a
scalar output without bias.

$f(\bm{x})=\frac{1}{\alpha}\sum_{r=1}^{m}a_{r}\sigma(\bm{w}_{r}^{\top}\bm{x})\,,$
(16)

where $\bm{x}\in\mathbb{R}^{d}$, $f(\bm{x})\in\mathbb{R}$, $\alpha$ is the
scaling factor. The parameters are initialized by
$a_{r}(0)\sim\mathcal{N}(0,\beta_{2}^{2})$,
$\bm{w}_{r}(0)\sim\mathcal{N}(0,\beta_{1}^{2}\bm{I}_{d})$. Our result can be
extended with slight modification to the multiple-output case with bias
setting.

Our proof requires some additional notation, which we establish below:

$\bm{H}_{ij}^{\infty}=\frac{m}{\alpha^{2}}\mathbb{E}_{\bm{w}\sim\mathcal{N}(0,\beta_{1}^{2}\bm{I}_{d}),\bm{a}\sim\mathcal{N}(0,\beta_{2}^{2})}a_{r}^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}^{\top}\bm{x}_{j}\geq 0\right\\}\,,$

$\widetilde{\bm{H}}_{i,j}(t)=\frac{1}{\alpha^{2}}\sum_{r=1}^{m}a_{r}^{2}(t)\mathbb{E}_{\bm{w}\sim\mathcal{N}(0,\beta_{1}^{2}\bm{I}_{d})}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}^{\top}\bm{x}_{j}\geq 0\right\\}\,,$

$\bm{H}_{i,j}(t)=\frac{1}{\alpha^{2}}\sum_{r=1}^{m}a_{r}(t)^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(t)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(t)^{\top}\bm{x}_{j}\geq 0\right\\}\,,$

$\widehat{\bm{H}}_{i,j}=\frac{1}{\alpha^{2}}\sum_{r=1}^{m}a_{r}(t)^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(0)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(0)^{\top}\bm{x}_{j}\geq 0\right\\}\,,$

$\bm{G}_{i,j}(t)=\frac{1}{\alpha^{2}}\sigma(\bm{w}_{r}(t)^{\top}\bm{x}_{i})\sigma(\bm{w}_{r}(t)^{\top}\bm{x}_{j})\,.$

Then, minimum eigenvalue of $\bm{H}_{ij}^{\infty}$ is denoted as $\lambda_{0}$
and is assumed to be strictly greater than 0, i.e.

$\lambda_{0}=\lambda_{\min}(\bm{H}^{\infty})>0\,.$

Remark: This assumption follows Du et al. [2018b] but can be proved by Nguyen
et al. [2021] under the NTK initialization. Moreover, Chen and Xu [2021],
Geifman et al. [2020], Bietti and Mairal [2019] discuss this assumption in
different settings.

The following two symbols are used to measure the weight changes during
training:

$R_{a}:=\frac{\alpha}{n}\sqrt{\frac{\lambda_{0}}{8nm}}-\sqrt{\frac{2}{\pi}}\beta_{2},\quad\text{and}\quad
R_{w}:=\frac{\alpha^{2}\lambda_{0}\sqrt{2\pi}\beta_{1}}{32n^{3}m(R_{a}(R_{a}+\sqrt{8/\pi}\beta_{2})+\beta_{2}^{2})}\,,$
(17)

The last two symbols are used to characterize the early stages of neural
network training:

$t_{1}^{\star}=-\frac{2}{\lambda_{0}}\log\bigg{(}1-\frac{R_{w}\lambda_{0}\alpha}{2\sqrt{n}(\sqrt{n}\beta_{2}+R_{a})\left\|\bm{y}-\bm{f}(0)\right\|_{2}}\bigg{)}\,,$

$t_{2}^{\star}=-\frac{2}{\lambda_{0}}\log\bigg{(}1-\frac{R_{a}\lambda_{0}\alpha}{2\sqrt{n}(3\beta_{1}\sqrt{\log(mn^{2})}+R_{w})\left\|\bm{y}-\bm{f}(0)\right\|_{2}}\bigg{)}\,.$

Then we present the details of our results on Section 4.3 in this section.
Firstly, we introduce some lemmas in Section D.1 to facilitate the proof of
theorems. Then in Section D.2 we provide the proof of Theorem 3.

###  D.1 Relevant Lemmas

######  Lemma 6.

[Du et al., 2018b, Appendix A.1] Given a two-layer neural network $f$ defined
by Eq. 16 and trained by $\left\\{\bm{x}_{i},y_{i}\right\\}_{i=1}^{n}$ using
gradient descent with the quadratic loss, let
$\bm{y}=(y_{1},\dots,y_{n})\in\mathbb{R}^{n}$ be the label vector and
$\bm{f}(t)=(f_{1}(t),\dots,f_{n}(t))\in\mathbb{R}^{n}$ be the output vector at
time $t$, then we have:

$\frac{\mathrm{d}\bm{f}(t)}{\mathrm{d}t}=(\bm{H}(t)+\bm{G}(t))(\bm{y}-\bm{f}(t))\,.$
(18)

###### Proof.

Our proof here just re-organizes Du et al. [2018b, Appendix A.1]. For self-
completeness, we provide a formal proof here.

We want to minimize the quadratic loss:

$L(\bm{W},\bm{a})=\sum_{i=1}^{n}\frac{1}{2}[f(\bm{W},\bm{a},\bm{x}_{i})-y_{i}]^{2}\,.$

Using the gradient descent algorithm, the formula for update the weights is:

$\bm{W}(t+1)=\bm{W}(t)-\eta\frac{\partial
L(\bm{W}(t),\bm{a}(t))}{\partial\bm{W}(t)}\,,$

$\bm{a}(t+1)=\bm{a}(t)-\eta\frac{\partial
L(\bm{W}(t),\bm{a}(t))}{\partial\bm{a}(t)}\,.$

According to the standard chain rule, we have:

$\frac{\partial
L(\bm{W}(t),\bm{a}(t))}{\partial\bm{W}(t)}=\frac{1}{\alpha}\sum_{i=1}^{n}[f(\bm{W}(t),\bm{a}(t),\bm{x}_{i})-y_{i}]a_{r}(t)1\left\\{\bm{w}_{r}^{\top}(t)\bm{x}_{i}\geq
0\right\\}\bm{x}_{i}\,,$

$\frac{\partial
L(\bm{W}(t),\bm{a}(t))}{\partial\bm{a}(t)}=\frac{1}{\alpha}\sum_{i=1}^{n}[f(\bm{W}(t),\bm{a}(t),\bm{x}_{i})-y_{i}]\sigma(\bm{w}_{r}^{\top}(t)\bm{x}_{i})\,.$

Then we have:

$\begin{split}\frac{\mathrm{d}f_{i}(t)}{\mathrm{d}t}&=\sum_{r=1}^{m}\left\langle\frac{\partial
f_{i}(t)}{\partial\bm{w}_{r}(t)},\frac{\partial\bm{w}_{r}(t)}{\partial
t}\right\rangle+\sum_{r=1}^{m}\frac{\mathrm{d}f_{i}(t)}{\mathrm{d}a_{r}(t)}\frac{\mathrm{d}a_{r}(t)}{\mathrm{d}t}\\\
&=\sum_{i=1}^{n}[y_{i}-f_{i}(t)][\bm{H}_{ij}(t)+\bm{G}_{ij}(t)]\,.\end{split}$

Written in vector form, we have:

$\frac{\mathrm{d}\bm{f}(t)}{\mathrm{d}t}=(\bm{H}(t)+\bm{G}(t))(\bm{y}-\bm{f}(t))\,,$

∎

######  Lemma 7.

If $\alpha\geq\frac{16n\beta_{2}\sqrt{\log(2n^{3})}}{\lambda_{0}}$, with
probability at least $1-\frac{1}{n}$, we have:

$\left\|\bm{H}(0)-\bm{H}^{\infty}\right\|_{2}\leq\frac{\lambda_{0}}{4},\quad\text{and}\quad\lambda_{\min}(\bm{H}(0))\geq\frac{3}{4}\lambda_{0}\,,$

Remark: This lemma is a modified version of Du et al. [2018b, Lemma 3.1],
which differs in the initialization of $\bm{a}$ from
$\text{Unif}(\left\\{-1,+1\right\\})$ to Gaussian initialization. This makes
our analysis relatively intractable due to their analysis based on
$a^{2}_{i}=1,~{}\forall i\in[m]$.

###### Proof.

Firstly, for a fixed pair $(i,j)$, $\bm{H}_{ij}^{\infty}$ is an average of
$\widetilde{\bm{H}}_{i,j}$ with respect to $a_{r}$ . By Bernstein’s inequality
[Vershynin, 2018, Chapter 2], with probability at least $1-\delta$ we have:

$\left|\bm{H}_{ij}^{\infty}-\widetilde{\bm{H}}_{i,j}\right|\leq\frac{2\beta_{2}\sqrt{\log(\frac{1}{\delta})}}{\alpha}\,.$

Then, for fixed pair $(i,j)$, $\widetilde{\bm{H}}_{i,j}$ is an average of
$\bm{H}_{ij}(0)$ with respect to $\bm{w}_{r}$. By Hoeffding’s inequality
[Vershynin, 2018, Chapter 2], with probability at least $1-\delta^{\prime}$ we
have:

$\left|\bm{H}_{ij}(0)-\widetilde{\bm{H}}_{i,j}\right|\leq\frac{2\beta_{2}\sqrt{\log(\frac{1}{\delta^{\prime}})}}{\alpha}\,.$

Choose $\delta:=\delta^{\prime}:=\frac{1}{2n^{3}}$, we have with probability
at least $1-\frac{1}{n^{3}}$, for fixed pair $(i,j)$:

$\left|\bm{H}_{ij}(0)-\bm{H}_{ij}^{\infty}\right|\leq\frac{4\beta_{2}\sqrt{\log(2n^{3})}}{\alpha}\,.$

Consider the union bound over $(i,j)$ pairs, with probability at least
$1-\frac{1}{n}$ we have:

$\left|\bm{H}_{ij}(0)-\bm{H}_{ij}^{\infty}\right|\leq\frac{4\beta_{2}\sqrt{\log(2n^{3})}}{\alpha}\,.$

Thus we have:

$\left\|\bm{H}(0)-\bm{H}^{\infty}\right\|_{2}^{2}\leq\left\|\bm{H}(0)-\bm{H}^{\infty}\right\|_{\mathrm{F}}^{2}\leq\sum_{i,j}\left|\bm{H}_{ij}(0)-\bm{H}_{ij}^{\infty}\right|^{2}\leq\frac{16n^{2}\beta_{2}^{2}\log(2n^{3})}{\alpha^{2}}\,.$

when $\alpha\geq\frac{16n\beta_{2}\sqrt{\log(2n^{3})}}{\lambda_{0}}$ we have
the desired result. ∎

######  Lemma 8.

With probability at least $1-\frac{2}{n}$ over initialization , if a set of
weight vectors $\left\\{\bm{w}_{r}\right\\}_{r=1}^{m}$ and the output weight
$\left\\{a_{r}\right\\}_{r=1}^{m}$ satisfy for all $r\in[m]$,
$\left\|\bm{w}_{r}(t)-\bm{w}_{r}(0)\right\|_{2}\leq R_{w}$ and
$\left|a_{r}(t)-a_{r}(0)\right|\leq R_{a}$, then we have:

$\left\|\bm{H}(t)-\bm{H}(0)\right\|_{2}\leq\frac{\lambda_{0}}{4},\quad\text{and}\quad\lambda_{\min}(\bm{H}(t))\geq\frac{\lambda_{0}}{2}\,,$

###### Proof.

Firstly, we can derive that:

$\widehat{\bm{H}}_{i,j}(t)-\bm{H}_{i,j}(0)=\frac{1}{\alpha^{2}}\sum_{r=1}^{m}(a_{r}(t)^{2}-a_{r}(0)^{2})\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(0)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(0)^{\top}\bm{x}_{j}\geq 0\right\\}\,,$

$\begin{split}\bm{H}_{i,j}(t)-\widehat{\bm{H}}_{i,j}(t)&=\frac{1}{\alpha^{2}}\sum_{r=1}^{m}a_{r}(t)^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(t)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(t)^{\top}\bm{x}_{j}\geq 0\right\\}\\\
&-\frac{1}{\alpha^{2}}\sum_{r=1}^{m}a_{r}(t)^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(0)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(0)^{\top}\bm{x}_{j}\geq 0\right\\}\,.\end{split}$

Then we can compute the expectation of
$\left|\widehat{\bm{H}}_{i,j}(t)-\bm{H}_{i,j}(0)\right|$:

$\begin{split}\mathbb{E}\left|\widehat{\bm{H}}_{i,j}(t)-\bm{H}_{i,j}(0)\right|&=\mathbb{E}\left|\frac{1}{\alpha^{2}}\sum_{r=1}^{m}(a_{r}(t)^{2}-a_{r}(0)^{2})\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(0)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(0)^{\top}\bm{x}_{j}\geq 0\right\\}\right|\\\
&\leq\frac{m}{\alpha^{2}}\mathbb{E}\left|a_{r}(t)^{2}-a_{r}(0)^{2}\right|\\\
&=\frac{m}{\alpha^{2}}\mathbb{E}\left|(a_{r}(t)-a_{r}(0))(a_{r}(t)+a_{r}(0))\right|\\\
&\leq\frac{mR_{a}}{\alpha^{2}}\mathbb{E}\left|a_{r}(t)+a_{r}(0)\right|\\\
&\leq\frac{mR_{a}}{\alpha^{2}}(R_{a}+2\mathbb{E}\left|a_{r}(0)\right|)\\\
&\leq\frac{m(R_{a}+\mathbb{E}\left|a_{r}(0)\right|)^{2}}{\alpha^{2}}\\\
&=\frac{m(R_{a}+\sqrt{\frac{2}{\pi}}\beta_{2})^{2}}{\alpha^{2}}\,.\end{split}$
(19)

Then we define the event:

$A_{i,r}=\left\\{\exists:\left\|\bm{w}_{r}(t)-\bm{w}_{r}(0)\right\|\leq
R_{w},1\left\\{\bm{w}_{r}(0)^{\top}\bm{x}_{i}\geq 0\right\\}\neq
1\left\\{\bm{w}_{r}(t)^{\top}\bm{x}_{i}\geq 0\right\\}\right\\}\,.$

This event happens if and only if
$\left|\bm{w}_{r}(0)^{\top}\bm{x}_{i}\right|<R_{t}$. According to this, we can
get
$\mathbb{P}(A_{i,r})=\mathbb{P}_{z\sim\mathcal{N}(0,\beta_{1}^{2})}(\left|z\right|\leq
R_{w})\leq\frac{2R_{w}}{\sqrt{2\pi}\beta_{1}}$, further:

$\begin{split}\mathbb{E}\left|\bm{H}_{i,j}(t)-\widehat{\bm{H}}_{i,j}(t)\right|&=\frac{1}{\alpha^{2}}\mathbb{E}\bigg{|}\sum_{r=1}^{m}a_{r}(t)^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(t)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(t)^{\top}\bm{x}_{j}\geq 0\right\\}\\\
&-\sum_{r=1}^{m}a_{r}(t)^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{\bm{w}_{r}(0)^{\top}\bm{x}_{i}\geq
0,\bm{w}_{r}(0)^{\top}\bm{x}_{j}\geq 0\right\\}\bigg{|}\\\
&\leq\frac{1}{\alpha^{2}}\sum_{r=1}^{m}\mathbb{E}\bigg{(}a_{r}(t)^{2}\bm{x}_{i}^{\top}\bm{x}_{j}1\left\\{A_{i,r}\cup
A_{j,r}\right\\}\bigg{)}\\\
&\leq\frac{1}{\alpha^{2}}\sum_{r=1}^{m}\mathbb{E}\bigg{(}a_{r}(t)^{2}\frac{4R_{w}}{\sqrt{2\pi}\beta_{1}}\bigg{)}\\\
&=\frac{4R_{w}}{\alpha^{2}\sqrt{2\pi}\beta_{1}}\sum_{r=1}^{m}\mathbb{E}(a_{r}(t)^{2}-a_{r}(0)^{2}+a_{r}(0)^{2})\\\
&\leq\frac{4R_{w}m}{\alpha^{2}\sqrt{2\pi}\beta_{1}}\bigg{(}R_{a}(R_{a}+\sqrt{\frac{8}{\pi}}\beta_{2})+\beta_{2}^{2}\bigg{)}\,,\end{split}$
(20)

where the last inequality uses the result of Eq. 19.

From Eqs. (19) and (20), using Markov’s inequality. with probability at least
$1-\frac{2}{n}$, we have:

$\left|\widehat{\bm{H}}_{i,j}(t)-\bm{H}_{i,j}(0)\right|\leq\frac{nm(R_{a}+\sqrt{\frac{2}{\pi}}\beta_{2})^{2}}{\alpha^{2}}\,,$

$\left|\bm{H}_{i,j}(t)-\widehat{\bm{H}}_{i,j}(t)\right|\leq\frac{4R_{w}nm}{\alpha^{2}\sqrt{2\pi}\beta_{1}}\bigg{(}R_{a}(R_{a}+\sqrt{\frac{8}{\pi}}\beta_{2})+\beta_{2}^{2}\bigg{)}\,.$

Then we have:

$\begin{split}\left\|\bm{H}(t)-\bm{H}(0)\right\|_{2}&\leq\left\|\bm{H}(t)-\bm{H}(0)\right\|_{\mathrm{F}}\\\
&\leq\sum_{(i,j)=(1,1)}^{(n,n)}\left|\bm{H}_{i,j}(t)-\bm{H}_{i,j}(0)\right|\\\
&\leq\sum_{(i,j)=(1,1)}^{(n,n)}\bigg{(}\left|\widehat{\bm{H}}_{i,j}(t)-\bm{H}_{i,j}(0)\right|+\left|\bm{H}_{i,j}(t)-\widehat{\bm{H}}_{i,j}(t)\right|\bigg{)}\\\
&\leq\frac{mn^{3}}{\alpha^{2}}\bigg{(}(R_{a}+\sqrt{\frac{2}{\pi}}\beta_{2})^{2}+\frac{4R_{w}}{\sqrt{2\pi}\beta_{1}}(R_{a}(R_{a}+\sqrt{\frac{8}{\pi}}\beta_{2})+\beta_{2}^{2})\bigg{)}\,.\end{split}$

Then, by Eq. 17 we have:

$\left\|\bm{H}(t)-\bm{H}(0)\right\|_{2}\leq\frac{\lambda_{0}}{4}\,,$

which implies:

$\lambda_{\min}(\bm{H}(t))\leq\lambda_{\min}(\bm{H}(0))-\frac{\lambda_{0}}{4}\leq\frac{\lambda_{0}}{2}\,.$

∎

######  Lemma 9.

Suppose that for $0\leq s\leq t$,
$\lambda_{\min}(\bm{H}(s))\geq\frac{\lambda_{0}}{2}$ and
$\left|a_{r}(s)-a_{r}(0)\right|\leq R_{a}$. Then with probability at least
$1-n\exp(-n/2)$ over initialization we have
$\left\|\bm{w}_{r}(t)-\bm{w}_{r}(0)\right\|_{2}\leq R_{w}$ for all $r\in[m]$
and the $t\leq t_{1}^{\star}$.

###### Proof.

By Lemma 6, we have
$\frac{\mathrm{d}\bm{f}(t)}{\mathrm{d}t}=(\bm{H}(t)+\bm{G}(t))(\bm{y}-\bm{f}(t))$.
Then we can calculate the dynamics of risk function:

$\begin{split}\frac{\mathrm{d}}{\mathrm{d}t}\left\|\bm{y}-\bm{f}(t)\right\|_{2}^{2}&=-2(\bm{y}-\bm{f}(t))^{\top}(\bm{H}(t)+\bm{G}(t))(\bm{y}-\bm{f}(t))\\\
&\leq-2(\bm{y}-\bm{f}(t))^{\top}(\bm{H}(t))(\bm{y}-\bm{f}(t))\\\
&\leq-\lambda_{0}\left\|\bm{y}-\bm{f}(t)\right\|_{2}^{2}\,,\end{split}$

in the first inequality we use that the $\bm{G}(t)$ is Gram matrix thus it is
positive. Then we have
$\frac{\mathrm{d}}{\mathrm{d}t}\bigg{(}e^{\lambda_{0}t}\left\|\bm{y}-\bm{f}(t)\right\|_{2}^{2}\bigg{)}\leq
0$, then $e^{\lambda_{0}t}\left\|\bm{y}-\bm{f}(t)\right\|_{2}^{2}$ is a
decreasing function with respect to $t$. Thus, we can bound the risk:

$\left\|\bm{y}-\bm{f}(t)\right\|_{2}^{2}\leq
e^{-\lambda_{0}t}\left\|\bm{y}-\bm{f}(0)\right\|_{2}^{2}\,.$ (21)

Then we bound the gradient of $\bm{w}_{r}$. For $0\leq s\leq t$, With
probability at least $1-n\exp(-n/2)$ we have:

$\begin{split}\left\|\frac{\mathrm{d}}{\mathrm{d}s}\bm{w}_{r}(s)\right\|_{2}&=\left\|\frac{1}{\alpha}\sum_{i=1}^{n}[f(\bm{W}(s),\bm{a}(s),\bm{x}_{i})-y_{i}]a_{r}(s)1\left\\{\bm{w}_{r}^{\top}(s)\bm{x}_{i}\geq
0\right\\}\bm{x}_{i}\right\|_{2}\\\
&\leq\frac{1}{\alpha}\sum_{i=1}^{n}\left|f(\bm{W}(s),\bm{a}(s),\bm{x}_{i})-y_{i}\right|\left|a_{r}(0)+R_{a}\right|\\\
&\leq\frac{\sqrt{n}}{\alpha}\left\|\bm{y}-\bm{f}(s)\right\|_{2}(\sqrt{n}\beta_{2}+R_{a})\\\
&\leq\frac{\sqrt{n}}{\alpha}(\sqrt{n}\beta_{2}+R_{a})e^{-\lambda_{0}s/2}\left\|\bm{y}-\bm{f}(0)\right\|_{2}\,,\end{split}$

where the second inequality is because of
$a_{r}(0)\sim\mathcal{N}(0,\beta_{2}^{2})$, then with probability at least
$1-\exp(-n/2)$ we have $a_{r}(0)\leq\sqrt{n}\beta_{2}$. Then we have:

$\left\|\bm{w}_{r}(t)-\bm{w}_{r}(0)\right\|_{2}\leq\int_{0}^{t}\left\|\frac{\mathrm{d}}{\mathrm{d}s}\bm{w}_{r}(s)\right\|_{2}\mathrm{d}s\leq\frac{2\sqrt{n}}{\lambda_{0}\alpha}(\sqrt{n}\beta_{2}+R_{a})\left\|\bm{y}-\bm{f}(0)\right\|_{2}(1-\exp(-\frac{\lambda_{0}t}{2}))\,.$
(22)

If we account for $t$, then we conclude the proof. ∎

######  Lemma 10.

Suppose that for $0\leq s\leq t$,
$\lambda_{\min}(\bm{H}(s))\geq\frac{\lambda_{0}}{2}$ and
$\left\|\bm{w}_{r}(s)-\bm{w}_{r}(0)\right\|_{2}\leq R_{w}$. Then with
probability at least $1-\frac{1}{n}$ over initialization we have
$\left|a_{r}(t)-a_{r}(0)\right|\leq R_{a}$ for all $r\in[m]$ and the $t\leq
t_{2}^{\star}$.

###### Proof.

Note for any $i\in[n]$ and $r\in[m]$,
$\bm{w}_{r}^{\top}(0)\bm{x}_{i}~{}\sim\mathcal{N}(0,\beta_{1}^{2})$. Therefore
applying Gaussian tail bound and union bound we have with probability at least
$1-\frac{1}{n}$, for all $i\in[n]$ and $r\in[m]$,
$\left|\bm{w}_{r}^{\top}(0)\bm{x}_{i}\right|\leq
3\beta_{1}\sqrt{\log(mn^{2})}$, That means for $0\leq s\leq t$, With
probability at least $1-\frac{1}{n}$ we have:

$\begin{split}\left|\frac{\mathrm{d}}{\mathrm{d}s}a_{r}(s)\right|&=\left|\frac{1}{\alpha}\sum_{i=1}^{n}[f(\bm{W}(t),\bm{a}(t),\bm{x}_{i})-y_{i}]\sigma(\bm{w}_{r}^{\top}(t)\bm{x}_{i})\right|\\\
&\leq\frac{\sqrt{n}}{\alpha}\left\|\bm{y}-\bm{f}(s)\right\|_{2}(\left|\bm{w}_{r}^{\top}(0)\bm{x}_{i}\right|+R_{w})\\\
&\leq\frac{\sqrt{n}}{\alpha}e^{-\lambda_{0}s/2}\left\|\bm{y}-\bm{f}(0)\right\|_{2}\bigg{(}3\beta_{1}\sqrt{\log(mn^{2})}+R_{w}\bigg{)}\,.\end{split}$

Then we have:

$\small\left|a_{r}(t)-a_{r}(0)\right|_{2}\leq\int_{0}^{t}\left|\frac{\mathrm{d}}{\mathrm{d}s}a_{r}(s)\right|\mathrm{d}s\leq\frac{2\sqrt{n}}{\lambda_{0}\alpha}\bigg{(}3\beta_{1}\sqrt{\log(mn^{2})}+R_{w}\bigg{)}\left\|\bm{y}-\bm{f}(0)\right\|_{2}(1-\exp(-\frac{\lambda_{0}t}{2}))\,.$
(23)

Bring in $t$, then finish the proof.

∎

######  Lemma 11.

Suppose $0\leq t\leq\min(t_{1}^{\star},t_{2}^{\star})$. Then with probability
at least $1-n\exp(-n/2)-\frac{3}{n}$ over initialization we have:
$\lambda_{\min}(\bm{H}(t))\geq\frac{\lambda_{0}}{2}$,

$\left|a_{r}(t)-a_{r}(0)\right|\leq\frac{2\sqrt{n}}{\lambda_{0}\alpha}\bigg{(}3\beta_{1}\sqrt{\log(mn^{2})}+R_{w}\bigg{)}\left\|\bm{y}-\bm{f}(0)\right\|_{2}(1-\exp(-\frac{\lambda_{0}t}{2})):=R_{a}^{\star}(t)\,,$

$\left\|\bm{w}_{r}(t)-\bm{w}_{r}(0)\right\|_{2}\leq\frac{2\sqrt{n}}{\lambda_{0}\alpha}(\sqrt{n}\beta_{2}+R_{a})\left\|\bm{y}-\bm{f}(0)\right\|_{2}(1-\exp(-\frac{\lambda_{0}t}{2})):=R_{w}^{\star}(t)\,,$

for all $r\in[m]$.

###### Proof.

When $t=0$, $\lambda_{\min}(\bm{H}(s))\geq\frac{3}{4}\lambda_{0}$,
$\left|a_{r}(t)-a_{r}(0)\right|=0<R_{a}$ and
$\left\|\bm{w}_{r}(t)-\bm{w}_{r}(0)\right\|_{2}=0<R_{w}$. Using induction,
combine Lemma 8, Lemma 9 and Lemma 10, we have the result. ∎

###  D.2 Proof of Theorem 3

###### Proof.

We can compute the gradient of the network that:

$\nabla_{\bm{x}}\bm{f}_{t}(\bm{x})=\frac{1}{\alpha}\sum_{r=1}^{m}a_{r}(t)1\left\\{\bm{w}_{r}^{\top}(t)\bm{x}\geq
0\right\\}\bm{w}_{r}^{\top}(t)\,.$

∎

Then we can derive that:

$\begin{split}\mathscr{P}(\bm{f}_{t},\epsilon)&=\mathbb{E}_{\bm{x},\hat{\bm{x}}}\left|\frac{1}{\alpha}\sum_{r=1}^{m}a_{r}(t)1\left\\{\bm{w}_{r}^{\top}(t)\bm{x}\geq
0\right\\}\bm{w}_{r}^{\top}(t)(\bm{x}-\bm{\hat{x}})\right|\\\
&\leq\frac{1}{\alpha}\mathbb{E}_{\bm{x},\hat{\bm{x}}}\sum_{r=1}^{m}\left|a_{r}(t)\bm{w}_{r}^{\top}(t)(\bm{x}-\bm{\hat{x}})\right|\\\
&\leq\frac{1}{\alpha}\mathbb{E}_{\bm{x},\hat{\bm{x}}}\sum_{r=1}^{m}\left|a_{r}(t)\right|\left\|\bm{w}_{r}(t)\right\|_{2}\left\|\bm{x}-\bm{\hat{x}}\right\|_{2}\\\
&\leq\frac{\epsilon}{\alpha}\sum_{r=1}^{m}\left|a_{r}(t)\right|\left\|\bm{w}_{r}(t)\right\|_{2}\,.\end{split}$
(24)

Then by Lemma 11, we have:

$\left|a_{r}(t)\right|\leq\left|a_{r}(t)-a_{r}(0)\right|+\left|a_{r}(0)\right|\leq
R_{a}^{\star}(t)+\left|a_{r}(0)\right|\,.$

$\left\|\bm{w}_{r}(t)\right\|_{2}\leq\left\|\bm{w}_{r}(t)-\bm{w}_{r}(0)\right\|_{2}+\left\|\bm{w}_{r}(0)\right\|_{2}\leq
R_{w}^{\star}(t)+\left\|\bm{w}_{r}(0)\right\|_{2}\,.$

From Eq. 19, we have
$\mathbb{E}\left|a_{r}(0)\right|=\sqrt{\frac{2}{\pi}}\beta_{2}$. That means
with probability at least $1-\frac{1}{n}$ over initialization we have
$\left|a_{r}(0)\right|\leq\sqrt{\frac{2}{\pi}}n\beta_{2}$.

By Vershynin [2018, Chapter 3], with probability at least $1-\delta$ over
initialization, we have $\left\|\bm{w}_{r}(0)\right\|_{2}\leq
4\beta_{1}\sqrt{m}+2\beta_{1}\sqrt{\log n}$.

By combining the results above with Eq. 24 and Lemma 11, with probability at
least $1-n\exp(-n/2)-\frac{3}{n}$ over initialization we obtain that:

$\begin{split}\mathscr{P}(\bm{f}_{t},\epsilon)&\leq\frac{\epsilon}{\alpha}\sum_{r=1}^{m}\left|a_{r}(t)\right|\left\|\bm{w}_{r}(t)\right\|_{2}\\\
&\leq\frac{\epsilon
m}{\alpha}(R_{a}^{\star}(t)+\sqrt{\frac{2}{\pi}}n\beta_{2})(R_{w}^{\star}(t)+4\beta_{1}\sqrt{m}+2\beta_{1}\sqrt{\log
n})\end{split}$ (25)

Suppose that $\alpha\sim 1$,
$\beta_{1}\sim\beta_{2}\sim\beta\sim\frac{1}{m^{c}}$, $c\geq 1.5$, $m\gg
n^{2}$. Then $R_{a}=\Theta(\frac{1}{\sqrt{n^{3}m}})$,
$R_{w}=\Theta(\frac{1}{m^{c}})$, $R_{a}^{\star}(t)=\Theta(\frac{\sqrt{n\log
m}}{m^{c}})$ and $R_{w}^{\star}(t)=\Theta(\frac{1}{\sqrt{n^{3}m}})$. Bring
these results into Eq. 25, with probability at least
$1-n\exp(-\frac{n}{2})-\frac{3}{n}$ over initialization we have:

$\mathscr{P}(\bm{f}_{t},\epsilon)\leq\Theta\bigg{(}\epsilon\frac{\sqrt{n\log
m}+n}{m^{c-1}}\bigg{(}\frac{1}{\sqrt{n^{3}m}}+\frac{1}{m^{c-0.5}}\bigg{)}\bigg{)}\,.$

##  Appendix E Additional Experiments

A number of additional experiments are conducted in this section. Unless
explicitly mentioned otherwise, the experimental setup remains similar to the
one in the main paper. The following experiments are conducted below:

  1. 1.

In Section E.1, we compare the two different training regimes, lazy training
and non-lazy training.

  2. 2.

In Section E.2, we conduct some experiments to verify the reasonableness of
using the early-stop training in the paper.

  3. 3.

In Section E.3, we extend the experiments in Section 5.3 from fully connected
network to Convolutional Neural Network.

  4. 4.

In Section E.4, we extend the experiments to some other initializations under
non-lazy training regime.

  5. 5.

In Section E.5, we extend the experiments from He and LeCun initialization to
NTK initialization.

  6. 6.

In Section E.6, we extend in Section 5.3 from fully connected network to
ResNet.

###  E.1 Comparison of Lazy training and Non-lazy training

In this section, we test the performance of lazy training regime and non-lazy
training regime on practical task and networks. We choose the ResNet-110
model333https://github.com/bearpaw/pytorch-classification for these
experiments. We adopt a narrow model width for computational efficiency. We
utilize the He initialization and the non-lazy training initialization as
mentioned in Section 5.1 on two commonly used datasets CIFAR10 and CIFAR100,
of which results are provided in Table 4. Notice that the non-lazy training
regime achieves a similar performance to lazy training regime. This implies
that non-lazy training regime is also needed for studying practical learning
tasks.

Table 4: Comparison results of lazy training regime and non-lazy training regime of ResNet-110 under practical network/datasets. Dataset | Lazy training | Non-lazy training
---|---|---
CIFAR10 | $92.89\%$ | $92.14\%$
CIFAR100 | $71.08\%$ | $70.55\%$

###  E.2 Ablation study for why we use early stopping (training 50 epochs)

In this section, we conduct some experiments to verify the reasonableness of
using the early-stop training (50 epochs) method in the paper. The
experimental results shown in Fig. 6 indicate that the loss and accuracy of
the neural network almost not change from the 50th epoch to the 200th epoch
under two different network settings: width = 32, depth = 4 and width = 64,
depth = 8. Such results verify the rationality of our choice to run 50 epochs.

Figure 6: Verify the reasonableness of using the early-stop training, (a)
accuracy and (b) loss for network with width=32 and depth=4, (c) accuracy and
(d) loss for network with width=64 and depth=8

###  E.3 Extend the experiment in Section 5.3 to CNN

In this section, we extend the experiments in Section 5.3 from fully connected
networks to convolutional neural networks in Fig. 7. Compared with the fully
connected network, the main difference of the convolutional neural network is
that the gap between different depths is much larger than fully connected
network, which is more in line with the relationship between robustness and
depth under He initialization in Theorem 1.

Figure 7: Relationship between _perturbation stability_ and width of CNN under
He initialization for different depths of $L=4,6,8$ and $10$.

###  E.4 More experiments in non-lazy training regime

In this section, we extend the experiments of Fig. 4(b) to more
initializations under non-lazy training regime (the variance of the initial
weight are $\frac{1}{m^{3}}$ and $\frac{1}{m^{4}}$). Fig. 8 provides the
relationship between robustness and width of neural network for these two
initializations and shows that the robustness improves with the increase of
the width of network which consistent with Theorem 3, but the difference
between different initializations is not as large as our theoretical
expectation, which may indicate that the bound in Theorem 3 is not tight
enough.

Figure 8: Influence of width of neural network on perturbation stability under
non-lazy training regime. (a) the variance of the initial weight is
$\frac{1}{m^{3}}$. (b) the variance of the initial weight is
$\frac{1}{m^{4}}$.

###  E.5 More experiments in under NTK initialization

In this section, we extend the experiments in Fig. 5 from He and LeCun
initialization to NTK initialization in Fig. 9. Our experimental results show
that, NTK initialization and He initialization yield similar curves, but
differs in the curve of $L=2$. This may be because the infinite-width NTK is
equivalent to the linear model, and the large finite-width network
approximates the linear model. This phenomenon can be more easily detected for
two-layer neural networks when compared to deeper networks.

Figure 9: Relationship between _perturbation stability_ and depth of FCN under
NTK initialization with different depths of $L=2,6$ and $10$.

###  E.6 More experiments on ResNet

In this section, we extend the experiments in Section 5.3 from fully connected
networks to ResNet in Fig. 10. Compared with the fully connected network, the
results of ResNet show similar characteristics to our theory on fully
connected networks. Specifically, the perturbation stability increases with
depth, and an insignificant phase transition can also be seen for width.

Figure 10: Relationship between _perturbation stability_ and width of
ResNet-18 and ResNet-34.

##  Appendix F Limitation and discussion

The limitation of this work is mainly manifested in that Theorem 3 is built on
two-layers neural networks. Extending this results to deep neural networks
beyond lazy training regime is non-trivial. Firstly, the dynamics of the deep
neural network and the bounds of the gap between the initialization and the
expectation of the gram matrix will become more complex. Secondly, due to the
coupling relationship between different layers, the critical change radius of
the weight in Lemma 8 is also coupled with each other and is difficult to
analyze. Then, due to the superposition of the previous two points, the
relationship between the weights changing with time in the early stage of
training (similar to Lemma 9) and the width and initialization of the neural
network will be difficult to distinguish, which leads to the final result
being complex, demanding and difficult to obtain a valid conclusion about
width and initialization.

##  Appendix G Societal impact

This is a theoretical work that explores the interplay of the width, the depth
and the initialization of neural networks on their average robustness. Our
goal is to deepen the understanding of the community in the factors that
affect the robustness. We do not focus on obtaining any state-of-the-art
results in a particular task, which means there are other works that can be
used for forming strong adversarial attacks and can be used with malicious
intent.

Despite the theoretical nature of our work, we encourage researchers to
further investigate the impact of robustness on the society. We expect
robustness to have a key role into a world where neural networks are
increasingly deployed into real-world applications.