# A DISTRIBUTIONAL ROBUSTNESS PERSPECTIVE ON ADVERSARIAL TRAINING WITH THE ∞-WASSERSTEIN DISTANCE

**Anonymous authors**
Paper under double-blind review

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.

1 INTRODUCTION

We call adversarial example an input which is a human-imperceptible ϵ-perturbation[1] 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 max _x, y))]_ (1)
_θ∈R[d][ E][(][x,y][)][∼][p][data]_ [[]∥x˜−x∥∞≤ϵ _[ℓ][(][f][θ][(˜]_

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 _x_ _padv_ [[][ℓ][(][f]θ[(˜]x, y))] (2)
_θ∈R[d][ max]padv∈P_ [E][˜]∼

Note that while standard adversarial training aims to use the point-wise optimal adversarial ˜xj
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 ⊂** R[d]. We
will note B(X ) the Borel σ-algebra of X and M(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][)][.] R

R

2 ADVERSARIAL TRAINING, TRANSPORT, AND DISTRIBUTIONAL
ROBUSTNESS


In this work, we say that ˜x is an adversarial example of f at the data point (x, y) if _x˜_ _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), y) ._ (3)
_∈_ _x˜_ _x_ _ϵ_ _[ℓ][(][f][θ][(˜]_
_∥_ _−_ _∥∞≤_

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_ . In other words we have,
_∥_ _−_ _∥∞_ _≤_ _∀_ _∈X_
_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:_
= _padv :_ _T :_ _, padv = T♯pdata and_ _T_ (x) _x_ _ϵ,_ _x_ (5)
_P_ _{_ _∃_ _X →X_ _∥_ _−_ _∥∞_ _≤_ _∀_ _∈X}_

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


_c(x, T_ (x))dµ(x) subject to _ν = T♯µ ._ (6)


inf


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 ˜xj). 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.


-----

3 ADVERSARIAL TRANSPORT FORMULATION

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_ ( ), π(A ) = pdata(A) _and_ _B_ ( ), π( _B) = padv(B)_ (7)
_∀_ _∈B_ _X_ _× X_ _∀_ _∈B_ _X_ _X ×_
_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 (˜xj), 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.

3.1 INCORPORATING THE PROXIMITY CONSTRAINT TO THE COUPLING.

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:_
_conv =_ _padv :_ _π_ Π(pdata _padv) with supp(π)_ (x, y, ˜x, y) _x˜_ _x_ _ϵ, y_ _._
_P_ _{_ _∃_ _∈_ _|_ _⊂{_ _| ∥_ _−_ _∥∞_ _≤_ _∈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.

3.2 CONNECTION WITH ∞-WASSERSTEIN

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

1/p[′]

_Wp,p′_ (µ, ν) := inf _z_ _z˜_ _p_ _[dπ][(][z,][ ˜]z)_ _._ (8)
_π_ Π(µ,ν) _∥_ _−_ _∥[p][′]_
_∈_  [Z]Z×Z 

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˜_ _p ._ (9)
_∞_ _π∈Π(µ,ν)_ (z,z˜)∈supp(π) _∥_ _−_ _∥_

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 max _x,y)_ _padv_ [[][ℓ][(][f]θ[(˜]x, y)] (10)
_θ∈R[d]_ _padv∈Bϵ(pdata)_ [E][(˜] _∼_

_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≠ _y′ |y −_ _y′|_
which can always be achieved by reparametrizing the discrete labels.


-----

3.3 ENTROPY-REGULARIZED FORMULATION

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:

R


min max E(˜x,y) _padv_ [[][ℓ][(][f]θ[(˜]x), y)] + _λ[1]_ _[H][(][π][)][ .]_ (11)
_θ∈R[d]_ _s.t. pπ∈Π(advpdata∈Bϵ,p(padvdata)_ ) _∼_

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 πλ[∗]_
_→∞_ _[→]_ _[π][∗][.]_

3.4 SOLUTIONS TO THE ADVERSARIAL TRANSPORTATION PROBLEM


In this section, we study the general framework where the two measures pdata and padv are defined on
metric spaces X . 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θ(π) :=_ _π∈Π(pmaxdata,padv)_ E(˜x,y)∼padv [[][ℓ][(][f]θ[(˜]x), y)] + _λ[1]_ _[H][(][π][)][,]_ (12)
_s.t. ∃padv∈Bϵ(pdata)_

where _ϵ(pdata) =_ _p_ _W_ _,_ (p, pdata) _ϵ_ . For any given θ R[d], the function hθ is strictly_B_ _{_ _|_ _∞_ _∞_ _≤_ _}_ _∈_
concave 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 θ ∈** R[d], The optimization problem (12) has a unique solution,
_π[∗]((x, y), (˜x, ˜y))_ _pdata(x, y) exp(λℓ(fθ(˜x), y))1_ _x_ _x˜_ _ϵ[1]y=˜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(x˜∈Bλℓϵ ((xf)θ[exp(](˜x),y[λℓ]))[(]1[f]∥[θ]x[(˜]x−)x˜,y∥∞≤))dx˜ϵ []] (14)
R

From this proposition, we notice that if ˜x _x(ϵ), then π(z, ˜z) > 0, i.e. any examples which_
_∈B_
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(] _x˜∈Bϵ_ (x) [exp(]pdata[λ][(]([ℓ]x,y[(][f][θ])[(˜]x),y)))dx˜) [)]

(c.f. Appendix A for proof) and is convex w.r.t. this variable. Thus, we can express the originalR
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 min E(x,y)∼pdata [ _λ[1]_ [log(]Z||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(x˜∈Bλℓϵ ((xf)θ∗[exp(](˜x),y[λℓ]))[(][f]1[θ]∥[(˜]xx−),yx˜∥∞≤))dx˜ϵ []] (16)
R


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 (17)
_θ∈R[d][ max]π∈P_ _[ϕ][(][θ, π][) = max]π∈P_ _θ[min]∈R[d][ ϕ][(][θ, π][)]_

_conv =_ _padv :_ _π_ Π(pdata _padv) with supp(π)_ (x, y, ˜x, y) _x˜_ _x_ _ϵ, y_ _.._
_P_ _{_ _∃_ _∈_ _|_ _⊂{_ _| ∥_ _−_ _∥∞_ _≤_ _∈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].

3.5 PRACTICAL CASE: SEMI-DISCRETE ADVERSARIAL TRANSPORTATION PROBLEM

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 = _n[1]_ _ni_ _[δ][x]i[. However, even when considering empirical distributions, the dis-]_

tribution of adversarial examplesexample could be any point in theP _p ℓadv-ball of radius is an arbitrary measure on metric space ϵ ball from the initial point (for datapoint X as an adversarial xi we_
_∞_
call that ball _ϵ(xi)). Its analysis is thus similar to the continuous case. However, in such a practical_
_B_
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 ̸= 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_ = j [n], _x˜j_ _xi_ _ϵ) = O(n[2]ϵ[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:_

_n_

_θ[∗]_ arg min [1] log exp(λℓ(fθ(˜x), yi))dx˜ =: arg min g(θ), (18)
_∈_ _nλ_ Xi=1  [Z]||x˜−xi||≤ϵ 

_and under Assumption 3.1 the optimal adversarial distribution associated with this adversarial_
_training problem is_


exp(λℓ(fθ(˜x), y))

_x˜_ _ϵ(xi)_ [exp(][λℓ][(][f][θ][(˜]x), y))dx˜ _if ∃_ _i ∈_ [n] s.t. ∥xi − _x˜∥∞_ _≤_ _ϵ_ (19)
_∈B_

0 _otherwise._


_padv(˜x, y) =_


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 (˜xi,k) associated with the
datapoint xi.

4 ADVERSARIAL TRANSPORT ALGORITHM

We want to solve the minimization problem (40). We can solve this problem using gradient descent:


_e[λℓ][(][f][θ][(˜]x),yi))_
_Bϵ(xi∇)_ _θℓ(fθ(˜x), yi))_ _Bϵ(xi)_ _[e][λℓ][(][f][θ][(˜]x),yi))dx˜_ _[d]x[˜]_ (20)

R


_θ[t][+1]_ = θ[t] _η_ _θg where_ _θg = [1]_
_−_ _∇_ _∇_ _n_


_i=1_


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.

4.1 LANGEVIN MONTE CARLO

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 towardsp 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).

4.2 PRACTICAL SETTING

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 P _i(ϵ)) and onto the space_ (operator P ). It allows us to estimate _g._
_B_ _X_ _X_ _∇_


-----

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.

**Algorithm 1 Adversarial Transport with Langevin**
5 EXPERIMENTAL RESULTS

1: input: dataset (xi, yi)[n]i=1[, step-size:][ η][, number of]
adversarial examples: K, noise variance σ.

We investigate the Adversarial Trans-port Algorithm at training robust clas- 2:3: Initialization: for n : nb of steps ˜xi,k = do xi, i ∈ [n], k ∈ [K]
sifiers (for a given hypothesis class)against adversarial attacks on MNIST 4: Sample a minibatch: (xi, yi)i∈B, B ⊂ [n]
and CIFAR-10. 5:6: Load the attacks:for T : nb langevin iter ˜x[(0)]i,k _[←] dox[˜]i,k, i ∈_ _B, k ∈_ [K]

**Experimental setup The experiments** 7: **for i ∈** _B, k ∈_ [K] do
are realized on MNIST and CIFAR-10.
We perform all attacks and training with 8: _x˜[(]i,k[t][+1)]_ _←_ _x˜[(]i,k[t][)]_ [+][ η][ sign(][∇][x][ℓ][(][f][θ][(˜]x[(]i,k[t][+1)], yi))
_ϵ = 0.3 for MNIST and ϵ = 8.0 for_ 9: _x˜[(]i,k[t][+1)]_ _P_ _i(ϵ)[˜x[(]i,k[t][+1)]_ + σξ]

_←_ _B_

CIFAR-10 (w.r.t. to thetrain our robustly trained classifier us-ing stochastic gradient descent with the ℓ∞ norm). We 10:11: _∇θx˜g[(]i,k =[t][+1)]|B←1|KPX [˜i∈xB,k[(]i,k[t][+1)]∈[]K]_ _[∇][θ][ℓ][(][f][θ][(˜]x[(]i,k[t][+1)], yi))_
cross-entropy loss. We use a learning 12: _θ_ _θ_ _η_ _θg_

_←_ _−_ _∇_ P

Transport and updaterate lr = 0.1 in the case of Adversarial θ with the sign of 14:13: Return:Save the attacks: θ ˜xi,k ← _x˜[(]i,k[T][ )][, i][ ∈]_ _[B, k][ ∈]_ [[][K][]]
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]σ[η][2][l][ = 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 Pytorch[3]. The
attacks are ℓ bounded. Additional details concerning the tuning of hyperparameters and hypothesis
_∞_
classes used are given in the Appendix B.1[4]. 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:

5.1 PERFORMANCE ON MNIST

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.


80

70

60

50

40

30

20

10


|Performance|Langevin|PGD|
|---|---|---|
|Train Adversarial Clean test set|98.48% 99.16%|94.81% 98.82%|
|FGSM PGD 40 PGD 100 Autoattack|96.53% 93.12% 91.87% 88.55%|94.95% 92.28% 91.18% 89.10%|


Performance Langevin PGD

Train Adversarial 98.48% 94.81%

Clean test set 99.16% 98.82%

FGSM 96.53% 94.95%

PGD 40 93.12% 92.28%

PGD 100 91.87% 91.18%

Autoattack 88.55% 89.10%

Table 1: Comparison of the performance
for MNIST of robust classifiers trained with
Langevin and PGD (with 40 iterations). The
architecture of the two classifiers is architecture
A. The attacks are FGSM, PGD 40, PGD 100,
and autoattack (Croce and Hein [2020]). The
classifier trained with Langevin is more robust
than the one trained with PGD for each measure
except Autoattack.

|Col1|Col2|Model|traine|d using:|Col6|
|---|---|---|---|---|---|
||||Lan|gevin||
||||PG|D||
|||||||
|||||||
|||||||
|||||||
|||||||
|||||||


25 50 75 100 125 150 175 200


Number of backprops

Figure 1: Comparison of Langevin and PGD adversarial
training on MNIST. We plot the error rate against FGSM
as a function of the number of backprops. We observe that
Langevin converges much faster as it only needs to compute
1 gradient per update of the classifier by being able to re-use
the samples from the previous iterations. After 8 iterations,
Langevin achieves a score that is not even reached by PGD
after 1600 iterations.


5.2 PERFORMANCE ON CIFAR-10


70

65

60

55

50

45

|Performance|Langevin|PGD|
|---|---|---|
|Train Adversarial Clean test set|99.82% 78.72%|99.38% 68.93%|
|FGSM PGD 40 PGD 100|53.40% 49.57% 49.50%|45.58% 44.70% 43.74%|


Performance Langevin PGD

Train Adversarial 99.82% 99.38%

Clean test set 78.72% 68.93%

FGSM 53.40% 45.58%

PGD 40 49.57% 44.70%

PGD 100 49.50% 43.74%


Table 2: Comparison of the performance for
CIFAR-10 of robust classifiers trained with
Langevin and PGD (with 40 iterations). The architecture of the two classifiers is RESTNET18.
The attacks are FGSM, PGD 40, and PGD
100. As for MNIST, the classifier trained with
Langevin is much more robust than the one
trained with PGD for each measure.

6 CONCLUSION

|Model trained using: PGD Langevin|Col2|Col3|Col4|Col5|
|---|---|---|---|---|
|||Model|traine PG|d using: D|
||||Lan|gevin|
||||||
||||||
||||||
||||||


100 200 300 400 500 600 700 800 900


Number of backprops

Figure 2: Comparison of Langevin and PGD adversarial
training on CIFAR. We plot the error rate against FGSM
as a function of the number of backprops. We observe that
Langevin converges much faster as it only needs to compute
1 gradient per update of the classifier by being able to re-use
the samples from the previous iterations.


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.


-----

REFERENCES

A. Athalye, L. Engstrom, and K. K. A. Ilyas. Synthesizing robust adversarial examples. Synthesizing
_robust adversarial examples. In The Thirty-fifth International Conference on Machine Learning_
_(ICML), 2018._

L. Balles, F. Pedregosa, and N. L. Roux. The geometry of sign gradient descent. arXiv preprint
_arXiv:2002.08056, 2020._

A. Ben-Tal and A. Nemirovski. Robust convex optimization. Math Oper Res, 23, pp. 769–805, 1998.

J. Blanchet and K. Murthy. Quantifying distributional model risk via optimal transport. Mathematics
_of Operations Research, 44(2):565–600, 2019._

J. Bose, G. Gidel, H. Berard, A. Cianflone, P. Vincent, S. Lacoste-Julien, and W. Hamilton. Adversarial example games. Advances in Neural Information Processing Systems, 33, 2020.

S. Boyd, S. P. Boyd, and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.

S. Bubeck, R. Eldan, and J. Lehec. Sampling from a log-concave distribution with projected langevin
monte carlo. Discrete & Computational Geometry, 2018.

T. Champion, L. de Pascale, and P. Juutinen. The ∞-wasserstein distance: local solutions and
existence of optimal transport map. SIAM Journal on Mathematical Analysis, 2008.

E. Chouzenoux, H. Gérard, and J. Pesquet. General risk measures for robust machine learning.
_Foundations of Data Science 1, 249, 2019._

F. Croce and M. Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse
parameter-free attacks. In ICML, 2020.

M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Adv. in Neural
_Information Processing Systems, pages 2292–2300, 2013a._

M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transportation distances. Advances
_in Neural Information Processing Systems 26, pages 2292–2300, 2013b._

E. Delage and Y. Ye. Distributionally robust optimization under moment uncertainty with application
to data-driven problems. Operations research, 2010.

J. Duchi and H. Namkoong. Stochastic gradient methods for distributionally robust optimization with
fdivergences. In Advances in neural information processing systems, pp. 2208–2216, 2016.

J. Duchi and H. Namkoong. Learning models with uniform performance via distributionally robust
optimization. arXiv preprint arXiv:1810.08750, 2018.

J. Duchi, P. Glynn, and H. Namkoong. Statistics of robust optimization: A generalized empirical
likelihood approach. arXiv preprint arXiv:1610.03425, 2016.

A. Durmus and E. Moulines. High-dimensional bayesian inference via the unadjusted langevin
algorithm. arXiv:1605.01559, 2016.

E.Wong, F. R. Schmidt, and J. Z. Kolter. Wasserstein adversarial examples via projected sinkhorn
iterations. Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6808_6817,, 2019._

R. Gao, X. Chen, and A. J. Kleywegt. Wasserstein distributional robustness and regularization in
statistical learning. arXiv preprint arXiv:1712.06050v2, 2017.

A. Genevay, M. Cuturi, G. Peyré, and F. Bach. Stochastic optimization for large-scale optimal
transport. NeurIPS, 2016.

G. Gidel, D. Balduzzi, W. Czarnecki, M. Garnelo, and Y. Bachrach. A limited-capacity minimax
theorem for non-convex games or: How i learned to stop worrying about mixed-nash and love
neural nets. In International Conference on Artificial Intelligence and Statistics, pages 2548–2556.
PMLR, 2021.


-----

I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples.
_arXiv:1412.6572, 2014._

L. V. Kantorovich. A new method of solving of some classes of extremal problems. In Dokl. Akad.
_Nauk SSSR, volume 28, pages 211–214, 1940._

A. Kurakin, I. Goodfellow, and S. Bengio. Adversarial machine learning at scale. arXiv:1611.01236,
2016.

H. Lam. Recovering best statistical guarantees via the empirical divergence- based distributionally
robust optimization. Operations Research, 2018.

X. Ma, B. Li, Y. Wang, S. M. Erfani, S. Wijewickrema, M. E. Houle, G. Schoenebeck, D. Song, and
J. Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. ICLR 2018,
2018.

Y.-A. Ma, Y. Chen, C. Jin, N. Flammarion, and M. I. Jordan. Sampling can be faster than optimization.
_Proceedings of the National Academy of Sciences, 2019._

A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant
to adversarial attacks. arXiv:1706.06083 [stat.ML], 2017.

A. Madry, A. M. L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to
adversarial attacks. In International Conference on Learning Representations, 2018.

Q. Merigot and B. Thibert. Optimal transport: discretization and algorithms. 2020.

S. Moosavi-Dezfooli, A. Fawzi, and P. Frossard. Deepfool: a simple and accurate method to fool
deep neural networks. Proceedings of the IEEE Conference on Computer Vision and Pattern
_Recognition, pages 2574–2582, 2016._

A. Nguyen, J. Yosinski, and J. Clune. Deep neural networks are easily fooled: High confidence
predictions for unrecognizable images. In Proceedings of the IEEE Conference on Computer
_Vision and Pattern Recognition, pp. 427–436, 2015a._

A. Nguyen, J. Yosinski, and J. Clune. Deep neural networks are easily fooled: High confidence
predictions for unrecognizable images. Computer Vision and Pattern Recognition (CVPR 2015).
_IEEE, 2015b._

N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami. The limitations of
deep learning in adversarial settings. Security and Privacy (EuroS&P), 2016 IEEE European
_Symposium on, pages 372–387, 2016a._

N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation as a defense to adversarial
perturbations against deep neural networks. Security and Privacy (SP), 2016 IEEE Symposium on,
_pages 582–597. IEEE, 2016b._

G. Peyré and M. Cuturi. Computational optimal transport. Foundations and Trends in Machine
_Learning, vol. 11, no. 5-6, pp. 355-607, 2019._

H. Rahimian and S. Mehrotra. Distributionally robust optimization: a review. arXiv preprint
_arXiv:1908.05659, 2019._

A. I. S. Santurkar, D. Tsipras, L. Engstrom, B. Tran, and A. Madry. Adversarial examples are not
bugs, they are features. arXiv:1905.02175, 2019.

A. Sinha, H. Namkoong, R. Volpi, and J. Duchi. Certifying some distributional robustness with
principled adversarial training. ICLR, 2018.

R. Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann.
_Math. Statist., 35:876–879, 1964._

Y. Song, T. Kim, S. Nowozin, S. Ermon, and N. Kushman. Pixeldefend: Leveraging generative
models to understand and defend against adversarial examples. ICLR 2018, 2017.


-----

M. Staib and S. Jegelka. Distributionally robust deep learning as a generalization of adversarial
training. In NIPS Machine Learning and Computer Security Workshop, 2017.

L. Sun, M. Tan, and Z. Zhou. A survey of practical adversarial example attacks. Cybersecurity,
_1(1):9, 2018._

C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing
properties of neural networks. International Conference on Learning Representations (ICLR),
2014.

F. Tramer, A. Kurakin, N. Papernot, I. Goodfellow, D. Boneh, and P. McDaniel. Ensemble adversarial
training: Attacks and defenses. International Conference on Learning Representations (ICLR),
2017.

F. Tramèr, A. Kurakin, N. Papernot, D. Boneh, and P. McDaniel. Ensemble adversarial training:
Attacks and defenses. arXiv:1705.07204 [stat.ML], 2017.

C. Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2003.

C. Villani. Optimal transport: old and new. Springer, 2009.

L. Weng. What are diffusion models? _lilianweng.github.io/lil-log, 2021._ [URL https:](https://lilianweng.github.io/lil-log/2021/07/11/diffusion-models.html)
[//lilianweng.github.io/lil-log/2021/07/11/diffusion-models.html.](https://lilianweng.github.io/lil-log/2021/07/11/diffusion-models.html)

A. Wilson. The use of entropy maximizing models, in the theory of trip distribution, mode split and
route split. Journal of Transport Economics and Policy, pages 108–126, 1969.

S. Zagoruyko and N. Komodakis. Wide residual networks. 2017.

T. Zheng, C. Chen1, and K. Ren. Distributionally adversarial attack. The Thirty-Third AAAI
_Conference on Artificial Intelligence, 2019._


-----

A PROOFS OF THEORETICAL RESULTS

**Proposition 2.1. The adversarial training problem (1) can be formulated as a DRO problem (2)**
_where:_

= _padv :_ _T :_ _, padv = T♯pdata and_ _T_ (x) _x_ _ϵ,_ _x_ (22)
_P_ _{_ _∃_ _X →X_ _∥_ _−_ _∥∞_ _≤_ _∀_ _∈X}_

_Proof of Proposition 2.1. Let us start with the original adversarial training problem:_

min max _x, y))]_ (23)
_θ∈R[d][ E][(][x,y][)][∼][p][data]_ [[]∥x˜−x∥∞≤ϵ _[ℓ][(][f][θ][(˜]_

Let us call T (x) := ˜x, thus, we have

E(x,y) _pdata_ [ max max
_∼_ _∥T (x)−x∥∞≤ϵ_ _[ℓ][(][f][θ][(][T]_ [(][x][)][y][))] =] _T, ∥T (x)−x∥∞≤ϵ, ∀x∈X_ [E][(][x,y][)][∼][p][data] [[][ℓ][(][f][θ][(][T] [(][x][)][, y][))]]]

By definition of the pushforward measure we have that

E(x,y) _pdata_ [ max max _x,y)_ _T♯pdata_ [[][ℓ][(][f]θ[(˜]x, y))]]
_∼_ _∥T (x)−x∥∞≤ϵ_ _[ℓ][(][f][θ][(][T]_ [(][x][)][y][))] =] _T, ∥T (x)−x∥∞≤ϵ, ∀x∈X_ [E][(˜] _∼_

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:_

_conv =_ _padv :_ _π_ Π(pdata _padv) with supp(π)_ (x, y, ˜x, y) _x˜_ _x_ _ϵ, y_ _._
_P_ _{_ _∃_ _∈_ _|_ _⊂{_ _| ∥_ _−_ _∥∞_ _≤_ _∈Y }}_

_Proof of Proposition 3.1. We will prove that_

_conv_ (24)
_P ⊂P_

and that Pconv is convex. First let us start by showing that,

_conv._ (25)
_P ⊂P_

Let us considerand _T_ (x) _x padv ∈Pϵ. Now, we can define the coupling measure. By definition of P there exists T : X →X π such thatT := (Id, I padvd, T, I = Td)♯♯ppdatadata_
_∥_ _−_ _∥∞_ _≤_
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 thatof _conv, we know that there exists Pconv is convex. Let us consider π1_ Π(pdata _p1) and p π1, p2_ 2 ∈PΠ(pconvdata andp2) λ such that ∈ [0, 1] supp(. By definitionπ1) and
supp( P _π2) are included in {(x, y, ˜x, y) ∈ s.t. ∥x˜ −_ _x|_ _∥∞_ _≤_ _ϵ, x, x ∈_ _[′]_ _∈X, y|_ _∈Y }. By linearity of the_
marginalization we have thatthat supp(λπ1 + (1 _λ)π2) = supp( λπ1 + (1π −1)_ _λ)supp(π2 ∈_ Π(π2)pdata|(λpx, y,1 + (1 ˜x, y −) s.t.λ)p2x˜). Moreoevr, we havex _ϵ, 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 adversar-**
_ial training can be reformulated as_

min max _x,y)_ _padv_ [[][ℓ][(][f]θ[(˜]x, y)]
_θ∈R[d]_ _padv∈Bϵ(pdata)_ [E][(˜] _∼_

_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 (z,z˜)∈supsupp(π) _∥z −_ _z˜∥∞_ _≤_ _ϵ_ (27)

min sup _z_ _z˜_ _ϵ_ (28)
_⇐⇒_ _π∈Π(pdata|padv)_ (z,z˜)∈supp(π) _∥_ _−_ _∥∞_ _≤_

Note that the second equivalence is possible because ϵ < miny≠ _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 θ** R[d], 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 θ ∈** R[d], The optimization problem (12) has a unique solution,

_π[∗]((x, y), (˜x, y))_ _pdata(x, y) exp(λℓ(fθ(˜x), y))1_ _x_ _x˜_ _ϵ[1]y˜=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(x˜∈Bλℓϵ ((xf)θ[exp(](˜x),y[λℓ]))[(]1[f]∥[θ]x[(˜]x−)x˜,y∥∞≤))dx˜ϵ []]
R

_π[∗](z, ˜z)_ _pdata(x, y) exp(λℓ(fθ(˜x), y))1_ _x_ _x˜_ _ϵ[1]y˜=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 C[1]_ in the neighborhood of π[∗]. Thus,
we can introduce dual variable α : R → R s.t. ∇πL(π[∗], α) = 0. The Lagrangian function L is:


_ℓ(fθ(˜x), y)dπ((x, y)(˜x, y))_
_−_ _λ[1]_
_Z×Z_


_L(π, α) =_


(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))_
_Z×Z_


(30)


(ℓ(fθ(˜x), y) _x, y)))_ 1) _α(x, y))dπ((x, y)(˜x, y))_
_−_ _λ[1]_ [(log(][π][((][x, y][)(˜] _−_ _−_
_Z×Z_ (31)

_α(x, y)pdata(x, y)dx_


_L(π, α) =_


_∂L(π, α))_

= ℓ(fθ(˜x), y) _x, y)))_ _α(x, y) = 0_ (32)
_∂π_ _−_ _λ[1]_ [log(][π][((][x, y][)(˜] _−_

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
_−_


-----

thatpdata(x, yR(˜x,y) )∈Bx˜∈Bϵϵ(((xx,y) [exp(])) _[dπ][λ]1[(][((][ℓ][(][f][x, y][θ][(˜]x)[)],y[,][ (˜])))x, ydx˜))[. Therefore, for each]=_ _pdata(x, y[ ((][x, y]),_ [)][,][ (˜]thusx, y)) s.t.exp( ∥−x −λαx˜[∗]∥≤(x, yϵ)):

R

exp(λ(ℓ(fθ(˜x), y)))
_π[∗]((x, y), (˜x, y)) = pdata(x, y)_ _y_

_x˜_ _ϵ(x)_ [exp(][λ][(][ℓ][(][f][θ][(˜]x), y)))dx˜ **[1][y][=˜]**
_∈B_

R


And π((x, y)(˜x, y)) = 0 for each ((x, y), (˜x, y)) s.t. ∥x − _x˜∥_ _> ϵ, i.e.:_

exp(λ(ℓ(fθ(˜x), y)))
_π[∗]((x, y), (˜x, y)) = pdata(x, y)_ _x_ _ϵ[1]y=˜y_

_x˜_ _ϵ(x)_ [exp(][λ][(][ℓ][(][f][θ][(˜]x), y))dx˜ **[1][∥][x][−][˜]∥≤**
_∈B_

R

_π[∗]((x, y)(˜x, y))_ _pdata(x, y) exp(λℓ(fθ(˜x), y))1_ _x_ _x˜_ _ϵ[1]y=˜y_ _[.]_
_∝_ _∥_ _−_ _∥∞≤_

Therefore, we have that:


sup
_π_ _[L][(][π, α][) = 1]λ_ [+]

Z

sup
_π_ _[L][(][π, α][) = 1]λ_ _λ_

_[−]_ [1]

sup
_π_ _[L][(][π, α][) = 1]λ_

Z


_α(x, y)pdata(x, y)d(x, y)_ (33)

_pdata(x, y)_
_pdata(x, y) log(_ (34)

ZZ _x˜∈Bϵ(x)_ [exp(][λ][(][ℓ][(][f][θ][(˜]x), y)))dx˜ [)][d][(][x, y][)]

R


_pdata(z) log(_


exp(λ(ℓ(fθ(˜x), y)))dx˜)))dz
_x˜∈Bϵ(x)_ _−_


_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 (36)
_θ∈R[d][ max]π∈P_ _[ϕ][(][θ, π][) = max]π∈P_ _θ[min]∈R[d][ ϕ][(][θ, π][)]_

_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_ = j [n], _x˜j_ _xi_ _ϵ) = O(n[2]ϵ[d])._
_≤_ _∈_ _∃_ _̸_ _∈_ _∥_ _−_ _∥∞_ _≤_

_Proof of Proposition 3.6. Let us consider the quantity_


P( _i_ = j [n], _x˜j_ _xi_ _ϵ)_
_∃_ _̸_ _∈_ _∥_ _−_ _∥∞_ _≤_ _≤_ _[n][(][n][ −]2_ [1)]

_≤_ _[n][(][n][ −]2_ [1)]

= _[n][(][n][ −]_ [1)]


P( _x˜_ _x_ _ϵ)_ (37)
_∥_ _−_ _∥∞_ _≤_

_MV ol(B(x, ϵ))_ (38)

_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:_

_n_

_θ[∗]_ arg min [1] log exp(λℓ(fθ(˜x), yi))dx˜ =: arg min g(θ), (40)
_∈_ _nλ_ Xi=1  [Z]||x˜−xi||≤ϵ 

_and under Assumption 3.1 the optimal adversarial distribution associated with this adversarial_
_training problem is_


exp(λℓ(fθ(˜x), y))

_x˜_ _ϵ(xi)_ [exp(][λℓ][(][f][θ][(˜]x), y))dx˜ _if ∃_ _i ∈_ [n] s.t. ∥xi − _x˜∥∞_ _≤_ _ϵ_ (41)
_∈B_

0 _otherwise._

min _x,y)_ _π(z,(˜x,y))[[][ℓ][(][f]θ[(˜]x), y)] + [1]_ (42)
_fθ∈F_ _padv[max]∈P_ [E][(][x,][˜] _∼_ _λ_ _[H][(][π][)]_


_padv(˜x, y) =_ _n_



_Proof of Theorem 3.2._

From Proposition 3.5:


_α(x, y)pdata(x, y)dx) + [1]_


_pdata(x, y)_

for _α(x, y) =_
_−_ _λ[1]_ [log(] _x˜_ _ϵ(x)_ [exp(][λ][(][ℓ][(][f][θ][(˜]x), y))))dx˜ [)]

_∈B_

(43)

R


= min
_fθ∈F_

= min
_fθ∈F_


min
_α_ [(]



_pdata(x, y) log(_


exp(λ(ℓ(fθ(˜x), y)))dx˜)dx
_∥x−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) =_ _dπ((x, y, )(˜x, ))_ (45)
Zx∈X

exp(λℓ(fθ(˜x), y)))

_padv(˜x, y) =_ _pdata(x, y)_ _x_ _ϵ[dx]_ (46)
ZX _X_ [exp(][λℓ][(][f][θ][(˜]x), y)))dx˜ [1][∥][x][−][˜]∥≤

_padv(˜x, y) = Ex∼px,data_ [pdataR (y|x) exp(x˜∈Bλℓϵ((fxθ)(˜[exp(]x),y))[λℓ]1[(]∥[f]x[θ]−[(˜]xx˜)∥∞≤,y)) _ϵ_ []] (47)
R


In practice: ∀i _pdatai =_ _n[1]_ [, so we have:]


exp(λℓ(fθ(˜x), y))

_x˜_ _ϵ(xi)_ [exp(][λℓ][(][f][θ][(˜]x), y)) if ∃ _i ∈_ [n] s.t. ∥xi − _x˜∥∞_ _≤_ _ϵ_
_∈B_

0 otherwise.


_padv(˜x, y) =_

and then,


_n_

log exp(λℓ(fθ(˜x), yi))dx˜ =: arg min g(θ),

Xi=1  [Z]||x˜−xi||≤ϵ 


_θ[∗]_ arg min [1]
_∈_ _nλ_


B ADDITIONAL RESULTS

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:

Figure 3: Influence of σ (noise_scale) on the performance of the classifier when training with
Adversarial Transport framework with architecture A. These results are for T = 1 and ηl(λ) = 0.2.
We did the same experiment with other values of ηl(λ) but whatever the value of σ, ηl(λ) = 0.2
gives the best result.

Figure 4: Influence of ηl(λ) (eta_langevin) on the performance of the classifier when training with
Adversarial Transport framework with architecture A. These results are for T = 1 and σ = 0.2. We
did the same experiment with other values of σ but whatever the value of ηl(λ), σ = 0.2 gives the
best result.

The two curves are similar. We notice that the method converges only for small range of values
of these hyperparameters. Regarding that λ = [2]σ[η][2][l][, 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.


-----

Architecture A
Conv(1,64,5)
ReLU()
Conv(64,64,5)
ReLU()
Dropout(0.25)
Linear(64 × 20 × 20, 128)
Dropout(0.5)
Linear(128,10)


|Performance|Langevin|PGD|
|---|---|---|
|Train Adversarial Clean test set|98.48% 99.16%|94.81% 98.82%|
|FGSM PGD 40 PGD 100|96.53% 93.12% 91.87%|94.95% 92.28% 91.18%|


Performance Langevin PGD

Train Adversarial 98.48% 94.81%

Clean test set 99.16% 98.82%

FGSM 96.53% 94.95%

PGD 40 93.12% 92.28%

PGD 100 91.87% 91.18%


Table 3: Comparison of the performance of robust classifiers trained with the Adversarial Transport
framework (Langevin) and PGD (trained with 40 iterations). The architecture of the two classifiers is
the above architecture A. The robustness of these two models is tested against FGSM attacks, PGD
with 40 iterations (PGD 40) and PGD with 100 iterations (PGD 100). The trained classifier with
Langevin is more robust than the one with PGD.


Architecture B
Conv(1,32,3,padding = 1)
ReLU()
Conv(32,64,3, padding = 1, stride = 2)
ReLU()
Conv(32,64,3, padding = 1)
ReLU()
Conv(32,64,3, padding = 1)
ReLU()
Flatten()
Linear(7 × 7 × 64, 100)
ReLU()
Linear(100,10)


|Performance|Langevin|
|---|---|
|Train Adversarial Clean test set|99.42% 99.10%|
|FGSM PGD 40 PGD 100|97.73% 94.82% 94.18%|


Performance Langevin

Train Adversarial 99.42%

Clean test set 99.10%

FGSM 97.73%

PGD 40 94.82%

PGD 100 94.18%


Table 4: Performance of robust classifiers trained with the Adversarial Transport framework
(Langevin) with architecture B. The robustness of this model is tested against FGSM attacks, PGD
with 40 iterations (PGD 40) and PGD with 100 iterations (PGD 100). The results are better than for
architecture A. Especially, we notice that there is no loss of performance between PGD 40 attacks
and PGD 100 attacks. As explained in Madry et al. [2018], networks with larger capacity are stronger
against adversarial attacks.

|Performance|Langevin|PGD 40|
|---|---|---|
|Train Adversarial Clean test set|98.90% 84.07%|97.42% 83.54%|
|FGSM PGD 40 PGD 100 Autoattack|56.47% 55.64% 54.50% 26.12%|59.51% 58.88% 57.97% 26.04%|


Performance Langevin PGD 40

Train Adversarial 98.90% 97.42%

Clean test set 84.07% 83.54%

FGSM 56.47% 59.51%

PGD 40 55.64% 58.88%

PGD 100 54.50% 57.97%

Autoattack 26.12% 26.04%


Table 5: Performance comparison of a wide ResNet (Zagoruyko and Komodakis [2017]) trained with
the Adversarial Transport framework (Langevin) and PGD 40 on CIFAR-10. No hyperparameter
tuning was done; the same setup as described in Section 5 is used with the exception of only training
for 36 epochs instead of 100. The Langevin framework took about 2h10m to train, while PGD 40
took 43h43m to train.


-----

