# Adversarial Robustness is at Odds with Lazy Training

Yunjuan Wang
Department of Computer Science
Johns Hopkins University
Baltimore, MD, 21218
<EMAIL_ADDRESS>
&Enayat Ullah
Department of Computer Science
Johns Hopkins University
Baltimore, MD, 21218
<EMAIL_ADDRESS>
Poorya Mianjy
Department of Computer Science
Johns Hopkins University
Baltimore, MD, 21218
<EMAIL_ADDRESS>
&Raman Arora
Department of Computer Science
Johns Hopkins University
Baltimore, MD, 21218
<EMAIL_ADDRESS>

###### Abstract

Recent works show that adversarial examples exist for random neural networks
(Daniely and Shacham, 2020) and that these examples can be found using a
single step of gradient ascent (Bubeck et al., 2021). In this work, we extend
this line of work to “ _lazy training_ ” of neural networks – a dominant model
in deep learning theory in which neural networks are provably efficiently
learnable. We show that over-parametrized neural networks that are guaranteed
to generalize well and enjoy strong computational guarantees remain vulnerable
to attacks generated using a single step of gradient ascent.

##  1 Introduction

Despite the tremendous success of deep learning, recent works have
demonstrated that neural networks are extremely susceptible to attacks. One
such vulnerability is due to arbitrary adversarial corruption of data at the
time of prediction, commonly referred to as _inference-time attacks_ (Biggio
et al., 2013; Szegedy et al., 2014). Such attacks are catastrophically
powerful, especially in settings where adversaries can directly access the
model parameters. By adding crafted imperceptible perturbations on the natural
input, such attacks are easily realized across various domains, including in
computer vision where an autonomous driving car may misclassify traffic signs
(Sitawarin et al., 2018), in natural language processing where automatic
speech recognition misinterprets the meaning of a sentence (Schönherr et al.,
2019), among many others.

The potential threat of adversarial examples has led to serious concerns
regarding the security and trustworthiness of neural network-based models that
are increasingly being deployed in real-world systems. It is crucial,
therefore, to understand why trained neural networks classify clean data with
high accuracy yet remain extraordinarily fragile due to strategically induced
perturbations.

One of the earliest works to describe adversarial examples was that of Szegedy
et al. (2014), motivated by the need for networks that not only generalize
well but are also robust to small perturbations of its input. This was
followed by a body of works that finds adversarial examples using various
methods (Goodfellow et al., 2015; Papernot et al., 2016; Madry et al., 2018;
Carlini and Wagner, 2017a, b). Although lots of defense algorithms have been
designed, most of them are quickly defeated by stronger attacks (Carlini and
Wagner, 2017a; Carlini et al., 2019; Tramèr et al., 2020). Much of the prior
work has focused on this empirical “arms race” between adversarial defenses
and attacks; yet, a deep theoretical understanding of why adversarial examples
exist has been somewhat limited.

Recently, a line of work theoretically constructs adversarial attacks for
random neural networks. Inspired by the work of Shamir et al. (2019), Daniely
and Shacham (2020) prove that small $\ell_{2}$-norm adversarial perturbations
can be found by multi-step gradient ascent method for random ReLU networks
with small width – each layer has vanishingly small width compared to the
previous layer. Bubeck et al. (2021) generalize this result to two-layer
randomly initialized networks with relatively large network width and show
that a single step of gradient ascent suffices to find adversarial examples.
Bartlett et al. (2021) further generalize this result to random multilayer
ReLU networks. However, all of the works above focus on random neural networks
and fail to explain why adversarial examples exist for neural networks trained
using stochastic gradient descent. In other words, _why do neural networks
that are guaranteed to generalize well remain vulnerable to adversarial
attacks?_

In this paper, we make progress toward addressing that question. In
particular, we show that adversarial examples can be found easily using a
single step of gradient ascent for neural networks trained using first-order
methods. Specifically, we focus on over-parametrized two layer ReLU networks
which have been studied extensively in recent years due to their favorable
computational aspects. Several works have shown that under mild over-
parametrization (size of the network is polynomial in the size of the training
sample), the weights of two-layer ReLU networks stay close to initialization
throughout the training of the network using gradient descent-based methods
(Allen-Zhu et al., 2019; Ji and Telgarsky, 2020; Arora et al., 2019). In such
a “lazy regime” of training, the networks are locally linear which allows us
to give computational guarantees for minimizing the training loss (aka,
optimization) as well as bound the test loss (aka, generalization). The
purpose of our work is to show the deficiency of the lazy regime even though
it is the dominant framework in the theory of deep learning.

Our key contributions are as follows. We investigate the robustness of over-
parametrized neural networks, trained using lazy training, against inference-
time attacks. Building on the ideas of Bubeck et al. (2021), we show that such
trained neural networks still suffer from adversarial examples which can be
found using a single step of gradient ascent.

In particular, we show that an adversarial perturbation of size
$O(\frac{\|{\textrm{x}}\|}{\sqrt{d}})$ in the direction of the gradient
suffices to flip the prediction of two-layer ReLU networks trained in the lazy
regime – these are networks with all weights at a distance of
$O(\frac{1}{\sqrt{m}})$ from their initialization, where $m$ is the width of
the network. To the best of our knowledge, this is the first work which shows
that networks with small generalization error are still vulnerable to
adversarial attacks.

Further, we validate our theory empirically. We confirm that a perturbation of
size $O(1/\sqrt{d})$ suffices to generate a strong adversarial example for a
trained two-layer ReLU networks.

The rest of the paper is organized as follows. In Section 2, we introduce the
preliminaries, give the problem setup, and discuss the related work. We
present our main result in Section 3, and give a proof sketch in Section 4. In
Section 5 we provide empirical support for our theory, and conclude with a
discussion in Section 6.

##  2 Preliminaries

#### Notation

Throughout the paper, we denote scalars, vectors and matrices, respectively,
with lowercase italics, lowercase bold and uppercase bold Roman letters, e.g.
$u$, u, and U. We use $[m]$ to denote the set $\\{1,2,\ldots,m\\}$. We use
$\|\cdot\|$ or $\|\cdot\|_{2}$ exchangeably for $\ell_{2}$-norm. Given a
matrix
$\textrm{U}=[{\textrm{u}}_{1},\ldots,{\textrm{u}}_{m}]\in\mathbb{R}^{d\times
m}$, we define $\|\textrm{U}\|_{2,\infty}=\max_{s\in[m]}\|{\textrm{u}}_{s}\|$.
We use $\mathcal{B}_{2}({\textrm{u}},R)$ to denote the $\ell_{2}$ ball
centered at u of radius $R$. For any $\textrm{U}\in\mathbb{R}^{d\times m}$, we
use
$\mathcal{B}_{2,\infty}(\textrm{U},R)=\\{\textrm{U}^{\prime}\in\mathbb{R}^{d\times
m}\mid\|\textrm{U}^{\prime}-\textrm{U}\|_{2,\infty}\leq R\\}$ to denote the
$\ell_{2,\infty}$ ball centered at U of radius $R$. For any function
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$, $\nabla f$ denotes the gradient
vector. We define the standard normal distribution as $\mathcal{N}(0,1)$, and
the standard multivariate normal distribution as
$\mathcal{N}(0,\textrm{I}_{d})$. We use $\mathbb{S}^{d-1}$ to denote the unit
sphere in $d$ dimensions. We use the standard O-notation ($O$ and $\Omega$).

###  2.1 Problem Setup

Let $\mathcal{X}\subseteq\mathbb{R}^{d}$ and $\mathcal{Y}$ denote the input
space and the label space, respectively. In this paper, we focus on the binary
classification setting where $\mathcal{Y}=\\{-1,+1\\}$. We assume that the
data $({\textrm{x}},y)$ is drawn from an unknown joint distribution
$\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$. For a function
$f_{{\textrm{w}}}:\mathcal{X}\to\mathcal{Y}$ parameterized by w in some
parameter space $\mathcal{W}$, the _generalization error_ captures the
probability that $f_{\textrm{w}}$ makes a mistake on a sample drawn from
$\mathcal{D}$:

$\displaystyle\text{generalization
error}:=P_{({\textrm{x}},y)\sim\mathcal{D}}(yf_{\textrm{w}}({\textrm{x}})\leq
0).$

For a fixed ${\textrm{x}}\in\mathcal{X}$, we consider norm-bounded adversarial
perturbations given by $\mathcal{B}_{2}({\textrm{x}},R)$, for some fixed
perturbation budget $R$. The robust loss on x is defined as

$\displaystyle\ell_{R}({\textrm{w}};{\textrm{x}},y)=\max_{{\textrm{x}}^{\prime}\in\mathcal{B}_{2}({\textrm{x}},R)}{\mathds{1}}\left(yf_{\textrm{w}}({\textrm{x}}^{\prime})\leq
0\right).$

The _robust error_ then captures the probability that there exists an
adversarial perturbation on samples drawn from $\mathcal{D}$ such that
$f_{\textrm{w}}$ makes a mistake on the perturbed point

$\displaystyle
L_{R}({\textrm{w}};\mathcal{D}):=\mathbb{E}_{({\textrm{x}},y)\sim\mathcal{D}}[\ell_{R}({\textrm{w}};{\textrm{x}},y)].$

In this work, we focus on two-layer neural networks with ReLU activation,
parameterized by a pair of weight matrices $({\textrm{a}},\textrm{W})$,
computing the following function:

$f({\textrm{x}};{\textrm{a}},\textrm{W}):=\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\sigma({\textrm{w}}_{s}^{\top}{\textrm{x}}).$

Here, $m$ corresponds to the number of hidden nodes, i.e., the width of the
network; $\sigma(z)=\max\\{0,z\\}$ is the ReLU activation function, and
$\textrm{W}=[{\textrm{w}}_{1},\ldots,{\textrm{w}}_{m}]\in\mathbb{R}^{d\times
m}$ and ${\textrm{a}}=[a_{1},\ldots,a_{m}]\in\mathbb{R}^{m}$ denote the top
and the bottom layer weight matrices, respectively.

In this work, we study the robustness of neural networks which are close to
their initialization. In particular, we are interested in the _lazy regime_ ,
defined as follows.

######  Definition 2.1 (Lazy Regime).

Initialize the top and bottom layer weights as
$a_{s}\sim\operatorname{unif}(\\{-1,+1\\})$ and
${\textrm{w}}_{s,0}\sim\mathcal{N}({\textrm{0}},\textrm{I}_{d}),\forall
s\in[m]$. Let
$\textrm{W}_{0}=[{\textrm{w}}_{s,1},\ldots,{\textrm{w}}_{s,m}]\in\mathbb{R}^{d\times
m}$ The _lazy regime_ is the set of all networks parametrized by
$({\textrm{a}},\textrm{W})$, such that
$\textrm{W}\in\mathcal{B}_{2,\infty}(\textrm{W}_{0},C_{0}/\sqrt{m})$, for some
constant $C_{0}$.

###  2.2 Related Work

#### Adversarial Examples.

The field of adversarially robust machine learning has received significant
attention starting with the seminal work of Szegedy et al. (2014). Most
existing works focus on proposing methods to generate adversarial examples,
for example, the fast gradient sign method (FGSM) (Goodfellow et al., 2015),
the projected gradient descent (PGD) method (Madry et al., 2018), the Carlini
& Wagner attack (Carlini and Wagner, 2017b), to name a few.

Most related to our work are those on proving the existence of adversarial
examples on random neural networks. This line of work initiated with the work
of Shamir et al. (2019), where authors propose an algorithm to generate
bounded $\ell_{0}$-norm adversarial perturbation with guarantees for arbitrary
deep networks. Shortly afterwards, Daniely and Shacham (2020) showed that
multi-step gradient descent can find adversarial examples for random ReLU
networks with small width (i.e. $m=o(d)$). More recently, work of Bubeck et
al. (2021) shows that a single gradient ascent update finds adversarial
examples for sufficiently wide randomly initialized ReLU networks. This was
later extended to multi-layer networks with the work of Bartlett et al.
(2021). A very recent work of Vardi et al. (2022) shows that gradient flow
induces a bias towards non-robust networks. Our focus and techniques here are
different – we show that independent of the choice of the training algorithm,
all neural networks trained in the lazy regime remain vulnerable to
adversarial attacks.

#### Over-parametrized Neural Networks.

Our investigation into the existence of adversarial examples in the lazy
regime is motivated by recent advances in deep learning theory. In particular,
a series of recent works establish generalization error bounds for first-order
optimization methods under the assumption that the weights of the network do
not move much from their initialization (Jacot et al., 2018; Allen-Zhu et al.,
2019; Arora et al., 2019; Chen et al., 2021; Ji and Telgarsky, 2020; Cao and
Gu, 2020). In particular, Chizat et al. (2019) recognize that “lazy training”
phenomenon is due to a choice of scaling that makes the model behave as its
linearization around the initialization. Interestingly, linearity has been
hypothesized as key reason for existence of adversarial examples in neural
networks (Goodfellow et al., 2015). Furthermore, this was used to prove
existence of adversarial attacks for random neural networks (Bubeck et al.,
2021; Bartlett et al., 2021) and also provide the basis of our analysis in
this work.

##  3 Main Results

In this section, we present our main result. We assume that the data is
normalized so that $\|{\textrm{x}}\|_{2}=1$. We show that under the lazy
regime assumption, a single gradient step on $f$ suffices to find an
adversarial example to flip the prediction, given the network width is
sufficiently wide but not excessively wide.

######  Theorem 3.1 (Main Result).

Let ${\textrm{w}}_{s,0}\sim N(0,\textrm{I}_{d})$,
${\textrm{a}}\sim\textrm{unif}(\\{\\-1,+1\\})$ and $\gamma\in(0,1)$. For any
given ${\textrm{x}}\in\mathbb{S}^{d-1}$, with probability at least $1-\gamma$,
the following holds simultaneously for all
$\textrm{W}\in\mathcal{B}_{2,\infty}(\textrm{W}_{0},C_{0}/\sqrt{m})$

$\displaystyle{\textrm{sign}}(f({\textrm{x}};{\textrm{a}},\textrm{W}))\neq{\textrm{sign}}(f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W}))$

where
$\delta=\eta\nabla_{{\textrm{x}}}f({\textrm{x}};{\textrm{a}},\textrm{W})$,
provided that the following conditions are satisfied:

  1. 1.

Step Size: $\displaystyle|\eta|=\frac{C_{2}}{\|\nabla
f(x;{\textrm{a}},\textrm{W})\|^{2}}$,

  2. 2.

Width requirement:
$\displaystyle\max\left\\{d^{2.4},C_{3}\log\Big{(}\frac{1}{\gamma}\Big{)}\right\\}\leq
m\leq C_{4}\exp(d^{0.24}),$

where $C_{0},C_{2},C_{3},C_{4}$ are constants independent of width $m$ and
dimension $d$.

Several remarks are in order.

We note that the setting in Theorem 3.1 is motivated by the popular gradient
ascent based attack model which has been shown to be fairly effective in
practice. While in practice, we perform multiple steps of projected gradient
ascent to generate an adversarial perturbation, here we show that a single
step of gradient suffices with a small step size of $O(1/d)$. This attests to
the claim that over-parameterized neural networks trained in the lazy regime
remain quite vulnerable to adversarial examples. We confirm our findings
empirically in Section 5.

Our analysis suggests that an attack size of $O(1/\sqrt{d})$ suffices, i.e.,
for any x a perturbation $\delta$ of size $\|\delta\|=O(1/\sqrt{d})$ can flip
the sign of $f({\textrm{x}})$. This is a relatively small budget for
adversarial perturbations, especially for for high-dimensional data. Indeed,
in practice, we find that a noise budget of this size allows for adversarial
attacks on neural networks trained on real datasets such as MNIST and CIFAR-10
(Madry et al., 2018). Interestingly, we find in our experiments, that
$O(1/\sqrt{d})$ is the “right” perturbation budget in the sense that there is
a sharp drop in robust accuracy. More details are provided in Section 5.

Our investigation focuses on the settings wherein the weights of the trained
neural network stay close to the initialization. Further, given the
initialization scheme we consider, the $O(1/\sqrt{m})$ deviation of the
incoming weight vector at any neuron of the trained network from its
initialization precisely captures the neural tangent kernel (NTK) regime
studied in several prior works (Ji and Telgarsky, 2020; Du et al., 2018). This
$O(1/\sqrt{m})$ deviation bound is also the largest radius that we can allow
in our analysis; see Section 4 for further details. In fact, our results would
also hold for adversarial training given the same initialization and the bound
on the deviation of weights is met. Curiously, our empirical results exhibit a
phase transition around the perturbation budget of $O(1/\sqrt{m})$ – we see in
Section 5 that robust accuracy increases as we allow the network weights to
deviate more.

There is an interesting interplay between the network width and the input
dimensionality. Our results require that the network is sufficiently wide
(i.e., polynomially large in $d$), but not excessively wide (is sub-
exponential in $d$). The upper bound is large enough to allow for the over-
parameterization required in the NTK setting, as long as the input
dimensionality is sufficiently large.

To get an intuition about how the result follows, we first paraphrase the
arguments from Bubeck et al. (2021); Bartlett et al. (2021) for random neural
networks with weights $\textrm{W}_{0}$. We consider a linear model
$f({\textrm{w}};{\textrm{x}})=\frac{1}{\sqrt{d}}\sum_{s=1}^{d}{\textrm{w}}_{s,0}{\textrm{x}}_{s}$.
Since the initial weights are independent (sampled i.i.d. from
$\mathcal{N}(0,1)$), using standard concentration arguments, we have that for
large $d$, with high probability $|f({\textrm{w}}_{0};{\textrm{x}})|\leq
O(1)$. In contrast,
$\nabla_{{\textrm{x}}}f({\textrm{w}}_{0};{\textrm{x}})={\textrm{w}}$, so
$\|\nabla_{{\textrm{x}}}f({\textrm{w}}_{0};{\textrm{x}})\|=\|{\textrm{w}}\|$,
which is roughly $\Theta(\sqrt{d})$. Hence, for large enough $d$, a step of
gradient ascent suffices to change the sign of $f$.

The above reasoning can be extended to weights that are _close_ to random
weights. In particular, for arbitrary weights W close to the initialization,
consider the linear model:
$f({\textrm{w}};{\textrm{x}})=\frac{1}{\sqrt{d}}\sum_{s=1}^{d}{\textrm{w}}_{s}{\textrm{x}}_{s}$.
Since $\|{\textrm{w}}_{s}-{\textrm{w}}_{s,0}\|=O\left(1\right)$, thus even in
the worst case, the function still behaves as a constant translation of the
initial prediction model $f({\textrm{w}}_{0};{\textrm{x}})$, and thus is
constant. Similarly, $\|\nabla
f({\textrm{w}},{\textrm{x}})\|=\Omega(\sqrt{d})$.

The work of Bubeck et al. (2021) extends the above observation to ReLU
activation exploiting the fact that the function, even though non-linear, is
still locally linear. Note that, in a different context, this local linearity
property is central to the Neural Tangent Kernel regime. In particular, the
key underlying idea there is based on the linear approximation to the
prediction function. Furthermore, with appropriate initialization, a linear
approximation is not only good enough model close to the initialization, but
also enables tractable analysis. We collapse this “good” linearization
property under the lazy training assumption since that suffices for our
purposes.

Figure 1: Cone containing the lazy-regime ball around initialization
$\textrm{W}_{0}$.

#### Beyond Lazy regime.

Our result can be easily extended to a broader class of neural networks. In
particular, consider the cone $C=\\{\textrm{W}:\exists
r>0,r\textrm{W}\in\mathcal{B}_{2,\infty}(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}})\\}$;
see Figure 1. Note that for binary classification, scaling the network weights
with a positive factor does not change the prediction. As a result, Theorem
3.1 still holds for network weights which belong to the cone $C$ but may not
be in the lazy regime.

#### Robust Test Error.

As a corollary to Theorem 3.1, we have that none of the networks in the lazy
regime are robust, i.e., for all networks in the lazy regime, the robust test
error is bounded from below by a constant with high probability.

######  Corollary 3.2.

Let ${\textrm{w}}_{s,0}\sim N(0,\textrm{I}_{d})$,
${\textrm{a}}\sim\textrm{unif}(\\{-1,+1\\}),R=\tilde{O}({1}/{\sqrt{d}})$ and
$\gamma\in(0,1)$. In the parameter settings of Theorem 3.1, for any data
distribution $\mathcal{D}$ supported on the sphere $\mathbb{S}^{d-1}$, with
probability at least $1-10\gamma$ (over the draw of $\textrm{W}_{0}$ and a),
for all W s.t.
$\textrm{W}\in\mathcal{B}_{2,\infty}(\textrm{W}_{0},C_{0}/\sqrt{m})$, the
robust error $L_{R}(\textrm{W};\mathcal{D})\geq 0.9$.

We note that our result above is not a contradiction to the prior result of
Gao et al. (2019), which claims that adversarial training finds robust
classifiers in overparameterized models. Firstly, our result shows that there
is no robust classifier in the lazy regime (Definition 2.1). In contrast, Gao
et al. (2019) simply assume the existence of robust classifier in an NTK
setting; see (Gao et al., 2019, Assumption 5.2). Indeed, ignoring some of the
(potentially unimportant) differences between our setting and that of Gao et
al. (2019), (e.g., smooth vs. non-smooth activations and tied vs. non-tied
weights in the last layer), then our result may suggest that the assumption in
Gao et al. (2019) is incorrect. Secondly, the main result of Gao et al. (2019)
is to show that the excess robust training error of the output of adversarial
training is small. However, this only implies a small robust training error if
the best-in-class robust training error is also small, which, again, as we
discussed above, does not hold. Finally, despite the validity of the key
assumption in Gao et al. (2019), the authors only provide a bound on robust
training error. In contrast, our result shows that robustness may not hold in
the sense of robust test error.

##  4 Proof Sketch

In this section, we provide an outline of the proof of Theorem 3.1. Recall
that our goal is to show that for any given ${\textrm{x}}\in\mathbb{S}^{d-1}$,
the vector
$\delta=\eta\nabla_{{\textrm{x}}}f({\textrm{x}};{\textrm{a}},\textrm{W})$ is
such that $\|\delta\|\ll\|{\textrm{x}}\|$, and
${\textrm{sign}}(f({\textrm{x}};{\textrm{a}},\textrm{W}))\neq{\textrm{sign}}(f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W}))$.
Assume without loss of generality that
$f({\textrm{x}};{\textrm{a}},\textrm{W})>0$, then ${\textrm{sign}}(\eta)=-1$.
From the fundamental theorem of calculus, we have
$f({\textrm{x}}+\delta)=f({\textrm{x}})+\int_{0}^{1}f^{\prime}({\textrm{x}}+t\delta)dt.$
Using simple algebraic manipulations (see full proof in Appendix B), we have
the following,

$\displaystyle f({\textrm{x}}\\!+\\!\eta\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W});{\textrm{a}},\textrm{W})$
$\displaystyle\leq$
$\displaystyle\overbrace{f({\textrm{x}};{\textrm{a}},\textrm{W})}^{O(1)}-|\eta|\overbrace{\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|}^{\Omega(\sqrt{d})}$
$\displaystyle\qquad+|\eta|\overbrace{\sup_{\begin{subarray}{c}\delta\in\mathbb{R}^{d}:\\\
\|\delta\|\leq\eta\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|\end{subarray}}\|\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|}^{o(\sqrt{d})}$

The goal now is to control each of the three terms on the right hand side.
Note that the suggested bounds on each of the terms will suffice to flip the
label, thereby establishing the main result.

Given any x and
$\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\right)$,
we need to control:

  1. 1.

The function value of neural network $f({\textrm{x}};{\textrm{a}},\textrm{W})$

  2. 2.

The size of the gradient of neural network $\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|$ with respect to the input x

  3. 3.

The size of the difference of gradients $\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})\|$ for $\|\delta\|\leq
O(1/\sqrt{d})$

###  4.1 Bounding the function value

######  Lemma 4.1.

(Informal) For any x, with probability at least $1-\gamma$,
$|f({\textrm{x}};{\textrm{a}},\textrm{W})|\leq 2\sqrt{\log(2/\gamma)}+C_{0}$
holds for all
$\textrm{W}\in\mathcal{B}_{2,\infty}\bigg{(}\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\bigg{)}$,
provided that $m\geq\Omega(\log(2/\gamma))$.

#### Proof Sketch:

From triangle inequality,

$\displaystyle|f({\textrm{x}};{\textrm{a}},\textrm{W})|\leq|f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|+|f({\textrm{x}};{\textrm{a}},\textrm{W})-f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|.$

For the first term, we have from Bubeck et al. (2021) that
$|f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|=O(1)$. For the second term
$|f({\textrm{x}};{\textrm{a}},\textrm{W})-f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|\leq
O\left(1\right)$ owing to the Lipschitzness of ReLU. Note that $O(1/\sqrt{m})$
is the largest deviation on $\|{\textrm{w}}_{s}-{\textrm{w}}_{s,0}\|$ that we
can allow to get the constant bound here.

We next move to the second and third terms. We note that while bounding the
first term simply follows from the Lipschitzness of the network, as we show in
the following sections, the second and third terms require a finer analysis,
due to the non-smoothness of ReLU.

###  4.2 Bounding the gradient

######  Lemma 4.2.

(Informal) For any x, with probability at least $1-\gamma$, $\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|\geq\frac{1}{4}\sqrt{d}$ holds for
all
$\textrm{W}\in\mathcal{B}_{2,\infty}(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}})$,
provided that $m\geq\Omega(\log(1/\gamma))$ and
$d\geq\Omega(\frac{\log(m/\gamma)}{m})$.

#### Proof Sketch:

Let $\textrm{P}:=\textrm{I}_{d}-{\textrm{x}}{\textrm{x}}^{\top}$ be the
projection matrix onto the orthogonal complement of x. Using triangle
inequality,

$\displaystyle\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|\geq\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|\geq\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|-\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|.$

The first term $\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|\geq\Omega(\sqrt{d})$, which
follows from Bubeck et al. (2021) with minor changes arising from different
scaling of the initialization.

We further decompose the second term,

$\displaystyle\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|$
$\displaystyle\\!\\!\\!\\!\leq\\!\\!\\!\\!$
$\displaystyle\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}({\textrm{w}}_{s}\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-{\textrm{w}}_{s,0}\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}}))\bigg{\|}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$
$\displaystyle+\ \
\bigg{\|}\sup_{\textrm{W}\in\mathcal{B}_{2,\infty}(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}})}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}.$

The first term is $O(1)$ simply from the fact that
$\|{\textrm{w}}_{s}-{\textrm{w}}_{0}\|\leq\frac{C_{0}}{\sqrt{m}}$. To bound
the second term, the key arguments are as follows: by definition of P, the
term $\textrm{P}{\textrm{w}}_{s,0}$ is independent of
$\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})$,
therefore, as in Bubeck et al. (2021), we can bound both of these terms
independently. Note that
$a_{s}\textrm{P}{\textrm{w}}_{s,0}\sim\mathcal{N}(0,\textrm{I}_{d-1})$.
Therefore, the second term is equal in distribution to the following random
variable:

where ${\textrm{z}}\sim\mathcal{N}(0,\textrm{I}_{d-1})$.

The term
$|\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})|=1$
only when the $s$-th neuron has different signs for incoming weights
${\textrm{w}}_{s,0}$ and ${\textrm{w}}_{s}$. So, at a high-level, we want to
bound the number of neurons changing sign between weights ${\textrm{w}}_{0}$
and w. To do this, we draw insights from results in the lazy training regime
that bound the number of such neurons in terms of deviations in weights. In
particular, the following lemma shows that with high probability, for all
$\textrm{W}\in\mathcal{B}_{2,\infty}(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}})$,
at most $O(\sqrt{m})$ neurons can have a sign different from their
initialization.

######  Lemma 4.3.

Let
$S_{v}:=\big{\\{}s\big{|}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\right),{\mathds{1}}[\langle{\textrm{w}}_{s},{\textrm{x}}\rangle>0]\neq{\mathds{1}}[\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle>0]\big{\\}}.$
Then, with probability at least $1-\gamma$, we have that $|S_{v}|\leq
C_{0}\sqrt{m}+\sqrt{\frac{m\log(1/\gamma)}{2}}.$

The key idea is that we can absorb the union bound in the definition of the
set above without compromising any increase in the size of the set. Putting
all of these pieces together yields the bound claimed in Lemma 4.2.

###  4.3 Bounding the difference of gradients

######  Lemma 4.4.

For any x, with probability at least $1-\gamma$, for all
$\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\right)$,
we have that $\sup_{r\in\mathbb{S}^{d-1},\delta\in\mathbb{R}^{d}}\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})\|\leq o(\sqrt{d}),$ provided
that $\|\delta\|\leq O(1/\sqrt{d})$, and $\displaystyle d^{2.4}\leq m\leq
O(\exp(d^{0.24}))$.

#### Proof Sketch:

It follows from the definition of norm that

$\displaystyle\|\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})\|$
$\displaystyle=\sup_{\begin{subarray}{c}r\in\mathbb{S}^{d-1},\delta\in\mathbb{R}^{d}\end{subarray}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{w}}_{s}^{\top}r\left(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))\right).$

The strategy, then, is to bound the right-hand side for fixed $r$ and
$\delta$, and then use an $\varepsilon$-net argument to bound the supremum. To
that end, define the following quantities:

$X_{s,0}=a_{s}{\textrm{w}}_{s,0}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta))),X_{s}=a_{s}{\textrm{w}}_{s}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))).$

Then, the norm of the difference of the gradients is upper bounded by

The first term
$\frac{1}{\sqrt{m}}\sum_{s=1}^{m}X_{s,0}=O((R\sqrt{\log(d)})^{1/4})$ which
follows from Bubeck et al. (2021) with minor changes due to the different
scale of the initialization. However, the second term requires a more careful
analysis. In particular, the difference $X_{s}-X_{s,0}$ includes deviations of
both variables x and W. Therefore, we need to expand the difference in terms
of each variable and carefully bound the resulting terms. Similar to the ideas
presented in the previous section, here we need to bound the size of the set
of neurons that can change sign under perturbations on both x and W. It turns
out that the size of this set is in the same order as the one in Lemma 4.3, as
long as the perturbation in x is $O(1)$.

##  5 Experiments

The primary goal of this section is to provide empirical support for our
theoretical findings. In particular, we want to verify how tight our
theoretical bounds are in practice, in terms of the size of the perturbation
needed and the interplay of robustness with training in the lazy regime. For
instance, are the trained models indeed vulnerable to small perturbations of
size $O(1/\sqrt{d})$ as suggested in Theorem 3.1? Is the assumption of
training in the lazy regime merely for analytical convenience or do we see a
markedly different behavior if we allow the iterates to deviate more than
$O(1/\sqrt{m})$ from initialization?

#### Datasets & Model specification.

We utilize the MNIST dataset for our empirical study. MNIST is a dataset of
$28\times 28$ greyscale handwritten digits (LeCun et al., 1998). We extract
examples corresponding to images of the digits ‘0’ and ‘1’, resulting in
$12665$ training examples and $2115$ test examples. To study the behaviour of
different quantities as a function of the input feature dimensionality, we
downsample the images by different factors to simulate data with $d$ ranging
between $25$ and $784$ (the original dimension). We use two-layer ReLU
networks with a fixed top layer to match our theory and use the initialization
described in Section 2.

###  5.1 Lazy regime for standard SGD

#### Setting.

For each $d\in\\{5^{2},7^{2},10^{2},14^{2},20^{2},25^{2},28^{2}\\}$, we set
the width of the network $m\in\\{1e3,1e4,1e5\\}$. We train the network using
standard SGD on the logistic loss using a learning rate of $0.1$. We denote
the weight matrix at the $t^{\text{th}}$ iterate of SGD as $\textrm{W}_{t}$
and the incoming weight vector into the $s^{\text{th}}$ hidden node at
iteration $t$ as ${\textrm{w}}_{s,t}$. The training terminates if the iterates
exit the lazy training regime, i.e., if $\sup_{1\leq s\leq
m}\|{\textrm{w}}_{s,t}-{\textrm{w}}_{s,0}\|>\frac{C_{0}}{\sqrt{m}}$. We
experiment with $C_{0}\in\\{10,20,30,40\\}$. We note that regardless of the
above stopping criterion, each of the trained models achieves a test error of
less than $1\%$. In other words, the models that our training algorithm
returns are guaranteed to satisfy the lazy regime assumption and generalize
well.

Given a trained neural network with parameters $(\textrm{W},{\textrm{a}})$,
for each test example x, we find the smallest step size $\eta$ such that the
perturbation $\delta=\eta\nabla_{\textrm{W}}f({\textrm{x}})$ flips the sign of
the prediction, i.e.,
$f_{\textrm{W}}({\textrm{x}})f_{\textrm{W}}({\textrm{x}}+\delta)<0.$ For each
experimental setting (i.e, for each value of $d$, $C_{0}$, and $m$), we report
results averaged over $5$ independent random runs.

#### Results.

|  |
---|---|---
Figure 2:  Minimal size of the perturbation vector needed to flip the predicted label (left), the norm of the gradient $\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})$ for W trained in the lazy regime (middle), and the corresponding step size (right), as a function of the input dimension $d$ for a fixed value of $C_{0}=10$ and different values of network widths ($m$). |  |
---|---|---
Figure 3:  Minimal size of the perturbation vector needed to flip the
predicted label (left), the norm of the gradient $\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})$ for W trained in the lazy regime
(middle), and the corresponding step size (right), as a function of the input
dimension $d$ for a fixed value of network width of $m=10^{5}$ and different
values of $C_{0}$.

The key quantities in our analysis are the step size $\eta$, the norm of the
gradient $\|\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})\|$, and the size of
the perturbation vector which is given as the product of the step size and the
norm of the gradient. In Figure 2, we plot these quantities as a function of
input dimension $d$, for a fixed $C_{0}$, for various values of width
$m\in\\{1e3,1e4,1e5\\}$ (corresponding to the curves in red, orange, and blue,
respectively). The green curves represent the corresponding theoretical bound.
As predicted by Theorem 3.1, the gradient norm behaves roughly as
$\Omega(\sqrt{d})$. Furthermore, the minimum step-size required to flip the
label, and the minimum size of the perturbation vector (normalized by the
input norm) behave as $O(1/d)$ and $O(1/\sqrt{d})$, respectively.

In Figure 3, we explore the behaviour of the key quantities as we allow for
larger deviations in the lazy regime, by allowing for larger values of
$C_{0},$ for a fixed network width of $m=10^{5}$. We see that as $C_{0}$
increases, both the size of the gradient and the minimum step size required to
flip the label increase, thereby increasing the size of the perturbation
vector needed to change the sign of the prediction. This suggests that
allowing the trained networks to deviate more from the initialization
potentially leads to models that are more robust (against the attack model
based on a single step of gradient ascent).

Remarkably, the minimum perturbation size, closely follows the $O(1/\sqrt{d})$
behaviour predicted by the theorem. This begets further investigation into the
required perturbation size, which is the focus of the next subsection.

###  5.2 Lazy regime for adversarial training

We begin by noting that our theoretical results are not limited to any
particular learning algorithm. In fact, the results hold simultaneously for
all networks in the lazy regime. In this section, we further verify our
theoretical results for networks that are adversarially trained in the lazy
regime.

#### Setting.

We downsample images as in the previous section to simulate data with
$d\in\\{5^{2},6^{2},7^{2},\ldots,28^{2}\\}.$ For this set of experiments, we
also normalize the data, so that $\|{\textrm{x}}\|=1$, to closely match the
setting of our theorem. We use projected gradient descent (PGD) (Madry et al.,
2018) for adversarial training. To ensure that the updates remain in the lazy
regime, after each gradient step, we project the weights onto
$\mathcal{B}_{2,\infty}(\textrm{W}_{0},V)$; see Algo. 1 in the appendix for
details. We experiment with values of $V$ and the size of $\|\delta\|$ in the
intervals $0.05\leq V\leq 1$ and $0.05\leq\|\delta\|\leq 1$, respectively.
These ranges are wide enough to include the $O(1/\sqrt{d})$ and
$O(1/\sqrt{m})$ theoretical bounds that we aim to verify here. We note that
the projection step is not commonly used in adversarial training; however, in
our experiments, it does not hurt the test accuracy of the trained models,
perhaps due to the simplicity of the classification task. At test time, we
generate the adversarial examples using the PGD attack instead of a single
gradient attack as in Section 5.1. We report the robust test accuracy averaged
over $5$ independent random runs of the experiment.

#### Results.

|
---|---
Figure 4: (Left):Robust test accuracy as a function of perturbation size
$\|\delta\|$ and dimension $d$, for a fixed network width of $m=1000$ and a
fixed value of maximal deviation of weight vectors of
$V=\frac{C_{0}}{\sqrt{m}}$ with $C_{0}=10$. (Right):Robust test accuracy as a
function of width $m$ and maximal deviation of weight vectors, $V$, for a
fixed dimension of $d=784$ and fixed perturbation size $\|\delta\|=0.2$.

For the experiments reported in Figure 4, left panel, we fix the network width
to $m=1000$ and set $V=\frac{C_{0}}{\sqrt{m}}=\frac{10}{\sqrt{1000}}=0.316$,
to check how the dimension $d$ and the perturbation budget affect the robust
accuracy. We observe a sharp drop in robust accuracy about the $5/\sqrt{d}$
threshold for the perturbation budget $\|\delta\|$ as predicted by Theorem
3.1. We can see that for perturbation sizes slightly larger than $5/\sqrt{d}$,
the robust accuracy drops to $0$, while the trained networks are robust
against smaller perturbations.

For the experiments reported in the right panel of Figure 4, we fix the input
dimensionality to $d=28^{2}$, and the perturbation size to $\|\delta\|=0.2$,
to check how the network width $m$ and the maximal deviation in weights, given
by $V$, affect the robust test accuracy. We observe a phase transition in the
robust test accuracy at value of $V$ around $O(1/\sqrt{m})$, as required by
Theorem 3.1. In particular, for any fixed width $m$, even a slight deviation
from the $25/\sqrt{m}$ radius allows for training networks that are completely
robust against the PGD attacks. With a smaller radius, however, the robust
test accuracy quickly drops to 0. This experiment suggests that adversarial
robustness may require going beyond the lazy regime.

#### Why MNIST?

We remark that our empirical demonstration on a simple dataset makes a
stronger case for our theoretical result. This is because the perturbation
size of $O(1/\sqrt{d})$ prescribed by our theoretical result is worst-case,
regardless of the dataset. So, in an easy setting like binary-MNIST, we would
expect our bound to be pessimistic and a smaller perturbation to be
sufficient. On the contrary, we see that even MNIST exhibits a perturbation-
dimension relationship that closely follows our theory. This can be regarded
as an empirical evidence of the tightness of our bounds.

##  6 Conclusion

In this paper, we study the robustness of two-layer neural networks trained in
the lazy regime against inference-time attacks. In particular, we show that
the class of networks for which the weights are close to the initialization
after training, are still vulnerable to adversarial attacks based on a single
step of gradient ascent with a perturbation of size
$O(\frac{\|{\textrm{x}}\|}{\sqrt{d}})$.

Our works suggests several research directions for future work. First, the
focus here is on two-layer networks, so a natural question is to ask whether
the same holds for multi-layer networks. Second, while we show that a single
step of gradient ascent-based attack is sufficient for our purposes, we expect
to get stronger results if we consider stronger attacks, for instance, with
gradient ascent based attack that is run to convergence. Third, our
experiments highlight an intriguing relationship between the width, the input
dimension, and the robust accuracy. So, a natural avenue is to understand
these dependencies more carefully. These include, figuring out the dependence
on the input dimensionality of the minimal perturbation required to generate
an adversarial example. Similarly, how does the robust error behave as a
function of the maximal distance of the weight vectors from the
initialization.

## Acknowledgments and Disclosure of Funding

This research was supported, in part, by the DARPA GARD award HR00112020004,
NSF CAREER award IIS-1943251, and the Spring 2022 workshop on “Learning and
Games” at the Simons Institute for the Theory of Computing.

## References

  * Allen-Zhu et al. [2019] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pages 242–252. PMLR, 2019.
  * Arora et al. [2019] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning_ , pages 322–332. PMLR, 2019.
  * Bartlett et al. [2021] Peter Bartlett, Sébastien Bubeck, and Yeshwanth Cherapanamjeri.  Adversarial examples in multi-layer random ReLU networks.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Biggio et al. [2013] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim $\check{\textrm{S}}$rndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli.  Evasion attacks against machine learning at test time.  In _Joint European conference on machine learning and knowledge discovery in databases_ , pages 387–402. Springer, 2013.
  * Bubeck et al. [2021] Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, and Rémi Tachet des Combes.  A single gradient step finds adversarial examples on random two-layers neural networks.  _Advances in Neural Information Processing Systems_ , 2021.
  * Cao and Gu [2020] Yuan Cao and Quanquan Gu.  Generalization error bounds of gradient descent for learning over-parameterized deep ReLU networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 3349–3356, 2020.
  * Carlini and Wagner [2017a] Nicholas Carlini and David Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In _Proceedings of the 10th ACM workshop on artificial intelligence and security_ , pages 3–14, 2017a.
  * Carlini and Wagner [2017b] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In _2017 IEEE symposium on security and privacy (SP)_ , pages 39–57. IEEE, 2017b.
  * Carlini et al. [2019] Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin.  On evaluating adversarial robustness.  _arXiv preprint arXiv:1902.06705_ , 2019.
  * Chen et al. [2021] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu.  How much over-parameterization is sufficient to learn deep relu networks?  In _9th International Conference on Learning Representations_ , 2021\.
  * Chizat et al. [2019] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  _Advances in Neural Information Processing Systems_ , 2019.
  * Daniely and Shacham [2020] Amit Daniely and Hadas Shacham.  Most ReLU networks suffer from $\ell^{2}$ adversarial perturbations.  _Advances in Neural Information Processing Systems_ , 33:6629–6636, 2020.
  * Du et al. [2018] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In _International Conference on Learning Representations_ , 2018.
  * Gao et al. [2019] Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang, and Jason D Lee.  Convergence of adversarial training in overparametrized neural networks.  _Advances in Neural Information Processing Systems_ , 32:13029–13040, 2019.
  * Goodfellow et al. [2015] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In _3rd International Conference on Learning Representations_ , 2015\.
  * Jacot et al. [2018] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Ji and Telgarsky [2020] Ziwei Ji and Matus Telgarsky.  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks.  In _8th International Conference on Learning Representations_ , 2020\.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Madry et al. [2018] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations_ , 2018.
  * Papernot et al. [2016] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami.  The limitations of deep learning in adversarial settings.  In _2016 IEEE European symposium on security and privacy (EuroS &P)_, pages 372–387. IEEE, 2016.
  * Schönherr et al. [2019] Lea Schönherr, Katharina Kohls, Steffen Zeiler, Thorsten Holz, and Dorothea Kolossa.  Adversarial attacks against automatic speech recognition systems via psychoacoustic hiding.  In _26th Annual Network and Distributed System Security Symposium_ , 2019.
  * Shamir et al. [2019] Adi Shamir, Itay Safran, Eyal Ronen, and Orr Dunkelman.  A simple explanation for the existence of adversarial examples with small hamming distance.  _arXiv preprint arXiv:1901.10861_ , 2019.
  * Sitawarin et al. [2018] Chawin Sitawarin, Arjun Nitin Bhagoji, Arsalan Mosenia, Prateek Mittal, and Mung Chiang.  Rogue signs: Deceiving traffic sign recognition with malicious ads and logos.  _arXiv preprint arXiv:1801.02780_ , 2018.
  * Szegedy et al. [2014] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In _2nd International Conference on Learning Representations_ , 2014\.
  * Tramèr et al. [2020] Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry.  On adaptive attacks to adversarial example defenses.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Vardi et al. [2022] Gal Vardi, Gilad Yehudai, and Ohad Shamir.  Gradient methods provably converge to non-robust networks.  _arXiv preprint arXiv:2202.04347_ , 2022.
  * Wainwright [2019] Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press, 2019.

##  Appendix A Additional experiments

Figure 5 and 6 plot the same phenomena as Figure 2 and 3. The only difference
is that they strictly follows the setting described in Section 2 where the
training data and test data has been normalized to $\|{\textrm{x}}\|=1$, and
there’s no bias term when initializing the neural network linear layer to
consist of our problem setup. For each experimental setting (i.e, for each
value of $d$, $C_{0}$, and $m$), we report results averaged over $5$
independent random runs.

|  |
---|---|---
Figure 5:  Normalize data $\|{\textrm{x}}\|=1$. Smallest size of perturbation to switch the prediction (left), norm of the gradient after training the neural networks (middle), smallest step size (right), as a function of input dimension $d$ for fix $C_{0}=10$ with different width $m$. |  |
---|---|---
Figure 6:  Normalize data $\|{\textrm{x}}\|=1$. Smallest size of perturbation
to switch the prediction (left), norm of the gradient after training the
neural networks (middle), smallest step size (right), as a function of input
dimension $d$ for fix $m=10^{5}$ with different $C_{0}$.

Figure 7 is the histogram of smallest size of perturbation to switch the
prediction, the norm of the gradient after training the neural networks, and
the step size when $d=784,m=10^{5},C_{0}=10$. The histogram exhibits a
Gaussian distribution, and the step size to flip the prediction is small.
($\eta$ concentrates around $0.045$.)

|  |
---|---|---
Figure 7: Histogram of smallest size of perturbation to switch the prediction,
the norm of the gradient after training the neural networks, and the step size
when $d=784,m=10^{5},C_{0}=10$.

In Algorithm 1, we describe our projected adversarial training algorithm in
details. For generating adversarial example with budget $R$ at each round, we
choose learning rate $\alpha=2.5\times R/100$ with $T_{2}=100$. This is a
common choice, which is first introduced in [Madry et al., 2018]. For updating
the weight matrix, we choose learning rate $\beta=0.01$. We stop when the
robust training accuracy is not increasing.

Algorithm 1 Projected Adversarial Training

1: Training samples
$(\textrm{X},{\textrm{y}})=\\{{\textrm{x}}_{i},y_{i}\\}_{i=1}^{n}$. Initialize
${\textrm{w}}_{s,0}\sim N(0,\textrm{I}_{d}),a_{s}\sim\operatorname{unif}\\{\pm
1\\},\forall s\in[m]$ with fixed a. Epochs $T_{1},T_{2}$. Learning rate
$\alpha,\beta$, perturbation budget per sample $R$. Logistic loss $\ell$.
Batch size $bs$. $\mathcal{P}_{\Delta}$ is the projection operator onto the
set $\Delta$.

2: for $t=1,\ldots,T_{1}$ do

3: for $k=1,\ldots,T_{2}$ do

4:
$\tilde{\textrm{X}}=\textrm{X}+\alpha\sum_{i=1}^{n}\nabla_{{\textrm{x}}_{i}}\ell(y_{i}f({\textrm{x}}_{i};{\textrm{a}},\textrm{W}_{t-1}))$

5:
$\tilde{\textrm{X}}=\mathcal{P}_{\mathcal{B}_{2,\infty}(\textrm{X},R)}(\tilde{\textrm{X}})$
{generate adversarial examples}

6: end for

7: for $\lfloor\frac{n}{bs}\rfloor$ rounds do

8: Sample a mini-batch of size $bs$ from $(\tilde{\textrm{X}},{\textrm{y}})$
as $(\tilde{\textrm{x}}_{i_{j}},y_{i_{j}})_{j=1}^{bs}$.

9:
$\textrm{W}_{t}=\textrm{W}_{t-1}-\beta\nabla_{\textrm{W}_{t-1}}\sum_{j=1}^{bs}\ell(y_{i_{j}}f(\tilde{\textrm{x}}_{i_{j}};{\textrm{a}},\textrm{W}_{t-1}))$

10: end for

11:
$\textrm{W}_{t}=\mathcal{P}_{\mathcal{B}_{2,\infty}(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}})}(\textrm{W}_{t})$
{Project the weight matrix to satisfy lazy regime.}

12: end for

13: return: $\textrm{W}_{T_{1}}$

##  Appendix B Proof of theorems

###### Proof of Theorem 3.1.

From Lemma B.5, B.7, B.9, we have that

$\displaystyle\|\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})\|$
$\displaystyle\geq C^{\prime}_{1}\sqrt{d},$
$\displaystyle|f({\textrm{x}};{\textrm{a}},\textrm{W})|$ $\displaystyle\leq
C^{\prime}_{2},$ $\displaystyle\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})\|$ $\displaystyle\leq
C^{\prime}_{3}\sqrt{d}\textrm{ for }\|\delta\|\leq o(\frac{1}{\sqrt{d}})$

We simplify the notation as
$f({\textrm{x}})=f({\textrm{x}};{\textrm{a}},\textrm{W})$. Define
$\tilde{\eta}=\eta\|\nabla f({\textrm{x}})\|^{2}$. Without loss of generality,
assume $f({\textrm{x}})>0$, let

$\tilde{\eta}=-\frac{2f({\textrm{x}})}{1-\sup_{\|\delta\|\leq\frac{\tilde{\eta}}{\|\nabla
f({\textrm{x}})\|}}\frac{\|\nabla
f({\textrm{x}}+\delta)\|-\|f({\textrm{x}})\|}{\|\nabla f({\textrm{x}})\|}},$

we have for the point ${\textrm{x}}+\tilde{\eta}\frac{\nabla
f({\textrm{x}})}{\|\nabla f({\textrm{x}})\|^{2}}$,

$\displaystyle f({\textrm{x}}+\tilde{\eta}\frac{\nabla
f({\textrm{x}})}{\|\nabla f({\textrm{x}})\|^{2}})$
$\displaystyle=f({\textrm{x}})+\int_{0}^{1}f({\textrm{x}}+t\tilde{\eta}\frac{\nabla
f({\textrm{x}})}{\|\nabla f({\textrm{x}})\|^{2}})^{\prime}dt$ (Fundamental
theorem of calculus)
$\displaystyle=f({\textrm{x}})+\int_{0}^{1}\tilde{\eta}\frac{\nabla
f({\textrm{x}})^{\top}}{\|\nabla f({\textrm{x}})\|^{2}}\nabla
f({\textrm{x}}+t\tilde{\eta}\frac{\nabla f({\textrm{x}})}{\|\nabla
f({\textrm{x}})\|^{2}})dt$
$\displaystyle=f({\textrm{x}})+\tilde{\eta}+\int_{0}^{1}\tilde{\eta}\frac{\nabla
f({\textrm{x}})^{\top}}{\|\nabla f({\textrm{x}})\|}\frac{(\nabla
f({\textrm{x}}+t\tilde{\eta}\frac{\nabla f({\textrm{x}})}{\|\nabla
f({\textrm{x}})\|^{2}})-\nabla f({\textrm{x}}))}{\|\nabla
f({\textrm{x}})\|}dt$ $\displaystyle\leq
f({\textrm{x}})+\tilde{\eta}+|\tilde{\eta}|\int_{0}^{1}\frac{\|\nabla
f({\textrm{x}}+t\tilde{\eta}\frac{\nabla f({\textrm{x}})}{\|\nabla
f({\textrm{x}})\|^{2}})-\nabla f({\textrm{x}})\|}{\|\nabla
f({\textrm{x}})\|}dt$ (Cauchy–Schwarz) $\displaystyle\leq
f({\textrm{x}})+\tilde{\eta}+|\tilde{\eta}|\sup_{\delta\in\mathbb{R}^{d}:\|\delta\|\leq\frac{\tilde{\eta}}{\|\nabla
f({\textrm{x}})\|}}\frac{\|\nabla f({\textrm{x}}+\delta)-\nabla
f({\textrm{x}})\|}{\|\nabla f({\textrm{x}})\|}$
$\displaystyle=-f({\textrm{x}})<0$

Note $|\tilde{\eta}|=\Theta(1)$ and thus $\eta\leq O(\frac{1}{d})$,
$\|\eta\nabla f({\textrm{x}})\|=\|\tilde{\eta}\frac{\nabla
f({\textrm{x}})}{\|\nabla f(x)\|^{2}}\|\leq O(\frac{1}{\sqrt{d}})$. ∎

In order to proof the main theorem, we start by giving some standard theorems,
which will be used in later proof.

######  Theorem B.1 (Berstein’s inequality).

Let $z_{1},\ldots,z_{n}$ be independent real-valued random variables. Assume
that there exist positive numbers $v$ and $c$ such that

$\displaystyle\sum_{i=1}^{n}\mathbb{E}[z_{i}^{2}]\leq v\textrm{ and
}\sum_{i=1}^{n}\mathbb{E}[|z_{i}|^{q}]\leq\frac{q!}{2}vc^{q-2}\textrm{ for all
integers }q\geq 3.$

If $S=\sum_{i=1}^{n}(z_{i}-\mathbb{E}z_{i})$, then for all $t>0$,

$\displaystyle\textrm{P}(S\geq\sqrt{2vt}+ct)\leq e^{-t}.$

We will also use repeatly that

$\displaystyle\mathbb{E}_{z\sim\mathcal{N}(0,1)}[|z|^{q}]\leq(q-1)!!\leq\frac{q!}{2},$
(1)

as well as the following concentration of $\chi^{2}$ random variables: let
$z_{1},\ldots,z_{m}$ be i.i.d. standard Gaussians, then with probability at
least $1-\gamma$, one has

$\displaystyle\bigg{|}\sum_{s=1}^{m}z_{s}^{2}-m\bigg{|}\leq
4\sqrt{m\log(2/\gamma)}$ (2)

######  Theorem B.2.

(Chernoff’s inequality) If $z_{1},z_{2},\ldots,z_{N}$ are independent
Bernoulli random variables with parameters $\mu_{i}$. Let
$S_{N}=\sum_{i}z_{i}$ and $p=\mathbb{E}S_{N}=\sum_{i}\mu_{i}$, then for $t>p$,

$\displaystyle P(S_{N}\geq t)\leq\exp(-p)\bigg{(}\frac{ep}{t}\bigg{)}^{t}$

######  Theorem B.3.

(Theorem 2.26 in Wainwright [2019]) Let
${\textrm{z}}=(z_{1},z_{2},\ldots,z_{n})$ be a vector of i.i.d standard
Gaussian variables, and let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be
$L$-Lipschitz w.r.t. the Euclidean norm. Then we have

$\displaystyle P(|f({\textrm{z}})-\mathbb{E}{f({\textrm{z}})}|\geq t)\leq
2e^{-\frac{t^{2}}{2L^{2}}}\textrm{ for all }t\geq 0$

In Lemma B.4, we let $S_{v}$ denote the set of neurons that change sign
between weights ${\textrm{w}}_{0}$ and w for the x, $S_{v}^{\prime}$ as the
set of neurons that change sign between weights ${\textrm{w}}_{0}$ and w for
the ${\textrm{x}}+\delta$. We show that the size of $S_{v}$ and
$S_{v}^{\prime}$ is small as long as the weights stay close to initialization.

######  Lemma B.4.

Define the following

$\displaystyle S_{v}\\!$
$\displaystyle:=\\!\big{\\{}s\big{|}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),{\mathds{1}}[\langle{\textrm{w}}_{s},{\textrm{x}}\rangle>0]\\!\neq\\!{\mathds{1}}[\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle>0]\big{\\}}$
$\displaystyle S_{v}^{\prime}\\!$
$\displaystyle:=\\!\big{\\{}s\big{|}\exists\delta,\|\delta\|\leq R\leq
0.5,\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),{\mathds{1}}[\langle{\textrm{w}}_{s},{\textrm{x}}+\delta\rangle>0]\\!\neq\\!{\mathds{1}}[\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle>0]\big{\\}}$

Then with probability at least $1-\gamma$, the following hold:

$\displaystyle|S_{v}|$
$\displaystyle\leq\bigg{|}\big{\\{}s\big{|}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|\leq
V\big{\\}}\bigg{|}=\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|\leq
V\big{]}\leq Vm+\sqrt{\frac{m\log(1/\gamma)}{2}}$
$\displaystyle|S_{v}^{\prime}|$
$\displaystyle\leq\bigg{|}\big{\\{}s\big{|}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|\\!\leq\\!V\big{\\}}\bigg{|}\\!=\\!\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|\\!\leq\\!V\big{]}\\!\leq\\!\bigg{(}\\!Vm+\sqrt{\frac{m\log(1/\gamma)}{2}}\bigg{)}(1+R)$

###### Proof of Lemma B.4.

Define ${\textrm{v}}_{s}={\textrm{w}}_{s}-{\textrm{w}}_{s,0}$. Note that $s\in
S_{v}$ implies $\forall 1\leq s\leq m$,

$\displaystyle\big{|}\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle\big{|}\leq\sup_{\|{\textrm{v}}_{s}\|\leq
V}\big{|}\langle\|{\textrm{w}}_{s}-{\textrm{w}}_{s,0}\|,{\textrm{x}}\rangle\big{|}\leq\sup_{\|{\textrm{v}}_{s}\|\leq
V}\|{\textrm{v}}_{s}\|_{2}\|{\textrm{x}}\|_{2}\leq V$

Thus we have

$\displaystyle\mathbb{E}\bigg{[}\frac{1}{m}\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|\leq
V\big{]}\bigg{]}=P\big{(}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|\leq
V\big{)}\leq\frac{2V}{\|{\textrm{x}}\|_{2}^{2}\sqrt{2\pi}}\leq V,$

where the expectation is with respect to the randomness in initialization, and
the inequality holds since $\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle$ is
a Gaussian r.v. with variance $1$. By Hoeffding inequality, with probability
at least $1-\gamma$,

$\displaystyle\frac{1}{m}\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|\leq
V\big{]}$
$\displaystyle\leq\mathbb{E}\bigg{[}\frac{1}{m}\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|\leq
V\big{]}\bigg{]}+\sqrt{\frac{\log(1/\gamma)}{2m}}$ (Hoeffding inequality)
$\displaystyle\leq V+\sqrt{\frac{\log(1/\gamma)}{2m}}$

As a result, with probability at least $1-\gamma$, we arrive at the following
upperbound on the size of $S_{v}$:

$\displaystyle|S_{v}|\leq\bigg{|}\big{\\{}s\big{|}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|$
$\displaystyle\leq
V\big{\\}}\bigg{|}=\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle|\leq
V\big{]}\leq Vm+\sqrt{\frac{m\log(1/\gamma)}{2}}$

Same way we can bound the size of $S_{v}^{\prime}$. $s\in S_{v}^{\prime}$
implies $\forall 1\leq s\leq m$,

$\displaystyle\big{|}\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle\big{|}\leq\sup_{\|{\textrm{v}}_{s}\|\leq
V,\|\delta\|\leq
R}\big{|}\langle{\textrm{v}}_{s},{\textrm{x}}+\delta\rangle\big{|}\leq\sup_{\|{\textrm{v}}_{s}\|\leq
V,\|\delta\|\leq R}\|{\textrm{v}}_{s}\|_{2}\|{\textrm{x}}+\delta\|_{2}\leq
V(1+R)$

Thus we have

$\displaystyle\mathbb{E}\bigg{[}\frac{1}{m}\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|\leq
V(1+R)\big{]}\bigg{]}=P\big{(}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|\leq
V(1+R)\big{)}\leq V(1+R),$

where the expectation is with respect to the randomness in initialization, and
the inequality holds since $\langle{\textrm{w}}_{s,0},{\textrm{x}}\rangle$ is
a Gaussian r.v. with variance $1$. By Hoeffding inequality, with probability
at least $1-\gamma$,

$\displaystyle\frac{1}{m}\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|\leq
V(1+R)\big{]}$
$\displaystyle\leq\mathbb{E}\bigg{[}\frac{1}{m}\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|\leq
V(1+R)\big{]}\bigg{]}+\sqrt{\frac{\log(1/\gamma)}{2m}}(1+R)$ (Hoeffding
inequality) $\displaystyle\leq V(1+R)+\sqrt{\frac{\log(1/\gamma)}{2m}}(1+R)$

As a result, with probability at least $1-\gamma$, we arrive at the following
upperbound on the size of $S_{v}$:

$\displaystyle|S_{v}|\\!\leq\\!\bigg{|}\big{\\{}s\big{|}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|$
$\displaystyle\\!\leq\\!V\big{\\}}\bigg{|}=\sum_{s=1}^{m}{\mathds{1}}\big{[}|\langle{\textrm{w}}_{s,0},{\textrm{x}}+\delta\rangle|\\!\leq\\!V\big{]}\\!\leq\\!\bigg{(}\\!Vm\\!+\\!\sqrt{\frac{m\log(1/\gamma)}{2}}\bigg{)}(1+R)$

∎

Now we begin our proof. Essentially we want to lower bound $\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|$, upper bound
$|f({\textrm{x}};{\textrm{a}},\textrm{W})|$ and upper bound $\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})\|$. Lemma B.5 gives the upper
bound of $|f({\textrm{x}};{\textrm{a}},\textrm{W})|$ as $O(1)$.

######  Lemma B.5.

For any x, with probability at least $1-\gamma$, the following holds for all
$\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\right)$,

$\displaystyle|f({\textrm{x}};{\textrm{a}},\textrm{W})|\leq\sqrt{2\log(2/\gamma)}+\frac{2\log(2/\gamma)}{\sqrt{m}}+C_{0}$

Particularly, there exists $C>0$ such that for $m\geq C\log(2/\gamma)$, we
have

$\displaystyle|f({\textrm{x}};{\textrm{a}},\textrm{W})|\leq
2\sqrt{\log(2/\gamma)}+C_{0}$

###### Proof of Lemma B.5.

From Bubeck et al. [2021] we know that
$|f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|\leq\sqrt{2\log(2/\gamma)}+\frac{2\log(2/\gamma)}{\sqrt{m}}$.
Now we consider bound
$|f({\textrm{x}};{\textrm{a}},\textrm{W})-f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|$,

$\displaystyle|f({\textrm{x}};{\textrm{a}},\textrm{W})-f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|$
$\displaystyle\leq|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}(\sigma({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))|$
$\displaystyle\leq\frac{1}{\sqrt{m}}\sum_{s=1}^{m}|\sigma({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma({\textrm{w}}_{s,0}^{\top}{\textrm{x}})|$
(Triangle Inequality)
$\displaystyle\leq\sqrt{m}|{\textrm{w}}_{s}^{\top}{\textrm{x}}-{\textrm{w}}_{s,0}^{\top}{\textrm{x}}|$
($\sigma(\cdot)$ is 1-Lipschitz.)
$\displaystyle\leq\sqrt{m}\|{\textrm{w}}_{s}-{\textrm{w}}_{s,0}\|\|{\textrm{x}}\|$
($\|{\textrm{w}}_{s}-{\textrm{w}}_{s,0}\|\leq\frac{C_{0}}{\sqrt{m}}$)
$\displaystyle\leq C_{0}$

Thus,

$\displaystyle|f({\textrm{x}};{\textrm{a}},\textrm{W})|=|f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|+|f({\textrm{x}};{\textrm{a}},\textrm{W})-f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})|\leq\sqrt{2\log(2/\gamma)}+\frac{2\log(2/\gamma)}{\sqrt{m}}+C_{0}$

∎

In Lemma B.6, we want to calculate the upper bound of the probability that the
neuron flips sign due to (1) perturbation $\delta$; (2) different perturbation
$\delta,\delta^{\prime}$ on the data x at weight ${\textrm{w}}_{s}$.

######  Lemma B.6.

For any $\delta$ such that $\|\delta\|\leq R\leq\frac{1}{2}$,

$\displaystyle
P\bigg{(}{\textrm{sign}}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})\neq{\textrm{sign}}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta))\bigg{)}\leq
R\sqrt{2\log(d)}+\frac{1}{d}$ (3) $\displaystyle
P\bigg{(}\exists\delta^{\prime},\delta^{\prime}\in\mathcal{B}_{2}(\delta,\varepsilon),\textrm{
and
}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))\neq{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta^{\prime}))\bigg{)}$
$\displaystyle\quad\quad\quad\quad\leq
2\varepsilon\bigg{(}\sqrt{d}+2\sqrt{d\log(2/\varepsilon)}\bigg{)}+(1+R+\varepsilon)V$
(4)

###### Proof of Lemma B.6.

Equation (3) directly follows from Bubeck et al. [2021]. For equation (4), we
have

$\displaystyle
P\bigg{(}\exists\delta^{\prime},\delta^{\prime}\in\mathcal{B}_{2}(\delta,\varepsilon),\textrm{
and
}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))\neq{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta^{\prime}))\bigg{)}$
$\displaystyle\leq
P\bigg{(}\exists\delta^{\prime},\delta^{\prime}\in\mathcal{B}_{2}(\delta,\varepsilon),\textrm{
and
}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),|{\textrm{w}}_{s}^{\top}(\delta^{\prime}-\delta)|\geq
t\bigg{)}$
$\displaystyle\quad\quad+P\bigg{(}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),|{\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta)|\leq
t\bigg{)}$ (Holds for any threshold $t$.) $\displaystyle\leq
P\bigg{(}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),\|{\textrm{w}}_{s}\|\geq
t/\varepsilon\bigg{)}+P\bigg{(}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),|{\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta)|\leq
t\bigg{)}$ $\displaystyle\leq
P\bigg{(}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),\|{\textrm{w}}_{s,0}\|\geq
t/\varepsilon-\|{\textrm{w}}_{s}-{\textrm{w}}_{s,0}\|\bigg{)}$
$\displaystyle\quad\quad+P\bigg{(}\exists\textrm{W},\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},V\right),|{\textrm{w}}_{s,0}^{\top}(x+\delta)|\leq
t+|({\textrm{w}}_{s}-{\textrm{w}}_{s,0})^{\top}({\textrm{x}}+\delta)|\bigg{)}$
(Triangle Inequality, pick
$t=\varepsilon\bigg{(}\sqrt{d+4\sqrt{d\log(2/\varepsilon)}}+V\bigg{)}$)
$\displaystyle\leq
P\bigg{(}\|{\textrm{w}}_{s,0}\|\\!\geq\\!\sqrt{d\\!+\\!4\sqrt{d\log(2/\varepsilon)}}\bigg{)}\\!+\\!P\bigg{(}|{\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)|\\!\leq\\!\varepsilon\sqrt{d\\!+\\!4\sqrt{d\log(2/\varepsilon)}}\\!+\\!(1\\!+\\!R\\!+\\!\varepsilon)V\bigg{)}$
(${\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)\sim\mathcal{N}(0,\sigma^{2})$
with $\sigma^{2}\geq\frac{1}{2}$ since $\|\delta\|\leq\frac{1}{2}$)
$\displaystyle\leq\varepsilon+\varepsilon\sqrt{d+4\sqrt{d\log(2/\varepsilon)}}+(1+R+\varepsilon)V$
(Using equation (2).)
$\displaystyle=2\varepsilon(\sqrt{d}+2\sqrt{d\log(2/\varepsilon)})+(1+R+\varepsilon)V$

∎

Lemma B.7 gives lower bound on $\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|\geq\Omega(\sqrt{d})$.

######  Lemma B.7.

For any x, with probability at least $1-\gamma$, the following holds for all
$\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\right)$,

$\displaystyle\|\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})\|$
$\displaystyle\geq\bigg{(}\frac{1}{2}-\big{(}\sqrt{\frac{2\log(4/\gamma)}{m}}+\frac{\log(4/\gamma)}{m}\big{)}\bigg{)}^{1/2}\bigg{(}d-5\sqrt{d\log(8/\gamma)}\bigg{)}^{1/2}$
$\displaystyle\quad\quad-
C_{0}-\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(4/\gamma)}{2}})}\bigg{(}d+4\sqrt{d\log(8m/\gamma)}\bigg{)}^{1/2}$

Particularly, there exists $C>0$ such that for $m\geq C\log(4/\gamma)$ and
$d\geq C\frac{\log(8m/\gamma)}{m}$, we have

$\displaystyle\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|\geq\frac{1}{4}\sqrt{d}$

###### Proof of Lemma B.7.

Follow the process of Bubeck et al. [2021], let
$\textrm{P}=\textrm{I}_{d}-{\textrm{x}}{\textrm{x}}^{\top}$ be the projection
on the orthogonal complement of the span of x. We have $\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|\geq\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|$. Thus we have,

$\displaystyle\|\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})\|$
$\displaystyle\geq\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})\|$ (5)
$\displaystyle=\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})+\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|$
$\displaystyle\geq\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|-\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|$

Since $a_{s}\textrm{P}{\textrm{w}}_{s,0}$ is distributed as
$\mathcal{N}(0,\textrm{I}_{d-1})$, denote
${\textrm{z}}:=a_{s}\textrm{P}{\textrm{w}}_{s,0}$, we have

$\displaystyle\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})=\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})\overset{(d)}{=}\bigg{(}\sqrt{\frac{1}{m}\sum_{s=1}^{m}\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})^{2}}\bigg{)}{\textrm{z}}\textrm{
where }{\textrm{z}}\sim\mathcal{N}(0,\textrm{I}_{d-1})$

where $\overset{(d)}{=}$ means equal in distribution.

Using (2), we have with probability at least $1-\gamma$

$\displaystyle\|{\textrm{z}}\|^{2}\geq d-1-4\sqrt{d\log(2/\gamma)}\geq
d-5\sqrt{d\log(2/\gamma)}$ ($d\geq 1,\gamma<2/e$)

Apply Bernstein’s inequality with $v=m,c=1$, we have with probability at least
$1-\gamma$,

$\displaystyle\frac{1}{m}\sum_{s=1}^{m}\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})^{2}$
$\displaystyle\geq\mathbb{E}_{X\sim\mathcal{N}(0,1)}[|\sigma^{\prime}(X)|^{2}]-\bigg{(}\sqrt{\frac{2\log(1/\gamma)}{m}}+\frac{\log(1/\gamma)}{m}\bigg{)}$
$\displaystyle=\frac{1}{2}-\bigg{(}\sqrt{\frac{2\log(1/\gamma)}{m}}+\frac{\log(1/\gamma)}{m}\bigg{)}$

Thus we can get

$\displaystyle\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|\geq\bigg{(}\frac{1}{2}-\big{(}\sqrt{\frac{2\log(2/\gamma)}{m}}+\frac{\log(2/\gamma)}{m}\big{)}\bigg{)}^{1/2}\bigg{(}d-5\sqrt{d\log(4/\gamma)}\bigg{)}^{1/2}$

Now we start upper bound $\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|$. Note that

$\displaystyle\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|$
$\displaystyle=\|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}({\textrm{w}}_{s}\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-{\textrm{w}}_{s,0}\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\|$
$\displaystyle\leq\|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}({\textrm{w}}_{s}\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-{\textrm{w}}_{s,0}\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}}))\|+\|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\|$
$\displaystyle\leq\|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}({\textrm{w}}_{s}\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-{\textrm{w}}_{s,0}\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}}))\|$
$\displaystyle\quad\quad\quad+\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\|$
$\displaystyle\leq\sqrt{m}\|{\textrm{w}}_{s}-{\textrm{w}}_{s,0}\|+\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\|$
$\displaystyle\leq C_{0}+\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\|$
(6)

Now we start bounding the second term of equation (6). We have that with
probability at least $1-\gamma$,

$\displaystyle\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))$
$\displaystyle\overset{(d)}{=}\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\bigg{(}\sqrt{\frac{1}{m}\sum_{s=1}^{m}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))^{2}}\bigg{)}{\textrm{z}}$
$\displaystyle=\bigg{(}\sqrt{\frac{1}{m}\sum_{s=1}^{m}\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))^{2}}\bigg{)}{\textrm{z}}$
$\displaystyle=\sqrt{\frac{1}{m}|S_{v}|}\cdot{\textrm{z}}$
$\displaystyle\leq\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(1/\gamma)}{2}})}\cdot{\textrm{z}}$
(7)

Using equation (2), we see that with probability at least $1-\gamma$, one has
for all $1\leq s\leq m$,

$\displaystyle\|{\textrm{z}}\|=\|a_{s}\textrm{P}{\textrm{w}}_{s,0}\|\leq\sqrt{d+4\sqrt{d\log(2m/\gamma)}}$

Thus follow from equation (6), we have

$\displaystyle\|\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\textrm{P}\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W}_{0})\|\leq
C_{0}+\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(2/\gamma)}{2}})}\sqrt{d+4\sqrt{d\log(4m/\gamma)}}$

And as a result, with probability at least $1-\gamma$

$\displaystyle\|\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})\|$
$\displaystyle\geq\bigg{(}\frac{1}{2}-\big{(}\sqrt{\frac{2\log(4/\gamma)}{m}}+\frac{\log(4/\gamma)}{m}\big{)}\bigg{)}^{1/2}\bigg{(}d-5\sqrt{d\log(8/\gamma)}\bigg{)}^{1/2}$
$\displaystyle\quad\quad-
C_{0}-\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d+4\sqrt{d\log(8m/\gamma)}}\geq\Omega(\sqrt{d})$

∎

Now we start bounding $\|\nabla f({\textrm{x}};{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})\|$. In order to prove Lemma
B.9, we will leverage the fact that for any $h\in\mathbb{R}^{d}$, we have
$\|h\|=\sup_{r\in\mathbb{S}^{d-1}}r\cdot h$. We first start a lemma with fixed
$r,\delta$ to prove Lemma B.8, then use the $\varepsilon$-net argument to
prove Lemma B.9.

######  Lemma B.8.

Fix $r\in\mathbb{S}^{d-1}$, and $\delta\in\mathbb{R}^{d}$ such that
$\|\delta\|\leq R\leq\frac{C_{1}}{\sqrt{d}}$, $C_{1}$ is a constant. For any
x, with probability at least $1-\gamma$, the following holds for all
$\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\right)$,

$\displaystyle\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}({\textrm{w}}_{s}\cdot
r)(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta)))$
$\displaystyle\leq
2\sqrt{\log(4/\gamma)}\bigg{(}\big{(}4R\sqrt{\log(d)}\big{)}^{1/4}+\sqrt{\frac{\log(4/\gamma)}{m}}\bigg{)}+C_{0}$
$\displaystyle\quad\quad+3\sqrt{\frac{1}{\sqrt{m}}(C_{0}\\!+\\!\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d\\!+\\!4\sqrt{d\log(8m/\gamma)}}\\!+\\!5(C_{0}\\!+\\!\sqrt{\log(4/\gamma)})\cdot\sqrt{\log(4m/\gamma)}$

###### Proof of Lemma B.8.

Let $X_{s,0}=a_{s}({\textrm{w}}_{s,0}\cdot
r)(\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta))),X_{s}=a_{s}({\textrm{w}}_{s}\cdot
r)(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta)))$.
We have $\mathbb{E}[X_{s,0}]=0$, and equation (1) gives us
$\mathbb{E}[|{\textrm{w}}_{s,0}\cdot r|^{2q}]\leq\frac{(2q)!}{2}$. Thus, we
have

$\displaystyle\mathbb{E}[|X_{s,0}|^{q}]$
$\displaystyle\leq\mathbb{E}[|{\textrm{w}}_{s,0}\cdot
r|^{q}|\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta))|^{q}]$
$\displaystyle\leq\sqrt{\mathbb{E}[|{\textrm{w}}_{s,0}\cdot r|^{2q}]\cdot
P({\textrm{sign}}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})\neq{\textrm{sign}}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))}$
(Using equation (3))
$\displaystyle\leq\sqrt{\frac{(2q)!}{2}}\cdot\sqrt{R\sqrt{2\log(d)}+\frac{1}{d}}$
$\displaystyle\leq\frac{q!}{2}2^{q}\cdot\sqrt{2R\sqrt{2\log(d)}}$

$\displaystyle\mathbb{E}[|X_{s,0}|^{2}]$
$\displaystyle\leq\sqrt{\mathbb{E}[({\textrm{w}}_{s,0}\cdot r)^{4}]\cdot
P({\textrm{sign}}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})\neq{\textrm{sign}}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))}$
$\displaystyle\leq 2\sqrt{R\sqrt{2\log(d)}}$
($\mathbb{E}_{X\sim\mathcal{N}(0,1)}[|X|^{4}]\leq 3!!\leq 4$)
$\displaystyle\leq 4\sqrt{R\sqrt{\log(d)}}$

Using Theorem B.1 with $v=4m\sqrt{R\sqrt{\log(d)}},c=2$, we have

$\displaystyle\frac{1}{\sqrt{m}}\sum_{s=1}^{m}X_{s,0}$
$\displaystyle\leq\sqrt{8\sqrt{R\sqrt{\log(d)}}\log(1/\gamma)}+\frac{2\log(1/\gamma)}{\sqrt{m}}$
$\displaystyle=2\sqrt{\log(1/\gamma)}\bigg{(}\big{(}4R\sqrt{\log(d)}\big{)}^{1/4}+\sqrt{\frac{\log(1/\gamma)}{m}}\bigg{)}$

Now we start bounding $|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}(X_{s}-X_{s,0})|$. In
fact, here we no longer fix $r,\delta$ and directly bound
$|\sup_{r\in\mathbb{S}^{d-1},\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}(X_{s}-X_{s,0})|$.

$\displaystyle\bigg{|}\sup_{\begin{subarray}{c}r\in\mathbb{S}^{d-1},\\\
\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}\end{subarray}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}(X_{s}-X_{s,0})\bigg{|}$
$\displaystyle=\bigg{|}\\!\\!\\!\\!\\!\sup_{\begin{subarray}{c}r\in\mathbb{S}^{d-1},\\\
\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}\end{subarray}}\\!\\!\\!\\!\\!\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\\!\bigg{(}\\!{\textrm{w}}_{s}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}\\!+\\!\delta)))\\!-\\!{\textrm{w}}_{s,0}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}\\!+\\!\delta)))\bigg{)}\bigg{|}$
$\displaystyle\leq\bigg{|}\\!\\!\\!\\!\sup_{\begin{subarray}{c}r\in\mathbb{S}^{d-1},\\\
\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}\end{subarray}}\\!\\!\\!\\!\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\\!\bigg{(}\\!{\textrm{w}}_{s}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}\\!+\\!\delta)))\\!-\\!{\textrm{w}}_{s,0}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}\\!+\\!\delta)))\bigg{)}\bigg{|}$
$\displaystyle\quad+\\!\\!\bigg{|}\\!\\!\\!\\!\\!\\!\sup_{\begin{subarray}{c}r\in\mathbb{S}^{d-1},\\\
\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}\end{subarray}}\\!\\!\\!\\!\\!\\!\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\\!\bigg{(}\\!{\textrm{w}}_{s,0}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}\\!+\\!\delta)))\\!-\\!{\textrm{w}}_{s,0}^{\top}r(\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}\\!+\\!\delta)))\\!\bigg{)}\\!\bigg{|}$
$\displaystyle\leq\frac{1}{\sqrt{m}}\sum_{s=1}^{m}\|{\textrm{w}}_{s}\\!-\\!{\textrm{w}}_{s,0}\||\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}\\!+\\!\delta))|\\!+\\!\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}$
$\displaystyle\quad+\bigg{\|}\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))\bigg{\|}$
$\displaystyle\leq
C_{0}+\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}$
(8)
$\displaystyle\quad+\bigg{\|}\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))\bigg{\|}$
(9)

Define $\textrm{P}=\textrm{I}_{d}-{\textrm{x}}{\textrm{x}}^{\top}$ as the
projection on the orthogonal complement of the span of x. For the second term
of equation (9), we have

$\displaystyle\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}$
$\displaystyle\leq\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}+\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{x}}{\textrm{x}}^{\top}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}$
$\displaystyle\leq\bigg{\|}\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}$
$\displaystyle\quad\quad+\frac{1}{\sqrt{m}}\sum_{s=1}^{m}\|{\textrm{x}}{\textrm{x}}^{\top}{\textrm{w}}_{s,0}\|\cdot|\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}})|$
$\displaystyle\leq\bigg{\|}\\!\\!\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\\!\\!\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\textrm{P}{\textrm{w}}_{s,0}(\sigma^{\prime}(({\textrm{w}}_{s,0}\\!+\\!{\textrm{v}}_{s})^{\top}{\textrm{x}})\\!-\\!\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}{\textrm{x}}))\bigg{\|}\\!+\\!\frac{1}{\sqrt{m}}|S_{v}|\max_{1\leq
s\leq m}\|{\textrm{x}}{\textrm{x}}^{\top}{\textrm{w}}_{s,0}\|$ (By the
definition of $S_{v}$ in Lemma B.4, Hölder’s inequality)
$\displaystyle\leq\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d+4\sqrt{d\log(8m/\gamma)}}+(C_{0}+\sqrt{\log(4/\gamma)})\cdot\sqrt{\log(4m/\gamma)}$
(Equation (7), ${\textrm{x}}^{\top}{\textrm{w}}_{s,0}\sim N(0,1)$)

where the last line holds because with probability at least $1-\gamma$, one
has for all $1\leq s\leq m$,
$|{\textrm{x}}^{\top}{\textrm{w}}_{s,0}|\leq\sqrt{\log(m/\gamma)}$.

Define
$\textrm{P}^{\prime}=\textrm{I}_{d}-\frac{({\textrm{x}}+\delta)({\textrm{x}}+\delta)^{\top}}{\|{\textrm{x}}+\delta\|^{2}}$
as the projection on the orthogonal complement of the span of
${\textrm{x}}+\delta$. We bound the third term of equation (9) the same way as
follows.

$\displaystyle\bigg{\|}\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))\bigg{\|}$
$\displaystyle\leq\bigg{\|}\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}P^{\prime}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))\bigg{\|}$
$\displaystyle\quad\quad+\bigg{\|}\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}\frac{({\textrm{x}}+\delta)({\textrm{x}}+\delta)^{\top}}{\|{\textrm{x}}+\delta\|^{2}}{\textrm{w}}_{s,0}(\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))\bigg{\|}$
$\displaystyle\leq\bigg{\|}\sup_{\begin{subarray}{c}\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}\\\
\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}P^{\prime}{\textrm{w}}_{s,0}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))\bigg{\|}$
$\displaystyle\quad\quad+\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}|\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta))|\bigg{\|}\frac{({\textrm{x}}+\delta)({\textrm{x}}+\delta)^{\top}}{\|{\textrm{x}}+\delta\|^{2}}{\textrm{w}}_{s,0}\bigg{\|}$
$\displaystyle\leq\sqrt{\sup_{\begin{subarray}{c}\forall
s\in[m],{\textrm{v}}_{s}\in\mathbb{R}^{d},\\\
\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}\end{subarray}}\frac{1}{m}\sum_{s=1}^{m}(\sigma^{\prime}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta))-\sigma^{\prime}({\textrm{w}}_{s,0}^{\top}({\textrm{x}}+\delta)))}\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\|{\textrm{z}}(\delta)\|$
(Define ${\textrm{z}}(\delta):=a_{s}\textrm{P}^{\prime}{\textrm{w}}_{s,0}\sim
N(0,\textrm{I}_{d-1})$)
$\displaystyle\quad\quad+\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\frac{1}{\sqrt{m}}|S_{v}^{\prime}|\bigg{\|}\frac{({\textrm{x}}+\delta)({\textrm{x}}+\delta)^{\top}}{\|{\textrm{x}}+\delta\|^{2}}{\textrm{w}}_{s,0}\bigg{\|}$
(By definition of $S_{v}^{\prime}$ in Lemma B.4)
$\displaystyle\leq\sqrt{\frac{1}{m}|S_{v}^{\prime}|}\cdot\sup_{\delta\in\mathbb{R}^{d},\|\delta\|\leq\frac{C_{1}}{\sqrt{d}}}\|{\textrm{z}}(\delta)\|$
$\displaystyle\quad\quad\quad+\frac{1}{\sqrt{m}}|S_{v}^{\prime}|\cdot
2\max_{1\leq s\leq
m}\bigg{|}{\textrm{x}}^{\top}{\textrm{w}}_{s,0}+\delta^{\top}{\textrm{w}}_{s,0}\bigg{|}$
($\|{\textrm{z}}(\delta)\|\leq\|{\textrm{w}}_{s,0}\|$)
$\displaystyle\leq\sqrt{\frac{1+R}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d+4\sqrt{d\log(8m/\gamma)}}$
$\displaystyle\quad\quad\quad+(C_{0}+\sqrt{\log(4/\gamma)})(1+R)\cdot
2\bigg{(}\sqrt{\log(4m/\gamma)}+\frac{\sqrt{d+4\sqrt{d\log(8m/\gamma)}}}{\sqrt{d}}\bigg{)}$
($R\leq\frac{C_{1}}{\sqrt{d}},d>\log(m/\gamma)\log(1/\gamma)$)
$\displaystyle\leq\sqrt{\frac{2}{\sqrt{m}}(C_{0}\\!+\\!\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d\\!+\\!4\sqrt{d\log(8m/\gamma)}}\\!+\\!4(C_{0}\\!+\\!\sqrt{\log(4/\gamma)})\bigg{(}\sqrt{\log(4m/\gamma)}\\!+\\!3\bigg{)}$

As a result, we get

$\displaystyle\frac{1}{\sqrt{m}}\sum_{s=1}^{m}X_{s}$
$\displaystyle\leq\frac{1}{\sqrt{m}}\sum_{s=1}^{m}X_{s,0}+|\frac{1}{\sqrt{m}}\sum_{s=1}^{m}(X_{s}-X_{s,0})|$
$\displaystyle\leq
2\sqrt{\log(4/\gamma)}\bigg{(}\big{(}4R\sqrt{\log(d)}\big{)}^{1/4}+\sqrt{\frac{\log(4/\gamma)}{m}}\bigg{)}+C_{0}$
$\displaystyle\quad\quad+3\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d+4\sqrt{d\log(8m/\gamma)}}$
$\displaystyle\quad\quad+5(C_{0}+\sqrt{\log(4/\gamma)})\bigg{(}\sqrt{\log(4m/\gamma)}+\\!3\bigg{)}$

∎

######  Lemma B.9.

Let $\|\delta\|\leq
R\leq\frac{C_{1}}{\sqrt{d}},\bar{C}=\max\\{1,C_{0}\\},m\geq d^{2.4}$. Then,
for any x, with probability at least $1-\gamma$, the following holds for all
$\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{m}}\right)$,

$\displaystyle\sup_{\begin{subarray}{c}r\in\mathbb{S}^{d-1},\\\
\delta\in\mathbb{R}^{d}:\|\delta\|\leq
R\end{subarray}}\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}({\textrm{w}}_{s}\cdot
r)(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta)))$
$\displaystyle\leq
9\bigg{(}C_{1}d^{2}\log^{2}(md)\sqrt{\frac{\log(d)}{d}}\bigg{)}^{1/4}$
$\displaystyle\quad\quad+\frac{15d\log(md)}{\sqrt{m}}+327\bar{C}C_{0}d^{0.25}$

provided that $d\geq\log(4/\gamma)^{2}$. Particularly, for any $c>0$, there
exists $C,C^{\prime}$ such that if $\log^{2}(md)\sqrt{\frac{\log(d)}{d}}\leq
C,\frac{d\log(md)}{\sqrt{m}}\leq C^{\prime}\sqrt{d}$, then we have,

$\displaystyle\sup_{\begin{subarray}{c}r\in\mathbb{S}^{d-1},\\\
\delta\in\mathbb{R}^{d},\|\delta\|\leq R\end{subarray}}\|\nabla
f({\textrm{x}};{\textrm{a}},\textrm{W})-\nabla
f({\textrm{x}}+\delta;{\textrm{a}},\textrm{W})\|\leq c\sqrt{d}$

The above can realize when $m\leq O(\exp(d^{0.24}))$

###### Proof.

Define
$\Phi(r,\delta)=\frac{1}{\sqrt{m}}\sum_{s=1}^{m}a_{s}({\textrm{w}}_{s}\cdot
r)(\sigma^{\prime}({\textrm{w}}_{s}^{\top}{\textrm{x}})-\sigma^{\prime}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta)))$,
and $N_{\varepsilon}$ an $\varepsilon$-net for
$\Omega=\\{(r,\delta),\|r\|=1,\|\delta\|\leq R\\}$. In Lemma B.8 we bound
$\Phi(r,\delta)$ for a fixed $r$ and $\delta$, here we bounded it uniformly
over $\Omega$. We know that $|N_{\varepsilon}|\leq(10/\varepsilon)^{2d}$.
Using Lemma B.8, we obtain with probability at least $1-\gamma$,

$\displaystyle\sup_{(r,\delta)\in\Omega}\Phi(r,\delta)$
$\displaystyle\leq\sup_{(r,\delta)\in
N_{\varepsilon}}\Phi(r,\delta)+\sup_{(r,\delta),(r^{\prime},\delta^{\prime})\in\Omega:\|r-r^{\prime}\|+\|\delta-\delta^{\prime}\|\leq\varepsilon}|\Phi(r,\delta)-\Phi(r^{\prime},\delta^{\prime})|$
(10) $\displaystyle\leq
2\sqrt{2d\log(10/\varepsilon)\\!+\\!\log(4/\gamma)}\bigg{(}\big{(}4R\sqrt{\log(d)}\big{)}^{1/4}\\!+\\!\sqrt{\frac{2d\log(10/\varepsilon)\\!+\\!\log(4/\gamma)}{m}}\bigg{)}$
$\displaystyle\quad\quad+C_{0}+3\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d+4\sqrt{d\log(8m/\gamma)}}$
$\displaystyle\quad\quad+5(C_{0}\\!+\\!\sqrt{\log(4/\gamma)})\\!\cdot\\!\bigg{(}\sqrt{\log(4m/\gamma)}\\!+\\!3\bigg{)}+\\!\\!\\!\\!\\!\\!\sup_{\begin{subarray}{c}(r,\delta),(r^{\prime},\delta^{\prime})\in\Omega:\\\
\|r-r^{\prime}\|+\|\delta-\delta^{\prime}\|\leq\varepsilon\end{subarray}}\\!\\!\\!\\!\\!\\!|\Phi(r,\delta)\\!-\\!\Phi(r^{\prime},\delta^{\prime})|$

For $r,r^{\prime}$, one has

$\displaystyle|\Phi(r,\delta)-\Phi(r^{\prime},\delta)|\leq\frac{\|r-r^{\prime}\|}{\sqrt{m}}\sum_{s=1}^{m}\|{\textrm{w}}_{s}\|\leq\frac{\|r-r^{\prime}\|}{\sqrt{m}}\sum_{s=1}^{m}(\|{\textrm{w}}_{s,0}\|+\frac{C_{0}}{\sqrt{m}})$

Using (2), we know with probability at least $1-\gamma$, one has for all
$s\in[m]$,

$\displaystyle\|{\textrm{w}}_{s,0}\|^{2}\leq d+4\sqrt{d\log(m/\gamma)},$

so that in this event we have,

$\displaystyle|\Phi(r,\delta)-\Phi(r^{\prime},\delta)|\leq\|r-r^{\prime}\|\bigg{(}\sqrt{md+4m\sqrt{d\log(m/\gamma)}}+C_{0}\bigg{)}$

On the other hand, for $\delta,\delta^{\prime}$, we write

$\displaystyle|\Phi(r,\delta)-\Phi(r,\delta^{\prime})|$
$\displaystyle\quad\leq\frac{1}{\sqrt{m}}\bigg{|}\sum_{s=1}^{m}{\mathds{1}}\\{{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))>{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta^{\prime}))\\}a_{s}{\textrm{w}}_{s}\cdot
r\bigg{|}$
$\displaystyle\quad+\frac{1}{\sqrt{m}}\bigg{|}\sum_{s=1}^{m}{\mathds{1}}\\{{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta))<{\textrm{sign}}({\textrm{w}}_{s}^{\top}({\textrm{x}}+\delta^{\prime}))\\}a_{s}{\textrm{w}}_{s}\cdot
r\bigg{|}$
$\displaystyle\leq\frac{1}{\sqrt{m}}\bigg{\|}\\!\\!\\!\sup_{\begin{subarray}{c}\forall
s\in[m],\\\ {\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq
V\end{subarray}}\\!\\!\\!\sum_{s=1}^{m}{\mathds{1}}\\{{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta))>{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta^{\prime}))\\}a_{s}{\textrm{w}}_{s}\bigg{\|}$
$\displaystyle\quad+\frac{1}{\sqrt{m}}\bigg{\|}\\!\\!\\!\sup_{\begin{subarray}{c}\forall
s\in[m],\\\ {\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq
V\end{subarray}}\\!\\!\\!\sum_{s=1}^{m}{\mathds{1}}\\{{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta))<{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta^{\prime}))\\}a_{s}{\textrm{w}}_{s}\bigg{\|}$

Letting
$X_{s}(\delta)={\mathds{1}}\\{\exists\delta^{\prime}:\|\delta-\delta^{\prime}\|\leq\varepsilon$
and $\exists{\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq
V,{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta))\neq{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta^{\prime}))\\}$,
we now control with exponentially high probability
$\sum_{s=1}^{m}X_{s}(\delta)$. By (4) in Lemma B.6, we know that
$X_{s}(\delta)$ is a Bernoulli of parameter at most
$p=2\varepsilon(\sqrt{d}+2\sqrt{d\log(2/\varepsilon)})+(1+R+\varepsilon)V$.
Using Theorem B.2 and apply a union bound, we have

$\displaystyle P\bigg{(}\exists(r,\delta)\in
N_{\varepsilon}:\sum_{s=1}^{m}X_{s}(\delta)\geq
k\bigg{)}\leq\bigg{(}\frac{10}{\varepsilon}\bigg{)}^{2d}\exp(-pm)\bigg{(}\frac{epm}{k}\bigg{)}^{k}:=g(p)$

We would like $g(p)\leq\gamma$. Since
$\sqrt{\varepsilon}(1+2\sqrt{\log(2/\varepsilon)})\leq 4\varepsilon^{3/8}$
holds for $\varepsilon\in(0,1)$, we keep upper bound $p\leq
8\sqrt{d}\varepsilon^{7/8}+3V$. Note that $p\leq\frac{k}{m}$ to make sure
$g(p)$ increases as $p$ increases. Choose $\varepsilon=m^{-4/7}d^{-4/7}$,
$V=\frac{C_{0}}{\sqrt{m}}$, $\bar{C}=\max\\{C_{0},1\\}$,
$k=44\bar{C}\sqrt{m}$, with $m\geq 58,m\geq d^{2.4}$, we have

$\displaystyle\log
g(8\sqrt{d}\varepsilon^{7/8}\\!+\\!\frac{3C_{0}}{\sqrt{m}})$
$\displaystyle=-pm+2d\log\bigg{(}\frac{10}{\varepsilon}\bigg{)}+44\bar{C}\sqrt{m}\log\bigg{(}\frac{epm}{44\bar{C}\sqrt{m}}\bigg{)}$
(Here
$p=8\sqrt{d}\varepsilon^{7/8}+\frac{3C_{0}}{\sqrt{m}}\leq\frac{11\bar{C}}{\sqrt{m}}$)
$\displaystyle=-(8\sqrt{d}\varepsilon^{7/8}\\!+\\!\frac{3C_{0}}{\sqrt{m}})m\\!+\\!2d\log(10m^{4/7}d^{4/7})\\!+\\!44\bar{C}\sqrt{m}\log\\!\bigg{(}\\!\frac{11e\bar{C}\sqrt{m}}{44\bar{C}\sqrt{m}}\\!\bigg{)}$
$\displaystyle\leq-8\sqrt{m}+2.3d\log(md)$ ($m\geq 58$)
$\displaystyle\leq-8\sqrt{m}+7\sqrt{m}$ ($m\geq d^{2.4}\implies\sqrt{m}\geq
0.33d\log(md)$) $\displaystyle\leq-\sqrt{m}$ $\displaystyle\leq\log(\gamma)$

The last line holds for $m\geq d^{2.4}$ and
$d\geq\log(4m/\gamma)^{2}\geq\log(4/\gamma)^{2}$.

By the concentration of Lipschitz functions of Gaussians (Theorem B.3) and a
union bound, we have

$\displaystyle P\bigg{(}\exists S\in[m],|S|\leq
44\bar{C}\sqrt{m},\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s\in
S}a_{s}{\textrm{w}}_{s,0}\bigg{\|}\geq\sqrt{\frac{|S|}{m}}(\sqrt{d}+t)\bigg{)}\leq
m^{44\bar{C}\sqrt{m}}e^{-\frac{t^{2}}{2}}$

By setting $t=\sqrt{88\bar{C}\sqrt{m}\log(m)+2\log(\frac{8}{\gamma})}$, we get
that with probability at least $1-\gamma/8$,

$\displaystyle\forall S\subset[m],|S|\leq
44\bar{C}\sqrt{m}:\\!\bigg{\|}\frac{1}{\sqrt{m}}\sum_{s\in
S}a_{s}{\textrm{w}}_{s,0}\bigg{\|}\\!\leq\\!\sqrt{\frac{44\bar{C}}{\sqrt{m}}}\sqrt{88\bar{C}\sqrt{m}\log(m)\\!+\\!2\log(\frac{8}{\gamma})}\\!+\\!\sqrt{\frac{44\bar{C}d}{\sqrt{m}}}$

$\displaystyle\forall S\subset[m],|S|\leq 44\bar{C}\sqrt{m}:$
$\displaystyle\bigg{\|}\sup_{{\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}}\frac{1}{\sqrt{m}}\sum_{i\in
S}a_{s}{\textrm{w}}_{s}\bigg{\|}$
$\displaystyle\leq\bigg{\|}\frac{1}{\sqrt{m}}\sum_{i\in
S}a_{s}{\textrm{w}}_{s,0}\bigg{\|}+\bigg{\|}\sup_{{\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}}\frac{1}{\sqrt{m}}\sum_{i\in
S}a_{s}{\textrm{v}}_{s}\bigg{\|}$
$\displaystyle\leq\sqrt{\frac{44\bar{C}}{\sqrt{m}}}\sqrt{88\bar{C}\sqrt{m}\log(m)+2\log(\frac{8}{\gamma})}+\sqrt{\frac{44\bar{C}d}{\sqrt{m}}}+\frac{44\bar{C}C_{0}}{\sqrt{m}}$
$\displaystyle\leq
113\bar{C}C_{0}\sqrt{\log(m)+\frac{2}{\sqrt{m}}\log(\frac{8}{\gamma})}$

Note that for all $(r,\delta)\in N$,
$\|\delta-\delta^{\prime}\|\leq\varepsilon$,

$\displaystyle\sup_{{\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}}{\mathds{1}}\\{{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta))<{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta^{\prime}))\\}\leq
X_{s}(\delta)$
$\displaystyle\sup_{{\textrm{v}}_{s}\in\mathbb{R}^{d},\|{\textrm{v}}_{s}\|\leq\frac{C_{0}}{\sqrt{m}}}{\mathds{1}}\\{{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta))>{\textrm{sign}}(({\textrm{w}}_{s,0}+{\textrm{v}}_{s})^{\top}({\textrm{x}}+\delta^{\prime}))\\}\leq
X_{s}(\delta)$

With probability at least $1-\gamma$, we have for all
$\delta,\delta^{\prime},r,r^{\prime}$ with $\|\delta-\delta^{\prime}\|\leq
m^{-4/7}d^{-4/7}$ and $\|r-r^{\prime}\|\leq m^{-4/7}d^{-4/7}$,

$\displaystyle|\Phi(r,\delta)-\Phi(r^{\prime},\delta)|$ $\displaystyle\leq
m^{-4/7}d^{-4/7}\bigg{(}\sqrt{md+4m\sqrt{d\log(m/\gamma)}}+C_{0}\bigg{)}$
$\displaystyle|\Phi(r,\delta)-\Phi(r,\delta^{\prime})|$ $\displaystyle\leq
226\bar{C}C_{0}\sqrt{\log(m)+\frac{2}{\sqrt{m}}\log(\frac{8}{\gamma})}$

Combining this with (10) we obtain with probability at least $1-\gamma$,

$\displaystyle\sup_{(r,\delta)\in\Omega}\Phi(r,\delta)$ $\displaystyle\leq
2\sqrt{2d\log(10m^{4/7}d^{4/7})\\!+\\!\log(4/\gamma)}\bigg{(}\big{(}4R\sqrt{\log(d)}\big{)}^{1/4}\\!+\\!\sqrt{\frac{2d\log(10m^{4/7}d^{4/7})\\!+\\!\log(4/\gamma)}{m}}\bigg{)}$
$\displaystyle\quad+C_{0}+3\sqrt{\frac{1}{\sqrt{m}}(C_{0}+\sqrt{\frac{\log(4/\gamma)}{2}})}\sqrt{d+4\sqrt{d\log(8m/\gamma)}}$
$\displaystyle\quad+5(C_{0}\\!+\\!\sqrt{\log(4/\gamma)})\cdot\bigg{(}\sqrt{\log(4m/\gamma)}\\!+\\!3\\!\bigg{)}\\!+\\!m^{-4/7}d^{-4/7}\bigg{(}\sqrt{md\\!+\\!4m\sqrt{d\log(m/\gamma)}}\\!+\\!C_{0}\\!\bigg{)}$
$\displaystyle\quad+226\bar{C}C_{0}\sqrt{\log(m)+\frac{2}{\sqrt{m}}\log(\frac{8}{\gamma})}$
$\displaystyle\leq
6\sqrt{d\log(md)}\\!\bigg{(}\\!(4R\sqrt{\log(d)})^{1/4}\\!+\\!\sqrt{\frac{6d\log(md)}{m}}\\!\bigg{)}\\!+\\!50d^{0.25}\\!+\\!227\bar{C}C_{0}\sqrt{\log(m)\\!+\\!\frac{2}{\sqrt{m}}\log(\frac{8}{\gamma})}$
$\displaystyle\leq
9\bigg{(}C_{1}d^{2}\log^{2}(md)\sqrt{\frac{\log(d)}{d}}\bigg{)}^{1/4}+\frac{15d\log(md)}{\sqrt{m}}+327\bar{C}C_{0}d^{0.25}$
($R\leq\frac{C_{1}}{\sqrt{d}}$) $\displaystyle=o(\sqrt{d})$ (holds when
$\log^{2}(md)\sqrt{\frac{\log(d)}{d}}=o(1),\frac{d\log(md)}{\sqrt{m}}=o(\sqrt{d})\implies
m\leq O(\exp(d^{0.24}))$)

∎

###### Proof of Corollary 3.2.

From Theorem 3.1, we have that for any point
${\textrm{x}}\in\mathbb{S}^{d-1}$, with probability at least $1-\gamma$, there
exists an adversarial example for the neural network, with parameters
$(\textrm{W},{\textrm{a}})$, at $x$ for perturbation size $R$. Thus, with
probability at least $1-\gamma$, the robust error of W at x with perturbation
$R$ is one: $\ell_{R}(\textrm{W};{\textrm{x}},y)=1$. This gives us that
$\mathbb{E}_{\textrm{W}}[\sup_{\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{d}}\right)}\ell_{R}(\textrm{W};{\textrm{x}},y)]\geq
1-\gamma$. From Markov’s inequality,

$\displaystyle\mathbb{P}\left[\sup_{\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{d}}\right)}L_{R}(\textrm{W})<0.9\right]$
$\displaystyle=\mathbb{P}\left[1-\sup_{\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{d}}\right)}L_{R}(\textrm{W})>0.1\right]$
$\displaystyle\leq
10\mathbb{E}_{\textrm{W}}\left[1-\sup_{\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{d}}\right)}L_{R}(\textrm{W})\right]$
$\displaystyle=10\mathbb{E}_{x}\mathbb{E}_{\textrm{W}}\left[1-\sup_{\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{d}}\right)}\ell_{R}(\textrm{W};{\textrm{x}},y)\right]$
$\displaystyle\leq
10\sup_{x}\mathbb{E}_{\textrm{W}}\left[1-\sup_{\textrm{W}\in\mathcal{B}_{2,\infty}\left(\textrm{W}_{0},\frac{C_{0}}{\sqrt{d}}\right)}\ell_{R}(\textrm{W};{\textrm{x}},y)\right]$
$\displaystyle\leq 10\gamma$

where in the second equality we swap the expectations using Fubini’s theorem.
∎