Adversarial Robustness with Semi-Infinite Constrained Learning
Authors: Alexander Robey
Luiz F. O. Chamon
George J. Pappas
Hamed Hassani
Alejandro Ribeiro
Venue: NeurIPS 2021 Poster (2021)
Keywords: Robust learning
adversarial robustness
constrained learning
semi-infinite programming

Abstract: Despite strong performance in numerous applications, the fragility of deep learning to input perturbations has raised serious questions about its use in safety-critical domains.  While adversarial training can mitigate this issue in practice, state-of-the-art methods are increasingly application-dependent, heuristic in nature, and suffer from fundamental trade-offs between nominal performance and robustness. Moreover, the problem of finding worst-case perturbations is non-convex and underparameterized, both of which engender a non-favorable optimization landscape. Thus, there is a gap between the theory and practice of robust learning, particularly with respect to when and why adversarial training works.  In this paper, we take a constrained learning approach to address these questions and to provide a theoretical foundation for robust learning. In particular, we leverage semi-infinite optimization and non-convex duality theory to show that adversarial training is equivalent to a statistical problem over perturbation distributions. Notably, we show that a myriad of previous robust training techniques can be recovered for particular, sub-optimal choices of these distributions. Using these insights, we then propose a hybrid Langevin Markov Chain Monte Carlo approach for which several common algorithms (e.g., PGD) are special cases. Finally, we show that our approach can mitigate the trade-off between nominal and robust performance, yielding state-of-the-art results on MNIST and CIFAR-10.  Our code is available at: https://github.com/arobey1/advbench.

Adversarial Robustness with Semi-Infinite Constrained Learning
Alexander Robey"
Luiz F. Chamon" University of California, Berkeley LfochamonCberkeley edu
University of Pennsylvania arobey1@sean 1eeas. upenn. edu
George J. Pappas University of Pennsylvania pappasgSseas upenn. edu
Hamed Hassani University of Pennsylvania hassani@seas upenn. edu
Alejandro Ribeiro
University of Pennsylvania aribeiro@seas upenn edu
Abstract
Despite strong performance in numerous applications, the fragility of deep learning to input perturbations has raised serious questions about its use in safety-critical domains. While adversarial training can mitigate this issue in practice, state-of- the-art methods are increasingly suffer from fundamental trade-off's between nominal performance and robustness. Moreover, the problem of finding worst-case perturbations is non-convex and underparameterized. both of which engender non-favorable optimization land- scape. Thus, there is gap between the theory and practice of adversarial training, particularly with respect to when and why adversarial training works. In this pa- per, we take a constrained learning approach to address these questions and to provide a theoretical foundation for robust learning. In particular, we leverage semi-infinite optimization and non-convex duality theory show that adversarial training equivalent statistical problem over perturbation distributions, which characterize completely. Notably, we show that myriad of previous robust training techniques can be recovered for particular, sub-optimal choices of these distributions. Using these insights, we then propose hybrid Langevin Monte Carlo approach of which several common algorithms (e.g., PGD) are special cases. Finally, show that approach can mitigate the trade-off between nominal and robust performance, yielding state-of of-the-art results on MNIST and CIFAR-10. Our code is available https:// thub. hww.bb..o//orbbb//aeeeeaee advvbench
pepiicatioo-dppnneeee heuristic in nature, and
Introduction
Learning is at the core of many modern information systems, with wide-ranging applications in clinical research [144] smart grids (5-7), and robotics [8 However, it has become clear that learning-based solutions suffer from a critical lack of robustness [1177), leading to models that are vulnerable malicious tampering and unsafe behavior 18 While robustness has been
studied in statistics for decades [53, this issue has been exacerbated by the opacity, scale, and non-convexity of modern learning models, such as convolutional neural network (CNNs). Indeed, the pernicious nature of these vulnerabilities has led to rapidly-growing the so-called adversarial robustness of modern MI. models. To this end, a great deal of empirical evidence has shown adversarial training to be the most effective way to obtain robust classifiers, wherein models are trained on perturbed samples rather than directly on clean data [11 While this approach is now ubiquitous in practice, adversarial training faces two fundamental challenges.
interest in improving
Alexander Robey and Luiz F. O. Chamon contributed equally to this work.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Firstly, it is well-known that obtaining worst-case. adversarial perturbations of data is challenging in the context of deep neural networks (DNNss [2 33]. While gradient- based methods have been shown to be empirically effective at finding perturbations that lead to misclassification, there are no guarantees that these perturbations are truly worst-case due to the non-convexity of most commonly- used MI. function classes [34.. Moreover, whereas optimizing the parameters of a DNNs is typically an overparameterized problem. finding worst-case perturbations is severely underparametrized and therefore does not enjoy the benign optimization landscape of standard training (35,39]. For this rea- son, state-of-the-a adversarial attacks increasingly rely on heuristics such as random initializations, multiple restarts, pruning, and other ad hoc training procedures 40 49
The second challenge faced by adversarial training is that it engenders fundamental trade-off between robustness and nominal performance [50 52]. In practice, penalty- based methods that incorporate clean data into the training objective are often used to overcome this issue (53)56). However, while empirically successful, these methods cannot typically guarantee nominal or adversarial performance outside of the training samples. Indeed, classical learning theory [57] 58 provides generalization bounds only for the aggregated objective and not each individual penalty term. Additionally, the choice of the penalty parameter is not straightforward and depends on the underlying learning task, making it difficult to transfer across applications and highly dependent on domain expert knowledge.
Contributions. To summarize, there is a significant gap between the theory and practice of robust learning, particularly with respect to when and why adversarial training works. In this paper, we study the algorithmic foundations of robust learning toward understanding the fundamental limits of adversarial training. To do so, we leverage semi-infinite constrained learning theory, providing a theoretical foundation for gradient- attacks and mitigating the issue of nominal performance degradation. In particular, our contributions are as follows:
We show that adversarial training is equivalent to a stochastic optimization problem over specific, non-atomic distribution, which we characterize using recent non-convex duality results 59 60). Further, we show that a myriad of previous adversarial attacks reduce to particular, sub-optimal choices of this distribution.
We propose an algorithm to solve this problem based on stochastic optimization and Markov chain Monte Carlo. Gradient-based methods can be seen as limiting cases of this procedure. We show that our algorithm outperforms ofte--of-the-at baselines on MNIST and CIFAR- 10. In particular, our approach yields ResNet-18 classifiers which simultaneously achieves greater than 50% adversarial accuracy and greater than 85% clean accuracy on CIFAR-10 -00, which represents a significant improvement over the previous state-of-the-art. We provide generalization guarantees for the empirical version of this algorithm, showing how to effectively limit the nominal performance degradation of robust classifiers.
2 Problem formulation
Throughout this paper, we consider a standard classification setting in which the data is distributed according to an unknown joint distribution D over instance-label pairs (x, v). In this setting, the instances X E X' are assumed to be supported on a compact subset of R and each label y E y :=
(1...., K} denotes the class of given instance x. By (S, B) we denote the underlying measurable space for this setting, where Ω = X' x y and B denotes its Borel alagebrr.. Furthermore, we assume that the joint distribution D admits density p( (X, y) defined over the sets of B.
At a high level, our goal is to learn a classifier which can correctly predict the label y of corre- sponding instance x. To this end, we let H be hypothesis class containing functions fe Ed - S parameterized by vectors 0 E θ C IR,, where we assume that the parameter space θ is compact and by SK we denote the (K- - 1) -immipee.. We also assume that (x) is differentiable with respect to 0 and x To make a prediction ì E Y, we assume that the simplex S is mapped to the set of classes ) via i E argmax,gy [ffe [x)] with ties broken arbitrarily. In this way, can think of the k-th output of the classifier as representing the probability that y = k. Given this notation, the statistical problem of learning classifier that accurately predicts the label y of given instance
Note that the classes of support vector machines, logistic classifiers, and convolutional neural networks (CNNs) with softmax outputs can all be described by this formalism.

---

drawn randomly from D can be formulated as follows:
min E (xx))>> [e(fo(x). 0
(P-NOM)
Here e is a [0, B--vuleed loss function and ((,, y) is M M-Lipschitz continuous for all E V. We assume that (x,y) + (fo(x); (x), y) is integrable so that the objective in (P-NOM) is well-defined; we further assume that this map is an element of the Lebgesgue space (2 B, p) for some fixed p E (1, (1).
Formulating the robust training objective. For common choices of the hypothesis class H. including DNNs, classifiers obtained by solving (-NOM are known be sensitive to small, norm- bounded imput perturbations [6]]. In other words, it is often straightforward to find relatively small perturbations 6 such that the classifier correctly predicts the label y of x. but misclassifies the
perturbed sample x + 8. This has led to increased interest in the robust analog of (P-NOM), namely,
PR a min B(x.)) OEG
max ( + +6), BEA
(P-RO)
In this optimization program, the set A C Fd denotes the set of valid perturbations" Typically, A is chosen to be a ball with respect given metric on Euclidean space, i.e.. A = {0 R || S e}. However, in this paper we make no particular assumption on the specific form of A. In particular, our results apply to arbitrary perturbation sets, such as those used in 66]
Analyzing conditions under which (P-RO) can be (probably approximately) solved from data re- mains an active area of research. While bounds on the Rademacher complexity [67 68) and VC dimension 667-7] of the robust loss
(ad (fo(x) = max (fo(x + 5). SEA
have been derived for array of losses E and hypothesis classes H. there are still open questions on the effectiveness and sample complexity of adversarial learning [68]. Moreover, because in general the map 5 + ( + 8), y) is non-concave, evaluating the maximum in (T) is not straightforward. To this end, the most empirically effective strategy for approximating the robust loss is to leverage the differentiability of modern MI models with respect their inputs. More specifically, by computing gradients of such models, one can approximate the value of (T) using projected gradient ascent. For instance, in [27 722 perturbation ō is computed for fixed parameter O and data point (x, y) by repeatedly applying
8 8 I1 - n ssgn [V&
(2)
where A denotes the projection onto A and 17 > 0 is fixed step size. This idea is at the heart of adversarial training, which (2) is iteratively applied to approximately evaluate the robust risk the objective of (P-RO): the parameters & can then be optimized with respect to this robust risk.
Common pitfalls for adversarial training. Their empirical success notwithstanding, gradient-bass based approaches to adversarial training are not without draks One pitfall is the fact that gradient-basee -based algorithms are not guaranteed to provide optimal (or even near-optimal) perturbations, since x H> (x). y) is typically not concave function. Because of this, heuristics [73] 74] are often needed to improve the solutions obtained from 22) Furthermore, adversarial training often degrades the
performance of the model on clean data (52 (7] (6). In practice, renalty-based approaches are used to empirically overcome this issue (53 although results are not guaranteed to generalize outside
of the training sample. Indeed, classical learning theory guarantees generalization in terms of the
aggregated objective and not in terms of the robustness requirements may describe [57] 58 60).
In the remainder of this paper, we address these pitfalls by leveraging semi-infinite constrained learn- ing theory. To do so, we explicitly formulate the problem of finding the most robust classifier among those that have good nominal performance. Next, we show that (P-RO) is equivalent to a stochastic optimization problem that can be related to numerous adversarial training methods (Section 33). We then provide generalization guarantees for the constrained robust learning problem when solve using empirical (unconstrained) risk minimization (Section D Finally, we derive an algorithm based on a Langevin MCMC sampler of which (2) is particular case (Section 5)..
Note that fe must now be defined on X' @ A, where @ denotes the Minkowski (set) sum. In slight abuse of uotation, will refer to this as X' from now on.
3

---

Dual robust learning
In the previous section, we argued that while empirically successful, adversarial training is not without shortcomings. In this section, we develop the theoretical foundations needed to tackle the two challenges of (P-RO): : (a) finding worst-case perturbations, i... evaluating the robust loss defined in (T) and (b) mitigating the trade-off between robustness and nominal performance. To address these challenges, we first propose the following constrained optimization problem which explicitly captures the trade-off between robustness and nominal performance:
p min BE0 subject to
E (xxy))>
max ((o(( + +)),)) BEA
(P-CON)
(xx,)) [<(Jo(x),u) sp
where p 2 0 is desired nominal performance level. At a high level, (P-CON) seeks the most robust classifier (-) among those classifiers that have strong nominal performance. In this way, (P-CON) directly designed address the trade-off between robustness and accuracy, and as such PP-CON will be the central object of study in this paper. We note that at face value, the statistical constraint in (P-CON) is challenging to enforce in practice, especially given the well- known difficulty in solving the unconstrained analog (P-RO). Following [60] [77). our approach is to use duality to obtain solutions for (P-CON) that generalize with respect both adversarial and nominal performance.
Computing worst-case perturbations. Before tackling the constrained problem P-CCON. we
begin by consider its unconstrained version, namely, (P-RO). We start by rewriting (P-RO) using epigraph formulation of the maximum function to obtain the following semi-infinite program:
PK
min 10
[x [[xx
(PI)
subject to {(f((x + 8),0) S v(x,y),
for almost every (x.8,y) X x x
Note that PI is indeed equivalent P-RO since
max SEA
(fo(x + 0). < ((x,g)
{(Jo(x + 6),8) = ((x,y) for all ò E A
(3)
While at first it may seem that we have made (P-CON) more challenging to solve by transforming
an unconstrained problem into an anfnitely-constraimee
problem, notice that (P] is no longer
composite minimax problem. Furthermore, it is linear in t. indicating that (PI) should be amenable
to approaches based on Lagrangian duality. Indeed, the following proposition shows that (1) can be used to obtain a statistical counterpart of (P-RO).
Proposition 3.1. If (x, v) + (foo()) v) E L" for p E (1, then P P-RO can be written as
P = min p(0),
(PII)
for the primal function
p()) A max (xxx)DD [ 50,
(4)
XEP;
where p9, with 1+1 1, is the subspace of L containing almost everywhere non-negative functions
p
such that p(x. v) 0 X(5 x, v) 0 and 2(5 x, y) for almost every (x.y) E X y
The proof is provided in Appendix B Informally, Proposition 3.1 shows that the robust learning problem in (P-RO) can be recast as problem of optimizing over set of probability distributions 1e taking support over A. This establishes an equivalence between the traditional robust learning problem P-R where the maximum is taken over perturbations ô E A of the input, and its stochastic version (II), where the maximum is taken over a conditional distribution over perturbations 5 ~ X(0)x x. y). Notably, variety of training formulations can be for particular sub-optimal choices of this distribution, paradigms such as random data augmentation and distributionally robust optimization
special cases of (PI). In fact,
be recovered (see Appendix for details).
As we remarked in Section 2 for many modern function classes, the task of evaluating the adversarial loss is nonconcave optimization problem, which is challenging to solve in general. Thus,

---

Proposition 3.1 can be seen as lifting the nonconeave inner problem maXiEa (x), y) to the equivalent linear optimization problem in 4 over probability distributions X E P This dichotomy parallels the one that arises in PAC vs. agnostic PAC learning. Indeed, while the former seeks deterministic map (0, x, y) + 6, the latter considers instead distribution of perturbations over 8|x, y parametrized by 0. In fact, since (PIT) is obtained from (P-RO) through semi-infiiite duality, the density of this distribution is exactly characterized by the dual variables X.
Note that while (PI)) was obtained using Lagrangian duality, it can also be seen as linear lifting of the maximization in ①T. From this perspective, while recovering (I] would require À to be atomic, Proposition 3.1 shows that this is not necessary as long as (ffe (x.y) is an element of L". That is, because pd does not contain any Dirac distributions, the optimal distribution A for the maximization problem in 4 is non-atomic Hence, Proposition does not show that (PI)) finds worst-case perturbations that achieve the maximum in the objective of (P-RO). It does, however, show that finding worst-case perturbation is not essential to find a solution of (P-RO)
Exact solutions for the maximization in (II.. While (II provides new constrained formulation for (P-RO), the objectives of both (PII) and (P-RO) still involve the solution of a non-trivial maximiza- tion. However, whereas the maximization problem in (P-RO) is finiteddimensional problem which is nonconcave for most modern function classes, the maximization in (PII) is a linear, variational problem regardless of the function class. We can therefore leverage variational duality theory to obtain a full characterization of the optimal distribution X when 2.
Proposition 3.2 (Optimal distribution for (PII). Let 2 (and q = 2) in Proposition 3. and let [z]+ max(0, z). For each (x.y) y) E Q there exists constants 7 [x. y) and μ(x. y) K s.t.
((fo(x 5), -(x, y)
X (6 x) v)
(5)
7(x,9) y)
is a solution of the maximization in + -))
In particular, the value of μ(x, y) is such that
/ (((f(((+)))
- p(x, w)}+ dō x)x,)) ( x
(6)
The proof is provided in Appendix C. This proposition shows that when (x, y) + l (fo (x). L2 we can obtain a closed-form expression for the distribution X that maximizes the objective of (PI). Moreover, this distribution proportional to truncated version of the loss of the classifier. Note that the assumption that the loss belongs to I is mild given that the compactness of X, y. and A imply that L L for P1 > P2. It is. however, fundamental to obtain the closed-form solution in Proposition 3.2 since it allows 4 to be formulated as strongly convex constrained problem whose primal solution (5) can be recovered from its dual variables (namely, Y and p). To illustrate this result, we consider two particular suboptimal choices for the constants f and 7y
Special case I: over-smoothed X Consider the case when 7(x, y) is taken to be the normalizing constant SA {.fe (x ++), y) for each (x, y) E Ω. As the loss function é is non-negative, (6) implies that pxx, 3) = 0, and the distribution defined in (5) can be written as
E(fo (x + 6), v) 1(8)x, y) SA efo(x + v),
(7)
meaning that \(0)x, y) is exactly proportional to the loss { xx 8),v) on perturbed copy of the data. Thus, for this choice of y and μr, the distribution À in (7) is an over-smoothed version of the optimal distribution X" In our experiments, we will use this over-smoothed approximation of X" to derive an MCMC-style sampler, which yields state-of-the art performance on standard benchmarks.
Special case I: under-smoothed X* is also of interest to consider the case in which approaches zero. In the proof of Proposition 3.2. we show that the value of μ is fully determined by y and that y is directly related to the smoothness of the optimal distribution; in fact, 7 is equivalent to a bound on the 1,2 norm of X* In this way, as take y zero, find that μ approaches max8e A ((fo + 8). meaning that the distribution is truncated so that mass is only placed on those perturbations 8 which induce the maximum loss. Thus, in the limit, À approaches an atomic distribution concentrated
3 Prropssition 3.1 does not account for p E (l) for conciseness. Nevertheless, neither of the dual spaces L L contain Dirac distributions, meaning that for p (0) X would remain non-atomic.
5

---

entirely at a perturbation 8* that maximizes the loss. Interestingly. this is the same distribution that would be needed to recover the solution to the inner maximization as in (P-RO). This highlights the fact that although recovering the optimal 5* in (P-CON) would require A to be atomic, the condition that y > O means that X need not be atomic.
These two cases illustrate the fundamental difference between P-RO and (III:: Whereas in (P-RO) we search for worst-case perturbations, in (PII) we seek method sample perturbations ô from the perturbation distribution X Thus, given method for sampling ó ~ A (0]xx x, 2). the max in (P-RO)
can be replaced by an expectation, allowing us consider the following optimization problem:
PR
min ((x.)) (8)x.)))) (x + 6, y)] o0
(PIII)
Notice that crucially this problem is non-composite in the sense that it no longer contains an inner maximization. To this end, in Section [
we propose scheme that can be used sample from close approximation of X* toward evaluating the inner expectation in (PIII.
4 Solving the constrained learning problem
So far, we have argued that (P-CON) captures the problem of finding the most robust model with high nominal performance and we have shown the the minimax objective of (P-CON) can be rewritten as stochastic optimization problem over perturbation distributions. this section, we address the distinct yet related issue of satisfying the constraint in (P-CON). which is challenging task in practice given the statistical and potentially non-convex nature of the problem. Further complicating matters the fact that by assumption we have access to the data distribution D only through samples (x, y) D, which means that in practice we cannot evaluate either of the expectations in (P-CON). To overcome these obstacles, given a dataset {(x.; No) J sampled i.i.d. from D, our approach is to use duality to approximate (P-CON) by the following empirical, unconstrained saddle point problem
D max min =20 AEE N
1
Σ
max (ff(xx, + 5), vn) + [e(fo(xn)) - e] GEA
(DI)
Conditions under which solutions of Di are (probably approximately) near-optimal and near-feasible for (P-CON) were obtained in (60 As one would expect, these guarantees only hold when the
objective and constraint of (P-CON) are learnable individually. As we discussed in Section this is known to hold variety of scenarios (e.g., when the Rademacher complexity or VC-dimension is bounded), although obtaining more general results remains area of active research (67 In what follows, we formalize these generalization results in our setting, starting with the learning theoretic assumptions we require on the objective and constraint.
Learning theoretic assumptions for (-CON). We first assume that the parameterization space θ is sufficiently expressive (A (Assumption 4.1 and that there exists parameters O E θ that strictly satisfy the nominal performance constraint (Assumption 4.2) We also assume that uniform convergence
holds for the objective and constraint (Assumption 4.3
Assumption 4.1. The parametrization fe is rich enough so that for each 0,, O2 E O and $ E [0, 1], there exists 0 θ such that supxex fā (a) + (1- f1- (x) fo (z) S a.
Assumption 4.2. There exists 0' E θ such that Ep (x) v)] < Ma. Assumption 4.3. There exists ÇR (R(NN, (N(N 2 monotonically decreasing in N such that v0 θ:
N
1
E m. ( max (ff(xx ( 0), BEA
max (z +5), (8, ym) SEA
$ <R(NN) w.p. 1 1 (8a)
N
E
Σ {(fo(xn)) Vn)
S (NN w.p. 1 (8b)
N
One natural question to ask is whether the bounds in 8al and 8b hold in practice. We note that in the non-adversarial bound (8b) has been shown to hold for a wide variety of hypothesis classes, including DNNs [78 58). And although these classical results do not imply the robust uniform

---

Algorithm Semi-Infinite Dual Adversarial Learning (DALE)
Initialize 0 < On and <- 0
1: repeat
2: for Batch {(x; y1) 9:)) 1mm do
,,...,77 4: for steps do
3:
ò; 4 0, for i
5:
U; - log
pen (xo + 5:), for E [mi] == fl,....m. m
6:
8, I
ô, 1 sign
Vo,Us U + 22nI'E where & Laplace(O,1), Vi E [m]
7:
end for
m
8:
Up
Vo lo (fo(x; + o:), vi) veo (fo(x;), yi)]
m
9:
end for
(fo((x))) -p) -p)
+ Nld
until convergence
convergence property (a). there is a growing body of evidence which suggests that this property
does fact hold for the function class of DNNs 668 79 80].
Near-optimality and near-feasibility of DI. By combining these assumptions with the techniques used in [60], we can explicitly bound the empirical duality gap (with high probability) and characterize the feasibility of the empircal dual optimal solution for (P-CON).
Proposition 4.4 (The empirical dual of (P-CON).. ). Let ((r.y) be convex function for all y y it holds with probability 55 that
Under Assumptions 4. 4.3
1. 1 D < Ma + (1 max((
and
2. There exists 01 argminnge L(0,0*) such that B(xy)~ [E( (x), Sp CN(N).
Here, i* denotes solution of Dip. v* denotes an optimal dual variable of (P-CON) solved over H. conv(H) instead of H. and classifier O', i.e. such that B(x.))D (x)r(()) 0, it holds that
maxx(D">0 v²). Additionally, for any interpolating
v² S P (X
max {(fo (x + +)) SEA
The proof is provided in Appendix
high level, Proposition 4.4ttells us that is possible to learn robust models with high clean accuracy using the empirical dual problem in (DI) at little cost to the sample complexity. This means that seeking robust classifier with given nominal performance is (probably approximately) equivalent to seeking a classifier that minimizes a combination of the nominal and adversarial empirical loss. Notably, the majority of past approaches for solving (P-CON) cannot be endowed with similar guarantees the spirit resembles a cenalty-basedd formulation. notice that is optimization variable rather than fixed hyperparameter. Concretely, the magnitude of this dual variable v quantifies how hard it is to learn an adversarially robust model while maintaining strong nominal performance. Though seemingly innocuous, this caveat is the difference between guaranteeing generalization only on the aggregated loss and guaranteeing generalization jointly for the objective value and constraint feasibility.
Proposition[4.4 Indeed, while the objective
Dual robust learning algorithm
Under the mild assumption that (x, v) + (xfo y) E L?,, Propositions 3.1 3.2 and 4.4 allow us to transform (P-CON) into the following Dual Adversarial LEannnng problem
D* A max min
Es. [e(So(xn + 8n), vn)) + (
(P-DALE)
20 OEG
N
7

---

PGD
FGSM
DALE
2.5
2.5
2.5
0.0
0.0
0.0
-2.5
-2.5
-2.5
2.5 0.0 2.5
-2.5 0.0 2.5
-25 0.0 2.5
Figure 1: Visualizing the distribution of adversarial perturbations. In this figure, we visualize the distribution of adversarial perturbations by projecting the perturbations generated by PGD, FGSM, and DALE onto their first two principal components. The first and second principal components are shown on the x- and y-axes respectively. Notice that DALE varies much less along the second principal component vis-a-vis PGD and FGSM; this indicates that DALE tends to focus more on directions in which the data varies most, indicating that it finds stronger adversarial perturbations.
where 8, ~ := [e(fo(( + 5,), Un) Mn.. for each {l..... N} and 7n and yon are the constants specified in Proposition 3.2 Note that this formulation considerably more amenable than (P-CON). Indeed, it is (i) empirical and therefore does not involve unknown statistical quantities such as D; (ii) unconstrained and therefore more amendable to gradient-baal techniques; and (iii) its objective does not involve a challenging maximization problem view of the closed-form characterization of X in Proposition 3.2 fact, for models that are linear but nonlinear in the input (e.g., kernel models logistic regression), this implies that we can transform non-convex, composite optimization problem (P-CON) into a convex problem P-DALE
optimization
remains a non-conver program in 0. And while there overwhelming theoretical and empirical evidence that stochastic gradient- based al algorithms yield good local minimizers for such overparametrizer problems 39 the fact remains that solving (P-DALE) requires us to evaluate an expectation with respect to X which is challenging due the fact that (4, and %n are not known priori. In the remainder of this section, propose a practical algorithm to solve (P-DALE) based on the approximation discussed in Section 3
Nevertheless, for many modern ML models such as CNNs, (--DALE
Sampling from the optimal distribution A;, Although Proposition provides characterization of the optimal distribution X,, obtaining samples from X, can still be challenging in practice, especially tasks). Moreover, in practice the (4) is not known a priori and can be arbitrarily close zero, making A; discontinuous and with a potentially vanishing support. Fortunately, these issues can be addressed by using Hamiltonian Monte Carlo (HMC) methods, which leverage the geometry of the distribution to overcome the curse of dimensionality.
when the dimension of 5, is large (e.g.. for image-classifics
value of for which (5) is solution
In particular, we propose to use a projected Langevin Monte Carlo (LMC) sampler 81). To derive this sampler, we first make a simplifying assumption: Rather than seeking the optimal constants and μr, consider the over-smoothed approximation of X; derived in 77. wherein the probability mass allocated to a particular perturbation 8 E A is proportional to the loss ((fe(x + 5), y). We note that while this choice of X; may not be optimal, the sampling scheme that we derive under this ussumption yields strong numerical performance. Furthermore. even if we knew the true values of Y, and pa, the resulting distribution for H., # would be discontinuous and sampling from such distributions in high-dimension settings is challenging in and of itself (see, e.g., [2
Given this approximate characterization of the optimal distribution, the following Langevin iteration can be derived directly from the commonly-used leapfrog simpletic integrator for the Hamiltonian dynamics induced by the distribution Xn defined in (7) (see Appendix for details). This, turn, yields the following update rule:
8 <- IT 8 siig V log [epe (Jo(x (x + 6),u)} + 22
(10)
8

---

Table Adversarial robustness on MNIST and CIFAR-10. Test accuracies of DALE (Algorithm) !
and ofute-of-hh--eeee baselines on MNIST and CIFAR-10. On both datasets, DALE surpasses the baselines against both adversaries, while simultaneously maintaining high nominal performance.
MNIST
CIFAR-10
Algorithm
P
Clean
FGSM
PGD 10
Clean
FGSM
PGD
ERM
99.3
14.3
1.46
94.0
0.01
0.01
FGSM
98.3
98.1
13.0
72.6
49.7
40.7
PGD
98.1
95.5
93.1
83.8
53.7
48.1
CLP
98.0
95.4
92.2
79.8
53.9
48.4
ALP
98.1
95.5
92.5
75.9
55.0
48.8
TRADES
98.9
96.5
94.0
80.7
55.2
49.6
MART
98.9
96.1
93.5
78.9
55.6
49.8
DALE
0.5
99.3
96.6
94.0
86.0
54.4
48.4
DALE
0.8
99.0
96.9
94.3
85.0
55.4
50.1
DALE
1.0
99.1
97.7
94.5
82.1
55.2
51.7
where & ~ Laplace(0, I). In this notation, T 0 and 1) 0 are constants which can be chosen as hyperparameters, and épert loss functions for the perturbation. The resulting algorithm is summa- rized in Algorithm[I] II Notice that l acciiuutss accountss for scenarios in which the losses associated with the adversarial performance (fm), the perturbation (fpe)). and the nominal performance (Enom) are different. It can therefore learn from perturbations that are adversarial for different loss than the one used for training the model 0. This generality allows it to tackle different applications, e-g., by replacing the adversarial error objective in (P-CON) by measure of model invariance (e.g., ACE in (53)). This feature can also be used to show that existing adversarial training procedures can be seen approximations of Algorithm T (sce Appendix A). We refer the reader to Appendix H for further discussion of the convergence properties of Algorithm
6 Experiments
In this section, we include an empirical evaluation of the DALE algorithm. particular, we consider two standard datasets: MNIST and CIFAR-10. For MNIST, we train four-layer CNNs and set A {8 || S 0.33; for CIFAR- 10, we train ResNet- models and set = (6 || S 8/255). All hyprraaraeeters and performance metrics are chosen with respect to the robust accuracy of PGD adversary evaluated on small hold-out validation set. Further details concerning hyperparameters and architectures provided in Appendix F. We also provide additional experiments in Appendix
Evaluating the adversarial robustness of DALE. We begin our empirical evaluation by comparing the adversarial robustness of DALE with numerous state-of-the-ar baselines in Table [ To evaluate the robust performance of these classifiers, we use a 1-step and an L-step PGD adversary to evaluate robust performance; we denote these adversaries by FGSM and PGD respectively. Notice that on CIFAR-10. 10, DALE with p 0.8 the only method achieve higher than 85% clean accuracy and 50% adversarial accuracy against 2GD Furthermore, when DALE is run with 1.1, we see that achieves nearly 52% adversarial accuracy, which significant improvement over all baselines. In Appendix
G we provide more complete characterization of the role of in controlling the trade-off between robustness and accuracy.
Visualizing the distribution of adversarial perturbations. To visualize the distribution over perturbations generated by DALE, we use principal component analysis (PCA) to embed perturbations into a two-dimensional space. In particular, we performed PCA on the MNIST training set to extract the first two principal components of the images; we then projected the perturbations & E A generated by PGD, FGSM, and DALE in the last iteration of training onto these principal components. A plot of these projections shown in Figure [ in which the first and second principal components are shown on the z- and y-axes respectively. Notice that the perturbations generated by FGSM are spread out somewhat unevenly this space. In contrast, the perturbations found by PGD and DALE are spread out more evenly. Furthermore, the perturbations generated by PGD and FGSM vary more

---

Test accuracy
Training loss
Dual variable
80
1.5
Nominal From
Accuracy (%)
Margin
Robust
Magnitude of
1.5
60
1.0
Loss
1.0
40
Clean
0.5
PGD
0.5
20
0.0
0
100
200
0
100 Epoch
200
0
100
200
Epoch
Epoch
Figure 2: Tracking the dual variables. Left: the clean and robust test accuracies of ResNet- 18 classifier trained on CIFAR-10 10 using DALE. Middle: the training losses for DALE. Right: The magnitude of the dual variable during training.
along the second principal component (y-axis) than the first (z-axis) relative to DALE. Since the first component describes the direction of largest variance of the data, this indicates that DALE tends to find perturbations that place more mass on the direction in which the data varies most.
Tracking the dual variables. In Figure 2 study the performance of DALE training. In the leftmost panel, we plot the test accuracy on clean samples and on adversarially perturbed samples. Notably, this classifier exceeds 50% robust accuracy against PGD as well as 85% clean accuracy; these figures are higher than either of the corresponding metrics for any of the baselines in Table [ indicating that our method is more effectively able to mitigate the trade-off between robustness and accuracy. In the middle panel of Figure 2 the dual variable v. Observe
the course of
we track the nominal and robust training losses, and the rightmost panel, we show the magmitude that at the onset of training, the constraint in (P-CON) is not satisfied, as the blue curve is above the red dashed-line. in (P-DAL.). After several epochs, this reweighting forces constraint satisfaction, after which the dual variable begins to decrease, which in turn decreases the weight on the nominal objective and allows the optimizer to focus on minimizing the robust loss.
response, the dual variable places more weight on the nominal loss term
Regularization vs. primal-dual. Our final ablation study to consider the impact of performing the dual-update step in line 10 of Algorithm T In particular, in Table 2 record the performance of DALE when Algorithm is run without the dual update step. This corresponds running DALE with a fixed weight v. Notice that although our method reaches the same level robust performance MART and TRADES, does not match the performance of the DALE classifiers in Table []] This indicates that the strong robust performance of our algorithm relies on adaptively updating the dual variable
Table 2: Regularized DALE. Test
accuracies attained by running DALE without the dual-update step in line 10 of Algorithm
Clean
FGSM
PGD 20
0.1
86.4
55.3
49.5
0.2
86.8
54.2
49.3
over the course of training.
0.3
86.3
54.8
48.2
0.4
86.2
54.6
47.3
7 Conclusion
0.5
86.5
54.3
46.8
0.6
85.7
53.3
46,4
In this paper, we studied robust learning from a constrained
0.7
85.8
53.3
46.0
learning perspective. We proved an equivalence between
0.8
84.9
53.1
45.9
the standard adversarial training paradigm and a stochastic
0.9
85.0
53,4
45.7
optimization problem over specific, non-atomic distribution.
1.0
84.5
52.7
45.8
This insight provided a new perspective on robust learning and engendered Langevin MCMC approach for adversarial robustness. We experimentally validated that this algorithm outperforms the state-of-the-ar on standard benchmarks. Notably, our method simultaneously achieved greater than 50% adversarial accuracy and greater than 85% clean accuracy on CIFAR-10 10, which represents a significant improvement over the previous state-of-the-ar
10

---

8 Acknowledgements and disclosure of funding
The authors would like to thank Juan Cervino and Samuel Sokota for their helpful feedback.
The research of Alexander Robey and Hamed Hassani is supported by NSF Grants 1837253, 1943064, 1934876, AFOSR Grant FA9550-20-1-011 and DCIST-CRA. Alexander Robey, George J. Pappas, Luiz F. O. Chamon, and Alejandro Ribeiro are all supported by the NSF-Simons Program on the Mathematics of Deep Learning. Alexander Robey and George J. Pappas are supported by ARL CRA DCIST W91 INF-17-2-018 and NSF 2038873.

---

References
[1] Andre Esteva, Alexandre Robicquet, Bharath Ramsundar, Volodymyr Kuleshov, Mark De- Pristo, Katherine Chou, Claire Cui, Greg Corrado, Sebastian Thrun, and Jeff Dean. A guide to deep learning in healthcare. Nature medicine, 25(1):24-22) 29, 2019.
[2] Li Yao, Jordan Prosky, Ben Covington, and Kevin Lyman. A strong baseline for domain adaptation and generalization in medical imaging. arXiv preprint arXiv: 1904.99443.33 2019.
[3] Haoliang Li, YuFei Wang. Renjie Wan. Shiqi Wang, Tie- Hie-Qiang Li, and Alex Kot. Domain generalization for medical imaging classification with linear-dependeng regularization. arXiv preprint arXiv:2009. 12829, 2020.
[4] Vishnu M Bashyam, Jimit Doshi, Guray Erus, Dhivya Srinivasan, Ahmed Abdulkadir, Mo- hamad Habes, Yong Fan, Colin L Masters, Paul Maruff, Chuanjun Zhuo, et al. Medical image harmonization using deep learning based canonical mapping: Toward robust and generalizable learning in imaging. arXiv preprint arXiv:2010.05355 2020.
[5] Dongxia Zhang, Xiaoqing Han, and Chunyu Deng. Review the research and practice of deep learning and reinforcement learning in smart grids. CSEE Journal of Power and Energy Systems, 4(3):362-33 3300, 2018
[6] Hadis Karimipour, Ali Dehghantanha, Reza M Parizi, Kim- Raymond Choo, and Henry Leung. A deep and scalable unsupervised machine learning system for cyber-attack detection in large-scale smart grids. IEEE Access, 7:80778-8075 80788, 2019.
[7] Tariq Samad and Anuradha M Annaswamy. Controls for smart grids: Architectures and applications. Proceedings of the IEEE, 105(11):2244-25)) 22611, 2017.
[8] Ryan Julian, Benjamin Swanson, Gaurav S Sukhatme, Sergey Levine, Chelsea Finn, and Karol Hausman. Never stop learning: The effectiveness of fine-tuning in robotic reinforcement learning. arXiv e-prints, pages arXiv-2004, 2020.
[9] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 12(11)) 1274, 2013.
[10] Niko Sünderhauf, Oliver Brock, Walter Scheirer, Raia Hadsell, Dieter Fox, Jürgen Leitner, Ben Uperoft, Pieter Abbeel, Wolfram Burgard, Michael Milford, al. The limits and potentials of deep learning for robotics. The International Journal of Robolics Research, 374--5)445--420, 2018.
[11] Battista Biggio, Igino Corona, Davide Maiorea, Blaine Nelson, Nedim Šmdić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pages 387-402. Springer, 2013.
[12] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privucy (sp), pages 39-57, IEEE, 2017.
[13] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. arXiv preprint arXiv: 1903. 2019.
[14] Josip Djolonga, Jessica Yung, Michael Tschannen, Rob Romijnders, Lucas Beyer, Alexan- der Kolesnikov, Joan Puigcerver, Matthias Minderer, Alexander D' Amour, Dan Moldovan, al. On robustness and transferability of convolutional neural networks. arXiv preprint rrXiv:2007.08558 2020.
[15] Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification, Advances in Neural Information Processing Systems, 33, 2020.
[16] Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: critical analysis of out-of-disttibution generalization. arXiv preprint arXiv:2006.162. 16241, 2020.
12

---

[17] Antonio Torralba and Alexei A Efros. Unbiased look at dataset bias. In CVPR 2011, pages 1521-1528. IEEE, 2011.
[18] Amit Datta, Michael Carl Tschantz, and Anupam Datta. Automated experiments on ad privacy settings: A tale of opacity, choice, and discrimination. arXiv preprint 1rXiv:1408.649)) 2014.
[19] Matthew Kay, Cynthia Matuszek, and Sean A Munson. Unequal representation and gender stereotypes in image search results for occupations. In Proceedings of the 33rd Annual ACM Conference on Human Factors Computing Systems, pages 3819-3828, 2015.
[20] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May, 23(2016):199-1599 2016.
[21]
Anoopkumar Sonar, Vincent Pacelli, and Anirudha Majumdar. Invariant policy optimization: Towards stronger generalization in reinforcement learning. arXiv preprint arXiv:2006.0 1009,, 2020.
[22] Eugene Vinitsky, Yuqing Du, Kanaad Parvate, Kathy Jang, Pieter Abbeel, and Alexandre Bayen. Robust reinforcement learning using adversarial populations. arXiv preprint 088 2020.
[23] John W Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pages 448-485, 1960.
[24] Peter J Huber. Robust estimation of location parameter. In Breakthroughs statistics, pages 492-518. Springer, 1992.
[25] Peter J Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
[26] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- 2014.
sarial examples. arXiv preprint arXiv:
[27] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06080 2017.
[28] Eric Wong and J Zico Kolter. Provable Defenses Against Adversarial Examples Via the Convex Outer Adversarial Polytope. arXiv preprint arXiv:1711.00833 2017.
[29] Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks neural network policies. arXiv preprint arXiv: 2017.
[30] Ayan Sinha, Zhao Chen, Vijay Badrinarayanan, and Andrew Rabinovich. Gradient adversarial training of neural networks. arXiv preprint arXiv: 08028, 2018.
[31] Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial training: Increasing local stability of supervised models through robust optimization. Neurocomputing, 307:195-22 204, 2018.
[32] Nicholas Carlini, Anish Athalye, Nicolas Pupernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint 10Xiv:/902.0670: 2019.
[33] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference Machine Learning, pages 274-283, PMLR, 2018
[34] Yan Li, Ethan Fang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adver- sarial training on separable data. In International Conference on Learning Representations, 2019.
[35] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-76) 2018.
13

---

[36] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Under- standing deep learning requires rethinking generalization. arXiv preprint arXiv: 2016.
[37] Devansh Arpit, Stanistaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer. Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International Conference Machine Learning, pages 233-242. PMLR, 2017.
[38] Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. arXiv preprini arXiv:1711.00500) 2017.
[39] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs. In International conference on machine learning, pages 605-614. PMLR, 2017.
[40] Dongxian Wu, Shu-tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. arXiv preprint vrXiv:2004.058%4 2020.
[41] Minhao Cheng, Qi Lei, Pin-Yu Yu Chen, Inderjit Dhillon, and Cho-Jui Hsieh. Cat: Customized adversarial training for improved robustness. arXiv preprint arXiv:2002.06789 2020.
[42] Harini Kannan, Alexey Kurakin, and Ian Goodfellow. Adversarial logit pairing. arXiv preprint arXiv:1803.06317 2018.
[43] Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens Van Der Maaten. Countering adversarial images using input transformations, arXiv preprint 1rXiv:1711.0011 2017.
[44] Uri Shaham, James Garritano, Yutaro Yamada, Ethan Weinberger, Alex Cloninger, Xiuyuan Cheng, Kelly Stanton, and Yuval Kluger. Defending against adversarial images using basis functions transformations. arXiv preprint arXiv: 10840, 2018.
[45] Guneet S Dhillon, Kamyar Arizzadenesheli, Zachary C Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial defense. arXiv preprint 1rXiv:1803.0144 2018
[46] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi, Unlabeled data improves adversarial robustness. arXiv preprint arXiv: 1905. /3736, 2019.
[47] Yang Bai, Yan Feng, Yisen Wang, Tao Dai, Shu-Tao Xia, and Yong Jiang. Hilbert-based generative defense for adversarial examples. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4784-4793, 2019.
[48] 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 preprini arXiv: 12843, 2019.
[49] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distilla- tion as defense to adversarial perturbations against deep neural networks. In 2016 IEEE symposium on security and privacy (SP), pages 582-597 597. IEEE, 2016
[50] Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey. Provable tradeoff's in adversarially robust classification. arXiv preprint arXiv:2006.05// 2020.
[51] Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pages 2034-2078. PMLR, 2020.
[52] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint arXiv:1805.12155 2018.
[53] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pages 7472-7482. PMLR, 2019.
14

---

[54] Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness robusttees requires revisiting misclassified examples. In International Conference Learning Representations, 2019.
[55] Stephan Zheng, Yang Song, Thomas Leung, and lan Goodfellow. Improving the robustness of deep neural networks via stability training. In Proceedings of the ieee conference on computer vision and paltern recognition, pages 4480-4488, 2016.
[56] Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. Mma train- ing: Direct input space margin maximization through adversarial training. arXiv preprint urXiv:1812.02637. 2018.
[57] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
[58] Shai Shalev-Shwarz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[59] Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained reinforcement learning has zero duality gap. arXiv preprint 19I0..111..1330 2019.
[60] Luiz Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning. Advances in Neural Information Processing Systems, 33, 2020.
[61] Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jörn- Henrik Jacobsen. Fundamental tradeoff' between invariance and sensitivity to adversarial perturbations. In International Conference on Machine Learning, pages 9561-9571. PMLR, 2020.
[62] Alexander Robey, Hamed Hassani, and George Pappas. Model- based robust deep learning.
arXiv preprint arXiv:2005. 10247, 2020.
[63] Alexander Robey, George Pappas, and Hamed Hassani. Model-based domain generalization. arXiv preprint arXiv:2 2021.
[64] Ian Goodfellow, Honglak Lee, Quoe Le, Andrew Saxe, and Andrew Ng. Measuring invariances in deep networks. Advances neural information processing systems, 6554, 2009.
[65] Eric Wong and J Zico Kolter. Learning perturbation sets for robust machine learning. arXiv preprini arXiv:2007.0844 2020.
[66] Sven Gowal, Chongli Qin. Po-Sen Huang, Taylan Cemgil, Krishnamurthy Dvijotham, Timothy Mann, and Pushmeet Kohli. Achieving robustness in the wild via adversarial mixing with disentangled representations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 1211-1220, 2020.
[67] Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pages 431-441. PMLR, 2020.
[68] Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International Conference on Machine Learning, pages 7085-7094. PMLR, 2019.
[69] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of evasion adversaries. arXiv preprint 1-X.iv:800..1444 2018.
[70] Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro. Efficiently learning adversarially robust halfspaces with noise. arXiv preprint arXiv:2005.07652 2020.
[71] Omar Montasser, Steve Hanneke, and Nathan Srebro. Vc classes are adversarially robustly learnable, but only improperly. arXiv preprint arXiv: 2019.
[72] Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial train- ing: Increasing local stability of neural nets through robust optimization. arXiv preprint axXiv:1511.0542.222 2015.
15

---

[73] Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint 1xXiv:2001.0399. 2020.
[74] Yucheng Shi, Yahong Han, Quanxin Zhang, and Xiaohui Kuang. Adaptive iterative attack towards explainable adversarial robustness. Puttern Recognition, 105: 107:107309, 2020.
[75] Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang, Un- derstanding and mitigating the tradeoff between robustness and accuracy. arXiv preprint arXiv:2002. 10716, 2020.
[76] Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaudhuri. A closer look at accuracy vs. robustness. arXiv preprint arXiv:2003.02460, 2020.
[77] Luiz FO Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. The empirical duality gap of constrained statistical learning. In ICASSP 2020-2020 IEEE Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8374-8378. IEEE, 2020.
[78] Peter Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normallieed margin bounds for neural networks. arXiv preprint arXiv:1706 08498, 2017.
[79] Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv:1810.09519, 2018.
[80] Zhuozhuo Tu, Jingwei Zhang, and Dacheng Tao. Theoretical analysis adversarial learning:
A minimax approach. 2019.
[81] Sebastien Bubeck, Ronen Eldan, and Joseph Lehec. Finite-time analysis of projected langevin monte carlo. In Advances in Neural Information Processing Systems, pages 1243 1251. Citeseer, 2015.
[82] Akihiko Nishimura, David B Dunson, and Jianfeng Lu. Discontinuous hamiltonian monte carlo for discrete parameters and discontinuous likelihoods. Biometrika, 107(2):365-380, 2020.
[83] Lasse Holmstrom, Petri Koistinen, et al. Using additive noise in pack-propagation training. IEEE transactions on neural networks, 3(1):24-38 38, 1992.
[84] Raphael Gontijo Lopes, Dong Yin, Ben Poole, Justin Gilmer, and Ekin D Cubuk. Improving robustness without sacrificing accuracy with patch gaussian augmentation. arXiv preprint arXiv:1906.026// 2019.
[85] Evgenia Rusak, Lukas Schott, Roland S Zimmermann, Julian Bitterwolf, Oliver Bringmann, Matthias Bethge, and Wieland Brendel. A simple way to make neural networks robust against diverse image corruptions. In European Conference on Computer Vision, pages 53-69. Springer, 2020.
[86] Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXi:: 04552, 2017.
[87] Zhun Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang. Random erasing data augmentation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 13001-1300s 2020.
[88] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings the IEEF/CVF International Conference on Computer Vision, pages 6023-6032, 2019.
[89] Ryo Takahashi, Takashi Matsubara, and Kuniaki Uehara. Data augmentation using random image cropping and patching for deep cnns. IEEE Transactions on Circuits and Systems for Video Technology, 3009):21 2019.
16

---

[90] Ajil Jalal, Andrew Ilyas, Constantinos Daskalakis, and Alexandros G Dimakis. The robust man- ifold defense: Adversarial training using generative models. arXiv preprint 97X.v:1712.09196. 2017.
[91] Chaowei Xiao, Bo Li, Jun-Yan Zhu, Warren He, Mingyan Liu, and Dawn Song. Generating adversarial examples with adversarial networks. arXiv preprini 1.Xiv:/801.0200 2018.
[92] Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan: Protecting classifiers against adversarial attacks using generative models. arXiv preprint 1805. 2018.
[93] Shuxiao Chen, Edgar Dobriban, and Jane H Lee. A group- group- theoretic framework for data augmentation. Journal of Machine Learning Research, 21(245):1-71, 2020.
[94] Radford M Neal et al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(11):2, 2011.
[95] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.09670, 2020.
[96] Dimitri P Bertsekas. Convex optimization theory. Athena Scientific Belmont, 2009.
[97] R Tyrelll Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
[98] Andrzej Ruszczynski. Nonlinear optimization. Princeton university press, 2011.
[99] Frédéric Bonnans and Alexander Shapiro. Perturbation analysis of optimization problems. Springer Science & Business Media, 2013.
[100] Michael Betancourt. A conceptual introduction to hamiltonian monte carlo. arXiv preprint arXiv:1701.02434 2017.
[101] Christopher M Bishop. Pattern recognition. Machine learning, 128(9), 2006.
[102] The MNIST datahase of handwritten digits Home Page. http://yann. lecun www.:eeeenncncc....eeeeee...eeee com/exdb/ mnist/
[103] Matthew DZeiller Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 121.55701 2012.
[104] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[105] Sébastien Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv:1405.4980. 2014.
[106] Frédéric Bonnans. Convex and Stochastic Optinization. Springer, 2019.
[107] Dimitri Bertsekas and John N Tsitsiklis. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 10(3):627-642, 2000.
[108] Ahmad Ajallocian and Sebastian Stich. Analysis of sgd with biased gradient estimators.
arXiv preprint arXiv:2008.0005: 2020.
[109] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv:1710.10571, 2017.
[110] Rui Gao, Xi Chen, and Anton J Kleywegt. Wasserstein distributional robustness and regular- ization in statistical learning. arXiv e-prints, pages arXiv-1712, 2017.
[111] Aharon Bal, Laurent Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton university press, 2009,
17

---

[112] Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv: 0et.//96600444 2019.
[113] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via random- ized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
[114) Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learning, pages 5458-5467. PMLR. 2020.
[115] Priya L Donti, David Rolnick, and Zico Kolter. De3: A learning method for optimization with hard constraints. arXiv preprint arXiv:2104 12225, 2021.
[116] Deepak Pathak, Philipp Krahenbuhl, and Trevor Darrell. Constrained convolutional neural networks for weakly supervised segmentation. Proceedings of the IEEE international conference computer vision, pages 1796-1804, 2015.
[117] Steven Chen, Kelsey Saulnier, Nikolay Atanasov, Daniel D Lee, Vijay Kumar, George J Pappas, and Manfred Morari. Approximating explicit model predictive control using constrained neural networks. In 2018 Annual American control conference (ACC), pages 1520-1527. IEEE, 2018.
[118) Thomas Frerix, Matthias Nießner, and Daniel Cremers. Homogeneous linear inequality constraints for neural network activations. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 748-749, 2020.
[119] Brandon Amos and Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
[120] Sathya N Ravi, Tuan Dinh, Vishnu Lokhande, and Vikas Singh. Constrained deep learning us- ing conditional gradient and applications in computer vision. arXiv preprint arXiv:1803.0m 1803.06453, 2018.
[121] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. arXiv preprint arXiv: 12430, 2019.
[122] Dimitris A Karras and Stavros J Perantonis. An efficient constrained training algorithm for feedforward networks. IEEE Transactions on Neural Networks, 4200,144,, 1995.
18


Reviews:
[{"review_id": "A9KnhE_yqa", "reviewer": "Reviewer_v1iK", "summary": "The paper provided a novel connection between the well-known adversarial training problem and a statistical problem over perturbation distributions. The former requires obtaining worst-case adversarial perturbations of a neural network as an inner optimization procedure, which has been known as a challenging task. The later can avoid this but needs to solve a new inner optimization over perturbation distributions instead. The authors demonstrated that the statistical problem recovered several existing adversarial training problems with sub-optimal perturbation distributions. Inspired by this connection, the paper introduced an alternative adversarial training algorithm that used a smoothed version of the optimal perturbation distribution and showed that the proposed algorithm can achieve competitive or even better performance compared to previous approaches in terms of empirical adversarial robustness (evaluated using empirical attacks) on image classification tasks such as MNIST and CIFAR-10.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The writing is clear and easy to follow. Even though there are some typos/missing definitions in the main body, I believe they are largely innocuous and do not hinder understanding. \n\nMy main concern of the paper at the current state is its lack of empirical evaluations:\n\n1) *Lack of evaluations on the trade-off between using more Langevin iterations vs. model performance*\nThe proposed method uses projected Langevin sampler to approximate the optimal distribution of the perturbation.\nHaving enough number of steps (L) in the sampling step is usually crucial to the quality of the approximation, but can incur a big computation cost at the same time.  \nBecause of this, I believe it is important to analyze the trade-off between $L$/training time and the performance, and I think the current paper does not do that thoroughly. \nThe authors did provide some results to show the difference in performance with different $L$'s. For example, the performance is reported with $L=1$ and $L=100$ for MNIST and $L=10$ for CIFAR-10, but they alone don't tell much about how practical these settings are when scaling up to larger networks without learning about their training time.  \n\n2) *Lack of experimental details*\nThe experimental section didn't specify the threat model (e.g., under which norm ball the perturbation should be confined in). \nThis is an important detail that should be included since the difficulty of robust classification varies greatly among different norms. \nAlso, the hyperparameters for the PGD attack evaluations are also missing. \nAs the authors also noted that adversarial attacks rely on \"heuristics such as random initializations and random starts, ...\", providing these details and the tuning procedures for the attacks would be helpful for a more thorough examination of the proposed method's performance.\n\nAside from these two main issues, the experiment section could also be benefited from a more diverse set of perturbation radius and perturbation shape (e.g., different norms). \n\n*Some More Detailed Comments*\n- Algorithm 1, L8 - What is the difference between $\\tilde{l}$ and $l$? Is it a typo?\n- Algorithm 1, L5 - I think $g, T$ should be defined somewhere in the main body rather than only in the Appendix. \n- L238 - same as above. I think $\\mathcal{H}$ is never defined in the main body. \n- L303 - typo \"it is well-know that...\" => well-known\n- The references are missing for some baselines in the experiment section (e.g., FAB, A-PGD, MART).\n\nOverall, I think it is a really wonderful paper with a novel reformulation of the adversarial learning problem accompanied with an effective practical algorithm. I would recommend acceptance and I think improving the empirical section could greatly further strengthen the paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think that the paper can be benefited from adding more discussion of the limitations of the proposed algorithm. For example,\n- What is the run-time of the proposed algorithm? (e.g., how large does $L$ need to be to be competitive of existing approaches and what is the resulting run-time?)\n- The proposition 3.2 assumed that the loss function $(x, y) \\mapsto \\ell(f_\\theta(x), y) \\in L^2$. Does this assumption usually hold for the neural networks of interest?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "-VTMPt1kEZW", "reviewer": "Reviewer_JwwU", "summary": "The paper presents a new algorithm for performing adversarially robust training via a dual characterization.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper considers the problem of learning adversarially robust classifiers. The problem is traditionally formulated as that of minimizing the robust loss where on any given point (x,y) the loss is evaluated at (x+delta, y) where delta is a perturbation among a set of allowed perturbations. The loss at (x,y), \\ell(x,y) is then the maximum loss in the neighborhood of x, i.e, \\ell((x+\\delta, y)). The robust loss is intractable in general and in fact even the maximization problem of finding the worst perturbation for a given (x,y) is hard unless the classifiers is a simple model, such as linear classifiers. \n\nThe paper proposes to solve the constrained robust learning problem where the goal is to minimize the robust loss subject to the fact that the standard (non-robust) loss is small as well. This formulation addresses practical concerns where optimizing for the robust loss typically leads to an increase in the standard loss. The authors propose a dual formulation of the problem by providing a dual characterization of the inner maximization problem. In the dual space the inner maximization can be written as optimizing over a set of distributions over perturbations (for a given (x,y)). The main result of the paper is a characterization of the optimal distribution. Based on this the authors propose a sampling approach, where for each (x,y) the perturbation is sampled from an approximation to the optimal perturbation distribution. The approximation essentially samples a perturbation delta with probability proportional to \\ell(x+delta, y). The authors present empirical results on CIFAR-10 and MNIST and show that the method proposed is competitive with existing approaches. \n\nOverall the paper presents a novel take on adversarial robustness. Proposition 3.2 is the key result. It would be interesting to consider better approximations to the optimal distribution than the choice made in the paper (given that the empirical improvements obtained are within 1-2%). \nThe paper also presents generalization bounds, but they more of less follow standard techniques. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some technical limitations of the work are addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "-AlHDwQxJro", "reviewer": "Reviewer_rhY5", "summary": "This paper studies the adversarial robustness through semi-infinite optimization and non-convex duality theory. By leveraging tools from constrained optimization and duality theory, the authors find the adversarial training formulation is equivalent to learning from a perturbation distribution. The authors propose a constrained learning problem for achieving model robustness while maintaining the nominal performance on clean samples. The authors propose an unconstrained saddle point reformulation for solving the constrained optimization problem via duality, and develop an LMC-based algorithm. Empirically, the authors find the new algorithm can achieve better performance on some standard benchmark tasks.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The identified connection between constrained formulation in (P-RO) and the statistical counterpart (in Eq. (5)) is interesting, which provides theoretical insights on the constrained problem as well as the trade-off between robustness and accuracy.\n\nCons:\n1. The results in Proposition 3.6 are meaningless. Since $\\zeta_{R}(N)$ is the difference between the expected robust risk and the empirical robust risk (defined in Eq. (9a)). $\\zeta_{R}(N)$ is relatively large, which suggests $|P^{\\star} - \\hat{D}^{\\star}|$ is large. More specifically, if $\\zeta_{R}(N)$ is small, then the model already achieves robust generalization. However, clear robust overfitting has been observed in the literature. \n2. The empirical results in Section 6 are not convincing to support the claim 'improved results over state-of-the-art benchmarks' mentioned in the abstract. For example, I would suggest the authors apply tools from RobustBench [85] to evaluate the robust accuracy properly (in order to avoid fake robustness). Also, AWP [46] should be included in section 6.2.\n\nTypo:\n1. $(x_n, y_n)$ in Line 268, $x_n$ should be bolded. \n\nMissing reference:\n1. Strong duality for non-convex problems, [BLW+2019].\n\nOverall, I think the paper is marginally below the acceptance bar.\n\n[BLW+2019]. Non-Convex Matrix Completion and Related Problems via Strong Duality. Maria-Florina Balcan, Yingyu Liang, David P. Woodruff. Journal of Machine Learning Research, 2019.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to solve the constrained robust learning problem via a dual formulation of the problem by where the inner maximization can be written as optimizing over a set of distributions over perturbations (for a given (x,y)). The main result of the paper is a characterization of the optimal distribution. Based on this the authors propose a sampling approach, where for each (x,y) the perturbation is sampled from an approximation to the optimal perturbation distribution. The paper presents a practical algorithm based on the theory that achieves competitive results on benchmark datasets.

The reviewers raised concern about some of the theoretical portions of the paper that follow from standard tools. Given that the empirical results are competitive with algorithms such as TRADES (that are also based on theoretical insights), it was unclear whether the main theoretical result (proposition 3.2) is novel enough for NeurIPS. It was also pointed out by the reviewers that the empirical comparisons where not conducted with respect to proper benchmarks such as RobustBench (this was addressed by the authors in the response via additional experimental results). Overall this is a borderline paper.
Decision: Accept (Poster)