Year: 2021

Abstract:
While ML tools are becoming increasingly used in industrial applications, adversarial examples remain a critical flaw of neural networks. These imperceptible perturbations of natural inputs are, on average, misclassified by most of the stateof-the-art classifiers. By slightly modifying each data point, the attacker is creating a new distribution of inputs for the classifier. In this work, we consider the adversarial examples distribution as a tiny shift of the original distribution. We thus propose to address the problem of adversarial training (AT) within the framework of distributional robustness optimization (DRO). We show a formal connection between our formulation and optimal transport by relaxing AT into DRO problem with an∞-Wasserstein constraint. This connection motivates using an entropic regularizer– a standard tool in optimal transport— for our problem. We then prove the existence and uniqueness of an optimal regularized distribution of adversarial examples against a class of classifier (e.g., a given architecture) that we eventually use to robustly train a classifier. Using these theoretical insights, we propose to use Langevin Monte Carlo to sample from this optimal distribution of adversarial examples and train robust classifiers outperforming the standard baseline and providing a speed-up of respectively ×200 for MNIST and ×8 for CIFAR-10.

heading: 1 INTRODUCTION
text: We call adversarial example an input which is a human-imperceptible -perturbation1 compared to a real example that results in an incorrect classification from a classifier [Goodfellow et al., 2014; Sun et al., 2018; Athalye et al., 2018; Santurkar et al., 2019; Nguyen et al., 2015a; Kurakin et al., 2016; Moosavi-Dezfooli et al., 2016]. The particularity of these examples, which justifies their study, is the fact that most of the so-called adversarial examples are misclassified by a large majority of state-of-the-art neural networks. Long seen as bugs, Santurkar et al. [2019] asserts that the existence of adversarial examples is explained by the presence of easy-to-perturb patterns within the data distribution that are not perceptible by humans but useful for the classification task.
In response to this discovery, different methods have been developed to train robust classifiers and to craft adversarial attacks by determining optimal perturbations [Nguyen et al., 2015b; Papernot et al., 2016a; Goodfellow et al., 2014; Papernot et al., 2016b; Tramèr et al., 2017; Madry et al., 2017]. Among these training methods, adversarial training [Goodfellow et al., 2014; Tramer et al., 2017; Madry et al., 2018] has settled as one of the strongest baselines to train robust classifiers. This method is relatively simple: it consists of training the classifier directly on batches of adversarial examples, leading to the following optimization problem [Madry et al., 2018]:
min θ∈Rd E(x,y)∼pdata [ max‖x̃−x‖∞≤ `(fθ(x̃, y))] (1)
where ` is usually the cross-entropy loss and pdata is the dataset distribution. Our goal is to rigorously connect adversarial training and robustness by providing a distributional robustness
1Adversarial example can be defined with respect to any notion of distance that captures the fact that an -perturbation is imperceptible by a human. In this work, for the sake of simplicity, we focus on the `∞ norm, which is the most common one.
perspective [Delage and Ye, 2010; Ben-Tal and Nemirovski, 1998; Sinha et al., 2018] for adversarial training. Distributional robustness is a framework to study predictive models that aim at being robust against distribution shift. Given a set of possible distribution P that a given predictive model fθ could encounter the distributionally robust classification task is:
min θ∈Rd max padv∈P Ex̃∼padv [`(fθ(x̃, y))] (2)
Note that while standard adversarial training aims to use the point-wise optimal adversarial x̃j examples (i.e. for each natural input xi), our perspective considers the optimal adversarial distribution. Working at the scale of distributions leads us to draw inspiration from the Kantorovich relaxation in Optimal Transport theory. To do so, we will define the set P using coupling measures between natural and adversarial distributions with the help of∞-∞-Wasserstein distance. Contributions. Our contributions are three-fold: First, we provide a strong connection between adversarial training and adversarial robustness and distributional robustness by using some tools from optimal transport, we call this formulation adversarial transport. Our second contribution is to show that, in this specific setting, there exists, against any given classifier fθ, an optimal distribution of adversarial examples and to provide a closed-form solution for this distribution. Our third contribution is to use these theoretical insights to come up with a practical training method using Langevin Monte-Carlo sampling to jointly find the optimal classifier and the optimal distribution of adversarial examples. By using this new technique for adversarial training we obtain robust classifiers outperforming the standard baseline [Madry et al., 2018] in terms of robustness and clean accuracy. Moreover, this training technique provides a speed-up of respectively ×200 for MNIST and ×8 for CIFAR in terms of training time.
Related Work. Among the various works about defenses and attacks in the context of adversarial examples, Adversarial Training [Madry et al., 2018] is the most common baseline. However, in this procedure, adversarial examples are generated independently of the others by searching for the optimal perturbation for each one. Thus, AT seeks point-wise optimality and not global optimality. Here, the goal is to make our classifier robust to any unknown adversarial example distribution. It justifies the consideration of the DRO framework. DRO enables a mathematical formulation for dealing with uncertainty in complex systems [Delage and Ye, 2010; Lam, 2018; Rahimian and Mehrotra, 2019]. In ML, DRO tries to minimize the loss over the worst-case distribution in a neighborhood of the observed training data distribution [Duchi and Namkoong, 2016; 2018; Chouzenoux et al., 2019; Duchi et al., 2016]. Thus, DRO is pertinent in the case of adversarial examples and allows to bring a principled distributional perspective on AT.
Within the DRO framework, one crucial point is to properly define the uncertainty set which contains the underlying data distribution. The importance of this set lies in the fact that it allows to reduce the computation time and the search area of the underlying distribution [Delage and Ye, 2010; Ben-Tal and Nemirovski, 1998; Lam, 2018]. Different methods have been proposed to construct uncertainty sets. Among them, one considers the help of OT operators and defines the set with all the probability measures such as the p-Wasserstein distance from the observed distribution is less than a given constant (p-Wasserstein ball)[Blanchet and Murthy, 2019].
Some works have started to study p-Wasserstein DRO in the case of adversarial examples. Zheng et al. [2019] defines Distributionally Adversarial Attacks (DAA) which is a generalization of PGD attacks on the space of probability measures with W2-DRO and [Staib and Jegelka, 2017] did the Wp-DRO generalization of AT. E.Wong et al. [2019] also considers the Wp ball using an explicit formulation of the uncertainty set with coupling matrices. However, while the previous works modified the AT problem—the Wp constraint on the adversarial distribution does not correspond to the distribution of adversarial examples computed in AT—our work aims at overcoming that. The original AT problem stays a the scale of the example and considers OT to deal with the displacement of pixels. This perspective leads to the discovery that the standard AT problem corresponds to an∞-Wasserstein DRO problem with the `∞ underlying geometry.
In the meantime, as in our paper, entropic regularization is used to find closed forms of the coupling matrix. To extend this understanding of adversarial examples in the case of distributions we generalize this uncertainty set with the ∞-∞-Wasserstein distance and add entropic regularization. 2-∞- Wasserstein DRO has already started to receive consideration in the case of AT [Gao et al., 2017].
Nevertheless, the use of the `∞ within the∞-Wasserstein distance allows both to consider the DRO problem at the dataset scale but also to ensure that the adversarial condition is respected for each
element of the adversarial distribution. Together with the use of coupling matrices in our formulation, we found a concave and tractable formulation of our problem which results in a different technique to sample from this distribution (namely Langevin Monte Carlo). Finally, we propose to keep them in memory to reuse the past samples for the update of the robust classifier.
Notations. In this work, we will consider a measurable finite dimensional input space X ⊂ Rd. We will note B(X ) the Borel σ-algebra of X andM(X )1+ the set of all probability measures on X . If not precised, a map T : X → X is considered measurable. We, recall that given a separable metric space X s.t. any probability measure on X is a Radon measure, for T : X → X , the push-forward measure of β = T]α ∈ M(X )1+ of some α ∈ M(X )1+ satisfies: ∀h ∈ C(X ), ∫ X h(x̃)dβ(x̃) =∫
X h(T (x))dα(x).

heading: 2 ADVERSARIAL TRAINING, TRANSPORT, AND DISTRIBUTIONAL ROBUSTNESS
text: In this work, we say that x̃ ∈ X is an adversarial example of f at the data point (x, y) if ‖x̃−x‖∞ ≤ [Goodfellow et al., 2014]. Given a loss function `, an optimal adversarial example x̃ aims at maximizing the following optimization problem:
x̃ ∈ arg max ‖x̃−x‖∞≤ `(fθ(x̃), y) . (3)
In practice, a large value for `(fθ(x̃), y) will yield a misclassification of the example y. By considering the adversarial training problem (1), one can notice that the distribution of input-output pairs seen by the classifier fθ depends on the value of its own parameters. We will call this distribution padv . Such a distribution can be described as the pushforward of a transport map T that respect the adversarial example constraint ‖T (x)− x‖∞ ≤ , ∀x ∈ X . In other words we have, padv = T]pdata : (x̃, y) ∼ padv ⇔ ∃(x, y) ∼ pdata s.t. x̃ = T (x) and ‖x̃− x‖∞ ≤ . (4)
This remark leads us to our first proposition that explicitly proposes a distributional robust optimization (DRO) formulation of the adversarial training problem. Proposition 2.1 (DRO formulation of adversarial training). The adversarial training problem (1) can be formulated as a DRO problem (2) where:
P = {padv : ∃T : X → X , padv = T]pdata and ‖T (x)− x‖∞ ≤ , ∀x ∈ X} (5)
Interestingly, one can draw parallels with Monge’s formulation of optimal transport (OT), were given an initial measure µ and a target measure ν, the task is to solve the following problem
inf T ∫ X c(x, T (x))dµ(x) subject to ν = T]µ . (6)
On the one hand, (6) and the DRO problem defined in Proposition 2.1 are drastically different problems in essence. It can be explained by the difference between the constraints on the transportation map and the fact that while Equation 6 aims at minimizing a function of the transportation map T , Equation 2 aims at maximizing a function of the transported distribution padv .
On the other hand, it is insightful to notice how both problems depend on a set of transportation maps to connect the initial and the target distributions.
The limitations of Monge’s problem are well known in the OT community: due to its non-linear constraint, the problem is often intractable and may not have a solution (i.e. the infimum may not be achieved). That is why Kantorovich [1940], proposed to relax (6) into a problem with linear constraints by considering coupling measures (an approach that allows a mass splitting from a natural example xi to different locations x̃j). Such a relaxation had the advantage to provide a better understanding of the original problem leading to novel theoretical guarantees (e.g., the existence of solutions for Kantorovich’s problem, duality, and in some situations equality between Monge’s problem and Kantorovich’s problem) as well as tractable algorithms [Sinkhorn, 1964; Cuturi, 2013b].
In a similar vein, we believe our perspective on adversarial examples that combine ideas from distributional robustness and adversarial transport leads to a better understanding of the problem of adversarial training. Thus, we will use that insight to consider coupling measures to relax the adversarial training problem (1). It will lead to a new DRO formulation for adversarial training that we call adversarial transport.

heading: 3 ADVERSARIAL TRANSPORT FORMULATION
text: We first define the notion of coupling measure, that we will use to define a relaxed version of the DRO formulation described in Proposition 2.1. Definition 3.1 (Transport plan). Let padv and pdata be two distributions on X . π ∈ B(X )⊗B(X )→ [0, 1] is a transport plan between padv and pdata if:
∀A ∈ B(X ), π(A×X ) = pdata(A) and ∀B ∈ B(X ), π(X ×B) = padv(B) (7) The space of transport plan between pdata and padv is denoted Π(pdata, padv).
Informally, the coupling measure π : B(X )⊗ B(X ) describes the spatial modification of the initial distribution pdata to the adversarial distribution padv. For instance, in the discrete case where we have the datapoints (xi) and the potential adversarial examples (x̃j), a coupling is a matrix P such that the value Pi,j represents the amount of mass flowing from the natural example i to the adversarial example j.

heading: 3.1 INCORPORATING THE PROXIMITY CONSTRAINT TO THE COUPLING.
text: Adversarial examples are tied to the original examples by a proximity constraint. Thus, a DRO formulation of adversarial training must encompass such a constraint. For a coupling measure it corresponds to the fact that it can transport (x, y) ∼ pdata to (x̃, y) ∼ padv only if ‖x− x̃‖∞ ≤ . Proposition 3.1 (DRO relaxation of adversarial training). The DRO problem (2) can be relaxed by considering coupling measure. In that case the constraint set P in Equation 2 take the form: Pconv = {padv : ∃π ∈ Π(pdata|padv) with supp(π) ⊂ {(x, y, x̃, y) | ‖x̃− x‖∞ ≤ , y ∈ Y }} .
This proposition proposes a convex relaxation of the initial constrain set (5). Intuitively, the set P constraints the distribution padv to be -close to pdata. Because this set is convex we can hope it corresponds to a notion -ball. We show in the next subsection that this intuition can be formalized by using the∞-Wasserstein distance.

heading: 3.2 CONNECTION WITH∞-WASSERSTEIN
text: Given two distributions µ and ν and a distance function d, the p-p′-Wasserstein distance corresponds to the minimal average `p norm to the power of p over the transport plans between µ and ν. Formally, by calling z = (x, y) and Z := X × Y , it can be defined as
Wp,p′(µ, ν) := inf π∈Π(µ,ν) (∫ Z×Z ‖z − z̃‖p ′ p dπ(z, z̃) )1/p′ . (8)
The p-∞-Wasserstein distance can be defined as the limiting case p′ →∞. Thus, it can be seen as the minimal amount of point-wise transport (w.r.t. the `p norm) necessary to transport µ to ν,
Wp,∞(µ, ν) = inf π∈Π(µ,ν) sup (z,z̃)∈supp(π)
‖z − z̃‖p . (9)
Thus by considering p = ∞, we can establish that the set introduced in Proposition 3.1 can be described using the∞-∞-Wasserstein distance. Proposition 3.2. [convex relaxation of adversarial training]For any < 1,2 the convex DRO relaxation of adversarial training can be reformulated as
min θ∈Rd max padv∈B (pdata) E(x̃,y)∼padv [`(fθ(x̃, y)] (10)
where B (pdata) = {p |W∞,∞(p, pdata) ≤ } and Wp,∞ is defined in (9).
In other words, adversarial training can be seen as a DRO problem restricted to the distributions that are -close to the data distribution with respect to the∞-∞-Wasserstein (∞-Wasserstein distance within a space with the `∞ metric).
The p-p′-Wasserstein distance has been widely studied in the context of optimal transport [Champion et al., 2008; Villani, 2003]. The closeness of our formulation with OT encourages us to add an entropic regularization [Peyré and Cuturi, 2019; Cuturi, 2013a].
2This assumption is only for simplicity of exposition, what we need in general is that < miny 6=y′ |y − y′| which can always be achieved by reparametrizing the discrete labels.

heading: 3.3 ENTROPY-REGULARIZED FORMULATION
text: Entropic regularization has been a very successful approach for finding an approximate solution to OT problems [Cuturi, 2013b; Genevay et al., 2016]. From a theoretical point of view, the entropic regularization prevents the sparsity of the coupling matrix, which is justified from a practical aspect in the context of transport by the fact that in practice the transport network is diffuse [Wilson, 1969]. In the context of adversarial examples, this is justified by the fact that the adversarial examples are mostly located in areas of low probability for the input distribution [Song et al., 2017; Ma et al., 2018]. We suppose that pdata admits a density. For an arbitrary coupling measure π, we can define a relative entropy function as H(π) = − ∫ Z×Z(log(π(z, z̃)) − 1)dπ(z, z̃) with H(π) = +∞ is π does not admit a density. Thus our entropy-regularized problem is:
min θ∈Rd max π∈Π(pdata,padv) s.t. padv∈B (pdata)
E(x̃,y)∼padv [`(fθ(x̃), y)] + 1 λH(π) . (11)
The objective is strictly concave in π, therefore our regularized problem becomes strongly concave which ensures the existence and uniqueness of an optimal solution. It will allow us to obtain an explicit formulation for the optimal coupling π and then for the optimal adversarial distribution padv . The solution of this new problem will be an approximate solution of the original problem (A). By calling the optimal coupling π∗λ associated to this regularized problem (11) we have the following property: Proposition 3.3. If λ→∞, then π∗λ → π∗.

heading: 3.4 SOLUTIONS TO THE ADVERSARIAL TRANSPORTATION PROBLEM
text: In this section, we study the general framework where the two measures pdata and padv are defined on metric spacesX . No particular assumption is made on the form of pdata and padv . The inner-objective of penalized adversarial transportation problem is the following:
g(θ) = max π hθ(π) := max π∈Π(pdata,padv)
s.t. ∃padv∈B (pdata)
E(x̃,y)∼padv [`(fθ(x̃), y)] + 1 λH(π) , (12)
where B (pdata) = {p |W∞,∞(p, pdata) ≤ }. For any given θ ∈ Rd, the function hθ is strictlyconcave and the constraints on π are convex (cf Appendix A for proof). Then, by using convex duality, we can deduce that the problem (12) has a unique closed-form solution: Proposition 3.4. For any given θ ∈ Rd, The optimization problem (12) has a unique solution,
π∗((x, y), (x̃, ỹ)) ∝ pdata(x, y) exp(λ`(fθ(x̃), y))1‖x−x̃‖∞≤ 1y=ỹ . (13) For a given natural example x with a label y, π((x, y), (x̃, ỹ)) grows with the propensity of x̃ to be better than the other elements of Bx( ) (the `∞-ball of radius ) to fool the classifier. We then deduce the explicit form of the adversarial distribution:
p∗adv(x̃, y) = Ex∼px,data [pdata(y|x) exp(λ`(fθ(x̃),y))1‖x−x̃‖∞≤ ∫ x̃∈B (x) exp(λ`(fθ(x̃),y))dx̃ ] (14)
From this proposition, we notice that if x̃ ∈ Bx( ), then π(z, z̃) > 0, i.e. any examples which satisfies the adversary condition has a non-zero probability to be considered as an adversarial example of x. However, when λ is large enough, most of the mass of the distribution lies where `(fθ(x̃), y) is close to its maximum value. Moreover it is interesting to notice that the mass of padv(x̃, y) can come from the transport of several input data-points as a potentially infinite number of input data-point x verify the constraint 1‖x−x̃‖∞ and thus could be transported to x̃. We will seen in the next section that is never happens in practice.
As we noticed before, the inner maximization problem is strictly-concave in π and the constraints are convex. By strong duality, we know that the dual form is equal to the primal. The primal can be expressed with a min over a lagrange multiplier α s.t. α(x, y) = − 1λ log( pdata(x,y)∫ x̃∈B (x) exp(λ(`(fθ(x̃),y)))dx̃) ) (c.f. Appendix A for proof) and is convex w.r.t. this variable. Thus, we can express the original min-max optimization problem as a convex minimizaion problem in θ which leads to our central theorem.
Theorem 3.1 (Characterization of the solutions). For any λ > 0, the solution set of the regularized adversarial training problem (11) is:
θ∗ ∈ arg minE(x,y)∼pdata [ 1λ log( ∫ ||x̃−x||≤ exp(λ`(fθ(x̃), y))dx̃)] =: arg min g(θ) , (15)
and the optimal adversarial distribution associated with this adversarial training problem is
padv(x̃, y) = Ex∼px,data [pdata(y|x) exp(λ`(fθ∗ (x̃),y))1‖x−x̃‖∞≤ ∫ x̃∈B (x) exp(λ`(fθ(x̃),y))dx̃ ] (16)
In order to solve (12) we would need to sequentially sample from π to compute the gradient of g (see §4) for the exact derivation of∇g(θ). Because of its normalization constant, the computation transport plan (29) for any given value of θ may be expensive to compute. However we will see in the next sections that: a) in practice, one computes this plan simultaneously with the training on the classifier and b) it has a simpler form in practice when dealing with a finite dataset.
A Zero-Sum game perspective on Adversarial Transport. One perspective on (11) is that it corresponds to game between a classifier fθ and a transport plan π that aims at transporting the data distribution pdata into an adversarial distribution padv that is -close to pdata with respect to the ∞-∞-Wasserstein distance. While the classifier aims at minimizing the average cross-entropy loss over the adversarial dataset the transport plan aims at maximizing the errors of the classifier and its own entropy. This perspective is closely related to Adversarial examples games (AEG) [Bose et al., 2020] where the authors tried to learn an adversarial distribution with a generator conditioned on the input examples. This work differs from AEG by its perspective (we connect adversarial examples with DRO), the problem formulation (we look for a regularized transport plan while AEG focused on a generator), the algorithmic implementation (we consider Langevin to find the transport plan), and the finale focus since AEG concentrated on the generation of transferable adversarial example while our focus is on training robust classifiers.
This perspective also gives us an insight: the optimal distribution of adversarial examples may provide adversarial attacks that transfer well across models. The latter point can be supported by the following minimax theorem that is a simple extension of the result from [Bose et al., 2020, Prop. 1]. Proposition 3.5. Let us call E(x̃,y)∼padv [`(fθ(x̃), y)] + 1 λH(π) = ϕ(θ, π). If {fθ | θ ∈ Θ} is a convex set, then we have that
min θ∈Rd max π∈P ϕ(θ, π) = max π∈P min θ∈Rd ϕ(θ, π) (17)
Pconv = {padv : ∃π ∈ Π(pdata|padv) with supp(π) ⊂ {(x, y, x̃, y) | ‖x̃− x‖∞ ≤ , y ∈ Y }} ..
The assumption that the class of function {fθ | θ ∈ Θ} is convex is not always true in practice but it holds in the case of linear classifier or when one assumes that we have infinite capacity classifiers (i.e. we can achieve a measurable function). Moreover, considering the class of neural networks, it has been argued that they were spanning a set that is almost convex [Gidel et al., 2021].

heading: 3.5 PRACTICAL CASE: SEMI-DISCRETE ADVERSARIAL TRANSPORTATION PROBLEM
text: In practice, we do not have access to the true distribution pdata but only to a finite dataset sampled from this distribution (e.g MNIST/ CIFAR-10, etc). This can be seen as considering the empirical distribution pdata = 1n ∑n i δxi . However, even when considering empirical distributions, the distribution of adversarial examples padv is an arbitrary measure on metric space X as an adversarial example could be any point in the `∞-ball of radius ball from the initial point (for datapoint xi we call that ball B (xi)). Its analysis is thus similar to the continuous case. However, in such a practical case the optimal transport map has a simpler form under the following assumption Assumption 3.1 (Empty intersection). We have that B (xi) ∩ B (xj) for all 1 ≤ i 6= j ≤ n.
For real world dataset, this assumption is almost always true. It means that two datapoints are not close which would mean that they are perceptually indistinguishable. We can actually show that if the inputs are high dimensional Assumption 3.1 hold with an exponentially high probability, Proposition 3.6. Let us assume that the datapoints xi are independently sampled from a distribution p over [0, 1]d that is absolutely continuous with respect to Lesbegue measure and has a upper-bounded value, i.e. p(x) ≤M , x ∈ [0, 1]d. Then P(∃i 6= j ∈ [n] , ‖x̃j − xi‖∞ ≤ ) = O(n2 d).
such a proposition could be extended to the more challenging setting where the data distribution is supported by a manifold but this is out of the scope of this paper since its purpose is purely illustrative.
Theorem 3.2. [Characterization of the solutions in the semi discrete case] For any λ > 0, the solution set of the regularized adversarial training problem (11) is:
θ∗ ∈ arg min 1 nλ n∑ i=1 log (∫ ||x̃−xi||≤ exp(λ`(fθ(x̃), yi))dx̃ ) =: arg min g(θ) , (18)
and under Assumption 3.1 the optimal adversarial distribution associated with this adversarial training problem is
padv(x̃, y) =  exp(λ`(fθ(x̃), y)) n ∫ x̃∈B (xi) exp(λ`(fθ(x̃), y))dx̃
if ∃ i ∈ [n] s.t. ‖xi − x̃‖∞ ≤
0 otherwise.
(19)
The practical insight from this result is that the distribution of adversarial example can, in practice be generated example-wise. Meaning that for each datapoint xi, i ∈ [n] one can generate the distribution of adversarial examples around xi distributed as padv(x̃, y) ∝ exp(λ`(fθ(x̃), y)), ∀x̃‖x̃− xi‖ ≤ . Practically, we will maintain a finite dataset of the adversarial examples (x̃i,k) associated with the datapoint xi.

heading: 4 ADVERSARIAL TRANSPORT ALGORITHM
text: We want to solve the minimization problem (40). We can solve this problem using gradient descent:
θt+1 = θt − η∇θg where ∇θg = 1
n n∑ i=1 ∫ B (xi) ∇θ`(fθ(x̃), yi)) eλ`(fθ(x̃),yi))∫ B (xi) eλ`(fθ(x̃),yi))dx̃ dx̃ (20)
To evaluate this gradient we need to sample from the distribution q̃(x̃) ∝ exp(λ`(fθ(x̃), yi)) defined over B (xi). This can be done via Langevin Monte Carlo [Durmus and Moulines, 2016] as the next section explains.

heading: 4.1 LANGEVIN MONTE CARLO
text: Unadjestued Langevin Algorithm [Durmus and Moulines, 2016] is convenient to sample highdimensional probability distribution q. Having the following density w.r.t. the Lesbegue measure q(x̃) ∝ exp(−U(x̃)), one can show that q is the stationnary measure of the following Stochastic Differential Equation:
Xt+1 = Xt − γt+1∇U(Xt) + √ 2γt+1ξt+1 (21)
With (ξt)t i.i.d N (0, Id) and (γt)t constant or decreasing towards 0. L-smoothness of U gives existence and uniqueness of a solution. Langevin MC can be seen as the sampling analog of gradient descent in optimization. In this work, we consider a projected version of the Langevin algorithm since we need to sample within some `∞ balls. Such an algorithm has been analyzed by Bubeck et al. [2018] in the case where U(x) is convex. In our practical setting we will consider Ui(x̃) = −λ`(fθ(x̃), yi)) for x̃ ∈ B (xi) , i ∈ [n] which are non-convex function. However, some results have been proven in that context by Ma et al. [2019]. Moreover, the Langevin algorithm has been recently used with great success in the context of diffusion models for deep learning for which the function U is not convex (see [Weng, 2021] for an overview).

heading: 4.2 PRACTICAL SETTING
text: As described in Algorithm 1, the training process has two loops:
1. Given a minibatch (xi, yi)i∈B , the inner loop samples the adversarial distributions qi(x) against the current classifier fθ via Langevin MC where each samples are then projected onto Bi( ) (operator PBi( )) and onto the space X (operator PX ). It allows us to estimate∇g.
2. The outer loop consists of the stochastic gradient descent step (20).
Sign of the Gradient. Similarly to standard adversarial training and attack methods we use the sign of the gradient of g to update θ. It can be motivated by the fact that the sign of gradient is well suited to the geometry defined by the `∞ ball since it corresponds to the steepest descent direction [Boyd et al., 2004] in the `∞ geometry [Balles et al., 2020].
Reusing the Examples. In practice, we restart the Langevin MC from the adversarial examples found at the previous iterations, this allow us to only use one step of Langevin MC in the inner loop and significantly speed-up training. This idea is justified by the fact that the distribution padv(x̃, y) ∝ exp(λ`(fθ(x̃), y)) is actually a continuous function of θ. It can be seen with duality argument from (12) where the function hθ(π) is strictly concave with respect to π which implies the continuity of θ 7→ arg maxπ hθ(π). We leave as a future work the formalization of this argument.
5 EXPERIMENTAL RESULTS Algorithm 1 Adversarial Transport with Langevin
1: input: dataset (xi, yi)ni=1, step-size: η, number of adversarial examples: K, noise variance σ. 2: Initialization: x̃i,k = xi , i ∈ [n], k ∈ [K] 3: for n : nb of steps do 4: Sample a minibatch: (xi, yi)i∈B , B ⊂ [n] 5: Load the attacks: x̃(0)i,k ← x̃i,k, i ∈ B, k ∈ [K] 6: for T : nb langevin iter do 7: for i ∈ B, k ∈ [K] do 8: x̃(t+1)i,k ← x̃ (t) i,k + η sign(∇x`(fθ(x̃ (t+1) i,k , yi)) 9: x̃(t+1)i,k ← PBi( )[x̃ (t+1) i,k + σξ]
10: x̃(t+1)i,k ← PX [x̃ (t+1) i,k ] 11: ∇θg = 1|B|K ∑ i∈B,k∈[K]∇θ`(fθ(x̃ (t+1) i,k , yi)) 12: θ ← θ − η∇θg 13: Save the attacks: x̃i,k ← x̃(T )i,k , i ∈ B, k ∈ [K] 14: Return: θ
We investigate the Adversarial Transport Algorithm at training robust classifiers (for a given hypothesis class) against adversarial attacks on MNIST and CIFAR-10.
Experimental setup The experiments are realized on MNIST and CIFAR-10. We perform all attacks and training with = 0.3 for MNIST and = 8.0 for CIFAR-10 (w.r.t. to the `∞ norm). We train our robustly trained classifier using stochastic gradient descent with the cross-entropy loss. We use a learning rate lr = 0.1 in the case of Adversarial Transport and update θ with the sign of the gradient.
For both datasets, we train our classifier with 100 epochs, a batch size of 100. For Langevin MC parameters, we take K = 1, ηl(λ) = 0.2 and σ = 0.2 (i.e. λ = 2ηlσ2 = 10). In theory, we must take λ big enough to have a good approximate of the solution. Appendix B.1 shows that in practice λ = 10 is the best value to ensure convergence of our algorithm.
Baselines We test our robust classifier against first-order attacks: Fast Gradient Sign Method (FGSM) attacks [Goodfellow et al., 2014; Szegedy et al., 2014], Projected Gradient Descent (PGD) attacks with 40 iterations (PGD 40) and PGD attacks with 100 iterations (PGD 100) [Madry et al., 2017; 2018]. We compare those results with the performance of classifiers adversarially trained with PGD [Goodfellow et al., 2014; Madry et al., 2017; 2018] on the same attacks (we trained PGD classifiers according to the method described in the paper and use the same parameters: lr = 0.01, 100 epochs, trained with PGD 40). All the attacks are generated via the library Advertorch of Pytorch3. The attacks are `∞ bounded. Additional details concerning the tuning of hyperparameters and hypothesis classes used are given in the Appendix B.14. We evalute white-box attacks (i.e. we have access to the gradient of the model we want to attack). The results are provided below:

heading: 5.1 PERFORMANCE ON MNIST
text: We first compare both methods on MNIST, the architecture is the same for both frameworks and is described in the Appendix B.2. We make two main observations, first training the model using Langevin improves the overall robustness of the classifier against all attackers we tested against as shown in Table 1. Secondly, by re-using the samples from the previous iterations we converge much
3https://github.com/BorealisAI/advertorch.git 4Code : https://anonymous.4open.science/r/Adversarial-Training-BCA4
faster, indeed for each update of the classifiers we only need to do one back-propagation instead. This leads to a very important speed up as observed in Fig 2.

heading: 5.2 PERFORMANCE ON CIFAR-10

heading: 6 CONCLUSION
text: In this paper, we introduce the Adversarial Transport Framework. We derived this framework from Adversarial Training relaxation through regularized Distributionally Robust Optimization (DRO) with∞-∞-Wasserstein distance. The outcome of this work provides a close form of the optimal adversarial distribution against a given classifier which can be sampled via Langevin Monte-Carlo. From that, we have designed an algorithm that optimally trains (for a given hypothesis class) a classifier against adversarial examples. The major asset of our work, which surely justifies these outstanding results, is that it considers the problem at the scale of the entire dataset and not at the scale of the example.
Our algorithm brings several novelties: at each iteration, we perform a gradient ascent on the distribution and a gradient descent on the classifier. For this, we keep in memory the current distribution of adversarial examples and iterate on it at each step. In addition, only one iteration of Langevin MC is necessary at each step. As a result, our experiments show that the Adversarial Transport classifier outperforms PGD trained classifier on MNIST and CIFAR-10, but also that our algorithm allows us to train it much faster than with PGD thanks to the novelties described above.

heading: A PROOFS OF THEORETICAL RESULTS
text: Proposition 2.1. The adversarial training problem (1) can be formulated as a DRO problem (2) where:
P = {padv : ∃T : X → X , padv = T]pdata and ‖T (x)− x‖∞ ≤ , ∀x ∈ X} (22)
Proof of Proposition 2.1. Let us start with the original adversarial training problem:
min θ∈Rd E(x,y)∼pdata [ max‖x̃−x‖∞≤ `(fθ(x̃, y))] (23)
Let us call T (x) := x̃, thus, we have
E(x,y)∼pdata [ max‖T (x)−x‖∞≤ `(fθ(T (x)y))] = max T , ‖T (x)−x‖∞≤ , ∀x∈X E(x,y)∼pdata [`(fθ(T (x), y))]]
By definition of the pushforward measure we have that
E(x,y)∼pdata [ max‖T (x)−x‖∞≤ `(fθ(T (x)y))] = max T , ‖T (x)−x‖∞≤ , ∀x∈X E(x̃,y)∼T]pdata [`(fθ(x̃, y))]]
which conclude our proof since then it is equivalent to maximize over T or padv = T]pdata.
Proposition 3.1. The DRO problem (2) can be relaxed by considering coupling measure. In that case the constraint set P in Equation 2 take the form: Pconv = {padv : ∃π ∈ Π(pdata|padv) with supp(π) ⊂ {(x, y, x̃, y) | ‖x̃− x‖∞ ≤ , y ∈ Y }} .
Proof of Proposition 3.1. We will prove that
P ⊂ Pconv (24) and that Pconv is convex. First let us start by showing that,
P ⊂ Pconv. (25) Let us consider padv ∈ P . By definition of P there exists T : X → X such that padv = T]pdata and ‖T (x) − x‖∞ ≤ . Now, we can define the coupling measure πT := (Id, Id, T, Id)]pdata where (Id, Id, T, Id)(x, y) = (x, y, T (x), y). We can verify that πT ∈ Π(pdata|T]pdata) and that by definition of T , we have suppπT ⊂ {(x, y, x̃, y) s.t. ‖x̃− x‖∞ ≤ , x, x′ ∈ X , y ∈ Y }. Finally, let us prove that Pconv is convex. Let us consider p1, p2 ∈ Pconv and λ ∈ [0, 1]. By definition of Pconv , we know that there exists π1 ∈ Π(pdata|p1) and π2 ∈ Π(pdata|p2) such that supp(π1) and supp(π2) are included in {(x, y, x̃, y) s.t. ‖x̃− x‖∞ ≤ , x, x′ ∈ X , y ∈ Y }. By linearity of the marginalization we have that λπ1 + (1 − λ)π2 ∈ Π(pdata|λp1 + (1 − λ)p2). Moreoevr, we have that supp(λπ1 + (1 − λ)π2) = supp(π1) ∪ supp(π2) ⊂ {(x, y, x̃, y) s.t. ‖x̃ − x‖∞ ≤ , x, x′ ∈ X , y ∈ Y }. Thus we have λp1 +(1−λ)p2 ∈ Pconv . It concludes the fact that Pconv is convex.
Proposition 3.2 (convex relaxation of adversarial training). The convex DRO relaxation of adversarial training can be reformulated as
min θ∈Rd max padv∈B (pdata) E(x̃,y)∼padv [`(fθ(x̃, y)]
where B (pdata) = {p |W∞,∞(p, pdata) ≤ } and Wp,∞ is defined in (9).
Proof of Proposition 3.2. Under mild assumptions (see the assumption of [Villani, 2009, Prop 5.21]) B (pdata) = {p |W∞,∞(p, pdata) ≤ } = Pconv . padv ∈ Pconv ⇐⇒ ∃π ∈ Π(pdata|padv) with supp(π) ⊂ {(x, y, x̃, y) | ‖x̃− x‖∞ ≤ , y ∈ Y }
(26) ⇐⇒ ∃π ∈ Π(pdata|padv) with sup
(z,z̃)∈supp(π) ‖z − z̃‖∞ ≤ (27)
⇐⇒ min π∈Π(pdata|padv) sup (z,z̃)∈supp(π) ‖z − z̃‖∞ ≤ (28)
Note that the second equivalence is possible because < miny 6=y′ |y − y′| and the third one because the minimum is achieved by compactness of Π(pdata|padv) (see [Villani, 2009, Prop 5.21]).
Proposition 3.3. If λ→∞, then π∗λ → π∗.
Proof of Proposition 3.3. The proof is similar to the proof of Proposition 4.1 from Peyré and Cuturi [2019] since P is compact.
Proposition A.1. For any given θ ∈ Rd, the function hθ(π) = E(x̃,y)∼padv [`(fθ(x̃), y)] + 1λH(π) is strictly-concave and the constraints on P are convex.
Proof. P and F are convex sets: both constraints of P are linear, and is convex by F by assumptions. Moreover,
• hθ(π) is the sum of a concave term and a strongly concave term. Indeed:
– π → E(x̃,y)∼padv [`(fθ(x̃), y)] concave in π by linearity. – π → 1λH(π) is strongly concave in π.
• θ → hθ(π) is convex by convexity of l (e.g. mean squared loss, cross entropy loss, ...).
Proposition 3.4. For any given θ ∈ Rd, The optimization problem (12) has a unique solution,
π∗((x, y), (x̃, y)) ∝ pdata(x, y) exp(λ`(fθ(x̃), y))1‖x−x̃‖∞≤ 1ỹ=y . (29)
For a given natural example x with a label y, π(z, z̃) grows with the propensity of x̃ to be better than the other elements of Bx( ) (the `∞-ball of radius ) to fool the classifier. We then deduce the explicit form of the adversarial distribution:
p∗adv(x̃, y) = Ex∼px,data [pdata(y|x) exp(λ`(fθ(x̃),y))1‖x−x̃‖∞≤ ∫ x̃∈B (x) exp(λ`(fθ(x̃),y))dx̃ ]
π∗(z, z̃) ∝ pdata(x, y) exp(λ`(fθ(x̃), y))1‖x−x̃‖∞≤ 1ỹ=y .
Proof of Proposition 3.4. The objective function is concave and at the optimum π∗((x, y), (x̃, y)) > 0 for each (x, x̃, y) s.t. ‖x− x̃‖ ≤ . The objective function is C1 in the neighborhood of π∗. Thus, we can introduce dual variable α : R→ R s.t. ∇πL(π∗, α) = 0. The Lagrangian function L is:
L(π, α) = ∫ Z×Z `(fθ(x̃), y)dπ((x, y)(x̃, y))− 1 λ ∫ Z×Z (log(π((x, y), (x̃, y))− 1)dπ((x, y)(x̃, y))
+ ∫ Z×Z α(x, y) ( pdata(x, y)dx− ∫ Z×Z dπ((x, y)(x̃, y)) ) (30)
L(π, α) = ∫ Z×Z (`(fθ(x̃), y)− 1 λ (log(π((x, y)(x̃, y)))− 1)− α(x, y))dπ((x, y)(x̃, y))
+ ∫ Z α(x, y)pdata(x, y)dx
(31)
∂L(π, α))
∂π = `(fθ(x̃), y)−
1 λ log(π((x, y)(x̃, y)))− α(x, y) = 0 (32)
So at the optimum, for each ((x, y), (x̃, y)) s.t. ‖x − x̃‖ ≤ , we have π∗((x, y), (x̃, y)) = exp(λ(`(fθ(x̃), y))) exp(−λα(x, y))). In addition, we know
that ∫
(x̃,y)∈B ((x,y)) dπ((x, y), (x̃, y)) = pdata(x, y), thus exp(−λα ∗(x, y)) =
pdata(x, y) 1∫
x̃∈B (x) exp(λ(`(fθ(x̃),y)))dx̃
. Therefore, for each ((x, y), (x̃, y)) s.t. ‖x− x̃‖ ≤ :
π∗((x, y), (x̃, y)) = pdata(x, y) exp(λ(`(fθ(x̃), y)))∫
x̃∈B (x) exp(λ(`(fθ(x̃), y)))dx̃ 1y=ỹ
And π((x, y)(x̃, y)) = 0 for each ((x, y), (x̃, y)) s.t. ‖x− x̃‖ > , i.e.:
π∗((x, y), (x̃, y)) = pdata(x, y) exp(λ(`(fθ(x̃), y)))∫
x̃∈B (x) exp(λ(`(fθ(x̃), y))dx̃ 1‖x−x̃‖≤ 1y=ỹ
π∗((x, y)(x̃, y)) ∝ pdata(x, y) exp(λ`(fθ(x̃), y))1‖x−x̃‖∞≤ 1y=ỹ .
Therefore, we have that:
sup π L(π, α) =
1 λ + ∫ Z α(x, y)pdata(x, y)d(x, y) (33)
sup π L(π, α) =
1 λ − 1 λ ∫ Z pdata(x, y) log( pdata(x, y)∫ x̃∈B (x) exp(λ(`(fθ(x̃), y)))dx̃ )d(x, y) (34)
sup π L(π, α) =
1
λ (∫ Z pdata(z) log( ∫ x̃∈B (x) exp(λ(`(fθ(x̃), y)))dx̃)))dz − ∫ Z pdata(z) log(pdata(z))dz + 1 ) (35)
Proposition 3.5. Let us call E(x̃,y)∼padv [`(fθ(x̃), y)] + 1 λH(π) = ϕ(θ, π). If {fθ | θ ∈ Θ} is a convex set, then we have that
min θ∈Rd max π∈P ϕ(θ, π) = max π∈P min θ∈Rd ϕ(θ, π) (36)
where P = {padv : ∃π ∈ Π(px,data|x, px,adv) with π((z), (x̃, y)) = 0 , ∀x, x̃ ∈ X s.t. ‖x̃ − x‖∞ > }.
Proof. The proof is similar to the proof of Theorem 28 from Merigot and Thibert [2020].
Proposition 3.6. Let us assume that the datapoints xi are independently sampled from a distribution p over [0, 1]d that is absolutely continuous with respect to Lesbegue measure and has a upper-bounded value, i.e. p(x) ≤M , x ∈ [0, 1]d. Then P(∃i 6= j ∈ [n] , ‖x̃j − xi‖∞ ≤ ) = O(n2 d).
Proof of Proposition 3.6. Let us consider the quantity
P(∃i 6= j ∈ [n] , ‖x̃j − xi‖∞ ≤ ) ≤ n(n− 1)
2 P(‖x̃− x‖∞ ≤ ) (37)
≤ n(n− 1) 2 MV ol(B(x, )) (38) = n(n− 1)
2 M d (39)
Theorem 3.2 (Characterization of the solutions in the semi discrete case). For any λ > 0, the solution set of the regularized adversarial training problem (11) is:
θ∗ ∈ arg min 1 nλ n∑ i=1 log (∫ ||x̃−xi||≤ exp(λ`(fθ(x̃), yi))dx̃ ) =: arg min g(θ) , (40)
and under Assumption 3.1 the optimal adversarial distribution associated with this adversarial training problem is
padv(x̃, y) =  exp(λ`(fθ(x̃), y)) n ∫ x̃∈B (xi) exp(λ`(fθ(x̃), y))dx̃
if ∃ i ∈ [n] s.t. ‖xi − x̃‖∞ ≤
0 otherwise.
(41)
Proof of Theorem 3.2.
min fθ∈F max padv∈P
E(x,x̃,y)∼π(z,(x̃,y))[`(fθ(x̃), y)] + 1
λ H(π) (42)
From Proposition 3.5:
= min fθ∈F ( min α ( ∫ X α(x, y)pdata(x, y)dx) + 1 λ ) for α(x, y) = − 1 λ log( pdata(x, y)∫ x̃∈B (x) exp(λ(`(fθ(x̃), y))))dx̃ )
(43)
= min fθ∈F
1
λ (∫ X pdata(x, y) log( ∫ ‖x−x̃‖≤ exp(λ(`(fθ(x̃), y)))dx̃)dx− ∫ X pdata(x, y) log(pdata(x, y))dx+ 1 ) (44)
Finally, the probability distribution of the adversarial examples padv is written:
padv(x̃, y) = ∫ x∈X dπ((x, y, )(x̃, )) (45)
padv(x̃, y) = ∫ X pdata(x, y) exp(λ`(fθ(x̃), y)))∫ X exp(λ`(fθ(x̃), y)))dx̃ 1‖x−x̃‖≤ dx (46) padv(x̃, y) = Ex∼px,data [pdata(y|x) exp(λ`(fθ(x̃),y))1‖x−x̃‖∞≤ ∫ x̃∈B (x) exp(λ`(fθ(x̃),y)) ] (47)
In practice: ∀i pdatai = 1n , so we have:
padv(x̃, y) =  exp(λ`(fθ(x̃), y)) n ∫ x̃∈B (xi) exp(λ`(fθ(x̃), y))
if ∃ i ∈ [n] s.t. ‖xi − x̃‖∞ ≤
0 otherwise.
and then,
θ∗ ∈ arg min 1 nλ n∑ i=1 log (∫ ||x̃−xi||≤ exp(λ`(fθ(x̃), yi))dx̃ ) =: arg min g(θ) ,

heading: B ADDITIONAL RESULTS
text: B.1 TUNING OF HYPERPARAMETERS
In this section, we detail the tuning of different hyperparameters. Among them:
• T : The number of Langevin iterations for crafting adversaries during the training process. • σ: Represents the noise which is the particularity of the Langevin. Indeed, it differs from
the gradient descent by the addition of Gaussian noise. The noise allows adding randomness in the crafting of adversarial examples. Thus, the size of the noise, as well as its shape, are of primary importance in the performance of Langevin. For example, a too important noise will generate totally random examples and will erase the weight of the gradient.
• ηl = λ × γ: represents the learning rate of Langevin MC. The parameter represents the learning rate of Langevin.
In general, even if T ≥ 2, we only keep the last batch of adversarial examples for updating θ. Here, all the results are presented for T = 1 which gives the best results and the best computation time. A further study could analyze the influence of using more batches of adversarial examples at each epoch of the training. The results for the influence of σ and ηl(λ) are provided below:
The two curves are similar. We notice that the method converges only for small range of values of these hyperparameters. Regarding that λ = 2ηlσ2 , these experiments show that the best value for λ we can take is λ = 10. These graphs justify the fact that our whole study was conducted with ηl(λ) = 0.2 and σ = 0.2.
B.2 MODELS ARCHITECTURE
We study the influence of the architecture of the neural network on the performance of our model. We test our algorithm with the two models below. Model B is the one used by Madry et al. [2018] for the PGD framework.

Review summaries:
The authors present a connection between adversarial robustness and distributional robustness. A duality result is given linking the $\infinity$-Wasserstein distance to an entropy regularisation problem. The problem is then solved using a Langevan-sampling based algorithm.   

- This paper proposes using $\infty$-Wasserstein distributional robustness for improving model robustness. Specifically, to obtain a tractable solution, it adds an entropic regularization term to the primal form of $\infty$-Wasserstein distributional robustness. The Langevin algorithm is used to sample adversarial examples for adversarial training.  - Although the experimental results show the merit of the proposed method, the experiments are still humble with a lack of experiments on more impactful architectures such as WideResNet and comparison to other SOTA adversarial training methods.

This paper establishes the equivalence between the adversarial training problem (under infinity-norm) and the Distributionally robust optimization (DRO) problem with \infty-\infty-Wasserstein distance. Then they propose to use an entropic regularizer to find the regularized optimal adversarial distribution more efficiently. Numerical results on MNIST and CIFAR-10 validate the performance of the proposed method.