Je Remercie Également

Alexandre Araujo

Raphael Ettedgui

Arnaud Grivet-Sebert

Geovani Rizk

Laurent Meunier

Anne Morvan

Renaud Sirdey

Martin Zuber

En premier lieu, je veux remercier l'ensemble des enseignants qui m'ont inculqué leur amour d'apprendre et de transmettre. Que ce soit au lycée, ou pendant mes études supérieures, j'ai croisé la route de personnes passionnées qui m'ont donné l'envie de faire le métier de chercheur. Je souhaite exprimer ma profonde reconnaissance envers Stéphane Canu et Panayotis Mertikopoulos pour avoir accepté d'être les rapporteurs de cette thèse, et pour leur lecture attentive du manuscrit ainsi que leurs commentaires détaillés. Je remercie Francis Bach d'avoir présidé mon jury ainsi que Sébastien Bubeck, Cordelia Schmid et Michèle Sébag d'avoir accepté d'en faire partie. C'est un véritable honneur d'avoir pu leur présenter mes travaux.

Je remercie évidemment Jamal Atif, Cédric Gouy-Pailler et Florian Yger pour ces trois années passées à mes côtés et pour la qualité de leur encadrement. Si cette thèse a été pour moi une expérience professionnelle et personnelle aussi réussie, je le leur dois en grande partie. Je remercie Jamal pour sa rigueur scienti que et son exigence intellectuelle. Il m'a appris à prendre du recul et à avoir une vision plus globale des domaines que nous avons abordés. Son investissement scienti que et humain dans mes travaux et mon bien être a été sans faille. J'espère pouvoir être un jour pour un de mes étudiants le directeur de thèse qu'il a été pour moi. Je remercie Cédric pour son pragmatisme et sa sérénité. Il m'a permis de faire avancer mes ré exions dans un environnement calme et bienveillant. Mais surtout, il a su déceler en moi la volonté de di user mes connaissances à un public plus large et il m'a o ert la chance de me former aux di érents aspects de la médiation scienti que. Pour cela, et pour tant d'autres choses, je lui suis éternellement reconnaissant. Je remercie Florian pour sa prévenance et pour m'avoir fait partager son expérience internationale. Il m'a incité en début de thèse à postuler à un programme d'échange avec un pays qu'il connait bien : le Japon. Ce voyage m'a permis de prendre du recul sur le monde de la recherche et a été une expérience de vie extraordinaire. Cet intérêt commun pour l'univers nippon nous a rapprochés et a marqué le début d'une belle relation humaine.

Speaking of my Japanese experience, I would like to thank the JSPS and the CNRS for making this stay possible and Hisashi Kashima for welcoming me in his team at Kyoto University. It was a pleasure to work with him and his collaborators and I hope we will meet again soon.

Pendant ces trois années, j'ai eu l'occasion de collaborer avec des chercheurs formidables que ce soit à Dauphine ou au CEA. Je remercie tout particulièrement Yann Chevaleyre et Benjamin Negrevergne pour leurs conseils et pour tous ces moments où ils m'ont fait partager leur expérience.

Foreword

Funding & grants

This thesis was prepared in the MILES team, part of the LAMSADE lab, at Université Paris Dauphine-PSL, and the LI A lab, at CEA LIST from October to October . It was funded by a grant from CEA. Rafael Pinot was also awarded with a Summer Program Fellowship from the Japanese Society for the Promotion of Science in to spend three months in Kyoto university -invited by Professor Hisashi Kashima -as a visiting scholar. Finally, this work was granted acces to OpenPOWER prototype from GENCI-IDRIS under the Preparatory Access AP , HPC resources of IDRIS under the allocation -made by GENCI, and HPC resources of FactoryIA partially funded by région Ile-de-France -projet SESAME .

Manuscript main focus

This thesis work focused on the notions of security and privacy in machine learning. We list below some of the contributions we made. In the main part of this manuscript, we try to give a clear overview of our contributions to the eld of robust machine learning. We deliberately focus on some of our most signi cant contributions to make the manuscript light and easy to follow. This thesis work also took other directions including unsupervised learning under privacy constraints, private deep learning, and cryptography.

Contributions discussed in the main part of the manuscript

• "Theoretical evidence for adversarial robustness through randomization" (chap. ).

Journal version, ongoing work .

• "Randomization matters, how to defend against strong adversarial attacks" (chap. ).

International Conference on Machine Learning (ICML)

. R. Pinot, R. Ettedgui, G. Rizk, Y. Chevaleyre, J. Atif.

• " A uni ed view on di erential privacy and robustness to adversarial examples" (chap. ).

Workshop on Machine Learning for CyberSecurity (ECML-PKDD)

. R. Pinot, F. Yger, C. Gouy-Pailler, J. Atif.

• "Theoretical evidence for adversarial robustness through randomization" (chap. & ).

Avances in Neural Information Processing (NeurIPS)

. R. Pinot, L. Meunier, A. Araujo, H. Kashima, F. Yger, C. Gouy-Pailler, J. Atif.

Foreword

Other contributions

• "SPEED: Secure, PrivatE, and E cient Deep learning" (app. C).

preprint, ongoing work . A. Grivet Sébert, R. Pinot, M. Zuber, C. Gouy-Pailler, R. Sirdey.

• "Advocating for Multiple Defense Strategies against Adversarial Examples" (app. A).

Workshop on Machine Learning for CyberSecurity (ECML-PKDD)

. A. Araujo, L. Meunier, R. Pinot and B. Negrevergne.

• "Graph-based Clustering under Di erential Privacy" (app. B).

Uncertainty in Artificial Intelligence (UAI)

. R. Pinot, A. Morvan, F. Yger, C. Gouy-Pailler, J. Atif.

Scienti c Outreach

Throughout this thesis, we did not only focus on the production of scienti c material. We also engaged in scienti c outreach through demos and press releases. We believe that it is also the role of scientists, especially in the eld of machine learning and arti cial intelligence, to explain their work to a wider audience within the scienti c community, and to increase public knowledge on the challenges and issues of new technologies. Here are some of our contributions.

• "Attaques adversariales: comprendre pour atténuer les risques" (media article).

Clef du CEA num . Contributors: R. Pinot, C. Gouy-Pailler.

• "AI vs Wild. How to strengthen neural networks of AI systems" (demo).

Consumer Electronic Show Las Vegas

. Contributors: C. Gouy-Pailler, E. Kawasaki, R. Pinot, F. Valente.

• "Randomization based defenses against adversarial examples" (demo).

DIGIHALL days Paris Saclay

. Contributors: R. Pinot, C. Gouy-Pailler.

• "La recherche et les risques inhérents à l'IA" (media article).

Préventique num

• Contributors: R. Pinot, C. Gouy-Pailler.

Pedagogical responsibilities

Last but not least, teaching is an integral part of a doctoral journey, and the rapid development of machine learning requires the design of new learning materials. During the time of this thesis, I also participated in the development of two new machine learning courses.

Foreword

• "Mathématiques du machine learning" -Université Paris-Dauphine -PSL.

Master IDD première année -. Lecturer: R. Pinot.

• "Trustworthy machine learning in practice" -Université Paris-Dauphine -PSL.

Executive Master

-. Lecturers: A. Araujo, R. Pinot, G. Rizk.

Reading guide

The organization of the manuscript has been designed to be simple, and the chapter titles should be self-explanatory. We advise the reader to follow a linear reading style -chapter by chapter. However, readers already familiar with the concepts and existing results in learning theory and adversarial classi cation may skip Chapter and go directly to the technical chapters , , and . Each chapter is divided into four main parts.

. An introduction to the speci c issues and terminology of the chapter -one section.

. Simple results with a focus on consequences and interpretations -one or two section(s). Machine learning models are part of our everyday life and their weaknesses in terms of security or privacy can be used to harm us either directly or indirectly. It is thus crucial to be able to account for, and deal with, any new vulnerabilities. Besides, the legal framework in Europe is evolving, forcing practitioners -from both the private and the public sectors -to adapt quickly to these new concerns. In this chapter, we rst present the context in which the idea of this thesis was born and our main motivations in Section . . Then, we present the problem which we have chosen to focus on: robust classification under adversarial perturbation in Section . . Finally, we summarize some of our contributions to the domain in Section . . .

Introduction

. Context & motivations

In the s, the rst arti cial intelligence projects were developed . At that time, the ultimate goal was the replication of human intelligence. The proposed approaches consisted of using mathematics to describe the world, model the human perception, and simulate the cerebral mechanisms. Seventy years later, the initial objective of replication of brain's functions has been largely supplanted by technological projects aiming to reproduce human performance in simple cognitive tasks [ ]. To this end, deep neural networks achieve state-of-the-art performance in a variety of domains such as natural language processing [ ], image recognition [ ] and speech recognition [ ]. The impressive e cacy of AI-driven technologies has made them omnipresent both in industry and in some public sectors. However, recent studies have identi ed several major aws of machine learning and data analysis such as information leakage [ ] or vulnerability to adversarial perturbations [ ]. These shortcomings raise questions about the legal liability of model providers and cause practitioners to reevaluate the trust they place in the systems they use.

. . Dealing with privacy issues: the General Data Protection Regulation

Protecting individuals' privacy against information leakage while producing statistical analysis is already an old topic; its foundations were largely established in the s [ , , ]. These concerns were brought back to light notably in , when Narayanan et al. [ ] demonstrated a robust de-anonymization procedure on the dataset released for the "Net ix Price contest". In , the European Union provided an answer to these concerns from a legal standpoint by publishing the General Data Protection Regulation [ ] -GDPR. This regulation aims to de ne the duties of model providers with respect to the personal data they use -see Figure . for an overview of the key principles . In order to comply with the GDPR, industries and governments are required to design models that preserve privacy. These new obligations, coupled with already existing users' concerns regarding their personal data, have made privacy issues the priority within the computer science community. Accordingly, several de nitions have been introduced to characterize privacy preserving algorithms in the context of machine learning and data publishing [ ]. Among them, di erential privacy [ ] has become the dominant standard to provide a formal and adaptive conception of privacy preserving data analysis. The rationale is that one individual's information is protected if "the outcome of any analysis is

We do not claim to provide a thorough presentation of this regulation here. To keep the discussion concise, we only highlight some points that we -as computer scientists -believe to be central.

essentially equally likely, independent of whether any individual joins, or refrains from joining, the data set" [ ].

More formally, an algorithm is said to be di erentially private if, given two similar databases, it produces statistically indistinguishable outputs. This privacy de nition has been broadly investigated in numerous frameworks and applications -see [ ] for a book of reference. Overall, privacy preserving machine learning is now a well-known and accepted concept. It relies on a proper legal framework, and technical solutions such as di erential privacy are consistently being implemented by major companiese.g. Google [ , ] -and public entitiese.g. the U. S. Census Bureau [ ]. The GDPR has been a real revolution both from a legal and scienti c standpoint. In our point of view, the battle for users' privacy is not over yet, but signi cant e orts have been made both by practitioners and researchers to meet the privacy requirements of our era.

. . Beyond privacy: interpretability, trust and and adversarial attacks

Despite focusing on data protection, the GDPR also includes an article -Article -on the right to receive an explanation for an algorithmic decision [ ]. This raises a number of questions on both the interpretability of machine learning algorithms and the trust users place in them [ ].

While there is no clear consensus yet on the de nition of interpretability or trust in machine learning [ ], recurring themes such as social bias [ ] or vulnerability to perturbations [ , ] often resurface. These new concerns, along with the privacy issues mentioned above, are sometimes put together under the name trustworthy machine learning and have lately attracted a lot of attention . Furthermore, the deployment of machine learning in real-world systems and the recent legal progress on data protection and decision explanation should encourage intensifying the research in this new domain.

In this thesis, our primary focus is the models' vulnerability to adversarial perturbations. The term adversarial perturbationa.k.a. adversarial attack -denotes a carefully chosen and humanly imperceptible perturbation that causes a model to fail. The existence of these vulnerabilities shows how far the deep learning community has drifted from the initial goal of reproducing the human perception. To demonstrate the genuine security issue that adversarial attacks represent, we take the example of self-driving cars. Recently, technology companies have made enormous investments in self-driving carsi.e. autonomous vehicles equipped with a tremendous amount of cameras and sensors that help them move with little to no human input. Much of the information gathered by these cars is processed using in-vehicle machine learning models. In particular, vision tasks process images through deep neural networks. However, recent works [ , , , ] have indicated that these very systems can be fooled by real-world adversarial attacks on tra c signse.g. by adding stickers on the tra c sign.

Figure . illustrates an attack setting where an adversary added such a sticker on a tra c sign. In the rst schematic -at top -the car captures the original version of the tra c sign, recognizes it as a speed limitation, and goes on normally. In the second schematic, at bottom, the red car captures an adversarial version of the tra c sign and recognizes it as a stop sign causing an accident with the blue car. Note that in this case, no human would have change his/her decision, but the car did. This gap between the human and model responses could lead to various security issues -here for example an accident triggered by an attack on a tra c sign. These technologies are currently being deployed; it is thus crucial to adapt quickly to this new threat both from a technical and legal standpoint. In the sequel, we will use self-driving cars as a running example. Accordingly, we will focus our application setting to deep learning for image classi cation.

. Problem setting(s)

The vulnerability of machine learning and deep learning models to adversarial attacks is a critical security issue, especially for high-stakes applications such as self-driving cars. It is essential for the community to understand the nature of this phenomenon in order to mitigate the threat. In this section, we start by giving some reminders on the problem of classi cation in the standard setting i.e. without adversary. Then we present the problem of classi cation in the adversarial setting and identify the core questions to which we aim to provide some answers. Finally, we outline the main questions we wish to address in this manuscript.

. . Classi cation in the standard setting

Let us consider the supervised classi cation problem with an input space Xe.g. images -and an output space Ye.g. label describing the images. For simplicity here, we will consider that Y = {1, . . . , K}, meaning that each description is characterized by an integer between 1 and K. The goal of a supervised machine learning algorithm is to design an accurate prediction function c : X → Ya.k.a. classi er -that for any image x ∈ X matches a label y ∈ Y that correctly describes the image. To nd c, the learner has access to a set of n input-output pairs S := {(x  , y 1 ), . . . , (x n , y n )}a.k.a. training sample. The main assumption behind the theory of classi cation is that there exists some ground truth distribution D that describes the connection between the images and the labels and from which the pairs (x i , y i ) are drawn i.i.d..

To build a classi er, the usual strategy is to build a hypothesis function h : X → R K that for any x ∈ X outputs a set of scores h(x) := [h 1 (x), . . . , h K (x)] -one for every possible label. Then, the prediction function c outputs the label with the better score for h. More formally, c writes c(x) := argmax k∈[K] h k (x). The problem then amounts to build a function h that describes well the connection between the images and the labels. To do so, the learner aims to select h * from a prede ned set H, called the hypothesis class, that solves -or approximate -the risk minimization problem. This optimization problem writes inf h∈H E (x,y)∼D [L(h(x), y)] , ( . ) where L : R K × Y → R is some loss function that measures how well h ts the ground-truth distribution. If L is su ciently well chosen -typically if it is convex and smooth [ ] -and if the hypothesis class H is rich enough, the classi er c we get will have a small probability to give the wrong label for a new sample (x, y) ∼ D.

In practice, the learner does not have access to the ground-truth distribution; hence it cannot estimate the risk E (x,y)∼D [L(h(x), y)]. To nd an approximate solution for Problem ( . ), a learning algorithm solves the empirical risk minimization problem instead. In this case, we simply replace the risk by its empirical counterpart over the training S := {(x  , y 1 ), . . . , (x n , y n )}. It writes

inf h∈H 1 n n i=1 L(h(x i ), y i ) . ( . )
Then, to evaluate how far the selected hypothesis h S is from the optimal h * , one wants to upper bound the di erence between the risk and the empirical risk of any h ∈ H. This di erence is known as the generalization gap. Intuitively, if we can control the di erence between the risk and the empirical risk of any function in h ∈ H, then the risk minimization problem and the empirical risk minimization problem will have similar solutions.

In light of the above, the choice of the hypothesis class H in supervised classi cation is critical. On one hand, if it is too large, it will be hard to control the generalization gap of all the elements in the class and the optimization problem is di cult. On the other hand, if it is too small, the generalization gap will be easy to control but the class might not be su ciently rich to describe the behavior of the ground-truth distribution, which leads to poor prediction functions. Another key component is the size of the training sample. If we have enough training samples, thanks to the uniform law of large numbers, the empirical risk of any hypothesis is a good approximation for its true risk. More precisely, for some well chosen hypothesis classes one can bound the generalization gap of any hypothesis by O 1 minimization -Problem ( . ). Let us now present the alternative classi cation setting we will study in this manuscript, namely Classification under adversarial perturbation.

Reading note. The interested reader can find a more thorough introduction to classification and learning theory in Chapter .

. . Classi cation under adversarial perturbation

Given a hypothesis h ∈ H and an image-label pair (x, y) ∼ D, the goal of an adversary is to nd a perturbation τ ∈ X such that the following assertions both hold.

• The perturbation is imperceptible to humans. Strictly speaking, this means that a human cannot visually distinguish the standard example x from the adversarial example x+τ . In a less conservative viewpoint, this could also mean that a human will give the same answer if it is asked to classify x or x + τ . For simplicity, we consider the strict de nition here.

• The perturbation modi es x enough to make the classi er misclassify. More formally, the adversary seeks a perturbation τ ∈ X such that c(x + τ ) = y.

Although the notion of imperceptible modi cation is very natural for humans, it is genuinely hard to formalize. Despite these di culties, a su cient condition to ensure that the attack will remain undetected is to constrain the perturbation τ to have a small p norm. This means that for any p ∈ [1, ∞], there exists a threshold α p > 0 for which any perturbation τ is imperceptible as soon as τ p ≤ α p . The literature on adversarial attacks for image classi cation [ , ] usually uses either an ∞ or an 2 norm as a surrogate for imperceptibility .

Remark .

Note that these norms have very di erent behaviors in high-dimensional spaces, hence the choice of p has a crucial impact on the answer one provides to Q and Q below. We will further discuss this point in Chapter and Appendix A. Adversarial examples represent a serious security threat that machine learning models should deal with. To do so, we need to revisit the standard risk minimization by incorporating the adversary in the problem. The goal becomes to minimize the worst-case risk under α p -bounded manipulations. We call this problem the adversarial risk minimization. It writes

inf h∈H E (x,y)∼D sup τ ∈Bp(αp)
L(h(x + τ ), y) , ( . ) where B p (α p ) := {τ ∈ X s.t. τ p ≤ α p }. In this new problem, the adversary focuses on optimizing the inner maximization, while the classi er tries to get the best hypothesis h * from H "under attack". In the standard setting, we can most of the time design su ciently rich hypothesis classes such that the risk minimization problem gives a solution h * with small risk. But in the adversarial setting, it becomes unclear whether this statement still holds. Hence the following question.

Sometimes, the adversary uses an 1 norm [ ] or an 0 semi-norm [ ].

Q : Is there some hypothesis class H for which the adversarial risk minimization problem has a solution h * with small adversarial risk?

At a rst glance -looking at the empirical literature on adversarial examples -the answer seems to be no. Indeed, a large body of works has been trying to design new models that would be less vulnerable to the adversarial setting [ , , , , ] but most of them were provenin time -to o er only limited protection against more sophisticated attacks [ , , , , ]. Nevertheless, it is important to investigate this question from a theoretical point of view to provide either de nitive negative answers or to design more robust models.

Let us suppose for a moment that Q has a positive answer and that we can design a hypothesis class H for which the adversarial risk minimization has a solution h * with small adversarial risk. By analogy with the standard setting, given n training examples S := {(x  , y 1 ), . . . , (x n , y n )}, we want to nd an approximate solution to the adversarial risk minimization by studying its empirical counterpart, the empirical adversarial risk minimization. This optimization problem writes ) In the presence of an adversary, two major issues appear in the empirical risk minimization. First, as recently pointed out by Madry et al. [ ], the adversarial generalization gapi.e. the gap between the empirical adversarial risk and the adversarial risk -can be much larger than in the standard setting. Indeed, the adversary makes the problem dependent on the dimension of X . Hence, in high-dimensional spacese.g. for images -one needs much more samples to classify correctly [ , ]. Second, nding an approximated solution to the adversarial risk minimization is not always su cient. Two recent works [ , ] gave theoretical evidence that training a robust model may lead to an increase of its standard risk. Hence nding a good approximation for the adversarial classi cation problem -Problem ( . ) -may lead to a poor solution for the standard problem -Problem ( . ). Accordingly, a second question emerges.

inf h∈H 1 n n i=1 sup τ ∈Bp(αp) L(h(x i + τ ), y i ) . ( .
Q : Can we find a class H and a hypothesis h * ∈ H that simultaneously has small standard and adversarial risks?

Analyzing the adversarial classi cation problem -Q

Our rst contribution consists in building new intuitions on the adversarial classi cation problem. To do so, we cast the adversarial risk minimization -Problem ( . ) -as an infinite zero-sum game between a defender -the learner -and an adversary that produces adversarial examples. In this new setting, we obtainw the following results.

. We demonstrate the non-existence of a Nash equilibrium in the game when both the defender and the adversary play deterministic strategies. This, coupled with some recent results from related works [ , ], entails that deterministic hypothesis classes may not be good candidates to provide a positive answer to Q .

. From a game theoretical standpoint, the natural next step is to investigate randomized strategies. We focus on randomizing the strategies for the defender -leaving the adversary strategies unchanged. In this context, we demonstrate that randomized classi ers can outperform deterministic ones in terms of worst-case theoretical guarantees -Problem ( . ). Therefore, we identify randomized classi ers as good candidates to answer Q positively.

Theoretical properties of randomized classi ers -Q & Q

For our second contribution, we study randomized classi ers through the prism of learning theory and information theory. By analogy with the deterministic case, we de ne a notion of robustness for randomized classi ers. This de nition boils down to forcing the classi er to satisfy local Lipschitzness with respect to the p norm on X , and a probability metric on Y. Denoting H Lip the class of randomized classi er that respect this Lipschitz condition, we present the following results.

. We show that for any h ∈ H Lip , we can upper-bound the gap between the risk and the adversarial risk of h. This result says that any good approximation of the risk minimization problem -Problem ( . ) -on H Lip is also a good approximation of the adversarial risk minimization -Problem ( . ). This means that H Lip is a good candidate to answer Q .

. We devise an upper-bound on the generalization gap of any h in H Lip . This means that, for a su ciently large training sample, solving the ERM -Problem ( . ) -on H Lip can provide a good approximate solution to the risk minimization problem. Since we can also bound the gap between the adversarial and the standard risk, this gives answers to both Q and Q . Note, however, that this result relies on a strong assumption on X that does not always bypass dimensionality issues. The problem of nding a subclass of H that provides tighter generalization bounds is an open question.

Practical schemes based on di erential privacy literature -Q

Previous contributions identi ed a class of randomized hypotheses H Lip , that answers both Q and Q -at least partially. But they gave no practical way to design this class. Our nal contribution tackles this issue by drawing lessons learned from privacy preserving machine learning. More precisely our contribution is as follows.

. We highlight some links between our de nition of robustness and the de nition of differential privacy. Both frameworks build upon the same theoretical groundi.e. stability with respect to probability metrics. Therefore, results obtained so far in di erential privacy can easily be transferred to design robust randomized classi ers.

. Based on this idea, we use two famous tools from di erential privacy -namely noise injection and post-processing -to design classes of robust randomized classi ers. In particular, we show that our previous ndings are applicable to a wide range of machine learning models, provided some minor adaptations. We further corroborate our ndings with experimental results using deep neural networks on standard image datasets -namely CIFAR and CIFAR [ ]. These models can simultaneously provide accurate prediction and reasonable robustness, giving practical answers to Q .

Outline of the thesis

The remainder of the manuscript is organized as follows. Chapter presents an overview of the domain of adversarial classi cation. Then, Chapters , and are devoted to the three main contributions we just presented above. Finally, Chapter concludes this work with additional discussions and open problems. Appendices provide a high-level summary of some additional results obtained during this thesis in terms of robustness to adversarial examples -Appendix A, di erential privacy -Appendix B, and cryptography for deep learning -Appendix C.

Background

Contents

Background

At the beginning of this thesis work -in -the vulnerability of machine learning models to adversarial examples was not much studied. But over the past three years, we have seen a massive increase in the number of articles published on this topic . In this chapter, we aim to provide an overview of this emerging eld. First, we give some background on image classi cation and learning theory in Section . . We then review in Sections . and . the current state-of-the-art in terms of adversarial attacks and defenses. We present in Section . some recent results studying the adversarial risk minimization through the lens of learning theory and Section . asks whether adversarial examples are unavoidable. Finally, we discuss in Section . how our work contributes to the domain.

. An introduction to learning theory and image classi cation

We rst come back to some of the elements we discussed in the introduction in a more precise manner, and present some prerequisites on classi cation and learning theory.

. . Formalizing the classi cation problem

To begin, let us present the supervised learning setting for classi cation. In this context, the learner e.g. model provider -has access to the following elements.

• An input space X , which is the set of objects the learner wants to classify. Here we consider a setting where X is a set of images with d pixels and values in

[0, 1]; hence X ⊂ [0, 1] d .
Note that in image classi cation, there is often thousand of pixels in the image, which means that X is a high dimensional space. As we will discuss later, this characteristic of the input space plays a key role in our understanding of the adversarial setting.

• An output space Y that denotes the set of possible labels for elements in X . In the image classi cation setting, a label is a succinct description of the image. For simplicity, we characterize Y by a set of K integers Y = {1, . . . , K} := [K].

• A training sample S := {(x  , y 1 ), . . . , (x n , y n )}, which is a set of n elements from X × Y. In the supervised learning setting, we hypothesize that these input-output pairs are drawn i.i.d.from some ground-truth distribution D the learner does not have access to.

Remark . Below, we define probabilities and expectations over the ground-truth distribution D.

Formally, we assume that there exists a σ-algebra A(X × Y) over X × Y and that D is a probability measure over (X × Y, A(X × Y)). Accordingly, the set we evaluate are assumed to be in A(X × Y) and the functions we define are measurable.

With these elements at hand, the goal of the learner is to nd a prediction function c : X → Y a.k.a. classi er -to predict the label of any new input x ∈ X . To measure the quality of this prediction we use the notion of misclassification error, i.e. the probability that c does not predict the correct label for a random sample (x, y) ∼ D. This probability writes ) See https://nicholas.carlini.com/writing/ /all-adversarial-example-papers.html.

P (x,y)∼D [c(x) = y] = E (x,y)∼D [1{c(x) = y}] . ( .
Given any ground-truth probability distribution D, one can easily verify that the optimal prediction function on X × Y writes ) This function is called the Bayes optimal classi er [ , Chap. ]. It is optimal in the sense that no other classi er c : X → Y can have a lower probability of misclassi cation on D.

c opt : x → argmax k∈[K] P y∼D [y = k | x] . ( .
In practice the learner does not have access to the ground-truth distribution D; hence it cannot know the Bayes optimal classi er. Its objective is then to design a learning procedure that nds a prediction function with misclassi cation error as close as possible from c opt . To do so, the usual strategy in machine learning is to de ne a set of functions H ⊂ {h : X → R K } that will mimic the behavior of P y∼D [y | x]. This set is also known as the hypothesis class. For any hypothesis function h ∈ H, by analogy with the Bayes optimal classi er, the prediction function writes ) where

c : x → argmax k∈[K] h k (x) , ( .
h k (x) is the kth element of the vector h(x) = [h 1 (x), . . . , h K (x)] .
To select the best hypothesis out of H, the learner uses a surrogate notion of misclassi cation error called the risk or the generalization error. The key component on which the risk relies is L : R K ×Y → R the loss function. It measures how well h ts the ground-truth distribution on a given sample (x, y) ∼ D. Accordingly, the learner's objective is to nd the hypothesis h * ∈ H that minimizes the expected value of the loss function over D. The risk minimization problem then writes ) If L and H are well chosen, a solution to the above optimization problem gives a classi er with small misclassi cation error. For example, if we use the 0/1 loss ) then Equation ( . ) directly amounts to seek a hypothesis h * in H minimizing the probability of misclassi cation of c * -the classi er associated to h * . The 0/1 loss is mostly used to analyze the problem theoretically. Since the indicator function is not di erentiable everywhere, for optimization purposes, the community often studies surrogate loss functions instead [ ]a.k.a.

inf h∈H R(h) with R(h) := E (x,y)∼D [L(h(x), y)] . ( .
L 0/1 (h(x), y) := 1 argmax k∈[K] h k (x) = y , ( .
classification calibrated losses. Under smoothness and convexity assumptions, we can also prove that Problem ( . ) minimizes the misclassi cation error of c * . Since the loss function is not a problem, the main objective the learner has is to design right class of hypotheses H to search on. On the one hand, if we take a su ciently rich set of hypotheses, it could contain the optimal h opt such that argmax k h opt k (x) = c opt (x). But when the hypothesis class becomes too complex, the learning process is much more di cult to manage -in terms of Note that argmax operator might output a set. In this case c opt (x) can be any element this set. Here we suppose that there is a unique maximum for simplicity.

Background

optimization. More generally, the choice of H is subject to a trade-o between estimation and approximation errors.

An important special case: binary classi cation

To study classi cation from a theoretical standpoint, it is often easier to consider the binary classification settingi.e. K = 2. In this context, it is standard to consider a setup slightly di erent from the above. We still consider X = [0, 1] d , but the output space is now Y = {-1, 1}. Furthermore the hypothesis space only considers real-valued functions h : X → R, and we also adjust the de nition of the classi er c(x) := sign(h(x)).

All other notions adapt accordingly. Our result in terms of learning theory are based on the K-class classi cation setting; hence we keep presenting results in this setting.

. . The estimation/approximation trade-o

Let h ∈ H be any hypothesis function, the excess risk of h is the di erence between R(h) and the optimal risk R(h opt ). It can decompose into two error types, namely the estimation error and the approximation error ) On one hand, the estimation error represents the di erence between the minimal error we could get in H and the actual error we have by using h. If the risk minimization problem on H admits a solution h * , the estimation error measures how well h estimates h * . On the other hand, the approximation error represents the minimal excess risk a hypothesis in H can achieve. It measures the amount of risk that is solely determined by the choice of the hypothesis class H. This error does not depend on the optimization procedure the learner uses. In that sens, it can be seen as a notion of richness of the hypothesis class. When we enlarge H the approximation error will drop.

R(h) -R(h opt ) = R(h) -inf h∈H R(h) estimation + inf h∈H R(h) -R(h opt ) approximation . ( .
Unfortunately, enlarging the hypothesis class will also increase the estimation error.

Figure . illustrates this phenomenon for two nested hypothesis classes H 1 ⊂ H 2 . Let us suppose that the there exist h * 1 , and h * 2 solutions of the risk minimization problems respectively on H 1 and H 2 . If we x h and make the hypothesis set grow from H 1 to H 2 , the estimation error grows but the approximation error diminishes. The eld of statistical learning theory studies this trade-o by designing hypothesis classes that have small approximation error -rich enoughwhile maintaining reasonable estimation error -not too complex. Note that the approximation error is very di cult to evaluate because we do not have access to the ground-truth distribution. Conversely, there is some learning procedure such as the empirical risk minimization for which we can estimate the approximation error.

. . Empirical risk minimization and generalization gap

Empirical risk minimization -ERM -is the most popular learning procedures in machine learning. In a nutshell, the idea is to replace the true risk by the average error over the training sample Sa.k.a. the empirical risk. Then, to nd an approximate solution for the risk minimization problem -Problem ( . ), a learning algorithm maps the n training examples to a hypothesis by solving the following optimization problem ) Intuitively, if we have enough training samples , the empirical risk of a hypothesis R S (h) is a good approximation for its true risk R(h). Then, a hypothesis h S that minimizes the empirical risk also minimizes the risk -or has risk close to the minimum -on H. More formally, we can bound the estimation error of the ERM as follows

inf h∈H R S (h) with R S (h) := 1 n n i=1 L(h(x i ), y i ) . ( .
R(h S ) -R(h * ) = R(h S ) -R S (h S ) + R S (h S ) -R(h * ) ( . ) ≤ R(h S ) -R S (h S ) + R S (h * ) -R(h * ) ( . ) ≤ 2 sup h∈H |R(h) -R S (h)|. ( . )
Thanks to the above inequality, we can control the estimation error if we bound the for all h ∈ H the di erence between the risk and the empirical risk of h. This di erence is called generalization gap and can generally be characterized according to the complexity of H and the size of the training sample n.

Background

In most classical settings, H is an in nite dimensional space, which makes the complexity analysis di cult. To measure the size of the hypothesis set anyway, the learning theory community [ , ] uses di erent complexity notions. Among them, the empirical Rademacher complexity is particularly useful to obtain quality bounds for complex classes such as neural networks, conversely to combinatorial notions such as the VC dimension [ ].

De nition (Rademacher complexity). For any function class F := {(x, y) → R}, given a sample S = {(x  , y 1 ), . . . , (x n , y n )}, the empirical Rademacher complexity is defined as

R S (F) := 1 n E r i sup f ∈F n i=1 r i f (x i , y i ) ,
where r i are i.i.d. drawn from a Rademacher measure -i.e. P(r i = 1) = P(r i = -1) = 1 2 . The empirical Rademacher complexity measures the uniform convergence rate of the empirical risk toward the risk on the class of function F. Thanks to this notion of complexity -under regularity assumption on the loss function -we can bound with high probability the generalization gap of any hypothesis h in a class H.

Theorem ([ , ]

). Let H be a hypothesis class and L : R K × Y → [0, L]. We denote L H := {(x, y) → L(h(x), y) s.t. h ∈ H} the set of functions that compose the loss function with a hypothesis. Then for any δ ∈ (0, 1), with probability at least 1δ, the following holds for any

h ∈ H, R(h) -R S (h) ≤ 2L R S (L H ) + 3L ln(2/δ) 2n .
In particular, when H admits a reasonable Rademacher complexity one can bound the generalization gap of any h ∈ H by O 1 √ n with high probability. This means that, when the training sample is su ciently large, the ERM gives a solution with risk close to the optimal on H. Note, however, that the ERM will only work if the class is already well chosen. In fact, if H is not complex enough, the approximation error can be very large. Conversely if H is too large, the limit of the estimation error becomes loose. But since the approximation error can not be evaluated, how can we select a good H?

. . Structural risk minimization

One way to look at the hypothesis class selection problem is through the structural risk minimization -SRM. Let us start by taking a hypothesis class H with very small -or no -approximation error. H will surely be too rich for the above generalization bounds to make sens. But the rational behind the SRM is to decompose H as the union of an increasing -in the sens of the inclusion -sequence of subclasses H = ∪ m≥1 H m . In theory, the problem then consists of selecting the parameter m * that o ers the best trade-o between estimation and approximation errors. Since this quantities are not know, we keep track of the trade-o with an upper bound on the excess riske.g. by using the generalization gap of the elements in H m . Figure . summarizes the evolution of the two error types according to the growing complexity of the hypothesis class -characterized by m. When the hypothesis class is small it leads to good estimation but high approximation error. Furthermore, enlarging this class may decrease the approximation but also increase the estimation error. m * represents the best trade-o we found by using the upper bound on the excess risk. In general, we write the structural risk minimization as follows ) where Ω is a penalty term on the size of the class H m . This reformulation of the problem allows to revisit the approximation/estimation trade-o using the generalization error and the empirical error. Figure . illustrates the evolution of the generalization error and the empirical rik, with respect to the complexity of the hypothesis class and the penalization term for the SRM. When

inf m≥1 inf h∈Hm R S (h) + Ω(H m ), ( .

Background

the complexity of the model -m -increases, the training error decreases while the penalty term increases. The generalization error follows the same kind of behavior as the upper bound for the excess risk in Figure . . Therefore, the SRM selects the model that minimizes the generalization error. The SRM provides valuable insights on the links between complexity of the model and generalization bounds. Note however that -in general -the SRM is computationally intractable. In fact, in most hypothesis classes, nding the ERM is already hard and the SRM demands to compute the ERM over a large number of di erent hypothesis sets. Nevertheless, there exists several workarounds to perform model selection at a lower cost such as cross-validation, or regularization based algorithms [ , Chap. ]. In this thesis, we focus on analyzing xed hypothesis classes in the context of adversarial classi cation; hence we do not discuss model selection. The hypothesis classes we study are however quite general; hence we believe it is safe to assume they have small approximation error. Studying adversarial classi cation through the lens of the structural risk minimization would be an interesting follow up to our work.

Let us end this section with some more practical considerations by presenting the hypothesis classes we will consider in practice, and some benchmark datasets.

. . Some more practical considerations: hypothesis classes and datasets

Some remarkable hypothesis classes

One of the rst hypothesis classes one should think of when considering a classi cation problem is the class of linear hypotheses. It writes

H := {x → h(x) := θ x s.t. θ ∈ Θ ⊂ M d×K (R)} . ( . )
The machine learning community often uses this hypothesis class on simple datasets, or to build intuitions on the di culty of the task. However, for involved applications such as image classi cation, linear classi ers are too simple to correctly capture the ground-truth distribution. Therefore, one usually uses neural networks instead. A typical class of neural networks is a composition of N -usually non-linear -parametric functions h (i) ) These classes are characterized by two features, namely their architecture and parameter sets.

θ i with respective parameter dimensions d i H := {x → h θ (x) := h (N ) θ N • • • • • h (1) θ (x) s.t. ∀i ∈ [N ], θ i ∈ Θ i ⊂ R d i }. ( .
• The architecture of the model. The architecture is the pre-de ned structure materialized by the set of parametric functions h

(1) θ , . . . , h (N ) θ N -a.k.a.
the layers of the network. Depending on the architecture, a neural network sometimes output a vector in the simplex

∆(K) := {z ∈ R K s.t. K
k=1 z k = 1} -called probit vector-or in R K without further assumptions -called logit vector. In the following, unless stated otherwise we always assume that a neural network gives arbitrary outputs in R K , i.e. logits.

• The parameter sets. The parameters materialized by real valued sets Θ := {Θ 1 , . . . , Θ N } on which the learner optimizes to select a hypothesis.

To select a hypothesis from these classes -be it a linear classi er or a neural network, we still need to solve the ERM. Since the classes are parametrized, it simpli es as follows . ) where Θ is the set of parameters at hand. For this problem, the loss function L we select as well as the optimization procedure we use are called the hyper-parameter of the model. In the remaining, unless stated otherwisee.g. when we look at the 0/1 loss, we always consider the mapping (θ, x, y) → L(h θ (x), y) to be di erentiable with respect to the parameters θ and the input xwhich is a standard assumption. Furthermore, in all our experiments we will use the cross entropy loss de ned as follows

inf θ∈Θ 1 n n i=1 L(h θ (x i ), y i ) , (
L : (z, y) → - K k=1 1{y = k} log exp(z k ) K j=1 exp(z j ) . ( . )
Finally, for a well chosen loss such as the cross-entropy, a simple optimization algorithme.g. a stochastic gradient descent combined with a back-propagation scheme -is su cient to obtain a good approximate solution to the empirical risk minimization.

Reading note.

Here we only give some quick notions to fix the terminology. The main purpose of this manuscript is not to discuss loss functions or optimization processes. We rather design new hypothesis classes on which we can use well known optimization schemes. We refer the interested reader to [ ] or [ , Part II] for a more complete overview on machine learning and deep learning in practice.

Image datasets and evaluation procedure

Provided with a dataset, we divide it into a training and a test samplesa.k.a. train and test sets. We use the training sample S to select c S a candidate classi er -model -and evaluate the performance of c S on unseen input-output pairs from the test sample. Naturally, the quality of the model depends on the error it gets on the test set -not the train set, but the di erence we observe between the quality of the prediction on the test and the training sample can be considered as an empirical evaluation of the generalization error. When we evaluate the performance of a classi er -be it on the train or the test set, we sometimes use the term accuracy instead of error. The accuracy of a classi er is simply the average number of good classi cations it makes. Accordingly, the notion of test-time accuracy -resp. train-time accuracy -denotes the accuracy of the model on the test setresp. the train set. Let us now present the datasets we will most often refer to in this manuscript.

CIFAR-/ CIFAR-

We refer to CIFAR-or CIFAR-datasets [ ] to present numerical intuitions and evaluations. The CIFAR-dataset is one of the most used benchmarks to evaluate vision tasks in machine learning and current state-of-the-art models achieve over 0.99 test-time accuracy on this dataset. It consists of 60000 color images of size 32×32 divided into 10 classes -6000 images per class. There are 50000 training images and 10000 test images. CIFARis just like CIFAR-with 100 classes and only 600 images per class. Accordingly, CIFAR-is harder to classify, and current state-of-the-art models achieve around 0.93 test-time accuracy on this dataset. Figure . presents a sample of images from CIFAR datasets. .

Adversarial attacks, an overview

. . A rst example

Let us rst give a simple example of what an attack looks like. Then, if we compute a perturbation of the image that forces the network make a mistake, we nd the mask in the middle of the gure. To the human eye this mask looks a lot like noise, but it is carefully computed according to the model. If we then multiply this structured perturbation by a small factor and add it to the original pig, we get an image that a human cannot distinguish from the original. That little change is, however, su cient for the network to classify the new imageon the right -as an airliner. This phenomenon is drawing a lot of attention, and many articles have been published on the vulnerability of neural networks to adversarial attacks [ , , , ]. But it is important to note that these vulnerabilities are not restricted to neural networks. Indeed, they apply to essentially any machine learning algorithm [ , , ].

. . Threat models

We de ne the adversaries regarding the information they have on the training set, the model architecture, and the parameters. Accordingly, the two main threat models considered in the literature -see e.g. [ ] -are the following.

• White box adversary. In this scenario, the adversary has the same knowledge as the model provider. This means that it has access to the training samples, the architecture and the parameters of the model. Furthermore, the adversary also knows if the model is defended by any pre-or-post processing.

• Black box adversary. In this scenario, the adversary has no knowledge about the model, and has only limited oracle access to ite.g. limited queries with access only to the hypothesis outputs' or the predicted classes.

In this work, we only consider the more powerful model threati.e. white box adversaries. As pointed out by Carlini et al. [ ], it is not reasonable to assume that the defense algorithm can be held secrets in practice. This concept, called the Kerckho s' principle [ ], is very common in To reproduce this example, the interested reader can follow this tutorial: https://adversarial-ml-tutorial.org/ introduction/.

Background the cryptography community. In a nutshell, it says that the only secret on which a cryptography system should hold is the secret of the encryption key. In this work, we apply the same principle and consider that the only secret is the random state of the algorithmi.e. the pseudo-random number generator is unknown from the adversary. Finally, note that considering the white box setting is fully general, since a black box adversary can only be -by de nition -less e ective than a white box adversary.

. . On the notions of imperceptibility in high dimension

As we mentioned in Chapter , evaluating the imperceptibility of an adversarial example is hard. In practice, we use an p norm with p ∈ [1, +∞] and a threshold α p to evaluate an acceptable variation. Accordingly, the set of allowed perturbations for a standard image x ∈ X is an p ball B p (x, α p ) := {x + τ ∈ X s.t. τ p ≤ α p }. Note that the threshold α p does not only depend on the norm, it also scales according to the dimension of the problem d. Indeed, if the image has a low resolution, the human eye can easily distinguish the pixels from each other; hence it will be much easier to see changes in this context than in a high quality image. Then the following question arises: given some input space X with dimension d and p ∈ [1, +∞], how should we select α p for the attacks to remain undetected?

First, one can give an empirical answer to this question for α ∞ [ , ]i.e. the pixel-wise maximal perturbation that does not change the human perception. Then, to build adversaries with comparable strength, but also because it matches empirical observations , we select α p such that B p (x, α p ) and B ∞ (x, α ∞ ) have equivalent volumes . Typically, on CIFAR datasets, a perturbation τ is considered imperceptible if τ ∞ ≤ 0.031 or τ 2 ≤ 0.8. Even if the p balls have similar volumes -when X is high dimensional, they will only overlap on a negligible region of the space. -on the left -the balls overlap on more than 98 percent of their respective volumes, but when the dimension grows -on the right -most of the mass for the ∞ ball moves toward the corners, leaving only a negligible mass in the intersection. From these di erent behaviors of the balls in high dimensions, we can draw two conclusions.

• Low-dimensional intuition can be misleading. In this work, we will sometimes illustrate our ndings with gures. By essence these gures cannot tell the whole story because they fail to render the high-dimensional nature of the problem.

• Being robust to one adversary does not say much about the others. Let us suppose that we can design a classi er c that is robust to any 2 perturbations with maximal radius α 2 . Then without a ner grain analysis, c can only ensure protection against ∞ perturbations of size α 2 / √ d. Therefore, when X is high dimensional, c does not ensure protection against realistic ∞ adversaries. Generally, guarantees devised for one adversary will not transfer to other ones. Hence we need to clearly state what adversary we study. In this work, we mainly present some general results, but we focus our empirical analysis on 2 and ∞ adversaries.

Reading note. The interested reader can refer to Appendix A for more detailed discussions on the impossibility to transfer defense strategies for one adversary to another.

The threat models we just discussed consider that the adversary is constrained to p -bounded perturbations -which is the most standard threat model in the literature. Note that these models -based on su cient conditions for imperceptibility -are too narrow to match real-world threats [ , ]. Nevertheless, they are mathematically well de ned, which facilitates principled analysis and assessments. Furthermore, while p threats are not su ciently realistic, they are part of any more general -realistic -threat model. Thus, building models robust to p adversaries -which is still an open question -would allow the community to make a step toward a more general notion of robustness. Hence, in this work, we keep studying p -bounded perturbations.

. . How to build an attack?

Recall the K-class adversarial classi cation setting with p ∈ [1, +∞] and α p ≥ 0. Given a hypothesis h ∈ H and an input-output pair (x, y) ∼ D, the adversary aims to nd a solution to the following maximization problem sup τ ∈Bp(αp) L(h(x + τ ), y) .

( . )

Two of the most common ways to do so are ) to try directly solving Problem ( . ) with a projected gradient descent, or ) to solve a Lagrangian relaxation of the problem.

Remark .

Note that -in general -Problem ( . ) might not have realizable solutions. However, finding an approximate solution is most of the time sufficient for c to misclassify -i.e. c(x+τ ) = y. The attacks we present below are sufficiently strong to make the test-time accuracy of any classical deep neural network drop to 0 -on either CIFAR or ImageNet datasets.

Solving directly with projected gradient descent

In one of the rst attack papers, Goodfellow et al. [ ] presented a simple attack scheme based on the idea that h has a linear behavior. This method is called fast gradient method -FGMand relies on the idea that a single gradient step -scaled to have an p norm smaller than α p -is su cient to fool most models. This technique was quickly extended to consider multiple gradient steps [ , ], and is now known as the projected gradient descent schemea.k.a. PGD attack. Given a image x to attack, a threshold α p and a maximal number of steps t max , PGD recursively computes

x t+1 = proj Bp(x,αp) x t + s argmax v s.t. ||v||p≤1 ∇ x t L h x t , y v ( . )
where, ∇ x t denotes the gradient with respect to the entry x t , s is a gradient step size, and proj Bp(x,αp) is the projection operator on B p (x, α p ) . PGD attack has been implemented for several reference norms such as ∞ or 2 and is widely used as a state-of-the-art benchmark to evaluate the e cacy of defense strategies [ , ].

Remark .

During training, we usually evaluate the gradient according to the parameters of the model. But one can use the back-propagation algorithm to compute the gradient on the input as well.

Solving the Lagrangian relaxation

The second procedure searches for the perturbation that has the minimal norm, under the constraint that L(h(x + τ ), y) is bigger than a parameter κ -typically chosen depending on the loss function L.

Remark .

Note that when we solve the Lagrangian relaxation, we have no guarantee that the approximate solution will have an α p bounded norm. To ensure imperceptibility in practice, at the end of the procedure, we force the solution to be in the p ball with a projection operator -as in the

If the projection operator does not exist, any operator that brings x t+1 back into the ball can work.

The authors also use a change of variable to ensure that x + τ ∈ X PGD attack. Nevertheless, for a sufficient number of gradient steps, since the goal is to minimize the norm, the solution will usually already be in the appropriate p ball.

. . Discussion on the attack strategies

The literature on attacks is rich, and this section does not provide an exhaustive list of the methods developed so far. We present only two of the most popular attack frameworks. Given an optimization problem, one can use a number of possible algorithms to get an approximate solution to it, which makes the attack literature ourishing. But, at this stage, most attacks are based on solving either one or the other optimization problems we have just introduced. Thus, we believe that the above methods are su cient to provide a general understanding of how to construct an adversarial example. For a more complete overview of the attack methods one can -for example -refer to [ ].

.

State-of-the-art on defense strategies

At the moment, most the works that aim to provide robust classi ers do not o er any provable protection against adversarial attacks, as the community has demonstrated on many occasions [ , , , ]. However, among the defense strategies, two are susceptible to pass the test of time, namely adversarial training and provable robustness.

. . Adversarial training

Let us suppose for a moment that we can solve the maximization Problem ( . ). This would for example be the case if Danskin Theorem [ ] holds. Then, given a classi er h and a sample (x, y) ∼ D, a well-calibrated stochastic gradient descent would nd

τ * =

. . Provable robustness

The main objective of the literature on provable robustness is to upper-bound the adversary's optimization problem -Problem ( . ). This allows gives worst-case accuracy results, even though h is a complex, non-linear classi er. The two most common methods to obtain provable defenses are ) to analyze a convex relaxation of the problem and ) to use randomized smoothing to build more robust classi ers.

Analyzing a convex relaxation of the problem

Given some x ∈ X , the idea of is to build a convex relaxation of the ball of authorized modi cations B p (x, α p ). Figure . illustrates this simpli cation for an ∞ adversary. Before applying the hypothesis function h -on the left -the ∞ ball is convex and easy to study. After applying h -on the right h(B ∞ (x, α ∞ )) is highly non convex. Therefore, to simplify the analysis, one should study the convex relaxation of h(B ∞ (x, α ∞ )) instead. The resulting problem is a linear program. By dualizing, we obtain an optimization problem similar to back-propagation and we can draw guarantees for the network. However, this technique involves a linear program and is therefore di cult to apply to high-dimensional datasets; hence hardening its application to image classi cation.

Randomized Smoothing

Randomized smoothing defenses are randomization based defenses. The idea of provable defense through randomization was rst introduced in [ ] and re ned in [ , , ]. The rationale behind this idea is very simple: take a hypothesis with probit outputs h : X → ∆(K), and smooth it after training by convolution with a Gaussian distribution N 0, σ 2 I . Then the robust classi er writes

c rob : x → argmax k∈[K] h k * N 0, σ 2 I (x) := argmax k∈[K] E z∼N (0,σ 2 I) [h k (x + z)] . ( . )
If we denote Φ the cumulative density function of the standard Gaussian distribution, we can show that Φ -1 h * N 0,

σ 2 I is 1-Lipschitz [ ].
Therefore, c rob is robust to adversarial examples that are close enough to the unperturbed input x. More precisely, for any point x ∈ X , we can build a radius around x for which no 2 adversary can change the decision of c rob . Furthermore, the radius depends on the di erence between the two biggest probits of ĥ := h * N 0, σ 2 I . Formally, if for any x ∈ X we denote ĥ(x) (1) ≥ ĥ(x) (2) ≥ • • • ≥ ĥ(x) (K) the values of the vector ĥ(x) in decreasing order, the following hold.

Theorem ([ , ]). For any x ∈ X and τ ∈ X the following hold.

If τ 2 ≤ 1 2 Φ -1 ĥ(x) (1) -Φ -1 ĥ(x) (2) , then c rob (x) = c rob (x + τ ).
This theorems says that the more separated the probits of the hypothesis, the more robust the classi er is to adversarial perturbations. Then, the model provider can evaluate its worst-case accuracy under attack according to its standard accuracy and the con dence the network has in it predictions. This technique gives provable defense against adversarial examples on a given dataset. Table . presents the current state-of-the-art results in terms of certi ed accuracyi.e. accuracy that cannot be diminished by an adversary -of randomized smoothing for 2 based adversaries with di erent thresholds on CIFAR-. Note that for a reasonable threshold of 0.75 one gets 0.52 certi ed accuracy. Following the works investigating Gaussian distributions against 2 adversaries,

. . Discussion on the current defense strategies

Over the last few years, there has been signi cant advances on the robustness of machine learning models to adversarial attacks. However, in terms of the quality of defenses, both provable robustness and adversarial training call for improvements. Indeed, the accuracy under attack of these methods is hardly above 0.5 against imperceptible perturbations on CIFAR-. These results are not su cient to consider deploying image recognition systems in real-world applications.

Furthermore, this literature focuses on minimizing the empirical adversarial risk and do not present any generalization guarantee. This question is critical, especially for classi cation under perturbation. Indeed, Madry et al. [ ] ) where

L(h(x i + τ ), y i ) , ( .
B p (α p ) := {τ ∈ X s.t. τ p ≤ α p }.
Unlike other notions such as training set corruptionsa.k.a. poisoning attacks [ , ], the theoretical aspects of adversarial robustness are not widely studied. For now, empirical observations tend to show that ) adversarial examples on state-of-the-art models are hard to mitigate and ) robust training methods give poor generalization performances. Some recent works study the problem through the lens of learning theory either to understand the links between robustness and accuracy or to provide bounds on the generalization gap of current learning procedures in the adversarial setting.

. . Is robustness antagonist with accuracy?

A rst line of research [ , , , ] suggests that designing robust models might be at odds with standard accuracy. These works study di erent experimental and theoretical toy settings. Among them, let us start with the toy binary classi cation task from [ ].

Toy Example. Given any (x, y) ∼ D, q ∈ [0, 1) and η > 0 , the following holds.

. y is uniformly distributed at random on {-1, 1}.

. Given y, x 1 takes value y with probability q and -y otherwise.

. All other elements x 2 , ..., x d of the vector x are drawn i.i.d. from a Gaussian N (ηy, 1).

According to the above distribution, when X is high dimensional, one can build a simple linear classi er h(x) = 1 d-1 d i=2 x i that will have arbitrary high test-time accuracy. Indeed -thanks to the central limit theorem -when d → ∞ we get h(x) = 1 d-1 d i=2 x i → ηy, meaning that sign(h(x)) = y with arbitrarily high probability. Nevertheless, an ∞ adversary that can shift all features by at most α ∞ = 2η will be able to make the test-time accuracy of h drop to 0. More generally, on this toy example, Tsipras et al. [ ] presented the following result.

Theorem ([ ])

. Any classifier that attains at least 1r standard test-time accuracy on D has robust test-time accuracy at most q 1-q r against an ∞ -bounded adversary with α ∞ ≥ 2η.

This result proves rst-hand that robustness can be at odds with precision. But it is not general enough to draw conclusions -since it is based on a very simple toy distribution. A subsequent work by Zhang et al. [ ] observed -for the binary classi cation setting with 0/1 loss -that the adversarial risk of any hypothesis h straightforwardly decomposes as follows,

R adv (h; α p ) = R(h) + E (x,y)∼D [1{c(x) = y and ∃τ ∈ B p (α p ) s.t. c(x + τ ) = y}],
( . ) where c(x) := sign(h(x)). Looking at Equation ( . ), we realize that minimizing the adversarial risk is not enough to ensure good standard accuracy -as one could only optimize over the second term. This indicates that adversarial risk minimization -Problem ( . ) -is harder than standard risk minimization -Problem ( . ). Note, however, that Equation ( . ) does not highlight a fundamental trade-o between robustness and accuracy. Finding such a relation in the general case remains an open question.

. . Studying adversarial generalization

To further compare the di culty of the two problems, a recent line of research began to explore the notion of the adversarial generalization gap. In this line, Schmidt et al. [ ] presented rst intuitions by studying a simpli ed binary classi cation framework where D is a mixture of spherical Gaussian distributions. In this framework, the authors show that we only need O(1) training samples to have a small generalization error. But against an ∞ adversary, we need O( √ d) training samples instead. In the discussion of their work, the authors present the problem of obtaining similar results without making assumptions about the distribution as an open problem.

This issue was rst tackled by Cullina et al. [ ] by using the VC-dimension. Their analysis shows that for linear classi ers, the VC dimension of the hypothesis class does not change under attack. This work indicates that -with respect to the VC dimension -classi cation under perturbation is not more di cult than standard classi cation which does not correspond to the empirical observations and initial intuitions provided earlier [ , ]. However, as previously mentioned, the Rademacher complexity generally allows for tighter generalization bounds than the VC dimension [ ]. Accordingly, further works studied the same problem, using Rademacher complexity and presented the following results relating the adversarial generalization error of linear classi ers with the dimension of the problem .

These works also investigate neural networks with one hidden layer -we refer the interested reader to the original papers for more details.

[ ] and [ ] only present bounds for ∞ adversaries. [ ] extended the results to any p attack.

Theorem ([ ])

. Let H q := x → θ x s.t. θ q ≤ M and let us suppose that L is L-Lipschitz.

Then with probability at least 1δ, the following holds for any h ∈ H q ,

R adv (h; α p ) ≤ R adv S (h; α p ) + 2L R S (H q ) + α p M √ n max d 1-1 p -1 q , 1 + 3 ln(2/δ) 2n .
Note that the main di erence between this result and the one we presented in the standard setting -Theorem -is the additive factor ) Therefore, by analyzing the problem using Rademacher complexity, we can show that the adversarial generalization does depend on the dimension of the problem. Hence, in terms of sample complexity, adversarial classi cation is more di cult than standard classi cation. However, when facing an p adversary, one can always select a class of linear classi ers for which the dimension term disappears. Indeed, if we select q to be the Holder conjugate of pi.e. 1 p + 1 q = 1 -the additive term becomes O 1 √ n . Therefore, we can build strong intuitions for an adversary, but the generalization bounds are not transferable to another p adversary.

α p M √ n max d 1-1 p -1 q , 1 = O d 1-1 p -1 q √ n . ( .

Reading note. At first a glance, the difficulty of adversarial generalization seems to contradict previous conclusions on the link between robustness and generalization [ ]. But as we will see in

Chapter , these results are based on very specific assumptions that may not hold in high dimensions.

. . Discussion on the learning theory literature

Some compelling insights were presented on whether robustness standard accuracy are in conict. However, in more general con gurations, the question remains open. Moreover, from the di erent results on the adversarial generalization gap, we can draw two -somewhat contradictory -conclusions. First, learning under perturbation is indeed much more di cult than standard learning and the di culty increases with the dimension of the problem. Second, for an p adversary -xed p -robustness might be achievable.

Going further, it should be noted that the generalization gap measures only the di erence between empirical and theoretical risk. In practice, the empirical adversarial risk is never really estimated -since we cannot compute the exact solution to the inner maximization problem. The following question therefore remains open: even if we can set up a learning procedure with a small generalization gap, will the adversarial risk be low? To answer this question, we need to study the adversarial risk minimization problem -Problem ( . ). Bubeck et al. [ ] who argued that the problem of adversarial classification is not the sample size, but the computational hardness. Thus, even with a reasonable sample size for both problems, we can present a set of learning problems where standard non-robust learning can be performed efficiently, but is difficult to compute in an adversarial setting.

Remark . Another line of research within the learning community studies the problem from a computational viewpoint. This was recently addressed by

. Is classi cation under perturbation feasible?

From preliminary intuitions to advanced mathematical analyses, some works are studying the fundamental properties of classi cation under perturbation -Problem ( . ). Speci cally, the community wonders why adversarial examples exist and whether we can mitigate them. These questions are far from settled, but most works indicate that sensitivity to adversarial perturbations is inevitable. Besides, a very recent line of research began to investigate the worst case adversarial risk of any hypothesis class; thus assessing whether Problem ( . ) is even worth solving.

. . Initial hypotheses on the existence of adversarial examples

When Szegedy et al. [ ] rst noticed the vulnerability of deep neural networks to small perturbations, they hypothesized that this phenomenon was a consequence of the model's overtting. The community uses complex and powerful neural networks that can sometimes be overparameterized for the task. Thus, even with enough training samples, the network learns structures that are too complicated to describe only the dataset distribution. As a result, it makes random mistakes in low probability regions of the image space that an adversary can exploit.

Figure . -on the left -illustrates this hypothesis on a training set of three blue crosses and three red circles. It is always possible to build a complex classi er that easily adapts to the training points. But since it has much more parameters than it needs, it also creates small classi cation areas in low probability regions -somewhat randomly. One can then easily see that a small shift of a point in a well-chosen direction causes an error in the classi er. tting than over-tting. Speci cally, the authors argued that deep neural networks -despite the use of non-linear transformations -have a linear behavior that make them vulnerable to attacks in high-dimensional spaces.

To better understand how under-tting can lead to a vulnerability, let us go back to Figure .

-on the right. If we t a linear model to the previous training set, we get a hyperplane lying between the two sets of points. However, this hyperplane does not account for the distribution of the dataset. The circles could be arranged in a C-shape, so moving a point along this shape causes the classi er to make an error. Some follow-up work kept linking the vulnerability of the models to the shape of their decision boundary. For example, Moosavi et al. [ ] related the vulnerability of a classi er to the curvature of its decision boundary. As such, the shape of the decision boundary is not su cient to explain the whole phenomenon, but it seems to play an important role as some very e cient attack methods extensively use this hypothesis [ , , ].

. . Are adversarial examples inevitable?

To further investigate whether adversarial examples are inevitable, subsequent works [ , ] has focused their analysis on the task -rather than the classi er itself. Consider for example K-class classi cation on the unit spherei.e.

X = S n-1 := {x ∈ R d s.t. x 2 = 1}. In this context, Shafahi et al. [ ] used isoperimetric inequalities [ ] to argue that adversarial examples are in- evitable.
The authors show that -under assumptions on the concentration of the ground-truth distribution -for any classi er on the unit sphere, there is at least one class k * ∈ Y for which adversarial examples exist with high probability.

Theorem ([ ])

. Let ν defines the probability distribution for y, µ k is the conditional distribution for x knowing y = k and g k its probability density function. Let us also consider c a classifier over the unit sphere X and α p a perception threshold for an p adversary. Then there exists k * ∈ Y such that for any x ∼ µ k * , with probability at least

1 -V k * π 8 1/2 exp - d -1 2 (α p ) 2 , there exist τ ∈ B p (x, α p ) such that c(x + τ ) = k * . Where V k * := sup x∈X g k * (x) × s n-1 .
This result means that when the conditional distribution µ k * has limited concentration, no classi er can be robust to p adversaries targeting samples from class k * . Gilmer et al. [ ] presented observations of the same nature by studying a toy dataset consisting of two concentric spheres. Their main result relates the errors in the standard and the adversarial setting by saying that even a small standard error on their toy dataset translates to a large adversarial error. These results were later presented in a more general way by Dohmatob [ ], but for simplicity we discussed here the initial contributions. Shafahi et al. [ ] tried to extend their conclusions to image classificationi.e. when X = [0, 1] d and d is large. However, in this context, the probability is high only when the The initial result in [ ] uses the geodesic distance. Hence the result holds at least for 2 and ∞ adversaries.

Remark . Note that

perturbation threshold α p is large -hence losing the imperceptibility of the attack. Dohmatob [ ] has conducted complementary experiments on -small-scale -image datasets with similar results; the number of adversarial examples is not prohibitive as long as α p is small. Therefore, the above results still need to be verified on large-scale image classification.

This literature suggests that adversarial examples are inevitable, which means that Problem ( . ) can have a large value. In the following section, we present some works that attempt to assess whether solving Problem ( . ) is even worth trying by estimating this value.

. . Finding worst case lower bounds on the adversarial risk minimization

Two recent works [ , ] studied adversarial risk minimization by using arguments from optimal transport [ ]. They show how to characterize the adversarial risk for binary classi cation by an optimal transport cost between the conditional probability distributions of the two classes µ 1 and µ 1 . Let us consider the adversary's problem from a distributional point of view. Instead of attacking every point, it directly moves the distributions µ 1 and µ 1 to maximize the risk with respect to D. In this context, we can evaluate the worst-case -non-normalized -accuracy under attack of any classi er by the minimal number of points that are not susceptible to be switched from one conditional distribution to the other ) where Π(µ 1 , µ 1 ) is the set of all joint probability measures on X × X with marginals µ 1 and µ 1 . Finally, we can de ne the best-case adversarial risk according to the non-normalized worstcase accuracy under attack D αp (µ 1 , µ 1 ) and the classes' distribution ν.

D αp (µ 1 , µ 1 ) = inf π∈Π(µ 1 ,µ 1 ) E (x,x )∼π 1{ x -x p > α p } , ( .

Theorem ([ , ]

). Let ν consider the probability distribution for y with ν(1) = ν( 1) = 1/2. Then the following holds,

inf h∈H R adv (h; α p ) = 1 2 1 -D αp (µ 1 , µ 1 ) .
This result indicates that if the conditional distributions are close enough -according to the above notion of distance -then the adversarial risk will be high, regardless of the classi er. Note, however, that this is already the case without adversaries. Indeed, the risk of the Bayes optimal classi er h opta.k.a. the Bayes optimal risk -is as follows

R(h opt ) = 1 2 (1 -D T V (µ 1 , µ 1 )), ( . )
where D T V (µ 1 , µ 1 ) is the total variation distance between the conditional distributions. Hence remains the question: how fast does D αp (µ 1 , µ 1 ) grow -compared to D T V (µ 1 , µ 1 ) -according to the distribution? To answer this, Pydi et al. [ ] evaluated their bounds on -a smoothed version -of CIFAR-dataset. Their preliminary results indicate that best-case adversarial risk -for α 2 ≤ 0.8 -can be 0.05 bigger than the Bayes optimal risk, which is not prohibitive but still represents an important loss of accuracy. For the gap to be more important -as we already Background pointed out in the previous section -we should select a larger α p ; hence the imperceptibility of the attack becomes questionable.

Remark .

Given an n points dataset, to build the smooth version of it, the authors use a mixture of n Gaussian distributions, where each mean is placed on a data point. This smoothness assumption seems reasonable, since machine learning practitioners often use Gaussian data augmentation to improve the performances of their models [ , ].

. . Discussion on the feasibility of classi cation under perturbation

The results we just presented seem to show that adversarial examples are -to some extent -inevitable and that accuracy under attack of a classi er will always be signi cantly smaller than its standard counterpart. However, these results -even if the authors sometimes claim the opposite -do not prove that no satisfactory solution can be found to the adversarial risk minimization -Problem ( . ). For example, on CIFAR-, diminishing the current state-of-the-art by 0.05 still gives a good classi er with over 0.9 test-time accuracy . Furthermore, as recently pointed out by Dohmatob [ ], the strength of these impossibility results might mainly come from the fact that the adversary we consider is unrealistically strong. Thus, rethinking the constraints for the adversary could question the ongoing consensus on whether we can build models that are both robust and accurate.

.

Our positioning with regard to prior art

In this thesis, we aim to bring a new understanding on adversarial examples and contribute to the development of new technical tools. Our main accomplishments are the followings.

Bringing a new point of view on the adversarial classi cation problem

We begin by revisiting the problem of adversarial risk minimization by regularizing the adversary objective function. We study this new problem through the lens of game theory by casting it as an in nite zero sum game. Our conclusions highlight a very interesting property of the adversarial classi cation problem, which is its instabilityi.e. the nature of the game between the adversary and the classi er changes completely when we add a small regularization term. This leads us to question current theses on adversarial classi cation and to ask whether existing conclusions would still hold if we limit the adversary's strength. The game theoretical point of view we develop also leads us to study randomized classi ersi.e. classi ers that produce random variables.

In particular, we show that they have principled advantages over deterministic classi ers in terms of robustness to adversarial perturbations. Some works have tackled the problem of adversarial examples as a two player game before [ , ], but they consider restricted versions of the gamee.g. when the players only have a nite set of possible strategies. We study a more general setting which allows us to build strong insights on the fundamental nature of the game between the classi er and the adversary.

Still, it remains to nd this optimal classi er, which can be hard as discussed in Section .

Studying adversarial defense from a probabilistic point of view

Based on the new insights we develop on adversarial classi cation, we present a theoretical analysis of randomized classi ers. To do so, we rst de ne a new notion of robustness for these classi ers using probability metrics. Then, we show that under robustness assumptions, we can limit the di erence between the standard risk and the adversarial risk of a randomized classi er. This result is important for the community because it shows that a well-chosen class of hypotheses can give both reasonable robustness and accuracy -thus mitigating the previous results on deterministic classi ers. We then devise bounds on the standard generalization gap of this new hypothesis class. This result encompasses existing works on the link between robustness and accuracy for deterministic classi ers. Finally we analyze the stability of the classi er's mode allowing us to present a probabilistic point of view on randomized smoothing techniques. Our point of view on randomization as a defense strategy could pave the way to further investigating randomized smoothing from a theoretical perspective.

Building robust classi ers

Finally, we link our de nition of robustness to the notion of di erential privacy. Thanks to this connection, we bring to the community a new set of technical tools. As a consequence, we design new noise injection schemes to build robust classes of randomized classi ers. These schemes prove that the theoretical analysis we have previously built is applicable to state-of-the-art image classi cation models.

Injecting noise into algorithms to improve train time robustness has been used for ages in detection and signal processing tasks [ , , , ]. It has also been extensively studied in several machine learning and optimization eldse.g. robust optimization [ ] and data augmentation techniques [ ]. Concurrently to our work, noise injection techniques have been adopted by the adversarial defense community [ , ]. In particular, Lecuyer et al. [ ] rst developed randomized smoothing, by using theoretical results from di erential privacy. Our work belongs to the same line of research, but the nature of our results is di erent. While randomized smoothing focuses on the construction of certi ed defenses, depending on the dataset and the classi er used, we study randomized mechanisms from the perspective of information theory and learning theory. Our analysis presents the fundamental properties of randomized defenses, including -but not limited to -randomized smoothing.

A game theoretical point of view on adversarial attacks

Q :

Is there some hypothesis class H for which the adversarial risk minimization problem has a solution h * with small adversarial risk?

In this chapter, we aim to answer Q by adopting a game-theoretical point of view. We present in Section . the adversarial attack and defense problem as an in nite zero-sum game. Then we discuss how unrealistic threat models might impact the analysis of this game and present a simple additional constraint to mitigate the overpower of the adversary. We demonstrate in Section . that -as long as this small constraint holds -no Pure Nash equilibrium exists in our game. This shows how current impossibility results may provide questionable ndings, but this is not su cient to rehabilitate deterministic hypotheses. Furthermore, we show in Section . that, in this setting, any deterministic hypothesis can be outperformed by a randomized one. This gives arguments for using randomization, and leads us to a simple method for building randomized classi ers that are robust to state-or-the-art adversarial attacks. In Section . , we validate our theoretical analysis with empirical results. Finally, we present some additional results, and provide concluding remarks respectively in Sections . , and . .

. Casting the problem as a zero sum game

Notations. For any set Z with σ-algebra A(Z), if there is no ambiguity on the considered σalgebra, we denote P(Z) the set of all probability measures over (Z, A(Z)). We also denote F Z the set of all measurable functions from (Z, A(Z)) to (Z, A(Z)). For µ ∈ P(Z) and ψ ∈ F Z , the push-forward measure of µ by ψ is the measure ψ#µ such that ψ#µ(B) = µ(ψ 1 (B)) for any B ∈ A(Z). Moreover, for any B ⊂ X we denote B c the complement of B in X . Finally, when the probability measure of reference is clear we denote essup the essential supremum, i.e. the supremum over the non-null sets for this measure.

. . Initial problem statement

As this chapter aims at building new intuitions on adversarial classi cation, we restrict our analysis to the binary classi cation setting with 0/1 loss. In the next chapters, we will come back to the more general

K-class classi cation. Let us set X ⊂ [0, 1] d , Y = { 1, 1} and H := C(X , R) -where C(X , R)
is the set of functions that are almost everywhere continuous from X to R. Then, given a distribution D with full support on X × Y, the model provider is looking for a hypothesis h ∈ H minimizing the risk of h with respect to D, ) where ν ∈ P(Y) is the probability distribution of y, and for any y ∈ Y, µ y ∈ P(X ) is the conditional law of x|y. Given a hypothesis h ∈ H and a data sample (x, y) ∼ D, the adversary seeks a perturbation τ ∈ X such that τ p ≤ α p and L 0/1 (h(x + τ ), y) = 1.

R(h) := E (x,y)∼D L 0/1 (h(x), y) = E y∼ν E x∼µy L 0/1 (h(x), y) , ( .
From a distributional point of view, this amounts to constructing -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 nd ψ = (ψ 1 , ψ 1 ) ∈ (F X |αp ) 2 that maximizes the adversarial score

Score adv (h, ψ) := E y∼ν E x∼ψy#µy L 0/1 (h(x), y) . ( . )
Finally, for the attack to remain undetected, we de ne F X |αp as the set of measurable functions that imperceptibly modi es a distribution on X , ) Here we use almost everywhere with respect to the conditional distributions µ1 and µ 1 de ned below.

F X |αp := f ∈ F X s.t. essup x∈X f (x) -x p ≤ α p . ( .
. Casting the problem as a zero sum game Within this distributional setting, the adversarial example problem is a two-player zero-sum game, where the defender -model provider -tries to nd the best possible hypothesis h, while the adversary is manipulating the dataset distribution. The defender problem then writes as follows. ) This means that the defender tries to design the hypothesis with the best performance under attack, whereas the adversary will each time design the optimal attack on this hypothesis.

inf h∈H sup ψ∈(F X |αp ) 2 Score adv (h, ψ). ( .

. . Adversarial attack and defense, a two-player zero-sum game

In game theory, the choice of a hypothesis h -resp. an attack ψ -for the defender -resp. the adversary -is called a strategy. Note that the sup-inf and inf-sup problems do not necessarily coincide. In this work, we mainly focus on the defender's point of view which corresponds to the inf-sup problem. We will be interested in understanding how the players behave in this gamei.e. the best responses they give to a strategy and whether some equilibria may arise. This motivates the following de nitions.

De nition (Best Response).

Let h ∈ H, and ψ ∈ F X |αp 2 .

• A best response from the defender to ψ is a hypothesis h * ∈ H such that

Score adv (h * , ψ) = min h∈H Score adv (h, ψ).
• Similarly, a best response from the adversary to h is an attack

ψ * ∈ F X |αp 2 such that Score adv (h, ψ * ) = max ψ∈(F X |αp ) 2 Score adv (h, ψ).

Remark . Note that the score achieved by a best response from the adversary to h is the adversarial risk of h Score

adv (h, ψ * ) = R adv (h; α p ).
In the remaining, we denote BR(h) the set of all best responses of the adversary to a hypothesis h. Similarly BR(ψ) denotes the set of best responses of the defender to an attack ψ.

De nition (Pure Nash Equilibrium). In the zero-sum game from Equation ( . )

, a Pure Nash Equilibrium is a couple (h, ψ) ∈ H × F X |αp 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 hypothesis, and that the hypothesis 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 discuss extensions to the randomized regime in Section . .

. . Trivial solution and regularized adversary

Our current de nition of the problem implies that the adversary has perfect information on the dataset distribution and the hypothesis. It also has unlimited computational power and no constraint on the attack except on the size of the perturbations. Thus, it is similar to the adversaries currently studied in the literature -see Section . . However the community starts wondering if this adversary is not too strong to be realistic [ , ]. Going back to the example of the autonomous car -Chapter -this would mean that the adversary can modify every tra c sign that the camera may receive during any trip, which is highly unrealistic. The adversary has no downside to attacking, even when the attack is unnecessarye.g. if the attack cannot work or if the point is already misclassi ed. illustrates this phenomenon for the uni-dimensional setting with Gaussian distributions. The adversary moves every point toward the decision boundary -each time saturating the norm constraint -and the defender cannot do much to mitigate the damages. In this case the best classi er remains unchanged, although both curves moved; hence a trivial equilibrium. Furthermore, thanks to Theorem , we can evaluate the value of this equilibrium, which can be high -depending on the conditional distributions.

In the remainder of this work, we show that this equilibrium does not hold when we add a small constraint on the adversary's strengthi.e. when it is not perfectly indi erent to producing unnecessary perturbations. To formalize the constraint on the adversary, we introduce a penalty term in the initial formulation of the game,

inf h∈H sup ψ∈(F X |αp ) 2 Score adv Ω (h, ψ) := Score adv (h, ψ) -λ Ω(ψ). ( .
)
The penalty function Ω represents the limitations on the adversary's budget -be it because of computational resources or to avoid being detected -and λ ∈ (0, 1) is some regularization weight.

The decision boundary is the set{x

s.t. h(x) = 0}
From a computer-security point of view, the rst limitation that comes to mind is to limit the number of queries the adversary can send. In our distributional setting, this boils down to penalizing the mass of points that the function ψ moves. Hence we de ne the penalty as follows ) Note that this limitation is also very relevant for the example of the self-driving car example. It forces the adversary to select a few signs that it will attack. In the remaining, we study this regularized game and denote BR Ω (h) the set of all best responses of the adversary to a hypothesis h, under penalty Ω. Since the penalty does not impact the defender's optimization problem, the notation remains unchanged. All above de nitions adapt accordingly.

Ω(ψ) := E y∼ν E x∼µy [1{x = ψ y (x)}] . ( .

. . Characterizing the best responses

Let us now study how the game behaves when the adversary has been penalized. We show that in this context, no Pure Nash Equilibrium exists. To do so, we characterize the best responses for each player, and show that they can never satisfy De nition . We rst present the best responses of the penalized adversary.

Lemma .

Let h ∈ H and ψ ∈ BR Ω (h). Then the following assertion holds:

ψ 1 (x) ∈ (P h ) c if x ∈ P h (α p ) ψ 1 (x) = x otherwise.
ψ 1 is characterized symmetrically.

Proof. Let us rst simplify the worst-case adversarial score for h. From the de nition of adversarial score we have:

sup ψ∈(F X |αp ) 2 Score adv Ω (h, ψ) = sup ψ∈(F X |αp ) 2 E y∼ν E x∼µy [1{sign(h(ψ y (x))) = y} -λ 1{x = ψ y (x)}]
We could build a lot of other di erent penalties. The results would still hold. See e.g. Section . for a penalty on the norm of the perturbation.

= E y∼ν sup

ψy∈F X |αp E x∼µy [1{h(ψ y (x))y ≤ 0} -λ 1{x = ψ y (x)}] .
Finding ψ 1 and ψ 1 are two independent optimization problems, hence we focus on characterizing ψ 1i.e. we set y = 1.

sup

ψ 1 ∈F X |αp E x∼µ 1 [1{h(ψ 1 (x)) ≤ 0} -λ 1{x = ψ y (x)}] = E x∼µ 1 essup z∈Bp(x,αp) 1{h(z) ≤ 0} -λ 1{x = z} = X essup z∈Bp(x,αp) 1{h(z) ≤ 0} -λ 1{x = z} dµ 1 (x).
Let us now consider (H j ) j∈J a partition of X , we can write.

sup

ψ 1 ∈F X |αp E x∼µ 1 [1{h(ψ 1 (x)) ≤ 0} -λ 1{x = ψ y (x)}] = j∈J H j essup z∈Bp(x,αp) 1{h(z) ≤ 0} -λ 1{x = z} dµ 1 (x).
In particular, we can take

H 0 = P c h , H 1 = P h \ P h (α p ), and
H 2 = P h (α p ).
Then we can study the three sets independently.

. For any x ∈ H 0 = P c h , taking z = x we get 1{h(z) ≤ 0}λ 1{x = z} = 1. Since for any z ∈ X we have 1{h(z) ≤ 0}λ 1{x = z} ≤ 1, this strategy is optimal. Furthermore, for any other optimal strategy z , we would have 1{x = z} = 0, hence z = x.

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

. Finally, for any x ∈ H 2 = P h (α p ), we have that B p (x, α p ) ∩ P c h = ∅, and for any z in this intersection, one has h(z) ≤ 0 and z = x. Hence

essup z∈Bp(x,αp) 1{h(z) ≤ 0} -λ 1{z = x} = max(1 -λ, 0). Since λ ∈ (0, 1) one has 1{h(z) ≤ 0} -λ 1{z = x} = 1 -λ for any z ∈ B p (x, α p ) ∩ P c h . Then any function that outputs ψ 1 (x) ∈ B p (x, α p ) ∩ P c h is optimal on H 2 . Since H 0 ∪ H 1 ∪ H 2 = X , Lemma holds.
The proof for y = -1 is symmetrical. Furthermore, the value for the optimal score writes

sup ψ∈(F X |αp ) 2 Score adv Ω (h, ψ) = E y∼ν    j∈J H j essup z∈Bp(x,αp) 1{h(z)y ≤ 0} -λ 1{x = z} dµ y (x)    = y=±1 ν(y) j∈J H j essup z∈Bp(x,αp) 1{h(z)y ≤ 0} -λ 1{x = z} dµ y (x) .
Since the value is 0 on ) where Equation ( . )

P h \ P h (α p ) for ψ 1 -resp. on N h \ N h (α p ) for ψ 1 -one gets = R(h) + (1 -λ) ν(1)µ 1 (P h (α p )) + ν( 1)µ 1 (N h (α p )) , ( .
holds since R(h) = ν(1)µ 1 (P c h ) + ν( 1)µ 1 (N c h ).
This provides an interesting decomposition of the adversarial risk into the risk without attack and the loss the adversary produces by attacking that recall the decomposition in Chapter .

Note that an optimal attack will only change points that are close enough to the decision boundary. This means that, when the adversary cannot change the hypothesis' decision on a point, it will not attack it. Let us now study what happens for the defender. At a rst glance, one would suspect that the best response for the defender ought to be the Bayes optimal classi er for the transported distributions. However, it is only well de ned if the conditional distributions admit a probability density function. This might not always hold here for the transported distribution. Nevertheless, we present a property, shared by the Bayes optimal classi er when de ned, that always holds for the defender's best response.

Lemma . Let us consider ψ ∈ F X |αp

2

. If we take h ∈ BR(ψ), then for any measurable

B ⊂ P h one has ψ 1 #µ 1 (B) × ν(1) ≥ ψ 1 #µ 1 (B) × ν(1). A similar result holds for N h .
Proof. We reason ad absurdum with the following assumption:

There exists a measurable set C ⊂ P h such that ν( 1)ψ 1 #µ 1 (C) > ν(1)ψ 1 #µ 1 (C).
Let us construct h as follows:

h(x) = h(x) if x / ∈ C -1 otherwise.
Since h and h are identical outside C, the di erence between the adversarial scores of h and h writes as follows:

Score adv Ω (h, ψ) -Score adv Ω ( h, ψ) = E y∼ν   C 1{h(x)y ≤ 0} -1 h(x)y ≤ 0 dψ y #µ y (x)   = y±1 ν(y)   C 1{h(x)y ≤ 0} -1 h(x)y ≤ 0 dψ y #µ y (x)   .
Since -by construction -for any x ∈ C we have h(x) < 0 and h(x) > 0, we can write

Score adv Ω (h, ψ) -Score adv Ω ( h, ψ) = ν(-1)ψ 1 #µ 1 (C) -ν(1)ψ 1 #µ 1 (C)
Since we assumed ν(-1)ψ 1 #µ 1 (C) > ν(1)ψ 1 #µ 1 (C) the di erence between the adversarial scores of h and h is strictly positive. This means that h gives strictly better adversarial score than the best response h, leading to a contradiction. Hence Lemma holds. The proof for N h is symmetrical.

In particular, when ψ 1 #µ 1 and ψ 1 #µ 1 admit probability density functions, Lemma means that h is the Bayes optimal classi er for the distribution characterized by ν, ψ 1 #µ 1 and ψ 1 #µ 1 .

. . No Pure Nash Equilibrium in the game

We can now state our rst main result relating the absence of equilibrium in the regularized game.

Theorem (Non-existence of a pure Nash equilibrium). In the zero-sum game from Equation ( . ), there is no Pure Nash Equilibrium.

Proof. Let h be a classi er and ψ ∈ BR Ω (h) an optimal attack against h. We will show that h / ∈ BR(ψ)i.e. that h does not satisfy the condition from Lemma . It su ces for Theorem to hold since it implies that there is no (h, ψ) ∈ H × F X |αp 2 such that h ∈ BR(ψ) and ψ ∈ BR Ω (h).

According to Lemma , we have ψ 1 #µ 1 (P h (α p )) = 0i.e. P h (α p ) is of null measure for the transported distribution conditioned by y = 1. Since ψ 1 is the identity on P h (α p ), and since µ 1 is of full support on X a we have

ψ 1 #µ 1 (P h (α p )) = µ 1 (P h (α p )) > 0.
( . )

Hence we get the following

ψ 1 #µ 1 (P h (α p )) > ψ 1 #µ 1 (P h (α p )). ( . )
Since the right side of the inequality is null, for any ν(1) and ν( 1) we get

ψ 1 #µ 1 (P h (α p ))ν( 1) > ψ 1 #µ 1 (P h (α p ))ν(1). ( .
)
This inequality is incompatible with the characterization of the best response for the defender of Lemma . Hence h / ∈ BR(ψ).

a Note that the full support hypothesis is much stronger than what we actually need. Fundamentally, we only need the null sets for measures µ1 and µ 1 to be su ciently far one from the other. illustrates Theorem with two uni-dimensional Gaussian distributions. We see that -one the right -µ 1 is set to 0 in P h (α p ), and this mass is transferred into N h (α p ). The symmetric holds for µ 1 . After attack, we have µ 1 (P h (α p )) = 0. Hence, any small amount of mass for µ 1 in P h (α p ) is now su cient to make it dominant; hence the zone will now be classi ed -1 by the Bayes optimal classi er. This result has several deep consequences. Among them, we focus on the following two.

Consequence : There might be room for robustness after all

The above result shows the fundamental di erence between regularized and unregularized games. While in the unregularized setting there may exist a pure -trivial -Nash Equilibrium, our analysis shows that such an equilibrium cannot exist as soon as we add an in nitesimally small regularization. Hence, our result highlights a very interesting property of the unregularized problem, which is its instability. This leads us to the following conclusions.

• We should reconsider the works on the limits of classi cation under perturbation and verify whether these results still hold -or are diminished -when we add a set of realistic constraints to the adversary, be it the one we just described or more sophisticated ones.

• There might be room for robustness after all. Even if for now, the defense community seems to be losing the race, the game is not over yet. If we design more realistic adversaries, we may be able to understand better the threat and design more robust models.

Consequence : No free lunch for transferable examples

To understand this statement, rst note that thanks to the weak duality, the following inequality always holds

sup ψ∈(F X |αp ) 2 inf h∈H Score adv Ω (h, ψ) ≤ inf h∈H sup ψ∈(F X |αp ) 2 Score adv Ω (h, ψ).
On the left side problem -sup-inf -the adversary looks for the best strategy ψ against any unknown hypothesis. This is closely related to the notion of transferablility of the attacks -investigated e.g. in [ , ] -which refers to attacks successful against a wide range of hypotheses.

On the right side problem -inf-sup -the defender tries to nd the best hypothesis under any possible attack, whereas the adversary plays in second and speci cally attacks this hypothesis. As a consequence of Theorem , the inequality is always strict:

sup ψ∈(F X |αp ) 2 inf h∈H Score adv Ω (h, ψ) < inf h∈H sup ψ∈(F X |αp ) 2 Score adv Ω (h, ψ).
This means that the problems are not equivalent. In particular, an attack designed to succeed against any hypothesisi.e. a transferable attack -will not be as good as an attack tailored for a given hypothesis. The adversary must therefore make a trade-o between e ectiveness and transferability of the attack. This sends a second encouraging message to the defense community.

. Randomization might be the clue

. . Adaptation of the problem statement

We just found that adversarial defense might be possible. However, both the current literature on adversarial attacks and the instability of the game in the deterministic setting pushes us to widen the class of strategies we consider. A natural extension of the game would be to allow randomization for both players. Now they choose a distribution over pure strategies, leading to the following game

inf η∈P(H) sup Ψ ∈P (F X |αp ) 2 E h∼η,ψ∼Ψ Score adv Ω (h, ψ) . ( . )
Without making further assumptionse.g. compactness -we cannot apply known results from game theory to prove the existence of an equilibrium. Studying the equilibrium is appealing from a theoretical point of view but would require strong results in the theory of optimal transport; hence we leave it to further investigations. But even without knowing if an equilibrium exists in the randomized setting, we can prove that randomization matters. More precisely we show that any deterministic hypothesis can be outperformed by a randomized one in terms of the worst-case adversarial score. To do so we simplify Equation ( . ) in two ways:

• We keep considering deterministic adversariesi.e. we restrict the search space of the adversary to (F X |αp ) 2 instead of P (F X |αp ) 2 . This condition corresponds to the current state-of-the-art in the domain: to the best of our knowledge, no e cient randomized adversarial attack has been designed -and so is used -yet.

• We only consider a subclass of randomized hypotheses, called mixtures, which are discrete probability measures on a nite set of hypotheses. We show that this randomization is enough to outperform any deterministic hypothesis. We will discuss in Chapters and the use of more general randomized hypothesis spaces. Let us now de ne a mixture.

De nition (Mixture of hypothesis). Let m ∈ N, h = (h 1 , ..., h m ) ∈ H m a vector of m hypothesis functions and q = (q 1 , . . . , q m ) ∈ P({1, . . . , m}) a probability vector . A mixed hypothesis of h by q is a mapping m q h from X to P(R) such that for all x ∈ X , m q h (x) outputs h i (x) with probability q i .

We call such a mixture a mixed strategy of the defender. Given some x ∈ X , this amounts to picking a hypothesis h i from h at random following the distribution q, and use it to output the predicted class for xi.e. sign(h i (x)). Note that a mixed strategy for the defender is a nondeterministic algorithm, since it depends on the sampling one makes on q. Hence, even if the attack space remains unchanged, the adversary now needs to maximize a new objective function which is the expectation of the adversarial score under the distribution m q h (x). It writes as follows

Score adv Ω (m q h , ψ) := E y∼ν E x∼ψy#µy E i∼q L 0/1 (h i (x), y) -λ Ω(ψ). ( . )
This notion of score is the natural extension of the deterministic case; hence we keep the notation Score adv Ω . In the following, it will be clear from context that the defender uses a mixed strategy.

. . Randomization matters: how to outperform deterministic hypotheses

Using this new set of hypotheses for the defender, we demonstrate that we can improve deterministic defenses using a simple mixed strategy. This method presents similarities with the notions of ctitious play [ ] in game theory, and boosting in machine learning [ ]. Given a deterministic hypothesis h 1 , we combine it -via randomization -with the best response h 2 to its optimal attack. The rationale behind this idea is that -by construction -e cient attacks on one of these two hypotheses will not work on the other. Mixing h 1 with h 2 has two opposite consequences on the adversarial score. On one hand, where we only had to defend against attacks 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. If we can calibrate the weights so that the new attacks have a low probability of succeeding, then the average risk under attack on the mixture will be low.

Theorem (Randomization matters). Let us consider h

1 ∈ H, λ ∈ (0, 1), ψ ∈ BR Ω (h 1 ) and h 2 ∈ BR(ψ).
Then for any q 1 ∈ (max(λ, 1λ), 1) and for any ψ ∈ BR Ω (m q h ) one has

Score adv Ω (m q h , ψ ) < Score adv Ω (h 1 , ψ).
Where h = (h 1 , h 2 ), q = (q 1 , 1q 1 ), and m q h is the mixture of h by q. Proof. To demonstrate Theorem , let us denote U = P h 1 (α p ) and de ne the

α p -dilation of U as U ⊕ α p := u + v | (u, v) ∈ U × X and v p ≤ α p .
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 . Then taking q 1 ∈ (0, 1), we can de ne m q h , and ψ ∈ BR Ω (m q h ). We aim to nd a condition on q 1 so that the score of m q h is lower than the score of h 1 . Finally, let us recall that

Score adv Ω (m q h , ψ ) = ν(1) X essup z∈Bp(x,αp) q 1 1{h 1 (z) ≤ 0} + (1 -q 1 ) 1{h 2 (z) ≤ 0} -λ 1{x = z} dµ 1 (x) + ν( 1) X essup z∈Bp(x,αp) q 1 1{h 1 (z) ≥ 0} + (1 -q 1 ) 1{h 2 (z) ≥ 0} -λ 1{x = z} dµ 1 (x).
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 ⊕α p ∩P h 1 and ψ -1 1 (U ) -inverse image of U by ψ 1 . These sets represent respectively the points we mix on, the points that may become attacked -when changing from h 1 to m q h -by moving them on U , and the ones that were -for h 1 -attacked before by moving them on U . Hence, for simplicity, we only write those terms. Furthermore, we denote

U + := U ⊕ α p ∩ P h 1 \ U, U -:= ψ -1 1 (U ) and recall U := P h 1 (α p ).
One can refer to Figure . for visual interpretation of this sets. We can now evaluate the worst-case adversarial score for h 1 restricted to the above sets. Thanks to Lemma that characterizes ψ, we can write

Score adv Ω (h 1 , ψ) |U, U + , U - = (1 -λ) × ν(1)µ 1 (U ) + ν( 1)µ 1 (U ) + 0 × ν(1)µ 1 U + + ν( 1)µ 1 U + + ν(1)µ 1 U -+ (1 -λ) × ν( 1)µ 1 U -.
Similarly, we can write the worst-case adversarial score of the mixture on the sets we consider. Note that the max operator comes from the fact that the adversary has to make a choice between attacking the zone or just taking advantage of the error due to randomization.

Score adv Ω (m q h , ψ ) |U, U + , U - = max(1 -q 1 , 1 -λ) × ν(1)µ 1 (U ) + max(q 1 , 1 -λ) × ν( 1)µ 1 (U ) + max(0, 1 -q 1 -λ) × ν(1)µ 1 U + + ν( 1)µ 1 U + + ν(1)µ 1 U -+ max(0, q 1 -λ) × ν( 1)µ 1 U -.
Computing the di erence between these two terms, we get the following

Score adv Ω (h 1 , ψ) -Score adv Ω (m q h , ψ ) ( . ) = (1 -λ -max(1 -q 1 , 1 -λ)) × ν(1)µ 1 (U ) ( .
) ) First recall that both µ 1 and µ 1 have full support. Let us now simplify Equation ( . ) using additional assumptions.

+ (1 -max(q 1 , 1 -λ)) × ν( 1)µ 1 (U ) ( . ) -max(0, 1 -q 1 -λ) × ν(1)µ 1 U + ( . ) +(1 -λ -max(0, q 1 -λ)) × ν( 1)µ 1 U -. ( .
• First, we have that Equation ( .) is equal to

min(1 -q 1 , λ)µ 1 (U )ν( 1) > 0.
Thus, a su cient condition for the di erence between the adversarial scores to be positive is to have the other terms greater or equal to 0.

• To have Equation ( .) ≥ 0 we can always set max(1q 1 , 1λ) = 1λ. This gives us q 1 ≥ λ.

• Also note that to get ( . ) ≥ 0, we can force max(1q 1λ, 0) = 0. This gives us q 1 ≥ 1λ.

• Finally, since q 1 ≥ λ, we have that 1λmax(0, q 1λ) = 1q 1 thus Equations ( . ) > 0.

With the above simpli cations, we have ( . ) > 0 for any q 1 > max(λ, 1λ) which concludes the proof.

Remark . Note that depending on the initial hypothesis h 1 and the conditional distributions µ 1 and µ 1 , the gap between Score adv Ω (m q h , ψ )and Score adv Ω (h 1 , ψ) could vary. Therefore, with additional conditions on h 1 , µ 1 and µ 1 , we could make the gap appear more explicitly. We keep the formulation general to emphasize that for any h 1 , we can build a better m q h .

Even-though Theorem only applies to mixtures of two classi ers, it directly implies that randomized hypotheses -de ned in a broader way -outperform deterministic ones in terms of regularized adversarial score. Based on this nding, we devise a simple procedure called boosted adversarial training to construct a robust mixture of two hypotheses. It relies on three core principles: adversarial training, boosting and randomization. The procedure is summarized in Algorithm .

Algorithm : boosted adversarial training

Input : D the training data set and q 1 the probability parameter.

Train

h 1 on D with adversarial training Generate the adversarial data set D against h 1 . Train h 2 on D q ← (q 1 , 1 -q 1 ) h ← (h 1 , h 2 ) return m q h
Given a dataset D and a probability parameter q 1 ∈ [1/2, 1), we construct h 1 the rst hypothesis of the mixture by using adversarial training on D. Then, we train the second hypothesis h 2 on a data set D that contains adversarial examples for h 1 . At the end of the procedure, we return the mixture constructed with the two hypothesis where the rst one has a probability of q 1 and the second 1q 1 accordingly. The parameter q 1 is found by conducting a grid-search.

. Numerical validation: improving adversarial training

To empirically evaluate the above procedure, we run a series of experiments on the CIFAR-and CIFAR-datasets using deep neural networks. We show that the above simple randomization scheme can improve the robustness of adversarial training. Let us rst start by presenting the experimental setup we use. For direct access to the implementation, one can refer to the following Github repository.

https://github.com/MILES-PSL/ Randomization-matters-How-to-defend-against-strong-adversarial-attacks

. . Experimental setup

Architecture and training procedure

All the hypotheses we use in this section are WideResNets -see [ ] -with 28 layers, a widen factor of 10, a dropout factor of 0.3 and LeakyRelu activation with a 0.1 slope. To train an undefended classi er we use the following hyper-parameters.

• Number of Epochs:

• Batch size:

• Loss function: Cross Entropy Loss • Optimizer : Stochastic gradient descent algorithm with momentum 0.9, weight decay of 2 × 10 -4 and a learning rate that decreases during the training as follows:

lr =            0.1 if 0 ≤ epoch < 60 0.02 if 60 ≤ epoch < 120 0.004 if 120 ≤ epoch < 160 0.0008 if 160 ≤ epoch < 200.

Remark . To train a hypothesis with adversarial training we use the same hyper-parameters as above, and generate adversarial examples during training using an ∞ adversary with 20 iterations.

We also use PGD with 20 iterations and α ∞ = 0.031 to build D.

Threat models

To compare the empirical performances of our method with adversarial training, we consider two p adversaries with thresholds corresponding to CIFAR datasets • An ∞ adversary with perturbation bounded by 0.031. To model this adversary we use the PGD attack with t max = 100 iterations and a step-size s = 0.008.

• An 2 adversary with perturbation bounded by 0.8. To model this adversary we use the C&W attack with 100 iterations, a learning rate equal to 0.01, 9 binary search steps, and an initial constant of κ = 0.001.

Note that, when evaluating a defense against adversarial examples, it is crucial to test the robustness of the method against the best possible attack. Accordingly, the defense method should be evaluated against attacks that were speci cally tailored to ita.k.a. adaptive attacks [ ]. Specifically, when evaluating randomized algorithms, one should not try to compute the gradient over the logits/probits directly to avoid gradient masking as pointed out in [ ] and [ ]. Instead -as we explained in Equation ( . ) -we should provide the expected logits/probits of the mixture to the adversary. Since we assume perfect information for the adversary, it knows the distribution of the mixture; hence it can directly compute the expectation over h 1 and h 2 -without having to go through a Monte Carlo sampling scheme.

. . Results

In Table . we present results for q 1 = 0.8 and compared with classical adversarial training [ ] .

The accuracy and accuracy under attack presented for the mixture are expectation over h 1 and h 2 with respect to q -as explained above, i.e. we give the true expectation.

These results

show that for both model threats and on both datasets, the accuracy under attack of our mixture is much higher -0.10 better against any adversary -than the single classi er with adversarial training. However the standard accuracy of our technique dropped a little bit in the process -minus 0.3/0.2 compared to adversarial training. A trade-o between robustness and standard accuracy seems to appear. Indeed -be it adversarial training or boosted adversarial training -the better the accuracy under attack, the worse the accuracy without attack. Nevertheless, the trade-o is not linear since boosted adversarial training gains four times more robust accuracy than it loses standard one. This indicates that randomization can improve robustness of deterministic hypotheses. However, one should be careful when analyzing Table . . We should not draw conclusions either on the e cacy of a defense nor on the trade-o between robustness and accuracy only based on empirical evidence -since empirical defenses are often broken sometimes after being designed [ , , ]. Therefore, we need further theoretical and empirical investigations to validate randomization as a proper defense strategy.

Note that we compare here with the vanilla version of adversarial training. Other versions exist with slightly better accuracy under attack. Furthermore, to avoid some computational burden, we did not use data augmentation during the leaning procedure -which explains some di erences with the initial paper [ ].

.

Additional results: another type of penalty

The core arguments we used to demonstrate Lemma and Theorems do not depend on the form of the penalty we consider. Any notion of distance between the perturbation and the initial point would allow to nd the same kind of results. To show this, let us consider that X is a Hilbert space with a dot product ., . and associated norm ||.|| = ., . . Then we can de ne the following regularization that penalizes the expected norm under perturbation ψ, ) This regularization could for example materialize an adversary that seeks a solution to the Lagrangian relaxation presented in Section .e.g. C&W attack [ ].

Ω(ψ) := E y∼ν E x∼µy [ x -ψ y (x) ] . ( .
Remark . Note that we only use a dot product for the projection operator to be well defined. But any notion of distance with a well-defined projection works alike.

In this context, the best responses for the defender remain unchanged; hence we only focus on characterizing the set of best responses for the adversary. The new best response we get for the adversary shares a fundamental similarity with the previous one: the optimal attack will only change points that are close enough to the decision boundary. However, with our new penalty all attacked points are projected on the decision boundary. The proof is very similar to Lemma , but we display it below for completeness.

Lemma .

Let h ∈ H and ψ ∈ BR Ω (h). Then the following assertion holds:

ψ 1 (x) = proj(x) if x ∈ P h (α p ) x otherwise.
Where proj is the orthogonal projection on (P h ) c . ψ 1 is characterized symmetrically.

Proof. Let us rst simplify the worst-case adversarial score for h.

sup ψ∈(F X |αp ) 2 Score adv Ω (h, ψ) = y=±1 ν(y) sup ψy∈F X |αp E x∼µy [1{h(ψ y (x))y ≤ 0} -λ x -ψ y (x) ] .
Finding ψ 1 and ψ 1 are two independent optimization problems, hence, we focus on characterizing ψ 1i.e. y = 1.

sup

ψ 1 ∈F X |αp E x∼µ 1 [1{h(ψ 1 (x)) ≤ 0} -λ x -ψ 1 (x) ] = X essup z∈Bp(x,αp) 1{h(z) ≤ 0} -λ x -z dµ 1 (x) = j∈J H j essup z∈Bp(x,αp) 1{h(z) ≤ 0} -λ x -z dµ 1 (x),
where (H j ) j∈J is a partition of X . In particular, we take H 0 = P c h , H 1 = P h \ P h (α p ), and H 2 = P h (α p ). Then we can study the three sets independently.

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

. For x ∈ H 1 = P h \ P h (α p ). We have B p (x, α p ) ⊂ P h by de nition of P h (α p ).

Hence, for any z ∈ B p (x, α p ), one gets h(z) > 0. Then 1{h(z) ≤ 0}-λ xz ≤ 0. The only optimal z will thus be z = x, giving value 0.

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

essup z∈Bp(x,αp) 1{h(z) ≤ 0} -λ x -z = max 1 -λ essinf z∈Bp(x,αp)∩P c h x -z , 0 = max 1 -λ x -proj Bp(x,αp)∩P c h (x) , 0
Where proj Bp(x,αp)∩P c h is the projection on the closure of B p (x, α p )∩P c h a . Finally, let us remark that, since λ ∈ (0, 1) and α p ≤ 1, one has

1 -λ x -proj Bp(x,αp)∩P c h (x) ≥ 0
for any x ∈ H 2 . Hence, on P h (α p ), the optimal attack projects all the points on P c h .

Finally, since H 0 ∪ H 1 ∪ H 2 = X , Lemma holds. Furthermore, the worst-case adversarial score writes

sup ψ∈(F X |αp ) 2 Score adv Ω (h, ψ) = y=±1 ν(y) j∈J H j essup z∈Bp(x,αp) 1{h(z)y ≤ 0} -λ x -z dµ y (x) .
Since the value is 0 on

P h \ P h (α p ) for ψ 1 -resp. on N h \ N h (α p ) for ψ 1 -one gets = R(h) + ν(1) P h (αp) 1 -λ x -proj(x) dµ 1 (x) + ν( 1) N h (αp) 1 -λ x -proj(x) dµ 1 (x) .
a Note that proj Bp(x,αp)∩P c h exists. Indeed h is continuous, so Bp(x, αp) ∩ P c h is a closed and bounded set; thus compact -since we are in nite dimension. The projection is however not guaranteed to be unique since we have no evidence on the convexity of the set.

Note that, in practice, it might be computationally hard to generate the exact best responsei.e. the projection on P c h . That will happen for example if the decision boundary is very complexe.g. highly non-smooth -or when X is in a high-dimensional space. To keep the attack tractable, the adversary will have to compute an approximate best response by allowing the projection to reach points within a small ball around the boundary. This means that the best responses for the new penalized problem will sometimes match the best response for the previous one. As for the previous penalty, we illustrate in Figure . the the non-existence of a Pure Nash Equilibrium with two uni-dimensional Gaussian distributions. We can see -on the right -that the mass of µ 1 that was in P h (α p ) is transported on a Dirac distribution at the decision boundary. Similarly to the previous penalty, the Bayes optimal classi er for the new distribution will predict 1 for the zone P h (α p ), hence Theorem holds with exactly the same proof as above. Finally, let us present an adaptation of Theorem to our new penalty. The statement is almost the same, with the only di erence that we have to interpolate on the bound of the perturbation, getting a new condition: q 1 > max(1λδ, λ(α pδ)) with δ ∈ (0, α p ). The proof follows the same steps as before but because of the proj operator, some more calculus is needed.

Remark .

For the condition on q 1 to make sens, we also need that max(1λδ, λ(α pδ)) < 1. This will hold in particular when α p ≤ 1 which is a standard assumption considering the threshold we have discussed so far. In the remaining we will consider that α p ≤ 1 accordingly.

Theorem (Randomization matters bis). Let us consider α p ≤ 1, h 1 ∈ H, λ ∈ (0, 1), δ ∈ (0, α p ) and ψ ∈ BR Ω (h 1 ). Then there exists h 2 such that, for any q 1 ∈ (max(1λδ, λ(α pδ)), 1) and for any ψ ∈ BR Ω (m q h ) one has Score adv Ω (m q h , ψ ) < Score adv Ω (h 1 , ψ).

Where h = (h 1 , h 2 ), q = (q 1 , 1q 1 ), and m q h is the mixture of h by q. Proof. Let us take U ⊂ P h 1 (α p ) such that

min x∈U x -proj P h \P h (αp) (x) = δ ∈ (0, α p ).
We 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. Let q 1 ∈ (0, 1), the corresponding mixture m q h , and ψ ∈ BR Ω (m q h ). We will nd a condition on q 1 so that the score of m q h is lower than the score of h 1 . Recall that

Score adv Ω (m q h , ψ ) = ν(1) X essup z∈Bp(x,αp) q 1 1{h 1 (z) ≤ 0} + (1 -q 1 ) 1{h 2 (z) ≤ 0} -λ x -z dµ 1 (x) + ν( 1) X essup z∈Bp(x,αp) q 1 1{h 1 (z) ≥ 0} + (1 -q 1 ) 1{h 2 (z) ≥ 0} -λ x -z dµ 1 (x) .
As we discussed in the proof of Theorem , 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 ⊕ α p ∩ P h 1 and ψ -1 1 (U ). Hence, for simplicity, we only write those terms. Furthermore, we denote

U + := U ⊕ α p ∩ P h 1 \ U, U -:= ψ -1
1 (U ) and P αp := P h 1 (α p ).

One can refer to Figure . for a visual interpretation of these sets. We can now evaluate the worst-case adversarial score for h 1 restricted to the above sets. Thanks to Lemma that characterizes ψ, we can write

Score adv Ω (h 1 , ψ) = ν(1) U 1 -λ x -proj P c h 1 (x) dµ 1 (x) + ν( 1)µ 1 (U ) + ν(1) U + \Pα p 0 dµ 1 (x) + ν( 1)µ 1 U + \ P αp + ν(1) U + ∩Pα p 1 -λ x -proj P c h 1 (x) dµ 1 (x) + ν( 1)µ 1 U + ∩ P αp + ν(1)µ 1 U -+ ν( 1) U - 1 -λ x -proj U (x) dµ 1 (x).
Similarly we can evaluate the worst-case adversarial score for the mixture,

Score adv Ω (m q h , ψ ) = ν(1) U max 1 -q 1 , 1 -λ x -proj P c h 1 (x) dµ 1 (x) + ν( 1) U max(q 1 , 1 -λ x -proj U + (x) ) dµ 1 (x) + ν(1) U + \Pα p max(0, 1 -q 1 -λ x -proj U (x) ) dµ 1 (x) + ν( 1)µ 1 U + \ P αp + ν(1) U + ∩Pα p max 1 -q 1 -λ x -proj U (x) , 1 -λ x -proj P c h 1 (x) dµ 1 (x) + ν( 1)µ 1 U + ∩ P αp + ν(1)µ 1 U - + ν( 1) U - max 0, 1 -λ x -proj N c h 1 \U (x) , q 1 -λ x -proj U (x) dµ 1 (x).
Note that 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 q 1 , since the classi cation on U is now randomized -or by projecting on P c h 1 , which works with probability but may use more distance and so pay more penalty. We can now compute the di erence between both scores.

Score adv Ω (h 1 , ψ) -Score adv Ω (m q h , ψ ) ( . ) = ν(1) U 1 -λ x -proj P c h 1 (x) -max 1 -q 1 , 1 -λ x -proj P c h 1 (x) dµ 1 (x) ( .
)

+ ν( 1) U 1 -max(q 1 , 1 -λ x -proj U + (x) )dµ 1 (x) ( . )
ν(1)

U + \Pα p max(1 -q 1 -λ x -proj U (x) , 0)dµ 1 (x) ( . )
+ ν(1)

U + ∩Pα p 1 -λ x -proj P c h 1 (x) -max 1 -q 1 -λ x -proj U (x) , 1 -λ x -proj P c h 1 (x) dµ 1 (x) ( . )
+ ν( 1) ) First recall that both µ 1 and µ 1 have full support. Let us simplify Equation ( . ) using using additional assumptions.

U - 1 -λ x -proj U (x) -max 0, 1 -λ x -proj N c h 1 \U (x) , q 1 -λ x -proj U (x) dµ 1 (x). ( .
• First, note that Equation ( . )> . Then a su cient condition for the di erence to be strictly positive is to ensure that other lines are ≥ 0.

• In particular to have ( . ) ≥ 0 it is su cient to have for all

x ∈ U max 1 -q 1 , 1 -λ x -proj P c h 1 (x) = 1 -λ x -proj P c h 1 (x) .

This gives us q

1 ≥ λ(α p -δ) ≥ λ max x∈U x -proj P c h 1 (x) .
• Similarly, to have ( . ) ≥ 0, we should set for all x ∈ U + \ P αp

q 1 ≥ 1 -λ x -proj U (x) .
Since min

x∈U + \Pα p
xproj U (x) = δ, we get the condition q 1 ≥ 1λδ.

• Finally ( . ) ≥ 0, since by de nition of U -, for any x ∈ U -we have

x -proj N c h 1 \U (x) ≥ x -proj U (x) .
Finally, by summing all these simpli cations, we have ( . ) > 0. Hence the result holds for any q 1 > max(1λδ, λ(α pδ)).

.

Lessons learned and future works

In this chapter, we provided a new point of view on the problem of classi cation under perturbation -Problem ( . ). Based on simple tools from game theory, we demonstrated that adding some regularization can fundamentally modify the nature of the game between the adversary and the defender -model provider. This analysis led us to investigate randomized hypothesis classes.

Both our theoretical ndings and empirical validation prove the e cacy of this method and thus provide a rst answer to Q :

There might be a class of randomized hypotheses H for which the adversarial risk minimization problem has a solution h * with small adversarial risk

In Chapters and we will further investigate some speci c classes and show that we can obtain both robustness and accuracy -to some extent. Nevertheless, several questions remain open. We list here some of them that we aim to investigate in the future.

Future work : The equilibrium in the randomized regime

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 |αp ) 2 ) which implies more technicalities. The study of this equilibrium is also tightly related to that of the value of the game, which would be interesting for obtaining min-max bounds on the accuracy under attack.

Future work : Study the duality gap

For now, Theorem shows that there is no Pure Nash Equilibrium in the game, meaning that strong duality does not hold. But it does not indicate how distant the values from the infsup and the supinf problem area.k.a. the duality gap. Evaluating this duality gap could help us build a ner analysis on the impact of regularization on the game.

Future work : Boosted adversarial training, a certi ed defense?

Although the experimental results show that our mixture of hypotheses outperforms adversarial training, the algorithm we present do not provide guarantees in terms of certi ed accuracy. As the literature on adversarial attacks and defenses demonstrated, better attacks always exist. This is why, we need to further study the theoretical aspects of our procedure, to prove the robustness of the mixtures we design.

Theoretical analysis of randomized classi ers

Q :

Is there some hypothesis class H for which the adversarial risk minimization problem has a solution h * with small adversarial risk?

Q : Can we find a class H and a hypothesis h * ∈ H that simultaneously has small standard and adversarial risks?

In Chapter , we identi ed randomized hypotheses as good candidates to build more robust classi ers; thus partially answering Q . Here, we keep answering Q and provide preliminary answers to Q by studying randomized classi ers through the prism of learning theory. In Section . , we de ne this class and adapt the notions of risk and robustness to account for the internal random state of the classi ers. In particular, we use the total variation distance to de ne robustness as a local Lipschitz condition from X to P(Y). We show in Section . that under this robustness assumption, we can bound the di erence between the standard risk and the adversarial risk of any randomized classi er. This answers Q by evaluating the maximal trade-o between robustness and accuracy of the classi er. Then, we devise bounds on the standard generalization gap of this hypothesis class in Section . and discuss the consequences and limitations of our result. In Section . we analyze the stability of randomized classi ers with respect to their mode and the implications it has on our understanding of randomized smoothing. Finally, we extend our results to the Renyi divergence, present some additional results and summarize our ndings respectively in Sections . and . .

. Terminology for randomized classi ers

Notations. For any set Z with σ-algebra A(Z), if there is no ambiguity on the considered σalgebra, we denote P(Z) the set of all probability measures over (Z, A(Z)). For ρ ∈ P(Y), we sometimes denote ρ = (ρ 1 , .

. . De nitions on randomized classi ers

Remark .

In Chapter , we discussed the properties of mixtures of hypotheses. The above definition generalizes the previous one. Furthermore, we can consider any mapping as a probabilistic mapping whether it explicitly considers randomization or not. In fact, any deterministic classifier can be seen as a randomized one, since we can characterize it with a Dirac measure.

As we previously did for randomized hypotheses, we can adapt the concepts of risk and adversarial risk for a randomized classi er. The loss function we use is the natural extension of the 0/1 loss to the randomized regime. Given a randomized classi er m and a sample (x, y) ∼ D it writes ) This loss function evaluates the probability of misclassi cation of m on a data sample (x, y) ∼ D.

L 0/1 (m(x), y) := E ŷ∼m(x) [1{ŷ = y}]. ( .
Accordingly, the risk of m with respect to D writes

R(m) := E (x,y)∼D L 0/1 (m(x), y) . ( . )
Finally, given m and (x, y) ∼ D, the adversary seeks a perturbation τ ∈ X such that τ p ≤ α p that maximizes the expected error of the classi er on xi. L 0/1 (m(x + τ ), y) .

( . )

. . Robustness for randomized classi ers

We could de ne the notion of robustness for a randomized classi er depending on whether it misclassi es any test sample (x, y) ∼ D. But in practice, neither the adversary nor the model provider have access to the ground-truth distribution D. Furthermore, in real-world scenariose.g. the autonomous car -we want to check before its deployment whether the model is robust. Therefore, we want the classi er to be stable on the regions of the space where it already classi es correctly. Formally a -deterministic -classi er c : X → Y is called robust if for any (x, y) ∼ D such that c(x) = y, and for any τ ∈ X one has

τ p ≤ α p =⇒ c(x) = c(x + τ ). ( .
)
By analogy with this notion, we de ne robustness for a randomized classi er as follows.

De nition (robustness for a randomized classi er). A randomized classifier m :

X → P(Y) is called (α p , )-robust w.r.t. D if for any x, τ ∈ X , one has τ p ≤ α p =⇒ D(m(x), m(x + τ )) ≤ .
Where D is a metric/divergence between two probability measures. Moreover, given such a metric D, we denote M D (α p , ) the set of all randomized classifiers that are (α p , )-robust w.r.t. D.

Remark . Note that we did not add the constraint that m classifies well on (x, y) ∼ D, since it is already encompassed in the probability distribution itself. If the two probabilities m(x) and m(x + τ ) are close, and if m(x) outputs y with high probability, then it will be the same for m(x + τ ).

This formulation naturally raises the question of the choice of metric D we should use to defend against adversarial attacks. Any choice of metric/divergence will instantiate a notion of adversarial robustness, and it should be carefully selected. In the present work, we focus our study on the total variation distance and extend our results to the Renyi divergence in Section . . The question whether these metrics/divergences are more appropriate than others remains open but these two divergences are su ciently general to cover a wide range of other de nitions -see Section . for more details. Furthermore, these notions of distance comply with both a high level -Chapter -and a more practical analysis -Chapter .

Let us now recall the de nition of total variation distance. Let Z be an arbitrary space, and ρ, ρ be two measures in P(Z). The total variation distance between ρ and ρ is

D T V ρ, ρ := sup Z⊂A(Z) |ρ(Z) -ρ (Z)| . ( . )
The total variation distance is one of the most commonly used probability metrics. It admits several very simple interpretations, and is a very useful tool in many mathematical elds such as probability theory, Bayesian statistics or optimal transport [ , , ]. In optimal transport, it can be rewritten as the solution of the Monge-Kantorovich problem with the cost function cost(z, z ) = 1{z = z }, . ) where the in mum is taken over all joint probability measures π in P(Z × Z) with marginals ρ and ρ . According to this interpretation, it seems quite standard to consider the total variation distance as a relaxation of the trivial distance on [0, 1] -see e.g. [ , chap ] for details. In the remaining we denote M T V (α p , ) the set of all (α p , ) robust classi ers w.r.t. D T V .

D T V (ρ, ρ ) = inf Z 2 1 z = z dπ(z, z ) , (
. Risks' gap for robust randomized classi ers

.

. An additive bound for the risks' gap

As we discussed in Section . , we can always decompose the adversarial risk of a classi er m in two terms. First the standard risk of m and second the amount of risk the adversary creates with non-zero perturbations

R adv (m; α p ) = R(m) + R adv >0 (m; α p ). ( . )
Hence minimizing R(m) can give poor values for R adv (m; α p ) and vise-versa. In this section, we upper-bound R adv >0 (m; α p ) to simplify the learning procedure. Speci cally, let us consider m in the class of (α p , )-robust classi ers w.r.t. D T V . Then we can control the loss of accuracy under attack of this classi er with the robustness parameter .

Theorem (Risk's gap for TV-robust classi ers). Let m ∈ M T V (α p , ) . Then we have

R adv (m; α p ) ≤ R(m) + .
Proof. Let m be an (α p , )-robust classi er w.r.t. D T V , (x, y) ∼ D and τ ∈ X such that τ p ≤ α p . By de nition of the 0/1 loss we have

L 0/1 (m(x + τ ), y) = E ŷ∼m(x+τ ) [1{ŷ = y}].
Furthermore, by de nition of the total variation distance we have

E ŷ∼m(x+τ ) [1{ŷ = y}] -E ŷ∼m(x) [1{ŷ = y}] ≤ D T V (m(x), m(x + τ )).
Since m ∈ M T V (α p , ), the above amounts to write

L 0/1 (m(x + τ ), y) -L 0/1 (m(x), y) ≤ .
Finally, this holds for any (x, y) ∼ D and any α p bounded perturbation τ , then we get

E (x,y)∼D sup τ ∈Bp(αp) L 0/1 (m(x + τ ), y) -E (x,y)∼D L 0/1 (m(x), y) ≤ .
The above inequality concludes the proof.

This result means that if we can design a class M T V (α p , ) with small enough , then minimizing the risk of m ∈ M T V (α p , ) is also su cient to get a good value for the adversarial risk.

. . Robustness may not be at odds with accuracy.

The above result is relatively easy to obtain, but it has an interesting consequence on the understanding we have of the trade-o between robustness and accuracy. It says that there exists some classes of randomized classi ers for which robustness and standard accuracy may not be at odds, since we can upper-bound the maximal loss of accuracy the model may su er under attack. This questions previous intuitions developed on deterministic classi ers -see Section . -and keeps advocating for using randomization schemes as defenses against adversarial attacks. Note, however, that we did not evade the trade-o between robustness and accuracy, we only showed that with certain hypothesis classes it is manageable. Since we can bound the di erence between the risk and the adversarial risk of any classi er m ∈ M T V (α p , ), we now want to minimize the risk over a hypothesis class M ⊂ M T V (α p , ) to obtain a good approximation for both Problems ( . ) and ( . ). But for this, we still need the empirical risk minimization to converge to a solution with small standard risk. To measure the rate of convergence of the empirical risk toward the risk on M, we need to upper-bound the Rademacher complexity of L M T V (αp, ) .

Remark .

Remark that this result is not limited to the 0/1 loss. Indeed, any loss function of the form (x, y) → E ŷ∼m(x) [L(ŷ, y)] with L non-negative would work alike.

. Generalization gap for randomized classi ers . . Bounding the Rademacher complexity for the total variation

Recall from Chapter that in the supervised learning setting we have access to n i. i.d.training examples drawn from D, denoted by S := {(x  , y 1 ), (x  , y 2 ), . . . , (x n , y n )}. Given a class M ⊂ M T V (α p , ), we aim to solve the empirical risk minimization problem

inf m∈M R S (m) := 1 n n i=1 L 0/1 (m(x i ), y i ) . ( . )
Then, to evaluate how far the theoretical risk of the selected classi er m is from what we observe on S, we need to upper bound the generalization gap of any m ∈ M T V (α p , ). To do so, we can to study the empirical Rademacher complexity of

L M T V (αp, ) := {(x, y) → L 0/1 (m(x), y) s.t. m ∈ M T V (α p , )}. ( . )
Then, thanks to Theorem , for any δ ∈ (0, 1), and for any m ∈ M T V (α p , ), the following holds with probability at least 1δ,

R(m) ≤ R S (m) + 2R S L M T V (αp, ) + 3 ln(2/δ) 2n . ( .
)
Remark . Note that in Theorem , there is an additional parameter W where L ∞ ≤ W .

Here, by definition of the 0/1 loss, we have L 0/1 ∞ ≤ 1; hence W = 1 in Equation ( . ).

Accordingly, we want to upper bound the empirical Rademacher complexity of L M T V (αp, ) , which motivates the following de nition.

De nition (α-covering and external covering number). Let us consider (X , . p ) a vector space equipped with the p norm, B ⊂ X and α ≥ 0. Then

• C = {c  , . . . , c m } is an α-covering of B for the p norm if for any x ∈ B there exists c i ∈ C such that x -c i p ≤ α.
• The external covering number of B writes N B, . p , α . It is the minimal number of points one needs to build an α-covering of B for the p norm.

The covering number is a well-known measure that is often used in statistical learning theory [ ] and asymptotic statistics [ ] to evaluate the complexity of a set of functions. Here we use it to evaluate the number of p balls we need to cover the training samples, which gives us the following bound on the Rademacher complexity of L M T V (αp, ) .

Theorem (Rademacher complexity TV-robust classi ers). Let L M T V (αp, ) be the loss function class associated with M T V (α p , ). Then, for any S := {(x  , y 1 ), . . . , (x n , y n )}, the following holds,

R S L M T V (αp, ) ≤ N × K n + .
Where N = N {x  , . x ic l = j .

We also denote

E j = ∪ y∈[K]
E y,j . Finally, we denote L m : (x, y) → L 0/1 (m(x), y). Then, by de nition of the empirical Rademacher complexity, we can write

R S L M T V (αp, ) = 1 n E r i sup m∈M T V (αp, ) n i=1 r i L m (x i , y i ) .
where r i are i.i.d. drawn from a Rademacher distributioni.e. P(r i = 1) = P(r i = -1) = 1 2 . Then we can use E j to write

R S L M T V (αp, ) = 1 n E r i   sup m∈M T V (αp, ) N j=1 i∈E j r i L m (x i , y i )   .
Furthermore for any m ∈ M T V (α p , ) and i ∈ E j , there exists i ∈ [-, ] such that:

L m (x i , y i ) = L m (c j , y i ) + i . Then we have R S L M T V (αp, ) ≤ 1 n E r i   sup m∈M T V (αp, ) N j=1 i∈E j r i L m (c j , y i )   + 1 n E r i   sup i ∈[-, ] N j=1 i∈E j r i i   .
Let us start by studying the second term. We have

1 n E r i   sup i ∈[-, ] N j=1 i∈E j r i i   = 1 n E r i sup i ∈[-, ] n i=1 r i i = 1 n n i=1 = .
Now looking at the rst term. Since L m (x, y) ∈ [0, 1] for all (x, y) we have

1 n E r i   sup m∈M T V (αp, ) N j=1 i∈E j r i L m (c j , y i )   = 1 n E r i   sup m∈M T V (αp, ) N j=1 K y=1 L m (c j , y) i∈E y,j r i   ≤ 1 n E r i   N j=1 K y=1 i∈E y,j r i   .
Finally using the Khintchine inequality and the Cauchy Schartz inequality we get

1 n E r i   N j=1 K y=1 i∈E y,j r i   ≤ 1 n N j=1 K y=1 |E y,j | (Khintchine)
Theoretical analysis of randomized classifiers

≤ 1 n √ N × K N j=1 K y=1 |E y,j | (Cauchy) = N × K n .
By combining the upper-bounds we have for each term, we get the expected result,

R S L M T V (αp, ) ≤ N × K n + .
The More precisely, both analyses conclude that robust models generalize well if the training samples have a small covering number. Note, however, that we base our formulation on an adaptive partition of the samples, while the initial paper only focuses on a xed partition of the input space.

The interested reader can refer to the discussion section in [ ] for more details. These ndings seem to contradict the current line of works on the hardness of generalization gap in the adversarial setting -see Section . . In fact, if the ground truth distribution is suciently concentrated, a small number of balls can cover S with high probability; hence N = O(1). This means that we can learn robust classi ers with the same sample complexity as in the standard setting. But if the ground truth distribution is not concentrated enough, the training samples will be far one from another; hence forcing the covering number to be large. In the worse case scenario, we need to cover the whole space [0, 1] d giving a covering number N = O 1 (αp) d which is exponential in the dimension of the problem. Figure . illustrates the exponential growth of the covering number of [0, 1] d for the ∞ norm. When d = 2 -on the left -we need 2 2 = 4 points to cover [0, 1] d with ∞ balls of radius 1 2 . When d = 3 -on the right -we need 2 3 = 8 points. In general, covering [0, 1] d with ∞ balls of radius α ∞ , requires at least 1 (α∞) d elements. Finally, when we change from the ∞ to any p norm, we get a covering number

N [0, 1] d , . p , α p = O 1 (αp) d . Therefore, in the worst-case scenario, our bound is in O 1 (αp) d √ n + .
When α p is small and the dimension of the problem is high, this bound is too large to give any meaningful insight on the generalization gap of the problem. Therefore, we still need to tighten our analysis to show that robust learning for randomized classi ers is possible in high dimensional spaces.

Remark .

Note that, we provided a very general result for randomized classifiers under the only assumption that they are robust w.r.t. the total variation distance. To build a finer analysis, and to evade the dimension dependencies, we should consider designing specific sub-classes M ⊂ M T V (α p , ) and adapt the techniques of proof to make the term N smaller in the worst-case scenario.

. Mode preservation and randomized smoothing

. . Mode preservation property for randomized classi ers

Notations. Let ρ ∈ P(Y) be the vector of point-wise probability ρ = (ρ 1 , . . . , ρ K ), we denote (ρ (1) , . . . , ρ (K) ) the probability vector ρ sorted in decreasing order.

Even though randomized classi ers have some interesting properties regarding generalization gap, we can also study them through the prism of deterministic robustness. Let us for example consider the classi er that outputs the class with the highest probability for m(x)a.k.a. the mode of m(x). It writes c :

x → argmax k∈[K] m(x) k ( . )
Then checking whether c is robust boils down to demonstrating that the mode of m(x) does not change under perturbation. It turns out that D T V robust classi ers have this property. We call it the mode preservation property of M T V (α p , ).

Proposition (Mode preservation for D T V -robust classi ers). Let m ∈ M T V (α p , ) be a robust randomized classifier and x ∈ X such that m(x) (1) ≥ m(x) (2) + 2 . Then, for any τ ∈ X , the following holds,

τ p ≤ α p =⇒ c(x) = c(x + τ ) . Proof. Let x, τ ∈ X such that τ p ≤ α p and m ∈ M T V (α p , ) such that m(x) (1) ≥ m(x) (2) + 2 .

Theoretical analysis of randomized classifiers

By de nition of M T V (α p , ), we have that

D T V (m(x), m(x + τ )) ≤ .
Then, for all k ∈ {1, . . . , K} we have

m(x) k -≤ m(x + τ ) k ≤ m(x) k + .
Let us denote k * the index of the biggest value in m(x)i.e. m(x) k * = m(x) (1) . For any k ∈ {1, . . . , K} with k = k * , we have m

(x) k * ≥ m(x) k + 2 . Finally, for any k = k * , we get m(x + τ ) k * ≥ m(x) k * -≥ m(x) k + ≥ m(x + τ ) k .
Then, argmax

k∈[K] m(x) k = argmax k∈[K] m(x + τ ) k .
This concludes the proof.

Coming back to the decomposition in Equation ( .), with the above result, we can bound the risk the adversary induces with non-zero perturbations by the mass of points on which the classi er c gives the good response but based on a low probability, i.e. with small con dence. ) This means that the only points on which the adversary may induce misclassi cation are the points on which m already has a high risk. Once more, this says something fundamental about the behavior of robust randomized classi ers. On undefended models, the adversary could change the decision on any point it wanted; now it is limited to changing points on which the classi er is already bad. This considerably mitigates the threat model we should consider.

R adv >0 (m) ≤ P (x,y)∼D c(x) = y and m(x) (1) < m(x) (2) + 2 . ( .
Furthermore, for any deterministic classi er designed as in Equation ( . ), we can also bound the maximal loss of accuracy under attack the classi er may su er. This bound may, however, be harder to evaluate since it now depends on both the classi er and the dataset distribution.

. . From mode preservation to randomized smoothing

The classi er we de ne in Equation ( . ) and the mode preservation property of m are closely related to provable defenses based on randomized smoothing. Recall that the core idea of randomized smoothing is to take a hypothesis h with probit outputs, and to build a robust classi er that writes ) From a probabilistic point of view, for any input x, randomized smoothing amounts to output the most probable class of the probability measure ) Hence, randomized smoothing uses the mode preservation property of m to build a provably robust -deterministic -classi er. Therefore, the above results -Proposition and Equation . -also hold for provable defenses based on randomized smoothing.

c rob : x → argmax k∈[K] E z∼N (0,σ 2 I) [h k (x + z)] . ( .
m(x) := E z∼N (0,σ 2 I) [h 1 (x + z), . . . , h K (x + z)] . ( .

Remark . Note that we can only use the mode preservation property of

m if it is (α p , )-robust w.r.t. D T V .
In the next chapter we will demonstrate that from any deterministic hypothesis h, we can build a robust randomized classifier using noise injection from a Gaussian distribution; hence m defined in Equation ( . )

is robust w.r.t. D T V .
Studying randomized smoothing from our point of view could give an interesting new perspective on that method. So far no results have been published on the generalisation gap of this defense in the adversarial setting. We could devise generalization bounds by similarity with our analysis. Furthermore, the probabilistic interpretation stresses that randomized smoothing is somewhat restrictive since it only considers probability measures which are the expectation on a simple noise injection scheme. The mode preservation property explains the behavior of randomized smoothing, but also presents fundamental properties of randomized defenses that could be used to construct more general defense schemes.

. Additional results: extension to the Renyi divergence and discussion on probability metrics . . Extending previous results to the Renyi divergence

In this section, we extend the previous results to another probability divergence of reference, namely the Renyi divergence. Let Z be an arbitrary space, and ρ, ρ be two measures in P(Z), with probability density functions of g and g according to a third measure ν. The Renyi divergence of order β writes

D β ρ, ρ := 1 β -1 log Y g (y) g(y) g (y)
β dν(y) .

The Renyi divergence [ ] is a generalized divergence de ned for any β on the interval [1, ∞].

It equals the Kullback-Leibler divergence when β → 1, and the maximum divergence when β → ∞. It also has the property of being non-decreasing with respect to β. This divergence is very common in machine learning and Information theory [ ], especially in its Kullback-Leibler form as it is widely used as the loss function -cross entropy -of classi cation algorithms. In the remaining, we denote M β (α p , ) the set of (α p , )-robust classi ers w.r.t. D β .

Let us show that, for any randomized classi er in this class, we can bound the gap between the risk and the adversarial risk of m. In the context of the Renyi divergence, the factor that controls the classi er's loss of accuracy under attack is multiplicative and depends both on the robustness parameter and on the divergence parameter β.

Theorem (Multiplicative risks' gap for Renyi-robust classi ers

). Let m ∈ M β (α p , ). Then we have R adv (m; α p ) ≤ (e R(m)) β-1 β .
The proof of this theorem mainly relies on a famous property of the Renyi divergence called probability preservation property.

Proposition ([ ])

. Let ρ and ρ be two measures in P(Z). Then for any Z ∈ A(Z), the following holds,

ρ(Z) ≤ exp D β (ρ, ρ ) ρ (Z) β-1 β .
With this proposition at hand, we can now demonstrate how the adversarial risk of a randomized classi er relates to its standard risk, under robustness assumptions.

Proof. Let m be an (α p , )-robust classi er w.r.t. D β , (x, y) ∼ D and τ ∈ X such that τ p ≤ α p . With the same reasoning as above, and with Proposition , we get

L 0/1 (m(x + τ ), y) = E ŷ∼m(x+τ ) [1{ŷ = y}] = P ŷ∼m(x+τ ) [ŷ = y] ≤ e D β (m(x+τ ),m(x)) P ŷ∼m(x) [ŷ = y] β-1 β (Prop. ) = e D β (m(x+τ ),m(x)) E ŷ∼m(x) [1{ŷ = y}] β-1 β ≤ e L 0/1 (m(x), y) β-1 β .
Since this holds for any (x, y) ∼ D and any α p bounded perturbation τ , we get

R adv (m; α p ) = E (x,y)∼D sup τ ∈Bp(αp) L 0/1 (m(x + τ ), y) ≤ E (x,y)∼D e β-1 β L 0/1 (m(x), y) β-1 β ≤ e β-1 β E (x,y)∼D L 0/1 (m(x), y) β-1 β .
Finally, using the Jensen inequality, one gets

≤ e β-1 β E (x,y)∼D L 0/1 (m(x), y) β-1 β = (e R(m)) β-1 β .
The above inequality concludes the proof.

This rst result gives a multiplicative bound on the gap between the standard and adversarial risks. This means that if we can design a class M β (α p , ) with small enough , and big enough β, then minimizing the risk of any m ∈ M β (α p , ) is su cient to also minimize the adversarial risk of m. Nevertheless, multiplicative factors are not easy to analyze. Theorem provides an additive counterpart to Theorem . It gives a control on the loss of accuracy under attack with respect to the robustness parameter and the Shannon entropy of m.

Theorem (Additive risks' gap for Renyi-robust classi ers). Let m ∈ M β (α p , ), then we have

R adv (m; α p ) -R(m) ≤ 1 -e -E x∼D |X e -H(m(x))
where H is the Shannon entropy -i.e. for any ρ ∈ P(Y),

H(ρ) = - k∈Y ρ k log(ρ k ) -and D |X is the marginal distribution of D for X . Proof. Let m ∈ M β (α p , ), then R adv (m; α p ) -R(m) = E (x,y)∼D sup τ ∈Bp(αp) L 0/1 (m(x + τ ), y) -L 0/1 (m(x), y) .
By de nition of the 0/1 loss, this amounts to write

= E (x,y)∼D sup τ ∈Bp(αp) E ŷadv ∼m(x+τ ),ŷ∼m(x) [1(ŷ adv = y) -1(ŷ = y)] ≤ E (x,y)∼D sup τ ∈Bp(αp) E ŷadv ∼m(x+τ ),ŷ∼m(x) [1(ŷ adv = ŷ)] = E (x,y)∼D sup τ ∈Bp(αp) P ŷadv ∼m(x+τ ),ŷ∼m(x) [ŷ adv = ŷ] = E (x,y)∼D sup τ ∈Bp(αp) 1 -P ŷadv ∼m(x+τ ),ŷ∼m(x) [ŷ adv = ŷ] = E (x,y)∼D sup τ ∈Bp(αp) 1 - K i=1 m(x) i × m(x + τ ) i .
Now, note that for any (x, y) ∼ D and τ ∈ X , by de nition of a probability vector in P(Y), and thanks to Jensen inequality we can write

K i=1 m(x) i × m(x + τ ) i ≥ exp K i=1 m(x) i log m(x + τ ) i .
Then by de nition of the entropy and the Kullback Leibler divergence we have

exp K i=1 m(x) i log m(x + τ ) i = exp -D 1 (m(x), m(x + τ )) -H(m(x)) .
Finally, by combining the above inequalities and since m ∈ M β (α p , ) we get

E (x,y)∼D sup τ ∈Bp(αp) P ŷadv ∼m(x+τ ),ŷ∼m(x) (ŷ adv = ŷ)
Theoretical analysis of randomized classifiers

≤ E (x,y)∼D sup τ ∈Bp(αp) 1 -e -D 1 (m(x),m(x+τ ))-H(m(x)) ≤ E (x,y)∼D 1 -e --H(m(x)) = 1 -e -E x∼D |X e -H(m(x)) .
The above inequality concludes the proof.

This result is interesting because it relates the accuracy of m with the bound we obtain. Intuitively, when m(x) has large entropyi.e. H(m(x)) → log(K) -the output distribution tends towards the uniform distribution; hence → 0. This means that the classi er is very robust but also completely inaccurate, since it outputs classes uniformly at random. On the opposite, if H(m(x)) → 0, then → ∞. The classi er may be accurate, but it is not robust anymore -at least according to our de nition. Hence we need to nd a classi er that has reasonable robustness and good accuracy simultaneously. To evaluate our ability to do so, as a corollary of Theorem , we can bound the Rademacher complexity of the class L M β (αp, ) .

Corollary . Let L M β (αp, ) be the loss function class associated with M β (α p , ). Then, for any S := {(x  , y 1 ), . . . , (x n , y n )}, the following holds,

R S L M β (αp, ) ≤ N × K n + min    3 2   1 + 4 9 -1   1/2 , e +1 -1 e +1 + 1   .
Where N = N {x  , . . . , x n }, . p , α p is the α p -external covering number of the inputs {x  , . . . , x n } for the p norm.

To prove Corollary , note that thanks to previous works [ , ], we can always upper-bound the total variation distance by a function of the Renyi divergence.

Proposition (Inequality between total variation and Renyi divergence). Let ρ and ρ be two measures in P(Z), and β ≥ 1. Then the following holds,

D T V (ρ, ρ ) ≤ min   3 2 1 + 4D β (ρ, ρ ) 9 -1 1/2 , exp(D β (ρ, ρ ) + 1) -1 exp(D β (ρ, ρ ) + 1) + 1   .
Proof. Thanks to [ ], one has

D 1 (ρ, ρ ) ≥ 2D T V (ρ, ρ ) 2 + 4D T V (ρ, ρ ) 4 9 .
From which it follows that

D T V (ρ, ρ ) ≤ 3 2 1 + 4D 1 (ρ, ρ ) 9 -1 1/2 .
Moreover, using inequality from [ ], one gets

D 1 (ρ, ρ ) + 1 ≥ log 1 + D T V (ρ, ρ ) 1 -D T V (ρ, ρ ) .
This inequality leads to the following

exp(D 1 (ρ, ρ ) + 1) -1 exp(D 1 (ρ, ρ ) + 1) + 1 ≥ D T V (ρ, ρ ).
By combining the above inequalities and by monotony of Renyi divergence regarding β, one obtains the expected result.

Then to get the proof of Corollary , we only need to combine Theorem and Proposition . Finally, let us present the mode preservation property for m ∈ M β (α p , ).

Proposition (Mode preservation for Renyi-robust classi ers). Let m ∈ M β (α p , ) be a robust randomized classifier and x ∈ X such that m(x) (1)

β β-1 ≥ exp (2 -1 β ) m(x) (2) β-1 β .
Then, for any τ ∈ X , the following holds,

τ p ≤ α p =⇒ c(x) = c(x + τ ),
where c(x) := argmax

k∈[K] m(x) k . Proof. Let x, τ ∈ X such that τ p ≤ α p and m ∈ M β (α p , ) such that m(x) (1) β β-1 ≥ exp (2 - 1 β ) m(x) (2) β-1 β .
Then by de nition of M β (α p , ), we have

D β (m(x), m(x + τ )) ≤ .
Furthermore, by using Proposition , for any k ∈ {1, . . . , K} we have

( * ) m(x) k ≤ (exp( ) m(x + τ ) k ) β-1 β and ( * * ) m(x + τ ) k ≤ (exp( ) m(x) k ) β-1 β .
Let us denote k * the index such that m(x) k * = m(x) (1) . Then using ( * ) we get

m(x + τ ) k * ≥ exp(-)(m(x) k * ) β β-1 .
Furthermore for any k ∈ {1, . . . , K} where k = k * , we can use the assumption we made on m to get

exp(-)(m(x) k * ) β β-1 ≥ exp β -1 β (m(x) k ) β-1 β .
Finally, using ( * * ) we have

exp β -1 β (m(x) k ) β-1 β ≥ m(x + τ ) k .
The above gives us argmax

k∈[K] m(x) k = argmax k∈[K]
m(x + τ ) k . This concludes the proof.

. . Discussion on the metric/divergence one should consider

As mentioned earlier in this chapter, the choice of the metric/divergence is crucial as it characterizes the notion of adversarial robustness we are examining. We focus on the total variation distance and Renyi divergence, but the question of whether these metrics/divergences are more appropriate than others remains open. It should be noted, however, that our de nition of robustness is monotonous depending on the metric/divergence we use.

D(m(x), m(x + τ )) ≤ f D (m(x), m(x + τ )) ≤ f ( ).
Then m is (α p , f ( ))-robust w.r.t. D which concludes the proof.

The above result suggests that the di erent notions of robustness we might conceive are more related than they appear. Here are some of the most classical divergences used in machine learning. Let ρ, ρ , ν three measures in P(Y). We denotes g and g the probability density functions of ρ and ρ with respect to ν. Then we can de ne the Wasserstein distance as follows

D W (ρ, ρ ) := inf Y 2
dist y, y dπ(y, y ), ( . ) where dist is some ground distance on Y, and the in mum is taken over all joint distributions π in P(Y × Y) with marginals ρ and ρ .

Remark .

In transportation theory, the Wasserstein distance is solution of the Monge-Kantorovich problem with the cost function c(y, y ) = dist(y, y ). Then, the definitions of total variation and Wasserstein distance match when we use the trivial distance dist(y, y ) = 1{y = y }. We also de ne respectively the Hellinger distance and the Separation distance as follows.

D H (ρ, ρ ) := Y √ g -g 2 dν 1/2 . ( . ) D S (ρ, ρ ) := sup y∈Y 1 - ρ(y) ρ (y) . ( .
)
If we take any of the above metrics/divergences to instantiate a notion of adversarial robustness we might get very di erent semantics for them. However, we can show that any of these de nitions can be covered -with respect to Proposition -either by the Renyi or the total variation robustness. Figure . summarizes the links we can make between all these di erent de nitions of robustness, and Propositions and present the associated results. We can see that the total variation distance and the Renyi divergence are both central since they can cover any of the other robustness notions. This does not mean that they are more appropriate than the others, but at least they are general enough to cover a wide range of possible de nitions.

Proposition .

Let m be a randomized classifier. If m is (α p , )-robust w.r.t. D T V then the following assertions hold.

• m is (α p , × diam(Y))-robust w.r.t. D W , where diam(Y) := max y,y ∈Y dist(y, y ). • m is α p , √ 2 -robust w.r.t. D H .
Proof. Let us consider ρ and ρ ∈ P(Y). Thanks to [ ] we have

• D W (ρ, ρ ) ≤ diam(Y)D T V (ρ, ρ ). • D H (ρ, ρ ) ≤ 2D T V (ρ, ρ ).
Hence, by using Proposition respectively with f : x → diam(Y)x and f : x → √ 2x we get the expected results.

Proposition .

Let m be a randomized classifier. If m is (α p , )-robust w.r.t. D β then the following assertions hold.

• m is (α p , )-robust w.r.t.

D T V with = min 3 2 1 + 4 9 -1 1/2 , exp( +1)-1 exp( +1)+1 . • m is (α p , √ )-robust w.r.t. D H . • If β = ∞, then m is (α p , ) robust w.r.t. D S .
Proof. ) First, let us suppose that β ≥ 1. Thanks to Proposition and to [ ], for any ρ, ρ ∈ P(Y) we have

• D H (ρ, ρ ) ≤ D 1 (ρ, ρ ) ≤ D β (ρ, ρ ) (see [ ]). • D T V (ρ, ρ ) ≤ min 3 2 1 + 4D β (ρ,ρ ) 9 -1 1/2 , exp(D β (ρ,ρ )+1)-1 exp(D β (ρ,ρ )+1)+1 (Prop. ).
Hence, by using Proposition , as above, we get the expected results.

) Now let us suppose that β = ∞. By de nition of the supremum divergence, we have

D ∞ (ρ, ρ ) = sup B⊂Y ln ρ(B) ρ (B) .
Furthermore, note that the function x → 1x -|ln(x)| is negative on R, therefore for any y ∈ Y one has

1 - ρ(y) ρ (y) ≤ ln ρ(y) ρ (y) .
Since the above inequality is true for any y ∈ Y, we have

D S ρ, ρ = sup y∈Y 1 - ρ(y) ρ (y) ≤ sup y∈Y ln ρ(y) ρ (y) ≤ sup B⊂Y ln ρ(B) ρ (B) = D ∞ (ρ, ρ ).
Finally, by using Proposition with f : x → x we get the expected results.

.

Lessons learned and future works

In this chapter, we examined the theoretical properties of randomized classi ers, both in terms of robustness and accuracy. We rst de ned a notion of robustness for randomized classi ers using probability metrics/divergences -the total variation distance and the Renyi divergence. We then demonstrated that when a randomized classi er complies with this de nition of robustness, we can estimate the maximum loss of precision it can su er under attack. This answers questions Q and Q as follows.

There exists classes of randomized classifiers for which we can control the gap between the adversarial and the standard risks.

We then studied the generalization properties of this class of functions and gave results indicating that robust randomized classi ers can generalize. Finally, we showed that randomized classi ers have a mode preservation property. This presents a fundamental property of randomized defenses that can be used to explain randomized smoothing from a probabilistic point of view. Based on the above analysis, we approach randomized classi ers from a more practical point of view in Chapter and demonstrate that we can build such classi ers from state-of-the-art neural network architectures. Our analysis could be re ned in several ways. We list some of them here for future considerations.

Future work : tighter bounds for the generalization gap

Our results on the standard generalization of randomized classi ers could be improved, especially since they can -in some cases -be very dependent on the dimension of the problem. In future works, we aim to study this property from a di erent perspective. We could for example study the covering number of the class of functions we consider instead of the covering number of the training samples. To this end, we could use technical tools such as the Massart's lemma or the notion of the shattering dimension to make the bound less dependent on the dimension of the problem.

Future work : studying the properties of randomized smoothing

In this chapter, we established some links between the mode preservation property of the randomized classi er, and the provable defense called randomized smoothing. Based on this evidence, we can bound the gap between the standard and adversarial risks for this defense. Another interesting direction would be to show that the classi ers based on randomized smoothing have a generalization gap similar to the classes of randomized classi ers we studied.

Future work : study f -divergences and integral probability metrics

For now, we presented results for randomized classi ers that are robust either with respect to the total variation distance or to the Renyi divergence. Both divergences have interesting properties, but we believe that they are a special case of more general classes of divergences for which similar results could be obtained. The study of more general forms of divergences such as f -divergences and integral probability metrics could provide some insights on the generality of the de nition of robustness we present in this chapter.

in Section . , we use Gaussian noise injection with advanced neural network architectures to build robust and accurate models. We support our theoretical claims with a series of experiments on CIFAR 10 and CIFAR 100. We achieve both good standard accuracy and state-of-the-art robustness. Finally, we extend our analysis to consider noise injection from exponential families and summarize our results respectively in sections . and . .

. From di erential privacy to Renyi robustness Notations. For any set Z with σ-algebra A(Z), if there is no ambiguity on the considered σalgebra, we denote P(Z) the set of all probability measures over (Z, A(Z)). Moreover, F Z×Z denotes the set of all measurable functions from (Z, A(Z)) to (Z , A(Z )). For ρ ∈ P(Z) and ψ ∈ F Z×Z , the pushforward measure of ρ by ψ is the measure ψ#ρ such that ψ#ρ(B) = ρ(ψ 1 (B)) for any B ∈ A(Z ). Finally, let us take M ∈ M d×d (R), we define the Mahalanobis norm with matrix M as the mapping x → x M = √ x M x.

. . Introduction to di erential privacy

The aim of this chapter is to link two seemingly unrelated notions, namely di erential privacy and robustness to adversarial examples. So far, we have discussed robustness thoroughly, but we have only mentioned the central idea behind di erential privacy in Chapter . So we begin with a brief introduction to this notion before making some links with our domain.

With the large adoption of machine learning techniques, researchers and practitioners are observing growing concerns on the user's privacy of the tools they develop. Beyond primary concerns to guarantee that the private information are not leaked or accidentally disclosed, a crucial issue of machine learning approaches is to ensure that information cannot be recovered or inferred from the sole release of the modeli.e. the learning algorithm should be privacy preserving. Several definitions have been introduced to characterize these algorithms in the context of machine learning and data publishing. Among them, di erential privacy has become the standard by providing a formal and adaptive de nition for privacy preserving data analysis. It has been widely studied in many frameworks and applications -see [ ] for a complete overview of the eld. The central idea of di erentiated privacy is to restore the user's trust in their privacy by ensuring that the learning procedure will yield essentially the same results whether or not a person joins the database. Formally, it writes as follows.

De nition (Di erential privacy). Let S n be the space of all data samples of size n, and H a class of hypotheses. A Learning algorithm A maps a training sample S ∈ S n to a hypothesis h ∈ H.

Then A is said to be -di erentially private if for any S, S ∈ S n that only di er from one inputoutput pair, and any h ∈ H, we have

P[A(S) = h] ≤ exp( ) P A S = h ,
where the probability is taken over the -possible -random states of the algorithm.

Note that the de nition of di erential privacy does not make any assumptions about the adversary, it only states a property of the algorithm. In practice, it is di cult to know what kind of auxiliary information and computing power the adversary may have access to. Therefore, the de nition of di erential privacy is based on the worst-case scenario where the adversary has access to all training samples and all details of the architecture except those it is trying to deduce. In this sense, the type of adversary we are considering is very close to the threat model we have dealt with until now -white box adversaries -even if they do not have the same objective. . If the training algorithm is not di erentially private -for example, if it is deterministicthe adversary can tune the dummy sample so that the training procedure on S and S gives the same results, i.e. h = h . The dummy sample is then very likely to contain information about Alice, which is a violation of her privacy.

. On the contrary, if the algorithm is di erentially private, given any dummy sample, the learning procedure produces the same model with a high probability. The adversary cannot tell whether the change in response is due to database change or randomization; therefore, Alice's information is safe.

Remark .

Note that in machine learning it is very rare to have a purely deterministic learning procedure -and even more so in deep learning. Indeed, as soon as we use stochastic gradient descent or random initialization, the learning procedure becomes random. In that sense, a learning procedure is a probabilistic mapping from S n to H. This definition of privacy makes intensive use of this property, and designs specific internal randomization procedures to make the algorithms safer.

. . Generalization of di erential privacy

The notion of di erential privacy is strongly correlated with the notion of "closeness", both in the input space S n and in the output space H.

P z ∼m(z) z ∈ B ≤ exp( ) P z ∼m(z) z ∈ B .
This de nition provides a more general view on di erential privacy, and adapts to more complex application settings such as geolocation and smart metering [ ]. Note that we return to the classical de nition of di erential privacy when we set Z = S n , Z = H, d Z is the hamming distance, and α = 1 . It is also worth noting that for any probability measures ρ, ρ ∈ P(Z ), and for any B ∈ A(Z ), having ρ(B) and ρ (B) within a multiplicative factor of exp( ) amounts to write

D ∞ (ρ, ρ ) := sup B∈A(Z ) ln ρ(B) ρ (B) ≤ . ( .
)
As a result, the two de nitions of di erential privacy we just saw simply enforce certain Lipschitz properties on probabilistic mappings based on a Renyi divergence with β = ∞. As a straightforward relaxation of these measure of privacy, Mironov [ ] proposed to use an arbitrary Renyi divergence of order β to obtain a more general de nition. This adaptation has principled theoretical advantages over the previous ones, making it the most practical formulation of the di erential privacy introduced so far.

De nition (Renyi di erential privacy). Let , α ≥ 0, (Z, d Z ) an arbitrary input metric space, and Z an output space. A probabilistic mapping m from Z to Z is called (α, , β) Renyi-private if for any z  , z  ∈ Z one has

d Z (z  , z  ) ≤ α =⇒ D β (m(z  ), m(z  )) ≤ .
Reading note. For the reader who might have skipped the additionnal results in Section . , let us recall the definition of Renyi divergence. Let Z be an arbitrary space, and ρ, ρ be two measures in P(Z), with probability density functions of g and g according to a third measure ν. The Renyi divergence of order β writes

D β ρ, ρ := 1 β -1 log Y g (y) g(y) g (y) β dν(y) .
The literature often sets α = 1, and argue that one can always scale dZ such that dZ ≤ 1 ts the appropriated notion of "closeness". We keep dZ unchanged and take an arbitrary α instead. Both de nitions are equivalent.

The Renyi divergence [ ] is a generalized divergence defined for any β on the interval [1, ∞]. It equals the Kullback-Leibler divergence when β → 1, and the maximum divergence when β → ∞.

Note also that the previous results we obtained on the risk and robustness using the total variation distance, can be extended with minor variations to the Renyi divergence.

. . A uni ed view on privacy and robustness

At a rst glance, the link between di erential privacy and robustness may not be immediate. First of all, the studied mapping is not the same: in the domain of privacy, we look at the learning algorithms, while in the domain of robustness, we look at the model. This equivalence -which comes directly from the de nitions -is important from a theoretical point of view and has direct practical implications. Let us discuss some of them below.

Consequence : Unifying robustness and privacy

At the moment, the privacy and robust machine learning communities do not interact much, and most often use very di erent mathematical tools. The explicit link we have just established between the two domains shows that they have very similar goals and that technical tools should be shared or transferred from one domain to the other. Moreover, privacy and robustness, although orthogonal in their semantics, may have common application settings. For example, in the case of facial or speech recognition systems, there are real privacy and security issues to be addressed. In this context, instead of considering two separate methodologies, adding unnecessary layers of complexity, we could address both issues simultaneously within a uni ed framework.

Consequence : Using di erential privacy as a fast track to robustness

Adversarial examples, in the context of deep learning, have only been studied for a few years now. On the other hand, di erential privacy -although still young on the scale of computer science research -is at least years ahead in terms of research accomplishments and societal awareness. It would therefore be interesting to take into account some of the lessons learned from privacy preserving machine learning and apply them to robustness. In particular, the literature on di erential privacy makes extensive use of Gaussian noise injection and data processing inequality to Note that we set the p norm for the de nition to exactly match. But as we discussed in Chapter , we could de ne a range of other notion for imperceptibility. Thus this equivalence between di erential privacy and robustness is much more general.

build private models. In the rest of this chapter, we show how we can easily adapt these two tools to build classes of robust classi ers -both w.r.t.D β and D T V .

. Leveraging tools from di erential privacy

. . Post-processing inequality

We just saw that di erential privacy amounts to controlling the Renyi divergence between the outputs of a probabilistic mapping m. A crucial property of the Renyi divergence is the Data processing inequality. It is a well-known result from information theory which states that "postprocessing cannot increase information" [ , ]. In the context of privacy preserving data analysis, this means that no adversary -regardless of its computational power -can increase the maximal probability to recover information from the data sample. This is a fundamental property that any good de nition of privacy should respect. Indeed, if an adversary can process the output of an algorithm to make the privacy guarrantees of the algorithm drop, then the privacy de nition is not reliable. In its general form the data-processing inequality is as follows.

Theorem (Post-processing inequality). Let us consider two arbitrary spaces Z, Z and ρ, ρ ∈ P(Z). Then for any ψ ∈ F Z×Z we have

D β (ψ#ρ, ψ#ρ ) ≤ D β (ρ, ρ ).
The proof of this statement exists in many forms in the information theory literature [ , , ]. But the notations and concepts can sometimes vary from the ones we use in this manuscript. Hence, we recall the proof for readability.

Proof. Let us consider ρ, ρ ∈ P(Z) with probability density functions g and g with respect to a third measure ν ∈ P(Z). Furthermore, let us denote ψ#g and ψ#g the probability density functions of ψ#ρ, ψ#ρ with respect to ψ#ν a . Then we have

D β (ψ#ρ, ψ#ρ ) = 1 β -1 log Z (ψ#g(z)) β ψ#g (z) 1-β dψ#ν(z) = 1 β -1 log Z ψ#g(z) ψ#g (z) β dψ#ρ (z).
Using the transfer theorem, we get

D β (ψ#ρ, ψ#ρ ) = 1 β -1 log Z ψ#g ψ#g • ψ(z) β dρ (z). Since ψ#g ψ#g • ψ(Z) = E g g (Z) ψ -1 (A(Z))
we get the following.

D β (ψ#ρ, ψ#ρ ) = 1 β -1 log Z ψ#g ψ#g • ψ(z) β dρ (z) = 1 β -1 log Z E g(z) g (z) ψ -1 (A(Z)) β dρ (z).
By using the Jensen inequality, and the property of the conditional expectation, we get

D β (ψ#ρ, ψ#ρ ) ≤ 1 β -1 log Z E g(z) g (z) β ψ -1 (A(Z)) dρ (z) = 1 β -1 log Z g(z) g (z) β dρ (z) = D β (ρ, ρ ).
The above inequality concludes the proof.

a ψ#g and ψ#g exist thanks to the Radon-Nykodym Theorem.

Remark . Note that the data-processing inequality is not limited to the Renyi divergence. Looking at the proof above, we see that the main argument is the Jensen inequality. Therefore, any divergence that can be written as the expectation of a convex function would give the same result. In fact, the data-processing inequality holds for any f -divergence ; which includes the total variation distance. Therefore the data -processing inequality holds both w.r.t.D β and D T V .

In the context of robustness to adversarial examples, we want to use the data processing inequality to ease the design of robust randomized classi ers. In particular, let us suppose that we can build a randomized pre-processing p : X → P(X ) such that for any x ∈ X and any α pbounded perturbation τ , we have

D(p(x), p(x + τ )) ≤ , with D ∈ {D T V , D β }. ( . )
Then, thanks to the data-processing inequality, we can take any deterministic classi er c to build an (α p , ) robust classi er w.r.t. D de ned as m : x → c#p(x). This considerably simpli es the problem of building a class of robust models, but we still need to build p in the rst place. To do so, we keep taking inspiration from the privacy preserving community and study noise injection schemes.

. . Pre-processing with Gaussian noise injection

We want to build p a randomized pre-processing that has a stable Renyi divergence and/or total variation distance.

To do this, we analyze the simple procedure of injecting random noise directly on the image before sending it to a classi er. Noise injection is another fundamental tool in the literature of di erential privacy. The most common noise choices are the Gaussian distribution and the Laplace distribution. Since the Renyi divergence is particularly well suited to the study of Gaussian distributions, we rst use this type of noise injection. More precisely, in this section, we focus on a mapping that writes as follows.

p : x → N (x, Σ), ( . ) for some given non-degenerate covariance matrix Σ ∈ M d×d (R). We extend our analysis in Section . to more general classes of noise, namely exponential families -which includes the see e.g. http://www.stat.yale.edu/~yw /teaching/ /lec .pdf for a very simple proof in the general case.

Laplace distribution. Let us now evaluate the maximal variation of Gaussian pre-processing p when applied to an image x ∈ X with and without perturbation.

Lemma . Let β > 1, x, τ ∈ X and Σ ∈ M d×d (R) a non-degenerate covariance matrix. Let ρ = N (x, Σ) and ρ = N (x + τ , Σ), then D β (ρ, ρ ) = β 2 τ 2 Σ 1 . Proof. Let β > 1.
Let us denote g and g respectively the probability density functions of ρ and ρ with respect to the Lebesgue measure. We also set x = x + τ for readability. Then we have

D β (ρ, ρ ) = 1 β -1 log E z∼ρ g(z) g (z) β = 1 β -1 log E z∼ρ exp β 2 (z -x ) Σ -1 (z -x ) -(z -x) Σ -1 (z -x)
.

By change of variable we get

= 1 β -1 log E z∼N (0,Σ) exp β 2 z Σ -1 z -(z + τ ) Σ -1 (z + τ ) = 1 β -1 log E z∼N (0,Σ) exp β 2 -2z Σ -1 τ -τ 2 Σ -1 = 1 β -1 log R d exp -1 2 z Σ -1 z -β 2 2z Σ -1 τ -β 2 τ 2 Σ -1 (2π) d det(Σ) d/2 dz .
Furthermore, for any z ∈ R d , we have

- 1 2 z Σ -1 z - β 2 2z Σ -1 τ - β 2 τ 2 Σ -1 = - 1 2 (z + βτ ) Σ -1 (z + βτ ) + β 2 -β 2 τ 2 Σ -1 .
Then we can re-write the Renyi divergence as follows

D β (ρ, ρ ) = 1 β -1 log E z∼N (-βτ ,Σ) exp β 2 -β 2 τ 2 Σ -1 = 1 β -1 log exp β 2 -β 2 τ 2 Σ -1 = β 2 τ 2 Σ 1 .
This concludes the proof.

Thanks to the above lemma, we know how to evaluate the level of Renyi-robustness that a Gaussian noise pre-processing brings to a classi er. Now that we have this result, thanks to Propo-sition , we can also upper-bound the total variation distance between N (x, Σ) and N (x + τ , Σ). But this bound is not always tight. Besides, we can directly evaluate the total variation distance between two Gaussian distributions as follows.

Lemma . Let x, x ∈ X and Σ ∈ M d×d (R) a non-degenerate covariance matrix. Let ρ = N (x, Σ) and ρ = N (x + τ , Σ), then D T V (ρ, ρ ) = 2Φ( τ Σ -1 2
) -1 with Φ the cumulative density function of the standard Gaussian distribution.

Proof. Let us denote g and g respectively the probability density functions of ρ and ρ with respect to the Lebesgue measure. Furthermore, we denote x = x + τ . Then by de nition of the total variation distance, we have

D T V (ρ, ρ) = ρ(Z)-ρ (Z) with Z = {z s.t. g(z) ≥ g (z)}. In our case g(z) ≥ g (z) is equivalent to (z -x ) Σ -1 (z -x ) -(z -x) Σ -1 (z -x) ≥ 0.
Then with the same simpli cation as above, we have

ρ(Z) = P z∼N (x,Σ) (z -x ) Σ -1 (z -x ) -(z -x) Σ -1 (z -x) ≥ 0 = P z∼N (0,Σ) (z -τ ) Σ -1 (z -τ ) -z Σ -1 z ≥ 0 = P z∼N (0,Σ) -2z Σ -1 τ + τ 2 Σ -1 ≥ 0 = P z∼N (0,I d ) z Σ -1/2 τ ≤ 1 2 τ 2 Σ -1 . Furthermore, if z ∼ N (0, I d ) then z Σ -1/2 τ ∼ N (0, τ 2 Σ -1 ); hence we also have z Σ -1/2 τ τ Σ -1 ∼ N (0, 1). Accordingly we get ρ(Z) = P z∼N (0,1) z ≤ 1 2 τ Σ -1 = Φ 1 2 τ Σ -1 .
By symmetry we get that ρ (A) = 1ρ(A) = 1 -Φ 1 2 τ Σ -1 . We then get

D T V (µ, ν) = 2Φ τ Σ -1 2 -1
which concludes the proof.

Note that both gures increase with the Mahalanobis distance of τ . Furthermore, we see that the greater the entropy of the Gaussian noise we inject, the smaller the distance between distributions. If we simplify the covariance matrix by setting Σ = σ 2 I d , it means that we can build more or less robust randomized classi ers against 2 adversaries, depending on σ.

Theorem (Robustness of Gaussian pre-processing). Let us consider c : X → Y a deterministic classifier, σ > 0 and p : x → N (x, σ 2 I d ) a pre-processing probabilistic mapping. Then the randomized classifier m := c#p is

• (α 2 , (α 2 ) 2 β 2σ )-robust w.r.t. D β against 2 adversaries. • (α 2 , 2Φ α 2 2σ -1)-robust w.r.t. D T V against 2 adversaries. Proof. Let x, τ ∈ X such that τ 2 ≤ α 2 .
Thanks to Lemma we have

D β (p(x), p(x + τ )) = β 2 τ 2 Σ -1 = β 2σ 2 τ 2 2 ≤ β(α 2 ) 2 2σ 2 .
Similarly, thanks to Lemma , we get

D T V (p(x), p(x + τ )) = 2Φ τ Σ -1 2 -1 ≤ 2Φ α 2 2σ -1.
Finally, from the data-processing inequality -Theorem , we get both

D β (m(x), m(x + τ )) ≤ β(α 2 ) 2 2σ 2 ,
and

D T V (m(x), m(x + τ )) ≤ 2Φ α 2 2σ -1.
The above inequalities conclude the proof.

Theorem means that we can build simple noise injection schemes as pre-processing of stateof-the-art image classi cation models and keep track of the maximal loss of accuracy under attack of the resulting randomized classi er. These results also highlight the profound link between randomized classi ers and randomized smoothing. Even-though our ndings are of di erent nature, both techniques use the same base mechanism -Gaussian noise injection. Therefore, Gaussian pre-processing is a principled defense method that can be analyzed trough several standpoints, including certi ed robustness and statistical learning theory.

. Numerical validation: the case study of the neural network

To illustrate our theoretical results, we train a randomized neural networks with Gaussian preprocessing during training and inference on CIFAR-and CIFAR-. Based on this randomized classi er, we study the impact of randomization on the standard accuracy of the network, and compare the theoretical trade-o between accuracy and robustness with experimental results against state-of-the-art attacks. Let us rst start by presenting the experimental setup we use. For direct access to the implementation, one can refer to the following Github repository.

https://github.com/MILES-PSL/Adversarial-Robustness-Through-Randomization

• An ∞ adversary with perturbation bounded by 0.06. To model this adversary we use the PGD attack with t max = 20 iterations and a step size s = 0.006.

• An 2 adversary with perturbation bounded by 1.6. To model this adversary we use the C&W attack with 60 iterations, a learning rate equal to 0.01, 9 binary search steps, and an initial constant of κ = 0.001.

As we already mentioned in Chapter , when evaluating a defense against adversarial examples, it is crucial to test the robustness of the method against the best possible attack. More precisely, when evaluating randomized algorithms, one must provide the adversary with the expected results from the classi er. Here, the actual distribution of the outputs can be di cult to evaluate since the Gaussian distribution passes through the network. Thus, to build an adversarial example, the adversary has to use a Monte Carlo mean estimator. For each input, we estimate the expected output of the network for 80 di erent samples of the Gaussian noise.

Remark .

In Chapter , we knew the exact distribution of the randomized classifier, so we didn't have to use Monte Carlos sampling. Therefore, to keep the calculation tractable, we decrease the number of gradient steps of the attacks compared to the previous experiments. . and . show the accuracy and the minimum level of accuracy under attack of our randomized neural network for several levels of injected noise. We can see -Figure . -that the precision decreases as the noise intensity grows. In that sense, the noise must be calibrated to preserve both accuracy and robustness against adversarial attacks -it must be large enough to preserve robustness and small enough to preserve accuracy. This is to be expected, because the greater the entropy of the classi er, the less precise it gets. Furthermore, when injecting Gaussian noise as a defense mechanism, the resulting randomized network m is both (α 2 , (α 2 ) 2 2σ )-robust w.r.t. D 1 and (α 2 , 2Φ α 2 2σ -1)-robust w.r.t. D T V against 2 adversaries. Therefore thanks to Theorems and we have that

. . Results

Figures

R adv (m; α 2 ) -R(m) ≤ 2Φ α 2 2σ
-1, and ( . ) ) Figure . illustrates the theoretical lower bound on accuracy under attack -based on the minimum gap between Equations ( .) and ( .) -for di erent standard deviations. The term in entropy has been estimated using a Monte Carlo method with 10 4 simulations. The trade-o between accuracy and robustness appears with respect to the noise intensity. With small noises, the accuracy is high, but the guaranteed accuracy drops fast with respect to the magnitude of the adversarial perturbation. Conversely, with bigger noises, the accuracy is lower but decreases slowly with respect to the magnitude of the adversarial perturbation. Overall, we get strong accuracy guarantees against small adversarial perturbations, but when the perturbation is bigger than 0.5 on CIFAR--resp. 0.3 on CIFAR-, the guarrantees are still not su cient. Remark . Note that the maximal 2 perturbation considered as imperceptible for CIFAR datasets is α 2 = 1.6. Hence our theoretical bounds are still not sufficient to consider worst case threats.

R adv (m; α 2 ) -R(m) ≤ 1 -e -(α 2 ) 2 2σ E x∼D |X e -H(m(x)) . ( .
Table . shows that in practice, randomized networks reach an accuracy under attack much higher than the theoretical lower bound we obtained, and keep a good accuracy against much larger perturbations. While Figure . illustrates theoretical robustness against increasing adversarial perturbations, Table . illustrates this trade-o experimentally. It compares the standard accuracy and accuracy under attack of randomized networks with Gaussian pre-processing for di erent standard deviations against the adversarial training of Madry et al. [ ]. We observe that the accuracy on the standard images for the noise injection method is similar to the one we .

Additional results: extension to the exponential family and experiments against 1 adversaries . . Extension to broader classes of noise injection

In the previous section we demonstrated, based on insights from the literature on di erential privacy, how Gaussian pre-processing can help build more robust models against adversarial examples. Now, from a di erential privacy perspective, the use of Laplace noise is at least as frequent as Gaussian noise. Moreover, the above results only work for 2 adversaries, so we wonder if we could use other types of noise to defend against other p adversaries. In this section, we extend the previous results to a larger family of noises, namely the exponential family.

De nition (Exponential family

g θ (z) = exp(t(z) θ -u(θ) + v(z))
where t(z) is a sufficient statistics, v a carrier measure (either for a Lebesgue or a counting measure) and u(θ) = log R d exp(t(z) θ + v(z))dz. We denote EF(θ, t, v) the set of such probability distributions.

To show the robustness of randomized networks with noise injected from an exponential family, we need to de ne the notion of modulus of continuity.

De nition

(Modulus of continuity). Let us consider d, d ∈ N and an arbitrary function f : R d → R d . f admits a non-decreasing modulus of continuity with respect to . p and . q if there exists a non-decreasing function ω p,q f : R + → R + such that for all x, x ∈ R d we have,

f (x) -f (x) q ≤ ω p,q f ( x -x p ).
The de nition of modulus of continuity is a simple relaxation of the Lipschitz continuity. Indeed, if ω p,q f is linear with 0 intercept and slope W , then f is W -Lipschitz with respect to . p and . q . We can now show how to control the Renyi divergence of a pre-processing based on an exponential family as follows.

Lemma . Let d ∈ N, β > 1 and θ ∈ R d . Let ρ be a probability measure from the exponential family EF (θ, t, v) where t and v have non-decreasing modulus of continuity ω t and ω v . Let us define the pre-processing p that to any image in X adds a noise drawn from ρ. Then, for any x ∈ X and any α p -bounded perturbation τ -for an p adversary -we have

D β (p(x), p(x + τ )) ≤ θ 2 ω p,2 t (α p ) + ω p,1 v (α p ).
Proof. Let us denote g θ the probability density function of ρ and δ a the Dirac measure mapping any element to 1 if it equals a and to 0 otherwise. Then by de nition of the convolution with the Dirac measure, we have that

D β (p(x), p(x + τ )) = D β (ρ * δ x , ρ * δ x+τ ).
Since the Renyi divergence is increasing with respect to β, we have

≤ D ∞ (ρ * δ x , ρ * δ x+τ ) = log sup z∈R d g θ (z -x) g θ (z -(x + τ )) = log sup z∈R d exp((t(z -x) -t(z -(x + τ ))) θ + v(z -x) -v(z -(x + τ ))).
By Cauchy Schwartz inequality, we get

≤ sup z∈R d θ 2 t(z -x) -t(z -(x + τ )) 2 + |v(z -x) -v(z -(x + τ ))|.
Furthermore, since t and v have modulus of continuity ω t and ω v , we get

≤ θ 2 ω p,2 t ( x + τ , x p ) + ω p,1 v ( x + τ , x p ) ≤ θ 2 ω p,2 t (α p ) + ω p,1 v (α p ).
The above inequality concludes the proof.

Thanks to this result, we identi ed a range of possible distributions to build robust classi ers. In particular, we can build a pre-processing based on the Laplace distribution to defend against 1 adversaries. However, the bound can be loose due to the use of the Cauchy Schwartz inequality.

The following result uses the same reasoning to get a tighter bound for a pre-processing based on Laplace noise injection.

Theorem (Robustness for Laplace pre-processing). Let us consider c : X → Y a deterministic classifier, σ > 0 and a pre-processing p that to any image adds noise drawn from Lap(0, σI d ) where Lap(0, σI d ) is the product measure of d uni-variate Laplace distributions with scale parameter σ and mean 0. Then the randomized classifier m

:= c#p is (α 1 , α 1 σ )-robust w.r.t. D β against 1 adversaries.
Proof. First, let us recall that a uni-variate Laplace distribution with scale σ and mean 0 denes an exponential family with t : x → |x|, v : x → 0, and θ = -1 σ . Furthermore, the distribution of Lap(0, σI d ) is de ned as the product of d uni-variate Laplace distributions. Then using the same rst steps as in Lemma , for any x, τ ∈ X such that τ 1 ≤ α 1 , we have

D β (p(x), p(x + τ )) ≤ log sup z∈R d exp - d i=1 |z i -x i | -|z i -(x i + τ i )| σ . Since d i=1 |z i -(x i + τ i )| -|z i -x i | ≤ τ 1 for any z, we get D β (p(x), p(x + τ )) ≤ log exp τ 1 σ ≤ α 1 σ .
The above inequality concludes the proof.

. . Additional experiments for 1 adversaries

To illustrate this result, we train a randomized neural network with Laplace pre-processing during training and inference on CIFAR-and CIFAR-. As for the Gaussian case, we study the impact of randomization on the standard accuracy of the network, and on its robustness. We use the same experimental protocol as above, but instead of using an 2 adversary -C&W -we take its adaptation to 1 attacks called Elastic Net attack -EAD [ ]. The optimization algorithm and implementation techniques are the same. The only modi cation is that we add an 1 term to the objective function, which gives

κ 1 × τ 1 + κ 2 × τ 2 + g(x + τ ). ( . )
Moreover, we select α 1 = 7 for the algorithm, as it corresponds to the volume condition we discussed in Chapter . This value may seem important, but the standard perturbations for an 1 adversary are usually much larger than those for an 2 or ∞ adversary -see [ ] for more details. Figures . and . show the standard accuracy and the minimum level of accuracy under attack of our new randomized network for multiple levels of injected noise. As in the Gaussian case, the precision decreases as the noise intensity grows. In addition, the theoretical trade-o between precision and robustness appears with respect to the noise intensity. We achieve high precision guarantees against small 1 perturbations, but when the perturbation is greater than 0.2, the guarantees decrease.

Remark .

The above theoretical limits only draw the bounds of Theorem . Indeed, we have not demonstrated that Laplace pre-processing gives robustness for the total variation yet. We will have to study it in future works to improve the theoretical worst case accuracy.

Table . shows that in practice, Laplace pre-processing achieves higher accuracy under attack than the theoretical bounds against 1 and ∞ adversaries. It compares the precision and accuracy under attack of randomized networks with Laplace preprocessing for di erent standard deviations. As in the Gaussian case, we found out that randomized defenses can be competitive given the intensity of the noise injected in the network.

. Lessons learned and future works

In this chapter, we presented simple schemes for building robust randomized classi ers. Based on the links we have established with the privacy preserving literature, we show that Gaussian noise injection can provide principled robustness against 2 adversarial attacks. Then, we used Gaussian noise injection with advanced neural network architectures to build robust and accurate models and supported our theoretical claims with a set of experiments on CIFAR 10 and CIFAR 100.

We achieve both good standard accuracy and state-of-the-art robustness. This responds to Q and Q from a practical point of view.

We can build randomized classi ers that are robust for both the total variation distance and the Renyi divergence.

Finally, we extended our analysis to take into account the noise injection from an exponential family. This allows us to build a principled defense against 1 adversaries based on Laplace noise injection. The practical schemes we developed could be improved in several ways. Among them, we list below some possible approaches.

Future work : widen the scope of adversaries

So far, we have identi ed Gaussian noise injection to defend against 2 attacks, and we have extended our study to 1 adversaries. But Lemma is quite general and could lead us to study other noises for di erent p adversaries. The question whether we can build noise injection schemes to defend against ∞ adversaries also remains open. To this end, we could use the fundamental link that our framework shares with randomized smoothing to study noises that proved useful for this defense. In particular, Yang et al. [ ] studied new classes of noise by using the Wul Crystals theory. This could open some interesting leads for more sophisticated noise injection mechanisms.

Future work : injecting noise anywhere in the network

In the particular case of neural network, we can decompose the deterministic hypothesis into successive compositions of functions h(x)

:= h (N ) • • • • • h (1) (x).
Thus, from a theoretical point of view, the data-processing inequality allows us to inject noise at any stage h (i) of the network and we would obtain results similar to those of this chapter. Nevertheless, noise injection only works if the maximum perturbation that the adversary can produce is limited, so the network should have a speci c design for the scheme to be applicable. The design architectures that allow for noise injection in the networke.g. networks with very small Lipschitz constant -rather than directly on the image would give a very interesting new perspective on the schemes we have just designed.

Future work : establishing deeper connections with di erential privacy

The link we have established with di erential privacy is fundamental, and we are far from having studied all its aspects. For example, we could design much more sophisticated random schemes based on this link, for example by using the exponential mechanism, or di erentially private voting procedures[ ]. Di erential privacy is also known to have very interesting properties for generalization based on stability theory [ ]. Thus, we could adapt previous results to improve the analysis we presented in Chapters and .

Conclusion & open problems

. Summary of the results

In this thesis, we studied the problem of adversarial classi cation from di erent angles, using a series of theoretical and practical tools. We have tried to analyze the problem using both a high level and a more precise analysis. Overall, our work advocates for the development of a probabilistic viewpoint on adversarial examples is a principled way to better understand and to build new useful theories. We can summarize our ndings as follows.

. We rst presented the problem as an in nite zero-sum game, and analyzed the fundamental nature of the game under di erent types of regularization using game theory. This analysis gave us a better understanding of the current analytical framework used in the adversarial examples community, and led us to argue for randomization as a principled defense against adversarial attacks.

. We then studied in more detail the key properties that random defenses should observe in order to build classi ers that are robust while maintaining high standard accuracy. To this end, we developed new approaches to study the robustness of randomized classi ers using information theory, probability theory and statistical learning theory. We identi ed su cient conditions for randomized algorithms to be robust and we studied the generalization property of these classi ers.

. Finally, we developed practical schemes for designing robust random classi ers using information theory and lessons learned from the privacy literature. This shows that we can build robust random classi ers based on state-of-the-art neural network architectures, and paves the way to exciting future works, both in theory and practice.

We hope that our analysis helped the community move forward and brought new and interesting perspectives on the di cult problem which is adversarial classi cation. The eld is still young and many research directions are still open. Throughout the manuscript, we have discussed future works that correspond -more or less -to direct improvements of our results. But here, we would like to take the time to present some more challenging open problems that would require more investment in terms of time and resources.

. Open problem : Revisiting the adversarial framework

Back to adversarial classi cation, the community studies the Problem ( . ) de ned as ) As we discussed in this work, from a functional point of view, the same problem writes ) This is the main focus of the literature, and the current analysis tends to show that the inf problem cannot have a good solution. Empirical evidence support these conclusions [ , ]. Nevertheless, in chapter , we have shown that the conclusions we draw about the nature of adversarial classi cation can change as soon as we modify the problem, even very slightly. This raises the following question.

inf h∈H E (x,y)∼D sup τ s.t. τ p ≤αp L(h(x + τ ), y) . ( .
inf h∈H sup ψ∈F X |αp E (x,y)∼D [L(h(ψ(x)), y)] . ( .
Remark . Note that even advanced methods based on randomization such as the one presented in chapter , or randomized smoothing achieve an accuracy under attack slightly above 0.5, which is not enough to consider classifiers as ultimately robust.

Is the problem of classi cation under adversarial perturbation ill-posed?

By ill-posed, we mean that the problem is not modeling a real threat scenario. We believe that the mathematical convenience of the current formulation has led researchers to study an oversimpli ed problem in which the opponent is unrealistically strong. This idea is shared by recent literature [ , ]. We therefore need to rethink the mathematical framework to make it more representative of real threat scenarios.

In Chapter , we rst pointed out that adversaries who can attack all points in the distribution are unrealistic and presented simple ways to mitigate this concern. In addition, we could also ask whether the better way of evaluating the performance of an attack is by computing the expectation over attacking all points. If we come back to the example of the self-driving car, an adversary who wants to trigger an accident may only want to change the decision on a very limited number of points and not care about the others. Similarly, the classi er may have di erent priorities on the points it has to defend. If we let L def and L adv encode the di erent policies of the defender and the adversary regarding the points, the problem now writes

     sup ψ∈F X |αp E (x,y)∼D L adv (h(ψ(x)), y) , for a given hypothesis h.
inf h∈H E (x,y)∼D L def (h(ψ(x)), y) , for a given adversary ψ.

( . )

From the game theoretical standpoint, we are now studying an asymmetrical and non-zero-sum game, which leads to very interesting and much more sophisticated designs. Wondering whether the model is ill-posed naturally leads to the following question.

If we change the mathematical framework, would existing ndings and insights still hold -at least to some extent?

As we saw in Chapter , a simple regularization can fundamentally change the nature of the game. Therefore, most of the previous conclusions may not be valid when we change the whole game design. In any case, studying new frameworks would allow us to assess whether existing conclusions are based solely on the over-strength of the adversary or whether they encompass some form of generality. In both cases, since the modi cations will be aimed at limiting the adversary's strength, it would allow us to better understand the actual defense capabilities that we may have when faced with adversarial examples.

. Open problem : Rethinking learning theory

Recall that most of the literature on learning theory focuses on demonstrating the convergence of the empirical risk to the theoretical risk using the uniform law of large numbers and some capacity control over the complexity of the hypothesis class. The goal is then to nd classes of models that are large enough for the ERM to have a small value, and small enough for us to get a good generalization gap. According to this interpretation -see Figure . on the left -the common way of thinking is that models with zero training error over-t samples, leading to poor test time accuracy. However, recent works have questioned the application of this point of view to modern machine learning models such as neural networks. For example, Zangh et al. [ ] have shown that we can learn a deep network for image classi cation on CIFAR -10 which has a training accuracy of 1.0 and still gives more than 0.85 test accuracy. This means that the model may either not over-t signi cantly or even not over-t at all. Returning to the classic form of a bound in learning theory, when the training error is zero, we get ) where R opt is the risk of the Bayes optimal classi er, and C(n) is a measure of complexity for the hypothesis class that may or may not depend on n. When R opt = 0 we can often show that to be optimal -which is never the case for the bounds on neural networks. As a result, the ideas of classical learning theory may not apply to deep learning frameworks, meaning that the analysis should not be based on the uniform law of large numbers or capacity control. Remark . Note that, most of the time, we will have R opt > 0 as the support of the conditional distributions {µ k } k∈ [K] are not likely to be disjoint.

R opt ≤ E (x,y)∼D [L(h(x), y)] ≤ O C(n) n , ( .
We nd that the ERM works quite well in practice, which is why researchers have begun to question capacity control. Speci cally, the following question arises.

How does the generalization of modern machine learning models depends on their complexity?

A partial answer to this question comes from an observation that is based on the extension of the study beyond the over tting regime for several machine learning models including neural networks [ , ]. When we arbitrarily increase the complexity of the model, we nd that after over tting the training samples, the theoretical risk of the model begins to decrease again. This phenomenon is called "double descent". Note that after over tting, all models have a zero training error, but the larger the model, the lower the theoretical risk. This is a very surprising phenomenon that has been observed on many models of advanced neural networks. From a theoretical point of view, the phenomenon has been identi ed and analyzed for linear models which indicates that the theory behind neural networks should also be revisited. Coming back to the main objective of this manuscript, we could also ask the following question.

Would this paradigm shift allow us to better understand or avoid adversarial examples?

An interesting way to start answering this question is to examine the k-nearest neighbor model, as suggested by Belkin et al. [ ]. This is a classical smoothing technique for which we can directly relate the expected loss of the algorithm to the Bayes optimal classi er. For example, Cover and Hard [ ] have shown that we can bound the model error as follows.

R opt ≤ E (x,y)∼D [L(h(x), y)] ≤ R opt 2 - KR opt K -1 . ( . )
Since the guarantees of this technique depend neither on the complexity of the model nor on the uniform law of large numbers, it is a good starting point for the study of a new formalism.

Regarding adversarial examples, it should be noted that some classi cation methods that do not over-t, such as the k nearest neighbor model, have proven robust against some forms of adver then adversarial examples become unavoidable, as it seems to be the case for neural networks. This suggests that the adversarial example phenomenon is closely related to the double-descent regime of deep neural networks and thus to over-tting.

Remark . As we already discussed in Chapter Goodfellow et al.

[ ] disproved the hypothesis of the model over-fitting the dataset by presenting transferable attacks. But here by over-fitting we mean a much more profound and convoluted phenomenon that occurs when the complexity of the model goes to infinity.

. Open problem : Unifying trustworthy machine learning In this manuscript, we have highlighted the theoretical links between di erential privacy and robustness to adversarial examples using information theory. But di erential privacy also has a formal framework that can be linked to other areas such as fairness in machine learning, as pointed out by Dwork et al. [ ]. Furthermore, robustness to adversarial examples has been linked to explainability in machine learning by Ignatiev et al. [ ] using a formal logic viewpoint. Hence, by transitivity, explainability and di erential privacy are related notions. It would be interesting to study whether we could establish a direct line between these two concepts using information theory. Di erential privacy seems to be a key concept that the community should continue using to build bridges with other areas of trustworthy machine learning.

In particular, the robustness to train time adversariesa.k.a. poisoning attacks [ , ] -could also be connected to di erential privacy since both notions are based on stability theory [ ]. Figure . summarizes the links between the areas we have just discussed -plain lines -and the links that we believe could be useful to the community -dotted lines. We strongly believe that di erential privacy and information theory can play a key role in building a uni ed view on the di erent domains of trustworthy machine learning. Let us consider a classi er c ∞ that is robust against adversarial examples with α ∞ bounded perturbation for the ∞ norm. It guarantees that for any input-output pair (x, y) ∼ D such that c(x) = y and for any α ∞ bounded perturbation τ we have c ∞ (x + τ ) = c ∞ (x). We now wonder what are the performances of this classi er against 2 adversaries with maximal perturbation α 2 . Figure A. -on the left, shows the balls with the respective radii α 2 and α ∞ . If we build an 2 adversarial example which is at the intersection of the two balls, it will not work on c ∞ . On the other hand, if we manage to select an example outside the ∞ ball, c ∞ has no more guarantee.

Thus, to characterize the probability that an 2 perturbation fools an c ∞ in the general casethat is, for any dimension d -we measure the ratio between the volume of the intersection of the ball ∞ of radius α ∞ and the ball 2 of radius α 2 . As shown in the Theorem , this ratio depends on the dimension of the problem d and quickly converges to zero when d increases. It is therefore unlikely that a defense mechanism that protects against ∞ adversaries will be e ective against 2 attacks.

Theorem . Let us consider

d ∈ N, x ∈ R d and B d|2 (α 2 ) -resp. B d|∞ (α ∞ ) -the 2 ball with radius α 2 -resp. the ∞ ball with radius α ∞ -with center x. If for all d, we select α 2 and α ∞ such that Vol B d|2 (α 2 ) = Vol B d|∞ (α ∞ ) . Then the following holds, Vol B d|2 (α 2 ) ∩ B d|∞ (α ∞ ) Vol B d|∞ (α ∞ ) -→ d→∞ 0.
Proof. Without loss of generality, let us x α ∞ = 1 and x = 0. Then we have

Vol B d|2 (α 2 ) = 2Γ 1 2 + 1 α 2 d Γ d 2 + 1 and Vol B d|∞ (1) = 2 d .
Then, to have balls with the same volumes, for any d we set

α 2 = 2 √ π Γ d 2 + 1 1/d
where Γ is the gamma function. Since α 2 is a function of d, in the remaining we use the notation α 2 (d). If we denote U, the uniform distribution on B d|∞ (1) we get

Vol(B d|2 (r 2 (d)) ∩ B d|∞ (1)) Vol(B d|∞ (1)) = P z∼U z ∈ B d|2 (r 2 (d)) = P z∼U d i=1 z 2 i ≤ α 2 (d) 2 = P z∼U d i=1 z 2 i -E z∼U d i=1 z 2 i ≤ α 2 (d) 2 -E z∼U d i=1 z 2 i .
Furthermore, when d is su ciently large we get

α 2 (d) 2 -E z∼U d i=1 z 2 i = α 2 (d) 2 - d 3 < 0.
Using the Hoe ding inequality we get

Vol(B d|2 (r 2 (d)) ∩ B d|∞ (1)) Vol(B d|∞ (1)) ≤ exp - α 2 (d) 2 -d 3 2 d .
Finally, thanks to Stirling's formula, we have

α 2 (d) ∼ d→∞ 2 πe d 1/2 .
Then the right hand term converges towards 0 when d goes to ∞ which concludes the proof.

Theorem indicates that, when d is large enough, 2 based perturbations have a null probability of being also in the ∞ ball of the same volume. Therefore, when the dimension of the problem is su ciently large, a defense mechanism o ering complete protection against ∞ adversaries is not guaranteed to o er any protection against 2 attacks . This result goes against two-dimensional intuition. Indeed, if we consider a two-dimensional problem, the ∞ and 2 balls overlap signi cantly -as shown on the left of gure A. -and the probability of sampling at the intersection of the two balls is about 0.98. However, this probability is close to zero for any realistic image setting, even for very simple image data sets such as MNIST [ ].

Theorem can easily be extended to any two balls with di erent norms. But we restrict to the case of ∞ and 2 norms as we mainly discussed these norms until now.

A. No free lunch for adversarial defenses in practice

Our theoretical analysis shows that if adversarial examples were uniformly distributed in a high dimensional space, then any mechanism that only defends perfectly against the ∞ adversaries has a zero probability to be robust to 2 adversarial examples. Although existing defense mechanisms do not necessarily assume such a distribution, targeted defenses only work marginally when attacked with di erent norms. Before analyzing the results, let us brie y present some details of the experimental protocol.

Experimental protocol

All experiments are conducted on CIFAR-10 with the Wide-Resnet -architecture. We use the training procedure and the hyper-parameters described in the original paper by [ ]. To train a neural network with adversarial training, we still use the same hyper-parameters, and generate adversarial examples during training using either PGD-∞ or PGD-2 adversary with 10 iterations.

To compare the empirical performances of our method with adversarial training, we consider two p adversaries with thresholds corresponding to CIFAR-10.

• An ∞ adversary with perturbation bounded by 0.031. To model this adversary we use the PGD attack with t max = 20 iterations.

• An 2 adversary with perturbation bounded by 0.8. To model this adversary we use the PGD attack with t max = 20 iterations.

• Another 2 adversary with perturbation bounded by 0.8. To model this adversary we use the C&W attack with 60 iterations, a learning rate equal to 0.01, 9 binary search steps, and an initial constant of κ = 0.001.

Remark .

Our analysis is mainly focusing on PGD attacks for both the ∞ and the 2 norms. However, these attacks have a very strict geometry . This is why, to present a deeper analysis of the behavior of adversarial attacks and defenses, we also present a set of experiments that use C&W attack.

Due to the projection operator, all PGD attacks saturate the constraint, which makes them all lie in a very small part of the ball.

Results

Table

α = α ∞ α = α ∞ × √ d 0 0.5 0.1 •10 4 α = α ∞ α = α ∞ × √ d 0 0.5 0.1 •10 4

A. Related works and perspective to defend against multiple perturbations

Defenses against adversarial examples, such as adversarial training, are usually tailored to a single type of perturbation. As we have just discussed, defending against a single perturbation o ers no guarantee and can even sometimes increase the vulnerability of the model to new attacks. Hence the community is trying to develop e ective defenses against multiple perturbations. This question has been studied in several recent works [ , ]. Tramer et al. [ ] rst proposed to address this problem by mixing adversarial training with attacks for di erent norms in order to defend against multiple models of perturbation. To design the loss function, the authors proposed two simple aggregation rules. The rst averages the attacks and the second selects the perturbation that maximizes the loss over the di erent threat models. While this approach can achieve varying degrees of robustness for the adversarial perturbation models considered, in practice it is quite di cult to adjust and often achieves varying degrees of robustness to individual perturbations. This results in a sub-optimal worst-case loss when we consider the union of threat models -which is actually our main purpose. To address this shortcoming, Maini [ ] has further re ned the PGD-based procedure to simultaneously incorporate all model threats into a single attack called MDS -Multi Steepest Descent. This technique achieves about the same level of robustness as adversarial training -against one model threat -when it faces any of the threats it has learned on. Much work remains to be done on defense against multi-model threats, which opens interesting theoretical and practical perspectives. In particular, it would be interesting to study cases where we could design provable defenses against multiple perturbations without compromising the accuracy of the model.

As mentioned in Chapter , the C&W attack is not bounded at rst since the Lagragian relaxation does not have a strong constraint. Hence, the beige zone represents the set of examples that will be clipped at the end of the procedure.

. Prune the tree according to some criteria in order to obtain a forest. Every connected component in this forest characterizes a cluster -Figure B. right.

Remark . Note that we will always assume here that the graph is connected, but similar results hold when we have more than one connected component.

MST-based clustering methods, however e ective, generally lack appropriate formal analysis. Our rst contribution lls this gap by providing a theoretical framework for MST-based clustering. More precisely, our contribution is twofold: ) we present a theoretical framework motivating MST-based clustering methods, where the notion of clustering is based on the concept of minimum path distance, ) we provide theoretical guarantees for DBMSTC [ ] algorithm, an MST-based clustering algorithm we previously worked on.

Analytical framework for MST-based clustering

In order to analyze the e ectiveness of an MST-based method, we must rst introduce a notion of clustering that we want to comply with. Since the graph is simple, it is possible to de ne the minimum path distance between two nodes, which makes our de nition of clustering more explicit.

De nition (Minimum path distance).

Let us consider G = (V, E, w) and u, v ∈ V . The minimum path distance between u and v is dist(u, v) = min { min

v∈C 1 dist(z, v) } ⊂ C 2 .
Remark . Assuming that a cluster is built of at least 3 points makes sense since singletons or groups of 2 nodes can be legitimately considered as noise. For simplicity of the proofs, the following theorems hold in the case where noise is neglected. However, they are still valid in the setting where noise is considered as singletons -with each singleton representing a generalized notion of cluster.

In particular, this de nition states that a cluster C can only be de ned if for any vertex u ∈ C, the closest vertex to u in G must be in C.

MST-based clustering with guarrantees

Let us brie y present this algorithm -refer to Figure B. for a basic description. Given an MST T , DBMSTC consists of successive cuts on T . At each iteration, an edge is cut if a certain criterion, called Density-Based Validity Index of a Clustering partition -DBCVI -is improved. This edge is greedily chosen to locally maximize the DBCVI at each step. When no improvement of the DBCVI can be made, the algorithm stops. The notion of DBCVI is constructive. In short, it compares the maximum edge weight inside the cluster with the minimum weight of the edges coming out of the cluster. When this di erence is high; the DBCVI is also high and vice versa. For more details on this notion, we refer the reader to [ ] and [ ].

Then -under mild assumption on the weight function w -we can guarantee that DBMSTC outputs a set of clusters that comply with De nition . In a nutshell, this condition says that the edge separating each cluster must have a weight that is su ciently distinct from the edges within the cluster. This motivates the following de nition.

De nition (Homogeneous separability condition).

Let us consider a graph G = (V, E, w), s ∈ E and T a tree of G with a set of edges E(T ). T is said to be homogeneously separable by s if the following holds, The latter condition is local and depends on a tree in G. Let us suppose that there exists K clusters in G -(C 1 , . . . , C K ) -characterized by subtrees (T 1 , . . . , T K ). Then if the subtrees are homogeneously separable by a set of edges (s 1 , ..., s K-1 ), then the graph is called homogeneous. This is simply a condition for clusters to be su ciently separated one from another in G. When the graph is homogeneous, we can show that DBMST recovers correctly the K clusters. We now have an algorithm in an appropriate analytical framework, which allows us to evaluate when it will correctly nd the underlying structure of the graph. Nevertheless, it is essential that the data representation we use protects the private characteristics contained in the graph. Let us consider an application in which we want to identify groups of web pages that have similar content, i.e. web pages with a similar audience. In this case, the vertices represent the web sites. The link between two vertices represents the fact that some users visit both of them. The edge weights re ect the number of common users and therefore carry sensitive information about individuals. When analyzing the graph data, no personal user's browsing behavior should be violated; i.e. browsing from one page to another should remain private. As already mentioned in the body of the manuscript, the gold standard for privacy data analysis is di erential privacy [ ]. In the following, we discuss how di erential privacy can be applied to graph based clustering algorithms.

Theorem

B. Di erentially private node clustering in a graph

Even though di erential privacy has been extensively investigated, learning from graph databases under di erential privacy remains challenging. Mir et al. [ ] Then several de nitions of di erential privacy on graphs appeared. Among them, the main ones are edge-di erential privacy [ ], and node-di erential privacy [ ]. Conceived for the protection of the graph topology, these de nitions are not suitable for applications to network analysis where the structure is static and the private information on the users are carried by the edge weights. Sealfon [ ] addressed this issue by providing a new formal framework for the private analysis of weighted graphs where the graph topology G = (V, E) is public and the private information is contained in the weight function w : E → R. We recently studied a slightly di erent version of the de nition that relies on the following notion of closeness between weight functions. α represents the sensitivity of the weight function and should be chosen according to the application at hand. The de nition of weight-di erential privacy for a graph algorithm can then write as follows.

De nition . For any graph topology G = (V, E), let A be a randomized algorithm that takes as input a weight function w. A is called -di erentially private on G = (V, E) if for all pairs of neighboring weight functions w ∼ w , and for any possible output o, one has

P[A(w) = o] ≤ e P A(w ) = o .
When it is -di erentially private on every graph topology in a class C, A is called -di erentially private on C.

In the remaining, we will be interested in this de nition of di erential privacy that we call weight-di erential privacy.

Node clustering in a graph under di erential privacy

Di erentially private clustering for unstructured datasets has been rst discussed in [ ]. This work introduced the rst method for di erentially private clustering based on the k-means algorithm. Since then most of the work in the eld focused on adaptation of this method [ , , ]. The main drawback of this work is that it is not able to deal with arbitrary-shaped clusters. This issue has been recently investigated in [ ] and [ ]. They proposed two new methods to nd arbitrary-shaped clusters in unstructured datasets respectively based on density clustering and wavelet decomposition. Even though both of them produce non-convex clusters, they only deal with unstructured datasets and thus are not applicable to node clustering in a graph. Graph clustering has already been investigated in a topology-based privacy framework [ , ], however, these works do not consider weight-di erential privacy. Hereafter, we present a new generic method for node clustering in a graph under this privacy notion using MST-based clustering methods. Recall that an MST-based clustering algorithm ) builds a minimum spanning tree and ) prunes it until getting a forest that represents the clusters. To make this procedure private, we choose to compute step ) under di erential privacy constraint. Then thanks to the post-processing inequality-see Theorem , we extend the obtained privacy guarantees to step

). Hence, we rst want to design a di erentially private minimum spanning tree algorithm. Sealfon [ ] addressed this issue by providing and analyzing an algorithm that releases an approximate minimum spanning tree under weight-di erential privacy. The error of this seminal algorithm in terms of weight approximation is O(|V | log |E|) for xed privacy parameters and its time complexity is O(|E| + |V | log |V |). Accordingly, this method can be highly inaccurate when the graph is large, which is common in machine learning applications. A way to improve the algorithm's performances in the context of graph learning under di erential privacy is to construct an iterative method which focuses on considering a local condition on the weight function in the process. This idea has been rst proposed by Gupta et al. [ ], and extensively investigated in the framework of di erentially private submodular optimization by Mitrovic et al. in [ ]. In the latter, the issue of releasing a minimum spanning tree under weightdi erential privacy is not directly investigated. Yet one could derive from the study of monotone submodular maximization a private version of Kruskal algorithm with an improved approximation error of O |V | 2 /|E| log |V | . Even though the approximation error is satisfying, Kruskal algorithm in the submodular framework has an algorithmic complexity of O(|E||V |) which is prohibitive when dealing with large and dense graphs.

I: G = (V, E, w) Pick v ∈ V at random, S V ← {v}, S E ← ∅ . S V = V ?
Under a similar privacy setting we recently produced an algorithm to release the topology of a tree under di erential privacy. We designed a Prim-like algorithm -called PAMST -to privately release the topology of an almost minimum spanning tree thanks to an iterative use of the well known scheme from the di erential privacy literature called the Exponential mechanism [ ]. The Exponential mechanism represents a way of privately answering arbitrary range of queries. It is de ned according to a utility function which aims at providing some preorder on the possible outputs of the algorithm according to the order in R. In PAMST we use it to select an edge at random from a subset of E. The algorithm is summarized in Figure B. . PAMST takes as an input a weighted graph. It outputs the spanning tree which weight is almost minimal, according to the weight function. To do so, the algorithm starts at an arbitrarily chosen vertex and chooses one of its incident edges according to the Exponential mechanism. Then it updates the set of edges S E and adds the second node belonging to this edge to the current node set S V . As long as the node set does not contain all the vertices, PAMST continues to choose at each This error is computed according to the di erence between the underlying weight of the tree topology -sum of the edges weights -and the weights of the minimum spanning tree, using the initial weight function.

For more details on Prim algorithm, the interested reader can refer to [ ].

∈ {1.0, 0.7}, it appears that the clustering result is slightly a ected. More precisely, in Figures B. and B. -(c) and (d) -the two main clusters are recovered. Some points however are isolated as singletons. This is due to the randomization involved in determining the edge weights for the topology returned by PAMST. Furthermore, as an expected e ect of di erential privacy, when decreases, the clustering quality deteriorates, as DBMSTC is sensitive to severe changes in the MST -see Figure B. and B. (e). In this appendix, we present some of our most recent work addressing the issue of collaborative deep learning with privacy constraints. In Section C. we present our problem setting and the new framework we designed. More precisely we aim to devise a framework that takes into account threat models that are beyond the scope of di erential privacy. Then, we present some related works on deep learning with privacy in Section C. .

C. A new framework beyond di erential privacy

As we have already discussed, the large adoption of machine learning in several domains, including critical ones, raises a number of concerns on the security and privacy of the tools we develop. For now, we mainly discussed the notion of di erential privacy, but here we try to go beyond this de nition of privacy preserving machine learning. Toy Example. An example of scenario from the field of cybersecurity where we need to consider a more sophisticated threat model is as follows. Several actors hold a database of cybersecurity incident signatures, that have occurred on their customer networks. Each actor can build a malware detection model on its own, but building a model that benefits from a larger set of such signatures would lead to improved detection capabilities. In general, these databases are highly-sensitive and highly-valuable; as such, they cannot be disclosed. In such a setting, the data owners wish to collaboratively transfer the knowledge they have into a global model while preserving the confidentiality of their learning sets.

In the context of collaborative learning, several recent works [ , , , , , ] focused on using di erential privacy to build privacy preserving deep learning models. However, these tech-C Secure and private deep learning with encrypted aggregation operator niques rely on a "trusted" aggregation server that gathers non-private information before processing some sanitizing scheme. In real-life scenarios the absence of such a server will jeopardize the privacy and security of the overall learning procedure. Hereafter, we present a new approach called SPEED which obtains di erential privacy guarantees without the need for a trusted aggregation server. Building upon di erentially private decentralized semi-supervised learning [ , ], we introduce homomorphically encrypted operations to extend the set of threats considered so far. The procedure is summarized in Figure C. . Our approach is supported by theoretical guarantees in terms of di erential privacy and provably-secure cryptography. In a nutshell, SPEED works as follows.

• First, every data owner builds a local modela.k.a. teacher model -using its own database.

• Then, given a new unlabeled dataset, the teacher models output encrypted predictions and send them to the server which computes a di erentially private aggregation in the encrypted domain to obtain an encrypted labeled dataset.

• From this new dataset, a collaborative modela.k.a. student model -is learned in a semisupervised manner.

C. Related works on private deep learning

The literature on private training of deep neural networks essentially uses either di erential privacy, secure multiparty computing or homomorphic encryption -see e.g. [ ]. Hereafter, we on di erential privacy and homomorphic encryption.

Di erential privacy and deep learning

Through the lens of di erential privacy, we can design machine learning algorithms that are protective of the database private attributes. For deep learning tasks, a widely used technique is to use a noisy stochastic gradient descent [ , ] during the learning procedure, and to keep track of the privacy budget using the moments accountant scheme [ ]. Even though some of these models can be satisfying when using a centralized database, none of them meet our problem requirements since it forces all the data owners to merge their databases.

To address these concerns some recent works considered to use di erential privacy in decentralized settings close to the one we consider [ , , , , , ]. Among them, the most e cient technique in terms of accuracy and privacy guarantees is Private Aggregation of Teacher Ensembles (PATE) rst presented in [ ] and re ned in [ ]. PATE uses private semi-supervised learning to privately transfer to the student model the knowledge of the ensemble of teachers by using a di erentially private aggregation method. This approach considers a setting very close to ours with the notable di erence that the aggregator is trusted. Hence applying PATE in our scenario makes the teacher models vulnerable. To tackle this issue, our work builds upon PATE idea, and adds a layer of homomorphic encryption in order for the overall learning framework to be kept secure.

Homomorphic Encryption -HE

HE allows to perform computations over encrypted data. In particular, this can be used so that the model can perform both training and prediction without handling cleartext data. In terms of learning, the naive approach would be to have the training sets homomorphically encrypted, sent to a server for training to be done in the encrypted domain and the resulting -encrypted -model be sent back to the participants for decryption. However, putting aside many subtleties, even by deploying all the arsenal available in the HE practitioner toolbox -batching, transciphering, etc.

-this would be impractical as standard learning is both computation and know-how intensive and HE operations are intrinsically costly. As a consequence, there are only very few works that capitalize on HE for private training [ , ] and inference [ , ] of machine learning tasks. Moreover, since some attacks can be performed in a black-box setting, the system is still vulnerable to attacks from the end user who has access to the decryption key. In our framework, we do not use HE directly to build the model, we use it as a mean for the aggregation to be kept private. That way, we are protected against potential threats from the aggregator -which does not have the decryption key, and we keep a manageable computational overhead.

Private aggregation

Several approaches have been considered to limit the need for a trusted aggregator when applying di erential privacy, for example by considering local di erential privacy [ , , ]. In practice it often results in applying too much noise, and maintaining utility can be di cult [ , ] especially for deep learning applications. In order to recover more accuracy while keeping privacy, some works combined decentralized noise distributiona.k.a. distributed di erential privacy [ ] -and encryption schemes [ , , , ] in the context of aggregation of distributed timeseries. Our work contributes to this line of research. Our framework, which combines distributed DP and HE, is the rst one to be su ciently e cient to investigate deep learning applications.

Les modèles d'apprentissage automatique font partie de notre vie quotidienne et leurs faiblesses en termes de sécurité peuvent être utilisées pour nous nuire directement ou indirectement. Il est donc crucial de pouvoir prendre en compte et de traiter toute nouvelle vulnérabilité. De plus, le cadre juridique en Europe évolue, ce qui oblige les praticiens -des secteurs public et privé -à s'adapter rapidement à ces nouvelles préoccupations. Dans cette annexe, nous présentons d'abord le contexte dans lequel l'idée de cette thèse est née et nos principales motivations dans la Section D. . Ensuite, nous présentons l'un des problèmes sur lequel nous nous sommes concentrés pendant ce travail de thèse: La classification supervisée sous perturbations adverses, ainsi que quelques résultats de l'état de l'art dans la Section D. . Nous résumons certaines de nos contributions au domaine dans la Section D. . Pour chacune de nos contributions, nous résumons succinctement nos résultats et présentons quelques pistes d'améliorations. En n, nous listons nos productions de matériel scienti que et pédagogique dans la Section D. , et nous présentons un problème ouvert pour la communauté en Section D. . L'impressionnante e cacité des technologies basées sur ce type de modèles les a rendu omniprésents tant dans l'industrie que dans certains secteurs publics. Cependant, des études récentes ont identi é plusieurs défauts majeurs des algorithmes d'intelligence arti ciel tels que la fuite d'informations [ ] ou la vulnérabilité aux perturbations adverses [ ]. Ces faiblesses soulèvent de nombreuses questions sur la responsabilité juridique des fournisseurs des modèles et amènent les praticiens à réévaluer la con ance qu'ils placent dans les systèmes qu'ils utilisent.

D. Contexte et motivations

D. . Gestion des questions relatives à la vie privée: le Règlement Général sur la Protection des Données

La protection des données personnelles contre de potentielles fuites pendant un traitement statistique de celles-ci n'est pas exactement une nouvelle préoccupation; les fondements théoriques sur l'analyse de données à caractère sensible ont été largement établis dans les années les gouvernements sont tenus de concevoir des modèles pour lesquelles les mécanismes de protection contre la fuite des données soient plus élaborées. Ces nouvelles obligations, associées aux préoccupations déjà existantes des utilisateurs concernant leurs données personnelles, ont fait de la question de protection des données l'une des priorités de la communauté informatique. En conséquence, plusieurs dé nitions ont été introduites pour caractériser les algorithmes de protection de données dans le contexte de l'apprentissage supervisé et de l'analyse de données [ ]. Parmi elles, la con dentialité di érentielle [ ] est devenue l'un des standards en permettant de fournir une dé nition forte et pratique de la protection de données. L'idée de cette dé nition est que les informations d'une personne de la base de données sont protégées si le résultat de toute analyse donne un résultat aussi probable, que la personne fasse ou non parti de l'ensemble des données à disposition de l'algorithme.

Plus formellement, on dit qu'un algorithme est di érentiellement con dentiel si, compte tenu de deux bases de données similaires, il produit des résultats statistiquement indissociables. Cette dé nition de protection de données a été largement étudiée dans de nombreux cadres et applications -voir [ ] pour un ouvrage de référence. Dans l'ensemble, l'apprentissage supervisé sous contrainte de protection des données est désormais un concept connu et intégré dans le paysage de la recherche en informatique. Il repose sur un cadre juridique approprié, et des solutions techniques telles que la con dentialité di érentielle sont systématiquement mises en oeuvre par les grandes entreprises -par exemple Google [ , ] -et les entités publiques -comme le U.S. Census Bureau [ ]. La bataille pour la protection des données utilisateurs n'est pas encore terminée, mais des e orts importants ont été déployés tant par les praticiens que par les chercheurs pour répondre aux exigences de notre époque en matière de protection de la vie privée. Bien qu'il n'y ait pas encore de consensus clair sur la dé nition de l'interprétabilité ou de la conance dans les modèles d'intelligence arti cielle [ ], des thèmes récurrents tels que les biais algorithmiques [ ] ou la vulnérabilité aux perturbations [ , ] sont souvent cités en exemple. Ces nouvelles préoccupations, ainsi que les questions de protection de données mentionnées plus tôt, sont parfois regroupées sous le nom d'Intelligence Artificielle de Confiance, concept qui a récemment attiré beaucoup d'attention. En outre, le déploiement de modèles d'intelligence arti cielle dans les systèmes industriels et commerciaux à fort impact, ainsi que les récents progrès juridiques en matière de droit à la protection et à l'explication encouragent l'intensi cation de la recherche dans ce nouveau domaine.

D. . Au-delà de la vie privée : interprétabilité, con ance et attaques adverses

Dans cette thèse, nous nous concentrons principalement sur la vulnérabilité des modèles aux perturbations adverses. Le terme de perturbation adverse -ou attaque adverse -désigne une perturbation soigneusement choisie et humainement imperceptible qui déclenche le dysfonctionnement d'un modèle. L'existence de ce type de faiblesse montre à quel point la communauté de l'apprentissage profond s'est éloignée de l'objectif initial de comprendre et reproduire la perception humaine. Pour mettre en évidence l'enjeu de sécurité que représentent les attaques adverses, nous prenons l'exemple des voitures autonomes. Récemment, les entreprises à la pointe des nouvelles technologies ont fait d'énormes investissements de recherche et de développement dans le domaine des voitures autonomes, c'est-à-dire des véhicules équipés d'un nombre considérable de caméras et de capteurs qui les aident à se déplacer avec peu ou pas d'intervention humaine. Une grande partie des informations recueillies par ces voitures sont traitées à l'aide de modèles d'apprentissage automatique embarqués. En particulier, les tâches de traitement d'images se font par le biais de réseaux de neurones profonds. Cependant, des travaux récents [ , , , ] ont démontré que ces mêmes systèmes peuvent être dupés par des modi cations marginales de panneaux de signalisation -par exemple en ajoutant des autocollants sur le panneau en question.

La Figure . illustre un contexte d'attaque où un adversaire a ajouté un tel autocollant sur un panneau de signalisation. Dans le premier schéma -en haut -la voiture analyse la version originale du panneau de signalisation, le reconnaît comme une limitation de vitesse et continue normalement. Dans le second schéma -en bas -la voiture rouge analyse une version modi ée du panneau de signalisation et le reconnaît comme un panneau "Stop" causant un accident avec la voiture bleue. Notez que dans ce cas, aucun humain n'aurait changé sa décision, mais la voiture le fait. Ce décalage manifeste entre la réponse humaine et la réponse du modèle peut conduire à d'innombrables problèmes de sécurité -ici par exemple un accident déclenché par une attaque sur un panneau de signalisation. Ce type de technologies est actuellement en cours de développement; il est donc crucial de s'adapter rapidement à la nouvelle menace que représente les attaques adverses, tant d'un point de vue technique que juridique.

D. Formalisation du/des problème(s) de classi cation

Dans cette section, nous commençons par faire quelques rappels sur le problème de classi cation dans le cadre standard -c'est-à-dire sans adversaire. Ensuite, nous présentons le problème de classi cation en présence d'un adversaire et identi ons les problèmes fondamentaux auxquels nous souhaitons apporter des réponses.

D. . Classi cation dans le cadre standard

Considérons le problème de classi cation supervisée avec un espace d'entrée X -des images -et un espace de sortie Y -des étiquettes décrivant les images. Pour simpli er, nous considérerons ici que Y = {1, . . . , K}, ce qui signi e que chaque étiquette est caractérisée par un entier compris entre 1 et K. L'objectif d'un algorithme d'apprentissage supervisé est de construire une fonction de prédiction c : X → Y -aussi appelée un classi eur -qui fait correspondre à toute image x ∈ X une étiquette y ∈ Y. Pour trouver c, l'algorithme d'apprentissage a accès à un ensemble S de n couples entrée-sortie S := {(x  , y 1 ), . . . , (x n , y n )} -aussi appelé ensemble d'apprentissage. L'hypothèse principale qui sous-tend la théorie de la classi cation est qu'il existe une certaine distribution D qui décrit le lien entre les images et les étiquettes et dont sont tirées indépendamment les paires (x i , y i ).

Pour construire un classi eur, on dé nit en général une fonction h : X → R K appelée hypothèse, qui pour toute image x ∈ X va renvoyer un vecteur de scores h(x) := [h 1 (x), . . . , h K (x)] . Ensuite, la fonction de prédiction c donne l'étiquette avec le meilleur score pour h. Plus formellement, c s'écrit c(x) := argmax

k∈[K] h k (x).
Le problème revient donc à construire une fonction h qui décrit bien le lien entre les images et les étiquettes.

D. . Classi cation sous perturbations adverses

Étant données une hypothèse h ∈ H et une paire image-étiquette (x, y) ∼ D, le but d'un adversaire est de trouver une perturbation τ ∈ X telle que les a rmations suivantes soient véri ées.

. La perturbation doit être imperceptible pour un humain. Cela signi e qu'un humain ne peut pas distinguer visuellement l'image standard x de l'image adverse x+τ .

. La perturbation modi e su samment x pour que le classi eur fasse une erreur de classi cation. Plus formellement, l'adversaire recherche une perturbation τ ∈ X telle que c(x + τ ) = y.

Bien que la notion de modi cation imperceptible soit très naturelle pour un humain, elle est véritablement di cile à formaliser. Malgré ces di cultés, une condition su sante pour garantir que l'attaque restera non détectée est de contraindre la perturbation τ à avoir une petite norme p . Cela signi e que pour tout p ∈ [1, ∞], il existe un seuil α p > 0 pour lequel une perturbation τ est imperceptible dès lors que τ p ≤ α p . La littérature sur les attaques adverses dans le cadre de la classi cation d'images [ , ] utilise généralement une norme ∞ ou 2 pour dé nir l'imperceptibilité .

Les exemples adverses représentent une menace sérieuse pour la sécurité des modèles d'intelligence arti cielle. Il est donc primordial de re-formaliser le problème de minimisation du risque standard en intégrant l'adversaire dans le problème. L'objectif devient donc de minimiser le risque adverse -aussi appelé risque contradictoire, lorsque les manipulations sont limitées en norme p . Nous appelons ce nouveau problème la minimisation du risque adverse. Il s'écrit comme suit: À première vue -au regard de la littérature empirique sur les exemples adverses -la réponse semble être non. En e et, un grand nombre de travaux ont tenté de concevoir des modèles qui seraient moins vulnérables aux manipulations [ , , , , ] . ) En présence d'un adversaire, plusieurs problèmes majeurs apparaissent dans la minimisation du risque empirique. Nous présentons ci-dessous quelques pointeurs bibliographiques qui per-Il arrive aussi parfois que l'on utilise une norme 1 [ ] ou une semi-norme 0 [ ]. Notez que ces normes ont des comportements très di érents dans les espaces de grande dimension, d'où l'impact crucial qu'a le choix de p sur la réponse que l'on donne à Q et Q ci-dessous. Pour plus de détails, nous incitons le lecteur à se référer à la partie anglaise du manuscrit. mettent de mieux comprendre les di cultés et enjeux de la minimisation du risque empirique adverse. [ , , ] démontrant que la généralisation contradictoire dépend e ectivement de la dimension du problème. Ainsi, en termes de taille de l'échantillon, la problème de classi cation adverse est plus di cile que celui de la classi cation standard.

inf h∈H E (x,y)∼D sup τ ∈Bp(αp) L(h(x + τ ), y) , ( D
L(h(x i + τ ), y i ) . ( D
• Un autre axe de recherche étudie le problème du point de vue des contraintes de calcul. Bubeck et al. [ ] se sont récemment penchés sur cette question pour démontrer que même avec un ensemble d'apprentissage su samment large, il existe un ensemble de problèmes d'apprentissage pour lesquels l'apprentissage standard non robuste peut être e ectué ecacement, mais demande des capacités de calcul considérable dans le cadre adverse.

• En n, il ne su t pas toujours de trouver une solution qui minimise le risque adverse. Certains travaux récents [ , , , ] ont apporté des arguments théoriques établissant que construire un modèle avec un faible risque adverse peut conduire à une augmentation de son risque standard. Ainsi, trouver une bonne approximation pour le problème de classication adverse -Problème (D. ) -peut conduire à une mauvaise solution pour le problème standard -Problème (D. ).

Au vu de l'état de l'art que nous venons de discuter, on se pose également la question suivante. . Cette publication est accompagnée d'un ensemble de codes hébergé sur Github permettant de reproduire nos résultats expérimentaux.

• "Randomization matters, how to defend against strong adversarial attacks".

International Conference on Machine Learning (ICML)

. R. Pinot, R. Ettedgui, G. Rizk, Y. Chevaleyre, J. Atif.

• https://github.com/MILES-PSL/Randomization-matters-How-to-defend-against -strong-adversarial-attacks Ce travail ouvre un grand nombre de questions particulièrement intéressantes à la fois sur le plan théorique et pratique. Nous présentons ci-dessous quelques-unes des pistes potentielles.

Travail futur : L'équilibre dans le régime randomisé

Il reste à étudier si un équilibre existe dans le régime randomisé. Cette question est séduisante d'un point de vue théorique, et nécessite d'étudier l'espace des adversaires randomisés ce qui implique plus de technicités. L'étude de cet équilibre est également étroitement liée à celle de la valeur du jeu, ce qui serait intéressant pour obtenir des bornes min-max sur la précision sous attaque des classi eurs randomisés.

Travail futur : Étudier le saut de dualité

Pour le moment, nous avons montré qu'il n'y a pas d'équilibre de Nash Pure dans le jeu. Cela signi e que la dualité forte ne tient pas. Mais cela n'indique pas l'écart entre les valeurs du problème inf/sup et du problème sup/inf -aussi appelé le saut de dualité. L'évaluation de ce saut de dualité pourrait nous aider à construire une analyse plus ne de l'impact de la régularisation sur le jeu.

Travail futur : Boosted Adversarial Training, une défense certi ée ?

Bien que les résultats expérimentaux montrent que Boosted Adversarial Training est plus performant dans le cadre de la classi action sous attaques adverses, l'algorithme que nous présentons ne fournit pas de garanties en termes de précision certi ée. Comme l'a démontré la littérature sur les attaques et les défenses, de meilleures attaques existent toujours. C'est pourquoi, nous devons approfondir les aspects théoriques de notre procédure, a n de prouver la robustesse des classi eurs randomisés que nous concevons.

D. . Propriétés théoriques des classi eurs randomisés -Q & Q

Pour notre deuxième contribution, nous étudions les classi eurs randomisés à travers le prisme de la théorie de l'apprentissage et de la théorie de l'information. Par analogie avec le cas déterministe, nous dé nissons une notion de robustesse pour les classi eurs randomisés. Cette dé nition se résume à véri er que le classi eur satisfasse une condition de Lipschitzité locale en ce qui concerne la norme p sur X , et une métrique de probabilité sur Y. En notant H Lip la classe des classi eur randomisés qui respectent cette condition de Lipschitz, nous présentons les résultats suivants. Une partie de ce travail en collaboration avec Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy-Pailler et Jamal Atif a été publiée à la Conférence Internationale sur les Systèmes de Traitement de l'Information Neuronale (NeuriPS) . Une version étendue de ce travail est actuellement en cours de préparation dans le but d'une soumission à une revue.

• "Theoretical evidence for adversarial robustness through randomization".

Version journal, en cours .

• "Theoretical evidence for adversarial robustness through randomization".

Avances in Neural Information Processing (NeurIPS) . R. Pinot, L. Meunier, A. Araujo, H. Kashima, F. Yger, C. Gouy-Pailler, J. Atif.

Notre analyse pourrait être a née de plusieurs façons. Nous en énumérons ici quelques-unes pour des futurs travaux possibles.

Il convient toutefois de noter que ce résultat repose sur une hypothèse forte concernant l'espace d'entrée qui n'est pas toujours véri ée. Le problème de trouver une sous-classe de H qui o re des bornes plus précises sur l'écart de généralisation reste une question ouverte.

Travail futur : des bornes plus précises pour l'écart de généralisation

Nos résultats sur la généralisation standard des classi eurs randomisés pourraient être améliorés. Dans nos travaux futurs, nous visons à étudier ces résultats sous un nouvel angle. A cette n, nous pourrions utiliser des outils techniques tels que le lemme de Massart ou la notion de dimension d'éclatement pour rendre la borne moins dépendante de la dimension du problème.

Travail futur : étudier les propriétés du lissage randomisé

Nous avons établi des liens entre la propriété de préservation de mode des classi eurs randomisés et la technique de défense appelée lissage randomisé. Sur la base de ces preuves, nous pouvons borner l'écart entre les risques standards et les risques adverses pour cette défense. Une autre direction intéressante serait de montrer que les classi eurs basés sur le lissage randomisé ont un écart de généralisation similaire à celui des classi eurs randomisés que nous avons étudiés.

Travail futur : f -divergences et métriques de probabilité dé nies par intégrales

Les résultats que nous avons obtenus jusque là reposent sur des propriété fondamentales de la distance de variation totale et de la divergence de Renyi. Ces deux divergences ont des propriétés intéressantes, mais nous pensons qu'elles constituent un cas particulier de classes de divergences plus générales pour lesquelles des résultats similaires pourraient être obtenus. L'étude de formes plus générales de divergences telles que les f -divergences et les métriques de probabilité dé nies par intégrales pourrait fournir quelques directions sur la généralité de la dé nition de robustesse que nous présentons dans ce manuscrit.

D. . Méthode simple basée sur l'injection de bruit -Q

Les contributions précédentes ont identi é une classe d'hypothèses randomisées H Lip , qui répond à la fois à Q et Q -au moins partiellement. Mais elles ne fournissent aucun moyen pratique pour construire cette classe. Notre dernière contribution aborde cette question en tirant les leçons de la littérature sur la protection des données. Plus précisément, notre contribution est la suivante.

. Nous mettons en évidence des connections entre notre dé nition de la robustesse et la définition de la con dentialité di érentielle. Les deux notions reposent sur les mêmes fondements théoriques, à savoir la stabilité sur des espaces de mesures. Par conséquent, les résultats obtenus jusqu'à présent en matière de protection des données peuvent facilement être transférés pour construire des classi eurs aléatoires robustes. Sur la base de cette idée, nous utilisons deux outils courants dans la littérature de la con dentialité di érentielle -à savoir l'injection de bruit Gaussien et l'inégalité de data-processing [ ] -pour concevoir des classes de classi eur aléatoires robustes. ont développé le lissage randomisé, en utilisant des résultats liés à la con dentialité di érentielle. Nos travaux s'inscrivent dans le même axe de recherche, cependant la nature de nos résultats est di érente. Alors que le lissage randomisé se concentre sur la construction de défenses certi ées, nous étudions les mécanismes randomisés du point de vue de la théorie de l'information et de la théorie de l'apprentissage supervisé. Notre analyse permet de comprendre certaines propriétés fondamentales des défenses randomisées, comprenant -mais ne se limitant pas -au lissage randomisé. Nos résultats sont applicables à un large éventail de modèles d'intelligence arti cielle, moyennant quelques adaptations mineures. Nous validons donc nos conclusions par des résultats expérimentaux utilisant des réseaux de neurones profonds et des jeux de données d'images standards -à savoir CIFAR et . De plus, cette publication est accompagné d'un ensemble de codes hébergé sur Github permettant de reproduire nos résultats expérimentaux.

• " A uni ed view on di erential privacy and robustness to adversarial examples".

Workshop on Machine Learning for CyberSecurity (ECML-PKDD)

. R. Pinot, F. Yger, C. Gouy-Pailler, J. Atif.

• "Theoretical evidence for adversarial robustness through randomization".

Avances in Neural Information Processing (NeurIPS)

. R. Pinot, L. Meunier, A. Araujo, H. Kashima, F. Yger, C. Gouy-Pailler, J. Atif.

• https://github.com/MILES-PSL/Adversarial-Robustness-Through-Randomization Les méthodes pratiques que nous avons développées pourraient être améliorées de plusieurs façons. Parmi celles-ci, nous énumérons ci-dessous quelques approches possibles.

Travail futur : élargir le champ des adversaires possibles

Jusqu'à présent, nous avons identi é des mécanismes d'injection de bruit pour se défendre contre les attaques dont l'imperceptibilité est mesurée par une norme 2 . Nous avons étendu notre étude à la norme 1 , mais la question de savoir si nous pouvons construire des systèmes d'injection de bruit pour nous défendre contre des perturbations en norme ∞ reste également ouverte. À cette n, nous pourrions utiliser le lien fondamental que notre cadre partage avec le lissage randomisé pour étudier les bruits qui se sont déjà avérés utiles dans cette littérature. En particulier, Yang et al. [ ] ont étudié de nouvelles classes de bruit en utilisant la théorie des cristaux de Wul . Cela pourrait ouvrir des pistes intéressantes pour des mécanismes d'injection de bruit plus sophistiqués.

Travail futur : établir des liens plus profonds avec la con dentialité di érentielle Le lien que nous avons établi avec la con dentialité di érentielle est fondamental, et nous sommes loin d'avoir étudié tous ses aspects. Par exemple, nous pourrions concevoir des modèles aléatoires beaucoup plus sophistiqués basés sur ce lien, notamment en utilisant le mécanisme exponentiel, ou des procédures de vote di érentiellement con dentiel [ ]. La con dentialité di érentielle est également connue pour avoir des propriétés très intéressantes pour la généralisation basée sur la théorie de la stabilité [ ]. Ainsi, nous pourrions adapter les résultats précédents pour améliorer l'analyse que nous avons présentée sur les propriétés des classi eurs randomisés (au regard de l'écart de généralisation).

D. Autres matériels scienti ques et pédagogiques D. . Publications non évoqués dans les corps du manuscrit

Pendant cette thèse nous avons eu l'occasion de travailler sur di érents aspects de la protection des données personnelles et de la robustesse aux exemples adverses. Dans la partie principale de ce manuscrit, nous avons essayé de donner un aperçu clair de nos contributions dans le domaine de l'apprentissage supervisé robuste. Nous nous sommes délibérément concentrés sur certaines de nos contributions les plus signi catives a n de rendre le manuscrit léger et facile à suivre. Ce travail de thèse a également pris d'autres directions. Nous avons notamment étudié l'apprentissage non supervisé sous contraintes de con dentialité di érentielle, et le développement d'outil cryptographique qui puisse être appliqués au développement de méthodes d'apprentissage profond. Nous listons ci-dessous les contributions qui ne sont pas directement traitées dans le corps du manuscrit.

• "SPEED: Secure, PrivatE, and E cient Deep learning".

preprint

. A. Grivet Sébert, R. Pinot, M. Zuber, C. Gouy-Pailler, R. Sirdey.

• "Advocating for Multiple Defense Strategies against Adversarial Examples".

Workshop on Machine Learning for CyberSecurity (ECML-PKDD)

. A. Araujo, L. Meunier, R. Pinot and B. Negrevergne.

• "Graph-based Clustering under Di erential Privacy".

Uncertainty in Artificial Intelligence (UAI)

. R. Pinot, A. Morvan, F. Yger, C. Gouy-Pailler, J. Atif.

D. . Publications à plus large audience

Tout au long de ce travail de thèse, nous n'avons pas seulement mis l'accent sur la production de publications scienti ques. Nous nous sommes également engagés dans la vulgarisation scienti que par le biais de démonstrations et de communiqués de presse. Nous pensons que c'est aussi le rôle des scienti ques, en particulier dans le domaine de l'intelligence arti cielle, d'expliquer leur travail à un public plus large au sein de la communauté scienti que, et d'accroître les connaissances du public sur les dé s et les enjeux des nouvelles technologies. Voici quelques-unes de nos contributions.

• "Attaques adversariales: comprendre pour atténuer les risques" (article de presse).

Clef du CEA num . Contributeurs: R. Pinot, C. Gouy-Pailler.

• "AI vs Wild. How to strengthen neural networks of AI systems" (démonstration).

Consumer Electronic Show Las Vegas

. Contributors: C. Gouy-Pailler, E. Kawasaki, R. Pinot, F. Valente.

• "Randomization based defenses against adversarial examples" (démonstration).

DIGIHALL days Paris Saclay

. Contributeurs: R. Pinot, C. Gouy-Pailler.

• "La recherche et les risques inhérents à l'IA" (article de presse).

Préventique num

• Contributeurs: R. Pinot, C. Gouy-Pailler.

D. . Responsabilités pédagogiques

En n, l'enseignement fait partie intégrante du parcours doctoral et le développement rapide de l'intelligence arti cielle nécessite la conception de nouveaux supports d'apprentissage. Pendant la durée de cette thèse, j'ai également participé à l'élaboration de deux nouveaux cours d'apprentissage automatique.

• "Mathématiques du machine learning" -Université Paris-Dauphine -PSL.

Master IDD première année -. Lecturer: R. Pinot.

• "Trustworthy machine learning in practice" -Université Paris-Dauphine -PSL.

Executive Master

-. Lecturers: A. Araujo, R. Pinot, G. Rizk.

D. Conclusion et problème ouvert pour la communauté D. . Conclusion

Dans cette thèse, nous avons étudié le problème de la classi cation contradictoire sous di érents angles, en utilisant une série d'outils théoriques et pratiques. Nous avons essayé d'analyser le problème théorique nement pour pouvoir proposer des solutions pratiques et viables. Dans l'ensemble, analyser le problème sous ces di érents angles, nous a permis de mieux le comprendre et de construire de nouveaux outils utiles sur le point de vue théorique et pratique. Nous pouvons résumer nos conclusions comme suit.

. Nous avons d'abord présenté le problème comme un jeu à somme nulle in nie, et analysé les propriétés fondamentales du jeu sous di érents types de régularisation.

Cette analyse nous a permis de mieux comprendre le formalisme actuellement utilisé dans la communauté des exemples adverses, et nous a amenés à justi er l'utilisation de méthodes randomisées comme défenses contre les attaques adverses.

. Nous avons ensuite étudié plus en détail les défenses aléatoires. Nous avons notamment développé de nouvelles approches pour étudier la robustesse des classi eurs aléatoires en utilisant la théorie de l'information, la théorie des probabilités et la théorie de l'apprentissage statistique. Cela nous a permis de mettre en évidence les propriétés que devraient respecter les classi eurs randomisés pour être robustes tout en maintenant une bonne précision. Plus particulièrement, nous avons identi é des conditions su santes pour que les classi eurs randomisés soient robustes et nous avons étudié la propriété de généralisation de ces classi eurs.

. En n, nous avons élaboré des méthodes simples et pratiques pour concevoir des classi eurs aléatoires robustes en utilisant la théorie de l'information et les leçons que nous avons pu tiré de la littérature sur la con dentialité di érentielle. Cela montre que nous pouvons construire des classi eurs aléatoires robustes en nous basant sur des architectures de réseaux de neurones profonds, et ouvre la voie à des travaux futurs passionnants, tant en théorie qu'en pratique.

Nous espérons que notre analyse a aidé la communauté à progresser et a apporté des perspectives nouvelles et intéressantes sur le problème di cile qu'est la classi cation contradictoire. Le domaine est encore jeune et de nombreuses pistes de recherche sont encore ouvertes. Tout au long du manuscrit, nous avons discuté des travaux futurs qui correspondent -plus ou moins -à des améliorations directes de nos résultats. Mais ici, nous aimerions prendre le temps de présenter un problème ouvert plus large pour l'ensemble de la communauté.

D. . Problème ouvert : Repenser la théorie de l'apprentissage

La majeure partie de la littérature sur la théorie de l'apprentissage s'attache à démontrer la convergence du risque empirique vers le risque théorique en utilisant la loi uniforme des grands nombres et en contrôlant la complexité de la classe d'hypothèses. L'objectif est alors de trouver des classes de modèles qui soient su samment grandes pour que la minimisation du risque empirique ait une petite valeur, et su samment petites pour que nous obtenions un faible écart de généralisation. Au regard de cet objectif -voir Figure D. à gauche -l'idée la plus courante est qu'un modèle dont l'erreur d'entraînement est nulle aura une mauvaise précision sur l'ensemble de test. Cependant, des travaux récents ont remis en question ce point de vue pour certains modèles tels que les réseaux de neurones. Par exemple, Zangh et al. [ ] ont montré que nous pouvons apprendre un réseau profond pour la classi cation d'images sur CIFAR-10 qui a une précision de 1.0 sur les données d'entraînement et qui obtient plus de 0.85 de précision sur les données de test. Cela signi e que le sur-apprentissage du modèle est soit modeste, soit même inexistant. Pour revenir à la forme classique d'une borne en généralisation en théorie de l'apprentissage, lorsque l'erreur de d'apprentissage est nulle, on obtient . ) où R opt est le risque du clasii eur optimal de Bayes, et C(n) est une mesure de complexité pour la classe d'hypothèses qui peut ou non dépendre de n. Lorsque R opt = 0, nous pouvons souvent montrer que C(n) n → 0, ce qui est logique. Mais, lorsque R opt > 0 , pour que le terme de droite permette d'expliquer l'erreur de manière non triviale, nous avons besoin que les constantes cachées dans O C(n) n soient optimales -ce qui n'est jamais le cas pour des réseaux de neurones. Par conséquent, les idées de la théorie classique de l'apprentissage peuvent ne pas s'appliquer au cadre de l'apprentissage profond, ce qui signi e que l'analyse ne doit pas être uniquement basée sur la loi uniforme des grands nombres ou sur le contrôle de la classe d'hypothèses. Nous constatons cependant que la minimisation du risque empirique fonctionne assez bien en pratique, c'est pourquoi les chercheurs ont commencé à s'interroger sur le contrôle de la complexité des modèles. Plus précisément, la question suivante se pose.

R opt ≤ E (x,y)∼D [L(h(x), y)] ≤ O C(n) n , ( D
En quoi, et à quel point la généralisation des modèles d'apprentissage supervisé dépendent de leur complexité ?

Un premier élément de réponse à cette question provient d'une observation faite en forçant les modèles à sur-apprendre -pour plusieurs modèles d'apprentissage machine, notamment les réseaux de neurones [ , ]. Lorsque nous augmentons arbitrairement la complexité du modèle, nous constatons qu'après le sur-apprentissage, le risque théorique du modèle recommence à diminuer. Ce phénomène est appelé "double descente". Notez qu'après le sur-apprentissage, tous les modèles ont une erreur d'entraînement nulle, mais plus le modèle est grand, plus le risque théorique est faible. C'est un phénomène très surprenant qui a été observé sur de nombreux modèles de réseaux de neurones avancés. D'un point de vue théorique, le phénomène a été identi é et analysé pour les modèles linéaires. Pour revenir à l'objectif principal de ce manuscrit, nous pourrions également poser la question suivante.

  the standard setting . . . . . . . . . . . . . . . . . Classi cation under adversarial perturbation . . . . . . . . . . .

  outline of the thesis. . . . . . . . . . .

Figure . :

 . Figure . : Key principles of the GDPR on the development of new machine learning models.

Figure . :

 . Figure . : Illustration of a self-driving car misclassifying real-world tra c signs with adversarial perturbations. On the top line: scenario without attack. On the bottom line: scenario with attack. Tra c sign images come from a real-life attack paper [ ].

Figure . :

 . Figure . : Evolution of the approximation and estimation error for a xed hypothesis h and two nested hypothesis classes H 1 and H 2 .

Figure . :

 . Figure . : Trade-o between the approximation and estimation errors according to the complexity of the hypothesis class.

Figure . :

 . Figure . : Reinterpretation of the approximation/estimation trade-o using the generalization error and the empirical risk -for the SRM.

Figure . :

 . Figure . : Sample of images from CIFAR datasets [ ].

Figure . :

 . Figure . : Sample of images from Imagenet datasets [ ].

  Figure . : Adversarial perturbation of a pig from ImageNet.

  Figure . illustrates how to design an adversarial example on an image from ImageNet dataset. The original image is a pig -on the left -and a state-of-the-art deep neural network trained on ImageNet recognizes it as such.

Figure . :

 . Figure . : Comparison of an 2 and an ∞ ball of similar volumes. On the left: d = 2. On the right: d → ∞.

  Figure . illustrates this and compares an 2 and an ∞ ball of similar volumes when the dimension of the problem -d -increases. In a 2 dimensional space See e.g. https://adversarial-ml-tutorial.org/adversarial_examples/ Simon-Gabriel et al. [ ] recently hypothesized that we should set αp = α∞ × d 1/p instead, but this formula does not match empirical observations as well as equalizing the volumes.

Figure . :

 . Figure . : Illustration of the convex relaxation technique from [ ].

Figure . :

 . Figure . : On the left: adversarial examples for a complicated over-tting network. On the right: adversarial examples for a linear under-tting classi er.

  defense, a two-player zero-sum game . . . . . . Trivial solution and regularized adversary . . . . . . . . . . . . . Instability of the game . . . . . . . . . . . . . . . . . . . . . . . . . . Characterizing the best responses . . . . . . . . . . . . . . . . . . No Pure Nash Equilibrium in the game . . . . . . . . . . . . . . Randomization might be the clue . . . . . . . . . . . . . . . . . . . . Adaptation of the problem statement . . . . . . . . . . . . . .

  future works. . . . . . . . . . . . . . . . . .

Figure . :

 . Figure . : Illustration of the conditional distributions µ 1 and µ 1 . On the left: without attack. On the right: under trivial attack. Blue and red zones are the points that are at distance less than α p of the boundary.

Figure .

 . Figure . illustrates this phenomenon for the uni-dimensional setting with Gaussian distributions. The adversary moves every point toward the decision boundary -each time saturating the norm constraint -and the defender cannot do much to mitigate the damages. In this case the best classi er remains unchanged, although both curves moved; hence a trivial equilibrium. Furthermore, thanks to Theorem , we can evaluate the value of this equilibrium, which can be high -depending on the conditional distributions.In the remainder of this work, we show that this equilibrium does not hold when we add a small constraint on the adversary's strengthi.e. when it is not perfectly indi erent to producing unnecessary perturbations. To formalize the constraint on the adversary, we introduce a penalty term in the initial formulation of the game,

Figure . :

 . Figure . : Illustration of the conditional distributions µ 1 and µ 1 . On the left: without attack. On the right: under penalized attack. Blue and red zones are respectively the sets P h (α p ) and N h (α p ).

Figure .

 . Figure . illustrates Theorem with two uni-dimensional Gaussian distributions. We see that -one the right -µ 1 is set to 0 in P h (α p ), and this mass is transferred into N h (α p ). The symmetric holds for µ 1 . After attack, we have µ 1 (P h (α p )) = 0. Hence, any small amount of mass for µ 1 in P h (α p ) is now su cient to make it dominant; hence the zone will now be classi ed -1 by the Bayes optimal classi er. This result has several deep consequences. Among them, we focus on the following two.

Figure . :

 . Figure . : Illustration of the notations U , U + , and U -for proof of Theorem .

Figure . :

 . Figure . : Illustration of the conditional distributions µ 1 and µ 1 . On the left: without attack. On the right: under penalized attack with the new penalty. Blue and red zones are respectively the sets P h (α p ) and N h (α p ).

Figure . :

 . Figure . : Illustration of the notations U , U + , U -and δ for proof of Theorem .

  classi ers . . . . . . . . . . . . . . . Risks' gap for robust randomized classi ers . . . . . . . . . . . . .. . An additive bound for the risks' gap . . . . . . . . . . . . . . . . . Robustness may not be at odds with accuracy. . . . . . . . . . . . Generalization gap for randomized classi ers . . . . . . . . . . . . . . Bounding the Rademacher complexity for the total variation . . .. . Discussion on the generalization bound . . . . . . . . . . . . . . Mode preservation and randomized smoothing . . . . . . . . . . .. . Mode preservation property for randomized classi ers . . . . . .

.

  to randomized smoothing . . . . . . . Additional results: extension to the Renyi divergence and discussion on probability metrics . . . . . . . . . . . . . . . . . . . . . . . .

  metric/divergence one should consider . . . . . . Lessons learned and future works . . . . . . . . . . . . . . . . . .

  This chapter's goal is to analyze how randomized classi ers could constitute good candidates to solve the problem of classi cation under perturbation. For this, we come back to the general Kclass classi cation setting. We have X ⊂ [0, 1] d , Y = {1, . . . , K} and D the ground-truth distribution on X × Y. Let us start by de ning what we mean by randomized classi ers. De nition (Probabilistic mapping). Let Z and Z be two arbitrary spaces. A probabilistic mapping from Z to Z is a mapping m : Z → P(Z ). When Z = X and Z = Y, m is called a randomized classi er. To get a numerical answer out of m for an input x, we sample ŷ ∼ m(x).

  e. E ŷ∼m(x+τ ) [1{ŷ = y}]. Therefore, the adversarial risk of m under α p -bounded perturbations writes R adv (m; α p ) := E (x,y)∼D sup τ ∈Bp(αp)

  above result means that, if we can cover the n training samples with O(1) balls, then we can bound the generalization gap of any randomized classi er m ∈ M T V (α p , ) by O 1 √ n + . . . Discussion on the generalization bound Xu et al. [ ] previously studied generalization bounds for learning algorithms based on their robustness. Although we use very di erent techniques of proof, their results and ours are similar.

Figure . :

 . Figure . : Illustration of a 1/2-covering for the hyper cube for the ∞ norm. On the left: [0, 1] 2 . On the right: [0, 1] 3 .

Figure . :

 . Figure . : Summary of the relations between the di erent robustness notions from Propositions and .

Figure . :

 . Figure . : Illustration of the typical threat scenario in di erential privacy.

Figure . :

 . Figure . : Impact of the standard deviation of the Gausian noise on accuracy in a randomized model on CIFAR-and CIFAR-dataset.

Figure . :

 . Figure . : Guaranteed accuracy of di erent randomized models with Gaussian noise given the 2 norm of the adversarial perturbations.

Figure . :

 . Figure . : Impact of the standard deviation of the Laplace noise on accuracy in a randomized model on CIFAR-and CIFAR-dataset.

Figure . :

 . Figure . : Guaranteed accuracy of di erent randomized models with Laplace noise given the 1 norm of the adversarial perturbations.

  sense. But, when R opt > 0, for the right term to explain the error in Conclusion & open problems a non-trivial way, we need the hidden constants in O C(n) n

Figure . :

 . Figure . : Comparison of the classical belief in learning theory with the double descent phenomenon.

Figure . :

 . Figure . : Summary of the links and expected links between several areas within the trustworthy machine learning community.

Figure A . :

 . FigureA. : On the left: D representation of the ∞ and 2 balls of respective radius α ∞ and α 2 . In the middle: a classi er trained with ∞ adversarial perturbations -red line -remains vulnerable to 2 attacks. On the right: a classi er trained with 2 adversarial perturbations -blue lineremains vulnerable to ∞ attacks.

  average ∞ norm of an 2 perturbation more than doubles between an unprotected model and a model trained with an adversarial training. As shown in Figure A. -on the right -the attack generates an adversarial example in the cap of the 2 ball, thus increasing the ∞ norm while maintaining the same 2 norm. The same phenomenon can be observed with the AT-2 against the PGD-∞ attack -see Figure A. in the middle and Table A. . The PGD-∞ attack increases the 2 norm while maintaining the same ∞ perturbation by generating the perturbation in the corner of the ∞ ball. As a result, we cannot expect adversarial training ∞ to guaranty any protection against the 2 adversarial examples.

Figure A . :

 . Figure A. : Comparison of the number of adversarial examples found by C&W, inside the ∞ ball -lower, blue area, outside the ∞ ball but inside the 2 ball -middle, red area -and outside the 2 ball -upper beige area. α ∞ is set to 0.03 and α varies along the x-axis. On the left: without adversarial training. On the right: with adversarial training.

P

  u-v e∈P u-v w(e), with P u-v a path from u to v in G -edges version. De nition (Cluster extended from [ ]). Let us consider G = (V, E, w), dist the minimum path distance defined on G and D ⊂ V . A vertices set C ⊂ D is a cluster if and only if |C| > 2 and for any partition C 1 , C 2 of C we have arg min z∈D\C 1

  FigureB. illustrates the de nition. On the left, we have a valid clustering. On the right, the cluster is obviously non representative of the underlying structure of the graph; hence De nition does not hold. Thanks to the above de nition of cluster, we can now motivate the use of MST-based algorithms for node clustering in a graph.Theorem (Motivation for MST-based clustering -Informal).Let G = (V, E, w) be a graph and T a minimum spanning tree of G. Let also C be a cluster in the sense of Definition . Then for any two vertices u, v ∈ C, we have P u-v ⊂ C, where P u-v is the path from u to v in T .

Figure B . :

 . Figure B. : Illustration of valid and non-valid clusters for De nition .

  Figure B. : Diagram summarizing DBMSTC algorithm. Figure from [ ].

De nition .

 . For any edge set E, two weight functions w, w are called neighbors -denoted w ∼ w -if ||ww || ∞ := max e∈E |w(e)w (e)| ≤ α.

  Figure B. : Diagram summarizing PAMST algorithm. Figure from [ ].

Figure B . :Figure B . :

 .. Figure B. : Di erentially private clustering for the Circles dataset of size n = 100.

Figure C . :

 . Figure C. : Diagram illustrating SPEED deep learning framework.

  Bien qu'il se concentre sur la protection des données, le RGPD comprend également un article -l'article -sur le droit de recevoir une explication lorsqu'une décision à été prise à l'aide d'un algorithme [ ]. Cela soulève un certain nombre de questions tant sur l'interprétabilité des algorithmes d'apprentissage supervisé que sur la con ance que les utilisateurs leur accordent [ ].

Figure D . :

 . Figure D. : Illustration d'une voiture autonome, dupée par une modi cation mineure d'un panneau de signalisation. En première ligne : le scénario sans attaque. En seconde ligne : scénario avec attaque. Les images des panneaux de signalisation proviennent d'une attaque présentée par Sitawarin et ses co-auteurs [ ].

  mais la plupart d'entre eux se sont avérés -avec le temps -ine caces contre des attaques plus sophistiquées [ , , , , ]. Néanmoins, il est important d'étudier cette question d'un point de vue théorique pour apporter des réponses négatives dé nitives ou pour concevoir des modèles plus robustes. Supposons un instant que Q ait une réponse positive et que nous puissions concevoir une classe d'hypothèses H pour laquelle la minimisation du risque adverse a une solution h * avec un faible risque contradictoire. Par analogie avec le cadre standard, étant donné les n exemples d'apprentissage S := {(x  , y 1 ), . . . , (x n , y n )}, nous voulons trouver une solution au problème de minimisation du risque adverse en étudiant sa contrepartie empirique, le risque empirique adverse. Ce problème d'optimisation s'écrit

  CIFAR [ ]. Ces modèles peuvent simultanément o rir une prédiction précise et une robustesse raisonnable, donnant des réponses pratiques à Q et Q . Nous pouvons construire facilement des classi eurs randomisés qui sont robustes aux attaques adverses. Une partie de ce travail en collaboration avec Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy-Pailler et Jamal Atif a été publiée à la Conférence Internationale sur les Systèmes de Traitement de l'Information Neuronale (NeuriPS) et dans un Workshop à la Conférence Européenne sur l'Apprentissage Machine (ECML)

Figure D . :

 . Figure D. : Illustration du phénomène de la double descente. Notez que, la plupart du temps, nous aurons R opt > 0, étant donnée que le support des distributions conditionnelles {µ k } k∈[K] ne sont pas susceptibles d'être disjoints.

  Ce changement de paradigme nous permettrait-il de mieux comprendre ou d'éviter les exemples adverses ? Une façon intéressante de commencer à répondre à cette question est d'examiner le modèle des k plus proches voisins, comme le suggère Belkin et al. [ ]. Il s'agit d'une technique de prédiction classique pour laquelle nous pouvons directement relier l'erreur attendue de l'algorithme au classi eur optimal de Bayes. Par exemple, Cover et Hard [ ] ont montré que nous pouvons encadrer l'erreur du modèle comme ceci: R opt ≤ E (x,y)∼D [L(h(x), y)] ≤ R opt 2 -KR opt K -1 . (

. An introduction to learning theory and image classi cation

  . . . . . Formalizing the classi cation problem . . . . . . . . . . . . . . The estimation/approximation trade-o . . . . . . . . . . . . . Empirical risk minimization and generalization gap . . . . . . . . Structural risk minimization . . . . . . . . . . . . . . . . . .

. . . . . . . . . . Some more practical considerations: hypothesis classes and datasets . Adversarial attacks, an overview . . . . . . . . . . . . . . . . . . . . . A rst example . . . . . . . . . . . . . . . . . . . . . . . . . . . Threat models . . . . . . . . . . . . . . . . . . . . . . . . . . . On the notions of imperceptibility in high dimension . . . . . . . . How to build an attack? . . . . . . . . . . . . . . . . . . . . . . Discussion on the attack strategies . . . . . . . . . . . . . . . . . State-of-the-art on defense strategies . . . . . . . . . . . . . . . . . . . Adversarial training . . . . . . . . . . . . . . . . . . . . . . . . Provable robustness . . . . . . . . . . . . . . . . . . . . . . . . Discussion on the current defense strategies . . . . . . . . . . . . Adversarial classi cation through the lens of statistical learning theory . . Is robustness antagonist with accuracy? . . . . . . . . . . . . . . . Studying adversarial generalization . . . . . . . . . . . . . . . . . Discussion on the learning theory literature . . . . . . . . . . . . Is classi cation under perturbation feasible? . . . . . . . . . . . . . . . Initial hypotheses on the existence of adversarial examples . . . . . . . Are adversarial examples inevitable? . . . . . . . . . . . . . . . . . Finding worst case lower bounds on the adversarial risk minimization . . Discussion on the feasibility of classi cation under perturbation

  The associated optimization problem is as follows,

	inf τ s.t. L(h(x+τ ),y)≥κ	τ p .	( . )
	Problem ( . ) has been studied extensively by Carlini et al. [ ], resulting in a method called
	C&W attack. It aims at solving the following Lagrangian relaxation of the problem
	inf τ	τ p + λ × g(x + τ )	( . )
	where g(x + τ ) < 0 if and only if L(h(x + τ ), y) ≥ κ. According to the loss function, Carlini et. al. use a binary search to optimize the constant κ and a stochastic gradient descent to compute
	an approximate solution of the problem . The C&W attack is well de ned for both p = 2 and
	p = ∞. However, empirical observations show a clear gap of e cacy for the 2 -based attack. Accordingly, for this work, we only consider C&W as an 2 attack.

  argmax

	Background
	this method is still unknown. Provable defenses attempt to address this concern by providing an
	in-depth mathematical analysis with the methods they present.
	τ s.t. τ p ≤α	L(h(x + τ ), y) .	( . )
	Then -intuitively -a standard training procedure on x + τ * instead of x would converge to
	a robust classi er if it exists. Even-though Danskin Theorem does not hold in practice , sev-
	eral works [ , , ] presented a learning procedure called adversarial training based on this
	reasoning. In a nutshell, adversarial training seeks a solution to the empirical adversarial risk min-
	imization -Problem ( . ) -by taking successive stochastic gradient steps on an approximated
	worst-case perturbation of the clean input. To simulate the worst-case perturbation, the proce-
	dure uses an attack method -usually PGD . This solution -inspired by the literature on robust
	optimization [ ] -is intuitive and provides state-of-the-art experimental robustness against the
	strongest ∞ attack methods proposed so far [ ]. Typically on CIFAR-, the latest improve-
	ment of adversarial training [ ] obtains 0.53 test-time accuracy under ∞ perturbations of size
	0.031. However, the main weakness of adversarial training is its lack of formal guarantees. De-
	spite some recent works [ , ] providing valuable insights, the worst-case adversarial risk of

  To nd a good approximation to the inner maximization problem, we should characterize the image of B p (x, α p ) through hi.e. h(B p (x, α p )).

				To simplify the problem,
	recent works [ ,	,	,	] performed a convex relaxation over the image set in the context
	of neural networks with ReLU non-linearity, and performed robust optimization over this new
	region.

Table . :

 . Certi ed accuracy of randomized smoothing model [ ] on the CIFAR-dataset.

	2 norm of the attack	0.25 0.5 0.75 1.0 1.25
	Randomized smoothing [ ] 0.81 0.63 0.52 0.37 0.33
	several extensions obtained similar results for other p norms [ , ], or discuss how this method
	relates to the dimension of the problem [ ]. Overall, randomized smoothing presents principled
	advantages over most previous methods. It is simple to implement and to interpret, computation-
	ally e cient and provides state-of-the-art provable robustness for benchmark datasets.

  noticed that the initial version of adversarial training achieves 0.96 train-time adversarial accuracy against 0.47 test-time adversarial accuracy. This gap between train and test performances is signi cantly larger than what models usually achieve in the standard setting. Hence it is crucial to study generalization guarantees in the adversarial setting to control the generalization gap between training and test errors.

. Adversarial classi cation through the lens of statistical learning theory Notations.

  By analogy with the standard setting, we denote R adv (h; α p ) and R adv S (h; α p ) the adversarial risk and empirical adversarial risk of h under α p -bounded perturbations

	R adv (h; α p ) := E (x,y)∼D	sup τ ∈Bp(αp)	L(h(x + τ ), y) ,	( . )
	R adv S (h; α p ) :=	1 n	n i=1	sup τ ∈Bp(αp)

. Instability of the game Notations

. Let h ∈ H, we denote P h := {x ∈ X s.t. h(x) > 0} the set of positive outputs of h and N h := {x ∈ X s.t. h(x) < 0} the set of negative outputs of h. We also denote P h (α p ) and N h (α p ) the set of points on which h can change sign under an α p -bounded perturbation. P h (α p ) :=

x ∈ P h s.t. ∃z ∈ (P h ) c where zx p ≤ α p , and N h (α p ) likewise.

Table . :

 . Accuracy under attack of a single adversarially trained classi er (AT) and the mixture formed with our method (Ours) on CIFAR-and CIFAR-datasets.

	Dataset	Method	Accuracy without attack α ∞ = 0.031 α 2 = 0.8 l ∞ -PGD 2 -C&W
		Undefended	.	.	.
	CIFAR 10	AT [ ]	.	.	.
		Ours	.	.	.
		Undefended	.	.	.
	CIFAR 100	AT [ ]	.	.	.
		Ours	.	.	.

  , α p . By de nition of a covering number, there exists C = {c  , . . . , c N } an α p -covering of {x  , . . . x n } for the p norm. Furthermore, for j ∈ {1, . . . , N } and y ∈ {1, . . . , K}, we de ne E y,j = i ∈ {1, . . . , n} s.t. y i = y and arg min

. . ,

x n }, . p , α p is the α p -external covering number of the inputs {x  , . . . , x n } for the p norm.

Proof. Let us denote S := {(x  , y 1 ), . . . , (x n , y n )} and N = N {x  , . . . , x n }, . p l∈{1,...,N }

  Since the original work of Dwork et al. [ ], many extensions have been introduced to adapt the de nition to other possible input or output spaces, depending on the application setting -see [ ] for a complete list. Recently, Chatzikokolakis et al. [ ] introduced a general framework, called "metric-di erential privacy", which encompasses many extensions of the initial de nition.De nition (Metric-di erential privacy). Let , α ≥ 0, (Z, d Z ) an arbitrary input metric space, and Z an output space. A probabilistic mapping m from Z to is called (α, )-metric private if for any z  , z  ∈ Z such that d Z (z  , z  ) ≤ α and for any B ∈ A(Z ) we have

  Second, adversaries do not have the same objective: in privacy, the adversary wants to infer a subset of the training sample, while in robustness, it wants to force to misclassify. But if robustness and privacy have very different semantics, we can see how the de nitions are based on the same mathematical foundation: Lipschitz continuity and information theory. If we consider Z an arbitrary input space with p norm and Z an arbitrary output space, then the following holds.

A mapping m is (α p , )-robust w.r.t. D β if and only if m is ( , α p , β) Renyi-private.

Table . :

 . Accuracy under attack of randomized neural networks with Gaussian pre-processing for di erent standard deviations versus adversarial training by Madry et al. [ ] -AT. The rst line refers to the baseline without attack. Results are presented for both CIFAR-and CIFARdatasets.

	Dataset	Method	Accuracy without attack α ∞ = 0.06 α 2 = 1.6 ∞ -PGD 2 -C&W
		Undefended	.	.	.
	CIFAR 10	AT [ ]	.	.	.
		Gaussian σ = 0.32	.	.	.
		Gaussian σ = 0.5	.	.	.
		Undefended	.	.	.
	CIFAR 100	AT [ ]	.	.	.
		Gaussian σ = 0.32	.	.	.
		Gaussian σ = 0.5	.	.	.

obtain for the adversarial training. Moreover, Gaussian pre-processing is more robust than adversarial training for both PGD and C&W attacks. These experiments show that randomized defenses can be competitive given the intensity of the noise injected into the network.

Remark .

Our theoretical findings only hold for 2 adversaries. Hence we were not guaranteed to have any protection against ∞ -PGD. Nevertheless, our method presents state-of-the-art experimental robustness against this attack as well.

  ). Let d ∈ N, Θ be an open convex set of R d , and θ ∈ Θ. Let ρ be a probability measure in P R d that admits a probability density function either with respect to the Lebesgue or the counting measure. ρ is said to be part of the exponential family of parameter θ if it has the following probability density function

Table . :

 . Accuracy under attack of randomized neural network with Laplace pre-processing for di erent standard deviations. CIFAR-and CIFAR-datasets.

	Dataset	Method	Accuracy without attack α ∞ = 0.06 α 1 = 7 ∞ -PGD 1 -EAD
	CIFAR 10	Laplace σ = 0.32 Laplace σ = 0.5	. .	. .	. .
	CIFAR 100	Laplace σ = 0.32 Laplace σ = 0.5	. .	. .	. .

  sarial examples [ ]. Nevertheless, recent results [ ] have also shown that if we force a k-nearest neighbor model to over-t the training samplesa.k.a. by interpolating nearest neighbor in [ ],

Table A .

 A : Comparison of the bound from Theorem when d varies from d = 2 to typical image classication setting -10 -0.009 ≈ 0.98.

	Dataset	Dimension (d) Volume of the intersection
	-	10 -0.009
	MNIST	10 -144
	CIFAR	10 -578
	ImageNet	10 -28946

  A. : Average norms of PGD-2 and PGD-∞ adversarial examples with and without ∞ adversarial training on CIFAR-(d = 3072). To demonstrate that adversarial training is not robust against PGD-2 attacks, we measure the evolution of the 2 norm of the adversarial examples generated by the attack against an unprotected model and a model trained with adversarial training ∞ -AT-∞ , where the adversarial examples are generated with the PGD-∞ . The results are presented in Table A. . We can see that the

	Adversary	Attack PGD-2	Attack PGD-∞
	Model	Unprotected AT-∞ Unprotected AT-2
	Average 2 norm	.	.	.	.
	Average ∞ norm	.	.	.	.

  (E cacy of DBMST -Informal). Let G be a simple weighted graph with K clusters C 1 , . . . , C K . If G is homogeneous, then DBMST applied on any MST of G outputs subtrees that match the clusters C 1 , . . . , C K .

  as well as Karwa et al. [ ] formalized the idea of releasing statistics from a graph in a di erentially private manner following the seminal work of Nissim et al. [ ].

C Secure and private deep learning with encrypted aggregation operator

  This appendix is a brief overview of an ongoin work in collaboration with Arnaud Grivet Sebert, Martin Zuber and Renaud Sirdey. We refer the interested reader to an arXiv version of this preparatory work called "SPEED: Secure, PrivatE, and E cient Deep learning".

	Contents
	C. A

new framework beyond di erential privacy

  . . . . . . . . . . . .

C.

Related works on private deep learning

  . . . . . . . . . . . . . . .

  C'est au cours des années que naît le concept de l'intelligence arti cielle. Plus particulièrement, c'est souvent la conférence de Dartmouth de qui est considérée comme l'acte fondateur du concept . À cette époque, le but était de comprendre et de tenter de reproduire l'intelligence humaine. Les approches proposées consistaient en l'utilisation des mathématiques pour décrire le monde, modéliser la perception humaine et simuler les mécanismes cérébraux. Soixante-dix ans plus tard, l'objectif initial de réplication des fonctions cérébrales a été largement supplanté par des projets technologiques visant à reproduire les performances humaines dans des tâches cognitives simples [ ]. À cet e et, les réseaux de neurones profonds atteignent des performances remarquables dans des domaines applicatifs complexes tels que le traitement automatique du langage [ ], la reconnaissance d'images [ ] ou la reconnaissance de la parole [ ].

  [ ] ont présenté une procédure de désanonymisation très e cace sur la base de données publiée pour le "Net ix Prize". En , l'Union européenne a apporté une réponse à ces préoccupations d'un point de vue juridique en publiant le Règlement Général sur la Protection des Données [ ] -RGPD.Ce règlement vise à dé nir les obligations des fournisseurs de modèles en ce qui concerne les données à caractère sensible qu'ils utilisent . A n de se conformer au RGPD, les industries et Cette conférence est en réalité l'aboutissement de plusieurs travaux pionniers traitant de la notion d'intelligence

				[ , ,
	]. Cependant, ces sujets sont revenus sur le devant de la scène notamment en	, lorsque
	Narayanan et al. arti cielle par Mc Culloch, Pitts et Wiener [ ,	,	] par la communauté cybernétique et par Turing [ ]
	pour celle de l'informatique.
	Nous ne prétendons pas présenter ici une analyse complète de ce règlement. Pour que la discussion reste concise,
	nous nous contentons de souligner certains points que nous -en tant qu'informaticiens -jugeons essentiels.

  R est une fonction de coût qui mesure à quel point h correspond à la distribution des données. Si L est su samment bien choisie -typiquement si elle est convexe et su samment régulière [ ] -et si la classe d'hypothèses H est su samment riche , le classi eur c que nous obtenons aura une faible probabilité de donner une mauvaise étiquette pour un nouvel échantillon (x, y) ∼ D.En pratique, l'algorithme d'apprentissage n'a pas accès à la distribution D; il ne peut donc pas estimer le risque E (x,y)∼D[L(h(x), y)]. Pour trouver une approximation au Problème (D. ), un On peut considérer cette notion comme la taille de la classe d'hypothèses. Lorsque la classe d'hypothèses est assez grande, il est facile de trouver au moins une h qui décrive bien D. Inversement, lorsqu'elle est trop petite, il est di cile de trouver un bon candidat. Pour plus de détails, nous incitons le lecteur à se référer à la partie anglaise du manuscrit. algorithme d'apprentissage résout le problème de minimisation du risque empirique à la place. Ce problème s'écrit Ensuite, pour évaluer la distance entre l'hypothèse sélectionnée h S et l'hypothèse optimale h * , on cherche à borner supérieurement la di érence entre le risque et le risque empirique de toute hypothèse h ∈ H. Cette di érence est connue sous le nom d'écart de généralisation. Intuitivement, si nous pouvons contrôler la di érence entre le risque et le risque empirique d'une fonction quelconque dans H, alors le problème de minimisation du risque et le problème de minimisation du risque empirique auront des solutions similaires.Au regard de ce qui précède, le choix de la classe d'hypothèses H est central pour résoudre un problème de classi cation. D'une part, si la classe est trop grande, il sera di cile de contrôler l'écart de généralisation pour tous les éléments de la classe et le problème d'optimisation sera di cile. D'autre part, si elle est trop réduite, l'écart de généralisation sera facile à contrôler mais la classe pourrait ne pas être su samment riche pour décrire correctement le comportement de la distribution des données, ce qui conduira à sélectionner de mauvaises fonctions de prédiction. Un autre élément clé est la taille de l'ensemble d'apprentissage. Si nous avons su samment d'échantillons d'apprentissage, grâce à la loi uniforme des grands nombres, le risque empirique de toute hypothèse est une bonne approximation de son risque théorique.Plus précisément, pour certaines classes d'hypothèses bien choisies, on peut limiter l'écart de généralisation de toute hypothèse par O 1 √ n . Ensuite, lorsque la taille de l'échantillon n est su samment grande, il su t de résoudre le problème de minimisation du risque empirique -Problème (D. ) -pour obtenir une bonne approximation pour le problème de minimisation du risque -Problème (D. ). Présentons maintenant le cadre de classi cation alternatif que nous allons étudier dans ce manuscrit, à savoir la classification sous perturbations adverses.

	inf h∈H	1 n	n i=1	L(h(x i ), y i ) .	(D. )

Pour ce faire, l'algorithme d'apprentissage cherche à sélectionner h * dans un espace fonctionnel H -aussi appelé classe d'hypothèses -qui soit solution du problème de minimisation du risque. Ce problème d'optimisation s'écrit comme ceci: inf h∈H E (x,y)∼D [L(h(x), y)] , (D. ) où L : R K × Y →

  . ) où B p (α p ) := {τ ∈ X t.q. τ p ≤ α p }. Dans ce nouveau problème, l'adversaire se concentre sur le problème de maximisation intérieur, tandis que l'algorithme d'apprentissage tente d'obtenir l'hypothèse optimale "sous attaque" h * à partir de H. Dans le cadre standard, nous pouvons la plupart du temps concevoir des classes d'hypothèses su samment riches pour que le problème de minimisation du risque donne une solution h * avec un risque faible. Mais dans le cadre adverse, on ne sait pas si cette a rmation tient toujours. D'où la question suivante.

Q : Existe-t-il une classe d'hypothèses H pour laquelle le problème de minimisation du risque

adverse a une solution h * avec un faible risque adverse?

•

  Comme récemment souligné par Madry et al. [ ], l'écart de généralisation adverse -c'està-dire l'écart entre le risque empirique contradictoire et le risque contradictoire -peut être beaucoup plus important que dans le cadre standard. Plus particulièrement, Madry et al. [ ] ont remarqué qu'il est possible d'atteindre une précision adverse de 0, 96 pendant l'apprentissage contre 0, 47 pendant l'étape de test. Cet écart entre les performances pendant ces deux étapes est nettement plus important que ce que les modèles atteignent habituellement dans le cadre standard. En e et, l'adversaire rend le problème dépendant de la dimension de X , et donc beaucoup plus di cile. • Pour mieux comprendre d'où provient la di culté de résoudre le problème de classi cation sous perturbations adverses, un certain nombre de travaux théoriques ont été menés. Notamment, Schmidt et al. [ ] ont montré dans un cadre joué que nous n'avons besoin que de O(1) exemples d'entraînement pour avoir un petit écart de généralisation. Par contre, en présence d'un adversaire ∞ , nous avons besoin d'au moins O( √ d) échantillons. Cette étude a été suivie de plusieurs avancée majeurs

Résumé des contributions de cette thèse

  Dans cette thèse, nous cherchons à apporter des réponses aux problèmes énoncés précédemment. Tout d'abord, nous analysons le problème de la classi cation contradictoire et fournissons des résultats montrant que les classi eurs randomisés -c'est-à-dire les classi eurs qui renvoient une variable aléatoire -sont de bons candidats pour donner une réponse positive à Q . Ensuite, nous identi ons des sous-classes de classi eurs randomisés qui fournissent des réponses positives à la fois à Q et Q . En n, nous présentons des méthodes simples pour construire ces classes en établissant des liens avec la littérature sur la protection des données personnelles.

Q : Peut-on trouver une classe H et une hypothèse h * ∈ H qui atteignent simultanément un petit risque standard et contradictoire ? D. D. .

Analyse du problème de la classi cation contradictoire -Q

  Notre première contribution consiste à construire de nouvelles intuitions sur le problème de la classi cation adverse. Pour ce faire, nous présentons la minimisation du risque contradictoire -Problème (D. ) -comme un jeu à somme nulle infini entre un défenseur -l'algorithme d'apprentissage -et un adversaire qui produit des exemples adverses. Certains travaux récents ont eux aussi abordé le problème des exemples d'adverses comme un jeu à deux joueurs [ , ], cependant ils considèrent des versions restreintes du jeu -par exemple lorsque les joueurs n'ont qu'un ensemble ni de stratégies possibles. Nous étudions un cadre plus général qui nous permet d'avoir une idée précise de la nature fondamentale du jeu entre le classi eur et l'adversaire. Plus particulièrement, nous obtenons les résultats suivants. . Nous démontrons la non existence d'un équilibre de Nash dans le jeu (régularisé) lorsque le défenseur et l'adversaire jouent tous deux des stratégies déterministes. Ceci, associé à certains résultats récents obtenues dans des travaux connexes [ , ], implique que les classes d'hypothèses déterministes peuvent ne pas être de bons candidats pour fournir une réponse positive à Q . Nos conclusions mettent également en évidence une propriété très intéressante du problème de classi cation contradictoire : son instabilité. Cela signi e que la nature du jeu entre l'adversaire et le classi eur change complètement lorsque nous ajoutons un petit terme de régularisation. Cela nous amène à remettre en question certaines thèses actuelles sur la classi cation adverse et à nous demander si les conclusions existantes tiendraient toujours si nous considérons un adversaire réaliste. . Du point de vue de la théorie des jeux, l'étape suivante consiste naturellement à étudier des stratégies randomisées. Nous nous concentrons sur la randomisation des stratégies pour le défenseur -en laissant les stratégies de l'adversaire inchangées. Dans ce contexte, nous démontrons que les classi eurs aléatoires peuvent surpasser les classi eurs déterministes en termes de garanties théoriques de robustesse -Problème (D. ). Par conséquent, nous identi ons les classi eurs aléatoires comme de bons candidats pour répondre à Q positivement. De plus, ce résultat nous permet de développer une méthode algorithmique que nous nommons Boosted Adversarial Training (BAT). Cette méthode repose sur une construction simple et permet de générer un classi eur randomisé à partir d'un classi eur déterministe. Le classi eur randomisé obtenu donne de meilleurs résultats expérimentaux en terme de précision sous attaques adverses que le classi eur déterministe initial. Ce travail en collaboration avec Raphael Ettedgui, Geovani Rizk, Yann Chevaleyre et Jamal Atif a été publié à la Conférence Internationale sur l'Apprentissage Machine (ICML)

	Il pourrait donc y avoir une classe d'hypothèses H aléatoires pour lesquelles le problème de minimisation du risque adverse a une solution h * avec un faible risque contradictoire

  . Nous démontrons que pour toute hypothèse h ∈ H Lip , il est possible de borner supérieurement l'écart entre le risque et le risque contradictoire de h. Ce résultat indique qu'une bonne approximation du problème de minimisation du risque -Problème (D. ) -sur H Lip est également une bonne approximation de la minimisation du risque contradictoire -Problème (D. ). Cela signi e que H Lip est un bon candidat pour répondre à Q . . Nous démontrons ensuite qu'il est possible de borner supérieurement l'écart de généralisation de toute hypothèse h dans H Lip . Cela signi e que, pour un ensemble d'apprentissage su samment important, la résolution du problème de minimisation du risque empirique -Problem (D. ) -sur H Lip peut fournir une bonne solution au problème de minimisation du risque théorique. En n, nous analysons la stabilité du mode des classi eurs randomisés, ce qui nous permet de présenter un point de vue probabiliste sur un ensemble de techniques existantes regroupées sous l'appellation de lissage randomisé [ , , , ]. Notre point de vue sur la randomisation en tant que stratégie de défense pourrait ouvrir la voie à une étude plus approfondie du lissage randomisé d'un point de vue théorique. Ces résultats nous permettent également d'o rir la réponse suivante à Q et à Q . Il existe des catégories de classifieurs aléatoires pour lesquelles nous pouvons contrôler l'écart entre le risque adverse et le risque standard.

  . L'injection de bruit est une méthode utilisée depuis longtemps dans les tâches d'apprentissage et de traitement du signal [ , , , ]. Elle a également été largement étudiée dans plusieurs domaines de l'apprentissage supervisé et de l'optimisation -par exemple en optimisation robuste [ ] ou dans les techniques d'augmentation de données [ ]. Parallèlement à nos travaux, d'autres techniques d'injection de bruit ont été mises en place par la communauté de la classi cation adverse [ , ]. En particulier, Lecuyer et al. [ ]

  . )Comme les garanties de cette technique ne dépendent ni de la complexité du modèle ni de la loi uniforme des grands nombres, elle constitue un bon point de départ pour l'étude d'un nouveau formalisme. En ce qui concerne les exemples adverses, il convient de noter que certaines méthodes de classi cation, telles que le modèle des k plus proches voisins, se sont révélées robustes face à certaines formes d'exemples adverses [ ]. Néanmoins, des résultats récents [ ] ont également montré que si nous forçons un tel modèle à sur-apprendre -aussi appelé régime d'interpolation [ ], alors les exemples adverses deviennent inévitables, comme cela semble être le cas pour les réseaux de neurones. Cela suggère que le phénomène des exemples adverses est étroitement lié au régime d'interpolation observé dans les réseaux de neurones profonds.. R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J.Ullman. "Algorithmic stability for adaptive data analysis". In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. N. J. Beaudry and R. Renner. "An Intuitive Proof of the Data Processing Inequality". B. K. Beaulieu-Jones, W. Yuan, S. G. Finlayson, and Z. S. Wu. "Privacy-Preserving Distributed Deep Learning for Clinical Data". arXiv preprint arXiv: . M. Belkin, D. J. Hsu, and P. Mitra. "Over tting or perfect tting? risk bounds for classication and regression rules that interpolate". In: Advances in neural information processing Belkin, D. Hsu, S. Ma, and S. Mandal. "Reconciling modern machine-learning practice and the classical bias-variance trade-o ". Proceedings of the National Academy of Sciences Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust optimization. Vol. . Princeton University Press, (cited on pages , , ). . D. P. Bertsekas. "Control of uncertain systems with a set-membership description of the uncertainty." PhD thesis. Massachusetts Institute of Technology, (cited on page ). . A. N. Bhagoji, D. Cullina, and P. Mittal. "Lower Bounds on Adversarial Robustness from Optimal Transport". In: Advances in Neural Information Processing Systems . Curran Associates, Inc., , pp. -(cited on pages , , ). . A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers. "Protection against reconstruction and its applications in private federated learning". arXiv preprint arXiv: B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šrndić, P. Laskov, G. Giacinto, and F. Roli. "Evasion attacks against machine learning at test time". In: Joint European conference on machine learning and knowledge discovery in databases. Springer. Blum, K. Ligett, and A. Roth. "A Learning Theory Approach to Non-interactive Database Privacy". In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Comput-Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, (cited on page ). . G. W. Brown. "Iterative solution of games by ctitious play". Activity analysis of production

					, pp.	-	(cited on pages	, ,	).
	Quantum Info. Comput. : -,	, pp.	-.	:	-	(cited on pages ,
	).
							abs/	.	,
	(cited on pages	, ).
	systems.	, pp.	-	(cited on pages	,	).
	. M. : ,	, pp.	-	(cited on pages	,	).
	. A. .	,
	(cited on pages	, ).
							, pp.	-
	(cited on pages , , , ,	,	).
	. A. ing. STOC ' . ACM, Victoria, British Columbia, Canada,	, pp.	-	(cited on
	page	).
	. S. and allocation : ,	, pp.	-	(cited on page ).

. . . .

Top tier machine learning conferences started launching several workshops on this matter -see e.g. https:// trustworthyiclr .github.io/ or https://icml workshop.github.io/. Note also that the number of paper on this matter have been growing exponentially in the last few years -see e.g. https://nicholas.carlini.com/writing/ /all-adversarial-example-papers.html for vulnerability to adversarial perturbations.

Note that we already de ned the simplex ∆(m) = P({1, . . . , m}), but for consistency of the notations in this chapter we use P({1, . . . , m}).

Remerciements

A uni ed view on privacy and robustness to adversarial examples

Q :

Can we find a class H and a hypothesis h * ∈ H that simultaneously has small standard and adversarial risks?

In chapter , we presented two classes of randomized hypotheses that have good properties both in terms of robustness and accuracy; thus answering Q and Q from a theoretical point of view. Here we continue to answer Q but we give a more practical point of view. More precisely, we present simple schemes to build the above mentioned classes and give numerical results demonstrating their accuracy and robustness. In Section . , we highlight the links between di erential privacy and Renyi-robustness. By analyzing their de nitions, we show that they are based on the same theoretical foundation; therefore, results obtained so far in one domain can be transferred to the other. In Section . , we use tools from the literature on di erential privacy to show that Gaussian noise injection can provide principled robustness against 2 adversarial attacks. Then,

. . Experimental setup

Important remark on the image space we consider

At the time of these experiments, we were using attack implementations that take an image with pixels scaled between -1 and 1; meaning that X = [-1, 1] d . All the above results remain valid in this setting, but we have to adapt the perception thresholds -multiply them by 2. This is why we report results with α ∞ = 0.06 and α 2 = 1.6.

Architecture and training procedure

All the neural networks we use in this section are WideResNets -see [ ] -with 28 layers, a widen factor of 10, a dropout factor of 0.3 and LeakyRelu activation with a 0.1 slope. To train an undefended classi er we use the following hyper-parameters.

• Number of Epochs:

• Batch size:

• Loss function: Cross Entropy Loss

• Optimizer : Stochastic gradient descent algorithm with momentum 0.9, weight decay of 2 × 10 -4 and a learning rate that decreases during the training as follows:

To transform these classical networks into randomized classi ers, we inject noise drawn from Gaussian distributions, each with various standard deviations directly on the image before passing it through the network. Both during training and test, for computational e ciency, we evaluate the performance of the the algorithm over a single run for every images; hence no Monte Carlo estimator is used. However, in practice, the test-time accuracy and accuracy under attack are quite stable when evaluated over the entire test dataset.

Remark . To train a neural network with adversarial training we use the same hyper-parameters as above, and generate adversarial examples during training using an

∞ adversary with 7 iterations. Furthermore, we want to build state-of-the-art models; hence we use data augmentation during the leaning procedure -which explains some di erences with the results from Chapter .

Threat models

To compare the empirical performances of our method with adversarial training, we consider two p adversaries with thresholds corresponding to CIFAR datasets

A. Related works and perspective to defend against multiple perturbations

As we have discussed several times in this manuscript, the construction of a defense mechanism against an p adversary does not guarantee protection against any other type of attack. Furthermore, no uni ed framework allows to simultaneous protect against multiple threats yet. In this appendix, we re ne the geometric analysis presented in Chapter and explain why it is di cult to deal with several threats simultaneously. We also provide a number of empirical insights to illustrate this phenomenon in practice. We then review some of the existing defense mechanisms that attempt to defend against multiple attacks by mixing defense strategies. The rest of this appendix is organized as follows. In Section A. , we conduct a theoretical analysis to show why ∞ defense mechanisms cannot be robust against 2 attacks and vice versa. We then corroborate this analysis in Section A. with empirical results using real adversarial attacks and defense mechanisms. In Section A. , we discuss some recent related works that try to build defenses against multiple adversarial attacks.

A. No free lunch for adversarial defenses -a theoretical approach

In this section, we show both theoretically and empirically that defense mechanisms that protect against ∞ attacks cannot provide adequate protection against 2 attacks. Our reasoning is perfectly general, so we can demonstrate the reciprocal assertion in the same way, but we focus on this side for the sake of simplicity.

B Unsupervised learning under di erential privacy constraints

This appendix is based on the individual and joint works of Anne Morvan and Rafael Pinot. We refer the interested reader to the following manuscripts for an in-depth analysis of all the concepts and contributions associated with this appendix.

• "Graph-based Clustering under Di erential Privacy".

Uncertainty in Artificial Intelligence (UAI)

. R. Pinot, A. Morvan, F. Yger, C. Gouy-Pailler, J. Atif.

• "Contributions to unsupervised learning from massive high-dimensional data streams".

PhD thesis PSL University

. A. Morvan. • "Minimum spanning tree release under di erential privacy constraints".

Master thesis Sorbonne University . R. Pinot.

Finally, to access implementation details, one can refer to the following Github repositories. In this appendix, we present an overview of another line of research we investigated in this thesis, namely unsupervised learning under di erential privacy constraints. More precisely, we developed a di erentially private clustering algorithm for arbitrarily-shaped clustering of nodes in a graph. The results we present here are somewhat orthogonal to the main object of the manuscript, but they represent advances in the eld of di erential privacy which is closely related to robustness as we discussed in Chapter . In Section B. , we rst present the key concepts of node clustering in a graph and summarize our ndings in this domain. We then introduce clustering based on differentially private graphs and present our main contributions in this area in Section B. . Finally, Section B. presents some numerical results.

Reading note. We only provide a very light introduction to our contributions and we deliberately skip a lot of technical details and state informal results for simplicity. The interested reader will find above references and source code for a more detailed reading.

B. Graph clustering and minimum spanning tree

Notations. Let G = (V, E, w) be a simple undirected weighted graph with a vertex set V , an edge set E, and a weight function w := E → R. We call G = (V, E) the topology of the graph, and W E denotes the set of all possible weight functions mapping E to weights in R. Cursive letters are used to represent weighted graphs and straight letters refer to topological arguments. Since graphs are simple, the path P u-v between two vertices u and v is characterized by the ordered sequence of vertices {u, . . . , v} or the corresponding binding edges depending on the context.

Weighted graphs are known to be a useful representation of data in many areas of computer science, such as bioinformatics or network analysis -be it social, computer or information networks. More generally, a graph can always be thought of as a representation of data dissimilarity where the points in the dataset are the vertices and the weighted edges express the distances between these objects. In both cases, graph clustering [ ] is a key tool for understanding the underlying structure of the datasets by locating groups of nodes ruled by a speci c similarity. Furthermore, the minimum spanning tree is known to help recognizing clusters with arbitrary shapes in tree-based clustering algorithms. It thus can be used for a wide range of applications [ , , , , ]. step an edge that is incident to S V to update the edge set, and updates the node set accordingly. Theorem states that using PAMST to get an almost minimal spanning tree topology preserves weight-di erential privacy.

Theorem

(Privacy for PAMST -Informal). PAMST is -di erentially private on the set of simple undirected weighted graphs, where depends on the type of exponential mechanism we use.

PAMST exhibits a weight approximation error of O |V | 2 /|E| log |V | for xed privacy parameters, and a time complexity of O(|V | 2 ). This result, in contrast to previous works, enables to deal with relatively large, and dense graphs, which are frequently met in machine learning applications. For more details on the design of the algorithm and the privacy guarrantees, one can refer to [ ]. Thanks to the above and to the data-processing inequality, we get a di erentially private clustering algorithm by combining PAMST and DBMSTC algorithms that we call PTC .

B. Experimental validation

To verify the e cacy of PTC for varying levels of privacy, we have performed experiments on two classical synthetic graph datasets for clustering with non-convex shapes: two concentric circles and two moons, both in their noisy versions. Before analyzing the results, let us brie y present some details of the experimental protocol.

Experimental protocol

For the readability and visualization purposes, both graphs are embedded into a two dimensional Euclidean space. Each dataset contains 100 vertices represented by a point of two coordinates. Both graphs have been built with respect to the homogeneity condition from Theorem . In practice, the complete graph -graph where all vertices are connected -has been trimmed from its irrelevant edges, i.e. the edges not respecting the homogeneity condition. Hence, those graphs are not necessarily Euclidean since close nodes in the visual representation may not be connected in the graph. Finally, weights are normalized between 0 and 1, and α is set to 0.1.

Figures B. and B. show for each dataset (a) the original homogeneous graph G we built, (b) the clustering partition of DBMSTC with the underlying MST. We compare this benchmark with the clustering partition for PTC with di erent privacy degrees -resp. (c) = 1, (d) = 0.7 and (e) = 0.5 . Each experiment is carried out independently and the tree topology obtained by PAMST will be di erent. This explains why the edge between clusters may not be the same when the experiment is repeated with a di erent level of privacy. However, this will marginally a ect the overall quality of the clustering.

Results

As expected, DBMSTC -(b) -recovers automatically the right partition and the results are shown here for comparison with PTC . For PTC , the true MST is replaced with a private approximate MST obtained using PAMST. When the privacy degree is moderate, i.e.

Although we could take any > 0, it is usually chosen in (0, 1] [ , Chap & ].

. F. Croce

. C.

ABSTRACT

Machine learning models are part of our everyday life and their weaknesses in terms of security or privacy can be used to harm us either directly or indirectly. It is thus crucial to be able to account for, and deal with, any new vulnerabilities. Besides, the legal framework in Europe is evolving, forcing practitioners, from both the private and the public sectors, to adapt quickly to these new concerns.

This thesis studies how to build safer machine learning models. In particular, we focus on a new security concern called adversarial attacks. The vulnerability of state-of-the-art models to these attacks has genuine security implications especially when models are used in AI-driven technologies, e.g. for self-driving cars. Besides security issues, these attacks show how little we know about the models used everyday in the industry, and how little control we have over them.

We provide some insights explaining how adversarial attacks work, and how to mitigate them by using statistical learning theory as well as probability and information theory.

MOTS CLÉS