Theoretically Principled Trade-off between Robustness and Accuracy

Hongyang Zhang$^{*}$
CMU & TTIC
[email protected]

Yaodong Yu$^{\dagger}$
University of Virginia
[email protected]

Jiantao Jiao
UC Berkeley
[email protected]

Eric P. Xing
CMU & Petuum Inc.
[email protected]

Laurent El Ghaoui
UC Berkeley
[email protected]

Michael I. Jordan
UC Berkeley
[email protected]

$^{*}$ Part of this work was done while H. Z. was visiting Simons Institute for the Theory of Computing.
$^{\dagger}$ Part of this work was done while Y. Y. was an intern at Petuum Inc.

Abstract

We identify a trade-off between robustness and accuracy that serves as a guiding principle in the design of defenses against adversarial examples. Although this problem has been widely studied empirically, much remains unknown concerning the theory underlying this trade-off. In this work, we decompose the prediction error for adversarial examples (robust error) as the sum of the natural (classification) error and boundary error, and provide a differentiable upper bound using the theory of classification-calibrated loss, which is shown to be the tightest possible upper bound uniform over all probability distributions and measurable predictors. Inspired by our theoretical analysis, we also design a new defense method, TRADES, to trade adversarial robustness off against accuracy. Our proposed algorithm performs well experimentally in real-world datasets. The methodology is the foundation of our entry to the NeurIPS 2018 Adversarial Vision Challenge in which we won the 1st place out of ~2,000 submissions, surpassing the runner-up approach by 11.41% in terms of mean $\ell_2$ perturbation distance.

Executive Summary: The research addresses the vulnerability of deep neural networks to small adversarial perturbations that cause misclassification, a problem that undermines reliability in security-critical applications such as autonomous driving and speech recognition. Existing empirical defenses often improve robustness at the expense of accuracy on natural inputs, yet lack a clear theoretical account of this trade-off or guarantees on how tightly surrogate losses approximate the true robust error.

The work set out to decompose the robust classification error, derive the tightest possible differentiable upper bounds on its components that hold uniformly over distributions and predictors, and translate the resulting characterization into a practical training algorithm.

The authors first established that robust error equals natural error plus boundary error, where the latter measures the probability mass near the decision boundary. They then applied the theory of classification-calibrated surrogate losses to bound both terms, proving that the resulting upper bound on the gap between robust and optimal natural error is tight up to an arbitrarily small constant. This analysis directly motivated TRADES, a regularized objective that minimizes a calibrated loss on natural examples while penalizing disagreement between predictions on natural and adversarially perturbed examples; the method extends straightforwardly to multi-class problems via cross-entropy and is implemented with projected gradient descent for the inner maximization. Experiments evaluated the approach on MNIST and CIFAR-10 under white-box and black-box attacks, with additional validation on the NeurIPS 2018 Adversarial Vision Challenge using Tiny ImageNet.

The analysis shows that models are vulnerable precisely when substantial probability mass lies near the decision boundary, and that increasing the regularization strength systematically trades natural accuracy for higher robust accuracy. On CIFAR-10, TRADES reached 56.61 percent robust accuracy under 20-step PGD attacks, exceeding prior methods by roughly 9–10 percentage points, while the same methodology secured first place in the competition by an 11.41 percent margin in mean ℓ₂ perturbation distance. The bounds confirm that the regularization term provides a principled surrogate for boundary error and that the overall formulation is computationally comparable to earlier adversarial training procedures yet yields stronger guarantees.

These results indicate that robustness need not be achieved solely through expensive robust optimization; instead, explicit control of the accuracy-robustness trade-off via a calibrated regularizer produces models that remain accurate on clean data while resisting stronger attacks. The approach is immediately usable for training new defenses and can be combined with complementary techniques such as feature denoising or architecture modifications.

Further gains are likely from incorporating unlabeled data to refine the boundary-error term, accelerating the inner maximization, and extending the framework beyond norm-bounded perturbations. The primary limitations are that the tightest theoretical statements are stated for binary classification (though the algorithm generalizes), that all reported experiments use ℓ∞ or ℓ₂ balls of fixed radius, and that performance on very large-scale or non-vision domains remains to be verified; nevertheless, the empirical margins and the matching upper and lower bounds support high confidence in the core claims for the settings examined.

1. Introduction

Section Summary: Adversarial defenses seek to train classifiers that remain accurate on both ordinary inputs and specially crafted perturbations designed to fool them, a challenge that spans machine learning, vision, and language tasks. Existing approaches struggle with a fundamental trade-off between natural accuracy and robustness, as well as the computational difficulty of optimizing the ideal robust loss, often relying on surrogate approximations that lack tight guarantees. This paper introduces a new method, TRADES, that bounds robust error by natural error plus a boundary term, yielding a scalable regularized objective with provable properties and strong empirical results.

In response to the vulnerability of deep neural networks to small perturbations around input data [1], adversarial defenses have been an imperative object of study in machine learning [2], computer vision [3, 4, 5], natural language processing [6], and many other domains. In machine learning, study of adversarial defenses has led to significant advances in understanding and defending against adversarial threat [7]. In computer vision and natural language processing, adversarial defenses serve as indispensable building blocks for a range of security-critical systems and applications, such as autonomous cars and speech recognition authorization. The problem of adversarial defenses can be stated as that of learning a classifier with high test accuracy on both natural and adversarial examples. The adversarial example for a given labeled data $(\bm{x},y)$ is a data point $\bm{x}'$ that causes a classifier $c$ to output a different label on $\bm{x}'$ than $y$, but is "imperceptibly similar" to $\bm{x}$. Given the difficulty of providing an operational definition of "imperceptible similarity, " adversarial examples typically come in the form of restricted attacks such as $\epsilon$-bounded perturbations [1], or unrestricted attacks such as adversarial rotations, translations, and deformations [8, 9, 10, 11, 12, 13]. The focus of this work is the former setting, though our framework can be generalized to the latter.

Despite a large literature devoted to improving the robustness of deep-learning models, many fundamental questions remain unresolved. One of the most important questions is how to trade off adversarial robustness against natural accuracy. Statistically, robustness can be be at odds with accuracy [14]. This has led to an empirical line of work on adversarial defense that incorporates various kinds of assumptions [15, 16]. On the theoretical front, methods such as relaxation based defenses [17, 18] provide provable guarantees for adversarial robustness. They, however, ignore the performance of classifier on the non-adversarial examples, and thus leave open the theoretical treatment of the putative robustness/accuracy trade-off.

The problem of adversarial defense becomes more challenging when computational issues are considered. For example, the straightforward empirical risk minimization (ERM) formulation of robust classification involves minimizing the robust 0-1 loss $\max_{\bm{x}': | \bm{x}'-\bm{x}|\le\epsilon} \mathbf{1}{c(\bm{x}')\not=y},$ a loss which is NP-hard to optimize even if $\epsilon = 0$ in general. Hence, it is natural to expect that some prior work on adversarial defense replaced the 0-1 loss $\mathbf{1}(\cdot)$ with a surrogate loss [19, 16, 20]. However, there is little theoretical guarantee on the tightness of this approximation.

{width=70%}

1.1 Our methodology and results

We begin with an example that illustrates the trade-off between accuracy and adversarial robustness in Section 2.4. This phenomenon was first theoretically demonstrated by [14]. We construct another toy example where the Bayes optimal classifier achieves natural error $0%$ and robust error $100%$, while the trivial all-one classifier achieves both natural error and robust error $50%$ (Table 1). While a large literature on the analysis of robust error in terms of generalization [21, 22, 23] and computational complexity [24, 25], in this work we focus on how to address the trade-off between the natural error and the robust error.

We show that the robust error can in general be bounded tightly using two terms: one corresponds to the natural error measured by a surrogate loss function, and the other corresponds to how likely the input features are close to the $\epsilon$-extension of the decision boundary, termed as the boundary error. We then minimize the differentiable upper bound. Our theoretical analysis naturally leads to a new formulation of adversarial defense which has several appealing properties; in particular, it inherits the benefits of scalability to large datasets exhibited by Tiny ImageNet, and the algorithm achieves state-of-the-art performance on a range of benchmarks while providing theoretical guarantees. For example, while the defenses overviewed in [26] achieve robust accuracy no higher than $47%$ under white-box attacks, our method achieves robust accuracy as high as $57%$ in the same setting. The methodology is the foundation of our entry to the NeurIPS 2018 Adversarial Vision Challenge where we won first place out of 2, 000 submissions, surpassing the runner-up approach by $11.41%$ in terms of mean $\ell_2$ perturbation distance.

1.2 Summary of contributions

Our work tackles the problem of trading accuracy off against robustness and advances the state-of-the-art in multiple ways.

• Theoretically, we characterize the trade-off between accuracy and robustness for classification problems via decomposing the robust error as the sum of the natural error and the boundary error. We provide differentiable upper bounds on both terms using the theory of classification-calibrated loss, which are shown to be the tightest upper bounds uniform over all probability distributions and measurable predictors.
• Algorithmically, inspired by our theoretical analysis, we propose a new formulation of adversarial defense, TRADES, as optimizing a regularized surrogate loss. The loss consists of two terms: the term of empirical risk minimization encourages the algorithm to maximize the natural accuracy, while the regularization term encourages the algorithm to push the decision boundary away from the data, so as to improve adversarial robustness (see Figure 1).
• Experimentally, we show that our proposed algorithm outperforms state-of-the-art methods under both black-box and white-box threat models. In particular, the methodology won the final round of the NeurIPS 2018 Adversarial Vision Challenge.

2. Preliminaries

Section Summary: This section introduces the basic setup and notation for binary classification, including score functions, decision boundaries, and norms for measuring perturbations. It defines the robust classification error, which captures mistakes under small adversarial changes to inputs, and decomposes it into the standard natural error plus a new boundary error term that accounts for points near the decision boundary. The authors also illustrate the inherent trade-off between natural and robust performance via a simple example and outline their aim of deriving tight surrogate losses to bound these errors.

We illustrate our methodology using the framework of binary classification, but it can be generalized to other settings as well.

2.1 Notations

We will use bold capital letters such as $\bm{X}$ and $\bm{Y}$ to represent random vector, bold lower-case letters such as $\bm{x}$ and $\bm{y}$ to represent realization of random vector, capital letters such as $X$ and $Y$ to represent random variable, and lower-case letters such as $x$ and $y$ to represent realization of random variable. Specifically, we denote by $\bm{x}\in \mathcal{X}$ the sample instance, and by $y\in{-1,+1}$ the label, where $\mathcal{X}\subseteq \mathbb{R}^d$ indicates the instance space. $\textup{\textsf{sign}}(x)$ represents the sign of scalar $x$ with $\textup{\textsf{sign}}(0)=+1$. Denote by $f: \mathcal{X}\rightarrow \mathbb{R}$ the score function which maps an instance to a confidence value associated with being positive. It can be parametrized, e.g., by deep neural networks. The associated binary classifier is $\textup{\textsf{sign}}(f(\cdot))$. We will frequently use $\mathbf{1}{\text{event}}$, the 0-1 loss, to represent an indicator function that is $1$ if an event happens and $0$ otherwise. For norms, we denote by $| \bm{x}|$ a generic norm. Examples of norms include $| \bm{x}|_\infty$, the infinity norm of vector $\bm{x}$, and $| \bm{x}|2$, the $\ell_2$ norm of vector $\bm{x}$. We use $\mathbb{B}(\bm{x},\epsilon)$ to represent a neighborhood of $\bm{x}$: ${\bm{x}'\in \mathcal{X}:| \bm{x}'-\bm{x}|\le\epsilon}$. For a given score function $f$, we denote by $\mathrm{DB}(f)$ the decision boundary of $f$; that is, the set ${\bm{x}\in \mathcal{X}:f(\bm{x})=0}$. The set $\mathbb{B}(\mathrm{DB}(f),\epsilon)$ denotes the neighborhood of the decision boundary of $f$: ${\bm{x}\in \mathcal{X}:\exists \bm{x}'\in \mathbb{B}(\bm{x},\epsilon)\text{ s.t. } f(\bm{x})f(\bm{x}')\le 0}$. For a given function $\psi(\bm{u})$, we denote by $\psi^*(\bm{v}):=\sup{\bm{u}}{\bm{u}^T \bm{v}-\psi(\bm{u})}$ the conjugate function of $\psi$, by $\psi^{**}$ the bi-conjugate, and by $\psi^{-1}$ the inverse function. We will frequently use $\phi(\cdot)$ to indicate the surrogate of 0-1 loss.

2.2 Robust (classification) error

In the setting of adversarial learning, we are given a set of instances $\bm{x}1,..., \bm{x}n\in \mathcal{X}$ and labels $y_1,...,y_n\in{-1,+1}$. We assume that the data are sampled from an unknown distribution $(\bm{X},Y)\sim \mathcal{D}$. To characterize the robustness of a score function $f: \mathcal{X}\rightarrow \mathbb{R}$, [21, 22, 24] defined robust (classification) error under the threat model of bounded $\epsilon$ perturbation: $\mathcal{R}\mathrm{rob}(f):= \mathbb{E}{(\bm{X},Y)\sim \mathcal{D}}\mathbf{1}{\exists \bm{X}'\in\mathbb{B}(\bm{X},\epsilon) s.t. f(\bm{X}')Y\le 0}.$ This is in sharp contrast to the standard measure of classifier performance—the natural (classification) error $\mathcal{R}\mathrm{nat}(f):= \mathbb{E}{(\bm{X},Y)\sim \mathcal{D}}\mathbf{1}{f(\bm{X})Y\le 0}.$ We note that the two errors satisfy $\mathcal{R}\mathrm{rob}(f)\ge \mathcal{R}\mathrm{nat}(f)$ for all $f$; the robust error is equal to the natural error when $\epsilon=0$.

2.3 Boundary error

We introduce the boundary error defined as $\mathcal{R}{bdy}(f) := \mathbb{E}{(\bm{X},Y)\sim \mathcal{D}}\mathbf{1}{\bm{X} \in \mathbb{B}(DB(f),\epsilon), f(\bm{X})Y> 0}.$ We have the following decomposition of $\mathcal{R}_\mathrm{rob}(f)$:

$ \mathcal{R}\mathrm{rob}(f) = \mathcal{R}\mathrm{nat}(f) +\mathcal{R}_{\text{bdy}}(f). $

2.4 Trade-off between natural and robust errors

Our study is motivated by the trade-off between natural and robust errors. [14] theoretically showed that training models to be robust may lead to a reduction of standard accuracy by constructing a toy example. To illustrate the phenomenon, we provide another toy example here.

Example. Consider the case $(X,Y)\sim \mathcal{D}$, where the marginal distribution over the instance space is a uniform distribution over $[0,1]$, and for $k=0,1,...,\lceil\frac{1}{2\epsilon}-1\rceil$,

$ \begin{split} \eta(x)&:=\Pr(Y=1|X=x)\ &= \begin{cases} 0, & x\in[2k\epsilon,(2k+1)\epsilon),\ 1, & x\in((2k+1)\epsilon,(2k+2)\epsilon]. \end{cases} \end{split} $

See Figure 2 for the visualization of $\eta(x)$. We consider two classifiers: a) the Bayes optimal classifier $\textup{\textsf{sign}}(2\eta(x)-1)$; b) the all-one classifier which always outputs "positive." Table 1 displays the trade-off between natural and robust errors: the minimal natural error is achieved by the Bayes optimal classifier with large robust error, while the optimal robust error is achieved by the all-one classifier with large natural error.

::: {caption="Table 1: Comparisons of natural and robust errors of Bayes optimal classifier and all-one classifier in . The Bayes optimal classifier has the optimal natural error while the all-one classifier has the optimal robust error."}

:::

Our goal. In practice, one may prefer to trade-off between robustness and accuracy by introducing weights in Equation (1) to bias more towards the natural error or the boundary error. Noting that both the natural error and the boundary error involve 0-1 loss functions, our goal is to devise tight differentiable upper bounds on both of these terms. Towards this goal, we utilize the theory of classification-calibrated loss.

2.5 Classification-calibrated surrogate loss

Definition. Minimization of the 0-1 loss in the natural and robust errors is computationally intractable and the demands of computational efficiency have led researchers to focus on minimization of a tractable surrogate loss, $\mathcal{R}\phi(f):= \mathbb{E}{(\bm{X},Y)\sim \mathcal{D}}\phi(f(\bm{X})Y)$. We then need to find quantitative relationships between the excess errors associated with $\phi$ and those associated with 0–1 loss. We make a weak assumption on $\phi$: it is classification-calibrated [27]. Formally, for $\eta\in[0,1]$, define the conditional $\phi$-risk by

$ H(\eta):=\inf_{\alpha\in \mathbb{R}} C_\eta(\alpha):=\inf_{\alpha\in \mathbb{R}} \left(\eta\phi(\alpha)+(1-\eta)\phi(-\alpha)\right), $

and define $H^-(\eta):=\inf_{\alpha(2\eta-1)\le 0} C_\eta(\alpha)$. The classification-calibrated condition requires that imposing the constraint that $\alpha$ has an inconsistent sign with the Bayes decision rule $\textup{\textsf{sign}}(2\eta-1)$ leads to a strictly larger $\phi$-risk:

########## {caption="Assumption 1: Classification-Calibrated Loss"}

We assume that the surrogate loss $\phi$ is classification-calibrated, meaning that for any $\eta\not=1/2$, $H^-(\eta)>H(\eta)$.

We argue that Assumption 1 is indispensable for classification problems, since without it the Bayes optimal classifier cannot be the minimizer of the $\phi$-risk. Examples of classification-calibrated loss include hinge loss, sigmoid loss, exponential loss, logistic loss, and many others (see Table 2).

Properties. Classification-calibrated loss has many structural properties that one can exploit. We begin by introducing a functional transform of classification-calibrated loss $\phi$ which was proposed by [27]. Define the function $\psi:[0,1]\rightarrow[0,\infty)$ by $\psi=\widetilde\psi^{**}$, where $\widetilde\psi(\theta):=H^-\left(\frac{1+\theta}{2}\right)-H\left(\frac{1+\theta}{2}\right)$. Indeed, the function $\psi(\theta)$ is the largest convex lower bound on $H^-\left(\frac{1+\theta}{2}\right)-H\left(\frac{1+\theta}{2}\right)$. The value $H^-\left(\frac{1+\theta}{2}\right)-H\left(\frac{1+\theta}{2}\right)$ characterizes how close the surrogate loss $\phi$ is to the class of non-classification-calibrated losses.

Below we state useful properties of the $\psi$-transform. We will frequently use the function $\psi$ to bound $\mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*$.

########## {caption="Lemma: [27]"}

Under Assumption 1, the function $\psi$ has the following properties: $\psi$ is non-decreasing, continuous, convex on $[0,1]$ and $\psi(0) = 0$.

\begin{tabular}{c|cc}
\hline
Loss & $\phi(\alpha)$ & $\psi(\theta)$
\\
\hline
Hinge & $\max\{1-\alpha, 0\}$ & $\theta$ \\
Sigmoid & $1-\tanh(\alpha)$ & $\theta$ \\
Exponential & $\exp(-\alpha)$ & $1-\sqrt{1-\theta^2}$ \\
Logistic & $\log_2(1+\exp(-\alpha))$ & $ \psi_{\mathsf{log}}(\theta)$ \\
\hline
\end{tabular}

3. Relating 0-1 loss to Surrogate Loss

Section Summary: The section develops theoretical bounds connecting the excess robust 0-1 risk of a classifier to its excess surrogate risk in binary classification. An upper bound shows that this excess robust risk is at most the surrogate excess risk (via a calibration function) plus the probability mass near the decision boundary, which can itself be controlled by the surrogate loss evaluated on adversarially perturbed points. A nearly matching lower bound establishes that the relationship is tight for standard surrogate losses, thereby explaining why models remain vulnerable to small perturbations whenever data points cluster near the boundary.

In this section, we present our main theoretical contributions for binary classification and compare our results with prior literature. Binary classification problems have received significant attention in recent years as many competitions evaluate the performance of robust models on binary classification problems [8]. We defer the discussion of multi-class problems to Section 4.

3.1 Upper bound

Our analysis leads to a guarantee on the performance of surrogate loss minimization. Intuitively, by Equation 1, $\mathcal{R}{\mathrm{rob}}(f)-\mathcal{R}{\mathrm{nat}}^*= \mathcal{R}\mathrm{nat}(f)-\mathcal{R}{\mathrm{nat}}^*+\mathcal{R}{\text{bdy}}(f)\le \psi^{-1}(\mathcal{R}\phi(f)-\mathcal{R}\phi^*)+\mathcal{R}{\text{bdy}}(f)$, where the last inequality holds because we choose $\phi$ as a classification-calibrated loss [27]. This leads to the following result.

########## {caption="Theorem 2"}

Let $\mathcal{R}\phi(f):= \mathbb{E}\phi(f(\bm{X})Y)$ and $\mathcal{R}\phi^*:=\min_f \mathcal{R}_\phi(f)$. Under Assumption 1, for any non-negative loss function $\phi$ such that $\phi(0)\ge 1$, any measurable $f: \mathcal{X}\rightarrow \mathbb{R}$, any probability distribution on $\mathcal{X}\times{\pm 1}$, and any $\lambda>0$, we have[^1]

[^1]: We study the population form of the risk functions, and mention that by incorporating the generalization theory for classification-calibrated losses [27] one can extend the analysis to finite samples. We leave this analysis for future research.

$ \begin{split} \mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*&\le \psi^{-1}(\mathcal{R}\phi(f)-\mathcal{R}\phi^*)+\Pr[\bm{X}\in\mathbb{B}(\mathrm{DB}(f),\epsilon),f(\bm{X})Y>0]\ &\le \psi^{-1}(\mathcal{R}\phi(f)-\mathcal{R}\phi^*)+\mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda). \end{split} $

Quantity governing model robustness. Our result provides a formal justification for the existence of adversarial examples: learning models are vulnerable to small adversarial attacks because the probability that data lie around the decision boundary of the model, $\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon),f(\bm{X})Y>0]$, is large. As a result, small perturbations may move the data point to the wrong side of the decision boundary, leading to weak robustness of classification models.

3.2 Lower bound

We now establish a lower bound on $\mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*$. Our lower bound matches our analysis of the upper bound in Section 3.1 up to an arbitrarily small constant.

########## {caption="Theorem 3"}

Suppose that $| \mathcal{X}|\ge 2$. Under Assumption 1, for any non-negative loss function $\phi$ such that $\phi(x)\rightarrow 0$ as $x\rightarrow +\infty$, any $\xi>0$, and any $\theta\in[0,1]$, there exists a probability distribution on $\mathcal{X}\times {\pm 1}$, a function $f: \mathbb{R}^d\rightarrow \mathbb{R}$, and a regularization parameter $\lambda>0$ such that $\mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*=\theta$ and

$ \begin{split} \psi\Big(\theta-\mathbb{E} &\max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda)\Big)\le \mathcal{R}\phi(f)-\mathcal{R}\phi^*\le \psi\left(\theta-\mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda)\right)+\xi. \end{split} $

Theorem 3 demonstrates that in the presence of extra conditions on the loss function, i.e., $\lim_{x\rightarrow +\infty} \phi(x)=0$, the upper bound in Section 3.1 is tight. The condition holds for all the losses in Table 2.

4. Algorithmic Design for Defenses

Section Summary: The section presents TRADES, a defense method derived from earlier theorems that minimizes a combined objective: one term that reduces natural classification error on clean inputs and a second regularization term that penalizes differences between predictions on clean and adversarially perturbed inputs, controlled by a tunable parameter λ to balance accuracy against robustness. This formulation encourages smoother decision boundaries that keep adversarial examples on the same side as their originals, unlike earlier robust-optimization approaches whose objectives may not explicitly capture that trade-off. The authors also outline a practical multi-class implementation using calibrated surrogate losses solved by alternating gradient steps and contrast the approach with prior regularization techniques such as Adversarial Logit Pairing.

Optimization. Theorem 2 and Theorem 3 shed light on algorithmic designs of adversarial defenses. In order to minimize $\mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*$, the theorems suggest minimizing[^2]

[^2]: For simplicity of implementation, we do not use the function $\psi^{-1}$ and rely on $\lambda$ to approximately reflect the effect of $\psi^{-1}$, the trade-off between the natural error and the boundary error, and the tight approximation of the boundary error using the corresponding surrogate loss function.

$ \min_{f} \mathbb{E} \Big{\underbrace{\phi(f(\bm{X})Y)}{\text{for accuracy}}+\underbrace{\max{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)} \phi(f(\bm{X})f(\bm{X}')/\lambda)}_{\text{regularization for robustness}}\Big}. $

We name our method TRADES (TRadeoff-inspired Adversarial DEfense via Surrogate-loss minimization).

Intuition behind the optimization. captures the trade-off between the natural and robust errors: the first term encourages the natural error to be optimized by minimizing the "difference" between $f(\bm{X})$ and $Y$, while the second regularization term encourages the output to be smooth, that is, it pushes the decision boundary of classifier away from the sample instances via minimizing the "difference" between the prediction of natural example $f(\bm{X})$ and that of adversarial example $f(\bm{X}')$. This is conceptually consistent with the argument that smoothness is an indispensable property of robust models [28]. The tuning parameter $\lambda$ plays a critical role on balancing the importance of natural and robust errors. To see how the $\lambda$ affects the solution in the example of Section 2.4, tends to the Bayes optimal classifier when $\lambda\rightarrow +\infty$, and tends to the all-one classifier when $\lambda\rightarrow 0$.

Comparisons with prior work. We compare our approach with several related lines of research in the prior literature. One of the best known algorithms for adversarial defense is based on robust optimization [19, 17, 29, 18, 30]. Most results in this direction involve algorithms that approximately minimize

$ \min_{f} \mathbb{E} \left{ \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')Y)\right}, $

where the objective function in serves as an upper bound of the robust error $\mathcal{R}_\mathrm{rob}(f)$. In complex problem domains, however, this objective function might not be tight as an upper bound of the robust error, and may not capture the trade-off between natural and robust errors.

A related line of research is adversarial training by regularization [31, 16, 32, 33]. There are several key differences between the results in this paper and those of [16, 32, 33]. Firstly, the optimization formulations are different. In the previous works, the regularization term either measures the "difference" between $f(\bm{X}')$ and $Y$ [16], or its gradient [32]. In contrast, our regularization term measures the "difference" between $f(\bm{X})$ and $f(\bm{X}')$. While [33] generated the adversarial example $\bm{X}'$ by adding random Gaussian noise to $\bm{X}$, our method simulates the adversarial example by solving the inner maximization problem . Secondly, we note that the losses in [31, 16, 32, 33] lack of theoretical guarantees. Our loss, with the presence of the second term in , makes our theoretical analysis significantly more subtle. Moreover, our algorithm takes the same computational resources as [16], which makes our method scalable to large-scale datasets. We defer the experimental comparisons of various regularization based methods to Table 5.

Differences with Adversarial Logit Pairing. We also compare TRADES with Adversarial Logit Pairing (ALP) [34, 35]. The algorithm of ALP works as follows: given a fixed network $f$ in each round, the algorithm firstly generates an adversarial example $\bm{X}'$ by solving $\operatorname*{argmax}_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)} \phi(f(\bm{X}')Y)$; ALP then updates the network parameter by solving a minimization problem

$ \min_f \mathbb{E} \left{\alpha \phi(f(\bm{X}')Y)+(1-\alpha)\phi(f(\bm{X})Y)+|f(\bm{X})-f(\bm{X}')|_{2}/\lambda\right}, $

where $0\le\alpha\le 1$ is a regularization parameter; the algorithm finally repeats the above-mentioned procedure until it converges. We note that there are fundamental differences between TRADES and ALP. While ALP simulates adversarial example $\bm{X}'$ by the FGSM$^{k}$ attack, TRADES simulates $\bm{X}'$ by solving $\operatorname*{argmax}_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)} \phi(f(\bm{X})f(\bm{X}')/\lambda)$. Moreover, while ALP uses the $\ell_2$ loss between $f(\bm{X})$ and $f(\bm{X}')$ to regularize the training procedure without theoretical guarantees, TRADES uses the classification-calibrated loss according to Theorem 2 and Theorem 3.

Heuristic algorithm. In response to the optimization , we use two heuristics to achieve more general defenses: a) extending to multi-class problems by involving multi-class calibrated loss; b) approximately solving the minimax problem via alternating gradient descent. For multi-class problems, a surrogate loss is calibrated if minimizers of the surrogate risk are also minimizers of the 0-1 risk [36]. Examples of multi-class calibrated loss include cross-entropy loss. Algorithmically, we extend to the case of multi-class classifications by replacing $\phi$ with a multi-class calibrated loss $\mathcal{L}(\cdot,\cdot)$:

$ \min_{f} \mathbb{E} \left{\mathcal{L}(f(\bm{X}), \bm{Y})+\max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)} \mathcal{L}(f(\bm{X}),f(\bm{X}'))/\lambda\right}, $

where $f(\bm{X})$ is the output vector of learning model (with softmax operator in the top layer for the cross-entropy loss $\mathcal{L}(\cdot,\cdot)$), $\bm{Y}$ is the label-indicator vector, and $\lambda>0$ is the regularization parameter. One can also exchange $f(\bm{X})$ and $f(\bm{X}')$ in the second term . The pseudocode of adversarial training procedure, which aims at minimizing the empirical form of , is displayed in 7.

Input: Step sizes $\eta_1$ and $\eta_2$, batch size $m$, number of iterations $K$ in inner optimization, network architecture parametrized by $\theta$
Output: Robust network $f_\theta$
Randomly initialize network $f_\theta$, or initialize network with pre-trained configuration
repeat
  Read mini-batch $B=\{\bm{x}_1,..., \bm{x}_m\}$ from training set
  for $i=1,...,m$ (in parallel) do
    $\bm{x}_i'\leftarrow \bm{x}_i+0.001\cdot \mathcal{N}(\mathbf{0}, \mathbf{I})$, where $\mathcal{N}(\mathbf{0}, \mathbf{I})$ is the Gaussian distribution with zero mean and identity variance
    for $k=1,...,K$ do
      $\bm{x}_i'\leftarrow \Pi_{\mathbb{B}(\bm{x}_i,\epsilon)}(\eta_1 \textup{\textsf{sign}}(\nabla_{\bm{x}_i'} \mathcal{L}(f_\theta(\bm{x}_i),f_\theta(\bm{x}_i')))+\bm{x}_i')$, where $\Pi$ is the projection operator
    end for
  end for
  $\theta\leftarrow \theta-\eta_2 \sum_{i=1}^m \nabla_\theta[\mathcal{L}(f_\theta(\bm{x}_i), \bm{y}_i)+\mathcal{L}(f_\theta(\bm{x}_i),f_\theta(\bm{x}_i'))/\lambda]/m$
until training converged

The key ingredient of the algorithm is to approximately solve the linearization of inner maximization in by the projected gradient descent (see Step 7). We note that $\bm{x}i$ is a global minimizer with zero gradient to the objective function $g(\bm{x}'):= \mathcal{L}(f(\bm{x}{i}),f(\bm{x}'))$ in the inner problem. Therefore, we initialize $\bm{x}_i'$ by adding a small, random perturbation around $\bm{x}_i$ in Step 5 to start the inner optimizer. More exhaustive approximations of the inner maximization problem in terms of either optimization formulations or solvers would lead to better defense performance.

Semi-supervised learning. We note that TRADES can be straightforwardly applied to the semi-supervised learning framework, as the second term in does not depend on the label $\bm{Y}$. Therefore, with more unlabeled data points, one can approximate the second term (in the expectation form) better by the empirical loss minimization. There are many interesting recent works which explore the benefits of invloving unlabeled data [37, 38, 39].

Acceleration. Adversarial training is typically more than 10x slower than natural training. To resolve this issue for TRADES, [40, 41] proposed new algorithms to solve at negligible additional cost compared to natural training.

5. Experimental Results

Section Summary: The experiments confirm the effectiveness of the TRADES method by testing it on MNIST and CIFAR10 datasets, using convolutional networks and ResNet models to measure both natural accuracy on clean data and robust accuracy under adversarial perturbations. They first show that the theoretical upper bound from Theorem 2 is tight for a binary classification task, as the gap between the actual robust error and the derived bound remains very small across different regularization values. Further tests reveal that raising the regularization strength improves robustness at the cost of some natural accuracy, with the trade-off being more pronounced on CIFAR10 than on the simpler MNIST task, while overall performance stays relatively stable across a range of hyperparameter choices.

In this section, we verify the effectiveness of TRADES by numerical experiments. We denote by $\mathcal{A}\mathrm{rob}(f) = 1- \mathcal{R}\mathrm{rob}(f)$ the robust accuracy, and by $\mathcal{A}\mathrm{nat}(f) = 1- \mathcal{R}\mathrm{nat}(f)$ the natural accuracy on test dataset. We release our code and trained models at https://github.com/yaodongyu/TRADES.

5.1 Optimality of

Theorem 2

We verify the tightness of the established upper bound in Theorem 2 for binary classification problem on MNIST dataset. The negative examples are ' $1'$ and the positive examples are' $3'$. Here we use a Convolutional Neural Network (CNN) with two convolutional layers, followed by two fully-connected layers. The output size of the last layer is 1. To learn the robust classifier, we minimize the regularized surrogate loss , and use the hinge loss in Table 2 as the surrogate loss $\phi$, where the associated $\psi$-transform is $\psi(\theta) = \theta$.

To verify the tightness of our upper bound, we calculate the left hand side in Theorem 2, i.e.,

$ \Delta_{\text{LHS}}= \mathcal{R}_rob(f)-\mathcal{R}_nat^*, $

and the right hand side, i.e.,

$ \Delta_{\text{RHS}} = (\mathcal{R}\phi(f)-\mathcal{R}\phi^*)+\mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda). $

As we cannot have access to the unknown distribution $\mathcal{D}$, we approximate the above expectation terms by test dataset. We first use natural training method to train a classifier so as to approximately estimate $\mathcal{R}\mathrm{nat}^*$ and $\mathcal{R}\phi^*$, where we find that the naturally trained classifier can achieve natural error $\mathcal{R}\mathrm{nat}^*=0%$, and loss value $\mathcal{R}\phi^*=0.0$ for the binary classification problem. Next, we optimize to train a robust classifier $f$. We take perturbation $\epsilon = 0.1$, number of iterations $K = 20$ and run $30$ epochs on the training dataset. Finally, to approximate the second term in $\Delta_{\text{RHS}}$, we use FGSM$^k$ (white-box) attack (a.k.a. PGD attack) [16] with $20$ iterations to approximately calculate the worst-case perturbed data $\bm{X}^{\prime}$.

::: {caption="Table 3: Theoretical verification on the optimality of Theorem 2."}

:::

The results in Table 3 show the tightness of our upper bound in Theorem 2. It shows that the differences between $\Delta_{\text{RHS}}$ and $\Delta_{\text{LHS}}$ under various $\lambda

5.2 Sensitivity of regularization hyperparameter $\lambda$

The regularization parameter $\lambda$ is an important hyperparameter in our proposed method. We show how the regularization parameter affects the performance of our robust classifiers by numerical experiments on two datasets, MNIST and CIFAR10. For both datasets, we minimize the loss to learn robust classifiers for multi-class problems, where we choose $\mathcal{L}$ as the cross-entropy loss.

MNIST setup. We use the CNN which has two convolutional layers, followed by two fully-connected layers. The output size of the last layer is 10. We set perturbation $\epsilon = 0.1$, perturbation step size $\eta_1 = 0.01$, number of iterations $K = 20$, learning rate $\eta_2 = 0.01$, batch size $m = 128$, and run $50$ epochs on the training dataset. To evaluate the robust error, we apply FGSM$^k$ (white-box) attack with $40$ iterations and $0.005$ step size. The results are in Table 4.

CIFAR10 setup. We apply ResNet-18 [42] for classification. The output size of the last layer is 10. We set perturbation $\epsilon = 0.031$, perturbation step size $\eta_1 = 0.007$, number of iterations $K = 10$, learning rate $\eta_2 = 0.1$, batch size $m = 128$, and run $100$ epochs on the training dataset. To evaluate the robust error, we apply FGSM$^k$ (white-box) attack with $20$ iterations and the step size is $0.003$. The results are in Table 4.

\begin{tabular}{c|cc||cc}
        \hline
         {} & \multicolumn{2}{c}{MNIST} & \multicolumn{2}{c}{CIFAR10}\\
        \hline
        $1/\lambda$ & $\mathcal{A}_\mathrm{rob}(f)$ $(\%)$ & $\mathcal{A}_\mathrm{nat}(f)$ $(\%)$ & $\mathcal{A}_\mathrm{rob}(f)$ $(\%)$ & $\mathcal{A}_\mathrm{nat}(f)$ $(\%)$ \\
        \hline
        0.1 & 91.09 $\pm$ 0.0385 & 99.41 $\pm$ 0.0235 & 26.53 $\pm$ 1.1698 & 91.31 $\pm$ 0.0579 \\
        0.2 & 92.18 $\pm$ 0.0450 & 99.38 $\pm$ 0.0094 & 37.71 $\pm$ 0.6743 & 89.56 $\pm$ 0.2154\\
        0.4 & 93.21 $\pm$ 0.0660 & 99.35 $\pm$ 0.0082 & 41.50 $\pm$ 0.3376 & 87.91 $\pm$ 0.2944\\
        0.6 & 93.87 $\pm$ 0.0464 & 99.33 $\pm$ 0.0141 & 43.37 $\pm$ 0.2706 & 87.50 $\pm$ 0.1621\\
        0.8 & 94.32 $\pm$ 0.0492 & 99.31 $\pm$ 0.0205 & 44.17 $\pm$ 0.2834 & 87.11 $\pm$ 0.2123\\
        1.0 & 94.75 $\pm$ 0.0712 & 99.28 $\pm$ 0.0125 & 44.68 $\pm$ 0.3088 & 87.01 $\pm$ 0.2819\\
        2.0 & 95.45 $\pm$ 0.0883 & 99.29 $\pm$ 0.0262 & 48.22 $\pm$ 0.0740 & 85.22 $\pm$ 0.0543\\
        3.0 & 95.57 $\pm$ 0.0262 & 99.24 $\pm$ 0.0216 & 49.67 $\pm$ 0.3179 & 83.82 $\pm$ 0.4050\\
        4.0 & 95.65 $\pm$ 0.0340 & 99.16 $\pm$ 0.0205 & 50.25 $\pm$ 0.1883 & 82.90 $\pm$ 0.2217\\
        5.0 & 95.65 $\pm$ 0.1851 & 99.16 $\pm$ 0.0403 & 50.64 $\pm$ 0.3336 & 81.72 $\pm$ 0.0286\\
        \hline
    \end{tabular}

We observe that as the regularization parameter $1/\lambda$ increases, the natural accuracy $\mathcal{A}\mathrm{nat}(f)$ decreases while the robust accuracy $\mathcal{A}\mathrm{rob}(f)$ increases, which verifies our theory on the trade-off between robustness and accuracy. Note that for MNIST dataset, the natural accuracy does not decrease too much as the regularization term $1/\lambda$ increases, which is different from the results of CIFAR10. This is probably because the classification task for MNIST is easier. Meanwhile, our proposed method is not very sensitive to the choice of $\lambda$. Empirically, when we set the hyperparameter $1/\lambda$ in $[1, 10]$, our method is able to learn classifiers with both high robustness and high accuracy. We will set $1/\lambda$ as either 1 or 6 in the following experiments.

5.3 Adversarial defenses under various attacks

Previously, [26] showed that 7 defenses in ICLR 2018 which relied on obfuscated gradients may easily break down. In this section, we verify the effectiveness of our method with the same experimental setup under both white-box and black-box threat models.

MNIST setup. We use the CNN architecture in [43] with four convolutional layers, followed by three fully-connected layers. We set perturbation $\epsilon = 0.3$, perturbation step size $\eta_1 = 0.01$, number of iterations $K = 40$, learning rate $\eta_2 = 0.01$, batch size $m = 128$, and run $100$ epochs on the training dataset.

CIFAR10 setup. We use the same neural network architecture as [19], i.e., the wide residual network WRN-34-10 [44]. We set perturbation $\epsilon = 0.031$, perturbation step size $\eta_1 = 0.007$, number of iterations $K = 10$, learning rate $\eta_2 = 0.1$, batch size $m = 128$, and run $100$ epochs on the training dataset.

5.3.1 White-box attacks

We summarize our results in Table 5 together with the results from [26]. We also implement methods in [33, 16, 32] on the CIFAR10 dataset as they are also regularization based methods. For MNIST dataset, we apply FGSM$^k$ (white-box) attack with $40$ iterations and the step size is $0.01$. For CIFAR10 dataset, we apply FGSM$^k$ (white-box) attack with $20$ iterations and the step size is $0.003$, under which the defense model in [19] achieves $47.04%$ robust accuracy. Table 5 shows that our proposed defense method can significantly improve the robust accuracy of models, which is able to achieve robust accuracy as high as $56.61%$. We also evaluate our robust model on MNIST dataset under the same threat model as in [45] (C&W white-box attack [43]), and the robust accuracy is $99.46%$. See appendix for detailed information of models in Table 5.

\begin{tabular}{c||c|c|c|c|c|c}
        \hline
        Defense & Defense type & Under which attack & Dataset & Distance & $\mathcal{A}_\mathrm{nat}(f)$ & $\mathcal{A}_\mathrm{rob}(f)$  
        \\
        \hline
        \hline
        [46] & gradient mask & [26] & CIFAR10 & $0.031$ ($\ell_\infty$) & - & 0\% \\
        [47] & gradient mask & [26] & CIFAR10 & $0.031$ ($\ell_\infty$) & - & 5\% \\
        [48] & gradient mask & [26] & CIFAR10 & $0.031$ ($\ell_\infty$) & - & 0\% \\
        [3] & gradient mask & [26] & CIFAR10 & $0.031$ ($\ell_\infty$) & - & 9\% \\ 
        [49] & gradient mask & [26] & CIFAR10 & $0.015$ ($\ell_\infty$) & - & 15\% \\ 
        [29] & robust opt. & FGSM$^{20}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 27.07\% & 23.54\% \\
        [19] & robust opt. & FGSM$^{20}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 87.30\% & \textbf{47.04\%} \\
        [33] & regularization & FGSM$^{20}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 94.64\% & 0.15\% \\
        [16] & regularization & FGSM$^{20}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 85.25\% & 45.89\% \\
        [32] & regularization & FGSM$^{20}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 95.34\% & 0\% \\
        {TRADES} ($1/\lambda=1$) & regularization & FGSM$^{1, 000}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 48.90\% \\
        {TRADES} ($1/\lambda=6$) & regularization & FGSM$^{1, 000}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & \textbf{56.43\%} \\
        {TRADES} ($1/\lambda=1$) & regularization & FGSM$^{20}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 49.14\% \\
        {TRADES} ($1/\lambda=6$) & regularization & FGSM$^{20}$ (PGD) & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & \textbf{56.61\%} \\
        {TRADES} ($1/\lambda=1$) & regularization & DeepFool ($\ell_\infty$) & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 59.10\% \\
        {TRADES} ($1/\lambda=6$) & regularization & DeepFool ($\ell_\infty$) & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & 61.38\% \\
        {TRADES} ($1/\lambda=1$) & regularization & LBFGSAttack & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 84.41\% \\
        {TRADES} ($1/\lambda=6$) & regularization & LBFGSAttack & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & 81.58\% \\
        {TRADES} ($1/\lambda=1$) & regularization & MI-FGSM & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 51.26\% \\
        {TRADES} ($1/\lambda=6$) & regularization & MI-FGSM & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & 57.95\% \\
        {TRADES} ($1/\lambda=1$) & regularization & C\&W & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 84.03\% \\
        {TRADES} ($1/\lambda=6$) & regularization & C\&W & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & 81.24\% \\
        \hline
        [45] & gradient mask & [26] & MNIST & $0.005$ ($\ell_2$) & - & 55\% \\
        [19] & robust opt. & FGSM$^{40}$ (PGD) & MNIST & $0.3$ ($\ell_\infty$) & 99.36\% & 96.01\% \\
        {TRADES} ($1/\lambda=6$) & regularization & FGSM$^{1, 000}$ (PGD) & MNIST & $0.3$ ($\ell_\infty$) & 99.48\% & 95.60\% \\
        {TRADES} ($1/\lambda=6$) & regularization & FGSM$^{40}$ (PGD) & MNIST & $0.3$ ($\ell_\infty$) & 99.48\% & 96.07\% \\
        {TRADES} ($1/\lambda=6$) & regularization & C\&W & MNIST & $0.005$ ($\ell_2$) & 99.48\% & 99.46\% \\
        \hline
    \end{tabular}

5.3.2 Black-box attacks

We verify the robustness of our models under black-box attacks. We first train models without using adversarial training on the MNIST and CIFAR10 datasets. We use the same network architectures that are specified in the beginning of this section, i.e., the CNN architecture in [43] and the WRN-34-10 architecture in [44]. We denote these models by naturally trained models (Natural). The accuracy of the naturally trained CNN model is $99.50%$ on the MNIST dataset. The accuracy of the naturally trained WRN-34-10 model is $95.29%$ on the CIFAR10 dataset. We also implement the method proposed in [19] on both datasets. We denote these models by Madry's models (Madry). The accuracy of [19]'s CNN model is $99.36%$ on the MNIST dataset. The accuracy of [19]'s WRN-34-10 model is $85.49%$ on the CIFAR10 dataset.

For both datasets, we use FGSM$^{k}$ (black-box) method to attack various defense models. For MNIST dataset, we set perturbation $\epsilon=0.3$ and apply FGSM$^k$ (black-box) attack with $40$ iterations and the step size is $0.01$. For CIFAR10 dataset, we set $\epsilon=0.031$ and apply FGSM$^k$ (black-box) attack with $20$ iterations and the step size is $0.003$. Note that the setup is the same as the setup specified in Section 5.3.1. We summarize our results in Table 6 and Table 7. In both tables, we use two source models (noted in the parentheses) to generate adversarial perturbations: we compute the perturbation directions according to the gradients of the source models on the input images. It shows that our models are more robust against black-box attacks transfered from naturally trained models and [19]'s models. Moreover, our models can generate stronger adversarial examples for black-box attacks compared with naturally trained models and [19]'s models.

\begin{tabular}{c||cc}
        \hline
        Defense Model & \multicolumn{2}{c}{Robust Accuracy $\mathcal{A}_\mathrm{rob}(f)$}
        \\
        \hline
        {Madry} & 97.43\% [0.0078484] & (Natural)  
        \\ 
        \hline
        {TRADES} & \textbf{97.63\%} [0.0075324] & (Natural)
        \\
        \hline
        {Madry} & 97.38\% [0.0084962] & (Ours) \\ 
        \hline
        {TRADES} & \textbf{97.66\%} [0.0073532] & (Madry)  
        \\
        \hline
    \end{tabular}

\begin{tabular}{c||cc}
        \hline
        Defense Model & \multicolumn{2}{c}{Robust Accuracy $\mathcal{A}_\mathrm{rob}(f)$}
        \\
        \hline
        {Madry} & 84.39\% [0.0519784] & (Natural) \\ 
        \hline
        {TRADES} & \textbf{87.60\%} [0.0380258] & (Natural) \\
        \hline
        {Madry} & 66.00\% [0.1252672] &(Ours) \\ 
        \hline
        {TRADES} & \textbf{70.14}\% [0.0885364] & (Madry) \\
        \hline
    \end{tabular}

5.4 Case study: NeurIPS 2018 Adversarial Vision Challenge

Competition settings. In the adversarial competition, the adversarial attacks and defenses are under the black-box setting. The dataset in this competition is Tiny ImageNet, which consists of 550, 000 data (with our data augmentation) and 200 classes. The robust models only return label predictions instead of explicit gradients and confidence scores. The task for robust models is to defend against adversarial examples that are generated by the top-5 submissions in the un-targeted attack track. The score for each defense model is evaluated by the smallest perturbation distance that makes the defense model fail to output correct labels.

Competition results. The methodology in this paper was applied to the competition, where our entry ranked the 1st place. We implemented our method to train ResNet models. We report the mean $\ell_2$ perturbation distance of the top-6 entries in Figure 3. It shows that our method outperforms other approaches with a large margin. In particular, we surpass the runner-up submission by $11.41%$ in terms of mean $\ell_2$ perturbation distance.

6. Conclusions

Section Summary: This paper examines defenses that help machine learning models resist small structural changes to input data, with a focus on the inherent tension between making models robust and keeping their accuracy high on normal data. The authors derive a tight upper bound on the performance gap between robust and standard error, which directly motivates a new regularized training objective called TRADES. Experiments on real datasets and in adversarial competitions show that this method improves robustness, and the work suggests combining it with other techniques such as feature denoising to build stronger systems overall.

In this paper, we study the problem of adversarial defenses against structural perturbations around input data. We focus on the trade-off between robustness and accuracy, and show an upper bound on the gap between robust error and optimal natural error. Our result advances the state-of-the-art work and matches the lower bound in the worst-case scenario. The bounds motivate us to minimize a new form of regularized surrogate loss, TRADES, for adversarial training. Experiments on real datasets and adversarial competition demonstrate the effectiveness of our proposed algorithms. It would be interesting to combine our methods with other related line of research on adversarial defenses, e.g., feature denoising technique [50] and network architecture design [28], to achieve more robust learning systems.

Acknowledgements. We thank Maria-Florina Balcan, Avrim Blum, Zico Kolter, and Aleksander Mądry for valuable comments and discussions.

Appendix

Section Summary: The appendix first surveys related research on adversarial attacks, such as the FGSM and projected gradient descent methods, along with defense strategies based on robust optimization and convex relaxations, and notes key theoretical gaps including the absence of formal guarantees and limited analysis of accuracy-robustness trade-offs. It then supplies formal proofs of the paper’s main results, beginning with Theorem 2, which derives upper bounds on the robust risk of a classifier in terms of a surrogate loss and a boundary error term under standard assumptions. The proofs rely on properties of classification-calibrated losses and properties of the perturbation ball to connect natural and adversarial error.

A. Other Related Works

Attack methods. Although deep neural networks have achieved great progress in various areas [51, 52], they are brittle to adversarial attacks. Adversarial attacks have been extensively studied in the recent years. One of the baseline attacks to deep nerual networks is the Fast Gradient Sign Method (FGSM) [53]. FGSM computes an adversarial example as

$ \bm{x}':= \bm{x}+\epsilon \textup{\textsf{sign}}(\nabla_{\bm{x}} \phi(f(\bm{x})y)), $

where $\bm{x}$ is the input instance, $y$ is the label, $f: \mathcal{X}\rightarrow \mathbb{R}$ is the score function (parametrized by deep nerual network for example) which maps an instance to its confidence value of being positive, and $\phi(\cdot)$ is a surrogate of 0-1 loss. A more powerful yet natural extension of FGSM is the multi-step variant FGSM$^k$ (also known as PGD attack) [16]. FGSM$^k$ applies projected gradient descent by $k$ times:

$ \bm{x}{t+1}':=\Pi{\mathbb{B}(\bm{x},\epsilon)}(\bm{x}t'+\epsilon \textup{\textsf{sign}}(\nabla{\bm{x}} \phi(f(\bm{x}_t')y))), $

where $\bm{x}_t'$ is the $t$-th iteration of the algorithm with $\bm{x}0':= \bm{x}$ and $\Pi{\mathbb{B}(\bm{x},\epsilon)}$ is the projection operator onto the ball $\mathbb{B}(\bm{x},\epsilon)$. Both FGSM and FGSM$^k$ are approximately solving (the linear approximation of) maximization problem:

$ \max_{\bm{x}'\in \mathbb{B}(\bm{x},\epsilon)} \phi(f(\bm{x}')y). $

They can be adapted to the purpose of black-box attacks by running the algorithms on another similar network which is white-box to the algorithms [54]. Though defenses that cause obfuscated gradients defeat iterative optimization based attacks, [26] showed that defenses relying on this effect can be circumvented. Other attack methods include MI-FGSM [55] and LBFGS attacks [56].

Robust optimization based defenses. Compared with attack methods, adversarial defense methods are relatively fewer. Robust optimization based defenses are inspired by the above-mentioned attacks. Intuitively, the methods train a network by fitting its parameters to the adversarial examples:

$ \min_{f} \mathbb{E} \left{ \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')Y)\right}. $

Following this framework, [57, 58] considered one-step adversaries, while [19] worked with multi-step methods for the inner maximization problem. There are, however, two critical differences between the robust optimization based defenses and the present paper. Firstly, robust optimization based defenses lack of theoretical guarantees. Secondly, such methods do not consider the trade-off between accuracy and robustness.

Relaxation based defenses. We mention another related line of research in adversarial defenses—relaxation based defenses. Given that the inner maximization in might be hard to solve due to the non-convexity nature of deep neural networks, [17] and [18] considered a convex outer approximation of the set of activations reachable through a norm-bounded perturbation for one-hidden-layer neural networks. [29] later scaled the methods to larger models, and [30] proposed a tighter convex approximation. [59, 60] considered a Lagrangian penalty formulation of perturbing the underlying data distribution in a Wasserstein ball. These approaches, however, do not apply when the activation function is ReLU.

Theoretical progress. Despite a large amount of empirical works on adversarial defenses, many fundamental questions remain open in theory. There are a few preliminary explorations in recent years. [61] derived upper bounds on the robustness to perturbations of any classification function, under the assumption that the data is generated with a smooth generative model. From computational aspects, [24, 25] showed that adversarial examples in machine learning are likely not due to information-theoretic limitations, but rather it could be due to computational hardness. From statistical aspects, [21] showed that the sample complexity of robust training can be significantly larger than that of standard training. This gap holds irrespective of the training algorithm or the model family. [22] and [23] studied the uniform convergence of robust error $\mathcal{R}_\mathrm{rob}(f)$ by extending the classic VC and Rademacher arguments to the case of adversarial learning, respectively. A recent work demonstrates the existence of trade-off between accuracy and robustness [14], without providing a practical algorithm to address it.

B. Proofs of Main Results

In this section, we provide the proofs of our main results.

B.1 Proof of Theorem 2

Theorem 2 (restated). Let $\mathcal{R}\phi(f):= \mathbb{E}\phi(f(\bm{X})Y)$ and $\mathcal{R}\phi^:=\min_f \mathcal{R}_\phi(f)$. Under Assumption 1, for any non-negative loss function $\phi$ such that $\phi(0)\ge 1$, any measurable $f: \mathcal{X}\rightarrow \mathbb{R}$, any probability distribution on $\mathcal{X}\times{\pm 1}$, and any $\lambda>0$, we have

$ \begin{split} \quad \mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*&\le \psi^{-1}(\mathcal{R}\phi(f)-\mathcal{R}\phi^*)+\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon),f(\bm{X})Y>0]\ &\le \psi^{-1}(\mathcal{R}\phi(f)-\mathcal{R}\phi^*)+\mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda). \end{split} $

Proof: By Equation 1, $\mathcal{R}{\mathrm{rob}}(f)-\mathcal{R}{\mathrm{nat}}^*= \mathcal{R}\mathrm{nat}(f)-\mathcal{R}{\mathrm{nat}}^*+\mathcal{R}{\text{bdy}}(f)\le \psi^{-1}(\mathcal{R}\phi(f)-\mathcal{R}\phi^*)+\mathcal{R}{\text{bdy}}(f)$, where the last inequality holds because we choose $\phi$ as a classification-calibrated loss [27]. This leads to the first inequality.

Also, notice that

$ \begin{split}\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon),f(\bm{X})Y>0]&\le \Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)]\&= \mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\mathbf{1}{f(\bm{X}')\not=f(\bm{X})}\&= \mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\mathbf{1}{f(\bm{X}')f(\bm{X})/\lambda<0}\&\le \mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda).\end{split} $

This leads to the second inequality.

B.2 Proof of Theorem 3

Theorem 3 (restated). Suppose that $| \mathcal{X}|\ge 2$. Under Assumption 1, for any non-negative loss function $\phi$ such that $\phi(x)\rightarrow 0$ as $x\rightarrow +\infty$, any $\xi>0$, and any $\theta\in[0,1]$, there exists a probability distribution on $\mathcal{X}\times {\pm 1}$, a function $f: \mathbb{R}^d\rightarrow \mathbb{R}$, and a regularization parameter $\lambda>0$ such that $\mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^=\theta$ and

$ \psi\Big(\theta-\mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda)\Big)\le \mathcal{R}\phi(f)-\mathcal{R}\phi^*\le \psi\left(\theta-\mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda)\right)+\xi. $

Proof: The first inequality follows from Theorem 2. Thus it suffices to prove the second inequality.

Fix $\epsilon>0$ and $\theta\in[0,1]$. By the definition of $\psi$ and its continuity, we can choose $\gamma,\alpha_1,\alpha_2\in[0,1]$ such that $\theta=\gamma\alpha_1+(1-\gamma)\alpha_2$ and $\psi(\theta)\ge \gamma\tilde{\psi}(\alpha_1)+(1-\gamma)\tilde{\psi}(\alpha_2)-\epsilon/3$. For two distinct points $\bm{x}_1, \bm{x}2\in \mathcal{X}$, we set $\mathcal{P}\mathcal{X}$ such that $\Pr[\bm{X}= \bm{x}_1]=\gamma$, $\Pr[\bm{X}= \bm{x}_2]=1-\gamma$, $\eta(\bm{x}_1)=(1+\alpha_1)/2$, and $\eta(\bm{x}_2)=(1+\alpha_2)/2$. By the definition of $H^-$, we choose function $f: \mathbb{R}^d\rightarrow \mathbb{R}$ such that $f(\bm{x})< 0$ for all $\bm{x}\in \mathcal{X}$, $C_{\eta(\bm{x}_1)}(f(\bm{x}_1))\le H^-(\eta(\bm{x}_1))+\epsilon/3$, and $C_{\eta(\bm{x}_2)}(f(\bm{x}_2))\le H^-(\eta(\bm{x}_2))+\epsilon/3$. By the continuity of $\psi$, there is an $\epsilon'>0$ such that $\psi(\theta)\le \psi(\theta-\epsilon_0)+\epsilon/3$ for all $0\le \epsilon_0<\epsilon'$. We also note that there exists an $\lambda_0>0$ such that for any $0<\lambda<\lambda_0$, we have

$ 0\le \mathbb{E} \max_{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda)<\epsilon'. $

Thus, we have

$ \begin{split}\mathcal{R}\phi(f)-\mathcal{R}\phi^*&= \mathbb{E}\phi(Yf(\bm{X}))-\inf_f \mathbb{E}\phi(Yf(\bm{X}))\&=\gamma [C_{\eta(\bm{x}_1)}(f(\bm{x}_1))-H(\eta(\bm{x}1))]+(1-\gamma)[C{\eta(\bm{x}_2)}(f(\bm{x}_2))-H(\eta(\bm{x}_2))]\&\le \gamma [H^-(\eta(\bm{x}_1))-H(\eta(\bm{x}_1))]+(1-\gamma)[H^-(\eta(\bm{x}_2))-H(\eta(\bm{x}2))]+\epsilon/3\&=\gamma \tilde\psi(\alpha_1)+(1-\gamma)\tilde{\psi}(\alpha_2)+\epsilon/3\&\le \psi(\theta)+2\epsilon/3\&\le \psi\left(\theta-\mathbb{E} \max{\bm{X}'\in \mathbb{B}(\bm{X},\epsilon)}\phi(f(\bm{X}')f(\bm{X})/\lambda)\right)+\epsilon.\end{split} $

Furthermore, by Lemma 8,

$ \begin{split}\mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*&= \mathbb{E}[\mathbf{1}{\textup{\textsf{sign}}(f(\bm{X}))\not= \textup{\textsf{sign}}(f^*(\bm{X})), \bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp}|2\eta(\bm{X})-1|]\&\quad +\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f^*(\bm{X}))=Y]\&= \mathbb{E}|2\eta(\bm{X})-1|\&=\gamma (2\eta(\bm{x}_1)-1)+(1-\gamma)(2\eta(\bm{x}_2)-1)\&=\theta,\end{split} $

where $f^*$ is the Bayes optimal classifier which outputs "positive" for all data points.

C. Extra Theoretical Results

In this section, we provide extra theoretical results for adversarial defenses.

C.1 Adversarial vulnerability under log-concave distributions Theorem 2 states that for any classifier $f$, the value $\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)]$ characterizes the robustness of the classifier. In this section, we show that among all classifiers such that $\Pr[\textup{\textsf{sign}}(f(\bm{X}))=+1]=1/2$, linear classifier minimizes

$ \liminf_{\epsilon\rightarrow+0}\frac{\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)]}{\epsilon}, $

provided that the marginal distribution over $\mathcal{X}$ is products of log-concave measures. A measure is log-concave if the logarithm of its density is a concave function. The class of log-concave measures contains many well-known (classes of) distributions as special cases, such as Gaussian and uniform measure over ball.

Our results are inspired by the isoperimetric inequality of log-concave distributions by the work of [62]. Intuitively, the isoperimetric problem consists in finding subsets of prescribed measure, such that its measure increases the less under enlargement. Our analysis leads to the following guarantee on the .

########## {caption="Theorem 4"}

Let $\mu$ be an absolutely continuous log-concave probability measure on $\mathbb{R}$ with even density function and let $\mu^{\otimes d}$ be the products of $\mu$ with dimension $d$. Denote by $d\mu=e^{-M(x)}$, where $M: \mathbb{R}\rightarrow[0,\infty]$ is convex. Assume that $M(0)=0$. If $\sqrt{M(x)}$ is a convex function, then for every integer $d$ and any classifier $f$ with $\Pr[\textup{\textsf{sign}}(f(\bm{X}))=+1]=1/2$, we have

$ \liminf_{\epsilon\rightarrow+0}\frac{\Pr_{\bm{X}\sim \mu^{\otimes d}}[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)]}{\epsilon}\ge c $

for an absolute constant $c>0$. Furthermore, among all such probability measures and classifiers, the linear classifier over products of Gaussian measure with mean $0$ and variance $1/(2\pi)$ achieves the lower bound.

Theorem 4 claims that under the products of log-concave distributions, the quantity $\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)]$ increases with rate at least $\Omega(\epsilon)$ for all classifier $f$, among which the linear classifier achieves the minimal value.

:::: {.figure cols="1"} {width=50%}

{width=50%}

Figure 4: Left figure: boundary neighborhood of linear classifier. Right figure: boundary neighborhood of non-linear classifier. Theorem 4 shows that the mass of $S_{\text{linear}}$ is smaller than the mass of $S_{\text{non-linear}}$, provided that the underlying distribution over the instance space is the products of log-concave distribution on the real line. ::::

C.1.1 Proofs of Theorem 4

For a Borel set $\mathcal{A}$ and for $\epsilon>0$, denote by $\mathcal{A}_\epsilon={\bm{x}:d(\bm{x}, \mathcal{A})\le\epsilon}$. The boundary measure of $\mathcal{A}$ is then defined as

$ \mu^+(\mathcal{A})=\liminf_{\epsilon\rightarrow+0}\frac{\mu(\mathcal{A}_\epsilon)-\mu(\mathcal{A})}{\epsilon}. $

The isoperimetric function is

$ I_\mu=\inf{\mu^+(\mathcal{A}):\mu(\mathcal{A})=1/2}. $

Before proceeding, we cite the following results from [62].

########## {caption="Lemma 5: Theorem 9, [62]"}

Let $\mu$ be an absolutely continuous log-concave probability measure on $\mathbb{R}$ with even density function. Denote by $d\mu=e^{-M(x)}$, where $M: \mathbb{R}\rightarrow[0,\infty]$ is convex. Assume that $M(0)=0$. If $\sqrt{M(x)}$ is a convex function, then for every integer $d$, we have $I_{\mu^{\otimes d}}\ge I_{\gamma^{\otimes d}}$, where $\gamma$ is the Gaussian measure with mean $0$ and variance $1/(2\pi)$. In particular, among sets of measure $1/2$ for $\mu^{\otimes d}$, the halfspace $[0,\infty)\times \mathbb{R}^{d-1}$ is solution to the isoperimetric .

Now we are ready to prove Theorem 4.

Proof: We note that

$ \begin{split} &\quad\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)]\ &=\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f(\bm{X}))=+1]+\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f(\bm{X}))=-1]. \end{split} $

To apply Lemma 5, we set the $\mathcal{A}$ in Lemma 5 as the event ${\textup{\textsf{sign}}(f(\bm{X}))=+1}$. Therefore, the set

$ \mathcal{A}_\epsilon={\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f(\bm{X}))=-1}. $

By Lemma 5, we know that for linear classifier $f_0$ which represents the halfspace $[0,\infty)\times \mathbb{R}^{d-1}$, and any classifier $f$,

$ \begin{split} &\liminf_{\epsilon\rightarrow+0} \frac{\Pr_{\bm{X}\sim \mu^{\otimes d}}[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f(\bm{X}))=-1]-\Pr[\textup{\textsf{sign}}(f(\bm{X}))=+1]}{\epsilon}\ &\ge \liminf_{\epsilon\rightarrow+0} \frac{\Pr_{\bm{X}\sim \gamma^{\otimes d}}[\bm{X}\in \mathbb{B}(\mathrm{DB}(f_0),\epsilon), \textup{\textsf{sign}}(f_0(\bm{X}))=-1]-\Pr[\textup{\textsf{sign}}(f_0(\bm{X}))=+1]}{\epsilon}. \end{split} $

Similarly, we have

$ \begin{split} &\liminf_{\epsilon\rightarrow+0} \frac{\Pr_{\bm{X}\sim \mu^{\otimes d}}[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f(\bm{X}))=+1]-\Pr[\textup{\textsf{sign}}(f(\bm{X}))=-1]}{\epsilon}\ &\ge \liminf_{\epsilon\rightarrow+0} \frac{\Pr_{\bm{X}\sim \gamma^{\otimes d}}[\bm{X}\in \mathbb{B}(\mathrm{DB}(f_0),\epsilon), \textup{\textsf{sign}}(f_0(\bm{X}))=+1]-\Pr[\textup{\textsf{sign}}(f_0(\bm{X}))=-1]}{\epsilon}. \end{split} $

Adding both sides , we have

$ \begin{split} \liminf_{\epsilon\rightarrow+0} \frac{\Pr_{\bm{X}\sim \mu^{\otimes d}}[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)]}{\epsilon}&\ge \liminf_{\epsilon\rightarrow+0} \frac{\Pr_{\bm{X}\sim \gamma^{\otimes d}}[\bm{X}\in \mathbb{B}(\mathrm{DB}(f_0),\epsilon)]}{\epsilon}\ge c. \end{split} $

C.2 Margin based generalization bounds

Before proceeding, we first cite a useful lemma. We say that function $f_1: \mathbb{R}\rightarrow \mathbb{R}$ and $f_2: \mathbb{R}\rightarrow \mathbb{R}$ have a $\gamma$ separator if there exists a function $f_3: \mathbb{R}\rightarrow \mathbb{R}$ such that $|h_1-h_2|\le\gamma$ implies $f_1(h_1)\le f_3(h_2)\le f_2(h_1)$. For any given function $f_1$ and $\gamma>0$, one can always construct $f_2$ and $f_3$ such that $f_1$ and $f_2$ have a $\gamma$-separator $f_3$ by setting $f_2(h)=\sup_{|h-h'|\le2\gamma}f_1(h')$ and $f_3(h)=\sup_{|h-h'|\le\gamma}f_1(h')$.

########## {caption="Lemma 6: Corollary 1, [63]"}

Let $f_1$ be a function $\mathbb{R}\rightarrow \mathbb{R}$. Consider a family of functions $f_2^\gamma: \mathbb{R}\rightarrow \mathbb{R}$, parametrized by $\gamma$, such that $0\le f_1\le f_2^\gamma\le 1$. Assume that for all $\gamma$, $f_1$ and $f_2^\gamma$ has a $\gamma$ separator. Assume also that $f_2^\gamma(z)\ge f_2^{\gamma'}(z)$ when $\gamma\ge\gamma'$. Let $\gamma_1>\gamma_2>...$ be a decreasing sequence of parameters, and $p_i$ be a sequence of positive numbers such that $\sum_{i=1}^\infty p_i=1$, then for all $\eta>0$, with probability of at least $1-\delta$ over data:

$ \mathbb{E}{(\bm{X},Y)\sim \mathcal{D}} f_1(\mathcal{L}(\bm{w}, \bm{X},Y))\le \frac{1}{n}\sum{i=1}^n f_2^\gamma(\mathcal{L}(\bm{w}, \bm{x}i,y_i))+\sqrt{\frac{32}{n}\left(\ln 4 \mathcal{N}\infty(\mathcal{L},\gamma_i, \bm{x}_{1:n})+\ln\frac{1}{p_i \delta}\right)} $

for all $\bm{w}$ and $\gamma$, where for each fixed $\gamma$, we use $i$ to denote the smallest index such that $\gamma_i\le\gamma$.

########## {caption="Lemma 7: Theorem 4, [63]"}

If $| \bm{x}|_p\le b$ and $| \bm{w}|_q\le a$, where $2\le p<\infty$ and $1/p+1/q=1$, then $\forall\gamma>0$,

$ \log_2 \mathcal{N}_\infty(\mathcal{L},\gamma,n)\le 36(p-1)\frac{a^2b^2}{\gamma^2}\log_2[2\lceil 4ab/\gamma+2\rceil+1]. $

########## {caption="Theorem"}

Suppose that the data is 2-norm bounded by $| \bm{x}|2\le b$. Consider the family $\Gamma$ of linear classifier $\bm{w}$ with $| \bm{w}|2=1$. Let $\mathcal{R}\mathrm{rob}(\bm{w}):= \mathbb{E}{(\bm{X},Y)\sim \mathcal{D}}\mathbf{1}[\exists \bm{X}^\mathrm{rob}\in \mathbb{B}_2(\bm{X},\epsilon) \text{ such that } Y \bm{w}^T \bm{X}^\mathrm{rob}\le 0]$. Then with probability at least $1-\delta$ over $n$ random samples $(\bm{x}_i,y_i)\sim \mathcal{D}$, for all margin width $\gamma>0$ and $\bm{w}\in\Gamma$, we have

$ \mathcal{R}\mathrm{rob}(\bm{w})\le \frac{1}{n}\sum{i=1}^n \mathbf{1}(\exists \bm{x}_i^\mathrm{rob}\in \mathbb{B}(\bm{x}_i,\epsilon)\text{ s.t. }y_i \bm{w}^T \bm{x}_i^\mathrm{rob}\le2\gamma)+\sqrt{\frac{C}{n}\left(\frac{b^2}{\gamma^2}\ln n+\ln\frac{1}{\delta}\right)}. $

Proof: The theorem is a straightforward result of Lemma 6 and Lemma 7 with

$ \mathcal{L}(\bm{w}, \bm{x},y)=\min_{\bm{x}^\mathrm{rob}\in \mathbb{B}(\bm{x},\epsilon)}y \bm{w}^T \bm{x}^\mathrm{rob}, $

$ f_1(g)= \mathbf{1}(g\le 0)\quad\text{and}\quad f_2^\gamma(h)=\sup_{|g-h|<2\gamma} f_1(g)=f_1(g-2\gamma)= \mathbf{1}(g\le 2\gamma), $

and $\gamma_i=b/2^i$ and $p_i=1/2^i$.

We note that for the $\ell_2$ ball $\mathbb{B}_2(\bm{x},\epsilon)={\bm{x}':| \bm{x}-\bm{x}'|_2\le\epsilon}$, we have

$ \mathbf{1}(\exists \bm{x}_i^\mathrm{rob}\in \mathbb{B}(\bm{x}_i,\epsilon)\text{ s.t. }y_i \bm{w}^T \bm{x}i^\mathrm{rob}\le2\gamma)=\max{\bm{x}_i^\mathrm{rob}\in \mathbb{B}(\bm{x}_i,\epsilon)}\mathbf{1}(y_i \bm{w}^T \bm{x}_i^\mathrm{rob}\le2\gamma)= \mathbf{1}(y_i \bm{w}^T \bm{x}_i\le2\gamma+\epsilon). $

Therefore, we can design the following algorithm—.

C.3 A lemma

We denote by $f^*(\cdot):=2\eta(\cdot)-1$ the Bayes decision rule throughout the proofs.

########## {caption="Lemma 8"}

For any classifier $f$, we have

$ \begin{split} \mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}^*=& \mathbb{E}[\mathbf{1}{\textup{\textsf{sign}}(f(\bm{X}))\not= \textup{\textsf{sign}}(f^*(\bm{X})), \bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp}|2\eta(\bm{X})-1|]\ &+\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f^*(\bm{X}))=Y]. \end{split} $

Proof: For any classifier $f$, we have

$ \begin{split} &\quad \Pr(\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. } \textup{\textsf{sign}}(f(\bm{X}'))\not=Y| \bm{X}= \bm{x})\ &=\Pr(Y=1,\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{X}'))=-1| \bm{X}= \bm{x})\ &\quad+\Pr(Y=-1,\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{X}'))=1| \bm{X}= \bm{x})\ &= \mathbb{E}[\mathbf{1}{Y=1}\mathbf{1}{\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{X}'))=-1}| \bm{X}= \bm{x}]\ &\quad +\mathbb{E}[\mathbf{1}{Y=-1}\mathbf{1}{\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{X}'))=1}| \bm{X}= \bm{x}]\ &= \mathbf{1}{\exists \bm{x}'\in \mathbb{B}(\bm{x},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{x}'))=-1}\mathbb{E}\mathbf{1}{Y=1| \bm{X}= \bm{x}}\ &\quad+\mathbf{1}{\exists \bm{x}'\in \mathbb{B}(\bm{x},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{x}'))=1}\mathbb{E}\mathbf{1}{Y=-1| \bm{X}= \bm{x}}\ &= \mathbf{1}{\exists \bm{x}'\in \mathbb{B}(\bm{x},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{x}'))=-1}\eta(\bm{x})+\mathbf{1}{\exists \bm{x}'\in \mathbb{B}(\bm{x},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{x}'))=1}(1-\eta(\bm{x}))\ &= \begin{cases} 1, & \bm{x}\in \mathbb{B}(\mathrm{DB}(f),\epsilon),\ \mathbf{1}{\textup{\textsf{sign}}(f(\bm{x}))=-1}(2\eta(\bm{x})-1)+(1-\eta(\bm{x})), & \text{otherwise}. \end{cases} \end{split} $

Therefore,

$ \begin{split}&\quad \mathcal{R}\mathrm{rob}(f)\&=\int{\mathcal{X}} \Pr[\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{X}'))\not=Y| \bm{X}= \bm{x}] d \Pr\nolimits_{\bm{X}}(\bm{x})\&=\int_{\mathbb{B}(\mathrm{DB}(f),\epsilon)} \Pr[\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{X}'))\not=Y| \bm{X}= \bm{x}] d \Pr\nolimits_{\bm{X}}(\bm{x})\&\quad +\int_{\mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp} \Pr[\exists \bm{X}'\in \mathbb{B}(\bm{X},\epsilon) \text{ s.t. }\textup{\textsf{sign}}(f(\bm{X}'))\not=Y| \bm{X}= \bm{x}] d \Pr\nolimits_{\bm{X}}(\bm{x})\&=\Pr(\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon))\&\quad +\int_{\mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp} [\mathbf{1}{\textup{\textsf{sign}}(f(\bm{x}))=-1}(2\eta(\bm{x})-1)+(1-\eta(\bm{x}))]d \Pr\nolimits_{\bm{X}}(\bm{x}).\end{split} $

We have

$ \begin{split}&\quad \mathcal{R}\mathrm{rob}(f)-\mathcal{R}\mathrm{nat}(f^*)\&=\Pr(\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon))+\int_{\mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp} [\mathbf{1}{\textup{\textsf{sign}}(f(\bm{x}))=-1}(2\eta(\bm{x})-1)+(1-\eta(\bm{x}))]d \Pr\nolimits_{\bm{X}}(\bm{x})\&\quad-\int_{\mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp} [\mathbf{1}{\textup{\textsf{sign}}(f^*(\bm{x}))=-1}(2\eta(\bm{x})-1)+(1-\eta(\bm{x}))]d \Pr\nolimits_{\bm{X}}(\bm{x})\&\quad-\int_{\mathbb{B}(\mathrm{DB}(f),\epsilon)} [\mathbf{1}{\textup{\textsf{sign}}(f^*(\bm{x}))=-1}(2\eta(\bm{x})-1)+(1-\eta(\bm{x}))]d \Pr\nolimits_{\bm{X}}(\bm{x})\&=\Pr(\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon))-\int_{\mathbb{B}(\mathrm{DB}(f),\epsilon)} [\mathbf{1}{\textup{\textsf{sign}}(f^*(\bm{x}))=-1}(2\eta(\bm{x})-1)+(1-\eta(\bm{x}))]d \Pr\nolimits_{\bm{X}}(\bm{x})\&\quad+\mathbb{E}[\mathbf{1}{\textup{\textsf{sign}}(f(\bm{X}))\not= \textup{\textsf{sign}}(\eta(\bm{X})-1/2), \bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp}|2\eta(\bm{X})-1|]\&=\Pr(\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon))-\mathbb{E}[\mathbf{1}{\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)}\min{\eta(\bm{X}),1-\eta(\bm{X})}]\&\quad+\mathbb{E}[\mathbf{1}{\textup{\textsf{sign}}(f(\bm{X}))\not= \textup{\textsf{sign}}(\eta(\bm{X})-1/2), \bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp}|2\eta(\bm{X})-1|]\&= \mathbb{E}[\mathbf{1}{\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)}\max{\eta(\bm{X}),1-\eta(\bm{X})}]\&\quad +\mathbb{E}[\mathbf{1}{\textup{\textsf{sign}}(f(\bm{X}))\not= \textup{\textsf{sign}}(\eta(\bm{X})-1/2), \bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp}|2\eta(\bm{X})-1|]\&=\Pr[\bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon), \textup{\textsf{sign}}(f^*(\bm{X}))=Y]\&\quad +\mathbb{E}[\mathbf{1}{\textup{\textsf{sign}}(f(\bm{X}))\not= \textup{\textsf{sign}}(f^*(\bm{X})), \bm{X}\in \mathbb{B}(\mathrm{DB}(f),\epsilon)^\perp}|2\eta(\bm{X})-1|].\end{split} $

D. Extra Experimental Results

In this section, we provide extra experimental results to verify the effectiveness of our proposed method TRADES.

D.1 Experimental setup in Section 5.3.1

We use the same model, i.e., the WRN-34-10 architecture in [44], to implement the methods in [33], [16] and [32]. The experimental setup is the same as TRADES, which is specified in the beginning of Section 5. For example, we use the same batch size and learning rate for all the methods. More specifically, we find that using one-step adversarial perturbation method like FGSM in the regularization term, defined in [16], cannot defend against FGSM$^k$ (white-box) attack. Therefore, we use FGSM$^k$ with the cross-entropy loss to calculate the adversarial example $\bm{X}'$ in the regularization term, and the perturbation step size $\eta_1$ and number of iterations $K$ are the same as in the beginning of Section 5.

As for defense models in Table 5, we implement the 'TRADES' models, the models trained by using other regularization losses in [16, 32, 33], and the defense model 'Madry' in the antepenultimate line of Table 5. We evaluate [29]'s model based on the checkpoint provided by the authors. The rest of the models in Table 5 are reported in [26].

D.2 Extra attack results in Section 5.3.1

Extra white-box attack results are provided in Table 8.

\begin{tabular}{c||c|c|c|c|c}
        \hline
        Defense & Under which attack & Dataset & Distance & $\mathcal{A}_\mathrm{nat}(f)$ & $\mathcal{A}_\mathrm{rob}(f)$  
        \\
        \hline
        {TRADES} ($1/\lambda=1.0$) & FGSM & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 56.38\% \\
        {TRADES} ($1/\lambda=1.0$) & DeepFool ($\ell_2$) & CIFAR10 & $0.031$ ($\ell_\infty$) & 88.64\% & 84.49\% \\
        \hline
        {TRADES} ($1/\lambda=6.0$) & FGSM & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & 61.06\% \\
        {TRADES} ($1/\lambda=6.0$) & DeepFool ($\ell_2$) & CIFAR10 & $0.031$ ($\ell_\infty$) & 84.92\% & 81.55\% \\
        \hline
    \end{tabular}

The attacks in Table 5 and Table 8 include FGSM$^k$ [16], DeepFool ($\ell_\infty$) [64], LBFGSAttack [56], MI-FGSM [55], C&W [43], FGSM [16], and DeepFool ($\ell_2$) [64].

D.3 Extra attack results in Section 5.3.2

Extra black-box attack results are provided in Table 9 and Table 10. We apply black-box FGSM attack on the MNIST dataset and the CIFAR10 dataset.

\begin{tabular}{c||c|c}
        \hline
        Defense Model & \multicolumn{2}{c}{Robust Accuracy $\mathcal{A}_\mathrm{rob}(f)$}
        \\
        \hline
        {Madry} & 97.68\% (Natural) & 98.11\% (Ours) \\ 
        \hline
        {TRADES} & \textbf{97.75\%} (Natural) & \textbf{98.44\%} (Madry) \\
        \hline
    \end{tabular}

\begin{tabular}{c||c|c}
        \hline
        Defense Model & \multicolumn{2}{c}{Robust Accuracy $\mathcal{A}_\mathrm{rob}(f)$}
        \\
        \hline
        {Madry} & 84.02\% (Natural) & 67.66\% (Ours) \\ 
        \hline
        {TRADES} & \textbf{86.84\%} (Natural) & \textbf{71.52}\% (Madry) \\
        \hline
    \end{tabular}

D.4 Experimental setup in Section 5.3.2

The robust accuracy of [19]'s CNN model is $96.01%$ on the MNIST dataset. The robust accuracy of [19]'s WRN-34-10 model is $47.66%$ on the CIFAR10 dataset. Note that we use the same white-box attack method introduced in the Section 5.3.1, i.e., FGSM$^{20}$, to evaluate the robust accuracies of Madry's models.

D.5 Interpretability of the robust models trained by TRADES

D.5.1 Adversarial examples on MNIST and CIFAR10 datasets

In this section, we provide adversarial examples on MNIST and CIFAR10. We apply foolbox[^3] [65] to generate adversarial examples, which is able to return the smallest adversarial perturbations under the $\ell_\infty$ norm distance. The adversarial examples are generated by using FGSM$^{k}$ (white-box) attack on the models described in Section 5, including $\textit{Natural}$ models, $\textit{Madry}

[^3]: Link: https://foolbox.readthedocs.io/en/latest/index.html

D.5.2 Adversarial examples on Bird-or-Bicycle dataset

We find that the robust models trained by TRADES have strong interpretability. To see this, we apply a (spatial-tranformation-invariant) version of TRADES to train ResNet-50 models in response to the unrestricted adversarial examples of the bird-or-bicycle dataset [8]. The dataset is bird-or-bicycle, which consists of 30, 000 pixel-$224\times 224$ images with label either 'bird' or 'bicycle'. The unrestricted threat models include structural perturbations, rotations, translations, resizing, 17+ common corruptions, etc.

We show in Figure 7 and Figure 8 the adversarial examples by the boundary attack with random spatial transformation on our robust model trained by the variant of TRADES. The boundary attack [66] is a black-box attack method which searches for data points near the decision boundary and attack robust models by these data points. Therefore, the adversarial images obtained by boundary attack characterize the images around the decision boundary of robust models. We attack our model by boundary attack with random spatial transformations, a baseline in the competition. The classification accuracy on the adversarial test data is as high as $95%$ (at $80%$ coverage), even though the adversarial corruptions are perceptible to human. We observe that the robust model trained by TRADES has strong interpretability: in Figure 7 all of adversarial images have obvious feature of 'bird', while in Figure 8 all of adversarial images have obvious feature of 'bicycle'. This shows that images around the decision boundary of truly robust model have features of both classes.

References

Section Summary: The references section compiles a list of academic papers mostly published between 2013 and 2019 that investigate how small, often imperceptible changes can trick neural networks into making errors. Many entries explore both the creation of these adversarial examples across tasks like image classification and language understanding, as well as proposed defenses such as training modifications or mathematical guarantees of robustness. Additional works analyze theoretical trade-offs, including whether greater security necessarily reduces a model's accuracy on normal data.

[1] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.

[2] Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv:1702.02284, 2017.

[3] Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. In International Conference on Learning Representations, 2018.

[4] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan Yuille. Adversarial examples for semantic segmentation and object detection. In International Conference on Computer Vision, 2017.

[5] Dongyu Meng and Hao Chen. Magnet: a two-pronged defense against adversarial examples. In ACM SIGSAC Conference on Computer and Communications Security, pages 135–147, 2017.

[6] Robin Jia and Percy Liang. Adversarial examples for evaluating reading comprehension systems. In Empirical Methods in Natural Language Processing, 2017.

[7] Warren He, James Wei, Xinyun Chen, Nicholas Carlini, and Dawn Song. Adversarial example defenses: Ensembles of weak defenses are not strong. arXiv preprint arXiv:1706.04701, 2017.

[8] Tom B Brown, Nicholas Carlini, Chiyuan Zhang, Catherine Olsson, Paul Christiano, and Ian Goodfellow. Unrestricted adversarial examples. arXiv preprint arXiv:1809.08352, 2018.

[9] Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. A rotation and a translation suffice: Fooling CNNs with simple transformations. arXiv preprint arXiv:1712.02779, 2017.

[10] Justin Gilmer, Ryan P Adams, Ian Goodfellow, David Andersen, and George E Dahl. Motivating the rules of the game for adversarial example research. arXiv preprint arXiv:1807.06732, 2018.

[11] Chaowei Xiao, Jun-Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. In International Conference on Learning Representations, 2018.

[12] Rima Alaifari, Giovanni S Alberti, and Tandri Gauksson. ADef: an iterative algorithm to construct adversarial deformations. In International Conference on Learning Representations, 2019.

[13] Huan Zhang, Hongge Chen, Zhao Song, Duane Boning, Inderjit S Dhillon, and Cho-Jui Hsieh. The limitations of adversarial training and the blind-spot attack. In International Conference on Learning Representations, 2019.

[14] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representations, 2019.

[15] Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin-Yu Chen, and Yupeng Gao. Is robustness the cost of accuracy? — a comprehensive study on the robustness of 18 deep image classification models. In European Conference on Computer Vision, 2018.

[16] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017.

[17] J Zico Kolter and Eric Wong. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, 2018.

[18] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018.

[19] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.

[20] Jonathan Uesato, Brendan O'Donoghue, Pushmeet Kohli, and Aaron van den Oord. Adversarial risk and the dangers of evaluating against weak attacks. In International Conference on Machine Learning, pages 5025–5034, 2018.

[21] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Mądry. Adversarially robust generalization requires more data. In Advances in Neural Information Processing Systems 31, pages 5019–5031, 2018.

[22] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. PAC-learning in the presence of adversaries. In Advances in Neural Information Processing Systems, pages 228–239, 2018.

[23] Dong Yin, Kannan Ramchandran, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. arXiv preprint arXiv:1810.11914, 2018.

[24] Sébastien Bubeck, Eric Price, and Ilya Razenshteyn. Adversarial examples from computational constraints. arXiv preprint arXiv:1805.10204, 2018.

[25] Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. Adversarial examples from cryptographic pseudo-random generators. arXiv preprint arXiv:1811.06418, 2018.

[26] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, 2018.

[27] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138–156, 2006.

[28] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, 2017.

[29] E Wong, F Schmidt, JH Metzen, and JZ Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, 2018.

[30] Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pages 10899–10909, 2018.

[31] Takeru Miyato, Shin-ichi Maeda, Shin Ishii, and Masanori Koyama. Virtual adversarial training: a regularization method for supervised and semi-supervised learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018.

[32] Andrew Slavin Ross and Finale Doshi-Velez. Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. arXiv preprint arXiv:1711.09404, 2017.

[33] Stephan Zheng, Yang Song, Thomas Leung, and Ian Goodfellow. Improving the robustness of deep neural networks via stability training. In IEEE Conference on Computer Vision and Pattern Recognition, pages 4480–4488, 2016.

[34] Harini Kannan, Alexey Kurakin, and Ian Goodfellow. Adversarial logit pairing. arXiv preprint arXiv:1803.06373, 2018.

[35] Logan Engstrom, Andrew Ilyas, and Anish Athalye. Evaluating and understanding the robustness of adversarial logit pairing. arXiv preprint arXiv:1807.10272, 2018.

[36] Bernardo Ávila Pires and Csaba Szepesvári. Multiclass classification calibration functions. arXiv preprint arXiv:1609.06385, 2016.

[37] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data improves adversarial robustness. arXiv preprint arXiv:1905.13736, 2019.

[38] Robert Stanforth, Alhussein Fawzi, Pushmeet Kohli, et al. Are labels required for improving adversarial robustness? arXiv preprint arXiv:1905.13725, 2019.

[39] Runtian Zhai, Tianle Cai, Di He, Chen Dan, Kun He, John Hopcroft, and Liwei Wang. Adversarially robust generalization just requires more unlabeled data. arXiv preprint arXiv:1906.00555, 2019.

[40] Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint arXiv:1904.12843, 2019.

[41] Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. arXiv preprint arXiv:1905.00877, 2019.

[42] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.

[43] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy, pages 39–57, 2017.

[44] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference, 2016.

[45] Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan: Protecting classifiers against adversarial attacks using generative models. arXiv preprint arXiv:1805.06605, 2018.

[46] Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In International Conference on Learning Representations, 2018.

[47] Xingjun Ma, Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Michael E Houle, Grant Schoenebeck, Dawn Song, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. arXiv preprint arXiv:1801.02613, 2018.

[48] Guneet S Dhillon, Kamyar Azizzadenesheli, Zachary C Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial defense. arXiv preprint arXiv:1803.01442, 2018.

[49] Taesik Na, Jong Hwan Ko, and Saibal Mukhopadhyay. Cascade adversarial machine learning regularized with a unified embedding. arXiv preprint arXiv:1708.02582, 2017.

[50] Cihang Xie, Yuxin Wu, Laurens van der Maaten, Alan Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. arXiv preprint arXiv:1812.03411, 2018.

[51] Hongyang Zhang, Junru Shao, and Ruslan Salakhutdinov. Deep neural networks with multi-branch architectures are intrinsically less non-convex. In International Conference on Artificial Intelligence and Statistics, pages 1099–1109, 2019.

[52] Hongyang Zhang, Susu Xu, Jiantao Jiao, Pengtao Xie, Ruslan Salakhutdinov, and Eric P Xing. Stackelberg GAN: Towards provable minimax equilibrium via multi-generator architectures. arXiv preprint arXiv:1811.08010, 2018.

[53] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.

[54] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. In International Conference on Learning Representations, 2018.

[55] Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. In IEEE Conference on Computer Vision and Pattern Recognition, pages 9185–9193, 2018.

[56] Pedro Tabacof and Eduardo Valle. Exploring the space of adversarial images. In International Joint Conference on Neural Networks, pages 426–433, 2016.

[57] Ruitong Huang, Bing Xu, Dale Schuurmans, and Csaba Szepesvári. Learning with a strong adversary. arXiv preprint arXiv:1511.03034, 2015.

[58] Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial training: Increasing local stability of neural nets through robust optimization. arXiv preprint arXiv:1511.05432, 2015.

[59] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.

[60] Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John C Duchi, Vittorio Murino, and Silvio Savarese. Generalizing to unseen domains via adversarial data augmentation. In Advances in Neural Information Processing Systems, pages 5339–5349, 2018.

[61] Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier. In Advances in Neural Information Processing Systems, pages 1186–1195, 2018.

[62] Franck Barthe. Extremal properties of central half-spaces for product measures. Journal of Functional Analysis, 182(1):81–107, 2001.

[63] Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2:527–550, 2002.

[64] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In IEEE Conference on Computer Vision and Pattern Recognition, pages 2574–2582, 2016.

[65] Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox v0. 8.0: A python toolbox to benchmark the robustness of machine learning models. arXiv preprint arXiv:1707.04131, 2017.

[66] Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. In International Conference on Learning Representations, 2018.