Certified Robust Neural Networks: Generalization and Corruption
  Resistance
Recent work have demonstrated that robustness (to "corruption") can be at
odds with generalization. Adversarial training, for instance, aims to reduce
the problematic susceptibility of modern neural networks to small data
perturbations. Surprisingly, overfitting is a major concern in adversarial
training despite being mostly absent in standard training. We provide here
theoretical evidence for this peculiar "robust overfitting" phenomenon.
Subsequently, we advance a novel distributionally robust loss function bridging
robustness and generalization. We demonstrate both theoretically as well as
empirically the loss to enjoy a certified level of robustness against two
common types of corruption--data evasion and poisoning attacks--while ensuring
guaranteed generalization. We show through careful numerical experiments that
our resulting holistic robust (HR) training procedure yields SOTA performance.
Finally, we indicate that HR training can be interpreted as a direct extension
of adversarial training and comes with a negligible additional computational
burden. A ready-to-use python library implementing our algorithm is available
at https://github.com/RyanLucas3/HR_Neural_Networks.
Amine Bennouna, Ryan Lucas, Bart Van Parys
# Certified Robust Neural Networks: Generalization and Corruption Resistance

###### Abstract

Recent work have demonstrated that robustness (to "corruption") can be at odds with generalization. Adversarial training, for instance, aims to reduce the problematic susceptibility of modern neural networks to small data perturbations. Surprisingly, overfitting is a major concern in adversarial training despite being mostly absent in standard training. We provide here theoretical evidence for this peculiar "robust overfitting" phenomenon. Subsequently, we advance a novel distributionally robust loss function bridging robustness and generalization. We demonstrate both theoretically as well as empirically the loss to enjoy a certified level of robustness against two common types of corruption--data evasion and poisoning attacks--while ensuring guaranteed generalization. We show through careful numerical experiments that our resulting holistic robust (HR) training procedure yields state of the art performance. Finally, we indicate that HR training can be interpreted as a direct extension of adversarial training and comes with a negligible additional computational burden. A ready-to-use python library implementing our algorithm is available at [https://github.com/RyanLucas3/HR_Neural_Networks](https://github.com/RyanLucas3/HR_Neural_Networks).

Machine Learning, Robustness Robustness, Generalization, Corruption, Robustness

## 1 Introduction

Recent work has shown that many modern neural networks are vulnerable to data corruption putting into question the reliability and performance of such models at deployment time. Robustness has in recent years, next to out-of-sample generalization, become a central research topic in the machine learning community. The key question is how to develop machine learning models which are reliable and perform well despite being trained on corrupted training data and evaluated on perturbed test data.

Data corruption can be due to multiple causes ranging from benign imprecise data collection to malicious adversaries. Two types of corruption, each associated with a distinct cause, stand out in prior work which we briefly discuss.

Evasion Corruption.This type of corruption results in small, often imperceptible, perturbations of all the test or train instances and may fool a naively trained model to suffer poor performance at deployment time. Goodfellow et al. (2014) study evasion attacks at test time and show that neural network models can suffer a severe decrease in accuracy when test instances are subjected to an imperceptible amount of noise. This pioneering work spurred on a rich literature on attacks (Tramer et al., 2020) as well as defense strategies such as the popular adversarial training (Madry et al., 2018; Bai et al., 2021). Evasion corruption need not necessarily be caused by an adversary or even take place at test time. Indeed, noise is present in training data as well often as a result of measurement imperfections. Examples include street noise and background chatter in speech recognition (Li et al., 2014; Mitra et al., 2017) or impulse noise and blur in image classification (Hendrycks and Dietterich, 2019; Hendrycks et al., 2021).

Poisoning Corruption.In this type of corruption, a certain fraction of the training data points is drastically changed. This alteration of the training dataset may then mislead the learning in selecting a "bad" model. Clearly, if a large majority of data points is affected, the data set is wholly corrupted and there is no point in hoping for a good performance. Hence, poisoning corruption is assumed to affect only a small fraction of the data points. One example is label flipping in classification problems, where a small portion of the training data points are wrongly labeled or an adversary can select a small number of labels to flip before training time (Biggio et al., 2012). Poisoning corruption has also been shown to considerably degrade performance at deployment time. For instance, Nelson et al. (2008) shows that altering only \(1\%\) of email spam labels can completely fool commercial spam filters. Several related attacks and defense mechanisms have been identified in follow-up work (Goldblum et al., 2022).
Generalization.Beyond protecting against both discussed types of attacks, an equally important challenge is out-of-sample performance. A model generalizes if it provides protection against **statistical error** which we take here to mean the difference between the finite number of data points provided during training time as opposed to the full data distribution. Indeed, all models must avoid _overfitting_ to a particular training set and generalize to the test data. Several classical approaches have been developed to address statistical error such as \(\ell_{1},\ell_{2}\) regularization, early stopping, and data augmentation. Such models seek not only a good expected performance under the randomness of the samples but also low variance. To generalization well, models need to avoid being overly sensitive to a particular training data and rather seek "satisfactory" performance on all "likely" data sets of the task at hand.

Generalization and robustness to each type of corruption have been extensively studied in isolation. However, the interaction between corruption protection and generalization has been largely ignored: existing "robust" approaches typically dismiss statistical error. Recent work has shown that robustness (to corruption) can be at odds with generalization, highlighting the need to consider corruption and statistical error simultaneously. Schmidt et al. (2018) and Rice et al. (2020) exhibit theoretical and empirical evidence that adversarial training (AT)--which provides robustness against evasive corruption--suffers from notably worse generalization than natural training. Rice et al. (2020) show in particular that the surprising generalization properties of neural networks, such as improved out-of-sample performance with larger models, vanishes under AT. Schmidt et al. (2018) indicate that "understanding the interactions between robustness, classifier model, and data distribution from the perspective of generalization is an important direction for future work". Hence, while AT aims to improve generalization performance by protecting against evasive corruption, it seems inadvertently to limit generalization by exacerbating the adverse effect of statistical error. This interesting phenomenon, dubbed _robust overfitting_, and its remedies is the topic of several recent papers (Wu et al., 2020; Li & Spratling, 2022; Yu et al., 2022). Similar observations were also noted in the case of poisoning, where poisoning corruption exacerbates overfitting (Zhang & Sabuncu, 2018; Hendrycks et al., 2019).

Besides generalization issues, existing robust approaches typically protect against one single type of corruption exclusively, either evasion or poisoning. However, in practical settings, we typically are unaware of what type of corruption, if any, plagues the data. Unsurprisingly, a model designed for a specific type of corruption risks considerably poor performance when deployed in a setting with a different type of corruption. Hence, to develop practical robust models, it is important to protect against both types of corruption, and their potential combination.

### Contributions

In this paper, we study generalization when learning with data affected by evasion and/or poisoning corruption on top of statistical error simultaneously.

We first provide theoretical evidence of the significance of the interaction between corruption and statistical error. We show that the generalization gap of AT can be decomposed into an empirical risk minimization (ERM) generalization gap and a positive term which we interpret as an _adversary shift_ (Section 3). This result provides theoretical evidence to the robust overfitting phenomenon observed empirically by Rice et al. (2020) and indicates that AT indeed suffers from worse generalization than ERM. This theoretical observation illustrates that protecting against corruption only while ignoring statistical error can inadvertently yield worse generalization performance.

Second, we tackle the problem of robustness against both types of corruption and statistical error simultaneously. We do so by designing and optimizing a provable "tight" upper bound on the _test loss_ when learning with data subject to corruption. This is in contrast to most prior work which is either empirically motivated or, like AT, merely optimizes empirical proxies to such upper bounds--dismissing statistical error. To design this upper bound, we construct a set around the corrupted training distribution which contains the testing distribution with high probability. A valid upper bound on the test loss can then be taken as the worst-case expectation of the loss over all distributions in this ambiguity set. We show that training a neural network model based on such associated distributionally robust optimization (DRO) objective function can be interpreted as a natural generalization to standard AT which protects against the two discussed corruption sources simultaneously and particularly enjoys strong generalization. Our holistic robust (HR) objective function has three parameters \(\alpha\in[0,1]\), \(r\geq 0\) and \(\mathcal{N}\), and is guaranteed to be an upper bound on the test performance with high probability \(1-e^{-rn+O(1)}\) when less then a fraction \(\alpha\) of all \(n\) samples are tampered by poisoning, and the evasion corruption is bounded within the set \(\mathcal{N}\). The latter guarantee certifies robustness for _any_ desired level of evasion attacks (\(\mathcal{N}\)) and poisoning attacks (\(\alpha\)): our out-of-sample deployment performance is at least as good as the estimated in-sample performance with high probability.

Finally, we propose a practical HR loss training algorithm for neural networks with negligible additional computational burden compared to classical AT. We conduct careful numerical experiments which illustrate the efficacy of HR training on both MNIST and CIFAR-10 datasets in all possible corruption settings: clean, affected by poisoning and/or evasive corruption. By using validation on the protection pa
rameters \(\alpha,r,\mathcal{N}\), HR training adapts to and protects against whatever corruption plagues the data including combination of evasion and poisoning, while ensuring strong generalization. In all settings, HR training achieves state of the art (SOTA) performance and outperforms classical evasion defense mechanisms (AT of Madry et al. (2018), TRADES of Zhang et al. (2019)), poisoning defense mechanisms (DPA of Levine and Feizi (2020); Wang et al. (2022)), and the combination of poisoning and evasion defenses. Furthermore, we replicate the experiments in Rice et al. (2020) and provide numerical evidence that HR training largely circumvents the robust overfitting phenomenon experienced by AT. Finally, we show empirically that the _training loss_ of HR training is an upper bound on its _adversarial test loss_ with high probability, providing a generalization guarantee. Notably, this observation does not hold for any of the prior robust approaches.

We release an open-source Python library ([https://github.com/RyanLucas3/HR_Neural_Networks](https://github.com/RyanLucas3/HR_Neural_Networks)) that can be directly installed through pip. With our library, HR training can be used to provide robustness by changing essentially only one line of the training code. We also provide an extensive Colab tutorial on using HR in the github repository.

### Related work

**Robust Overfitting.** Understanding and eliminating the robust overfitting phenomenon has been the topic of previous work. Rice et al. (2020) suggests that conventional remedies for overfitting cannot improve upon early stopping. To compensate for poor generalization of AT (Schmidt et al., 2018), data augmentation techniques such as semi-supervised learning (Alayrac et al., 2019; Carmon et al., 2019) and data interpolation (Lee et al., 2020; Chen et al., 2021) have been considered. Alternative approaches directly modify the AT loss function by reweighing data points (Wang et al., 2019; Zhang et al., 2021), mitigating memorization effects (Dong et al., 2021) or favoring large loss data (Yu et al., 2022). Kulynych et al. (2022) recently considers differential privacy as a way to ensure strong generalization. Previous works mostly attempt to eliminate robust overfitting through empirical insight. In our work, however, we present theoretical evidence with regards to the working of the robust overfitting mechanism (Theorem 3.2) and propose a disciplined approach at its elimination. Our proposed HR training is indeed a theoretically disciplined approach which comes with a theoretical certificate against overfitting (Theorem 4.1). On a practical level, HR can be understood as a smart reweighing of the standard adversarial examples considered in Madry et al. (2018) and in doing so equips standard AT against with protection against both poisoning and evasion attacks.

**Distributionally Robust Optimization.** Wasserstein distributionally robust optimization (WDRO) has recently received attention in the context of AT (Staib and Jegelka, 2017; Sinha et al., 2017; Wong et al., 2019; Bui et al., 2022). WDRO safeguards against attackers with a bound on the average perturbation applied to all data points as opposed to standard AT which protects against attacks in which the perturbation on each individual data point is bounded. WDRO however still suffers from fundamentally the same robust overfitting phenomenon as standard AT as it does not take into account statistical error. However, the Kullback-Leibler (KL) divergence ambiguity sets are known in the DRO literature to be superior at providing safeguards against statistical error (Lam, 2019; Van Parys et al., 2021) than their Wasserstein counterparts in the absence of data corruption. The Levy-Prokhorov (LP) metric has been shown in the statistical literature (Hampel, 1971) to precisely captures certain types of data corruption. Recently, Bennouna and Van Parys (2022) proposed a novel ambiguity set combining both the KL and LP metrics in an attempt to safeguard against corruption and statistical error simultaneously. Contrary to the WDRO approach of Sinha et al. (2017), the holistic robust DRO formulation based on this novel ambiguity set is proven here to guarantee an upper bound on the adversarial test loss for _any_ desired corruption level and _any_ loss function. Moreover, the HR formulation is not harder to train than classical AT. This paper considers the ambiguity set of Bennouna and Van Parys (2022) in the context of evasion (at _test time_) and poisoning, and proves new statistical properties. In particular, we prove the HR ambiguity set to provide _uniform_ finite sample generalization bounds, independent of the dimentionality of the model class--a crucial novel property in the context of deep learning.

## 2 Preliminaries: Learning under corruption

We formalize here the setting of learning under evasion and poisoning corruption. A typical underlying assumption in prior work is that the empirical distribution of the data is close to the out-of-sample distribution, neglecting statistical error and risking poor generalization. Here, we carefully consider both types of corruption and their interaction with statistical error.

Consider a learning problem with covariates \(x\in\mathcal{X}\) and outputs \(y\in\mathcal{Y}\) (e.g., labels in classification problems), following a joint distribution \(\mathcal{D}\) with compact support \(\mathcal{Z}\subseteq\mathcal{X}\times\mathcal{Y}\) which represents the distribution of the clean data. We do not observe samples directly from this clean distribution \(\mathcal{D}\) but rather up to a fraction \(\alpha\) of these \(n\) independent samples are wholly corrupted (poisoning corruption). We hence observe the \(n\) samples \(\{z_{i}\coloneqq(x_{i},y_{i})\}_{i=1}^{n}\in\mathcal{Z}^{n}\) post corruption and denote with \(\mathcal{D}_{n}\) their empirical distribution. During test time, the test data is again sampled from \(\mathcal{D}\) but
is subjected to noise out of a set \(\mathcal{N}\) (evasion corruption). Typical work in AT considers for example the noise bounded in an \(l_{p}\) ball (Madry et al., 2018). We denote the distribution of the perturbed test instances with \(\mathcal{D}_{\text{test}}\). We observe \(\mathcal{D}_{n}\) but our goal is to learn a model that minimizes the test loss

\[\mathcal{L}_{\text{test}}(\theta):=\mathbb{E}_{\mathcal{D}_{\text{test}}}[ \ell(\theta,Z)],\]

where \(\theta\in\Theta\) are the model parameters, \(\ell\) is a bounded loss function (e.g., cross-entropy on neural networks); see Figure 1. Here, as in the remainder of the paper, \(\mathbb{E}_{\mathcal{D}^{\prime}}\) denotes expectation over a random variable \(Z\) with distribution \(\mathcal{D}^{\prime}\).

## 3 Adversarial training and generalization

We now highlight the importance of robustness against statistical error when learning under corruption. Consider the classical setting of adversarial evasion attacks in the absence of poisoning (i.e., \(\alpha=0\)) and let here \(\ell^{\mathcal{N}}(\theta,z):=\max_{\delta\in\mathcal{N},\,z+\delta\in \mathcal{Z}}\ell(\theta,z+\delta)\) when the adversary can perturb the data \(z\) within the set \(\mathcal{N}\ni 0\). The AT models of Madry et al. (2018) minimize the empirical adversarial loss \(\mathcal{L}_{\text{AT}}(\theta):=\mathbb{E}_{\mathcal{D}_{n}}[\ell^{\mathcal{ N}}(\theta,z)]\) and hope that its minimizer \(\theta_{\mathcal{D}_{n}}^{\text{AT}}\) over the parameter set \(\Theta\) is safeguarded against evasion attacks. We have indeed that the testing loss \(\mathcal{L}_{\text{test}}(\theta)\) is upper bounded by \(\mathbb{E}_{\mathcal{D}}\big{[}\ell^{\mathcal{N}}(\theta,z)\big{]}\) and hence minimizing its empirical counterpart \(\mathcal{L}_{\text{AT}}(\theta)\) makes intuitive sense. However, due to statistical error there might be a considerable gap between the adversarial test loss \(\mathbb{E}_{\mathcal{D}}\big{[}\ell^{\mathcal{N}}(\theta,z)\big{]}\) and the empirical adversarial loss \(\mathcal{L}_{\text{AT}}(\theta)\) putting into question the intuitive appeal of this approach. AT typically does overfit to the worst-case perturbations of the _data points_--rather than the out-of-sample distribution--and thus generalizes poorly. This is akin to classical overfitting in ERM caused by the gap between the minimized loss \(\mathcal{L}_{\text{ERM}}(\theta):=\mathbb{E}_{\mathcal{D}_{n}}[\ell(\theta,Z)]\) and the out-of-sample cost \(\mathbb{E}_{\mathcal{D}}[\ell(\theta,Z)]\). In the case of AT, it has been empirically observed that overfitting is in fact exacerbated when compared to ERM (Rice et al., 2020). We now provide theoretical insight into why AT suffers from overfitting more than ERM.

First, we present a distributional perspective on AT which will be useful in what follows. Consider the ambiguity set

\[\mathcal{U}_{\mathcal{N}}(\mathcal{D}_{n}):=\{\mathcal{D}^{\prime}_{\text{ test}}:\text{LP}_{\mathcal{N}}(\mathcal{D}_{n},\mathcal{D}^{\prime}_{\text{ test}})\leq 0\} \tag{1}\]

associated with the optimal transport metric

\[\text{LP}_{\mathcal{N}}(\mathcal{D}_{n},\mathcal{D}^{\prime}_{ \text{test}}):= \tag{2}\] \[\inf\left\{\int\mathbf{1}(z^{\prime}-z\not\in\mathcal{N})\,\text {d}\gamma(z,z^{\prime})\ :\ \gamma\in\Gamma(\mathcal{D}_{n},\mathcal{D}^{\prime}_{\text{test}})\right\}\]

where \(\Gamma(\mathcal{D}_{n},\mathcal{D}^{\prime}_{\text{test}})\) denotes the set of all couplings on \(\mathcal{Z}\times\mathcal{Z}\) between \(\mathcal{D}_{n}\) and \(\mathcal{D}^{\prime}_{\text{test}}\)(Villani, 2009). It is straightforward to observe that

\[\mathcal{L}_{\text{AT}}(\theta)=\max\{\mathbb{E}_{\mathcal{D}^{\prime}_{\text {test}}}[\ell(\theta,Z)]\ :\mathcal{D}^{\prime}_{\text{test}}\in\mathcal{U}_{\mathcal{N}}( \mathcal{D}_{n})\}. \tag{3}\]

Clearly, hence, naively considering DRO formulations does not by itself eliminate robust overfitting. We will show in Section 4 that a careful generalization of the previous DRO formulation does protect against robust overfitting.

ERM overfitting gap.Let us first provide intuition on classical overfitting in ERM. As \(\mathcal{D}_{n}\) is here the empirical distribution of a random dataset it is itself a random variable and we denote with \(\mathcal{S}_{n}\) its distribution. Denote the associated ERM solution to some arbitrary distribution \(\mathcal{D}^{\prime}\) as \(\theta_{\mathcal{D}^{\prime}}\in\arg\min_{\theta\in\Theta}\mathbb{E}_{\mathcal{ D}^{\prime}}[\ell(\theta,Z)]\) which we assume to be unique for simplicity. ERM overfitting is bound to occur as the expected testing loss is larger than the expected training loss, i.e.,

\[\mathbb{E}_{\mathcal{D}_{n}\sim\mathcal{S}_{n}}[\mathbb{E}_{ \mathcal{D}}[\ell(\theta_{\mathcal{D}_{n}}\!\!,Z)]] \!\!= \mathbb{E}_{\mathcal{D}^{1}_{n},\mathcal{D}^{2}_{n}\sim\mathcal{S} _{n}}[\mathbb{E}_{\mathcal{D}^{1}_{n}}[\ell(\theta_{\mathcal{D}^{1}_{n}}\!\!,Z)]] \tag{4}\] \[\!\!\geq \mathbb{E}_{\mathcal{D}^{1}_{n},\mathcal{D}^{2}_{n}\sim\mathcal{S} _{n}}[\mathbb{E}_{\mathcal{D}^{1}_{n}}[\ell(\theta_{\mathcal{D}^{1}_{n}}\!\!,Z)]]\] (5) \[\!\!= \mathbb{E}_{\mathcal{D}_{n}\sim\mathcal{S}_{n}}[\mathbb{E}_{ \mathcal{D}_{n}}[\ell(\theta_{\mathcal{D}_{n}}\!\!,Z)]]\,. \tag{6}\]

Here, Equality (4) is due to Fubini's theorem. Inequality (5) follows from the fact that \(\theta_{\mathcal{D}^{1}_{n}}\) is a minimizer of \(\mathbb{E}_{\mathcal{D}^{1}_{n}}[\ell(\theta,Z)]\). Equality (6) follows from the fact that \(\mathcal{D}^{2}_{n}\) and \(\mathcal{D}^{1}_{n}\) are independent and share the same distribution \(\mathcal{S}_{n}\). The right hand side of (6) is precisely the expected training loss. We define the ERM _overfitting gap_, between training and testing loss, as

\[\mathcal{G}_{\text{ERM}}(\mathcal{S}_{n},\ell)\] \[\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
**AT overfitting gap.** Let us now examine the robust overfitting phenomenon in AT. For an arbitrary distribution \(\mathcal{D}^{\prime}\) and an arbitrary model \(\theta\) we define its associated worst-case adversary as the distribution \(\mathcal{D}^{\prime}(\theta)\in\arg\max\{\mathbb{E}_{\mathcal{D}^{\prime\prime }_{\text{out}}}[\ell(\theta,Z)]:\mathcal{D}^{\prime}_{\text{test}}\in\mathcal{U }_{\mathcal{N}}(\mathcal{D}^{\prime})\}\). We denote in particular with \(\mathcal{D}^{\prime\prime}:=\mathcal{D}^{\prime\prime\prime}(\theta^{\text{ AT}}_{\mathcal{D}^{\prime}})\) the worst-case adversary of the AT solution \(\theta^{\text{AT}}_{\mathcal{D}^{\prime}}\in\arg\min_{\theta\in\Theta}\max\{ \mathbb{E}_{\mathcal{D}^{\prime\prime}_{\text{out}}}[\ell(\theta,Z)]:\mathcal{ D}^{\prime}_{\text{test}}\in\mathcal{U}_{\mathcal{N}}(\mathcal{D}^{\prime})\}\) which minimizes \(\mathcal{L}_{\text{AT}}\) (see (3)). We will assume in this section that the AT best model \(\theta^{\text{AT}}_{\mathcal{D}^{\prime}}\) and its associated worst-case adversary \(\mathcal{D}^{\prime\prime\prime}\) form a saddle-point.

**Assumption 3.1** (Saddle-Point).: For any \(\mathcal{D}^{\prime}\) we have \(\mathbb{E}_{\mathcal{D}^{\prime}_{\text{out}}}[\ell(\theta^{\text{AT}}_{ \mathcal{D}^{\prime}},Z)]\leq\mathbb{E}_{\mathcal{D}^{\prime\prime\prime}}[ \ell(\theta,Z)]\) for all \(\theta\in\Theta\) and \(\mathcal{D}^{\prime}_{\text{test}}\in\mathcal{U}_{\mathcal{N}}(\mathcal{D}^{ \prime})\).

The previous saddle point condition implies in particular that the AT best model also minimizes a nominal ERM cost \(\mathbb{E}_{\mathcal{D}^{\text{AT}}}[\ell(\theta,Z)]\) with respect to a worst-case adversary \(\mathcal{D}^{\text{AT}}_{n}\sim\mathcal{S}^{\text{AT}}_{n}\), i.e., \(\theta^{\text{AT}}_{\mathcal{D}_{n}}=\theta_{\mathcal{D}^{\text{AT}}_{n}} \in\arg\min_{\theta\in\Theta}\mathbb{E}_{\mathcal{D}^{\text{AT}}_{n}}[\ell( \theta,Z)]\). Assumption 3.1 holds for any convex loss functions such as logistic regression (Sion, 1958; Bose et al., 2020). However, it is not necessarily verified for neural networks due to their inherent nonconvexity. Recent work by Gidel et al. (2021) suggests however that it may also hold for neural networks approximately. We define the _AT overfitting gap_ as the expected difference between the adversarial testing loss and the AT loss, i.e.,

\[\mathcal{G}_{\text{AT}}(\mathcal{S}_{n},\ell)\!:=\!\mathbb{E}_{ \mathcal{D}_{n}\sim\mathcal{S}_{n}}[\mathbb{E}_{\mathcal{D}}[\ell^{\mathcal{ N}}(\theta^{\text{AT}}_{\mathcal{D}_{n}},Z)]\!-\!\mathbb{E}_{\mathcal{D}_{n}}[ \ell^{\mathcal{N}}(\theta^{\text{AT}}_{\mathcal{D}_{n}},Z)]]\] \[\qquad=\mathbb{E}_{\mathcal{D}_{n}\sim\mathcal{S}_{n}}[\mathbb{E} _{\mathcal{D}(\theta^{\text{AT}}_{\mathcal{D}_{n}})}[\ell(\theta^{\text{AT}} _{\mathcal{D}_{n}},Z)]-\mathbb{E}_{\mathcal{D}^{\text{AT}}_{n}}[\ell(\theta^{ \text{AT}}_{\mathcal{D}_{n}},Z)]].\]

Our next result shows that under a saddle-point assumption, the AT overfitting gap can be decomposed into an ERM overfitting gap and a _nonnegative_ term \(\mathcal{G}_{\text{SHIFT}}(\mathcal{S}_{n},\ell):=\mathbb{E}_{\mathcal{D}^{ \prime}_{n},\mathcal{D}^{\prime}_{n}\sim\mathcal{S}_{n}}[\mathbb{E}_{\mathcal{ D}^{\prime}_{n}(\theta^{\text{AT}}_{\mathcal{D}_{n}})}[\ell(\theta^{\text{AT}}_{ \mathcal{D}_{n}},Z)]-\mathbb{E}_{\mathcal{D}^{\prime\prime}_{n}(\theta^{ \text{AT}}_{\mathcal{D}_{n}})}[\ell(\theta^{\text{AT}}_{\mathcal{D}_{n}},Z)]].\)

**Theorem 3.2**.: _Let Assumption 3.1 hold. Then,_

\[\mathcal{G}_{\text{AT}}(\mathcal{S}_{n},\ell)=\mathcal{G}_{\text{ERM}}( \mathcal{S}^{\text{AT}}_{n},\ell)+\underbrace{\mathcal{G}_{\text{SHIFT}}( \mathcal{S}_{n},\ell)}_{\geq 0}.\]

The proof of Theorem 3.2 can be found in Appendix A and indicates in particular that AT overfitting gap is always at least as large as the overfitting gap suffered by an ERM procedure on data generated by the worst-case adversary \(\mathcal{D}^{\text{AT}}_{n}\). Hence, while ERM overfitting is due to difference between train and test data sets, AT suffers worse overfitting as its gap is due to a difference between (adversarial) train and test datasets and an additional adversary shift term. This result gives theoretical evidence for the robust overfitting phenomenon observed empirically in a flurry of recent papers. The additional adversary shift term can be interpreted as the sensitivity of the AT solution to a change of adversary. Hence, Theorem 3.2 indicates that robust overfitting is due to the trained model adapting too much to the specific artificially added perturbations during AT.

Let us detail this adversary shift gap \(\mathcal{G}_{\text{SHIFT}}\) interpretation. Recall that \(\theta^{\text{AT}}_{\mathcal{D}_{n}}\) is an AT model trained with distribution \(\mathcal{D}_{n}\). Intuitively, \(\mathcal{D}^{2}_{n}\) can be seen as a testing distribution, and \(\mathcal{D}^{2}_{n}(\theta^{\text{AT}}_{\mathcal{D}^{\prime}_{n}})\) (resp. \(\mathcal{D}^{2}_{n}(\theta^{\text{AT}}_{\mathcal{D}^{\prime}_{n}})\)) is a testing distribution with adversarial examples where the adversary is chosen against model \(\theta^{\text{AT}}_{\mathcal{D}^{\prime}_{n}}\) (resp. \(\theta^{\text{AT}}_{\mathcal{D}^{\prime}_{n}}\)). Hence, each of the two terms of the gap measures the robust testing error under a _distinct_ adversary. The difference measures therefore the gap of testing error when the adversary changes. This implies that the adversary shift quantifies the _sensitivity of the AT model to a change of adversary_ resulting from a change of training distribution: if we train with data \(\mathcal{D}^{1}_{n}\), AT trains with perturbation from adversary against \(\theta^{\text{AT}}_{\mathcal{D}^{1}_{n}}\), while if we train with data \(\mathcal{D}^{2}_{n}\), AT trains with perturbation from a distinct (shifted) adversary, namely against \(\theta^{\text{AT}}_{\mathcal{D}^{2}_{n}}\). This gap is large when the trained model adapts too much (overfits) to the specific added perturbation to the training samples with AT.

## 4 A holistic robust loss

From the previous section, it is clear that practical robustness requires us to take into account statistical error in addition to poisoning and evasion corruption. The key idea, following the motivation behind AT, is to construct an upper bound on the test loss when learning with corruption. As opposed to classical AT, such upper bound should account for poisoning as well, and also, crucially, should bound the _out-of-sample_ adversarial test loss \(\mathcal{L}_{\text{test}}\) rather than its empirical proxy.

Let us first build intuition on our upper bound. As Section 3 demonstrate, an empirical proxy of the test loss typically underestimates the test loss of the trained model, as the expected overfitting gap is always positive \(\mathcal{G}_{\text{ERM}},\mathcal{G}_{\text{AT}}\geq 0\). This is caused by the fluctuations of the empirical distribution of samples around the out-of-sample distributions generating the samples. Hence, instead of considering the ambiguity set (1) of the AT loss (3) capturing only the corruption at hand, we augment this ambiguity set to capture the fluctuations of the empirical distribution due to sampling. These statistical fluctuations are captured by the Kullback-Leibler divergence (Van Erven and Harremos, 2014), denoted here as KL, as we will demonstrate shortly. On the other hand, the optimal transport metric LP (defined in (2)) will capture both evasion and poisoning. This augmentation will increase the estimated loss "just enough" to be a tight upper bound on the test loss.

Define here an ambiguity set \(\mathcal{U}_{\mathcal{N},\alpha,r}(\mathcal{D}_{n}):=\{\mathcal{D}^{\prime}_{\text{ test}}:\exists\mathcal{D}^{\prime}\text{ s.t. }\text{LP}_{\mathcal{N}}(\mathcal{D}_{n},\mathcal{D}^{\prime})\leq\alpha,\text{ KL}(\mathcal{D}^{\prime},\mathcal{D}^{\prime}_{\text{test}})\leq r\}\), and the associated holistic robust (HR) loss as

\[\mathcal{L}^{\mathcal{N},\alpha,r}_{\text{HR}}(\theta)\!:=\!\max\{\mathbb{E}_{ \mathcal{D}^{\prime}_{\text{test}}}[\ell(\theta,Z)]:\mathcal{D}^{\prime}_{\text{ test}}\!\in\!\mathcal{U}_{\mathcal{N},\alpha,r}(\mathcal{D}_{n})\}, \tag{7}\]

where the desired protection against evasion corruption is controlled by \(\mathcal{N}\), protection against poisoning corruption is
controlled by \(\alpha\), and statistical error is accounted for by \(r\), respectively. Intuitively, the LP ball \(\{\mathcal{D}^{\prime}\ :\ LP_{\mathcal{N}}(\mathcal{D}_{n},\mathcal{D}^{\prime}) \leq\alpha\}\) contains all the possible "training" empirical distributions \(\mathcal{D}^{\prime}\) directly sampled from the adversarial testing distribution \(\mathcal{D}_{test}\)--that is, by removing the poisoned data points and then perturbing each data point by evasion. As \(\mathcal{D}^{\prime}\) is an empirical distribution of samples from \(\mathcal{D}_{test}\), then large deviation theory (Dembo & Zeitouni, 2009) ensures that the set \(\{\mathcal{D}^{\prime}_{test}\ :\ KL(\mathcal{D}^{\prime},\mathcal{D}^{\prime}_{ test})\leq r\}\) contains (intuitively) \(\mathcal{D}_{test}\) with high probability \(1-e^{-rn+O(1)}\). This intuitive explanation is merely a simplified illustration. In the proof of subsequent Theorem 4.1 (which we defer to Appendix C) we prove indeed that the considered ambiguity set around the random observed empirical distribution contains the adversarial testing distribution (with probability \(1-e^{-rn+O(1)}\)), given that less than a fraction \(\alpha\) of all training data points are corrupted by poisoning and the evasive attack on the test data is limited to a compact set in the interior of the set \(\mathcal{N}\).

**Theorem 4.1** (Robustness Certificate).: _Suppose that less than a fraction \(\alpha\in(0,1]\) of the independent identically distributed (IID) training data is poisoned and the evasion attack on the test set is limited to a compact set in \(\text{int}(\mathcal{N})\). Then, \(\text{Pr}(\mathcal{L}^{\mathcal{N},\alpha,r}_{\text{HR}}(\theta)\geq\mathcal{ L}_{\text{test}}(\theta)\ \forall\theta\in\Theta)\geq 1-e^{-rn+O(1)}\)._

Denote here the holistic robust solution as \(\theta^{\text{HR}}_{\mathcal{D}_{n}}\in\arg\min_{\theta\in\Theta}\max_{ \mathcal{D}^{\prime}_{\text{HR}}\in\mathcal{U}^{\prime}\alpha,r(\mathcal{D}_{ n})}\mathbb{E}_{\mathcal{D}^{\prime}_{\text{res}}}[\ell(\theta,Z)]\). The previous theorem certifies that asymptotically the testing error is not larger than the HR loss with high probability, i.e.,

\[\text{Pr}\Big{(}\mathcal{L}^{\mathcal{N},\alpha,r}_{\text{HR}}(\theta^{\text{ HR}}_{\mathcal{D}_{n}})\geq\mathcal{L}_{\text{test}}(\theta^{\text{HR}}_{ \mathcal{D}_{n}})\Big{)}\geq 1-e^{-rn+O(1)}.\]

In Appendix C we prove a finite sample extension of this generalization certificate (Theorem C.4) and indicate that the results is statistically tight (Theorem C.5). We point out that, unlike certificates founds in several prior works (for instance in Sinha et al. (2017)), our bound does not depend on the dimension of the parameter space \(\Theta\) but rather only on the "size" of the event set \(\mathcal{Z}\) (eg images and labels). This is critical as in the context of neural networks typically the number of weights is taken much larger than the number of data points \(n\). The HR loss is a natural generalization of the AT loss. When no robustness against statistical error (\(r=0\)) and poisoning corruption (\(\alpha=0\)) is desired, we have indeed \(\mathcal{L}^{\mathcal{N},0,0}_{\text{HR}}(\theta)=\mathcal{L}_{\text{AT}}(\theta)\); See Appendix B for further details.

## 5 HR training algorithm

We now introduce an algorithm--HR training--to optimize efficiently the HR loss \(\mathcal{L}^{\mathcal{N},\alpha,r}_{\text{HR}}\). At first glance, minimizing the HR loss seems challenging as it requires the solution of a saddle point problem over the model parameters \(\theta\in\Theta\) and potentially continuous distribution \(\mathcal{D}^{\prime}_{\text{test}}\in\mathcal{U}_{\mathcal{N},\alpha,r}( \mathcal{D}_{n})\). We exploit, however, a finite reformulation of the HR loss by Bennouna & Van Parys (2022). For any given training data (sub)set \(\{z_{i}=(x_{i},y_{i})\}_{i\in I}\) with \(I\subseteq[n]\), we can compute its associated HR loss _exactly_ as

\[\mathcal{L}^{\mathcal{N},\alpha,r}_{\text{HR}}(\theta)=\left\{\begin{array}{l} \max\sum_{i=1}^{n}d^{\prime}_{i}\ell^{\mathcal{N}}(\theta,z_{i})+d^{\prime}_ {0}\ell^{\mathcal{Z}}(\theta)\\ \text{s.t. }d^{\prime}\in\Re^{n+1}_{+},\,\hat{d}^{\prime}\in\Re^{n+1}_{+},\,s\in \Re^{n}_{+},\\ \sum_{i=0}^{n}d^{\prime}_{i}=\sum_{i=0}^{n}\hat{d}^{\prime}_{i}=1,\\ \hat{d}^{\prime}_{i}\!+\!s_{i}\!=\!\frac{1}{n}\ \forall i\!\in\![1,\ldots,n],\\ \sum_{i=0}^{n}\hat{d}^{\prime}_{i}\log(\frac{d_{i}}{d_{i}})\leq r,\ \sum_{i=1}^{n}s_{i}\leq\alpha \end{array}\right. \tag{8}\]

where \(\ell^{\mathcal{Z}}(\theta):=\max_{z\in\mathcal{Z}}\ell(\theta,z)\) and \(\ell^{\mathcal{N}}(\theta,z):=\max_{\delta\in\mathcal{N},z+\delta\in\mathcal{Z }}\ell(\theta,z+\delta)\). In particular, the supremum of the HR loss (7) is attained in distributions \(\mathcal{D}^{\prime}_{test}\) and \(\mathcal{D}^{\prime}\) of finite support (\(d^{\prime}\) and \(\hat{d}^{\prime}\) respectively in (8)), specifically the adversarial examples and a point maximizing the loss. The HR loss is therefore in essence simply an adversarial reweighing of loss terms comprising the AT loss and an additional loss term \(\ell^{\mathcal{Z}}(\theta)\). Determining the HR loss exactly requires evaluating the adversarial loss \(\ell^{\mathcal{N}}(\theta,z)\) and subsequently solving the exponential cone problem (8) with \(O(n)\) variables and constraints, which can be done efficiently by off-the-shelf optimization solvers.

Practically, we train the HR loss by mimicking standard adversarial training. At each minibatch iteration, we indeed first compute an approximate adversarial example \(z^{\prime}_{i}\approx z_{i}+\arg\max_{\delta\in\mathcal{N},z_{i}+\delta\in \mathcal{Z}}\ell(\theta,z_{i}+\delta)\) for each data point in the minibatch \(I\subset[n]\) using the projected gradient descent (PGD) algorithm of Madry et al. (2018). With the help of the approximations \(\ell^{\mathcal{N}}(\theta,z_{i})\approx\ell(\theta,z^{\prime}_{i})\) as well as \(\ell^{\mathcal{Z}}(\theta)\approx\max_{i\in I}\ell(\theta,z^{\prime}_{i})\) we determine an approximate maximizer \(d^{\prime\star}\) in problem (8). The model parameters are then updated by stepping in the direction of the negative gradient of the HR loss. We remark that this gradient can be computed efficiently using Danskin's theorem as a weighted sum of the gradients on the adversarial examples, i.e., \(\nabla_{\theta}\mathcal{L}^{\mathcal{N},\alpha,r}_{\text{HR}}(\theta;I)=\sum_{ i\in I}d^{\prime\star}_{i}\nabla_{\theta}\ell(\theta,z^{\prime}_{i})+d^{\prime\star}_{0} \nabla_{\theta}\ell(\theta,z^{\prime}_{\arg\max_{i\in I}\ell(\theta,z^{\prime}_{i})})\). The algorithm is summarized in Algorithm 1 where we remark that HR training is different from standard adversarial training only in that it requires computing the maximizer \(d^{\prime\star}\) in (8). Practically, HR training with PGD takes less than 6% more time than standard adversarial training using PGD in typical benchmarks.

## 6 Experiments

In this section, we investigate the efficacy of HR training through extensive experiments on the MNIST and CIFAR-10 datasets1. We consider the crossentropy loss
\(\ell(\theta,(x,y))=-\sum_{k=1}^{K}y^{(k)}\log f_{\theta}^{(k)}(x)\), \(K=10\), where \(f_{\theta}(x)\in\Re^{K}\) represents the network with weights \(\theta\) and softmax output probabilities for covariate \(x\) and one-hot encoded class label \(y\in\Re^{K}\). We present here only the CIFAR-10 results and leave the MNIST experiments, which bear the same insights, to Appendix D. We conduct three sets of experiments. The first set evaluates each type of robustness separately and shows that each parameter provides robustness against a distinct source of overfitting: \(\mathcal{N}\) against data evasion, \(\alpha\) against data poisoning and finally \(r\) against statistical error. The second set of experiments shows that HR training does not suffer robust overfitting and also benchmarks HR training against SOTA evasion robustness methods. The last set of experiments evaluates robustness against statistical error and both corruptions simultaneously and shows that HR training significantly outperforms benchmarks. In particular, each of these sets of experiments shows the theoretical robustness certificate provided in Theorem 4.1 holds empirically.

In these experiments, we train HR with PGD (see Algorithm 1) and adopt the classical setting of covariates evasion attacks by choosing \(\mathcal{N}=B(0,\epsilon)\times\{0\}\) where depending on the context \(B(0,\epsilon)\) is here either a Euclidean or infinity norm ball with radius \(\epsilon\).

``` Specification: Learning rate \(\lambda\), number of epochs \(T\), mini-batches \(B\), minibatch replays \(M\), HR parameters (\(\mathcal{N},\alpha,r\)). Input: Data \(\{z_{i}=(x_{i},y_{i})\}_{i\in[n]}\). Initialized \(\theta\). //iterate \(M\) times per batch, for a total of \(T\) epochs for\(t\in[T/M]\), minibatch \(I\in B\), \(\boldsymbol{\cdot}\in[M]\)do //adversarial attack, e.g., using PGD  Compute \(z_{i}^{\prime}\boldsymbol{\approx}z_{i}+\arg\max_{\delta\in\mathcal{N}}\ell( \theta,z_{i}+\delta)\,\forall i\in I\), //reweigh data points  Compute optimal weights \(d^{\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot}\boldsymbol{\cdot} \boldsymbol{\cdot}\boldsymbol{\cdot}
### Combatting robust overfitting

We replicate here the experiment of Rice et al. (2020) exhibiting robust overfitting for AT training. As in Rice et al. (2020) we use preactivation ResNet18 on CIFAR-10 with PGD attacks of 10 steps, and with SGD learning rate decay at epochs 100 and 150. Further experimental setup is discussed in Appendix D.1. We train AT with PGD of Madry et al. (2018), TRADES of Zhang et al. (2019), and HR with \(r\geq 0\), \(\epsilon>0\) and \(\alpha=0\). For all algorithms, we use the same PGD attack on training with \(\epsilon=8/255\) and 10 attack steps. Figure 3 shows the test loss and error up to 200 training epochs when using pre-activation ResNet18 under \(\ell_{\infty}\) attacks. Table 1 reports the test error at the 200 epoch mark, replicating the results reported in Table 2 in Rice et al. (2020). AT clearly exhibits robust overfitting as the test loss drastically increases with more training epochs. The test error also increases but perhaps not as drastically. This indicates that although the number of errors made eventually settles, worryingly, the errors are made with increasing confidence as quantified by the crossentropy loss. Similar to Rice et al. (2020), we find that TRADES (Zhang et al., 2019) without early stopping also experiences robust overfitting although to a lesser extent than regular PGD training. HR training with modest parameter values \(r\) effectively mitigates this phenomenon and results in a monotonically decreasing test loss as a function of training epochs eliminating the need for early stopping. It is worth noting that PGD best checkpoint performs better than HR final checkpoint. However, it might be practically hard to recover the performance of such best checkpoint with early stopping. In fact, PGD's training curve around the best checkpoint is very steep, and hence, early stopping might result in unstable performance on practical datasets, with potentially lower datasize.
tails. The hyperparameters of each algorithm are selected based on a 70/30 train/validation split of the training data as detailed in Appendix D.2.

**Results.** Table 2 presents the natural and adversarial classification errors of each algorithm under various corruption settings. HR training significantly surpasses all other benchmarks in _every setting_. Traditional robust algorithms, such as PGD, TRADES, and DPA, unsurprisingly falter when faced with a corruption variant different from what they were originally designed to handle, performing even worse than ERM. In stark contrast, HR training demonstrates its adaptability by automatically adjusting to the specific corruption in the data, consistently maintaining high performance even when faced with combined attack strategies. Furthermore, the superior generalization capability of HR enables it to outperform each algorithm even in the unique attack settings for which they were specifically designed. Finally, HR also significantly outperforms the combination of defense techniques (PGD+DPA). Indeed, combining these defense techniques does not necessarily yield cumulative benefits due to the potential negative interactions between them. In contrast, HR is designed to provide effective simultaneous defenses while ensuring strong generalization.

Figure 4 shows the training loss and the adversarial test loss of each algorithm in the settings of combined evasion and poisoning. Here, DPA and DPA+PGD are not represented a they have no clear notion of loss. HR training significantly outperforms all other benchmarks in two distinct ways. First, HR training enjoys the smallest adversarial test loss. Furthermore, the variance of its adversarial test loss is the smallest among the benchmarked procedures. Second, HR training effectively provides a robustness certificate as alluded to in Theorem 4.1. The training loss is indeed with high probability an upper bound on the testing loss--an observation which fails to hold for the other procedures.

Training time.We investigate the train time of HR to evaluate the computational cost of its gain in robustness and generalization. Table 3 reports the training time (in minutes) per epoch of ERM, PGD, and HR on various datasets and architectures. While HR takes four times longer than PGD for small datasets and architectures (ConvNet on MNSIT), its additional computational cost compared to PGD is negligible for large datasets and architectures: \(<\)**+6%** for CIFAR-10 with ResNet and TinyImageNet with ResNet/EfficientNet. This is due to the fact that computationally, HR training only differ with PGD in solving an additional conic optimization problem (8) as described in Algorithm 1. This optimization problem depends only on the batch size (linearly) and is _independent_ on the data dimensionality and the network's size/architecture. As a result, while the PGD step and the network gradient step scale with the network's size and data dimensionality, HR's additional step does not scale with these factors, keeping its additional computational burden constant compared to PGD.

## 7 Discussion & Conclusion

We make neural network training resilient against adversarial attacks based on a disciplined robust optimization approach. We remark that our approach can be generalized to other corruption models by substituting the LP metric with a metric suitable for the considered corruption model (e.g., Wasserstein for perturbations bounded on average). The tractability properties of the resulting method may however depend on the considered metric. We believe hence that the considered approach constitutes an interesting new inroad to bridging generalization and adversarial robustness of modern deep neural networks.

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline  & \begin{tabular}{c} Natural \\ (No Attack) \\ \end{tabular} & \begin{tabular}{c} Evasion \\ \end{tabular} & \begin{tabular}{c} Stat.Error + \\ Poisoning \\ \end{tabular} & \begin{tabular}{c} Stat.Error + \\ Evasion \\ \end{tabular} & 
\begin{tabular}{c} Stat.Error + \\ Poisoning \\ \end{tabular} \\ \hline
**Combined Defenses** & HR & **9.0\%** & **18.5\%** & **25.3\% (27.1\%)** & **33.0\% (34.4\%)** & **36.6\% (38.9\%)** \\  & PGD + DPA & 18.6\% & 27.8\% & 37.0\% (38.2\%) & 47.1\% (48.0\%) & 45.2\% (46.1\%) \\ \hline
**AT Defenses** & PGD & 10.6\% & 20.2\% & 30.1\% (32.4\%) & 33.8\% (35.3\%) & 40.6\% (41.7\%) \\  & TRADES & 13.9\% & 32.8\% & 32.6\% (34.3\%) & 43.3\% (46.9\%) & 49.7\% (52.0\%) \\ \hline
**Poisoning Defenses** & DPA & 15.6\% & 39.2\% & 35.4\% (37.9\%) & 50.3\% (51.4\%) & 49.6\% (51.4\%) \\  & TV & 9.8\% & 40.8\% & **25.3\% (27.1\%)** & 43.9\% (50.5\%) & 50.6\% (54.4\%) \\ \hline
**No Defense** & ERM & 9.4\% & 35.4\% & 28.8\% (30.5\%) & 43.9\% (50.5\%) & 52.2\% (55.5\%) \\  & KL & **9.0\%** & 38.1\% & 28.4\% (31.5\%) & 43.9\% (50.5\%) & 49.9\% (54.7\%) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Mean and (worst-case) error rate over 10 trials with model parameters chosen based on a validation set.

\begin{table}
\begin{tabular}{l l c c c} \hline \hline Architecture & Dataset & ERM & PGD & HR \\ \hline ConvNet & MNIST & 0.04 & 0.28 & 1.30 \\ ResNet-18 & CIFAR-10 & 0.24 & 2.60 & 2.75 \\ ResNet-18 & Tiny ImageNet & 3.39 & 6.06 & 6.36 \\ EfficientNet & Tiny ImageNet & 7.65 & 39.59 & 40.87 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Runtime of ERM, PGD, and HR in minutes per epoch (one full pass of the training dataset).