Convergence of Adversarial Training in Overparametrized Neural Networks

Introduction

Recent studies have demonstrated that neural network models, despite achieving human-level performance on many important tasks, are not robust to adversarial examples—a small and human imperceptible input perturbation can easily change the prediction label . This phenomenon brings out security concerns when deploying neural network models to real world systems . In the past few years, many defense algorithms have been developed to improve the network’s robustness, but most of them are still vulnerable under stronger attacks, as reported in . Among current defense methods, adversarial training has become one of the most successful methods to train robust neural networks.

To obtain a robust network, we need to consider the “robust loss” instead of a regular loss. The robust loss is defined as the maximal loss within a neighborhood around the input of each sample, and minimizing the robust loss under empirical distribution leads to a min-max optimization problem. Adversarial training is a way to minimize the robust loss. At each iteration, it (approximately) solves the inner maximization problem by an attack algorithm $\mathcal{A}$ to get an adversarial sample, and then runs a (stochastic) gradient-descent update to minimize the loss on the adversarial samples. Although adversarial training has been widely used in practice and hugely improves the robustness of neural networks in many applications, its convergence properties are still unknown. It is unclear whether a network with small robust error exists and whether adversarial training is able to converge to a solution with minimal adversarial train loss.

In this paper, we study the convergence of adversarial training algorithms and try to answer the above questions on over-parameterized neural networks. We consider width-$m$ neural networks both for the setting of deep networks with $H$ layers, and two-layer networks for some additional analysis. Our contributions are summarized below.

For an $H$-layer deep network with ReLU activations, and an arbitrary attack algorithm, when the width $m$ is large enough, we show that projected gradient descent converges to a network where the surrogate loss with respect to the attack $\mathcal{A}$ is within $\epsilon$ of the optimal robust loss (Theorem 4.1). The required width is polynomial in the depth and the input dimension.

For a two-layer network with smooth activations, we provide a proof of convergence, where the projection step is not required in the algorithm (Theorem 5.1).

We then consider the expressivity of neural networks w.r.t. robust loss (or robust interpolation). We show when the width $m$ is sufficiently large, the neural network can achieve optimal robust loss $\epsilon$; see Theorems 5.2 and C.1 for the precise statement. By combining the expressivity result and the previous bound of the loss over the optimal robust loss, we show that adversarial training finds networks of small robust training loss (Corollary 5.1 and Corollary C.1).

We show that the VC-Dimension of the model class which can robustly interpolate any $n$ samples is lower bounded by $\Omega(nd)$ where $d$ is the dimension. In contrast, there are neural net architectures that can interpolate $n$ samples with only $O(n)$ parameters and VC-Dimension at most $O(n\log n)$. Therefore, the capacity required for robust learning is higher.

Related Work

Adversarial examples are inputs that are slightly perturbed from a natural sample and yet incorrectly classified by the model. An adversarial example can be generated by maximizing the loss function within an $\epsilon$-ball around a natural sample. Thus, generating adversarial examples can be viewed as solving a constrained optimization problem and can be (approximately) solved by a projected gradient descent (PGD) method . Some other techniques have also been proposed in the literature including L-BFGS , FGSM , iterative FGSM and C&W attack , where they differ from each other by the distance measurements, loss function or optimization algorithms. There are also studies on adversarial attacks with limited information about the target model. For instance, considered the black-box setting where the model is hidden but the attacker can make queries and get the corresponding outputs of the model.

Improving the robustness of neural networks against adversarial attacks, also known as defense, has been recognized as an important and unsolved problem in machine learning. Various kinds of defense methods have been proposed , but many of them are based on obfuscated gradients which does not really improve robustness under stronger attacks . As an exception, reported that the adversarial training method developed in is the only defense that works even under carefully designed attacks.

Adversarial Training

Adversarial training is one of the first defense ideas proposed in earlier papers . The main idea is to add adversarial examples into the training set to improve the robustness. However, earlier work usually only adds adversarial example once or only few times during the training phase. Recently, showed that adversarial training can be viewed as solving a min-max optimization problem where the training algorithm aims to minimize the robust loss, defined as the maximal loss within a certain $\epsilon$-ball around each training sample. Based on this formulation, a clean adversarial training procedure based on PGD-attack has been developed and achieved state-of-the-art results even under strong attacks. This also motivates some recent research on gaining theoretical understanding of robust error . Also, adversarial training suffers from slow training time since it runs several steps of attacks within one update, and several recent works are trying to resolve this issue . From the theoretical perspective, a recent work considers to quantitatively evaluate the convergence quality of adversarial examples found in the inner maximization and therefore ensure robustness. consider generalization upper and lower bounds for robust generalization. improves the robust generalization by data augmentation with GAN. considers to reduce the optimization of min-max problem to online learning setting and use their results to analyze the convergence of GAN. In this paper, our analysis for adversarial is quite general and is not restricted to any specific kind of attack algorithm.

Global convergence of Gradient Descent

Recent works on the over-parametrization of neural networks prove that when the width greatly exceeds the sample size, gradient descent converges to a global minimizer from random initialization . The key idea in the earlier literature is to show that the Jacobian w.r.t. parameters has minimum singular value lower bounded, and thus there is a global minimum near every random initialization, with high probability. However for the robust loss, the maximization cannot be evaluated and the Jacobian is not necessarily full rank. For the surrogate loss, the heuristic attack algorithm may not even be continuous and so the same arguments cannot be utilized.

Certified Defense and Robustness Verification

In contrast to attack algorithms, neural network verification methods tries to find upper bounds of the robust loss and provide certified robustness measurements. Equipped with these verification methods for computing upper bounds of robust error, one can then apply adversarial training to get a network with certified robustness. Our analysis in Section 4 can also be extended to certified adversarial training.

Preliminaries

Let $[n]=\{1,2,\ldots,n\}$. We use $\mathcal{N}(\mathbf{0},\mathbf{I})$ to denote the standard Gaussian distribution. For a vector $\mathbf{v}$, we use $\left\lVert\mathbf{v}\right\rVert_{2}$ to denote the Euclidean norm. For a matrix $\mathbf{A}$ we use $\left\lVert\mathbf{A}\right\rVert_{F}$ to denote the Frobenius norm and $\left\lVert\mathbf{A}\right\rVert_{2}$ to denote the spectral norm. We use $\langle\cdot,\cdot\rangle$ to denote the standard Euclidean inner product between two vectors, matrices, or tensors. We let $O(\cdot)$, $\Theta(\cdot)$ and $\Omega\left(\cdot\right)$ denote standard Big-O, Big-Theta and Big-Omega notations that suppress multiplicative constants.

2 Deep Neural Networks

Here we give the definition of our deep fully-connected neural networks. For the convenience of proof, we use the same architecture as defined in .We only consider the setting when the network output is scalar. However, it is not hard to extend out results to the setting of vector outputs. Formally, we consider a neural network of the following form.

where $\overline{\mathbf{x}}^{(h)}$ and $\mathbf{x}^{(h)}$ are the feature vectors before and after the activation function, respectively. Sometimes we also denote $\overline{\mathbf{x}}^{(0)}=\mathbf{x}^{(0)}$.

3 Perturbation and the Surrogate Loss Function

The goal of adversarial training is to make the model robust in a neighbor of each datum. We first introduce the definition of the perturbation set function to determine the perturbation at each point.

Given a perturbation set, we are now ready to define the perturbation function that maps a data point to another point inside its perturbation set. We note that the perturbation function can be quite general including the identity function and any adversarial attackIt is also not hard to extend our analysis to perturbation functions involving randomness.. Formally, we give the following definition.

With the definition of perturbation function, we can now define a large family of loss functions on the training set $\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}$. We will show this definition covers the standard loss used in empirical risk minimization and the robust loss used in adversarial training.

Given a perturbation function $\mathcal{A}$ defined in Definition 3.2, the current parameter $\mathbf{W}$ of a neural network $f$, and a training set $\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}$, we define the surrogate loss $L_{\mathcal{A}}(\mathbf{W})$ on the training set as

It can be easily observed that the standard training loss $L(\mathbf{W})$ is a special case of surrogate loss function when $\mathcal{A}$ is the identity. The goal of adversarial training is to minimize the robust loss, i.e. the surrogate loss when $\mathcal{A}$ is the strongest possible attack. The formal definition is as follows:

Convergence Results of Adversarial Training

We consider optimizing the surrogate loss $L_{\mathcal{A}}$ with the perturbation function $\mathcal{A}(\mathbf{W},\mathbf{x})$ defined in Definition 3.2, which is what adversarial training does given any attack algorithm $\mathcal{A}$. In this section, we will prove that for a neural network with sufficient width, starting from the initialization $\mathbf{W}_{0}$, after certain steps of projected gradient descent within a convex set $B(R)$, the loss $L_{\mathcal{A}}$ is provably upper-bounded by the best minimax robust loss in this set

Denote $\mathcal{P}_{B(R)}$ as the Euclidean projection to the convex set $B(R)$. Denote the parameter $\mathbf{W}$ after the $t$-th iteration as $\mathbf{W}_{t}$, and similarly $\mathbf{W}^{(h)}_{t}$. For each step in adversarial training, projected gradient descent takes an update

Specifically, we have the following theorem.

where $\mathbf{W}_{\ast}=\arg\min_{\mathbf{W}\in B(R)}L_{\ast}(\mathbf{W})$.

Recall that $L_{\mathcal{A}}(\mathbf{W})$ is the loss suffered with respect to the perturbation function $\mathcal{A}$. This means, for example, if the adversary uses the projected gradient ascent algorithm, then the theorem guarantees that projected gradient ascent cannot successfully attack the learned network. The stronger the attack algorithm is during training, the stronger the guaranteed surrogate loss becomes.

The value of $R$ depends on the approximation capability of the network, i.e. the greater $R$ is, the less $L_{\ast}(\mathbf{W}_{\ast})$ will be, thus affecting the overall bound on $\min_{t}L_{\mathcal{A}}(\mathbf{W}_{t})$. We will elaborate on this in the next section, where we show that for $R$ independent of $m$ there exists a network of small adversarial training error.

Adversarial Training Finds Robust Classifier

Motivated by the optimization result in Theorem 4.1, we hope to show that there is indeed a robust classifier in $B(R)$. To show this, we utilize the connection between neural networks and their induced Reproducing Kernel Hilbert Space (RKHS) via viewing networks near initialization as a random feature scheme . Since we only need to show the existence of a network architecture that robustly fits the training data in $B(R)$ and neural networks are at least as expressive as their induced kernels, we may prove this via the RKHS connection. The strategy is to first show the existence of a robust classifier in the RKHS, and then show that a sufficiently wide network can approximate the kernel via random feature analysis. The approximation results of this section will be, in general, exponential in dimension dependence due to the known issue of $d$-dimensional functions having exponentially large RKHS norm , so only offer qualitative guidance on existence of robust classifiers.

Since deep networks contain two-layer networks as a sub-network, and we are concerned with expressivity, we focus on the local expressivity of two-layer networks. We write the standard two-layer network in the suggestive wayThis makes $f(\mathbf{W},\mathbf{x})=0$ at initialization, which helps eliminate some unnecessary technical nuisance. (where the width $m$ is an even number)

and initialize as $\mathbf{w}_{r}\sim\mathcal{N}(0,\mathbf{I}_{d})$ i.i.d. for $r=1,\cdots,\frac{m}{2}$, and $\bar{\mathbf{w}}_{r}$ is set to be equal to $\mathbf{w}_{r}$, $a_{r}$ is randomly drawn from $\{1,-1\}$ and $a^{\prime}_{r}=-a_{r}$. Similarly, we define the set $B(R)=\left\{\mathbf{W}:\left\lVert\mathbf{W}-\mathbf{W}_{0}\right\rVert_{F}\leq R\right\}$Note that we have taken out the term $\frac{1}{\sqrt{m}}$ explicitly in the network expression for convenience, so in this section there is a difference of scaling by a factor of $\sqrt{m}$ from the $\mathbf{W}$ used in the previous section. for $\mathbf{W}=(\mathbf{w}_{1},\cdots,\mathbf{w}_{m/2},\bar{\mathbf{w}}_{1},\cdots,\bar{\mathbf{w}}_{m/2})$, $\mathbf{W}_{0}$ being the initialization of $\mathbf{W}$, and fix all $a_{r}$ after initialization.

To make things cleaner, we will use a smooth activation function $\sigma(\cdot)$ throughout this sectionSimilar approximation results also hold for other activation functions like ReLU., formally stated as follows.

Prior to proving the approximation results, we would like to first provide a version of convergence theorem similar to Theorem 4.1, but for this two-layer setting. It is encouraged that the reader can read Appendix B for the proof of the following Theorem 5.1 first, since it is relatively cleaner than that of the deep setting but the proof logic is analogous.

Suppose the loss function satisfies Assumption 3.1 and the activation function satisfies Assumption 5.1. With high probability, using the two-layer network defined above, for any $\epsilon>0$, if we run gradient descent with step size $\alpha=O\left(\epsilon\right)$, and if $m=\Omega\left(\frac{R^{4}}{\epsilon^{2}}\right)$, we have

where $\mathbf{W}_{\ast}=\min_{\mathbf{W}\in B(R)}L_{\ast}(\mathbf{W})$ and $T=\Theta(\frac{\sqrt{m}}{\alpha})$.

Compared to Theorem 4.1, we do not need the projection step for this two-layer theorem. We believe using a smooth activation function can also eliminate the need of the projection step in the deep setting from a technical perspective, and from a practical sense we conjecture that the projection step is not needed anyway.

Now we’re ready to proceed to the approximation results, i.e. proving that $L_{\ast}(\mathbf{W}_{\ast})$ is also small, and combined with Equation (5) we can give an absolute bound on $\min_{t}L_{\mathcal{A}}(\mathbf{W}_{t})$. For the reader’s convenience, we first introduce the Neural Tangent Kernel (NTK) w.r.t. our two-layer network.

For a given kernel $K$, there is a reproducing kernel Hilbert space (RKHS) introduced by $K$. We denote it as $\mathcal{H}(K)$. We refer the readers to for an introduction of the theory of RKHS.

We formally make the following assumption on the universality of NTK.

For any $\epsilon>0$, there exists $f\in\mathcal{H}(K_{\sigma})$, such that $\left|f(\mathbf{x}_{i}^{\prime})-y_{i}\right|\leq\epsilon$, for every $i\in[n]$ and $\mathbf{x}_{i}^{\prime}\in\mathcal{B}(\mathbf{x}_{i})$.

Also, we make an additional assumption on the activation function $\sigma(\cdot)$:

Under these assumptions, by applying the strategy of approximating the infinite situation by finite sum of random features, we can get the following theorem:

Given data set $\mathcal{D}=\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{n}$ and a compatible perturbation set function $\mathcal{B}$ with $\mathbf{x}_{i}$ and its allowed perturbations taking value on $\mathcal{S}$, for the two-layer network defined in (4), if Assumption 3.1, 5.1, 5.2, 5.3 hold, then for any $\epsilon>0$, there exists $R_{\mathcal{D},\mathcal{B},\epsilon}$ such that when the width $m$ satisfies $m=\Omega\left(\frac{R_{\mathcal{D},\mathcal{B},\epsilon}^{4}}{\epsilon^{2}}\right)$, with probability at least 0.99 over the initialization there exists $\mathbf{W}$ such that

Combining Theorem 5.1 and 5.2 we finally know that

Given data set on the unit sphere equipped with a compatible perturbation set function and an associated perturbation function $\mathcal{A}$, which also takes value on the unit sphere. Suppose Assumption 3.1, 5.1, 5.2, 5.3 are satisfied. Then for any $\epsilon>0$, there exists a $R_{\mathcal{D},\mathcal{B},\epsilon}$ which only depends on dataset $\mathcal{D}$, perturbation $\mathcal{B}$ and $\epsilon$, such that for any $2$-layer fully connected network with width $m=\Omega(\frac{R_{\mathcal{D},\mathcal{B},\epsilon}^{4}}{\epsilon^{2}})$, if we run gradient descent with stepsize $\alpha=O\left(\epsilon\right)$ for $T=\Omega(\frac{R_{\mathcal{D},\mathcal{B},\epsilon}^{2}}{\epsilon\alpha})$ steps, then with probability $0.99$,

We point out that Assumption 5.2 is rather general and can be verified for a large class of activation functions by showing their induced kernel is universal as done in . Also, here we use an implicit expression of the radius $B_{\mathcal{D},\mathcal{B},\epsilon}$, but the dependence on $\epsilon$ can be calculated under specific activation function with or without the smoothness assumptions. As an example, using quadratic ReLU as activation function, we solve the explicit dependency on $\epsilon$ in Appendix C.2 that doesn’t rely on Assumption 5.2.

Therefore, adversarial training is guaranteed to find a robust classifier under a given attack algorithm when the network width is sufficiently large.

Capacity Requirement of Robustness

In this section, we will show that in order to achieve adversarially robust interpolation (which is formally defined below), one needs more capacity than just normal interpolation. In fact, empirical evidence have already shown that to reliably withstand strong adversarial attacks, networks require a significantly larger capacity than for correctly classifying benign examples only . This implies, in some sense, that using a neural network with larger width is necessary.

We begin with the definition of the interpolation class and the robust interpolation class.

We say that a function class $\mathcal{F}$ is an $n$-robust interpolation class, if the following is satisfied:

We will use the VC-Dimension of a function class $\mathcal{F}$ to measure its complexity. In fact, as shown in (Equation(2)), for neural networks there is a tight connection between the number of parameters $W$, the number of layers $H$ and their VC-Dimension

In addition, combining with the results in (Theorem 3) which shows the existence of a 4-layer neural network with $O(n)$ parameters that can interpolate any $n$ data points, i.e. an $n$-interpolation class, we have that an $n$-interpolation class can be realized by a fixed depth neural network with VC-Dimension upper bound

For a general hypothesis class $\mathcal{F}$, we can evidently see that when $\mathcal{F}$ is an $n$-interpolation class, $\mathcal{F}$ has VC-Dimension at least $n$. For a neural network that is an $n$-interpolation class, without further architectural constraints, this lower bound of its VC-dimension is tight up to logarithmic factors as indicated in Equation (7). However, we show that for a robust-interpolation class we will have a much larger VC-Dimension lower bound:

If $\mathcal{F}$ is an $n$-robust interpolation class, then we have the following lower bound on the VC-Dimension of $\mathcal{F}$

where $d$ is the dimension of the input space.

For neural networks, Equation (8) shows that any architecture that is an $n$-robust interpolation class should have VC-Dimension at least $\Omega(nd)$. Compared with Equation (7) which shows an $n$-interpolation class can be realized by a network architecture with VC-Dimension $O(n\log n)$, we can conclude that robust interpolation by neural networks needs more capacity, so increasing the width of neural network is indeed in some sense necessary.

Discussion on Limitations and Future Directions

This work provides a theoretical analysis of the empirically successful adversarial training algorithm in the training of robust neural networks. Our main results indicate that adversarial training will find a network of low robust surrogate loss, even when the maximization is computed via a heuristic algorithm such as projected gradient ascent. However, there are still some limitations with our current theory, and we also feel our results can lead to several thought-provoking future work, which is discussed as follows.

Removal of projection. It is also natural to ask whether the projection step can be removed, as it is empirically unnecessary and also unnecessary for our two-layer analysis. We believe using smooth activations might resolve this issue from a technical perspective, although practically it seems the projection step in the algorithm is unnecessary in any case.

Generalizing to different attacks. Firstly, our current guarantee of the surrogate loss is based on the same perturbation function as that used during training. It is natural to ask that whether we can ensure the surrogate loss is low with respect to a larger family of perturbation functions than that used during training.

Exploiting structures of network and data. Same as the recent proof of convergence on overparameterized networks in the non-robust setting, our analysis fails to further incorporate useful network structures apart from being sufficiently wide, and as a result increasing depth can only hurt the bound. It would be interesting to provide finer analysis based on additional assumptions on the alignment of the network structure and data distribution.

Improving the approximation bound. On the expressivity side, the current argument utilizes that a neural net restricted to a local region can approximate its induced RKHS. Although the RKHS is universal, they do not avoid the curse of dimensionality (see Appendix C.2). However, we believe in reality, the required radius of region $R$ to achieve robust approximation is not as large as the theorem demands. So an interesting question is whether the robust expressivity of neural networks can adapt to structures such as low latent dimension of the data mechanism , thereby reducing the approximation bound.

Capacity requirement of robustness and robust generalization. Apart from this paper, there are other works supporting the need for capacity including the perspective of network width , depth and computational complexity . It is argued in that robust generalization is also harder using Rademacher complexity. In fact, it appears empirically that robust generalization is even harder than robust training. It is observed that increasing the capacity, though benifiting the dacay of training loss, has much less effect on robust generalization. There are also other factors behind robust generalization, like the number of training data . The questions about robust generalization, as well as to what extent capacity influnces it, are still subject to much debate.

The above are several interesting directions of further improvement to our current result. In fact, many of these questions are largely unanswered even for neural nets in the non-robust setting, so we leave them to future work.

Acknowlegements

We acknowlegde useful discussions with Siyu Chen, Di He, Runtian Zhai, and Xiyu Zhai. RG and TC are partially supported by the elite undergraduate training program of School of Mathematical Sciences in Peking University. LW acknowledges support by Natioanl Key R&D Program of China (no. 2018YFB1402600), BJNSF (L172037). JDL acknowledges support of the ARO under MURI Award W911NF-11-1-0303, the Sloan Research Fellowship, and NSF CCF #1900145.

References

Appendix A Proof of the Convergence Result for Deep Nets in Section 4

and the gradient w.r.t. $\mathbf{W}^{(h)}$ is

First, we will restate some basic results at initialization.

If $m\geq d$, with probability $1-O(H)e^{-\Omega(m)}$ at initialization, we have $\left\lVert\mathbf{A}\right\rVert_{2}=O(1)$, $\left\lVert\mathbf{W}^{(h)}\right\rVert_{2}=O(1),\forall h\in[H]$, and $\left\lVert\mathbf{a}\right\rVert_{2}=O(\sqrt{m})$.

For any fixed input $\mathbf{x}\in\mathcal{S}$, with probability $1-O(H)e^{-\Omega(m/H)}$ over the randomness of initialization, we have for every $h\in\{0,\ldots,H\}$, $\left\lVert\overline{\mathbf{x}}^{(h)}\right\rVert_{2}\in[2/3,4/3]$ and $\left\lVert{\mathbf{x}}^{(h)}\right\rVert_{2}\in[2/3,4/3]$ at initialization.

This is a restatement of Lemma 7.1 in taking the number of data $n=1$. ∎

If $m=\Omega\left(H\log H\right)$, for any fixed input $\mathbf{x}\in\mathcal{S}$, with probability $1-e^{-\Omega(m/H)}$, at initialization we have for every $h\in[H]$,

Note that $\left\lVert\mathbf{a}^{\top}\mathbf{D}^{(H)}\mathbf{W}^{(H)}\cdots\mathbf{D}^{(h)}\mathbf{W}^{(h)}\right\rVert_{2}\leq\left\lVert\mathbf{a}^{\top}\right\rVert_{2}\left\lVert\mathbf{D}^{(H)}\right\rVert_{2}\left\lVert\mathbf{W}^{(H)}\cdots\mathbf{D}^{(h)}\mathbf{W}^{(h)}\right\rVert_{2}$ and $\left\lVert\mathbf{D}^{(H)}\right\rVert_{2}\leq 1$. This lemma then becomes a direct consequence of Lemma A.1 and Lemma 7.3(a) in with number of data $n=1$. ∎

Our general idea is that within the local region (where $R=\Omega(1)$)

the gradient $f^{\prime(h)}(\mathbf{W})$ remains stable over $\mathbf{W}$ when $\mathbf{x}$ is fixed, and the perturbation of $f^{\prime(h)}(\mathbf{W})$ is small compared to the scale of $f^{\prime(h)}(\mathbf{W}_{0})$. This property has been studied in extensively. However, in the non-adversarial setting, they only need to prove this property at finitely many data points $\{\mathbf{x}_{i}\}_{i=1}^{n}$. In our adversarial training setting, though, we also need to prove that it holds for any $\mathbf{x}^{\prime}_{i}\in\mathcal{B}(\mathbf{x}_{i})$. Specifically, in this section we would like to prove that it holds for any $\mathbf{x}\in\mathcal{S}$. Our method is based on viewing the perturbation of $\mathbf{x}$ as an equivalent perturbation of the parameter $\mathbf{W}^{(1)}$, and then we will be able to make use of the results in . This is elaborated in the following lemma:

Given any fixed input $\mathbf{x}\in\mathcal{S}$. If $R=O(\sqrt{m})$, with probability $1-O(H)e^{-\Omega(m/H)}$ over random initialization, for any $\mathbf{x}^{\prime}\in\mathcal{S}$ satisfying $\left\lVert\mathbf{x}-\mathbf{x}^{\prime}\right\rVert_{2}\leq\delta$, and any $\mathbf{W}\in B(R)$, there exists $\widetilde{\mathbf{W}}\in B(R+O(\sqrt{m}\delta))$ such that $\mathbf{W}^{(h)}=\widetilde{\mathbf{W}}^{(h)}$ for $h=2,\cdots,H$, and for all $h\in[H]$ we have

In other words, the network with a perturbation from $\mathbf{x}$ to $\mathbf{x}^{\prime}$ is same as the network with a perturbation from $\mathbf{W}$ to $\widetilde{\mathbf{W}}$ since layer $\overline{\mathbf{x}}^{(1)}$ and up.

By Lemma A.1, with probability $1-O(H)e^{-\Omega(m)}$, $\left\lVert\mathbf{A}\right\rVert_{2}=O(1)$ and $\left\lVert\mathbf{W}_{0}^{(1)}\right\rVert_{2}=O(1)$. Thus $\left\lVert{\mathbf{W}}^{(1)}\right\rVert_{2}\leq\left\lVert{\mathbf{W}}^{(1)}_{0}\right\rVert_{2}+\frac{R}{\sqrt{m}}=O(1)$. By Lemma A.2, with probability $1-O(H)e^{-\Omega(m/H)}$, $\left\lVert\mathbf{x}^{(0)}\right\rVert_{2}\in[2/3,4/3]$. Let

$\widetilde{\mathbf{W}}^{(1)}$ obviously satisfies $\widetilde{\mathbf{W}}^{(1)}\mathbf{x}^{(0)}={\mathbf{W}}^{(1)}\mathbf{x}^{\prime(0)}$. Then setting $\widetilde{\mathbf{W}}^{(2)},\ldots,\widetilde{\mathbf{W}}^{(H)}$ equal to ${\mathbf{W}}^{(2)},\ldots,{\mathbf{W}}^{(H)}$ will make all the following hidden layer vectors and $\mathbf{D}^{(h)}$ equal. It is also easy to verify that

so we know that $\widetilde{\mathbf{W}}\in B(R+O(\sqrt{m}\delta))$. ∎

By Lemma A.4, we can directly apply many results in which are only intended for the fixed data originally, to our scenario where the input can be perturbed, as long as we take the parameter radius as $\frac{R}{\sqrt{m}}+O(\delta)$ in their propositionsNote that in the corresponding region $B(R)$ is defined by the $2$-norm instead of the $F$-norm: $B_{2}(R):=\{\mathbf{W}:\left\lVert\mathbf{W}^{(h)}-\mathbf{W}_{0}^{(h)}\right\rVert_{2}\leq\frac{R}{\sqrt{m}},\forall h\in[H]\}$. Since obviously $B_{2}(R)\subset B(R)$, we can still apply their results to our case directly.. This can give us the following important lemma:

Given any fixed input $\mathbf{x}\in\mathcal{S}$. If $m\geq\max(d,\Omega(H\log H))$, $\frac{R}{\sqrt{m}}+\delta\leq\frac{c}{H^{6}(\log m)^{3}}$ for some sufficiently small constant $c$, then with probability at least $1-O(H)e^{-\Omega(m(R/\sqrt{m}+\delta)^{2/3}H)}$ over random initialization, we have for any $\mathbf{W}\in B(R)$ and any $\mathbf{x}^{\prime}\in\mathcal{S}$ with $\left\lVert\mathbf{x}-\mathbf{x}^{\prime}\right\rVert_{2}\leq\delta$,

By Lemma 8.2(b)(c) of , using the method of Lemma A.4 stated above, when $\frac{R}{\sqrt{m}}+\delta\leq\frac{c}{H^{9/2}(\log m)^{3}}$, with probability $1-e^{-\Omega(m(R/\sqrt{m}+\delta)^{2/3}H)}$, for any $\mathbf{W}\in B(R)$ and any $\mathbf{x}^{\prime}\in\mathcal{S}$ with $\left\lVert\mathbf{x}-\mathbf{x}^{\prime}\right\rVert_{2}\leq\delta$, we have for $h\in[H]$, Here the zero norm $\left\lVert\cdot\right\rVert_{0}$ denotes the number of non-zero entries of a matrix or a vector.

where (11) is also easily verified to hold for $h=0$. Next, according to Lemma 8.7 of We only use the setting when the network output is a scalar., when the bound (10) satisfies $O(m(\frac{R}{\sqrt{m}}+\delta)^{2/3}H)\leq\frac{m}{H^{3}\log m}$, with probability $1-e^{-\Omega((R/\sqrt{m}+\delta)^{2/3}Hm\log m)}$, we have for any $\mathbf{W}\in B(R)$ and any $\mathbf{x}^{\prime}\in\mathcal{S}$ with $\left\lVert\mathbf{x}-\mathbf{x}^{\prime}\right\rVert_{2}\leq\delta$, $\forall h\in[H]$,

Note that with our condition $\frac{R}{\sqrt{m}}+\delta\leq\frac{c}{H^{6}(\log m)^{3}}$, the previous requirements are all satisfied. Also, combining (11) with Lemma A.2, we know for $h=0,\cdots,H$,

Combining Equation (11), (12), (13), and Lemma A.3, we obtain

With Lemma A.5, we are ready to state an important bound that implies the loss function is close to being convex within the neighborhood $B(R)$ for any $\mathbf{x}\in\mathcal{S}$. We use the $\epsilon$-net to turn the result from a fixed $\mathbf{x}$ to all $\mathbf{x}\in\mathcal{S}$,

where the first inequality uses the convexity of $l$ w.r.t $f$ and the last inequality is due to the boundedness of $|\partial l/\partial f|$ is bounded, Lemma A.5, and $\nabla_{\mathbf{W}}f=(f^{\prime(1)},\ldots,f^{\prime(H)})$. We take $\delta=\frac{R}{\sqrt{m}}$. With $R=O\left(\frac{\sqrt{m}}{H^{6}(\log m)^{3}}\right)$ the requirement $\frac{R}{\sqrt{m}}+\delta\leq\frac{c}{H^{6}(\log m)^{3}}$ can be satisfied. Therefore, taking union event over all $N$ points, our proposition holds with probability

where the last equation is due to the condition $m=\Omega\left(\frac{d^{3/2}\log^{3/2}(\sqrt{m}/R)}{RH^{3/2}}\right)$. ∎

With the above preparations, we are ready to prove the main theorem.

We denote $\mathbf{W}_{t}$ as the parameter after $t$ steps of projected gradient descent, starting from the initialization $\mathbf{W}_{0}$. We perform a total of $T$ steps with step size $\alpha$.

For projected gradient descent, ${\mathbf{W}}_{t}\in B(R)$ holds for all $t=0,1,\cdots,T$. Recall that the update rule is $\mathbf{W}_{t+1}=\mathcal{P}_{B(R)}\left(\mathbf{V}_{t+1}\right)$ for $\mathbf{V}_{t+1}=\mathbf{W}_{t}-\alpha\nabla_{\mathbf{W}}L_{\mathcal{A}}(\mathbf{W}_{t})$. Let $d_{t}:=\|{\mathbf{W}}_{t}-{\mathbf{W}}_{\ast}\|_{F}$. We have

where the second inequality is due to Lemma A.6 and Lemma A.5, the third inequality is due to the definition of $\mathcal{A}_{\ast}$. Note that in order to satisfy the condition for Lemma A.6 and Lemma A.5, our choice $m=\max\{\Omega\left(\frac{H^{16}R^{9}}{\epsilon^{7}}\right),\Omega(d^{2})\}$ suffices. By induction on the above inequality, we have

where in the last inequality we use our choice of $\alpha=O\left(\frac{\epsilon}{mH^{2}}\right)$, $T=\Theta\left(\frac{R^{2}}{m\alpha\epsilon}\right)$, and also $m^{-1/6}R^{4/3}H^{5/2}\sqrt{\log m}\leq O(\epsilon)$, which is satisfied by $m=\Omega\left(\frac{H^{16}R^{9}}{\epsilon^{7}}\right)$.

Appendix B Proof of Theorem 5.1: Convergence Result for Two-Layer Networks

We denote $\mathbf{W}_{t}$ as the parameter after $t$ steps of projected gradient descent, starting from the initialization $\mathbf{W}_{0}$. We perform a total of $T$ steps with step size $\alpha$, where each step is an update $\mathbf{W}_{t+1}=\mathbf{W}_{t}-\alpha\nabla_{\mathbf{W}}L_{\mathcal{A}}(\mathbf{W}_{t})$. Firstly, the formula for the network gradient is

where $\mathbf{a}=(a_{1},\cdots,a_{\frac{m}{2}},a_{1}^{\prime},\cdots,a_{\frac{m}{2}}^{\prime})^{\top}$ is the parameter for the output layer. We can compute the Lipschitz property of $\nabla_{\mathbf{W}}f$ w.r.t $\mathbf{W}$: For any fixed $\mathbf{x}\in\mathcal{S}$,

In addition, we can also easily know that for $\mathbf{W}\in B(R)$ and $R=O(\sqrt{M})$, $\mathbf{x}\in\mathcal{S}$, we have

since the initialization satisfies $\left\lVert\mathbf{W}_{0}\right\rVert_{2}=O(\sqrt{m})$ with high probability given $m=\Omega(d)$ (see Lemma A.1), thereby $\left\lVert\mathbf{W}\right\rVert_{2}=O(\sqrt{m})$.

Denote $d_{t}=\|\mathbf{W}_{t}-\mathbf{W}_{*}\|_{F}$. Without a projection step, there could be two possible scenarios during the optimization process: Either $\mathbf{W}_{t}\in B(3R)$ holds for all $t=1,\cdots,T$, or there exists some $T_{0}<T$ such that $\mathbf{W}_{t}\in B(3R)$ for $t\leq T_{0}$ but $\mathbf{W}_{T_{0}+1}\notin B(3R)$. Either way, while $\mathbf{W}_{t}$ is still in $B(3R)$ up to $t-1$, we have

where the first inequality is based on (14) and (15), the second inequality is based on the definition of $L_{\ast}(\mathbf{W}_{\ast})$, and $c$ is some constant. Let $S_{t}=(1+\frac{c\alpha}{\sqrt{m}})^{t}$ which is a geometric series, and dividing (16) by $S_{t}$ we have

and note that $\sum_{i=0}^{t-1}\frac{1}{S_{i+1}}=\frac{\sqrt{m}}{c\alpha}\left(1-\frac{1}{S_{t}}\right)$, which yields

Now we will consider the two cases separately:

Case 1. $\mathbf{W}_{t}\in B(3R)$ holds for all $t=1,\cdots,T$. We have chosen $T=\frac{\sqrt{m}}{c\alpha}$, and then $S_{T}\approx e$. Also, since $d_{0}^{2}-\frac{d_{T}^{2}}{S_{T}}\leq d_{0}^{2}=O(R^{2})$, by choosing $m=\Omega(R^{4}/\epsilon^{2})$ and $\alpha=O\left(\epsilon\right)$, and taking $t=T$ in (17), we can obtain $\min_{t=0,\cdots,T}L_{\mathcal{A}}(\mathbf{W}_{t})-L_{\ast}(\mathbf{W}_{\ast})\leq\epsilon$.

Case 2. There exists some $T_{0}<T$ such that $\mathbf{W}_{t}\in B(3R)$ for $t\leq T_{0}$ but $\mathbf{W}_{T_{0}+1}\notin B(3R)$. Since $\mathbf{W}_{*}\in B(R)$, we know that $d_{0}\leq R$ and $d_{T_{0}+1}\geq 2R$. Still using the choice of parameters above, we have $d_{0}^{2}-\frac{d_{T_{0}+1}^{2}}{S_{T_{0}+1}}\leq R^{2}-(4/e)R^{2}\leq 0$. Hence, taking $t=T_{0}+1$ in (17), we obtain $\min_{t=0,\cdots,T}L_{\mathcal{A}}(\mathbf{W}_{t})-L_{\ast}(\mathbf{W}_{\ast})\leq\min_{t=0,\cdots,T_{0}}L_{\mathcal{A}}(\mathbf{W}_{t})-L_{\ast}(\mathbf{W}_{\ast})\leq\epsilon$.

So in any case the result is correct, thus we have proved the convergence without the need of projection. ∎

Appendix C Proof of Gradient Descent Finding Robust Classifier in Section 5

As discussed in Section 5, we will use the idea of random feature to approximate ${g}\in\mathcal{H}(K_{\sigma})$ on the unit sphere. We consider functions of the form

Let $\mathcal{F}_{\text{RF}}$ and $\mathcal{H}(K_{\sigma})$ be defined as above. Then $\mathcal{F}_{\text{RF}}$ is dense in $\mathcal{H}(K_{\sigma})$, and further, dense in $\mathcal{H}(K_{\sigma})$ w.r.t. $\left\lVert\cdot\right\rVert_{\infty,\mathcal{S}}$, where $\left\lVert f\right\rVert_{\infty,\mathcal{S}}=\sup_{\mathbf{x}\in\mathcal{S}}\left|f(\mathbf{x})\right|$.

We then show that we can approximate elements of $\mathcal{F}_{\text{RF}}$ by finite random features. Our results are inspired by . For the next theorem, recall Assumption 5.1, 5.3, the constant $C$ satisfies $\sigma^{\prime}$ is $C$-Lipschitz, $\left|\sigma^{\prime}(\cdot)\right|\leq C$.

This result is obtained by importance sampling, where we construct $\hat{h}$ with $c_{i}=\frac{c(\mathbf{w}_{i})}{Mp_{0}(\mathbf{w}_{i})}$. We first notice that $\left\lVert c_{i}\right\rVert_{2}=\frac{\left\lVert c(\mathbf{w}_{i})\right\rVert_{2}}{Mp_{0}(\mathbf{w}_{i})}\leq\frac{\left\lVert h\right\rVert_{\text{RF}}}{M}$ which satisfies the condition of the theorem. We then define the random variable

We bound this deviation from its expectation using McDiarmid’s inequality.

by using triangle, Cauchy-Schwartz inequality, $\left|\sigma^{\prime}(\cdot)\right|\leq C$ and $\left\lVert\mathbf{x}\right\rVert_{2}=1$.

where $\epsilon_{1},\cdots,\epsilon_{M}$ is a sequence of Rademacher random variables.

Since $\left|c_{i}^{\top}\mathbf{x}\right|\leq\left\lVert c_{i}\right\rVert_{2}\leq\frac{\left\lVert h\right\rVert_{\text{RF}}}{M}$ and $\sigma^{\prime}$ is $C$-Lipschitz, we have that $c_{i}^{\top}\mathbf{x}\sigma^{\prime}(\cdot)$ is $\frac{C\left\lVert h\right\rVert_{\text{RF}}}{M}$-Lipschitz in the scalar argument and zero when the scalar argument is zero. Following (18), by Talagrand’s lemma (Lemma 5.7) in together with Cauchy-Schwartz, Jensen’s inequality, we have

The proposition is proved by solving the $\epsilon$ while setting the right hand to the given $\delta$. ∎

. Finally, we construct $\mathbf{W}_{\ast}$ within a ball of the initialization $\mathbf{W}_{0}$ that suffers little robust loss $L_{\ast}(\mathbf{W}_{\ast})$. Using the symmetric initialization in (4), we have $f(\mathbf{W}_{0},\mathbf{x})=0$ for all $\mathbf{x}$. We then use the neural Taylor expansion w.r.t. the parameters:

where $\mathbf{w}_{i0}$ denotes the value of $\mathbf{w}_{i}$ at initialization. We omitted the second order term. The term (i) has the form of the random feature approximation, and so Proposition C.1 can be used to construct a robust interpolant.

In summary, we give the entire proof of Theorem 5.2 as follows.

By Assumption 5.2 with $\bar{\epsilon}$, there exists $g_{1}\in\mathcal{H}(K_{\sigma})$ such that

for every $\mathbf{x}_{i}^{\prime}\in\mathcal{B}(\mathbf{x}_{i})$, $i\in[n]$, where $\mathcal{B}(\mathbf{x}_{i})$ is the perturbation set.

such that $g_{3}=\sum_{i=1}^{m/2}c_{i}^{\top}\mathbf{x}\sigma^{\prime}(\mathbf{w}_{i}^{\top}\mathbf{x})$ satisfies

with probability at least $1-\delta$ on the initialization $\mathbf{w}_{i}$’s.

We decompose $f$ into the linear part and its residual:

Then set $\mathbf{w}_{i}=\mathbf{w}_{i0}+\sqrt{\frac{m}{4}}c_{i},\bar{\mathbf{w}}_{i}=-\sqrt{\frac{m}{4}}c_{i}+\bar{\mathbf{w}}_{i0}$, we have

Finally, set $m$ to be large enough ($=\Omega\left(\frac{\left\lVert g_{2}\right\rVert_{\text{RF}}^{4}}{\epsilon^{2}}\right)$) so that the left hand in Equation (19) no more than $\bar{\epsilon}$ and let $R_{\mathcal{D},\mathcal{B},\epsilon}$ to be $\left\lVert g_{2}\right\rVert_{\text{RF}}/2$. Then

The theorem follows by setting $\delta=0.01$. ∎

C.2 Example of Using Quadratic ReLU Activation

The dataset $\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}\subset\mathcal{S}$ and the perturbation set function $\mathcal{B}$ satisfies the following: There does not exist $\mathbf{x},\bar{\mathbf{x}}$ and $i,j$ such that $\mathbf{x}\in\overline{\mathcal{B}(\mathbf{x}_{i})}\cup(-\overline{\mathcal{B}(\mathbf{x}_{i})}),\bar{\mathbf{x}}\in\overline{\mathcal{B}(\mathbf{x}_{j})}\cup(-\overline{\mathcal{B}(\mathbf{x}_{j})})$ but $y_{i}\neq y_{j}$.

And then we can derive the finite-sum approximation result by random features.

For a given Lipschitz function $h\in\mathcal{H}(K_{\sigma})$. For $\epsilon>0,\delta\in(0,1)$, let $\mathbf{w}_{1},\cdots,\mathbf{w}_{M}$ be sampled i.i.d. from the uniform distribution on the surface of the sphere of radius $\sqrt{d}$ where

Let $h\in\mathcal{H}(K_{\sigma})$. For $\epsilon>0$, let $d\rho$ be the uniform distribution on $\mathcal{S}$. Let $\mathbf{w}_{1},\cdots,\mathbf{w}_{M}$ be sampled i.i.d. from uniform distribution on the surface of the sphere of radius $\sqrt{d}$, then for any $\delta\in(0,1)$, if

Then we can give the proof of Theorem C.1.

Let $Lip(f)$ denote the Lipschitz coefficient of $f$. We consider $\hat{h}$ in Lemma C.2, by the property of Lipschitz coefficient, we have

By Lemma C.2, for some constant $C_{\mathcal{D},\mathcal{B}}$, when $M=\Omega\left(\frac{C_{\mathcal{D},\mathcal{B}}}{\epsilon^{d+1}}\log\frac{1}{\epsilon^{d+1}\delta}\right)$, Equation (25) fails, so $\left\lVert h-\hat{h}\right\rVert_{\infty,\mathcal{S}}\leq\epsilon$ holds and at the same time we have $\sum_{r=1}^{M}\left\lVert c_{r}\right\rVert_{2}^{2}=O\left(\frac{C^{\prime}_{\mathcal{D},\mathcal{B}}}{M}\right)$ for some $C^{\prime}_{\mathcal{D},\mathcal{B}}$ that only depends on the data and the perturbation. ∎

Now, we get a similar but more explicit finite-sum approximation result for quadratic ReLU activation, we are then going to show that the RKHS is rich enough that Assumption 5.2 can be derived. We have the following lemma to characterize the capacity of the RKHS.

Then, by plugging-in the finite-sum approximation theorem (Theorem C.1) and the theorem of the capacity of RKHS (Theorem C.3) to the proof of Theorem 5.2 and combining with the optimization theorem, we can get an overall theorem for the quadratic-ReLU network which is similar to Corollary 5.1 but with explicit $\epsilon$ dependence:

Given data set on the unit sphere equipped with a compatible perturbation set function and an associated perturbation function $\mathcal{A}$, which also takes value on the unit sphere. Suppose Assumption 3.1, C.1 are satisfied. Let $C_{\mathcal{D},\mathcal{B}}^{\prime\prime}$ be a constant that only depends on the dataset $\mathcal{D}$ and perturbation $\mathcal{B}$. Then for any $2$-layer quadratic-ReLU network with width $m=\Omega(\frac{C_{\mathcal{D},\mathcal{B}}^{\prime\prime}}{\epsilon^{d+1}}\log\frac{1}{\epsilon})$, if we run gradient descent with stepsize $\alpha=O(\epsilon)$ for $T=\Omega(\frac{\sqrt{m}}{\alpha})$ steps, then with probability $0.99$,

Appendix D Proof of Theorem 6.1

We prove this theorem by an explicit construction of $\left[\frac{n}{2}\right]\times d$ data points that $\mathcal{F}$ is guaranteed to be able to shatter. Consider the following data points

we can always put $r=\delta$. This also holds in the case that $P_{i}$ or $N_{i}$ is empty, where we can simply put one ball centered at $\mathbf{x}_{i,1}=\mathbf{c}_{i}$ and put $\mathcal{B}_{r}(\mathbf{x}_{i,2})$ anywhere far away so that it is disjoint from the other balls. Recall that we have chosen $\left\lVert\mathbf{c}_{i}-\mathbf{c}_{i^{\prime}}\right\rVert_{2}\geq 6\delta$ for $i\neq i^{\prime}$. Such balls $\mathcal{B}_{r}(\mathbf{x}_{i,l}):i\in\{1,\cdots,\left[\frac{n}{2}\right]\},l\in\{1,2\},$ are disjoint since $\epsilon\leq\delta$, and $\left\lVert\mathbf{x}_{i,l}^{\prime}-\mathbf{c}_{i}\right\rVert_{2}\leq 2\delta$ for $l=1,2$. In this way, since $\mathcal{F}$ is an $n$-robust interpolation class, we can use the fact that there exists a function $f\in\mathcal{F}$ such that for any $i\in\{1,\cdots,\left[\frac{n}{2}\right]\}$, $f(\mathbf{x})=1$ for $\mathbf{x}\in\mathcal{B}_{r}(\mathbf{x}_{i,1})$ and $f(\mathbf{x})=-1$ for $\mathbf{x}\in\mathcal{B}_{r}(\mathbf{x}_{i,2})$. In this way, $f(\mathbf{x}_{i,j})=y_{i,j}$ holds for all $i,j$. Since the labels $y_{i,j}$ can be picked at will, by the definition of the VC-dimension, we know that the VC-dimension of $\mathcal{F}$ is always at least $\left[\frac{n}{2}\right]\times d$. ∎