Rafael Pinot

Raphael Ettedgui

Geovani Rizk

Yann Chevaleyre

Jamal Atif

Randomization matters How to defend against strong adversarial attacks

come   L'archive ouverte pluridisciplinaire

Introduction

Adversarial example attacks recently became a major concern in the machine learning community. An adversarial attack refers to a small, imperceptible change of an input that is maliciously designed to fool a machine learning algorithm. Since the seminal work of [START_REF] Biggio | Evasion attacks against machine learning at test time[END_REF] and [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] it became increasingly important to understand the vulnerability of machine learning models to adversarial attacks. Accordingly, a large body of work has been published on designing attacks [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]Papernot et al., 2016a;[START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF]Carlini & * Equal contribution 1 Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE, Paris, France 2 Institut LIST, CEA, Université Paris-Saclay, France. Correspondence to: Rafael Pinot <rafael.pinot@dauphine.fr>, Raphael Ettedgui <raphael.ettedgui@polytechnique.edu>. [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF][START_REF] Athalye | Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples[END_REF] and defenses [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]Papernot et al., 2016b;[START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF][START_REF] Cohen | Certified adversarial robustness via randomized smoothing[END_REF]. At the same time, there has been a growing interest in understand the very nature of this phenomenon (Fawzi et al., 2016;2018;[START_REF] Bubeck | Adversarial examples from computational constraints[END_REF]Ilyas et al., 2019;Gourdeau et al., 2019). Despite these significant efforts, the existence of a classifier with optimal robustness against all attacks remains an open problem. In this paper we tackle the following questions for which we provide principled and theoretically-grounded answers: Q1: Is there a deterministic classifier that ensures optimal robustness against any adversarial attack?

A1: To answer this question, in Section 3, we cast the adversarial examples problem as an infinite zero-sum game between a Defender (the classifier) and an Adversary that produces adversarial examples. Then we demonstrate, in Section 4, the non-existence of a Nash equilibrium in the deterministic setting of this game. This entails that no deterministic classifier can claim to be more robust than all other classifiers against any possible adversarial attack, including Adversarial Training. Another consequence of our analysis is that there is no free lunch for transferable attacks: an attack that works on all classifiers will never be optimal against any of them.

Q2: Would randomized defense strategies be a suitable alternative to defend against strong adversarial attacks? A2: We tackle this problem both theoretically and empirically. In Section 5, we demonstrate, under a mild condition on the data distribution, that for any deterministic defense there exists a mixture of classifiers that offers better worstcase theoretical guarantees. Building upon this, we devise a new algorithm that generates robust randomized classifiers using a boosting-type procedure. We evaluate this method, that we call Boosted Adversarial Training, in Section 6 against strong attacks on the CIFAR10 dataset. It outperforms Adversarial Training against both ∞ -PGD [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF], and 2 -C&W attacks [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF]. More precisely, our algorithm achieves 0.58 (resp. 0.59) accuracy under attack against ∞ -PGD (resp. 2 -C&W) with 100 iterations, which is an improvement of 0.16 (resp. 0.08) over Adversarial Training. arXiv:2002.11565v1 [cs.LG] 26 Feb 2020

Related Work

Many works have studied adversarial examples, in several different settings. We discuss hereafter the different frameworks that we believe to be related to our work, and discuss the aspects on which our contribution differs from them.

Distributionally robust optimization. [START_REF] Sinha | Certifiable distributional robustness with principled adversarial training[END_REF] address the problem of adversarial examples through the lens of distributionally robust optimization. They study a min-max problem where the Adversary manipulates the test distribution while being constrained in a Wasserstein distance ball. A similar analysis was presented in Lee & Raginsky (2018) in a more general setting that does not focus on adversarial examples. Even though our work studies the same problem, our reasoning is very different. We adopt a game theoretic standpoint, which allows us to investigate randomized defenses and endow them with strong theoretical evidences.

Game Theory. Some works have tackled the problem of adversarial examples as a two player game. For example [START_REF] Brückner | Stackelberg games for adversarial prediction problems[END_REF] views adversarial example attacks and defenses as a Stackelberg game. More recently, Rota [START_REF] Rota Bulò | Randomized prediction games for adversarial machine learning[END_REF] and [START_REF] Perdomo | Robust attacks against multiple classifiers[END_REF] investigated zero-sum games. They consider restricted versions of the game where classical theorems apply, such as when the defender only has a finite set of possible strategies. We study a more general setting. Finally, [START_REF] Dhillon | Stochastic activation pruning for robust adversarial defense[END_REF] motivated the use of noise injection as a defense mechanism by game theoretic arguments but only present empirical results.

Randomization. Following the work of [START_REF] Dhillon | Stochastic activation pruning for robust adversarial defense[END_REF] and [START_REF] Xie | Mitigating adversarial effects through randomization[END_REF], several recent works studied noise injection as a defense mechanism. In particular, [START_REF] Lecuyer | Certified robustness to adversarial examples with differential privacy[END_REF], followed by [START_REF] Cohen | Certified adversarial robustness via randomized smoothing[END_REF]; Li et al. (2019); [START_REF] Pinot | Theoretical evidence for adversarial robustness through randomization[END_REF]; Wang et al. (2019) demonstrated that noise injection can, in some cases, give provable defense against adversarial attacks. The analysis and algorithm we propose in this paper are not based on noise injection. However, a link could be made between these works and the mixture algorithm we propose, by noting that a classifier in which noise is being injected can be seen as an infinite mixture of perturbed classifiers.

Optimal transport. Our work considers a distributionnal setting, in which the Adversary manipulating the dataset is formalized by a push-forward measure. This kind of setting is close to optimal transport settings recently developed by Bhagoji et al. (2019) and [START_REF] Pydi | Adversarial risk via optimal transport and optimal couplings[END_REF]. Specifically, these works investigate classifier-agnostic lower bounds on the risk for binary classification under attack, with some hypothesis on the data distribution. Even though they do not treat the same problem, we believe that these works are profoundly related and complementary to ours.

Problem statement

Notations. For any set Z with σ-algebra σ (Z), if there is no ambiguity on the considered σ-algebra, we denote P (Z) the set of all probability measures over (Z, σ (Z)), and F Z the set of all measurable functions from (Z, σ (Z)) to (Z, σ (Z)). For µ ∈ P (Z) and φ ∈ F Z , the pushforward measure of µ by φ is the measure φ#µ such that φ#µ(B) = µ(φ -1 (B)) for any B ∈ σ(Z).

Binary classification task. Let X ⊂ R d and Y = {-1, 1}. We consider a distribution D ∈ P (X × Y) that we assume to be of support X × Y. The Defender is looking for a hypothesis (classifier) h in a class of functions H, minimizing the risk of h w.r.t. D, which is defined as the probability of misclassification:

R(h) := E (X,Y )∼D [1 {h(X) = Y }] = E Y ∼ν E X∼µ Y [1 {h(X) = Y }] . (1)
Where

H := {h : x → sgn g(x) | g : X → R continuous}, ν ∈ P (Y)
is the probability measure that defines the law of the random variable Y , and for any y ∈ Y, µ y ∈ P (X ) is the conditional law of X|(Y = y).

Adversarial example attack (point-wise). Given a classifier h : X → Y and a data sample (x, y) ∼ D, the Adversary seeks a perturbation τ ∈ X that is visually imperceptible, but modifies x enough to change its class, i.e. h(x + τ ) = y. Such a perturbation is called an adversarial example attack. In practice, it is hard to evaluate the set of visually imperceptible modifications of an image. However, a sufficient condition to ensure that the attack is undetectable is to constrain the perturbation τ to have a small norm, be it for the ∞ or the 2 norm. Hence, one should always ensure that τ ∞ ≤ ∞ , or τ 2 ≤ 2 , depending on the norm used to measure visual imperceptibility. The choice of the threshold depends on the application at hand. For example, on CIFAR10, typical values for ∞ and 2 are respectively, 0.031 and 0.4/0.6/0.8.

Note that our definition of the problem implies that the Adversary has perfect information on the dataset and the classifier, so we consider here the strongest type of attacks, called white-box attacks. In particular, the same point x may have different perturbations depending on what its true class is: since the Adversary wants the classifier to do as many mistakes as possible, it may not attack a point when it is already misclassified.

Adversarial example attack (distributional). The Adversary is choosing, for every x ∈ X , a perturbation that depends on its true label y. This amounts to construct, for each label y ∈ Y, a measurable function φ y such that φ y (x) is the perturbation associated with the labeled example (x, y). This function naturally induces a probability distribution over adversarial examples, which is simply the push-forward measure φ y #µ y . The goal of the Adversary is thus to find φ = (φ -1 , φ 1 ) ∈ (F X ) 2 that maximizes the adversarial risk R adv (h, φ) defined as:

R adv (h, φ) := E Y ∼ν E X∼φ Y #µ Y [1 {h(X) = Y }] -λ Ω (φ) .
(2)

The penalty function Ω represents the transportation cost of the Adversary, and λ ∈ (0, 1) some regularization weight. More precisely, Ω encodes the constraints that the Adversary enforces on the attacks, to remain undetected.

Transportation costs. The analysis of Equation (2) will heavily depend on the choice of the penalty function Ω. In this paper, we study two types of penalties: the norm penalty Ω norm , and the mass penalty Ω mass . The first one penalizes the expected norm of the perturbation as follows:

Ω norm (φ) := E Y ∼ν E X∼µ Y X -φ Y (X) 2 +∞1 { X -φ Y (X) 2 > 2 } , (3)
with the convention ∞ × 0 = 0. The first term of the regularization has been proposed by [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF] to compute the eponymous attack (C&W) 1 . However, using this alone may lead to create perceptible attacks. To deal with this, but also for numerical experiments to be fair, [START_REF] Carlini | On evaluating adversarial robustness[END_REF] proposed to reject the perturbation when the 2 norm is greater than some threshold 2 , hence the second term 2 .

We define the mass penalty as follows:

Ω mass (φ) := E Y ∼ν E X∼µ Y 1 {X = φ Y (X)} +∞1 { X -φ Y (X) ∞ > ∞ } . (4)
The mass penalty discourages the Adversary from attacking too many points by penalizing the overall mass of transported points. This type of constraint, although not often discussed in the literature, is very important to understand and analyze real life scenarios, where the Defender tries to detect attacks based on the occurrences of its failures.

Since the attack should also remain visually undetected, the penalty ensures that all attacks have an ∞ norm smaller than a given ∞ . This kind of ∞ constraint is related to other attacks form the literature (e.g. FGSM [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] or PGD [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF]).

1 Ωnorm is not limited to 2 norm. The results we present hold as long as the norm used to compare X and φY (X) comes from a scalar product on X .

2 One could also use a threshold on the ∞ norm. We chose the 2 norm to be consistent with the first term of the penalty.

We will also see in Section 4 that the mass penalty can be useful to study approximate solutions for the norm penalty.

Adversarial defense, a two-player zero-sum game. Whatever penalty we choose, its value does not depend on h (hence, the optimal Defender minimizing Eq. ( 1) or ( 2) is the same). The adversarial examples problem can thus be seen as a two-player zero-sum game, where the Defender tries to find the best possible hypothesis h, while a strong Adversary is manipulating the dataset distribution:

inf h∈H sup φ∈(F X ) 2 R adv (h, φ). (5)
This means that the Defender tries to design the classifier with the best performance under attack, whereas the Adversary will each time design the optimal attack on this specific classifier. In the game theoretical terminology, the choice of a classifier h (resp. an attack φ) for the Defender (resp. the Adversary) is called a strategy.

It is crucial to note that in our game, the sup-inf and inf-sup problems do not coincide. In this paper, we mainly focus on the Defender's point of view which corresponds to the inf-sup problem.

Definition 1 (Best Response). Let h ∈ H, and φ ∈ (F X ) 2 . A best response from the Defender to φ is a classifier

h * ∈ H such that R adv (h * , φ) = min h∈H R adv (h, φ). Similarly, a
best response from the Adversary to h is an attack φ * such that R adv (h, φ * ) = max φ∈(F X ) 2 R adv (h, φ).

In the remaining, we denote BR Ω (h) the set of all best responses of the Adversary to a classifier h, under penalty Ω. Similarly BR(φ) denotes the set of best responses to an attack φ. Since Ω does not impact the Defender's optimization problem, we omit to mention Ω.

Definition 2 (Pure Nash Equilibrium). In the zero-sum game (Eq. 5) with penalty Ω, a Pure Nash Equilibrium is a couple of strategies (h, φ) ∈ H × (F X ) 2 such that h ∈ BR(φ), and, φ ∈ BR Ω (h).

When it exists, a Pure Nash Equilibrium is a state of the game in which no player has any incentive to modify its strategy. In our setting, this simultaneously means that no attack could better fool the current classifier, and that the classifier is optimal for the current attack.

Remark. All the definitions in this section assume a deterministic regime, i.e. that neither the Defender nor the Adversary use randomization, hence the notion of Pure Nash Equilibrium in the game theory terminology. We will study this deterministic regime in Section 4. The randomized regime will be studied in Section 5. The black vertical line is the Bayes optimal classifier for the initial distributions. Finally, the red (lighter) and the blue (darker) areas represents the zones on which the Adversary can change the distributions for mass (middle) and norm (right) penalty.

Deterministic regime

Notations. Let h ∈ H, y ∈ Y, and p ∈ {2, ∞}.

We denote P h := {x ∈ X | h(x) = 1}, and N h := {x ∈ X | h(x) = -1} respectively the set of positive and negative outputs of h. We also denote P p h (δ) := {x ∈ P h | ∃z ∈ N h and z -x p ≤ δ}, and in the same way N p h (δ) the points that are closer than δ from the other class. We omit p, when it is clear from the context 3 .

In this section we show that whatever penalty the Adversary has, no Pure Nash Equilibrium exists. To do so, we characterize the best responses for each player, and show that they can never satisfy Definition 2.

Adversary's best response. Let us first present the best responses of the Adversary under respectively the norm penalty and the mass penalty.

Lemma 1. Let h ∈ H, 2 ≤ 1 the perceptibility parameter, and φ ∈ BR Ωnorm (h). Then the following holds:

φ 1 (x) = π(x) if x ∈ P h ( 2 ) x otherwise.
Where π is the orthogonal projection on (P h ) , the complement of P h in X . φ -1 is characterized symmetrically.

Lemma 2. Let h ∈ H, ∞ ≤ 1 the perceptibility parameter, and φ ∈ BR Ωmass (h). Then the following holds:

φ 1 (x) ∈ (P h ) if x ∈ P h ( ∞ ) φ 1 (x) = x otherwise.
and φ -1 is characterized symmetrically.

Both best responses share a fundamental behavior: the optimal attack will only change points that are close enough to the decision boundary be it w.r.t 2 or ∞ norm. This means that, when the Adversary has no chance of making 3 In particular when δ = p it depends on the p norm.

the classifier change its decision about a given point, it will not attack it.

However, for the norm penalty all attacked points are projected on the decision boundary, whereas with the mass penalty the attack moves the points across the border. This difference is illustrated in Figure 1 with two uni-dimensional Gaussian distributions. For the norm penalty (on the right), the part of µ 1 (dashed and dotted lines) that was in P h ( 2 ) (blue zone) is transported on a Dirac distribution at the decision boundary. The same holds for µ -1 (dashed lines). After attack, we now have µ 1 (P h ( 2 )) = 0, so a small value of µ -1 in P h ( 2 ) suffices to make it dominant, and that zone will now be classified -1 by the Bayes classifier.

For the norm penalty (in the middle), µ 1 (dashed and dotted lines) is set to 0 in P h ( ∞ ) (blue zone), and this mass is transported into N h ( ∞ ) (red zone), and added to the small amount of µ 1 that was already there. Similarly to the norm penalty case, the small value of µ -1 (dashed lines) in the P h ( ∞ ) now suffices to make the best response classify that zone as -1.

Remark. In practice, it might be computationally hard to generate the exact best response for the norm penalty, i.e. the projection on the decision boundary. That will happen for example if this boundary is very complex (e.g. highly nonsmooth), or when X is in a high dimensional space. In order to keep the attack computationally tractable, the Adversary will have to compute an approximated best response by allowing the projection to reach the point within a small ball around the boundary. This means that the best responses of the norm penalty and the mass penalty problems will often match (for a well chosen ).

Defender's best response. At a first glance, one would suspect that the best response for the Defender ought to be the Bayes classifier for the transported distribution. However, the Bayes classifier is only well defined for distributions that have probability density functions. This does not always hold here for the transported distribution. Typically, we see on Figure 1 that in the 1 dimensional setting, projecting on the decision boundary creates a Dirac distribution. Nevertheless, we show that there is a property, shared by the Bayes classifier when defined, that always holds for the Defender's best response.

Lemma 3. Let us consider φ ∈ (F X )

2 . If we take h ∈ BR(φ), then for y = 1 (resp. y = -1), and for any B ⊂ P h (resp. B ⊂ N h ) one has:

P(Y = y|X ∈ B) ≥ P(Y = -y|X ∈ B) with Y ∼ ν and for all y ∈ Y, X|(Y = y) ∼ φ y #µ y .
In particular, when φ 1 #µ 1 and φ -1 #µ -1 admit probability density functions, Lemma 3 simply means that h is the optimal Bayes classifier for the distribution (ν, φ 1 #µ 1 , φ -1 #µ -1 )4 . We can now state our main theorem, as well as two of its important consequences.

Theorem 1 (Non-existence of a pure Nash equilibrium). In the zero-sum game (Eq. 5) with penalty Ω ∈ {Ω mass , Ω norm }, there is no Pure Nash Equilibrium.

Consequence 1. No free lunch for transferable attacks.

To understand this statement, remark that, thanks to weak duality, the following inequality always holds:

sup φ∈(F X ) 2 inf h∈H R adv (h, φ) ≤ inf h∈H sup φ∈(F X ) 2 R adv (h, φ).
On the left side problem (sup-inf), the Adversary looks for the best attacking strategy φ against any unknown classifier. This is tightly related to the notion of transferable attacks (e.g. [START_REF] Tramèr | The space of transferable adversarial examples[END_REF]), which refers to attacks successful against a wide range of classifiers. On the right side our problem (inf-sup), where the Defender tries to find the best classifier under any possible attack, whereas the Adversary plays in second and specifically attacks this classifier. As a consequence of Theorem 1, the inequality is always strict:

sup φ∈(F X ) 2 inf h∈H R adv (h, φ) < inf h∈H sup φ∈(F X ) 2 R adv (h, φ).
This means that both problems are not equivalent. In particular, an attack designed to succeed against any classifier (i.e. a transferable attack) will not be as good as an attack tailored for a given classifier.

Consequence 2. No deterministic defense (including Adversarial Training) may be proof against every attack.

Let us consider the state-of-the-art defense which is Adversarial Training. The idea is to compute an efficient attack φ, and train the classifier on created adversarial examples, in order to move the decision boundary and make the classifier more robust to new perturbations by φ. To be fully efficient, this method requires that φ remains an optimal attack on h even after training. Our theorem shows that it is never the case: after training our classifier h to become (h ) robust against φ, there will always be a different optimal attack φ that is efficient against h . Hence Adversarial Training will never achieve a perfect defense.

Randomization matters

Fully randomized regime. We have shown, that since there is no pure Nash equilibrium, no deterministic classifier may be proof against every attack. We would therefore need to allow for a wider class of strategies. A natural extension of the game would thus be to allow randomization for both players, who would now choose a distribution over pure strategies, leading to this game:

inf η∈P(H) sup ϕ∈P((F X ) 2 ) E h∼η φ∼ϕ [R adv (h, φ)] . (6)
Without making further assumptions on this game (e.g. compactness), we cannot apply known results from game theory (e.g. Sion theorem) to prove the existence of an equilibrium in this setting. These assumptions would however make the problem loose much generality, and does not hold here.

Randomization matters. Even without knowing if an equilibrium exists in the randomized setting, we can prove that randomization matters. More precisely we show that, under mild condition on the data distribution, any deterministic classifier can be outperformed by a randomized one in terms of the worst case adversarial risk. To do so we simplify Equation 6 in two ways.

1. We do not consider the Adversary to be randomized, i.e we restrict the search space of the Adversary to (F X ) 2 instead of P (F X ) 2 . This condition corresponds to the current state-of-the-art in the domain: to the best of our knowledge, no efficient randomized adversarial example attack has been designed (and so is used) yet.

2. We only consider a subclass of randomized classifiers, called mixtures, which are discrete probability measures on a finite set of classifier. We show that this kind of randomization is enough to strictly outperform any deterministic classifier. We will discuss later the use of more general randomization (such as noise injection) for the Defender.

Let us now define a mixture of classifiers: Definition 3 (Mixture of classifier). Let n ∈ N, h = (h 1 , ..., h n ) ∈ H n , and q ∈ P ([n]). A mixed classifier of h by q is a mapping m q h from X to P (Y) such that for all x ∈ X , m q h (x) is the discrete probability distribution that is defined for all y ∈ Y by: We call such a mixture a mixed strategy of the Defender. Given some x ∈ X , this amounts to picking a classifier h i from h at random following the distribution q, and use it to output the predicted class for x, i.e h i (x). Note that a mixed strategy for the Defender is a non deterministic algorithm, since it depends on the sampling one makes on q. Hence, even if the attacks are defined in the same way as before, the Adversary now needs to maximize a new objective function which is the expectation of the adversarial risk under the distribution m q h . It writes as follows:

m q h (x)(y) := E i∼q [1 {h i (x) = y}] .
E Y ∼ν E X∼φ Y #µ Y E Ŷ ∼m q h (X) 1 Ŷ = Y -λ Ω (φ) . (7)
We also write R adv to mean Equation ( 7), when it is clear from context that the Defender uses a mixed classifier. Using this new set of strategies for the Defender, we can study whether mixed classifiers outperform deterministic ones, and how to efficiently design them.

To do so, let us demonstrate that the efficiency of any deterministic defense can be improved using a simple mixture algorithm. This method presents similarities with the notions of fictitious play [START_REF] Brown | Iterative solution of games by fictitious play[END_REF] in game theory, and boosting in machine learning [START_REF] Freund | A Decision Theoretic Generalization of On-Line Learning and an Application to Boosting[END_REF]. Given a deterministic classifier h 1 , we combine it (via randomization) with the best response h 2 to its optimal attack. The rational behind this idea is that, by construction, efficient attacks on one of these two classifiers will not work on the other. If we can then calibrate the weights so that attacks on important zones have a low probability of succeeding, then the average risk under attack on the mixture will be low. We will thus need the following condition on the data distribution : Definition 4 (( , p)-dilation and vanishing measure). Let U be a subset of X , a positive value, p ∈ {2, ∞}, and µ a probability measure.

1. The ( , p)-dilation of U is defined as follows:

U p ⊕ := u + v | (u, v) ∈ U × X and v p ≤ .
2. We say that µ is ( , p)-vanishing5 on U if we have:

µ U p ⊕ \U ≤ µ(U ).
This is because mixing h 1 with h 2 has two opposite consequences on the adversarial risk. On one hand, where we only had to defend against attack on h 1 , we are now also vulnerable to attacks on h 2 , so the total set of possible attacks is now bigger. On the other hand, each attack will only work part of the time, depending on the probability distribution q. When Definition 4 applies on the attackable zones, it ensures that we gain more than we loose.

With these new definitions, we now can state our second main result: mixtures outperform deterministic classifiers.

Theorem 2. (Randomization matters) Let h 1 ∈ H, λ ∈ (0, 1) the regularization parameter, φ ∈ BR Ωnorm (h 1 ), and

h 2 ∈ BR(φ). If µ 1 (resp. µ -1 ) is 2 -vanishing on P h1 ( 2 ) (resp. on N h1 ( 2 )
), then for any α ∈ ( 1+λ 2 2 , 1) one has:

∀φ ∈ BR Ωnorm (m q h ), R adv (m q h , φ ) < R adv (h 1 , φ).
Where h = (h 1 , h 2 ), q = (α, 1 -α), and m q h is the mixture of h by q. A similar result holds for the mass penalty, with α ∈ ( 1+λ 2 , 1).

On the vanishing measure condition. Let us briefly explain this property. To defend against an attack, the general tactic is to change the classifier output, when points are close to the border (either all the time, as in Adversarial Training where we move the decision boundary to incorporate adversarial examples, or part of the time as in our randomized algorithm so that the attack only works with a given probability).

For example on figure 2, we mix the Bayes classifier (left) with its optimal attack that swaps the blue and red zone between the dotted line, on the gray area that is the former attack zone for the blue class. This gives the figure on the right. If the first classifier has a weight α = 0.5, the 10 old attacks (points between the dotted lines) now succeed only with probability 0.5 (the new optimal attack for star points being to leave them in place), whereas 3 new attacks are created (blue points outside of the gray area) that succeed with probability 0.5, for a total attack score of 6.5, which is lower than the old attack score of 10.

When adversarially training a classifier (Figure 2, middle), we change its output on the blue zone, so that four of the star points cannot be successfully attacked anymore. But in exchange, the dilation of this zone (in red) can now be attacked. For Adversarial Training to work, we need the number of new potential attacks (i.e. the points that are circled, 2 red ones in the dilatation and 2 blue ones that are close to the new boundary) to be smaller than the number of attacks we prevent (the points that are in a square, 4 blue ones that an attack would send in the blue zone, and 3 red points that are far from the new decision boundary). Here we prevent 7 attacks at the cost of four new ones, so the Adversarial Training improves the total score from 10 to 7.

This discussion shows that when no measure have any vanishing zone, Adversarial Training cannot bring any gain. By contraposition, whenever a deterministic classifier can be improved by Adversarial Training, it will also be outperformed under optimal attack by a randomized algorithm (see Theorem 2).

6. Experiments: How to build the mixture Contrary to classical algorithms such as Fictitious play that also generates mixtures of classifiers, and whose theoretical guarantees rely on the existence of a Mixed Nash Equilibrium, the performance of our algorithm is ensured by Theorem 2 to be at least as good as the classifier it uses as a basis. Moreover, the implementation of Fictitious Play would be impractical on high dimensional dataset we consider, due to computational costs. Create and adversarially train h 1 on D h = (h 1 ) ; q = (1) for i = 2, . . . , n do Generate the adversarial data set D against m q h . Create and naturally train h i on D

q k ← (1 -α)q k ∀k ∈ [i -1] q i ← α q ← (q 1 , . . . , q i ) h ← (h 1 , . . . , h i ) end return m q h
BAT starts by constructing an adversarially trained classifier on D, and gives it a weight of 1. Then, at each step of the algorithm, we train a new classifier on a data set D built from D that contains adversarial examples created to fool the current mixture. This new classifier is added to the mixture with a weight of α. Previous weights are then multiplied by 1 -α.

At each step, we use ∞ -PGD with 20 iterations and ∞ = 0.031 to attack the current mixture and build the adversarial dataset D. We choose this attack to fairly compare against Adversarial Training, which uses it during the training procedure.

On evaluating against ∞ -PGD We use Expectation over Transformation (EOT) following [START_REF] Athalye | Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples[END_REF] and [START_REF] Carlini | On evaluating adversarial robustness[END_REF], when implementing an ∞ -PGD attack against a mixture of classifier. Indeed, it is important to compute the expected loss over the mixture, so that the attack optimizes Equation ( 7). Previous works such as [START_REF] Dhillon | Stochastic activation pruning for robust adversarial defense[END_REF] and [START_REF] Pinot | Theoretical evidence for adversarial robustness through randomization[END_REF] estimate the expected loss through a Monte Carlo sampling. Since we assume perfect information for the Adversary, it knows the exact distribution of the mixture. Hence it can directly compute the expected loss without using a sampling method.

We conduced a grid-search to evaluate the influence of α (see the supplementary material for more details). For the results we present here, the optimal α we found is equal to 0.06 for 10 classifiers. In Table 1 we compare the accuracy (on the CIFAR10 dataset (Krizhevsky & Hinton, 2009) ∞-PGD we use an epsilon equal to 8/255 (≈ 0.031), a step size equal to 2/255 (≈ 0.008) and we allow random initialization. For 2-C&W we use a learning rate equal to 0.1, 9 binary search steps, the initial constant to 0.001, we allow the abortion when it has already converged and we give the results for the different values of rejection threshold 2 ∈ {0.4, 0.6, 0.8}. Since the mixture draws a classifier in h according to q to predict a class for each sample, we run 100 times the evaluation to compute the expected accuracy under attack of the mixture. The width of the 95% confidence interval is negligible (< 0.01). For this reason, we chose to omit it.

Results against ∞ -PGD. We compute 100 steps of ∞ -PGD for the attack at test time, while only 20 steps during the training. The idea behind this difference is that the Adversary may target only a few specific points, and so may have access to more computational power for attacks than the Defender that trains on the whole dataset. For a classifier to be fully robust, its loss of accuracy should be controlled when the attacks are strongest than what it was trained on.

As shown in Table 1, the mixture generated by BAT with 10 classifiers and α = 0.06 outperforms adversarial training on all four attacks. This is already the case for 2 classifiers, which corroborates the result from Theorem 2. We refer the reader to the supplementary material for additional results on how the size of the mixture influences the performance.

On Evaluating against 2 -C&W. Adversarial Training can also be used to defend against 2 -C&W. We conducted experiments to evaluate whether the mixture constructed with BAT also outperforms it against this attack. Since the basic 2 -C&W attack creates an unbounded perturbation on examples, we implemented the constraint from Equation 3 by checking at test time whether the 2 -norm of the perturbation exceeds a certain threshold 2 ∈ {0.4, 0.6, 0.8}.

If this holds, we keep the natural example, instead of its adversary version.

For the attacks to be comparable, the radiuses of the balls must be chosen carefully. For CIFAR10, which is a 3 × 32 × 32 dimensional space, this gives 2 = 0.8 and ∞ = 0.03. The results of this evaluation are presented in Table 1. Note that we ran 100 steps for the 2 -C&W as well.

Results against l 2 -C&W. The accuracy under attack of our mixture is higher than that of adversarial training for all the thresholds. Our mixture is especially more robust than Adversarial Training when the threshold (i.e. the budget for a perturbation), is high. Here again, we see that with two classifiers the mixture already gives an accuracy under attack of 0.53 against 2 -C&W with 2 = 0.8 and outperforms Adversarial Training. This result also corroborates Theorem 2.

We refer the reader to the supplementary material for all implementation details (architecture of models, optimization settings, hyper-parameters, etc.).

Discussion & Conclusion

Finally, is there a classifier that ensures optimal robustness against all adversarial attacks? We gave a negative answer in the deterministic regime, but part of the question remains open when considering randomized algorithms. We demonstrated that randomized defenses are more efficient than deterministic ones, and devised an algorithm to implements them. There remains to study whether an Equilibrium exists in the Randomized regime. This question is appealing from a theoretical point of view, and requires to investigate the space of randomized Adversaries P((F X ) 2 ). The characterization of this space is not straightforward, and would require strong results in the theory of optimal transport. A possible research direction is to quotient the space (F X ) 2 so as to simplify the search in P((F X ) 2 ) and the characterization of the Adversary's best responses. To do so, one could use an equivalence relation that matches two functions when they have the same adversarial risk.

The study of the mixed equilibrium is tightly related to that of the value of the game, which would be interesting for obtaining min-max bounds on the accuracy under attack, as well as certificates of robustness for a set of classifiers. One could also build upon the connection between mixtures and noise injection to investigate a broader range of randomized strategies for the Defender, and to devise such certificates.

From an algorithmic point of view, BAT can be improved in several ways. For instance, the weights can be learned while choosing the new classifier for the mixture. This could lead to an improved accuracy under attack, but would lack some theoretical justifications that still need to be set up. Finally, tighter connections with standard boosting algorithms could be established to improve the analysis of BAT.

Supplementary Material 1. Technical results

Notations: Let us suppose that X is a normed vector space, with norm . . B . (x, ) = {z ∈ X | x -z ≤ } is the closed ball of center x and radius for the norm . . Note that H := {h : x → sgn g(x) | g : X → R continuous}, with sgn the function that outputs 1 if g(x) > 0, -1 if g(x) < 0, and 0 otherwise. Hence for any (x, y) ∼ D, and h ∈ H one has 1{h(x) = y} = 1{g(x)y ≤ 0}. Lemma 1. Let h ∈ H, 2 ≤ 1 the perceptibly parameter, and φ ∈ BR Ωnorm (h). Then the following holds:

φ 1 (x) = π(x) if x ∈ P h ( 2 ) x otherwise.
Where π is the orthogonal projection on P h , the complement of P h in X . φ -1 is characterized symmetrically.

Proof. Ω norm is defined with an 2 norm, but this result holds as long as X is an Hilbert space with dot product <|> and associated norm ||.|| = < . | . >. We demonstrate the result with these general notations.

Let us first simplify the worst case adversarial risk for h. Recall that h = sgn(g) with g continuous. From the definition of adversarial risk we have:

sup φ∈(F X ) 2 R adv (h, φ) = sup φ∈(F X ) 2 y=±1 ν y E X∼µy 1 {h (φ y (X)) = y} -λ X -φ y (X) -∞1 { X -φ y (X) > 2 } (8) = sup φ∈(F X ) 2 y=±1 ν y E X∼µy 1 {g (φ y (X)) y ≤ 0} -λ X -φ y (X) -∞1 { X -φ y (X) > 2 } (9) = y=±1 ν y sup φy∈F X E X∼µy 1 {g (φ y (X)) y ≤ 0} -λ X -φ y (X) -∞1 { X -φ y (X) > 2 } (10)
Since finding φ 1 and φ 1 are two independent optimization problems, hereafter, we focus on characterizing φ 1 (i.e. y = 1).

sup

φ1∈F X E X∼µ1 1 {g (φ 1 (X)) ≤ 0} -λ X -φ 1 (X) -∞1 { X -φ 1 (X) > 2 } (11) = E X∼µ1 essup z∈B . (X, 2) 1(g(z) ≤ 0) -λ X -z (12) = X essup z∈B . (x, 2) 1 {g(z) ≤ 0} -λ x -z dµ 1 (x). ( 13
)
Let us now consider (H j ) j∈J a partition of X , we can write.

sup φ1∈F X E X∼µ1 1 {g (φ 1 (X)) ≤ 0} -λ X -φ 1 (X) -∞1 { X -φ 1 (X) > 2 } (14) = j∈J Hj essup z∈B . (x, 2) 1 {g(z) ≤ 0} -λ x -z dµ 1 (x) (15)
In particular, we consider here H 0 = P h , H 1 = P h \ P h ( 2 ), and H 2 = P h ( 2 ).

• For x ∈ H 0 = P h , taking z = x we get 1 {g(z) ≤ 0} -λ x -z = 1. Since for any z ∈ X we have 1 {g(z) ≤ 0}λ x -z ≤ 1, this strategy is optimal. Furthermore, for any other optimal strategy z , we would have x -z = 0, hence z = x, and an optimal attack will never move the points of H 0 = P h .

• For x ∈ H 1 = P h \ P h ( 2 ), we have B . (x, 2 ) ⊂ P h by definition of P h ( 2 ). Hence, for any z ∈ B . (x, 2 ), one gets g(z) > 0. Then 1 {g(z) ≤ 0} -λ x -z ≤ 0. The only optimal z will thus be z = x, giving value 0.

• Let us now consider x ∈ H 2 = P h ( 2 ), which is the interesting case where an attack is possible. We know that B . (x, 2 ) ∩ P h = ∅, and for any z in this intersection, 1(g(z) ≤ 0) = 1. Hence :

essup z∈B . (x, 2) 1 {g(z) ≤ 0} -λ x -z = max(1 -λ essinf z∈B . (x, 2)∩P h x -z , 0) (16) = max(1 -λπ B . (x, 2)∩P h (x), 0) (17)
Where

π B . (x, 2)∩P h is the projection on the closure of B . (x, 2 ) ∩ P h . Note that π B . (x, 2)∩P h exists: g is continuous, so B . (x, 2
) ∩ P h is a closed set, bounded, and thus compact, since we are in finite dimension. The projection is however not guaranteed to be unique since we have no evidence on the convexity of the set. Finally, let us remark that, since λ ∈ (0, 1), and 2 ≤ 1, one has 1 -λπ B . (x, 2)∩P h (x) ≥ 0 for any x ∈ H 2 . Hence, on P h ( 2 ), the optimal attack projects all the points on the decision boundary. For simplicity, and since there is no ambiguity, we write the projection π.

Finally, since H 0 ∪ H 1 ∪ H 2 = X , Lemma 1 holds. Furthermore, the score for this optimal attack is:

sup φ∈(F X ) 2 R adv (h, φ) = y=±1 ν y j∈J Hj essup z∈B . (x, 2) 1 {g(z)y ≤ 0} -λ x -z dµ y (x) (18)
Since the value is 0 on

P h \ P h ( 2 ) (resp. on N h \ N h ( 2 ) ) for φ 1 (resp. φ -1
), one gets:

= ν 1    P h ( 2 ) 1 -λπ(x) dµ 1 (x) + P h 1dµ 1 (x)    + ν -1    N h ( 2 ) 1 -λπ(x) dµ -1 (x) + N h 1dµ -1 (x)    (19) = ν 1    P h ( 2) 1 -λπ(x) dµ 1 (x) + µ 1 (P h )    + ν -1    N h ( 2) 1 -λπ(x) dµ -1 (x) + µ -1 (N h )    (20) = R(h) + ν 1 P h ( 2 ) 1 -λπ(x) dµ 1 (x) + ν -1 N h ( 2 ) 1 -λπ(x) dµ -1 (x) (21) Since R(h) = P(h(X) = Y )P(g(X)Y ≤ 0) = ν 1 µ 1 (P h ) + ν -1 µ -1 (N h ).
This provides an interesting decomposition of the adversarial risk into the risk without attack and the loss on the attack zone.

Lemma 2. Let h ∈ H, ∞ ≤ 1 the perceptibility parameter, and φ ∈ BR Ωmass (h). Then the following holds:

φ 1 (x) ∈ P h if x ∈ P h ( ∞ ) φ 1 (x) = x otherwise.
and φ -1 is characterized symmetrically.

Proof. Following the same proof schema as before the adversarial risk writes as follows:

sup φ∈(F X ) 2 R adv (h, φ) = sup φ∈(F X ) 2 y=±1 ν y E X∼µy 1 {h (φ y (X)) = y} -λ1 {X = φ y (X)} -∞1 X -φ y (X) ∞ > ∞ (22) = sup φ∈(F X ) 2 y=±1 ν y E X∼µy 1 {g (φ y (X)) y ≤ 0} -λ1 {X = φ y (X)} -∞1 X -φ y (X) ∞ > ∞ (23) = y=±1 ν y sup φy∈F X E X∼µy 1 {g (φ y (X)) y ≤ 0} -λ1 {X = φ y (X)} -∞1 X -φ y (X) ∞ > ∞ (24)
Since finding φ 1 and φ 1 are two independent optimization problem, hereafter, we focus on characterizing φ 1 (i.e. y = 1).

sup

φ1∈F X E X∼µ1 1 {g (φ 1 (X)) ≤ 0} -λ1 {X = φ 1 (X)} -∞1 { X -φ 1 (X) ∞ > ∞ } (25) = E X∼µ1 essup z∈B . ∞ (X, ∞) 1 {g(z) ≤ 0} -λ1 {X = φ 1 (X)} (26) = X essup z∈B . ∞ (x, ∞) 1 {g(z) ≤ 0} -λ1 {x = φ 1 (x)} dµ 1 (x). (27)
Let us now consider (H j ) j∈J a partition of X , we can write.

sup φ1∈F X E X∼µ1 1 {g (φ 1 (X)) ≤ 0} -λ1 {X = φ 1 (X)} -∞1 { X -φ 1 (X) ∞ > ∞ } (28) = j∈J Hj essup z∈B . ∞ (x, ∞) 1 {g(z) ≤ 0} -λ1 {x = φ 1 (x)} dµ 1 (x) (29)
In particular, we can take H 0 = P h , H 1 = P h \ P h ( 2 ), and H 2 = P h ( 2 ).

For x ∈ H 0 = P h or x ∈ H 1 = P h \ P h ( 2 ), with the same reasoning as before, any optimal attack will choose φ 1 (x) = x.

Let x ∈ H 2 = P h ( 2 ). We know that B . ∞ (x, ∞ )∩P h = ∅, and for any z in this intersection, one has g(z) ≤ 0 and z = x. Hence essup

z∈B . ∞ (x, ∞) 1 {g(z) ≤ 0}-λ1 {z = x} = max(1-λ, 0). Since λ ∈ (0, 1) one has 1 {g(z) ≤ 0}-λ1 {z = x} = 1 -λ for any z ∈ B . ∞ (x, ∞ ) ∩ P h . Then any function that given a x ∈ X outputs φ 1 (x) ∈ B . ∞ (x, ∞ ) ∩ P h is optimal on H 2 . Finally, since H 0 ∪ H 1 ∪ H 2 = X , Lemma 2 holds. Lemma 3. Let us consider φ ∈ (F X )
2 . If we take h ∈ BR(φ), then for y = 1 (resp. y = -1), and for any B ⊂ P h (resp. B ⊂ N h ) one has:

P(Y = y|X ∈ B) ≥ P(Y = -y|X ∈ B)
with Y ∼ ν and for all y ∈ Y, X|(Y = y) ∼ φ y #µ y .

Proof. We reason ad absurdum. Let us consider y = 1, the proof for y = -1 is symmetrical. Let us suppose that there exists

C ⊂ P h such that ν -1 φ -1 #µ -1 (C) > ν 1 φ 1 #µ 1 (C).
We can then construct h 1 as follows:

h 1 (x) = h(x) if x / ∈ C -1
otherwise.

Since h and h 1 are identical outside C, the difference between the adversarial risks of h and h 1 writes as follows:

R adv (h, φ) -R adv (h 1 , φ) = y=±1 ν y C 1 {h(x) = y} -1 {h 1 (x) = y} d(φ y #µ y )(x) (30) = ν -1 1 {h(x) = 1} φ -1 #µ -1 (C) -ν 1 1 {h 1 (x) = 1} φ 1 #µ 1 (C) (31) = ν -1 φ -1 #µ -1 (C) -ν 1 φ 1 #µ 1 (C) (32)
Since by hypothesis ν -1 φ -1 #µ -1 (C) > ν 1 φ 1 #µ 1 (C) the difference between the adversarial risks of h and h 1 is strictly positive. This means that h 1 gives strictly better adversarial risk than the best response h. Since, by definition h is supposed to be optimal, this leads to a contradiction. Hence Lemma 3 holds.

Additional Result. Let us assume that there is a probability measure ζ that dominates both φ 1 #µ 1 and φ -1 #µ -1 . Let us consider φ ∈ (F X )

2 . If we take h ∈ BR(φ), then h is the Bayes optimal classifier for the distribution (ν, φ 1 #µ 1 , φ -1 #µ -1 ).

Proof. For simplicity, we denote

f 1 = (dφ1#µ1) dζ and f -1 = d(φ-1#µ-1)
dζ the Radon-Nikodym derivatives of φ 1 #µ 1 and φ -1 #µ -1 w.r.t. ζ. The best response h minimizes adversarial risk under attack φ. This minimal risk writes:

inf h∈H R adv (h, φ) = inf h∈H y=±1 ν y E x∼µy [1 {h(φ y (x)) = y}] -λ Ω (φ) (33)
Since the the penalty function does not depend on h, it suffices to seek inf

h∈H y=±1 ν y X 1 {h(x) = y} d(φ y #µ y )(x).
Moreover thanks to the transfer theorem, one gets the following:

inf h∈H y=±1 ν y X 1 {h(x) = y} d(φ y #µ y )(x) = inf h∈H y=±1 ν y X 1 {h(x) = y} f y (x) dζ(x) (34) = inf h∈H X y=±1 ν y 1 {h(x) = y} f y (x) dζ(x). (35)
Finally, since the integral is bounded we get:

inf h∈H X y=±1 ν y 1 {h(x) = y} f y (x) dζ(x) = X inf h∈H y=±1 ν y 1 {h(x) = y} f y (x) dζ(x). (36)
Hence, the best response h is such that for every x ∈ X , and y ∈ Y, one has h(x) = y if and only if f y (x) ≤ f -y (x). Thus, h is the optimal Bayes classifier for the distribution (ν, φ 1 #µ 1 , φ -1 #µ -1 ). Furthermore, for y = 1 (resp. y = -1), and for any B ⊂ P h (resp. B ⊂ N h ) one has:

P(Y = y|X ∈ B) ≥ P(Y = -y|X ∈ B)
with Y ∼ ν and for all y ∈ Y, X|(Y = y) ∼ φ y #µ y .

Theorem 1 (Non-existence of a pure Nash equilibrium). In our zero-sum game with penalty Ω ∈ {Ω mass , Ω norm }, there is no Pure Nash Equilibrium.

Proof. Let h be a classifier, φ ∈ BR Ω (h) an optimal attack against h. We will show that h / ∈ BR(φ), i.e. that h does not satisfy the condition from Lemma 3. This suffices for Theorem 1 to hold since it implies that there is no (h, φ) ∈ H × (F X ) 2 such that h ∈ BR(φ) and φ ∈ BR Ω (h).

According to Lemmas 1 and 2, whatever penalty we use, there exists p ∈ {2, ∞}, and δ > 0 such that φ 1 #µ 1 (P p h (δ)) = 0 or φ -1 #µ -1 (N p h (δ)) = 0 6 . Both cases are symmetrical, so let us assume that P p h (δ) is of null measure for the transported distribution conditioned by y = 1. Furthermore we have φ -1 #µ -1 (P p h (δ)) = µ -1 (P p h (δ)) > 0 since φ -1 is the identity function on P p h (δ), and since µ -1 is of full support on X . Hence we get the following:

φ -1 #µ -1 (P p h (δ)) > φ 1 #µ 1 (P p h (δ)) . (37)
Since the right side of the inequality is null, we also get:

φ -1 #µ -1 (P p h (δ)) ν -1 > φ 1 #µ 1 (P p h (δ)) ν 1 ( 38
)
This inequality is incompatible with the characterization of best response for the Defender of Lemma 3. Hence h / ∈ BR(φ).

Theorem 2. (Randomization matters) Let h 1 ∈ H, λ ∈ (0, 1) the regularization parameter, φ ∈ BR Ωnorm (h 1 ), and

h 2 ∈ BR(φ). If µ 1 (resp. µ -1
) is 2 -vanishing on P h1 ( 2 ) (resp. on N h1 ( 2 )), then for any α ∈ ( 1+λ 2 2 , 1) one has:

∀φ ∈ BR Ωnorm (m q h ), R adv (m q h , φ ) < R adv (h 1 , φ).
Where h = (h 1 , h 2 ), q = (α, 1 -α), and m q h is the mixture of h by q. A similar result holds for the mass penalty, with α ∈ ( 1+λ 2 , 1).

Proof. Here we consider Ω norm but the proof is similar for Ω mass . To demonstrate Theorem 2, we actually show a more general result, where we only need µ 1 to be 2 -vanishing on some U ⊂ P h1 ( 2 ). In particular this will be true when U = P h1 ( 2 ). Let us assume that such an U exists.

We can construct h 2 as follows:

h 2 (x) = -h 1 (x) if x ∈ U h 1 (x) otherwise.
This means that h 2 changes the class of all points in U , and do not change the rest, compared to h 1 . Let α ∈ (0, 1), and the corresponding m q h , and φ ∈ BR Ωnorm (m q h ). We will find a condition on α so that the score of m q h is lower than the score of h 1 .

R adv (m q h , φ ) = y=±1 ν y X essup z∈B . (x, ) α1 {h 1 (z) = y} + (1 -α)1 {h 2 (z) = y} -λ||x -z|| dµ y (x) (39)
The only terms that may vary between the score of h 1 and the score of m q h are the integrals on U , U ⊕ 2 and φ -1 -1 (U ) (inverse image of U by φ -1 ), respectively the points we mix on, the points that may become attackable when y = 1 by moving them on U , and the ones that were attacked for y = -1 by moving them on U . Hence, for simplicity, we only write those terms in the following. Let us first consider the score of h 1 under optimal attack. Thanks to the analysis of the Lemma 1, it writes:

sup φ∈(F X ) 2 R adv (h 1 , φ) = ν 1 U 1 -λ x -π P h 1 (x) dµ 1 (x) + ν -1 µ -1 (U ) (40) + ν -1 µ -1 (U ⊕ 2 \ P h1 ( 2 )) + ν 1 (U ⊕ 2 \U )\P h 1 ( 2) 0 dµ 1 (x) (41) + ν -1 µ -1 (U ⊕ 2 ∩ P h1 ( 2 )) + ν 1 (U ⊕ 2\U )∩P h 1 ( 2) 1 -λ x -π P h 1 (x) dµ 1 (x) (42) + ν -1 φ -1 -1 (U ) 1 -λ x -π U (x) dµ -1 (x). (43)
For y = 1 all points in P h1 ( 2 ) are attacked by projecting on the decision boundary, and no point outside is attacked. For y = -1 some points of N h1 ( 2 ), that are attacked, may be sent into U , and others may not. Now let us consider the score of the mixture under its optimal attack.

sup φ∈(F X ) 2 R adv (m q h , φ) = ν 1 U max 1 -α, α -λ x -π P h 1 (x) dµ 1 (x) (44) + ν -1 U max α, 1 -α -λ x -π U ⊕ 2\U (x) dµ -1 (x) (45) + ν 1 (U ⊕ 2\U )∩P h 1 ( 2 ) max 1 -α -λ x -π U (x) , 1 -λ x -π P h 1 (x) dµ 1 (x) (46) + ν -1 µ -1 ((U ⊕ 2 \ U ) ∩ P h1 ( 2 )) + ν 1 (U ⊕ 2\U )\P h 1 ( 2) max (0, 1 -α -λ x -π U (x) ) dµ 1 (x) (47) + ν -1 µ -1 ((U ⊕ 2 \ U ) \ P h1 ( 2 )) + ν -1 φ -1 -1 (U ) max 0, 1 -λ x -π N h 1 (x) , α -λ x -π U (x) dµ -1 (x) (48)
We need to take into account the special case of the points in the dilation that were already in the attacked zone before, and that can now be attacked in two ways, either by projecting on U (but that works with probability α, since the classification on U is now randomized) or by projecting on P h1 , which works with probability 1 but may use more distance and so pay more penalty. For y = -1, attacks on U now work with probability α instead of 1, so the attacker may choose to attack on other points instead, even if that takes more distance.

We can now compute the difference between both risks, and show that it is strictly positive:

∆ R adv = sup φ∈(F X ) 2 R adv (h 1 , φ) -sup φ∈(F X ) 2 R adv (m q h , φ) (49) > ν 1 U 1 -λ x -π P h 1 (x) -max 1 -α, α -λ x -π P h 1 (x) dµ 1 (x) (50) + ν -1 µ -1 (U ) -ν -1 U max α, 1 -α -λ x -π U ⊕ 2\U (x) dµ -1 (x) (51) + ν 1 (U ⊕ 2 \U )∩P h 1 ( 2) 1 -λ x -π P h 1 (x) -max 1 -α -λ x -π U (x) , 1 -λ x -π P h 1 (x) dµ 1 (x) (52) + ν -1 φ -1 -1 (U ) 1 -λ x -π U (x) -max 0, 1 -λ x -π N h 1 (x) , α -λ x -π U (x) dµ -1 (x) (53) -ν 1 (U ⊕ 2\U )\P h 1 ( 2) max (1 -α -λ x -π U (x) , 0) dµ 1 (x) (54)
Let us simplify Equation (49) using using additional hypothesis:

• A sufficient condition for the adversarial risk to decrease will be to choose max 1 -α, α -λ x -π P h 1 (x) = α -λ x -π P h 1 (x) , so that the attacker continues to attack on U even with a smaller probability of success, thus reducing the adversarial risk. This gives us α > 1+λ max x∈U

x-π P h 1

2

. In the remaining we consider such an α.

• In particular, this gives α > 1/2 and max α,

1 -α -λ x -π U ⊕ 2 \U (x) = α. Hence line (51) = (1 - α)ν -1 µ -1 (U ) > 0.
• Furthermore, we have that 1

-λ x -π P h 1 (x) -max 1 -α -λ x -π U (x) , 1 -λ x -π P h 1 (x) is equal to : 0 if max = 1 -λ x -π P h 1 (x) 1 -λ x -π P h 1 (x) -(1 -α) + λ x -π U (x) > -(1 -α) elsewhere
Thus the expression on line (52

) > -ν 1 (1 -q)µ 1 ((U ⊕ 2 \ U ) ∩ P h1 ( 2 )). • Also note that, max (1 -α -λ x, π U (x) , 0) < 1 -α. Hence line (54) > -ν 1 (1 -α)µ 1 ((U ⊕ 2 \ U ) \ P h1 ( 2 )).
Finally, ( 52)

+ (54) > -ν 1 (1 -α)µ 1 ((U ⊕ 2 \ U ))
, hence the difference between the adversarial risks is as follows:

∆ R adv > ν 1 (1 -α) (µ 1 (U ) -µ 1 ((U ⊕ 2 ) \ U )) (55)
Since µ 1 is vanishing on U , the expected result holds for α >

Experimental results

In the experimental section, we consider X = [0, 1] 32×32 to be the set of images, and Y = {1, ..., 10} or Y = {1, ..., 100} according to the dataset at hand.

Adversarial attacks

Let (x, y) ∼ D and h ∈ H. We consider the following attacks:

(i) ∞ -PGD attack. In this scenario, the Adversary maximizes the loss objective function, under the constraint that the ∞ norm of the perturbation remains bounded by some value ∞ . To do so, it recursively computes:

x t+1 = Π B . ∞ (x, ∞) x t + β sgn ∇ x L h x t , y (56)
where L is some differentiable loss (such as the cross-entropy), β is a gradient step size, and Π S is the projection operator on S. One can refer to [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF] for implementation details.

(ii) 2 -C&W attack. In this attack, the Adversary optimizes the following objective:

argmin τ ∈X τ 2 + λ × cost(x + τ ) (57)
where cost(x + τ ) < 0 if and only if h(x + τ ) = y. The authors use a change of variable τ = 1 2 (tanh(w) -x + 1) to ensure that x + τ ∈ X , a binary search to optimize the constant λ, and Adam or SGD to compute an approximated solution. One should refer to [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF] for implementation details.

Experimental setup

Datasets. To illustrate our theoretical results we did experiments on the CIFAR10 and CIFAR100 datasets. See (Krizhevsky et al., 2009) for more details.

Classifiers. All the classifiers we use are WideResNets (see [START_REF] Zagoruyko | Wide residual networks[END_REF])) with 28 layers, a widen factor of 10, a dropout factor of 0.3 and LeakyRelu activations with a 0.1 slope.

Natural Training. To train an undefended classifier we use the following hyperparameters. Adversarial Training. To adversarially train a classifier we use the same hyperparameters as above, and generate adversarial examples using the ∞ -PGD attack with 20 iterations. When considering that the input space is [0, 255] 32×32 , on CIFAR10 and CIFAR100, a perturbation is considered to be imperceptible for ∞ = 8. Here, we consider X = [0, 1] 32×32 which is the normalization of the pixel space [0.255] 32×32 . Hence, we choose ∞ = 0.031 (≈ 8/255) for each attack. Moreover, the step size we use for ∞ -PGD is 0.008 (≈ 2/255), and we use a random initialization for the gradient descent. For the ∞ -PGD attack against the mixture m q h , we use the same parameters as above, but compute the gradient over the expected loss (as explained in the main paper).

Evaluation Under Attack. At evaluation time, we use 100 iterations instead of 20 for ∞ -PGD, and the same remaining hyperparameters as before. For the 2 -C&W attack, we use 100 iterations, a learning rate equal to 0.1, 9 binary search steps, and an initial constant of 0.001. We give results for several different values of the rejection threshold: 2 ∈ {0.4, 0.6, 0.8}.

Library used. We used the Pytorch and Advertorch libraries for all implementations.

Machine used. 6 Tesla V100-SXM2-32GB GPUs Computing 2 -C&W on a mixture with Advertorch. The implementation of the 2 -C&W attack in Advertorch takes as input not only the loss, but also the probits of the classifier. Hence, when attacking a mixture we need to compute both the expected loss, and the expected probits of the mixture. See the submitted code for more details.

Experimental details on CIFAR10

Grid search on α. Let us provide some results on the grid search that helped us select the parameter α = 0.06 we present in the main paper. Note that as described in the main paper, α here represents the weight of the new classifier added to the mixture at each step. As shown in Figure 3, when α is small (e.g. 0.01), the accuracy under attack increases slowly for every new classifier added to the mixture. Conversely, when α is to large (e.g. bigger than 0.07) the accuracy under attack rapidly increases for the first classifiers and then plummet when the mixture becomes to big (more than 4 classifiers). This phenomenon can be explained as follows: for bigger values of α, the probability of selecting the first classifiers decreases too quickly, so that after a few steps they are not taken into account anymore. Since the newest classifiers in the mixture are designed not to be robust by themselves but to compensate the weeknesses of the others, the accuracy under attack will then decrease. Hence 1-α is a parameter that represents the 'memory' of the boosting procedure.

The parameter α and the size of the mixture have an influence not only on the accuracy under ∞ -PGD attack, but also on the natural accuracy of the mixture. This is why we selected a mixture with 10 classifiers and α = 0.06. Indeed, this mixture offers the best trade-off between natural accuracy and accuracy under attack. For completeness, we present all evaluations in Table 2.

Additional results on CIFAR100

As we did for CIFAR10, we compare the robustness of Adversarial Training with our boosting procedure on CIFAR100. Since the images have the same dimension, we use the same architectures and sets of hyperparameters as listed in Section 2.2, and only change the dimension of the output to be equal to 100. As shown in Table 4, a mixture of 5 classifiers constructed with our algorithm and α = 0.06 has a better accuracy under attack, as well as a better natural accuracy, than Adversarial Training.

Training method

Natural ∞ -PGD [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF] 0.585 0.271 BAT (n = 5, α = 0.06, bestAUA=True) 0.592 0.402

Figure 1 .

 1 Figure1. Comparison of the distributions µ1 and µ-1 before attack (left) and after attack, according either to the mass penalty (middle) or the norm penalty (right). The blue (dotted and dashed) curve represents the distribution of X|Y = 1, and the red (dashed) one X|Y = -1. The black vertical line is the Bayes optimal classifier for the initial distributions. Finally, the red (lighter) and the blue (darker) areas represents the zones on which the Adversary can change the distributions for mass (middle) and norm (right) penalty.

Figure 2 .

 2 Figure 2. Illustration of adversarial examples (only on class 1 for more readability) crossing the decision boundary (left), adversarially trained classifier for the class 1 (middle), and a randomized classifier that defends class 1. Stars are natural examples for class 1, and crosses are natural examples for class -1. The straight line is the optimal Bayes classifier, and dashed lines delimit the points close enough to the boundary to be attacked resp. for class 1 and -1.

  Based on Theorem 2 we devise a new procedure (Algorithm 1), called Boosted Adversarial Training (BAT) to construct robust classifiers. It is based on three core principles: Adversarial Training, Boosting and Randomization.

  Given a dataset D and a weight update parameter α ∈ [0, 1], Algorithm 1 Boosted Adversarial Training Input : n the number of classifiers, D the training data set and α the weight update parameter.

•

  Number of Epochs: 200 • Batch size: 128 • Loss function: Cross Entropy Loss • Optimizer : SGD algorithm with momentum 0.9, weight decay of 2 × 10 -4 and a learning rate that decreases during the training as follows: if 60 ≤ epoch < 120 0.004 if 120 ≤ epoch < 160 0.0008 if 160 ≤ epoch < 200

Table 1 .

 1 ) of Boosted and classical Adversarial Training under attack with ∞ -PGD run for 100 iterations. Evaluation on CIFAR10 without data augmentation. Accuracy under attack of a single classifier adversarially trained and the mixture formed with our Algorithm 1. The evaluation is made with ∞-PGD and 2-C&W attacks both computed with 100 steps. For

	Training method	Natural l ∞ -PGD	2 -C&W 0.4	2 -C&W 0.6	2 -C&W 0.8
	Natural	0.88	0.00	0.00	0.00	0.00
	(Madry et al., 2018)	0.83	0.42	0.67	0.60	0.51
	BAT (n = 10, α = 0.06)	0.80	0.58	0.70	0.65	0.59

Table 4 .

 4 Evaluation on CIFAR100 without data augmentation. Accuracy under attack of a single classifier adversarially trained and the mixture formed with our algorithm. The evaluation is made with ∞-PGD computed with 100 steps.

We prove this result in the supplementary material.

As for P p h we omit p when it is clear from the context.

p = 2 for Ωnorm and p = ∞ for Ωmass.

Selecting the first element of the mixture. Our algorithm creates classifiers in a boosting fashion, starting with an adversarially trained classifier. There are several ways of selecting this first element of the mixture: use the classifier with the best accuracy under attack (option 1, called bestAUA), or rather the one with the best natural accuracy (option 2). Table 3 compares both options.

Beside the fact that any of the two mixtures outperforms the first classifier, we see that the fisrt option always outperforms the second. In fact, when taking option 1 (bestAUA = True) the accuracy under ∞ -PGD attack of the mixture is 3% better than with option 2 (bestAUA = False). One can also note that both mixtures have the same natural accuracy (0.80), which makes the choice of option 1 natural.


Rafael Pinot
email: rafael.pinot@dauphine.fr

Florian Yger

Cédric Gouy-Pailler

Jamal Atif

A unified view on differential privacy and robustness to adversarial examples

Keywords: Differential Privacy, Adversarial Examples, Renyi divergence

) and our definition of robustness share several similarities. We finally discuss how can both communities benefit from this connection to transfer technical tools from one research field to the other.

Introduction

With the large adoption of machine learning techniques in several domains (including critical ones), researchers and practitioners are observing growing concerns on the security and privacy of the tools they develop. A primary concern is to guarantee that sensitive information from the used databases are not leaked, accidentally disclosed, or inferred from the sole release of the model (privacy preserving algorithms). Beyond preserving privacy, a crucial issue of recent machine learning approaches is to protect the methods against malicious users targeting their weaknesses (e.g adversarial examples, or poisoning attacks).

Privacy preserving algorithms: Several definitions have been introduced to characterize privacy preserving algorithms in the context of machine learning and data publishing. Among them, differential privacy has become the dominant standard by providing a formal and adaptive conception of privacy preserving data-analysis. It has been broadly investigated in numerous frameworks and applications (see [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] for a complete overview of the field). An algorithm is said to be differentially private if, given two close databases, it produces statistically indistinguishable outputs. Highly correlated to the notion of "closeness" both in the input and output spaces, most frameworks [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF][START_REF] Chatzikokolakis | Broadening the scope of differential privacy using metrics[END_REF][START_REF] Elsalamouny | Generalized Differential Privacy: Regions of Priors That Admit Robust Optimal Mechanisms[END_REF][START_REF] Dwork | Concentrated differential privacy[END_REF] rely on divergences/pseudo-metrics between probability measures to characterize this notion. Recently, Mironov [START_REF] Mironov | Rényi differential privacy[END_REF] proposed to use the well-known Renyi divergence to obtain a more general definition of privacy. This notion is well defined, and it exhibits principled theoretical advantages over previous definitions, which makes it the most general formulation of differential privacy introduced so far.

Adversarial examples attacks: Modern neural networks achieve state of the art performances in a variety of domains. However, it has been shown that such neural networks can be vulnerable to adversarial examples, i.e. imperceptible variations of legitimate examples crafted to deliberately mislead a machine learning algorithm [START_REF] Szegedy | Intriguing properties of neural networks[END_REF]. Since then, attacks and defenses are developed in a tight backand-forth(see [START_REF] Carlini | On evaluating adversarial robustness[END_REF] for a complete overview of the field). Most past defenses were deterministic (see e.g [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF][START_REF] Samangouei | Defense-GAN: Protecting Classifiers Against Adversarial Attacks Using Generative Models[END_REF]), but recently, the idea of using randomization in the learning process to ensure robustness against adversarial examples attacks is gaining in interest [START_REF] Lecuyer | Certified robustness to adversarial examples with differential privacy[END_REF][START_REF] Cohen | Certified adversarial robustness via randomized smoothing[END_REF][START_REF] Pinot | Theoretical evidence for adversarial robustness through randomization: the case of the exponential family[END_REF].

Outline of the paper: We first recall the key notions of probabilistic mapping and Renyi divergence in Section 2. Then we introduce the notion of differential privacy and present its generalization called Renyi-differential privacy in Section 3. Section 4 presents the problem of adversarial examples and our generalized definition of robustness to these attacks. Finally we discuss in Section 5 the similarity between the two concepts, and an application to image classification in which we transfer tools from differential privacy to make algorithms robust to adversarial examples.

Preliminaries

Let us consider two arbitrary metric spaces (X , d X ), and (Y, d Y ), let σ(Y) be a σ-algebra over Y and P(Y) be the set of probability measures over (Y, σ(Y)). The notion of probabilistic mapping is the central concept used in differential privacy, we recall it below.

Definition 1 (probabilistic mapping).

A probabilistic mapping from X to Y is a mapping M : X → P(Y). Given x, M outputs a probability measure M(x).

To get a numerical output y out of M for x, one needs to sample y ∼ M(x).

Informally, a probabilistic mapping M is said to be differentially private, if given x and x ′ two close inputs (i.e d X (x, x ′ ) is small enough) it outputs two close measures M(x), and M(x ′ ). To evaluate the closeness between this two probability measures in the formal definition of differential privacy, Dwork et. al [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] uses the maximum divergence, which is a special case of the more general Renyi divergence defined as follows:

Definition 2 (Renyi divergence of order λ [START_REF] Rényi | On measures of entropy and information[END_REF]). Let us consider µ 1 , µ 2 ∈ P(Y) two probability measures, both dominated by a third measure ν. The Renyi divergence of order λ between µ 1 and µ 2 writes

D λ (µ 1 , µ 2 ) := 1 λ -1 log Y g 2 (y) g 1 (y) g 2 (y) λ dν(y).
Where g 1 and g 2 are the probability density of µ 1 , and µ 2 with respect to ν.

The Renyi divergence (see [START_REF] Van Erven | Rényi divergence and kullback-leibler divergence[END_REF] for more details) is defined for λ ∈ (1, ∞). It equals the Kullback-Leibler divergence when λ → 1, and the maximum divergence (denoted D ∞ ) when λ → ∞. It also has the very special property of being non decreasing with respect to λ. This divergence is very common in machine learning (especially the Kullback-Leibler divergence), statistics, and information theory. Using this notion of closeness between distributions, one can define both differential privacy (with D ∞ ), and Renyi-differential privacy (with D λ ).

Differential privacy and its generalization

We now present the definition of differential privacy, and its Renyi generalization.

Definition 3 (Classical differential privacy [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]). Let X be a space of databases, Y an output space, and "∼ h " denoting the that two databases from X only differ from one row. A probabilistic mapping M from X to Y is called differentially private if for any x, x ′ ∈ X s.t. x ∼ h x ′ and for any Y ∈ σ(Y)

on has M(x)(Y ) ≤ exp(ǫ) M(x ′ )(Y ).
Definition 4 (Metric differential privacy [START_REF] Chatzikokolakis | Broadening the scope of differential privacy using metrics[END_REF]). Let ǫ > 0, (X , d X ) an arbitrary (input) metric space, and Y an output space. A probabilistic mapping

M from X to Y is called (ǫ, α)-d X private if for any x, x ′ s.t d X (x, x ′ ) ≤ α, one has D ∞ (M(x), M(x ′ )) ≤ ǫ.
Classical differential privacy is a particular case of Metric differential privacy where X is a set of tabular databases, d X is the hamming distance, and α = 1 3 . We finally introduce a general form of privacy definition that complies both with classical, and metric differential privacy, namely Renyi-differential privacy.

Definition 5 (Renyi differential privacy [START_REF] Mironov | Rényi differential privacy[END_REF]). Let ǫ > 0, (X , d X ) an arbitrary (input) metric space, and Y the output space. A probabilistic mapping M from

X to Y is called (λ, ǫ, α)-d X Renyi-private if for any x, x ′ s.t d X (x, x ′ ) ≤ α, one has D λ (M(x), M(x ′ )) ≤ ǫ
According to Definition 5, it is clear that both Metric, and differential privacy are included in Renyi-differential privacy. Moreover, note that the definition above is based on arbitrary spaces, and metrics (X , d X , and Y). Hence, one can define Renyi-privacy for an arbitrary learning task, even if preserving privacy in this task has no clear semantic. In the following, we present robustness against adversarial examples, and how robustness and privacy are formally similar.

Robustness to adversarial examples

Let us now consider a classification task over X (i.e Y = [N ]). Let us denote D the ground-truth distribution one tries to learn, and h the classifier at hand (trained over some subset of X × Y). An adversarial example attack for x is a small perturbation of x that fools the results of h. For instance, for image classification, the changes from the initial image to the perturbed one are visually imperceptible, but images are classified with two different labels. The problem of generating an adversarial example from an input x writes min d X (x, x + τ ) , where τ ∈ X , and h(x

+ τ ) = h(x) (1)
Even if adversarial examples are intensively studied, a broadly accepted definition of robustness against adversarial attacks does not seem to exist. We settle that the notion of prediction-change risk initially formalized in [START_REF] Diochnos | Adversarial risk and robustness: General definitions and implications for the uniform distribution[END_REF], and implicitly used in e.g [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] is a suitable start-point. Given a classifier h, it is defined as

P x∼DX [∃x ′ ∈ B(x, α) s.t h(x ′ ) = h(x)] .
Where B(x, α) = {x ′ ∈ X s.t d X (x, x ′ ) ≤ α}, and D X is the marginal distribution of D with respect to X . From this we can derive a definition of robustness to adversarial attacks.

Definition 6 (Adversarial robustness).

A classifier h is said to be (α, γ)-

robust if P x∼DX [∃x ′ ∈ B(x, α) s.t h(x ′ ) = h(x)] ≤ γ.
Regarding [START_REF] Xie | Mitigating adversarial effects through randomization[END_REF][START_REF] Moosavi-Dezfooli | Divide, denoise, and defend against adversarial attacks[END_REF], probabilistic mappings seem to be good candidates to defend against adversarial example attacks. The following definition gives a generalized notion of robustness against adversarial examples attacks complying with probabilistic mappings.

Definition 7 (Generalized adversarial robustness). Let D P(Y) be a metric/divergence on P(Y). A randomized classifier M is said to be

D P(Y) -(α, ǫ, γ)- robust if P x∼DX ∃x ′ ∈ B(x, α) s.t D P(Y) (M(x ′ ), M(x)) > ǫ ≤ γ.
Definition 7 is fully general, and depends on the metric/divergence D P(Y) one chooses to consider. In particular, if one restricts the study of randomized classifiers to Dirac measures, and sets D P(Y) to be the trivial distance (which takes the value 0 where the measures are equal and 1 elsewhere), definitions 6 and 7 match. One can refer to [START_REF] Pinot | Theoretical evidence for adversarial robustness through randomization: the case of the exponential family[END_REF] for more details on definition 7 and proof on the interest of choosing D P(Y) to be the Renyi divergence D λ .

Links between differential privacy and robustness to adversarial attacks

The starting point to highlight the similarities between both notions are Definitions 5 and 7. A first observation is that in an abstract way (i.e. without instantiating the spaces), and by considering the Renyi divergence both definitions are strictly equivalent. This suggests the following claim, the proof of which is straightforward since it follows from the definitions.

Claim (Renyi-DP ⇐⇒ D λ -robustness). An algorithm M is D λ -(α, ǫ, 0)-robust if and only if M is D X -almost surely (λ, ǫ, α)-d X Renyi-differentially private.
While this mathematical equivalence is important from a theoretical point of view, we will now go into deeper details to consider practical implications of this formulation. Without loss of generality, practical settings, in which privacy or robustness are needed, can be classified into three categories:

1. Differential privacy and adversarial robustness need to be ensured: prominent examples of this situation are image or voice classification. In this case, instead of considering two separate methodologies, both problems can be treated simultaneously, with the same tools.

2. Adversarial robustness has to be ensured but there are no special constraint on privacy: in this case, thanks to Claim 5, one could be able to design new defense mechanisms against adversarial examples attacks based on the extensive literature on differential privacy. Accordingly, one can design new defense mechanisms against adversarial example attacks based on the noise injection techniques traditionally used in the differential privacy literature proposed in e.g [START_REF] Pinot | Theoretical evidence for adversarial robustness through randomization: the case of the exponential family[END_REF][START_REF] Lecuyer | Certified robustness to adversarial examples with differential privacy[END_REF][START_REF] Cohen | Certified adversarial robustness via randomized smoothing[END_REF]. Note that, even though the formal connecting between differential privacy and robustness to adversarial examples is not identically stated in [START_REF] Lecuyer | Certified robustness to adversarial examples with differential privacy[END_REF][START_REF] Cohen | Certified adversarial robustness via randomized smoothing[END_REF] and this note, both visions are not conflicting.

3. Differential privacy needs to be ensured but robustness to adversarial examples is not needed: while this setting does not seem intuitively natural, we advocate that a few emerging frameworks currently actively developed to test against adversarial robustness could also be used to evaluate differential privacy with minor adaptations.

Point 2 is currently being investigated. We however argue that the explicit link we just draw between differential privacy and robustness to adversarial examples might lead practitioners from both side to investigate further points 1 and 3.

Classical definitions set α = 1, and argue that one can always scale dX such that dX ≤ 1 fits the notion of "close enough". We rather keep dX unchanged and take an arbitrary α instead. Both definitions are equivalent.