The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization

Introduction

In recent years, modern machine learning methods have exhibited their superiority over traditional models in an abundance of machine learning tasks, e.g., image classification , speech recognition and language translation , medical diagnosis , text recognition and information extraction , online fraud detection , and self-driving cars , among others. However, they can also be extremely vulnerable to adversarial, human-imperceptible data modifications . This vulnerability is even more concerning and dangerous when machine learning methods are used in scenarios directly connected to human safety such as medical diagnosis (misinterpreting medical images) or self-driving cars (misreading traffic signs). To circumvent these issues, practitioners introduce adversarial training in order to produce adversarially robust models that can still make consistently correct predictions, even when faced with perturbed data.

There is a large body of work dedicated to adversarially robust models . In particular, it has been shown that there exists a trade-off between the generalization of a model (i.e. the standard accuracy) and its robustness to adversarial perturbation . Along a similar vein, Schmidt et al. showed that adversarially robust models need more training data compared to their standard counterparts in order to achieve the same generalization performance. In this paper, we want to further investigate these ideas and explore whether simply adding more data is enough for adversarially robust models to catch up to the generalization ability of their standard counterparts.

Previous works have studied the generalization of adversarially robust models from a variety of perspectives. For instance, Yin et al. and Khim and Loh gave bounds on the generalization error of adversarially robust models via Rademacher complexity. More recently, Chen et al. studied the influence of a larger training set upon the gap between the generalization performance of an adversarially robust model and a standard model. They proved that more training data could result in expansion of the gap and denied the belief that more training data always helps adversarially robust models reach a similar generalization performance to the standard model. Building on these works, our goal is to move past bounds and gaps, and directly characterize how the size of training set affects the accuracy of adversarially robust models on unperturbed test data.

A conventional wisdom in machine learning is that a larger training set will result in better generalization on the test data. We provably establish a surprising, and to some extent even paradoxical, result that more training data can hurt the generalization of adversarially robust models. We first consider a linear classification problem with a linear loss function and identify three regimes of different adversary strengths, i.e., the weak, medium, and strong adversary regimes.

In the strong adversary regime, the generalization of adversarially robust models deteriorates with more training data, except for a possible short initial stage where the generalization is improved with more data.

The medium adversary regime is probably the most interesting one among the three regimes. In this regime, the evolution of the generalization performance of adversarially robust models could be a double descent curve. In particular, at the initial stage, the generalization loss on the test data is reduced with more training data. At the intermediate stage, however, the generalization loss increases as there is more training data (more data hurts the generalization of adversarial robust models). At the final stage, more training data improves the generalization performance.

In the weak adversary regime, the generalization is consistently improved with more training data.

We then move to the analysis of the 0-1 loss and investigate a two-dimensional classification problem where the candidate decision boundary is given by a piecewise constant function. Similar weak and strong adversary regimes are observed under this setting. In particular, in the strong adversary regime, more data always hurts the generalization of adversarially robust models.

We complement the above theroetical results with empirical studies on important machine learning models, including support vector machines (SVMs), linear regression, and Gaussian mixture classification with 0-1 loss. We observe a similar phenomenon that more data hurts generalization in adversarial training. These empirical results suggest that the observed phenomenon may be ubiquitous across different models and loss functions and that we need to reflect on the true role that the size of the training set plays in adversarial training.

Related Work

In this section, we briefly discuss some additional papers on the generalization of adversarially robust models and the double descent phenomenon, which are most relevant to our work.

Schmidt et al. showed that adversarially robust models need more training data compared to their standard counterpart. They considered a Gaussian mixture model similar to ours and proved that the training of a robust model requires a training set with size $\Omega(d)$ where $d$ is the dimension of the data, whereas the standard model only needs a constant number of data points. Bubeck et al. studied a binary classification problem under a statistical query setting and showed that to train a robust classifier one needs exponentially (in dimension $d$) many queries, while only polynomially many to train a standard classifier. The main difference between their work and our work is that we quantify the training dynamic in terms of the size of the training set. Very recently, Javanmard et al. precisely characterized the trade-off of standard/robust accuracy under the linear regression setting. Raghunathan et al. gave empirical evidence that adversarial training could hurt the standard accuracy, despite its improvement on robustness. The PAC-learning setting has also been studied by several authors . Cullina et al. provided a polynomial (in the VC dimension) upper bound for the sample complexity, while Diochnos et al. gave a lower bound for the sample complexity which is exponential in the dimension of the input.

The strength of the adversary is crucial in the adversarial training. Theoretically, Dohmatob showed that a classifier with high standard accuracy can inevitably be fooled by a strong adversary. Empirically, Papernot et al. and Tsipras et al. found that a strong adversary can drive down standard accuracy for robust models. Ilyas et al. found that the adversarial training tends to learn non-robust features and omit robust ones if the adversary is too strong.

The double descent phenomenon has been studied by several authors. Belkin et al. and Mei and Montanari provably showed the existence of double descent curves for the generalization error. However, we would like to remark that the double descent curve they considered is in terms of the number of parameters (model complexity), while ours is sample-wise. Empirically, Nakkiran et al. also discovered a sample-wise double descent phenomenon.

Preliminaries

The generalization error of the robust classifier is given by

where the inner expectation is over the randomness of the test data point and the outer expectation is over the randomness of the training dataset. The test and training data are assumed to be independently sampled from the same distribution. The generalization error can be interpreted as the expected loss of the robust model over standard/unperturbed test data.

Theoretical Results

In this section we study two different binary classification models. In Section 4.1, we analyze the Gaussian mixture model under linear loss and prove the existence of three possible regimes (weak, medium and strong adversary regimes), in which more training data can help, double descend, or hurt generalization of the adversarially trained model, respectively. In Section 4.2, we construct a model called the Manhattan model that enables us to analyze the 0-1 loss and prove that analogous weak and strong adversary regimes also exist under a different loss function.

We study how the generalization error of the robust model evolves as the size of the training dataset changes, i.e., the dependence of $L_{n}$ on $n$. By (2) the generalization error of the robust classifier under linear loss is given by

For the Gaussian classification problem under the linear loss, we identify that the behavior of $L_{n}$ exhibits a phase transition which is determined by the strength of the adversary. Our main result is summarized by Theorem 1.

Given $n$ i.i.d. training data points $(x_{i},y_{i})\sim\cD_{\cN}$, if the robust classifier is defined by (3) and its generalization error is defined by (4), then there exist $0<\delta_{1}<\delta_{2}<1$, such that

If $0<\varepsilon<\delta_{1}\cdot\min_{j\in[d]}\mu(j)$, then $L_{n}<L_{n-1}$ for all $n$. That is, the loss $L_{n}$ monotonically decreases as the number of training points $n$ increases.

If $\delta_{2}\cdot\max_{j\in[d]}\mu(j)<\varepsilon<\min_{j\in[d]}\mu(j)$, and we further assume that $\frac{\mu(j)}{\sigma(j)}$ is the same for all $j$, then there exist $N_{1}<N_{2}<N_{3}<N_{4}$ such that

If $\max_{j\in[d]}\mu(j)\leq\varepsilon$, then there exists $N_{5}$ such that $L_{n}>L_{n-1}$ for all $n>N_{5}$.

Theorem 1 verifies the existence of three possible regimes during the commonly used adversarial training procedure and gives conditions for when the phase transition between these regimes will take place. Part (a) identifies the weak regime, showing that when the strength of the adversary $\varepsilon$ is small compared to the signal $\mu$, the generalization error decreases as the size of the training dataset increases. In this regime, the generalization benefits from the use of a large training set. This regime is illustrated by Fig. 1(a), where the curve is always decreasing.

However, as the adversary becomes stronger, we reach the medium regime and things change. Part (b) proves the existence of a double descent curve for the generalization error. It shows that when $\varepsilon$ becomes larger and approaches the signal in magnitude, the generalization error will first decrease as more training data is used. Surprisingly, once it reaches a certain point, it will start increasing as we feed more data. This increasing stage continues until the dataset size reaches some threshold $N_{2}$ and then the error will decrease again. The medium adversary regime is illustrated by Fig. 1(b), where the three stages are marked by three different colored areas.

If the adversary’s strength reaches the signal level or becomes even stronger, then for all sufficiently large $n$, the generalization error monotonically increases as the size of training set increases. This strong regime is described in part (c) of Theorem 1 and illustrated by Fig. 1(c). Note that despite the decreasing stage near the very beginning, the loss keeps going up after the threshold $N_{5}$.

Furthermore, we see that in the medium regime, the length of the increasing stage is given by $N_{3}-N_{2}$, according to part (b) of Theorem 1. We would like to remark that the model can have an arbitrarily long increasing stage, which depends on the adversary’s strength. To better interpret this idea and the meaning behind Theorem 1, we consider the following special case where $\mu(j)=\mu_{0}$ and $\sigma(j)=\sigma_{0}$ for all $j\in[d]$. In this special case, it can be shown that in the medium regime, as $\varepsilon$ approaches the signal strength $\mu_{0}$, the increasing stage grows and can be arbitrarily long.

Under the same assumption as Theorem 1 and further assuming that $\mu(j)=\mu_{0}$ and $\sigma(j)=\sigma_{0}$ for all $j\in[d]$, we have

If $0<\varepsilon<\delta_{1}\mu_{0}$, then $L_{n}<L_{n-1}$ for all $n$.

If $\delta_{2}\mu_{0}<\varepsilon<\mu_{0}$, then there exist $N_{1}(\varepsilon)<N_{2}(\varepsilon)$ such that

and $\lim_{\varepsilon\to\mu_{0}^{-}}N_{2}(\varepsilon)-N_{1}(\varepsilon)=+\infty$.

If $\mu_{0}\leq\varepsilon$, then there exists $N_{3}(\varepsilon)$ such that $L_{n}>L_{n-1}$ for all $n>N_{3}$.

Part (a) and (c) of 2 are a re-statement of corresponding parts of Theorem 1 in the simplified setting. Part (b) additionally states that as $\varepsilon$ increases towards $\mu_{0}$, the length of the increasing stage goes to infinity. In this setting, the three regimes are marked by the thresholds $\delta_{1}\mu_{0}$, $\delta_{2}\mu_{0}$ and $\mu_{0}$.

Fig. 2 illustrates the behavior of the generalization error in this simplified setting. In the simulation we set the parameters as $d=1$, $\mu_{0}=1$ and $\sigma_{0}=2$ (for all three plots). Fig. 2(a) shows the weak adversary regime. We see that the generalization error maintains a decreasing trend when $\varepsilon$ is as large as half the signal strength. In Fig. 2(b), it is clear that the generalization error has a double descent curve. At first there is a decreasing stage, which is followed by an increasing stage. Also observe that as $\varepsilon$ becomes larger, the error increases faster during the increasing stage. The error will finally start decreasing as the size of training dataset reaches the second decreasing stage. On the contrary, in the strong adversary regime, the increasing stage lasts forever and the error keeps increasing no matter how much data is provided, as illustrated by Fig. 2(c).

2 Manhattan Model

In general, the 0-1 loss is mathematically intractable for most data models and computationally prohibitive to optimize in practice. With this in mind, we introduce a conceptual classification model that we call the Manhattan model. Note that this model is highly simplified and thus unlikely to be suitable for modeling real-world problems. Instead, the purpose of the Manhattan model is to allow a mathematical study of the 0-1 loss, and thus provide a springboard for the study of 0-1 loss in more complicated models.

We start by describing the data distribution. Assume we have data points $(x,y)\in\bR^{2}\times\{\pm 1\}$, where the support of $x$ is given as $x=(s,t)\in\{(i,y\mu)$ : $i\in[N],\ y\in\{\pm 1\}\}$, where $0<\mu<1/4$. In other words, every data point $(x,y)$ consists of a positive or negative label $y$ and a point on the 2-D plane $x=(s,t)$ where $s$ is an integer between 1 and $N$ and $t$ is either $\mu$ or $-\mu$ depending on whether the label $y$ is $+1$ or $-1$. Thus, the support consists of exactly $2N$ points with half in the positive class and half in the negative class. The data is uniformly sampled from these $2N$ points and this distribution is denoted by $\cD_{2N}$.

Next, we consider a conceptual classifier of the form of a step function over the 2-D $(s,t)$-plane. That is, a classifier is defined by a function $t=f(s)$ such that $f\in F$ where

A point $x=(s,t)$ is classified $+1$ if $t>f(s)$ and $-1$ if $t<f(s)$. If $t=f(s)$, then $x$ is classified as either $+1$ or $-1$ uniformly at random. Fig. 3 illustrates the support of the data distribution, as well as a possible classifier $f(s)$.

where $H(s)=\mathds{1}[s>0]+\frac{1}{2}\mathds{1}[s=0]$ is the Heaviside step function. Note that the RHS of Eq. 6 is the limit of a sequence of sets. This slight abuse of notation is justified by the following Lemma 3, which shows for all sufficiently small $\lambda$, the set $S(\lambda)$ remains fixed. We define the set of candidate classifiers without the penalty as

For all sufficiently small $\lambda>0$ and for any $\varepsilon<1/2$, the set $S(\lambda)$ defined by Eq. 6 is equivalent to the following set which is nonempty

The generalization error of $f_{n}^{\text{rob}}$ is then given by

Assume the training data $(x_{i},y_{i})\sim\cD_{2N}$ where $i\in[n]$. For the robust classifier defined by (6) and its generalization error defined by (8), we have

If $\ 0<\varepsilon<2\mu$, then L_{n}=0\ for all $n$.

If $\ 2\mu<\varepsilon\leq 1/2$, then L_{n+1}>L_{n}\ for all $n\geq 1$.

Again, the purpose of the Manhattan model is not to model any real-world problems, but instead to show that adversarial training under a 0-1 loss can also be characterized with weak/strong regimes. More generally, we have now shown that the existence of weak/strong regimes is not solely an artifact of the linear loss used in Section 4.1, and thus that it may not be surprising to see analogous results for a much broader class of loss functions.

Empirical Results

In this section, we empirically study the generalization error of robust models in three settings.

We remark that under this setting, the robust classifier is not unique and the set of classifiers is an interval (details in Section D.1). Thus to select a classifier, we consider two tiebreaking methods. One is the agnostic tiebreak, which means the classifier is chosen uniformly at random from the interval. The other is the optimal tiebreak in hindsight, referring to picking the classifier from the interval with the smallest expected test loss. The test loss of a classifier $w$ is given by

where $\Phi$ is the CDF of the standard normal distribution. In Section D.2, we explain that the optimal classifier in hindsight is the one that is closest to among the interval of classifiers.

Fig. 4(a) and Fig. 4(b) illustrate the test loss versus the size of the training dataset under the agnostic tiebreak and the optimal tiebreak in hindsight. We set $\mu=\sigma=1$ and use the same set of values for $\varepsilon$ for both tiebreaking methods. We have three observations. First, the generalization error is increasing in $n$ when $\varepsilon$ is larger than the signal strength. This confirms the existence of the strong adversary regime under the 0-1 loss. Second, for small enough $\varepsilon$ (e.g. $\varepsilon\leq 0.5$), the generalization error is decreasing in $n$ (more precisely after $n=3$), thus also confirming a weak adversary regime. For the medium adversary where $\varepsilon$ is in between $0.7$ and $1.0$, the curve has an increasing stage followed by a decreasing stage, which is very similar to what we see in Fig. 2(b).

2 Support Vector Machine

We study the soft-margin support vector machine with hinge loss (details in Appendix E). The dimension $d$ equals 2 and the data is generated as $y\sim\operatorname{Unif}(\{\pm 1\})$ and $X\sim\cN(y\mu,I)$ where $\mu=(1,1)^{\top}$. The results are shown in Fig. 4(c) and Fig. 4(d). We find that for small $\varepsilon$ the standard test loss keeps decreasing, while for large $\varepsilon$ it keeps increasing. The curves reveal a transition from the weak to the strong regime as $\varepsilon$ grows, and such transition occurs when $\varepsilon$ is in between 0.5 and 0.7. Note that at $\varepsilon=0.7$, the test loss increases even though the strength of the adversary is still weaker than the signal level. This may indicate that for more complicated models (such as SVMs), even relatively weaker adversaries can result in situations where more data always increases the test loss.

3 Linear Regression

Conclusion

The goal of adversarial training is to produce robust models that provide protection against attacks that make perturbations to the data at test time. While protection against such attacks is undoubtedly important, we still want our robust models to perform well on unperturbed data. However, our results indicate that there are scenarios in which it is impossible for current approaches to achieve low generalization error on both datasets simultaneously. This is in direct contradiction to one of the primary tenets of machine learning, which is that more data should help us learn better. Our findings suggest that the current adversarial training framework may not be ideal and that fundamentally new ideas may be required to develop models that can reliably perform well on both perturbed and unperturbed test sets.

Acknowledgements

We would like to thank Peter Bartlett and Yiping Lu for helpful comments and thank Marko Mitrovic for his help in preparation of the paper.

References

Appendix A Proof of Theorem 1 and 2

Before proving Theorem 1, we need to establish several lemmas. First we restate the result by Chen et al. that gives the closed form solution for the robust classifier.

First, we define the error function $\operatorname{\textnormal{erf}}(\cdot):\bR\to\bR$ by

In light of the density of the standard normal distribution and by a change of variable, we have

In addition, we define the function $L(\cdot,\cdot):\ \bR^{2}\to\bR$ by

where $\mu(j)$ and $\sigma(j)$ are defined in the data generation process described at the beginning of Section 4.

Lemma 7 gives the expression for the generalization error.

Suppose that the generalization error is defined as in (4). Then we have

where $v_{j}$ and $\varepsilon^{\prime}_{j}$ are defined in (12).

By (4), 5 and the independence between test and training data, we have

Since $y_{i}x_{i}\sim\cN(\mu,\Sigma)$, we have $u\sim\cN(\mu,\frac{\Sigma}{n})$, and it follows that

where $z$ is a standard normal random variable. By Lemma 6 we have

which implies that $L_{n}=W\sum_{j\in[d]}\mu(j)L(v_{j},\varepsilon^{\prime}_{j})$.

Note that $L(v,\varepsilon^{\prime})$ is differentiable in $v$, and by our definition each $v_{j}$ is smooth and monotonic in $n$. Together with Lemma 7 we know that $L_{n}$ is differentiable w.r.t. $n$. Therefore, to study the dynamic of $L_{n}$ in $n$, it is equivalent to studying the derivative $\frac{dL_{n}}{dn}$. We define the function $f(\cdot,\cdot):\bR^{2}\to\bR$ by

In Lemma 8, we compute the partial derivative of $L$.

Let $t=e^{-v^{2}}$ and $f$ be defined as in (A). The partial derivative of $L(v,\varepsilon^{\prime})$ w.r.t. $v$ is given by

The proof of Theorem 1 follows from studying the derivative $\frac{dL_{n}}{dn}$. Lemma 8 implies that the derivative depends on the sign of the function $f$. We investigate the sign of $f$ in Lemma 9.

There exist $0<\delta_{1}\leq\delta_{2}<1$ such that the following statements hold.

When $0<\varepsilon^{\prime}<\delta_{1}$, $f(t,\varepsilon^{\prime})<0$ for $\forall\ t\in(0,1)$.

When $\delta_{2}<\varepsilon^{\prime}<1$, there exist $0<\tau_{1}<\tau_{2}<1$ depending on $\varepsilon^{\prime}$ such that

When $1\leq\varepsilon^{\prime}$, $f(t,\varepsilon^{\prime})$, there exists $\tau_{2}<1$ such that

We compute the partial derivative of $f$ w.r.t. $t$

The proof of Lemma 9 uses the following Lemma 10 and Lemma 11. To make it concise, whenever we fix $\varepsilon^{\prime}$ in the context, we omit $\varepsilon^{\prime}$ and write $f(t)=f(t,\varepsilon^{\prime})$ and $f^{\prime}(t)=f^{\prime}(t,\varepsilon^{\prime})$.

The right-sided limit of $f^{\prime}$ at is given by

The proof of Lemma 10 follows from direct computation. Using Lemma 10, we obtain Lemma 11.

For any fixed $0<\varepsilon^{\prime}<1$, there exists some $t_{0}=t_{0}(\varepsilon^{\prime})\in(0,1)$ such that $f^{\prime}(t)$ is strictly increasing for $t\in(0,t_{0})$ and strictly decreasing for $t\in(t_{0},1)$. For any fixed $1\leq\varepsilon^{\prime}\leq 2$, $f^{\prime}(t)$ is strictly decreasing for $t\in(0,1)$.

We differentiate $f^{\prime}$ w.r.t. $t$ to get

First we consider the case where $0<\varepsilon^{\prime}<1$. The function $f^{\prime}$ is continuously differentiable on $(t,\varepsilon^{\prime})\in(0,1)\times(0,1)$. For any fixed $\varepsilon^{\prime}<1$, setting $\frac{\partial f^{\prime}(t)}{\partial t}=0$ yields the unique solution of $t$ in $(0,1)$ as

Since $\lim_{t\to 0^{+}}f^{\prime}(t)=-\infty$, $f^{\prime}(t)$ is strictly increasing w.r.t. $t\in(0,t_{0})$. Also note that

which together with $\frac{\partial}{\partial t}(f^{\prime}(t_{0}))=0$ indicates that $f^{\prime}(t)$ is strictly decreasing for $t\in(t_{0},1)$. We conclude that $t_{0}$ is the unique local extreme and also the global maximum of $f^{\prime}(t)$ on $t\in(0,1)$.

For $1\leq\varepsilon^{\prime}\leq 2$, we have for all $t\in(0,1)$

It follows that $\frac{\partial f^{\prime}(t)}{\partial t}<0$, which implies that $f^{\prime}(t)$ is strictly decreasing.

A direct application of Lemma 11 gives the following Lemma 12

For all $0<\varepsilon^{\prime}<1$ sufficiently close to 1, $f^{\prime}(t)$ has exactly two zeros on $t\in(0,1)$.

By Lemma 11, we know that $f^{\prime}(t)$ is strictly increasing on $t\in(0,t_{0})$ and strictly decreasing on $(t_{0},1)$. Recall that Lemma 10 shows that for $0<\varepsilon^{\prime}<1$, $\lim_{t\to 0^{+}}f^{\prime}(t)=-\infty$ and $\lim_{t\to 1^{-}}f^{\prime}(t)<0$. Therefore it suffices to show $f^{\prime}(t_{0})>0$ for all $\varepsilon^{\prime}$ sufficiently close to $1^{-}$. We define

We have $A$ tends to $+\infty$ as $\varepsilon^{\prime}\to 1^{-}$. We then write

Note that $\lim_{\varepsilon^{\prime}\to 1^{-}}(1+\varepsilon^{\prime})^{3}A^{-\frac{1}{2}-\frac{\varepsilon^{\prime}}{4}}=0$, and

Therefore we conclude that $f^{\prime}(t_{0})>0$ as $\varepsilon^{\prime}\to 1^{-}$.

We denote the two zeros in Lemma 12 by $t_{1}=t_{1}(\varepsilon^{\prime})$ and $t_{2}=t_{2}(\varepsilon^{\prime})$ where $t_{1}<t_{2}$.

We show (a) first. Note that for any fixed $\varepsilon^{\prime}<1$, $f(0)=0$. Therefore it suffices to show that for any $\varepsilon^{\prime}$ sufficiently close to , the derivative $f^{\prime}(t)<0$. Since by Lemma 11 we have $f^{\prime}(t)<\sup_{t\in(0,1)}f^{\prime}(t)=f^{\prime}(t_{0})$ when $0<\varepsilon^{\prime}<1$ , it remains to show that $f^{\prime}(t_{0})<0$ for all $\varepsilon^{\prime}$ sufficiently close to 0.

In light of (13), $f^{\prime}(t_{0})<0$ is equivalent to

Rearranging the terms yields $A^{{\varepsilon^{\prime}}/{4}}<(1+\varepsilon^{\prime})^{3}A^{-1/2}+(1-\varepsilon^{\prime})^{3}A^{1/2}$. Since $A>1$ and $\varepsilon^{\prime}<1$, we have $A^{\varepsilon^{\prime}/4}<A^{1/2}$. Thus it now suffices to show $A^{1/2}<(1+\varepsilon^{\prime})^{3}A^{-1/2}+(1-\varepsilon^{\prime})^{3}A^{1/2}$, or equivalently $A<(1+\varepsilon^{\prime})^{3}/[1-(1-\varepsilon^{\prime})^{3}]$. We can further simplify this into

Now we show (b). By Lemma 12, we know that for all $\varepsilon^{\prime}$ sufficiently close to $1^{-}$, $f^{\prime}$ has exactly two zeros $t_{1}$ and $t_{2}$. By Lemma 11, we know that $f^{\prime}(t)>0$ for $t\in(t_{1},t_{2})$. These imply that $f(t)$ is decreasing on $t\in(0,t_{1})$, increasing on $t\in(t_{1},t_{2})$ and decreasing on $t\in(t_{2},1)$, which gives $\operatorname*{arg\,max}_{t\in}f(t)\subseteq\{0,t_{2}\}$. Furthermore, since $f(0)=0$ and $f^{\prime}(t)<0$ for $t\in(0,t_{1})$, we know $f(t)<0$ in $t\in(0,t_{1})$. Also note that $f(1)=-1<0$. Therefore, depending on $\varepsilon^{\prime}$, the sign of $f(t)$ in $t\in(0,1)$ only has two possibilities: either $f(t)<0$ for all $t\in(0,1)$ except possibly one point where $f(t)=0$, or there exist $\tau_{1}$ and $\tau_{2}$ as described in (b). In the latter case we have $0<t_{1}<\tau_{1}<t_{2}<\tau_{2}<1$.

We now show the existence of such $\tau_{1}$ and $\tau_{2}$ for all $\varepsilon^{\prime}$ sufficiently close to $1^{-}$. Since we have shown that $\operatorname*{arg\,max}_{t\in}f(t)\subseteq\{0,t_{2}\}$ and $f(0)=0$, it suffices to show $f(t_{2})>0$. Since $f^{\prime}(t_{2})=0$, we have $f(t_{2})>0\Leftrightarrow f(t_{2})-t_{2}\cdot f^{\prime}(t_{2})>0\Leftrightarrow[(1+\varepsilon^{\prime})^{3}-(1+\varepsilon^{\prime})]t_{2}^{(1+\varepsilon^{\prime})^{2}}>[(1-\varepsilon^{\prime})-(1-\varepsilon^{\prime})^{3}]t_{2}^{(1-\varepsilon^{\prime})^{2}}$, which can be simplified into

Since $\varepsilon^{\prime}<1$, it then suffices to show

The claim in (b) that $\tau_{2}(\varepsilon^{\prime})\geq\frac{1}{3}$ follows directly from the above analysis since $t_{2}<\tau_{2}$ and $\liminf_{\varepsilon^{\prime}\to 1^{-}}t_{2}\geq\frac{1}{2}$.

To show $\lim_{\varepsilon^{\prime}\to 1^{-}}\tau_{1}(\varepsilon^{\prime})=0$, we claim that $\tau_{1}\leq(1-\varepsilon^{\prime})^{0.9}$ as $\varepsilon^{\prime}\to 1^{-}$. Then it suffices to show that $f((1-\varepsilon^{\prime})^{0.9},\varepsilon^{\prime})>0$ for all $\varepsilon^{\prime}\to 1^{-}$. We have

which tends to 1 as $\varepsilon^{\prime}\to 1^{-}$. This implies (b).

We now show (c). First note that $f(0)=0$ and $f(1)=-1$.

When $\varepsilon^{\prime}=1$, $f(t)=t-2t^{4}$. In this case, we have $f(t)>0$ for $t\in(0,2^{-1/3})$ and $f(t)<0$ for $t\in(2^{-1/3},1)$.

When $1<\varepsilon^{\prime}\leq 2$, by Lemma 11, we have $f^{\prime}(t)=1+(\varepsilon^{\prime}-1)^{3}t^{(\varepsilon^{\prime}-1)^{2}-1}-(\varepsilon^{\prime}+1)^{3}t^{(\varepsilon^{\prime}+1)^{2}-1}$ being strictly decreasing on $t\in(0,1)$. Therefore the function $f(t)$ is concave. Since $\lim_{t\to 0^{+}}f^{\prime}(t)>0$, $f(0)=0$ and $f(1)=-1<0$, the result follows by concavity.

When $2<\varepsilon^{\prime}$, again since $f(0)=0$ and $f(1)=-1$, it suffices to show $f$ is strictly increasing and then strictly decreasing on $t\in(0,1)$. Note that since $\lim_{t\to 0^{+}}f^{\prime}(t)=1>0$ and $\lim_{t\to 1^{-}}f^{\prime}(t)<0$, it then suffices to show $f^{\prime}(t)$ is increasing and then decreasing on $(0,1)$. To show this, it suffices to show that if $f^{\prime\prime}(\hat{t})=\frac{\partial}{\partial t}f(\hat{t})<0$ for some $\hat{t}\in(0,1)$, then $f^{\prime\prime}(t)<0$ for all $t\in[\hat{t},1)$. Now, since

and $\hat{t}^{(\varepsilon^{\prime}+1)^{2}-(\varepsilon^{\prime}-1)^{2}}<t^{(\varepsilon^{\prime}+1)^{2}-(\varepsilon^{\prime}-1)^{2}}$ for all $t\geq\hat{t}$, we conclude that $f^{\prime\prime}(t)<0$ for all $t\in[\hat{t},1)$. So we are done.

Now we are in a position to prove Theorem 1.

Let $t_{j}=e^{-v_{j}^{2}}$ for all $j\in[d]$. By Lemma 7 and Lemma 8, we have

By part (a) of Lemma 9, when $\varepsilon<\delta_{1}\min_{j\in[d]}\mu(j)$, we have for all $j\in[d]$, it holds that $\varepsilon^{\prime}_{j}<\delta_{1}$ and thus $f(t_{j},\varepsilon^{\prime}_{j})<0$ for all $t\in(0,1)$. Combining it with (15) yields $\frac{dL_{n}}{dn}<0$.

When $\max_{j\in[d]}\mu(j)\leq\varepsilon$, we have for all $j\in[d]$, it holds that $1<\varepsilon^{\prime}_{j}$. It follows from part (c) of Lemma 9 that for all $j\in[d]$, there exists $\tau_{2}(\varepsilon^{\prime}_{j})$ such that $f(t_{j},\varepsilon^{\prime}_{j})>0\ \forall\ t_{j}\in(0,\tau_{2}(\varepsilon^{\prime}_{j}))$. Pick $\tau_{2}=\min_{j}\tau_{2}(\varepsilon^{\prime}_{j})$. Then for all $j\in[d]$, we have $f(t_{j},\varepsilon^{\prime}_{j})>0$ when $t_{j}<\tau_{2}$. Since $t_{j}=e^{-v_{j}^{2}}=\exp(-\frac{n\mu^{2}(j)}{2\sigma^{2}(j)})$, when $\exp(-\frac{n\mu^{2}(j)}{2\sigma^{2}(j)})<\tau_{2}$, or equivalently $n>2\log\left(\frac{1}{\tau_{2}}\right)\max_{j\in[d]}\frac{\sigma^{2}(j)}{\mu^{2}(j)}$, we have $\frac{dL_{n}}{dn}>0$ .

When $\delta_{2}\cdot\max_{j\in[d]}\mu(j)<\varepsilon<\min_{j\in[d]}\mu(j)$, we have for all $j\in[d]$, it holds that $\delta_{2}<\varepsilon^{\prime}_{j}<1$. Then by part (b) of Lemma 9, for all $j\in[d]$, $\exists\ \tau_{1}(\varepsilon^{\prime}_{j})$ and $\tau_{2}(\varepsilon^{\prime}_{j})$ such that

where $\tau_{1}(\varepsilon^{\prime}_{j})\to 0^{+}$ as $\varepsilon^{\prime}_{j}\to 1^{-}$ and $\tau_{2}(\varepsilon^{\prime}_{j})>\frac{1}{3}$, for all $j\in[d]$. Let $\tau_{2}=\max_{j\in[d]}\tau_{2}(\varepsilon^{\prime}_{j})>\frac{1}{3}$, $\tau_{1}=\min_{j\in[d]}\tau_{1}(\varepsilon^{\prime}_{j})$ and $\hat{\tau}_{1}=\max_{j\in[d]}\tau_{1}(\varepsilon^{\prime}_{j})$. Note that since $\lim_{\varepsilon^{\prime}_{j}\to 1^{-}}\tau_{1}(\varepsilon^{\prime}_{j})=0$, without loss of generality we can assume $\hat{\tau}_{1}<\frac{1}{3}$. It follows from (16) that for all $j\in[d]$

Denote $\gamma=\frac{\mu(j)}{\sigma(j)}$ for all $j\in[d]$ since this ratio is fixed. Then we have $t_{j}=\exp\left(-\frac{\mu^{2}(j)n}{2\sigma^{2}(j)}\right)=\exp(-\gamma^{2}n/2)$. Therefore we can choose $N_{4}=\log(\tau_{1}^{-1})\cdot\left(\frac{2}{\gamma^{2}}\right)$, $N_{3}=\log(\hat{\tau}_{1}^{-1})\cdot\left(\frac{2}{\gamma^{2}}\right)$, $N_{2}=\log(3)\cdot\left(\frac{2}{\gamma^{2}}\right)$ and $N_{1}=\log(\tau_{2}^{-1})\cdot\left(\frac{2}{\gamma^{2}}\right)$ where $N_{1}<N_{2}<N_{3}<N_{4}$ and the result follows from (15) and (17).

From the proof of Theorem 1, in this simplified case we have $\tau_{1}=\hat{\tau}_{1}$ and $\tau_{2}=\tau_{2}(\varepsilon^{\prime}_{j})$ for all $j$. It follows that the thresholds $N_{1},\ N_{2},\ N_{3},$ and $N_{4}$ in Theorem 1 satisfy $N_{1}=N_{2}$, and $N_{3}$ is no longer needed and can be replaced by $N_{4}$. Therefore only two thresholds are needed in 2. We denote the two thresholds as $N_{1}$ and $N_{2}$.

It remains to show $\lim_{\varepsilon\to\mu_{0}^{-}}N_{2}(\varepsilon)-N_{1}(\varepsilon)=+\infty$. From part (b) of Lemma 9 and (15), we know the derivative $\frac{dL_{n}}{dn}$ is positive when $t:=\exp(-\frac{n\mu_{0}^{2}}{2\sigma_{0}^{2}})\in(\tau_{1},\tau_{2})$, or equivalently $n\in\left(\log(\frac{1}{\tau_{2}})\frac{2\sigma_{0}^{2}}{\mu_{0}^{2}},\log(\frac{1}{\tau_{1}})\frac{2\sigma_{0}^{2}}{\mu_{0}^{2}}\right)$. By (b) of Lemma 9, we know $\tau_{1}\to 0^{+}$ as $\varepsilon\to\mu_{0}^{-}$ while $\tau_{2}$ is bounded away from . This shows $\lim_{\varepsilon\to\mu_{0}^{-}}\log(\frac{1}{\tau_{1}})-\log(\frac{1}{\tau_{2}})=+\infty$ and completes the proof. ∎

Appendix B Proof of Lemma 3

Note that by letting $\varepsilon<1/2$, any two intervals have no overlap. To see why $f^{*}$ is a constant function over each interval $I_{j}$, we consider three possible cases of the dataset $\{(x_{i},y_{i}),i\in[n]\}$. For the first case, suppose that those data points with $s=j$ contain only positive points. Then in order to correctly classify these points with $\varepsilon$ perturbation, we must have $f^{*}(s)\leq\mu-\varepsilon$ for all $s\in I_{j}$. In order to minimize $||f^{*}||_{1}$, we would take $\alpha_{j}=\min\{0,\ \mu-\varepsilon\}$. Similarly, if those points purely consist of negative points, then $\alpha_{j}=\max\{0,\ -\mu+\varepsilon\}$. For the second case, suppose that those data points with $s=j$ contain both positive and negative points. Suppose the number of positive points exceeds the number of negative points. Then to correctly classify the positive points, we have $f^{*}(s)\leq\mu-\varepsilon$ for all $s\in I_{j}$. To correctly classify the negative points, we have $f^{*}(s)\geq-\mu+\varepsilon$ for all $s\in I_{j}$. If $-\mu+\varepsilon\leq 0\leq\mu-\varepsilon$, then $\alpha_{j}=0$. Otherwise, if $-\mu+\varepsilon>\mu-\varepsilon$, then $f^{*}$ can never simultaneously classify both classes correctly. It will choose to correctly classify the class with more points, which is the positive class. Then $\alpha_{j}=\mu-\varepsilon$. On the other hand, if negative class has more points, then $\alpha_{j}=-\mu+\varepsilon$. If the two class have equal number of points at $s=j$, then $\alpha_{j}$ can be either $-\mu+\varepsilon$ or $\mu-\varepsilon$. For the third case, assume no point in the training set has $s=j$. Then $\alpha_{j}=0$.

We have now specified the form that $f^{*}\in S_{2}$ can take, which also indicates that $S_{2}$ is nonempty. We now show for all sufficiently small $\lambda$, $S(\lambda)=S_{2}$.

First we show $S(\lambda)\subseteq S_{2}$. Let $f\in S(\lambda)$. We want to show $f\in S$ and $||f||_{1}\leq||\hat{f}||_{1}$ for all $\hat{f}\in S$. Suppose on the contrary that $f\notin S$. Then by definition of $H$, there exists $f^{*}\in S$ s.t.

and since $S_{2}$ is nonempty we can further assume $f^{*}$ satisfies

Since $f\in S(\lambda)$, we then have $\lambda||f||_{1}\leq\lambda||f^{*}||_{1}-1/2$, which implies $||f^{*}||_{1}\geq 1/2\lambda$. From above analysis we know $f^{*}$ must take the form of Eq. 18 where $\alpha_{j}\leq|\mu-\varepsilon|$, and $I_{j}$ has length equal to $2\varepsilon$. This implies $||f^{*}||_{1}\leq 2N\varepsilon|\mu-\varepsilon|$. Therefore, if we pick $\lambda<\frac{1}{4N\varepsilon|\mu-\varepsilon|}$, then such $f^{*}$ cannot exist. Therefore, for all sufficiently small $\lambda$, we have $f\in S$.

Now we show $||f||_{1}\leq||\hat{f}||_{1}$ for all $\hat{f}\in S$. Suppose on the contrary that there exists $f^{*}\in S$ such that $||f^{*}||_{1}<||f||_{1}$. However, since we have already shown

this would contradict the fact that $f\in S(\lambda)$. Therefore we have $S(\lambda)\subseteq S_{2}$.

To see $S_{2}\subseteq S(\lambda)$ for all sufficiently small $\lambda$, we again pick $\lambda<\frac{1}{4N\varepsilon|\mu-\varepsilon|}$. Note that since $||f^{*}||_{1}\leq 2N\varepsilon|\mu-\varepsilon|$ for all $f^{*}\in S_{2}$, we have $\lambda||f^{*}||_{1}<\frac{1}{2}$. Now suppose on the contrary that there exists $f\notin S_{2}$ such that

which is a contradiction. Therefore $S_{2}\subseteq S(\lambda)$. Altogether we have $S(\lambda)=S_{2}$.

Appendix C Proof of Theorem 4

The proof follows from the Lemma 3 and its proof. By Lemma 3, we have $S(\lambda)=S_{2}$ and we can consider the equivalent definition that $f^{\textnormal{rob}}_{n}\in S_{2}$. From the proof of Lemma 3, we know $f^{\textnormal{rob}}_{n}$ must take the form of (18). Since $|\alpha_{j}|\leq|\mu-\varepsilon|$, when $\varepsilon<2\mu$, we have $|\alpha_{j}|<\mu$ and thus $|f^{\textnormal{rob}}_{n}(s)|<\mu$ for all $s\in\bR$. For such $f^{\textnormal{rob}}_{n}$, we have $H\left(-y\left(t-f^{\textnormal{rob}}_{n}(s)\right)\right)=0$ for all $(x,y)=(s,t,y)$ in the support of $\cD_{2N}$. This implies $L_{n}=0$ for all $n$.

Assume $2\mu<\varepsilon<1/2$. Then $|\alpha_{j}|$ can take the value of either or $|\mu-\varepsilon|>|\mu|$. When $\alpha_{j}=0$, $f^{\textnormal{rob}}_{n}$ can classify both the positive and negative points at location $s=j$ correctly. When $|\alpha_{j}|>\mu$, then $f^{\textnormal{rob}}_{n}$ can only classify one of the two classes correctly. Note that $\alpha_{j}=0$ if and only if there is no point with $s=j$ in the training set. Let the random variable $Z\in{0}\cup[N]$ denote the cardinality of the set $\{j\in[N]:\ s_{i}\neq j\ \textnormal{for all}\ i\in[n]\}$, which is a function of the training set $\{(x_{i},y_{i})\}_{i=1}^{n}$. Then the generalization error can be written as

Note that $\bE_{\{(x_{i},y_{i})\}_{i=1}^{n}}Z$ decreases as $n$ increases. Therefore $L_{n}<L_{n+1}$ for all $n$.

Appendix D Further Details on Gaussian Mixture with 0-1 Loss

If the training dataset is $\{(x_{i},y_{i})\}_{i=1}^{n}$, we define the neuralized dataset $\{(x^{\prime}_{i},y_{i})\}_{i=1}^{n}$ that satisfies $x^{\prime}_{i}=x_{i}-y_{i}\varepsilon$ for all $i\in[n]$. In other words, for a positive sample $(x_{i},y_{i}=1)$, we obtain its neutralized sample by shifting $x_{i}$ to the negative direction by $\varepsilon$, i.e., $x^{\prime}_{i}=x_{i}-\varepsilon$; for a negative sample $(x_{i},y_{i}=-1)$, its neutralized sample is obtained by shifting $x_{i}$ to the positive direction by $\varepsilon$, i.e., $x^{\prime}_{i}=x_{i}+\varepsilon$. We see that the dataset remains unchanged after neutralization if $\varepsilon=0$. With this definition, the robust classifier can be expressed as the following.

Given the training dataset $\{(x_{i},y_{i})\}_{i=1}^{n}$ and the neuralized dataset $\{(x^{\prime}_{i},y_{i})\}_{i=1}^{n}$, the robust classifier is given by

Now one can see the tiebreaking issue in light of 13. To see this, let $s$ be the permutation of $[n]$ such that $x^{\prime}_{s(1)}\leq x^{\prime}_{s(2)}\leq\dots\leq x^{\prime}_{s(n)}$. The $n$ points divide the real line into $n+1$ intervals: $(-\infty,x^{\prime}_{s(1)}]$, $(x^{\prime}_{s(i)},x^{\prime}_{s(i+1)}]$ for $1\leq i\leq n-1$, and $(x^{\prime}_{s(n)},\infty)$. Let $w^{*}$ be a minimizer of (19). If $w^{*}$ lies in any of the above $n+1$ intervals, then any other point in the same interval is also a minimizer, since at these two points the objective function has the same value. Therefore, a tiebreaking procedure is required here.

For the agnostic tiebreak, if $w^{*}\in(x^{\prime}_{s(i)},x^{\prime}_{s(i+1)}]$, it chooses $w^{\textnormal{rob}}_{n}$ uniformly at random from the interval. If $w^{*}>x^{\prime}_{s(n)}$, it chooses $w^{\textnormal{rob}}_{n}$ arbitrarily close to $x^{\prime}_{s(n)}$ from above. If $w^{*}\leq x^{\prime}_{s(1)}$, it chooses $w^{\textnormal{rob}}_{n}=x^{\prime}_{s(1)}$.

By (1), it suffices to show that under the 0-1 loss

D.2 Test Loss and Optimal Tiebreak

To find the optimal tiebreaking in hingsight, we need to minimize the test loss over the model parameter $w$, which is given by 14.

The test loss of classifier $w$ is given by

where $\Phi$ is the CDF of the standard normal distribution. Furthermore, the minimizer of (21) is $w=0$.

14 indicates that the optimal tiebreak in hindsight chooses the point closest to (i.e., the point with the minimum absolute value) from (the closure of) the interval where $w^{*}$ lies. This is because $w=0$ minimizes the test loss in (21), and one can see that (21) increases as $|w|$ increases. Indeed, the derivative of (21) is given by $\frac{1}{2\sigma\sqrt{2\pi}}\left(\exp({-\frac{(w-\mu)^{2}}{2\sigma}})-\exp({-\frac{(w+\mu)^{2}}{2\sigma}})\right)$, which is negative for $w<0$ and positive for $w>0$.

Since the derivative is $\frac{1}{2\sigma\sqrt{2\pi}}\left(\exp({-\frac{(w-\mu)^{2}}{2\sigma}})-\exp({-\frac{(w+\mu)^{2}}{2\sigma}})\right)$, we see that $w^{*}=0$ minimizes the above quantity. ∎

Appendix E Additional Details about the SVM Experiment

The standard test loss (the $y$-axis in Fig. 4(c) and Fig. 4(d)) of the robust classifier is given by

where the penalty term is not included. The robust classifier $w^{\textnormal{rob}}_{n}$ is solved for by optimizing (22) which is convex in $w$ using gradient descent.