Rademacher Complexity for Adversarially Robust Generalization

Introduction

In recent years, many modern machine learning models, in particular, deep neural networks, have achieved success in tasks such as image classification , speech recognition , machine translation , game playing , etc. However, although these models achieve the state-of-the-art performance in many standard benchmarks or competitions, it has been observed that by adversarially adding some perturbation to the input of the model (images, audio signals), the machine learning models can make wrong predictions with high confidence. These adversarial inputs are often called the adversarial examples. Typical methods of generating adversarial examples include adding small perturbations that are imperceptible to humans , changing surrounding areas of the main objects in images , and even simple rotation and translation . This phenomenon was first discovered by Szegedy et al. in image classification problems, and similar phenomena have been observed in other areas . Adversarial examples bring serious challenges in many security-critical applications, such as medical diagnosis and autonomous driving—the existence of these examples shows that many state-of-the-art machine learning models are actually unreliable in the presence of adversarial attacks.

Since the discovery of adversarial examples, there has been a race between designing robust models that can defend against adversarial attacks and designing attack algorithms that can generate adversarial examples and fool the machine learning models . As of now, it seems that the attackers are winning this game. For example, a recent work shows that many of the defense algorithms fail when the attacker uses a carefully designed gradient-based method . Meanwhile, adversarial training seems to be the most effective defense method. Adversarial training takes a robust optimization perspective to the problem, and the basic idea is to minimize some adversarial loss over the training data. We elaborate below.

2 Notation

3 Organization

The rest of this paper is organized as follows: in Section 2, we discuss related work; in Section 3, we describe the formal problem setup; we present our main results for linear classifiers and neural networks in Sections 4 and 5, respectively. We demonstrate our experimental results in Section 6 and make conclusions in Section 7.

Related Work

During the preparation of the initial draft of this paper, we become aware of another independent and concurrent work by Khim and Loh , which studies a similar problem. In this section, we first compare our work with Khim and Loh and then discuss other related work. We make the comparison in the following aspects.

For binary classification problems, the adversarial Rademacher complexity upper bound by Khim and Loh is similar to ours. However, we provide an adversarial Rademacher complexity lower bound that matches the upper bound. Our lower bound shows that the adversarial Rademacher complexity is never smaller than that in the natural setting, indicating the hardness of adversarially robust generalization. As mentioned, although our lower bound is for Rademacher complexity rather than generalization, Rademacher complexity is a tight bound for the rate of uniform convergence of a loss function class and thus in many settings can be a tight bound for generalization. In addition, we provide a lower bound for the adversarial Rademacher complexity for neural networks. These lower bounds do not appear in the work by Khim and Loh .

We discuss the generalization bounds for the multi-class setting, whereas Khim and Loh focus only on binary classification.

Both our work and Khim and Loh prove adversarial generalization bound using surrogate adversarial loss (upper bound for the actual adversarial loss). Khim and Loh use a method called tree transform whereas we use the SDP relaxation proposed by . These two approaches are based on different ideas and thus we believe that they are not directly comparable.

We proceed to discuss other related work.

Besides generalization property, another recent line of work aim to design provable defense against adversarial attacks. Two examples of provable defense are SDP relaxation and LP relaxation . The idea of these methods is to construct upper bounds of the adversarial risk that can be efficiently evaluated and optimized. The analyses of these algorithms usually focus on minimizing training error and do not have generalization guarantee; in contrast, we focus on generalization property in this paper.

A few other lines of work have conducted theoretical analysis of adversarial examples. Wang et al. analyze the adversarial robustness of nearest neighbors estimator. Papernot et al. try to demonstrate the unavoidable trade-offs between accuracy in the natural setting and the resilience to adversarial attacks, and this trade-off is further studied by Tsipras et al. through some constructive examples of distributions. Fawzi et al. analyze adversarial robustness of fixed classifiers, in contrast to our generalization analysis. Fawzi et al. construct examples of distributions with large latent variable space such that adversarially robust classifiers do not exist; here we argue that these examples may not explain the fact that adversarially perturbed images can usually be recognized by humans. Bubeck et al. try to explain the hardness of learning an adversarially robust model from the computational constraints under the statistical query model. Another recent line of work explains the existence of adversarial examples via high dimensional geometry and concentration of measure . These works provide examples where adversarial examples provably exist as long as the test error of a classifier is non-zero.

Problem Setup

and to this end, a natural way is to conduct adversarial training—minimizing the adversarial empirical risk

For any $\delta\in(0,1)$, with probability at least $1-\delta$, the following holds for all $f\in\mathcal{F}$,

Linear Classifiers

We prove Theorem 2 in Appendix A. We can see that the adversarial Rademacher complexity, i.e., $\mathfrak{R}_{\mathcal{S}}(\widetilde{\mathcal{F}})$ is always at least as large as the Rademacher complexity in the natural setting. This implies that uniform convergence in the adversarial setting is at least as hard as that in the natural setting. In addition, since $\max\{a,b\}\geq\frac{1}{2}(a+b)$, we have

2 Multi-class Classification

Consider the above multi-class classification setting. For any fixed $\gamma>0$, we have with probability at least $1-\delta$, for all $f\in\mathcal{F}$,

Consider the above adversarial multi-class classification setting. For any fixed $\gamma>0$, we have with probability at least $1-\delta$, for all $f\in\mathcal{F}$,

2.2 Multi-class Linear Classifiers

Consider the multi-class linear classifiers in the above setting, and suppose that $\frac{1}{p}+\frac{1}{q}=1$, $p,q\geq 1$. For any fixed $\gamma>0$ and $W>0$, we have with probability at least $1-\delta$, for all $\mathbf{W}$ such that $\|\mathbf{W}^{\top}\|_{p,\infty}\leq W$,

We prove Theorem 3 in Appendix B.1 for completeness. In the adversarial setting, we have the following margin bound.

Consider the multi-class linear classifiers in the adversarial setting, and suppose that $\frac{1}{p}+\frac{1}{q}=1$, $p,q\geq 1$. For any fixed $\gamma>0$ and $W>0$, we have with probability at least $1-\delta$, for all $\mathbf{W}$ such that $\|\mathbf{W}^{\top}\|_{p,\infty}\leq W$,

We prove Theorem 4 in Appendix B.2. As we can see, similar to the binary classification problems, if $p>1$, the margin bound in the adversarial setting has an explicit polynomial dependence on $d$, whereas in the natural setting, the margin bound does not have dimension dependence. This shows that, at least for the generalization upper bound that we obtain, the dimension dependence in the adversarial setting also exists in the multi-class classification problems.

Neural Networks

We start with a comparison of Rademacher complexities of neural networks in the natural and adversarial settings. Although naively applying the definition of Rademacher complexity may provide a loose generalization bound , when properly normalized by the margin, one can still derive generalization bound that matches experimental observations via Rademacher complexity . Our comparison shows that, when the weight matrices of the neural networks have bounded norms, in the natural setting, the Rademacher complexity is upper bounded by a quantity which only has logarithmic dependence on the dimension; however, in the adversarial setting, the Rademacher complexity is lower bounded by a quantity with explicit $\sqrt{d}$ dependence.

Consider the neural network hypothesis class

On the other hand, in this work, we prove the following result which shows that when the product of the spectral norms of all the weight matrices is bounded, the Rademacher complexity of the adversarial loss function class is lower bounded by a quantity with an explicit $\sqrt{d}$ factor. More specifically, for binary classification problems, since

and $\phi(\cdot)$ is Lipschitz, we consider the function class

Let $\widetilde{\mathcal{F}}$ be defined as in (6). Then, there exists a universal constant $c>0$ such that

We prove Theorem 6 in Appendix C.1. This result shows that if we aim to study the Rademacher complexity of the function class defined as in (6), a $\sqrt{d}$ dimension dependence may be unavoidable, in contrast to the natural setting where the dimension dependence is only logarithmic.

2 Generalization Bound for Surrogate Adversarial Loss

For any $(\mathbf{x},y)$, $\mathbf{W}_{1}$, $\mathbf{W}_{2}$, and $y^{\prime}\neq y$,

where $Q(\mathbf{v},\mathbf{W})$ is defined as

Consider the neural network hypothesis class

Then, for any fixed $\gamma>0$, with probability at least $1-\delta$, we have for all $f_{\mathbf{W}}(\cdot)\in\mathcal{F}$,

Experiments

In this section, we validate our theoretical findings for linear classifiers and neural networks via experiments. Our experiments are implemented with Tensorflow on the MNIST dataset . The implementation of the experiments can be found at https://github.com/dongyin92/adversarially-robust-generalization.

2 Neural Networks

Conclusions

D. Yin is partially supported by Berkeley DeepDrive Industry Consortium. K. Ramchandran is partially supported by NSF CIF award 1703678. P. Bartlett is partially supported by NSF grant IIS-1619362. The authors would like to thank Justin Gilmer for helpful discussion.

References

Appendix A Proof of Theorem 2

Thus, we conclude that $\widetilde{f}_{\mathbf{w}}(\mathbf{x},y)=y\langle\mathbf{w},\mathbf{x}\rangle-\epsilon\|\mathbf{w}\|_{1}$, and therefore

Define $\mathbf{u}:=\sum_{i=1}^{n}\sigma_{i}y_{i}\mathbf{x}_{i}$ and $v:=\epsilon\sum_{i=1}^{n}\sigma_{i}$. Then we have

Since the supremum of $\langle\mathbf{w},\mathbf{u}\rangle-v\|\mathbf{w}\|_{1}$ over $\mathbf{w}$ can only be achieved when $\operatorname{sgn}(w_{i})=\operatorname{sgn}(u_{i})$, we know that

Now we prove an upper bound for $\mathfrak{R}_{\mathcal{S}}(\widetilde{\mathcal{F}})$. By triangle inequality, we have

where the last step is due to Khintchine’s inequality.

We then proceed to prove a lower bound for $\mathfrak{R}_{\mathcal{S}}(\widetilde{\mathcal{F}})$. According to (10) and by symmetry, we know that

Then, combining (10) and (11) and using triangle inequality, we have

Appendix B Multi-class Linear Classifiers

According to the multi-class margin bound in , for any fixed $\gamma$, with probability at least $1-\delta$, we have

In the special case of linear classifiers $\mathcal{F}=\{f_{\mathbf{W}}(\mathbf{x}):\|\mathbf{W}^{\top}\|_{p,\infty}\leq W\}$, we can see that

B.2 Proof of Theorem 4

Since the loss function in the adversarial setting is

Since we consider linear classifiers, we have

To see this, we can see that according to (13),

If $\min_{k\neq y}h^{(k)}_{\mathbf{W}}(\mathbf{x},y)\leq\gamma$, we have $\min_{k\neq y}h^{(k)}_{\mathbf{W}}(\mathbf{x},y)=\min_{k\in[K]}h^{(k)}_{\mathbf{W}}(\mathbf{x},y)$, since $h^{(y)}_{\mathbf{W}}(\mathbf{x},y)=\gamma$. On the other hand, if $\min_{k\neq y}h^{(k)}_{\mathbf{W}}(\mathbf{x},y)>\gamma$, then $\min_{k\in[K]}h^{(k)}_{\mathbf{W}}(\mathbf{x},y)=\gamma$. In this case, we have $\phi_{\gamma}(\min_{k\neq y}h^{(k)}_{\mathbf{W}}(\mathbf{x},y))=\phi_{\gamma}(\min_{k\in[K]}h^{(k)}_{\mathbf{W}}(\mathbf{x},y))=0$. Therefore, we can see that (14) holds.

We proceed to analyze $\mathfrak{R}_{\mathcal{S}}(\mathcal{F}_{k})$. The basic idea is similar to the proof of Theorem 2. We define $\mathbf{u}_{y}=\sum_{i=1}^{n}\sigma_{i}\mathbf{x}_{i}\mathds{1}(y_{i}=y)$ and $v_{y}=\sum_{i=1}^{n}\sigma_{i}\mathds{1}(y_{i}=y)$. Then, we have

where the last equality is due to the same derivation as in the proof of Theorem 2. Let $n_{y}=\sum_{i=1}^{n}\mathds{1}(y_{i}=y)$. Then, we apply triangle inequality and Khintchine’s inequality and obtain

where the last step is due to Cauchy-Schwarz inequality.

Appendix C Neural Network

We first review a Rademacher complexity lower bound in .

and $\widehat{\mathcal{F}}^{\prime}=\{\mathbf{x}\mapsto\langle\mathbf{w},\mathbf{x}\rangle:\|\mathbf{w}\|_{2}\leq\frac{r}{2}\}$. Then we have $\widehat{\mathcal{F}}^{\prime}\subseteq\widehat{\mathcal{F}}$, and thus there exists a universal constant $c>0$ such that

According to Lemma 2, in the adversarial setting, by defining

we have $\widetilde{\mathcal{F}}^{\prime}\subseteq\widetilde{\mathcal{F}}$. Therefore, there exists a universal constant $c>0$ such that

where the last inequality is due to Theorem 2.

C.2 Proof of Lemma 1

Since $Q(\cdot,\cdot)$ is a linear function in its first argument, we have for any $y,y^{\prime}\in[K]$,

where the first inequality is due to the property of ramp loss, the second inequality is by the definition of the margin, the third inequality is due to Theorem 7, the fourth inequality is due to (16), the fifth inequality is by the definition of the margin and the last inequality is due to the property of ramp loss.

C.3 Proof of Theorem 8

We study the Rademacher complexity of the function class

Define $M_{\mathcal{F}}:=\{(\mathbf{x},y)\mapsto M(f_{\mathbf{W}}(\mathbf{x}),y):f_{\mathbf{W}}\in\mathcal{F}\}$. Then we have

where we use the Ledoux-Talagrand contraction inequality and the convexity of the supreme operation. For the first term, since we have $\|\mathbf{W}_{1}\|_{1}\leq b_{1}$, we have $\|\mathbf{W}_{1}^{\top}\|_{2,1}\leq b_{1}$. Then, we can apply the Rademacher complexity bound in and obtain

Now consider the second term in (17). According to , we always have

In addition, we know that when $\mathbf{P}\succeq 0$ and $\operatorname{diag}(\mathbf{P})\leq 1$, we have

where the first inequality is due to (19), the second inequality is due to Khintchine’s inequality, the third inequality is due to Hölder’s inequality, and the fourth inequality is due to the definition of $Q(\cdot,\cdot)$ and (20), the fifth inequality is a direct upper bound, and the last inequality is due to (21).