Haroun, Tahir, Karine Damien Nabil

Zakaria

Kun, Rémi Guillaume D Laurent

Elisabeth François

Eline Tristan Quentin

Keywords: Robustness, Deep Learning, Robust Optimization, Coverage, Lipschitz constants

I wouldn't fail to thank my family for their support:

Résumé

Le plus grand enjeu actuel de l'apprentissage profond n'est plus la puissance de calcul ni son cadre applicatif qui n'a cessé de s'étendre au cours des deux dernières décennies mais la robustesse des modèles induits. En effet, alors que les applications touchent des domaines industriels critiques variés comme la voiture autonome ou la gestion de réseau électrique, la nécessité de fiabilité, d'explicabilité et de robustesse en intelligence machine en est acerbée. Cependant, et malgré des années de recherche et une communauté de plus en plus active sur le sujet, nous en sommes encore aujourd'hui à un manque de consensus concernant la démarche de certification des réseaux de neurones profonds pour les applications à haut risques. Cette question a attiré de nombreux chercheurs de domaines variés qui ont donc produit des algorithmes et des garanties de forme multiple. Dans cette dissertation nous explorons plusieurs approches où nous détaillons, quand cela est applicable, l'étendue des garanties/algorithmes fournis. Ce travail commence par un état de l'art général des dernières avancées et des méthodes pour la robustesse qui va servir à situer les chapitres qui suivent au sein de la littérature. Ensuite nous examinons de manière empirique une analogie qui lie la robustesse et la notion de couverture: nous démêlons ces deux concepts à l'aide d'une série d'expériences impliquant une nouvelle métrique de couverture sousdifférentiable. Nous appuyons nos résultats par une grande diversité de modèles et de bases de données. Par la suite nous proposons une approche nouvelle pour tester la performance des algorithmes calculant la constante de Lipschitz de réseaux de neurones (cette dernière étant intimement liée à la robustesse). Actuellement ces algorithmes sont testés sur des cas réels où la vraie constante de Lipschitz est inconnue. Nous fournissons des cas tests avec une constante de Lipschitz donnée qui sont construits de manière la plus générale possible pour pouvoir comparer de manière objective les algorithmes qui visent à majorer ou approcher la constante de Lipschitz. Pour finir nous présentons un nouvel objectif de substitution pour approcher le problème d'optimisation robuste distributionnelle d'un réseau de neurones. Notre méthode bénéficie de garanties de convergence sous le couvert d'hypothèses raisonnables. Nous présentons des exemples pratiques où notre optimisation lissée donne des résultats équivalents si ce n'est meilleurs que les méthodes état de l'art non garanties de converger.

Mots clés:

Robustesse, Apprentissage profond, Optimisation Robuste, Couverture, Constantes de Lipschitz.

Chapter 1

Introduction: The numerous problems of robustness 1.1 The problem of robustness, the thorn in the side of modern learning of neural networks

Deep Neural Networks (DNNs) are nonlinear models that, unlike any other model, resort to millions or billions of parameters that are optimized jointly to tackle one given specific task. Applications cover numerous problem types in statistical learning such as regression, classification, unsupervised learning and policy learning, just to name a few. They often provide gains of performance over traditional methods by benefiting from large datasets, that have become more common in the digital era. They are, in practice, very suited for diverse tasks and data structures with dedicated architectures such as convolution networks [START_REF] Lecun | Handwritten Digit Recognition with a Back-Propagation Network[END_REF] for vision tasks or transformers networks [START_REF] Vaswani | Attention is all you need[END_REF] for sequential data. As of today no model has had this broad scope of applications and this can be mostly explained by the simplicity of use of these technologies, along with the increase of parallel computing on dedicated hardware such as Graphical Processing Units (GPUs). Yet the reasons for this versatility and this unprecedented level of performance are still missing and thus cannot replace existing, well understood and certified technologies. DNNs could be used in addition to more traditional methods relying on simpler decisionmaking processes in order to support traditional approaches: DNNs are able to consider broader information and identify a pathological example that would have been overlooked otherwise. This can be a crucial advantage as a better prediction model means that safety margins can be reduced due to a higher confidence on a diagnosis. For instance, a more accurate medical diagnosis means being able to give to a patient the correct treatment in the adequate quantity. However, some of these applications have heavy implications in terms of safety and ethics that cannot be overlooked: these are called critical applications.

Critical applications are use cases with costly material or human stakes such as autonomous driving or collision avoidance systems [START_REF] Julian | Deep Neural Network Compression for Aircraft Collision Avoidance Systems[END_REF], that therefore need a high level of validation and extended testing. The thorough validation and testing of DNNs are relevant to the point that public legislators are currently adapting their policy to account for, what they call, "high risk applications" for artificial intelligence. The most striking example is the AI (Artificial Intelligence) act [START_REF]Proposal for a regulation laying down harmonised rules on artificial intelligence[END_REF]: a proposal to define and regulate on a European level use cases that fall into the scope of critical applications. The non-exhaustive list of high risk applications concerns biometric and categorization of natural persons, management and operation of critical infrastructure (health, aeronautics, power grids, road traffic), educational and vocational training, access to private services or public services, law enforcement, migration and border control management along with administration of justice and democratic processes. In these fields, ill decision-making can lead to drastic money loss, unfairness and more importantly can have a real negative impact on people's lives. Recently, concerns about fairness were acerbated since statistical algorithms have been shown particularly skilled at reproducing biases and discrimination that might lie in man-made training sets [START_REF] Crawford | There is a blind spot in AI research[END_REF][START_REF] Chouldechova | Fair prediction with disparate impact: A study of bias in recidivism prediction instruments[END_REF]. A certified system should then be able to provide risk mitigating measures, a validation of the design choices and the data used, an appropriate documentation, measures to ensure robustness and logs that should, when possible, be accessible to users. The AI act explicitly mentions that a compliant AI requires technical solutions to "address AI specific vulnerabilities", namely "data poisoning" and "adversarial examples". Providing a robust and interpretable model that fulfills all these certification requirements is one of the current challenges in statistical learning.

The stakes of robustness

A few notions are thus key to understanding the stakes of these requirements: a. Interpretability and how it relates to responsibility. b. Adversarial attacks and how they endanger modern deep learning. c. Robustness and how it can address vulnerabilities. d. Validation and how it is essential for certifying DNNs for an industrial application.

Interpretability/explainability and its link to responsibility. A first diagnosis tool in order to understand and explain a given misconduct of a statistical model is interpretability. It seeks to highlight causal relations between inputs and outputs of a model by striving to answer two basic questions: "Why on this example this decision was made over another?" and "On which element(s) of the input the decision relies?". The end goal here is to identify local causes that could enlighten the responsibility in the case of a wrong decision. Unfortunately, the complexity of the models usually comes at the cost of interpretability: it becomes far more complex to understand the decision-making of the algorithm when considering a nonlinear model and high dimensional inputs. Researches on interpretability highlighted that occasionally the prediction is based on naive or shortsighted elements. This is referred to as the "Clever Hans" effect [START_REF] Pfungst | The horse of Mr. Von Osten): a contribution to experimental animal and human psychology[END_REF][START_REF] Lapuschkin | Unmasking Clever Hans predictors and assessing what machines really learn[END_REF], named after a horse Hans that was supposedly able to make arithmetic however, as it turned out, it was simply enumerating with his hoof until he heard the crowd cheering. The "Clever Hans" effect in machine learning encompasses all abuse of contextual information or bias in the dataset to perform the diagnosis or decision. For instance, when a model resorts to an embedded caption or symbol in the image rather than the actual content to make the decision. These findings display a difficulty of knowing whether the cognitive system has actually learned the object of our interest rather than resorting to simpler proxies of it [START_REF] Searle | Minds, brains, and programs[END_REF]. Such misguided learned correlations can be exploited and having proper diagnosis tools is thus essential for explaining a potential misconception. Interpretability is beyond the scope of this dissertation and we will not elaborate further on the matter, but it is worth noting that it is key to empirically understand the decision-making process and can provide insights that can be leveraged for improvements.

Adversarial samples jeopardize modern deep learning.

Adversarial examples are carefully designed light noises that are crafted explicitly to fool the decision-making of neural networks [START_REF] Szegedy | Intriguing properties of neural networks[END_REF]. The adversarial samples are often indistinguishable by a human oracle from the original sample. It questions whether the model really inferred some relevant features in the process of training and if the identified representations are robust. The reason behind the existence of adversarial attacks is not fully understood yet but it appears to be an unavoidable effect of high dimension of the input space [START_REF] Goodfellow | Explaining and Harnessing Adversarial Examples[END_REF][START_REF] Shafahi | Are adversarial examples inevitable?[END_REF][START_REF] Mahloujifar | The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure[END_REF]. Some attacks can be reproduced through the means of patches or specific occlusions that perturb the prediction of vision algorithms in real-world settings [START_REF] Wu | Making an invisibility cloak: Real world adversarial attacks on object detectors[END_REF][START_REF] Kurakin | Adversarial examples in the physical world[END_REF]. Adversarial attacks are a key security issue if deep learning based algorithms are, for example, used in autonomous driving, where someone could exploit the vision algorithm of a car to have it select a wrong decision. As of today, there are no procedures that can prevent 100% of adversarial attacks, but there are empirical and theoretical methods to mitigate their effects. A possible safety could be to add filters upstream in the form of anomaly detection mechanisms [START_REF] Liang | Principled detection of out-of-distribution examples in neural networks[END_REF][START_REF] Lee | A simple unified framework for detecting outof-distribution samples and adversarial attacks[END_REF][START_REF] Paudice | Detection of adversarial training examples in poisoning attacks through anomaly detection[END_REF] so that adversarial attacks could be removed before being processed through the network. However, such techniques are often based on neural networks themselves that are also vulnerable to attacks. The most promising defenses against adversarial samples are based on dedicated training procedures such as adversarial training [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF][START_REF] Carlini | Towards Evaluating the Robustness of Neural Networks[END_REF][START_REF] Zhang | Theoretically Principled Trade-off between Robustness and Accuracy[END_REF] or regularizations [START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF][START_REF] Zhang | Theoretically Principled Trade-off between Robustness and Accuracy[END_REF][START_REF] Bungert | CLIP: Cheap Lipschitz Training of Neural Networks[END_REF] that incorporate robustness directly in the training of the network. These approaches are closely tied to the concept of robust learning: an ideal robust training should discard the existence of these litigious samples or at least downplay their effects. Robust learning considers a possible set of perturbations (in which lie adversarial samples) and tries to find the optimal model that remains stable with respect to these alterations. In real-life settings these perturbations can be, for instance, uncertainties in sensor measurements as elaborated in the next paragraph.

Mitigating the effects of uncertainty with robustness. All physical systems are plagued by uncertainty: sensors, cameras, probes or human assertions are subject to perturbations that need to be taken into account when performing any form of statistical learning. Uncertainty can be random, systemic or a combination of both. At a macroscopic scale, it can be categorized into two types [START_REF] Gal | Uncertainty in Deep Learning[END_REF]: first, epistemic uncertainty comes from the lack of knowledge in the phenomenon we are trying to explain, for instance, if an explanatory variable is missing or if we are fitting a linear model on a second order function. Secondly, aleatoric uncertainty is mostly non-compressible noise on the observed variables such as white noise. In the following we will only consider aleatoric uncertainty since adversaries only modify the observed input space and alterations on unobserved variables have no influence on the prediction. Such uncertainties cannot always be detected and removed before processing the information through the model, but it remains possible to take them into account to some extent in the optimization problem. A naive but efficient idea is to assess what is the overall effect of uncertainty on the prediction: by propagating the uncertainties throughout the system it is possible to apprehend the resulting alterations on the prediction. Of course, this can only be achieved if the uncertainty of the input is known, which is rarely the case in practice. On the other hand, robust optimization [START_REF] Ben-Tal | Robust Optimization[END_REF][START_REF] Dp Bertsekas | Control of uncertain systems with a set-membership description of the uncertainty[END_REF] can tackle problems where only the support of the uncertainty is known. But this drastically increases the complexity of the learning problem since the optimization procedure of the parameters needs to account for any possible perturbation in the uncertainty support. This support has to be defined the closest possible to the real perturbation otherwise this might provide over-conservative solutions [START_REF] Shafieezadeh-Abadeh | Distributionally Robust Logistic Regression[END_REF]. Models resulting from robust optimization might be penalizing for regular use, but on the other hand they mitigate the worst possible scenario in the range of possibilities. This ultimately ensures a robust behavior of the model.

Validation and its role in certification.

There is an ambiguity in the literature on the terms certification and validation where they are often used to name similar concepts. To avoid any confusion, we first elaborate on these two notions. Verification [START_REF] Huang | A survey of safety and trustworthiness of deep neural networks: Verification, testing, adversarial attack and defence, and interpretability[END_REF] is a method to assess exactly if a formal assertion is met on a system: for instance, in an industrial context, it is essential to verify that a solution abides by the technical specifications composed of design constraints. In the context of statistical learning, this could be asserting if the prediction of a model does not change under some perturbations. Certification stands for a list of requirements which are legally needed for a technology to be put into a production state and made available to the public under any kind of retail contract. This list of requirements has to be formulated by a public legislator and ensures that ethics and safety questions have been addressed during the design process and it can include verification of multiple statements. As of today there is little consensus over a general certification process for DNN-based systems. However, some conditions have unanimous backing: on the one hand, a system has to be verified to work even though it is subject to uncertainties, as detailed previously. On the other hand, a statistical decision system has to be proven to work on a production environment that may be slightly different than the training environment. Indeed if the production environment is too far from the training environment then the guarantees proven on the one cannot be applicable to the other (for instance if the inference environment has a different floating precision, or if it is assessed on unseen data). The production environment is usually different from the training one since statistical models are commonly used for interpolating, or if industrial constraints enforce the use of specific software or hardware. But current methods for verification can only provide limited guarantees around training points [START_REF] Cohen | Certified Adversarial Robustness via Randomized Smoothing[END_REF][START_REF] Wong | Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope[END_REF][START_REF] Katz | Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks[END_REF]. There are a lot of challenges for testing points: the robustness of the prediction is difficult to assess since we theoretically have no way of computing the proximity of a testing sample to a training sample with the knowledge of the trained model only. Certification and validation are two heavily recommended steps to attest of the robustness of a neural network. Unfortunately, verification methods that provide a training procedure are scarce ( [START_REF] Wong | Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope[END_REF] for instance). In current practice, the usual methodology relies on using any robust training method at training times to increase the safe bounds probed subsequently by verification algorithms. Ultimately a verification method that helps provide information on how to improve the training would be an all-in-one procedure to make neural networks robust.

In the light of the previous considerations, robustness appear as the focal point of modern deep learning. We will dedicate the next section to a thorough discussion on this concept.

Robustness definition

The aim of this section is to clarify the notion of robustness in statistical learning and to explain what to expect from robust models. Ultimately, we will highlight flaws in the current way of dealing with robust learning. In order to give a proper definition of robustness, we first propose to list some key related facts:

(a) Statistical learning is impossible to achieve without some regularity. We are performing interpolation from finite datasets to other finite test sets that may differ entirely from the already seen data. If no other assumption is made regarding the model or the data distribution, there is no reason that the learned model would perform any good on the test set. Indeed, it may prove completely wrong the learned model on the training set. A usual implicit and necessary assumption is that the observed phenomenons have some underlying structure and some limited variations along this structure. Statistical learning is nothing but understanding and exploiting this latent structure.

(b) Uncertainties over explanatory variables need to be accounted for. Uncertainties regarding the input information have to be dealt with when building a robust model. This may be done by building safety zones around input samples where the prediction should be constant. This is the dominating vision of robustness that assumes separability of the data, yet, it may not hold on more complex datasets.

(c) Robustness over a dataset is not the robustness over the points in the dataset. Robustness safety bounds may collide between one another, and dealing with this case naively by building the biggest possible safe zone ends up in overfitting the data. This puts into perspective the previous point where safety zones were an obvious solution to uncertainties. It is essential to consider conflict in the robustness zones in case there are outliers or mislabeled inputs.

(d) Labels may be subject to perturbations as well. In some cases (conflicting information in an image, mislabelling because it is man-made), having one single label over a sample is not guaranteed. Building a robust prediction needs to reflect such uncertainty or has to reduce the impact of an obviously wrong label in the dataset. It is essential to take into account possible label misspecifications (or output uncertainty in the case of regression) along with input uncertainty.

(e) Our models are not flawless. Many supporters of DL invoke the universal approximation theorem [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF][START_REF] Leshno | Multilayer feedforward networks with a nonpolynomial activation function can approximate any function[END_REF] to justify the use of deep neural networks on a given application. This existence theorem is very powerful but it does not provide any practical way of finding the existing approximator nor does it give the architecture that would achieve so. On top of this, it assumes that we possess complete information about the problem regardless of uncertainties related to input/outputs. Neural networks will fail to achieve global optimality since our methods are merely approximating an optimal configuration and optimal parameters: there are still lingering errors coming from our optimization methods.

What is robustness? A general definition of robustness

In order to give a definition of robustness we first need to assume that the data has some form of structure on which interpolating has meaning. Robustness, then, denotes the principle by which a model or an estimator is stable against light perturbations over the structure of the data or parameters [START_REF] Peter | Robust Statistics[END_REF]. In the context of building a predictive system, it may be rephrased in a more explicit manner: a robust statistical model provides a prediction that is reasonably insensitive to small perturbations either to its parameters, inputs or outputs over their respective structure. Ultimately, a "robust statistical model" is an antithesis since it has to be, on the one hand, robust and thus stable to modifications and on the other hand it has to provide different decision if the inputs were to change (hence the emphasis on the word reasonably). This indicates that in our given framework of statistical learning, bringing robustness actually means making compromises between the generalization of the model and its robustness.

Robust learning, a compromise between generalization and robustness

We call generalization the performance of a model on the real -and often unknown-data distribution. An accuracy on a finite test set is a proxy of the generalization that is valid only if the test set is representative of the real set with small error. There exists a trade-off between robustness and generalization: the more robustness is sought the lower the generalization capacity will be. This has been shown in multiple papers [START_REF] Tsipras | Robustness May Be at Odds with Accuracy[END_REF][START_REF] Su | Is Robustness the Cost of Accuracy? -A Comprehensive Study on the Robustness of 18 Deep Image Classification Models[END_REF][START_REF] Zhang | Theoretically Principled Trade-off between Robustness and Accuracy[END_REF][START_REF] Raghunathan | Understanding and Mitigating the Tradeoff between Robustness and Accuracy[END_REF][START_REF] Raghunathan | Adversarial Training Can Hurt Generalization[END_REF][START_REF] Yao-Yuan | A Closer Look at Accuracy vs. Robustness[END_REF] that robustness and generalization are, to some extent, concurrent objectives. In order to illustrate this compromise on a simple example, let us consider a simple binary classification of four points presented in Figure 1.1. A naive yet reasonable way of enforcing robustness could be to have safety zones around the point where the predicted class does not change. This explicitly makes the prediction robust to small uncertainties and if the safety zones are rather small they do not conflict. Yet, if one wants to increase the size of these safety zones as presented in Figure 1.2 there appears conflict and dealing with this case is not trivial. One could seek to build the biggest safety zone close to each point as depicted in Figure 1.3 but this falls into the trap of a nearest neighbor algorithm that has well-known overfitting issues and is not robust. Another possible method could be to assign a label based on the most represented label among safety zones overlapping the point: this would provide the most robust outcome at the cost of some accuracy in the prediction. One cannot expect a model to be able to make swift changes in its decision process and to be stable regarding any modifications of the input as well. The only way to prevent any perturbation of the decision function is to have a prediction that is completely insensitive to its inputs, i.e. a constant model. This does not condemn the search for both robust and accurate models, however, the questions are: what level of robustness do we need to achieve and which toll does it take on generalization? Ideally, one should seek the Pareto front of robustness versus generalization in order to select the best compromise according to the context or application, assuming robustness and generalization can be quantified reliably.

How robustness is addressed in the litterature?

We will distinguish 3 different sources of uncertainty, although they can all be combined altogether. These different sources have had historically separated approaches to deal with each of them. All approaches assume that there exists a regularity in the data (a), yet they tackle different robustness problems:

Robustness regarding the parameters/model (addressing (e))

Bayesian approaches in statistical learning aim at building decision systems where parameters are uncertain: an assumed prior distribution of the parameters, that encompasses our lack of confidence regarding the value of the parameters, is updated considering the input data. Ideally, the more data is observed the more narrow the posterior distribution becomes. Thus, our confidence in our parameters and in the resulting prediction increases. If the posterior distribution does not narrow, this usually means that the model cannot grasp the full extent of the phenomenon at hand and thus displays the lack of robustness of the model. Bayesian inference can be applied to small neural networks [START_REF] Radford | Bayesian Learning for Neural Networks[END_REF][START_REF] David | Bayesian Methods for Adaptive Models[END_REF] but it is difficult to extend them to large neural networks. Some efficient approximations are possible with variational inference [START_REF] Blei | Variational inference: A review for statisticians[END_REF] or rougher approximations with Monte Carlo dropout [START_REF] Gal | Uncertainty in Deep Learning[END_REF].

Robustness regarding the prediction (addressing (d))

The existing literature typically considers the case of robustness against label noise that may happen [START_REF] Angluin | Learning from noisy examples[END_REF]3,[START_REF] Yan | Learning from multiple annotators with varying expertise[END_REF] as a consequence of poor mechanisms for attributing the prediction result, for instance man-made labelling. It has become essential for algorithms to take into account possible corruption in the target value. For classification settings the stability assumption specific of robust problems is the fact the correct label is given randomly with a probability greater than 1 2 . For regression settings the true value is assumed to be in a close neighborhood of the given reference value. Output uncertainty might be caused by input uncertainties themselves [START_REF] Saltelli | Global Sensitivity Analysis. The Primer[END_REF].

Robustness regarding the input space (addressing (b) and (c))

This is, by a wide margin, the robustness that is the most studied in nowadays robust learning: it considers perturbations (either small or large) on the explanatory variables. Such interest of the community around input uncertainty comes from the fact that adversarial attacks are yet an unresolved challenge in deep learning. The literature mostly differs on the nature of the "small perturbations" along which one needs to build resistance, since the notion of closeness varies loosely with the data under consideration. For instance, in R 2 the closeness of two samples is quite straightforward. However, the closeness of two images is more complex than a pixel to pixel distance: we expect slight translations/rotations of images to trigger the same decision by the algorithm even though the example are far apart when considering a euclidean distance. As of today, possible perturbations have been characterized into two macro groups: attacks based on bounded perturbation balls are called restricted attacks as opposed to unrestricted attacks such as light rotations, translations and deformations. Methods to reduce the impact of input uncertainties are diverse: besides from building models that has an inner regularity [START_REF] Meunier | Mixed Nash Equilibria in the Adversarial Examples Game[END_REF][START_REF] Cissé | Parseval Networks: Improving Robustness to Adversarial Examples[END_REF], the most used method for taking into account these uncertainties remains to sample from these perturbation sets and to find the model parameters that mitigate the most the error with respect to these perturbations [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF][START_REF] Goodfellow | Explaining and Harnessing Adversarial Examples[END_REF][START_REF] Xiao | Spatially transformed adversarial examples[END_REF][START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF]. There are attempts at providing networks that are robust to both types of attacks [START_REF] Raff | Barrage of random transforms for adversarially robust defense[END_REF], but the approach is overall empirical as the authors used a broad range of man-selected perturbations regardless of any notion of distance. The issue is that the perturbations under consideration are always too specific: the literature lacks of computable, guaranteed methods to mitigate all possible perturbations in a given ball.

The need for robustness in an industrial context

Safran, an aeronautic company designing aircraft engines and onboard systems, has seen DNN use cases emerge in several of its applications as ways to provide better embedded systems with, among others, monocular depth assessment [START_REF] Moukari | Deep multi-scale architectures for monocular depth estimation[END_REF], improved predictive maintenance for aging mechanical systems [START_REF] Pineau | Unsupervised ageing detection of mechanical systems on a causality graph[END_REF] or simulation acceleration [START_REF] Daniel | Model order reduction assisted by deep neural networks (ROM-net)[END_REF]. Although gains have been showcased in all these applications, they were rarely put into production for four main reasons:

1. The difficulty of adapting the technology to production environments: the process of transferring a technology from a research department to production has multiple hurdles. For instance, the hardware in production is certified and is not as flexible as the one used in research. On top of that the specifications that need to be respected depend on each application, making this procedure impossible to generalize over a broad range of applications.

2. The fact that an official procedure for certifying the use of DNNs is still missing: the list of requirements is to be elaborated by a collaboration between a public legislator and academic researchers. Industrial actors might have a conflict of interest if they were to design such a document.

3. The presence of vulnerabilities such as adversarial attacks: this is up to the company to provide a system that is the safest possible, this implies building up methodologies that can infuse robustness into DNN solutions.

4. Being able to provide justification for the predictions devised by the algorithms: the research around explainability can be applied to a broad class of models during inference time so as to find the causes of a given prediction. It is up to the company offering a service to provide an explanation mechanism along.

A business that is aiming to sell a technology that resorts to statistical learning can only advance on points (3) and (4). Point ( 1) is application dependent, while point (2) relies on an independent entity, thus making both of them unfit for our study. Point (3) is the main focus of this thesis since it precedes point (4) to some extent: the conception of the robust model might provide by design an explanation of the decision (for instance, using a linear model provides a direct explanation of the influence of each input). Robustness is the aspect that needs the most consideration from an industrial standpoint since its goal is to provide general methodologies to ensure the validity of DNNs over a broad range of problems.

Blind spots in the robustness literature and driving questions of the dissertation

Robustness is central to theoretical deep learning and it is needed from an industrial standpoint. We raise some key questions that need to be addressed in the making of a robust model:

(Q1) Is there a well identified cause or reason for the lack of robustness in DNN models?

(Q2) What are the key metrics that can quantify reliably a level of robustness? (Q3) What kind of perturbations is it legitimate to consider? Are there more general perturbations than others?

(Q4) Are we able to know, and perhaps model, all kinds of uncertainty that a DNN is exposed to?

(Q5) How one can change the learning phase of neural networks to account for the possible perturbations of the input variables?

Contributions

After Chapters 2 and 3 respectively dedicated to the mathematical background and a state of the art, we present different contributions in consideration of the questions above. In particular, we push through three angles focused on testing of neural networks and their robust training.

Coverage testing and the potential link between coverage and robustness

In multilayer neural networks there can be parts of the neural network that do not impact the decision made by the model, mostly because there are nonlinearities between each layer. Such blind spots could be exploited by an attacker to change the prediction of specific samples. For these reasons, the notion of coverage aims at quantifying which fraction of the network is used on a test input distribution. The current literature has presented successful attempts at building coverage guided attacks and coverage guided testing of DNNs [START_REF] Xie | DeepHunter: a coverage-guided fuzz testing framework for deep neural networks[END_REF][START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF].

However, there appears to be little correlations between any of the proposed coverage metrics and robustness metrics [START_REF] Yan | Correlations between deep neural network model coverage criteria and model quality[END_REF]. In order to ascertain if adversarial training or adversarial attacks could benefit from coverage related optimization, we devised a range of experiments to highlight the presence of a possible interaction by considering a variety of models and datasets. The experiments failed to showcase a cross effect between an attack and coverage, as if they were completely different objectives. We however show empirically that using coverage for training a neural network brings robustness in the same fashion that regularization does, but that it does not explicitly make models robust to targeted attacks. This research showed that some appealing analogies in deep learning may be erroneous when considering models in high dimension. This contribution questions the cause of vulnerabilities in modern deep learning (Q1) and is the core of Chapter 4.

Lipschitz prescription for a better robustness assessment

Chapter 5 presents the second part of our research that stems from studying Lipschitz neural networks. Lipschitz continuity is obviously tightly related to robustness as the Lipschitz constant bounds the variations of the model around any given point. The Lipschitz constant of a network is therefore a very good metric showing the robustness of a model against potential perturbations (Q2). Our starting point was to notice that the methods for computing the Lipschitz constant were systematically comparing their performance with concurrent algorithms on either trained models or random networks. However, the discrepancy between the real Lipschitz constant and the one assessed by the algorithm cannot be quantified, since estimating the Lipschitz constant of an unconstrained network is NP-hard [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF]. Only computing a guaranteed upper bound is sound for displaying superiority of one algorithm over another (the one lower is therefore the better), but the distance with the real value remains unknown. As a remedy, we offer to the best of our knowledge the first algorithm for designing a neural network with a prescribed Lipschitz constant. Despite having no convergence guarantees yet, our algorithm provides general architectures with a Lipschitz continuity close to the objective. This opens the path for systematic testing of Lipschitz assessing algorithms on some prescribed architectures by computing their error on their estimation of the Lipschitz constant, their dependence to the different dimensions of the problem (input dimension or parameter dimension) and their behavior around their validity domain. Our findings show that algorithms providing approximations of bounds need to be used with caution: many methods often trade approximation errors with computational performance and/or scalability.

Smoothed robust optimization for deep neural networks

In the previous two contributions, we only focused on testing, i.e. checking the correct implementation of a given neural network. The final step is to devise a training procedure that provides a model which has been designed robust from the start. Among approaches for robust training, we select Wasserstein distributional approaches due to the fact that they engulf local robustness approaches. Moreover, the formalism is general enough to derive results for a broader class of models than neural networks. Unfortunately, current approaches that aim at solving the distributional robust optimization often provide intractable algorithms [START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF][START_REF] Staib | Distributionally Robust Optimization and Generalization in Kernel Methods[END_REF]. This is due to the overall complexity of the inner distributional maximization problem that happens on an infinite dimension space. In Chapter 6 we present a novel approach in order to circumvent this difficulty: we propose a proxy method where the distributional robust objective is cast into an equivalent pointwise robust objective. The latter can then be smoothed into an integral computation in infinite dimension and finally be approximated using Monte Carlo integration. The method enjoys convergence guarantees provided some assumptions on the class of function optimized. We then proceed to show the benefits of using this algorithm on a neural network training where we compare our method with current empirical methods for robust training. The benefits of our algorithm are twofold: while providing at least the same performance in terms of accuracy than concurrent approaches, it also regularizes effectively and implicitly the model. The integral estimation inside our algorithm however adds computational load due to sampling, which may limit its use for high dimensional models. This contribution aims at answering questions (Q3), (Q4) and (Q5).

Chapter 2

Prerequisites and background

This chapter centralizes common notations and the mathematical prerequisites for all chapters. This does not exclude more specific notations to be introduced in the different chapters when judged relevant.

Euclidean spaces

Often dealing with Euclidean spaces we will define the general notations that will be used on all the chapters of this manuscript (mainly the notions of distance, operator norm and balls).

Distance. We note • q , q ∈ [1, +∞] the ℓ q norm. dist(x, C) = inf z∈C x -z is the distance function to the nonempty set C. The set of nearest points of x in C is denoted by P C (x).

Ball and volume. B q r (x) = y, x -y q ≤ r is the ℓ q ball of radius r ≥ 0 centered at x. µ L (S) = S dµ is the volume of a set S. When the superscript is omitted, this refers to the ℓ 2 norm ball.

Operator norm.

Let A be an operator between two normed vector spaces (V, • V ) and (W,

• W ) then the operator norm is |||A||| V,W = sup x∈V Ax W x V . When • W = • V = • 2
we note the operator norm without the subscript (|||A|||) and it is called the spectral norm.

Deep learning

Deep learning is nowadays a broad field from Machine Learning (ML) and it is a form of machine intelligence. At its core lies the neural network, a parametric statistical model and its variants around which revolve more general fields such as optimization, statistical learning and statistics. Deep learning resorts to advances, both theoretical and practical, in all these fields in order to construct a decision-making process with the most accurate prediction. Most modern applications are to be found where data is available and in quantity to be able to determine correctly the numerous parameters of the model. These models have been increasingly used in the last years in fields such as computer vision [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF], language processing [START_REF] Cho | Learning phrase representations using RNN encoder-decoder for statistical machine translation[END_REF], games [START_REF] Silver | Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm[END_REF], MRI scan analysis [START_REF] Selvikvåg | An overview of deep learning in medical imaging focusing on mri[END_REF], molecule shape prediction [START_REF] Senior | Improved protein structure prediction using potentials from deep learning[END_REF], object detection [START_REF] Zhao | Object detection with deep learning: A review[END_REF] but also in physics, biology and manufacturing with unprecedented accuracy and performance. Although very experimental and empirical at first the domain is gaining more and more theoretical consolidations in order to explain, improve and certify these technologies. We will succinctly remind the basics of deep learning models:

One hidden layer neural network. For simplicity of notation, we introduce at first the neural network with one hidden layer. This will simplify the generalization to a multilayer neural network. Let (l, r) ∈ N 2 , Z ⊂ R l × R r be a dataset, (x, y) ∈ Z where x is the input (explanatory variables) and y is the variable that we would like to predict by inference from x. We will build a predictor in order to predict y from x (it has meaning if there is causality or correlation between x and y). With n ∈ N, let us define two linear operators W 1 ∈ R l×n and W 2 ∈ R n×r and two "bias" vectors b 1 ∈ R n and b 2 ∈ R r . We also need to equip our network with an activation function [START_REF] Leshno | Multilayer feedforward networks with a nonpolynomial activation function can approximate any function[END_REF] φ : R → R that can be applied element-wise to the elements of a vector. A single hidden layer network writes:

f 2 (θ, x) = W 2 φ(W 1 x + b 1 ) + b 2 = y pred , (2.2.1
)

with θ = (W 1 , b 1 , W 2 , b 2 ) ∈ Θ.
The notation f 2 anticipates a recursive application of these nonlinear operators (see multilayer neural network in the next paragraph). A neuron in this definition is a component of an affine operator, for instance, neuron k in the hidden layer is the affine operator:

(W 1 x + b 1 ) k = l j=1 w kj x j + b k .
The linear layer is the collection of all the neurons. A neuron network can then be seen as a collection of small linear units organised in layers on all of which we apply some nonlinear function φ.

We select the parameters θ in order to minimize a loss ℓ : R r × R r → R measuring the discrepancy between the prediction f 2 (θ, x) and the real value y.

min θ∈Θ ℓ(f 2 (θ, x), y).
This is not usually made for one point but over all tuples (x, y) drawn from a data probability distribution

ρk = 1 k k i=1 δ (x i ,y i ) where δ (a,b) is the dirac mass in point (a, b): min θ∈Θ 1 k k i=1 ℓ(f 2 (θ, x i ), y i ) = min θ∈Θ E ρk [ℓ(f 2 (θ, x), y)].
For a regression setting ℓ is usually chosen among the euclidean distance, the absolute loss or the Huber smooth loss. For a classification setting ℓ is usually the 0-1 loss or its possible proxies such as a hinge loss or a cross entropy.

Multilayer neural network.

For multilayer neural networks one should simply apply recursively the linear product and activation function to the output of the previous layer: Definition 2.2.1. Given a nonlinear function φ : R → R that can be applied element-wise on a vector, and a set of d ∈ N matrices (W i ) d i=1 with compatible dimensions so that the matrix product W 1 W 2 ...W d is well defined. A linear neural network with biases is a function f : Θ × X → R r , where X ⊂ R l and Θ ⊂ R p is the space of parameters (weights and biases

θ def = (W i , b i ) i∈[d] ) f 1 (θ, x) def = W 1 x + b 1 , f i (θ, x) def = W i φ(f i-1 (θ, x)) + b i , ∀i ∈ [d], f (θ, x) def = f d (θ, x). (2.2.2)
This model has given better experimental results in terms of performance than the one hidden layer one.

In the exact same fashion as the one layer linear network θ ∈ Θ are found by solving an optimization problem:

min θ∈Θ 1 k k i=1 ℓ(f (θ, x i ), y i ) = min θ∈Θ E ρk [ℓ(f (θ, x), y)]. (2.2.3)
This problem can be approximated with any adequate optimizer, yet the most used algorithms are (sub)gradient descents as they are very efficient in case θ has a high dimension. This is a non-trivial approach since this problem is non-convex and non-differentiable if the activation function chosen is not differentiable, for instance: the Rectified Linear Unit (ReLU) [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF]. Nevertheless this approach is gaining serious momentum for its remarkable results.

Although very general and allegedly able to tackle all regression problems just like their shallow counterparts [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF][START_REF] Leshno | Multilayer feedforward networks with a nonpolynomial activation function can approximate any function[END_REF], Deep ReLU networks appear to have an extra advantage at representing complex functions as it has be shown to generalize better [START_REF] Daubechies | Nonlinear Approximation and (Deep) ReLU Networks[END_REF]. Other architectures dedicated to specific tasks have emerged. For instance, Convolutional Neural Networks (CNNs) [START_REF] Lecun | Handwritten Digit Recognition with a Back-Propagation Network[END_REF][START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF] that focus on finding local 2D structures rather than pixel to pixel correlations. Theoretically linear networks should be able to perform equivalently well than CNNs but in practice the prior knowledge incorporated in the structure of CNNs is forcing them to consider spatial correlations which gives them a significant advantage on images. That much is attested by the unrivaled performance of CNNs on image classification tasks and object detection. Ever since the achievements made by CNNs in recognition tasks [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF] the empirical testing around neural networks has spurred and theoretical justifications lag behind.

Robust optimization

Vanilla learning. To ease the notations of the next paragraphs and to provide a smoother introduction to the notion of robust learning we present the "traditional" problem met in optimization: let (Z, d) be a (data) metric space with Z = X × Y ⊂ R m , where X (resp. Y) is the input (resp. output) space. Let ρ be a probability measure on Z, Θ ⊂ R p the parameter/action space, L : Θ × Z → R + a loss function such that L(•, θ) is ρ-measurable for all θ ∈ Θ. Consider the optimization problem:

min θ∈Θ E z∼ρ L(θ, z).
(2.3.1)

In the scope of statistical learning, we have, given a distance/divergence function ℓ : Y × Y → R adapted to the problem (mean square error for regression, cross entropy or hinge loss for classification etc...), for all (x, y) ∈ Z = (X × Y) and θ ∈ Θ:

L(θ, (x, y)) = ℓ(f (θ, x), y).
This draws the link between general optimization and the procedure for finding the parameters of a deep learning model (2.2.3)

Pointwise robust counterpart.

Recalling the notations of equation (2.3.1) , let us define U (x, y) ⊂ R m a bounded uncertainty set that in all generality depends of x and y, then the robust pointwise counterpart of (2.2.3) writes in the form of the minmax problem:

min θ∈Θ 1 k k i=1 max (x,ỹ)∈U (x i ,y i ) ℓ(f (θ, x), ỹ) = min θ∈Θ E (x,y)∼ρ k max (x,ỹ)∈U (x,y) ℓ(f (θ, x), ỹ). (2.3.2) Equation (2.3.
2) means that we are no longer minimizing only on a dataset, but that we minimize the problem with respect to the worst case among the uncertainty set. Uncertainties could theoretically generate unseen configurations or adversarial samples for the statistical model thus one should minimize the impact of uncertainty on the decision model. In case the distribution of uncertainty is well known, it can be included in the learning process and optimized directly with this prior knowledge. In most cases it is not known and it requires a model free approach of learning under uncertainty [START_REF] Ben-Tal | Robust Optimization[END_REF] that is, by essence, much more conservative due to the broad range of possible perturbations. Usually perturbation sets are taken as balls with various distances around the points in the dataset. This is a common model for the perturbation and corresponds to assuming that the prediction of the model should not change when we are close to a known point. Often the uncertainty set is not fully known either and is chosen as a close ball around (x, y) with some ground cost (or distance) c : Z 2 → R, the uncertain set takes the form:

U ǫ (x, y) = {(x, ỹ), c((x, y), (x, ỹ)) ≤ ǫ}.
If the ground cost c is taken to be the ℓ k norm then U ǫ (x, y) = B k ǫ ((x, y). However, the result of (2.3.2) depends heavily on the metric chosen even if ultimately all vector norms are equivalent.

Distributional robust counterpart.

An alternative to the robust pointwise counterpart is to consider perturbation not on the points of the dataset (x, y) but on their distribution ρk . To that extend we consider a distance/divergence D : P(Z) 2 → R between two distributions (P(Z) denotes the positive measures of norm 1 distributed on Z) , most popular choices are Total Variation distance, φ-divergences, Wasserstein distance or Maximum Mean Discrepancy. Thus the Distributional Robust Counterpart writes:

min θ∈Θ max D(ρ,ρ k )≤ǫ E (x,y)∼ρ [ℓ(f (θ, x), y)].
(2.3.3)

Note that in equation (2.3.3) the max and expectancy are reversed compared to (2.3.2) as in the former the perturbation lies on the distribution of the points and on the latter on the points of the nominal distribution. This is particularly suitable when the nominal distributions are discrete samples of a unknown distribution: this formalism allows building a decision system that takes into account the sampling uncertainty of the dataset.

Adversarial attacks and defenses

Adversarial attacks 2.4.1.1 Perturbing one sample

Adversarial attacks are considered to be one of the greatest menace for certifying neural networks and we discussed them in paragraph 1.1.1. We provide here the mathematical framework of such attacks and the methods for computing them. We need to equip ourselves with a neural network f : θ × X → R r as defined in Section 2.2, a loss function ℓ : R r × R r → R and ε > 0. Generally, adversarial attacks are different methods for approximating the argument of the following problem:

max x∈B ∞ ε (x) ℓ(f (θ, x), y). (2.4.1)
Or equivalently with a perturbation variable δ ∈ R p :

max δ∈B ∞ ε (0) ℓ(f (θ, x + δ), y). (2.4.2)
The most popular methods for approximating this problem are using the very same gradient update used for training the model: a gradient backpropagation and then an update. Instead of computing the gradient of the loss with respect of the parameters we compute it with respect to the inputs this allows to alter slightly the inputs of the model and the update is usually performed with projected gradient (i.e. taking the sign of the gradient before multiplying with the step size). As an example we provide in algorithm 1 of the Projected Gradient Descent (PGD) attack: In algorithm 1, P C denotes the projection on set C, sign denote the function that, applied element-wise, returns the sign of each value and G L(θ,•,y) denotes generalized gradient of the function L with respect to x.

L has been chosen equal to the learning loss (i.e. L(θ, x, y) = ℓ(f (θ, x), y) but we can change it to any other appropriated loss that depends of θ, x and/or y.

PGD is thus a procedure that takes a loss function L : Θ × X × Y → R, L(θ, x, y) → ℓ(f (θ, x), y), the parameters θ, a bounded perturbation set C = B ∞ ε (x), a tuple (x, y) of input/output and returns a perturbed input x. Problem (2.4.1) is then approximated via PGD:

ℓ(f (θ, x), y)
where x = PGD(L, θ, B ∞ ε (x), x, y).

(2.4.

3)

The Fast Gradient Sign Method (FGSM) is the one step variant of PGD where the step size γ k is taken equal to the radius of C.

Another interesting approach is the Carlini and Wagner attack [START_REF] Carlini | Towards Evaluating the Robustness of Neural Networks[END_REF] (C&W): it is only applicable on classification settings and differs from the FGSM and PGD attack by the fact that is does not attempts to reduce the likelihood of the currently predicted label but it tries to increase the likelihood of the second most probable label. This is a proxy of problem 2.4.1 as it resorts to unused information during training coming from negative samples. Formally it seeks to approximate using a multi-step gradient descent algorithm the argument of equation (2.4.4):

min x∈B ∞ ε (x),ỹ =y,ỹ∈Y ℓ(f (θ, x), ỹ), (2.4.4)
where ỹ has to lie within the range of possible labels. In practice ỹ is selected as the second most likely output (the first one being usually equal to the real label).

Perturbing batches of samples

For computational efficiency the perturbations x are usually computed in a batched manner since the summed contributions to the loss over the dataset {(x i , y i ), i ∈ [m]} are independent from one another:

∂ ∂x k m i=1 ℓ(f (θ, x i ), y i ) = ∂ ∂x k ℓ(f (θ, x k ), y k ).
Therefore the batched adversarial problem (2.4.1) can be written in a batched manner:

max xi ∈B ∞ ε (x i ),∀i∈[m] 1 m m i=1 ℓ(f (θ i , xi ), y i ). (2.4.5)
We can also write a batched version of problem (2.4.4) for which C&W approximates the argument:

min xi ∈B ∞ ε (x i ),ỹ i =y i ,ỹ i ∈Y,∀i∈[m] 1 m m i=1 ℓ(f (θ, xi ), ỹi ). (2.4.6)
These batched expressions are useful if one wants to add a penalty that encourages the diversity of the perturbations (x) i∈[m] or any other metric mixing the different

(x i ) i∈[m] or (y i ) i∈[m]
. In Chapter 4 we will be using a coverage metric that will be computed over a batch of data thus only the formulation in equation (2.4.5) allows us to achieve as much.

A direct parallel can be drawn between adversarial attacks and the pointwise robust counterpart inner maximization problem: the procedures PGD, FGSM and C&W attempt to approximate the argument of the inner maximization (2.3.2) with an uncertain set of the form of a infinite ball on the input exclusively and no label perturbation.

Adversarial defenses

The goal of adversarial defenses is to mitigate the impact of adversarial attacks. Defenses did not resort originally to adversarial attacks as they initially used regularizations such a weight decay, dropout [START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF] or distillation Chapter 2 2.5. Lipschitz continuity [START_REF] Papernot | Distillation as a Defense to Adversarial Perturbations Against Deep Neural Networks[END_REF]. However these methods were not giving a satisfying performance against adversarial attacks therefore current methods prefer a two step approach: finding a solution x that approximates equation (2.4.1) and then minimize the loss with respect to this perturbation x Let L : Θ×X ×Y → R, L(θ, x, y) → ℓ(f (θ, x), y) be a loss function, θ the parameters of the model, (x, y) an input/output tuple and C a bounded perturbation set. We then define an attack (Attack ∈ {FGSM, PGD, C&W}) as a procedure that takes L, θ, C, x and y and returns a perturbed input x. The adversarial training writes:

min θ∈Θ E (x,y)∼ρ k [ℓ(f (θ, x), y)]
where x = Attack(L, θ, C, x, y).

(2.4.7)

If the attack is exactly computing the maximum in a ball C = B ∞ ε (x) (equation 2.4.1) then the problem becomes exactly the pointwise robust counterpart:

min θ∈Θ E (x,y)∼ρ k max x∈B ∞ ε (x)
ℓ(f (θ, x), y).

(2.4.8)

Therefore adversarial training and the pointwise robust counterpart are one and the same if the attack manages to find exactly the optimal in the neighborhood. That much cannot be guaranteed when resorting to gradient methods on non convex-concave saddle point problem. Nonetheless, this approach is computationally efficient and it has the best performance results on perturbed datasets.

Lipschitz continuity

The Lipschitz continuity is a property that bounds the variations of a continuous non-smooth function: the smaller the constant is, the smaller variations of the function are. This is closely intertwined with the notion of robustness as it gives a direct way of upper bounding the changes of a function with respect to perturbations in its arguments. This is overall a suitable indicator of a well-regularized decision process that can be explicitly enforced or conditioned throughout a dedicated training. Definition 2.5.1. Let X ⊂ R l , l ∈ N and Y ⊂ R r , r ∈ N, equipped with the usual norms, a function f : X → Y is called Lipschitz if there exists a constant L such that for all

(x 1 , x 2 ) ∈ X 2 f (x 1 ) -f (x 2 ) 2 ≤ L x 1 -x 2 2 .
(2.5.1)

Of course, any L ′ > L is also a Lipschitz constant of f , for simplicity the minimal Lipschitz constant L f,X of the function f is called the Lipschitz constant of f . L f,X can also be expressed as the upper bound of the differential quotient:

L f,X = sup x 1 ,x 2 ∈X 2 f (x 1 ) -f (x 2 ) 2 x 1 -x 2 2 . (2.5.2)
Let f be a neural network as defined in (2.2.2). In the case of a multilayer perceptron the Lipschitz constant of f over X in the norm • is

L f,X (θ) def = sup x∈X ( d-1 i=1 W ⊤ i diag(G φ (f i (θ, x)))W ⊤ d , (2.5.3)
and G φ (f i (θ, x)) is an appropriate generalized Jacobian of φ evaluated at f i (θ, x). Typically G is a conservative field [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF] in which case L f,X (θ) is indeed a Lipschitz constant whenever X is convex [START_REF] Chen | Semialgebraic Optimization for Lipschitz Constants of ReLU Networks[END_REF]. When φ is differentiable this generalized gradient is the singleton of the Jacobian.

By standard conjugacy results, we also have

L f,X (θ) def = sup x∈X ,U ∈B * U, ( d-1 i=1 W ⊤ i diag(G φ (f i (θ, x))))W ⊤ d , (2.5.4)
where B * is the unit ball for the dual norm (nuclear norm).

Kernel density estimation

Kernel density estimation (KDE) [START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF][START_REF] Jones | A brief survey of bandwidth selection for density estimation[END_REF] is a non-parametric method to build from k ∈ N samples

(x i ) i∈[k] , x i ∈
R p an approximation ρ of the unknown underlying density function ρ. The method requires the use of a kernel K : R l → R + which is a positive and normalized measure:

∀x ∈ R l , K(x) ≥ 0 and R p K(x)dx = 1.
The predictor of the distribution ρ is then built by summing contributions from the points (x i ) i∈[k] to the overall estimated distribution:

ρ(x) = 1 hk k i=1 K( x -x i h ).
(2.6.1)

The choices of K and h depend on our prior knowledge about the distribution ρ: usually K is taken symmetric, centered around 0. Depending on the physics that are observed when drawing the points other arbitrary choices can be made: using a symmetric kernel might prove to be less efficient than a skewed and long right-tailed kernel when trying to approximate an exponential law. Nonetheless popular choices for K are the Gaussian, uniform, Epanechnikov or triangular kernels. Concerning h, the choice of the value boils down to the regularity class of ρ: for a Gaussian kernel there exists a general criterion [START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF] that ensures some regularity of the estimated distribution given h = σ(

4 3k 1 5
) where σ is the standard deviation of the samples

(x i ) i∈[k]
. This h is not suited for all possible approximated distribution and one can add extra specific heuristics in order to select it more suitable.

Probability measures

Considerations on probability measures are key to distributional robustness. Confusion between a set and the set of probability distributions over it should be avoided since we will switch regularly between the two. We therefore aim here at explicitly distinguish the different metrics in each space.

For a subset C ⊂ R m , let B be the Borel sigma algebra on C. M + (C) denotes the cone of non-negative measures on (C, B) equipped with the finite total variation norm. We also define P(C) the space of Borel probability measures supported on C P(C)

def = ϕ ∈ M + (C) : C dϕ(x) = 1 . δ x is the Dirac measure at x.
For any (ν, µ) ∈ P(C), the Kullback-Leibler divergence between µ and ν is

KL(µ, ν) =      C log( µ(x) ν(x) )dµ(x) if µ ≪ ν and C log( µ(x) ν(x) ) dµ(x) < ∞ +∞ otherwise,
where ≪ stands for absolute continuity of measures.

Let c : Z 2 → R + be a continuous and symmetric ground cost function is (c(z, z ′ ) = c(z ′ , z)) and c(z, z ′ ) = 0 ⇔ z = z ′ . For (ν, µ) ∈ P(C), denote Π(µ, ν) their couplings, i.e., joint probability measures π on Z 2 whose marginals are µ and ν. The Wasserstein distance between µ and ν with ground/transportation cost c is

W c (µ, ν) = inf π∈Π(µ,ν) Z 2 c(z, z ′ )dπ(z, z ′ ). Chapter 2 2.8. Γ-or epi-convergence When c(z, z ′ ) = z -z ′ q q , q ≥ 1, then W 1/q c
is indeed a distance, known as the q-Wasserstein distance. We will denote it W q .

For (ν, µ) ∈ P(C) let F be a class of function on C then the Maximum Mean Discrepancy (MMD) [START_REF] Gretton | A kernel two-sample test[END_REF][START_REF] Borgwardt | Integrating structured biological data by kernel maximum mean discrepancy[END_REF] between µ and ν is:

MMD[F, ν, µ] def = sup f ∈F (E x∼ν [f (x)] -E y∼µ [f (y)])
If F is the unit ball of a reproducing kernel Hilbert space with associated positive definite kernel k : C 2 → R then the MMD has a tractable expression:

MMD[F, ν, µ] = E x∼ν x ′ ∼ν k(x, x ′ ) -2Ex∼ν y∼µ [k(x, y)] + E y∼µ y ′ ∼µ k(y, y ′ )
The MMD distance benefits from a better tractability than the Wassertein distance and less constraints on the support of the distributions than the KL divergence.

Γ-or epi-convergence

We will invoke the notion of Γ-convergence, which plays a fundamental role in convergence of optimization problems (values and extrema points). In finite dimension, Γ-convergence of a sequence of functions corresponds to convergence of their epigraphs. The interested reader may refer to [START_REF] Maso | An Introduction to Γ-Convergence[END_REF] for a comprehensive treatment.

Tameness

We will need the notion of tame functions (and sets). A rich family will be provided by semialgebraic functions, i.e., functions whose graph is defined by some Boolean combination of real polynomial equations and inequalities [START_REF] Coste | An introduction to semialgebraic geometry[END_REF]. Definable functions on an o-minimal structure over R correspond in some sense to an axiomatization of some of the prominent geometrical properties of semialgebraic geometry [START_REF] Coste | An introduction to o-minimal geometry[END_REF][START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]. O-minimality includes many important structures such as globally subanalytic sets or sets belonging to the log-exp structure hence covering the vast majority of applications in learning, including neural network learning with various activation and loss functions. A slightly more general notion is that of a tame function, which is a function whose graph has a definable intersection with every bounded box. We then use the terminology definable for both. Given the variety of optimization problems that can be formulated within the framework of definable functions and sets, our convergence results will be stated for this class. The reader unfamiliar with these notions can just replace definability by semialgebraicity.

Clarke subdifferential

We now summarize a few properties of the Clarke subdifferential that will be useful to us in this contribution (see [START_REF] Frank | Optimization and Nonsmooth Analysis[END_REF]).

Proposition 2.10.1. Let f, g : R n → R be locally Lipschitz continuous functions, then

(i) ∂ C (λf )(x) = λ∂ C f (x), λ ∈ R. (ii) ∂ C (f + g)(x) ⊂ ∂ C f (x) + ∂ C g(x).
(iii) Consider the family of functions (f t ) t∈T , where T is a compact space and t → f t (x) is upper semicontinuous. Suppose that for each t, f t : R n → R is locally Lipschitz continuous. Let f (x) = max t∈T f t (x).

Let S be a subset of full Lebesgue measure, then Chapter 2 2.10. Clarke subdifferential

∂ C f (x) ⊂ conv lim k→∞ ∇f t k (x k ) : x k → x, x k ∈ S, t k ∈ T, f t k (x) → f (x) .
(2.10.1)

If, moreover, the functions f t are of class C1 such that f t (x) and ∇f t (x) depend continuously on (t, x) 1 , then:

∂ C f (x) = T ∇f t (x)dµ(t) : µ ∈ P Argmax t∈T f t (x) .
(2.10.2)

Remark 2.10.2. We have made no effort to further weaken the assumptions in the calculus rules of Proposition 2.10.1 since they are sufficient for our purpose.

Chapter 3

State of the art

In this chapter we summarize the current state of the art concerning robustness of neural networks. The current challenges in deep learning attracted a broad public, since the issue of robustness against adversarial samples remains unsolved and the demand for reliable and trustworthy algorithms is growing. There are lots of promising takes on the problem and we offer here an appreciation of the different shades of this literature. Our starting point is verification methods that can assess the trustworthiness of a given assertion on a neural network, followed by testing methods that aim at detecting possible defects in a implementation. Finally, we present methods made for robust learning that incorporate robustness at training times of the statistical model.

In order to provide a more synthetic vision of the state of the art we categorized the different contributions in three main categories, a color scale is used to present the type of the guarantees offered. In Figure 3.1, Chapter 4 is located in the testing bibliography among works on coverage. Chapter 5 is located in the testing literature as well but it focuses on the Lipschitz assessing algorithms. Our third contribution in Chapter 6 deals with robust learning and bridges pointwise robust learning with distributionally robust learning. We detail all these categories hereinafter in their dedicated sections.

Robustness verification

The first group of methods about robustness is posterior robustness, where the aim is to verify given properties of a network once it is trained. The property consisting of a stable prediction around training points can then be assessed and ideally confirmed. Lots of different techniques have been suggested and they can be qualified of being either deterministic or probabilistic.

Deterministic methods for verification

SMT solvers. Deterministic methods are methods that can guarantee if a model is robust around a given datapoint. We would like to emphasize that, unless explicitly said, a deterministic method can usually validate but not invalidate local robustness (this is a yes/maybe, rather than a yes/no type of answer). Using Satisfiability Modulo Theories (SMT) solvers [START_REF] Katz | Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks[END_REF][START_REF] Bastani | Measuring neural net robustness with constraints[END_REF][START_REF] Pulina | Challenging SMT solvers to verify neural networks[END_REF] one can verify explicitly if a property is met, for instance, if the prediction is stable around a datapoint. The method explores the set of constraints to be verified using the piecewise linear structure of the network and making disjunction of cases at each ReLU activation that encounters 0 on the domain to be verified: combinatorial explosion of cases makes these techniques impractical for large networks. [START_REF] Gehr | AI2: Safety and robustness certification of neural networks with abstract interpretation[END_REF][START_REF] Mirman | Differentiable abstract interpretation for provably robust neural networks[END_REF][START_REF] Li | Analyzing deep neural networks with symbolic propagation: Towards higher precision and faster verification[END_REF][START_REF] Singh | An abstract domain for certifying neural networks[END_REF] aims at processing a specific convex envelope (such as boxes or polytopes) of the input uncertainty set throughout a modified network that maintains soundness: if the propagated envelope has constant label, then the robustness property is kept on the uncertain set. This method has, however, a major flaw: one needs to be able to test a property continuously on the propagated set which could be multidimensional. [START_REF] Gowal | On the effectiveness of interval bound propagation for training verifiably robust models[END_REF][START_REF] Wang | Formal security analysis of neural networks using symbolic intervals[END_REF][START_REF] Zhang | Towards stable and efficient training of verifiably robust neural networks[END_REF] is simple: given an input set that is not necessarily finite, the goal is to compute a convex over-approximation of the output set. This approach is fairly close to abstract interpretation that we mentioned in the previous paragraph. This technique allows to certify the neighborhood of a given point even on a test set: if the output interval has constant label then the input interval around the tested point is certified. Such approach has the same flaws as Abstract Interpretation, therefore we grouped them together in our summary in Figure 3.1. [START_REF] Tsui-Wei Weng | Towards Fast Computation of Certified Robustness for ReLU Networks[END_REF] allows to check the property on a finite set of values (vertices of a polytope around the prediction), but for deep neural network the approximation is quite loose and it does not scale very well to large networks. [START_REF] Fischetti | Deep neural networks and mixed integer linear optimization[END_REF][START_REF] Cheng | Maximum resilience of artificial neural networks[END_REF][START_REF] Huang | Safety verification of deep neural networks[END_REF] is another form of linearization where the approximation of the ReLU function is similar to the one of ReluPlex [START_REF] Katz | Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks[END_REF]. These methods do not scale well with the size of the model: they often have to make distinction of cases which number grows exponentially with the size of the network. They are often impractical or give poor results when probed on large networks, since they hardly scale with the dimension of the parameters of the model.

Abstract interpretation. Abstract interpretation

Interval propagation. The principle behind interval propagation

Linearization. Linearization of activations

Mixed Integer Linear Programming (MILP). Mixed integer linear programming

Computing the Lipschitz constant.

A measure of the robustness to input perturbations is the Lipschitz constant. It measures how much the output of the function can change when its input is modified: it is therefore a key metric when assessing the variation of the decision-making of a neural network on a small neighborhood. Measuring and controlling the Lipschitz constant has hence become a major challenge to characterize robustness or to build robust neural networks [START_REF] Béthune | The Many Faces of 1-Lipschitz Neural Networks[END_REF]. Indeed, the lack of robustness can be caused by Lipschitz constants not being constrained during training, which in turns, allows small perturbations to cause large changes in the decision function. But estimating the Lipschitz constant of a neural network is an NP-hard problem [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF] resulting in papers often facing an accuracy/complexity dilemma and resorting to different upper bounds [START_REF] Combettes | Lipschitz certificates for layered network structures driven by averaged activation operators[END_REF] that are guaranteed or not. The assessment of a Lipschitz constant answers two specific needs: the first one is the need for verification where the goal is to ensure that around specific datapoints a certain property is met -often stability of the prediction-. The second one is the need to ensure more stability to perturbation on any sample of the data distribution, i.e. robustness. Having access to local Lipschitz constant ensures robustness over local neighborhood [START_REF] Raghunathan | Semidefinite relaxations for certifying robustness to adversarial examples[END_REF][START_REF] Fazlyab | Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks[END_REF] as it can provide bounds of possible deformation around data points. The causal link between the Lipschitz property and robustness has fueled research in the last years with loose estimations of the Lipschitz constant first [START_REF] Huster | Limitations of the Lipschitz Constant as a Defense Against Adversarial Examples[END_REF] and then tighter ones: for instance Seqlip [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF] is reformulating the computation of the Lipschitz constant in a maximization problem on activation variables that, if solved exactly, provides an upper bound for the Lipschitz constant. On the other hand, Semi Definite Programming (SDP) relaxations such as LipSDP [START_REF] Fazlyab | Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks[END_REF] or [START_REF] Raghunathan | Semidefinite relaxations for certifying robustness to adversarial examples[END_REF] give a certified upper bound. Computing the Lipschitz constant of ReLU networks can also be cast as polynomial optimization, for which the sparse version of the Lasserre's SDP-hierarchy was proposed in [START_REF] Chen | Semialgebraic Optimization for Lipschitz Constants of ReLU Networks[END_REF] to provide upper bounds that are sometimes strict improvements over previously known upper bounds. All these approaches only test their methods on random networks and trained networks that have, by design (or by lack of design), an unknown and varying Lipschitz constant. This results in mixing different sources of variance when approximating it: the variance of the training of the network and the variance of the Lipschitz assessing algorithms. We address this point in Chapter 5.

Probabilistic methods

These methods can scale respectively well on large models contrary to the aforementioned deterministic verification methods but they are still very much dependent of the input dimension. However, their assessment of the robustness relies on a sampling strategy that might require lots of costly computations. Overall, probabilistic methods fail to quantify the presence of null measure sub-spaces that could contains adversarial attacks.

Random smoothing.

Random smoothing [START_REF] Cohen | Certified Adversarial Robustness via Randomized Smoothing[END_REF][START_REF] Li | Certified adversarial robustness with additive noise[END_REF] provides a probabilistic robustness certification bound. It requires the knowledge of the percentage of the perturbation space classified correctly which could be challenging to assess in high dimensions, however the effect of sampling on the probabilistic bound is not assessed as it should depend on the dimension of the problem. The main strength of the method comes from its scalability to large networks, giving a good alternative to other verification methods.

Measuring robustness. [START_REF] Bastani | Measuring neural net robustness with constraints[END_REF] suggests statistically relevant metrics such as frequency and severity of adversarial examples. These metrics offer an alternative to the usual "adversarial accuracy" that is used to quantify the robustness of a given network. It provides a better appreciation of the overall neighborhood of points in a dataset. Let us emphasize once again that the sampling method and sampling size are key to providing a proper estimation and that it is heavily dependent on the dimension and its influence on the metrics given is not assessed.

Verification tools are necessary as they allow to prove formal assertions of the final solution and validate a neural network. However, it must be noted that these methods hardly scale either with the dimension of the model or the dimension of the input. We would like to stress that although a model that passes these tests can be qualified as robust, these methods do not provide ways of improving the robustness of the model. Designing a neural network robust can only be performed prior to verification: these methods are necessary but not sufficient for robustness. They allow to target specific flaws in a trained network and cast a new light on the inner working of these "black-box" models but they do not essentially design robust models.

Neural network testing

Testing methods answer the need of generating tests suites that probe a statistical model. They differ from verification methods since their goal is to expose vulnerabilities instead of trying to demonstrate resistance to perturbations [START_REF] Jie | Machine learning testing: Survey, landscapes and horizons[END_REF]. In a sense they are mandatory when the production environment is different than the development environment. This mostly covers two scopes of research:

1. Approaches based on code coverage criteria that aim at finding and exploiting blind spots in an activation pattern.

2. Approaches based on fuzzing: an automated test case generation that aims at finding bugs of implementations.

Coverage based testing

Measuring coverage. The goal of coverage based techniques is to generate erroneous behaviors/predictions by studying and exploiting the parts of a statistical model that are not used in its training set. This originated with deepXplore [START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF], that leveraged the activation pattern to generate erroneous examples. The authors assess, via back-propagation, the gradient direction on the input that increases a specific activation in the same fashion that adversarial attack increases the loss of the network. Following this methodology the authors manage to generate fooling samples, however, the impact of coverage in their method is unclear as it is optimized in conjunction with an adversarial loss to generate erroneous samples. In order to test more plausible transformations, DeepTest [START_REF] Tian | DeepTest: automated testing of deep-neuralnetwork-driven autonomous cars[END_REF] optimizes the same coverage criterion with greedy search. DeepGauge [START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF] extends the notion of coverage with a higher level of granularity by not only considering if a neuron is activated, but by considering also smaller intervals of the activation landscape. This has the advantage of showcasing blind spots even in multimodal patterns. The only drawback from this metric is that there is no explicit way of optimizing it directly: the authors use attacks from the literature and show that they tend to increase coverage. Their experimentation shows only that adversarial attacks imply a greater coverage, but they do not assess if increasing coverage is an efficient way of generating adversarial attacks. [START_REF] Sun | Structural test coverage criteria for deep neural networks[END_REF] introduced structural coverage that aims at quantifying the relations between features, i.e. if neural network activations have a correlated pattern whereas previous contributions considered the coverage of the neurons independently. In a attempt to have a more interpretable coverage metric [START_REF] Xie | NPC: neuron path coverage via characterizing decision logic of deep neural networks[END_REF] introduced Neuron Path Coverage as a more elaborated way to highlight paths in neural networks that have an influence on their prediction.

Coverage vs Robustness. In order to investigate the possible correlations between robustness and coverage, [START_REF] Yan | Correlations between deep neural network model coverage criteria and model quality[END_REF] and [START_REF] Chen | Deep Neural Network Test Coverage: How Far Are We?[END_REF] independently computed Pearson's correlations between a wide range of coverage metrics and a wide range of robustness metrics and noticed how little correlation there was between the two. However, Pearson's correlation only displays linear dependencies between variables, thus this does not completely discard a possible link between robustness and coverage. [START_REF] Yan | Correlations between deep neural network model coverage criteria and model quality[END_REF] tried as well to include coverage attacks into the training of neural networks just like adversarial attacks could be used at training times to increase the robustness of the learning procedure (the idea was originally suggested in DeepXplore [START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF] but was not assessed). However, this training on coverage attacks did not prove to be effective in improving the robustness. In order to avoid making the arbitrary choice of the number of sections as done in DeepGauge [START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF], [START_REF] Harel-Canada | Is neuron coverage a meaningful measure for testing deep neural networks[END_REF] suggested a metric using a KL divergence between the layer-wise activations values and a uniform distribution. This also has the advantages of providing a subdifferentiable metric that can be optimized concurrently with the loss and to handle activation in a more continuous manner. However, the relevance of using a layer-wise coverage metric instead of a neuron-wise is not discussed in the paper.

Fuzzing

The goal of most papers elaborating on fuzzing is to find implementation mistakes rather than wrong predictions. To that purpose, fuzzing is a method that generates a test suite that covers a maximal percentage of the code and monitors for induced bugs, errors or failures. The test suite needs not be representative of the input distribution, thus enabling a broader search space. The first seminal work on fuzzing adapted to DNN testing, [START_REF] Odena | TensorFuzz: Debugging Neural Networks with Coverage-Guided Fuzzing[END_REF], is offering a coverage guided test suite where examples are generated in order to maximize a diversity of activation patterns. DeepHunter [START_REF] Xie | DeepHunter: a coverage-guided fuzz testing framework for deep neural networks[END_REF] tries to achieve the same goal but using mutations that are closer to image perturbations (such as changes in brightness, blur, contrast, translation, rotation or scaling) and the diversity metric for guiding generation of samples is a distance between six different testing criteria. Both approaches work remarkably well for finding defects in implementations. Other methods for fuzzing change the generation method, such as Generative Adversarial Networks (GANs [START_REF] Goodfellow | Generative adversarial networks[END_REF]) [START_REF] Zhang | Deeproad: Ganbased metamorphic testing and input validation framework for autonomous driving systems[END_REF] or changed the coverage criterion used for samples generation [START_REF] Guo | Dlfuzz: differential fuzzing testing of deep learning systems[END_REF]. Fuzzing can easily be a compulsory step for certifying a deep learning solution that is to be put to production in order to test the production environment.

Overall, research around coverage based testing is mostly empirical and some of the initial conclusions on the subject were quite optimistic concerning the benefits on robustness, a vision that currently appears flawed [START_REF] Li | Structural coverage criteria for neural networks could be misleading[END_REF][START_REF] Dong | There is Limited Correlation between Coverage and Robustness for Deep Neural Networks[END_REF][START_REF] Sekhon | Towards improved testing for deep learning[END_REF]: we address this matter in Chapter 4. Concerning Fuzzing, the end goal is different as it aims at finding defect of implementation rather than explaining model misconduct. Coverage is used in accordance with its initial purpose from code coverage: explore all branches of the code in order to ensure that inference can be performed without bugs regardless of possible errors in the prediction.

Robustness aware learning

As mentioned above, verification and testing focus on trying to validate a deep learning solution. On the other hand, the third group of robustness methods consists in modifications of the learning procedure so as to build a robust model. It can thus be used sequentially with testing methods that can check the extent of the obtained robustness a posteriori. These approaches are a very active field of deep learning: they aim at finding a more suitable set of parameters by incorporating prior knowledge on the possible perturbations. Some methods are explicitly enforcing constraints on the network during training, this ensures the compliance of the resulting network with the constraints. Other methods aim at regularizing the network or making changed training procedures without given constraints, hoping to find an optimal configuration with a suitable robustness.

Preprocessing robustness

Out Of Distribution (OOD) detection. A first approach to prevent spurious behavior caused by an adversarial sample is to detect or preprocess the inputs before performing a prediction on them: the OOD literature tries to achieve as much by adding a preliminary step in the processing of an input. Among the literature, the goals of these preprocessings differ: it can be to spot and remove adversarial samples via a dedicated classification before feeding them to the network [START_REF] Liang | Principled detection of out-of-distribution examples in neural networks[END_REF][START_REF] Lee | A simple unified framework for detecting outof-distribution samples and adversarial attacks[END_REF][START_REF] Paudice | Detection of adversarial training examples in poisoning attacks through anomaly detection[END_REF][START_REF] Hendrik Metzen | On detecting adversarial perturbations[END_REF][START_REF] Grosse | On the (statistical) detection of adversarial examples[END_REF]. Other methods resort to principal component analysis in order to identify adversarial attacks (linear Principal Component Analysis -PCA- [START_REF] Hendrycks | Early methods for detecting adversarial images[END_REF], nonlinear PCA [START_REF] Arjun | Dimensionality reduction as a defense against evasion attacks on machine learning classifiers[END_REF]), or even analyse the activation pattern with respect to the activation trace (distribution of the activations over the training set) using the MMD distance [START_REF] Grosse | On the (statistical) detection of adversarial examples[END_REF] or KDE estimation [START_REF] Feinman | Detecting adversarial samples from artifacts[END_REF]. These techniques can be very powerful for monitoring the behavior of the model, but one has to make sure that these methods can not be attacked as well (for instance, methods based on neural networks): [START_REF] Carlini | Adversarial examples are not easily detected: Bypassing ten detection methods[END_REF] showed that these methods can easily be bypassed by powerful adversarial attacks. OOD can help providing a diagnosis, yet it does not make our prediction models less sensitive to perturbation: it simply censors erroneous samples. The guarantees of these methods depend on the guarantees of the detection/preprocessing methods: if a method is based on neural networks this translates the robustness issue from the model to the diagnosis tool that is supposed to bring some extra robustness.

Prior explicit robustness

Lipschitz enforcing. A first category of methods relies on inducing explicitly boundness of variations in a neural network. [START_REF] Miyato | Spectral normalization for generative adversarial networks[END_REF][START_REF] Yoshida | Spectral Norm Regularization for Improving the Generalizability of Deep Learning[END_REF] for multilayer perceptron, [START_REF] Cissé | Parseval Networks: Improving Robustness to Adversarial Examples[END_REF][START_REF] Serrurier | Achieving Robustness in Classification Using Optimal Transport With Hinge Regularization[END_REF][START_REF] Gouk | Regularisation of neural networks by enforcing Lipschitz continuity[END_REF] for convolutional networks, and more recently [START_REF] Dasoulas | Lipschitz normalization for self-attention layers with application to graph neural networks[END_REF] for graph neural networks propose to bound the parameters at training times in order to enforce an upper bound of the Lipschitz constant. But these methods require much more computation than vanilla trainings, even though they allow knowing beforehand the resulting maximal variations of the network. For any classification problem, for example, we can find a 1-Lipschitz network that has 100% accuracy on the problem [START_REF] Béthune | The Many Faces of 1-Lipschitz Neural Networks[END_REF]. Advocating evil, this also means that shrinking the Lipschitz constant for classification tasks never cancels out the risk of overfitting. That much is not true for regression problems, where the phenomenon that one wants to approximate has an intrinsic regularity: any attempt to fit a statistical model that has lower regularity than the phenomenon would be unable to perform the regression perfectly. Bounding the Lipschitz constant has a direct implication in limiting steep variations of the function, and thus overfitting.

Regularization. More traditional techniques already existed in order to provide a sense of sparsity and regularity for a learned function such as weight decay [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF]. They apply methods from linear modeling that incorporate ℓ 2 regularization to provide models more robust to input perturbations. Recently, more elaborated methods are emerging, for instance, using RKHS norm as a regularization [START_REF] Bietti | On Regularization and Robustness of Deep Neural Networks[END_REF] directly influences the Lipschitz property of the learned model. Alternatively, [START_REF] Zhang | Theoretically Principled Trade-off between Robustness and Accuracy[END_REF] suggests a regularization that reduces the difference between the prediction and a possible perturbation of this prediction, rather than between the perturbed prediction and the true label. More specific techniques have also been developed for different neural architectures: dropout [START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF] or batch normalization [START_REF] Ioffe | Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift[END_REF] for instance. These empirical regularizations have proven to be very effective in practice, since they are designed to compensate for some poor conditioning of the neural networks. In addition, they rely on strong practical results and efficient implementations that make them popular. They are based on a sparsity assumption, meaning that between two equivalently performing models, the less complex one should be preferred, since over-parametrization may lead to over-fitting. This abides by the Occam's Razor principle: a simpler theory or explanation is often preferred over more complex or far-fetched ones. Removing unused parameters allows to derive simpler causal links in a model and should lead to simpler models. At this point, it is worth recalling that Occam's Razor principle is an empirical view and that it has no grounding on a nonlinear model that learns on an empirical distribution. On top of that, the assumption of sparsity of a problem might simply not be relevant or adequate, since there might not be a simple solution when considering a complex problem.

Prior implicit robustness

As opposed to the previous group that incorporates robustness in the training formulation by enforcing sparsity, we focus now on the works that attempt to formulate the problem as an optimization under uncertainty (also called robust optimization), where regularization might come as a side effect. It is proven that, for linear predictors or support vector machines, regularization with a proper distance and robust optimization are the one and the same [START_REF] Lebret | Robust Solutions to Least-Squares Problems with Uncertain Data[END_REF][START_REF] Xu | Robustness and Regularization of Support Vector Machines[END_REF], however for models non convex in the parameters and non concave in the input it is relevant to consider the two approaches as different.

Theory on robust optimization [START_REF] Ben-Tal | Robust Optimization[END_REF][START_REF] Bertsimas | Theory and Applications of Robust Optimization[END_REF][START_REF] Bertsimas | Data-driven robust optimization[END_REF][START_REF] Wald | Statistical Decision Functions Which Minimize the Maximum Risk[END_REF] is rather advanced when it comes to linear predictors or linear decision-making [START_REF] Ben-Tal | Robust solutions of optimization problems affected by uncertain probabilities[END_REF][START_REF] Ben-Tal | Robust Optimization[END_REF][START_REF] Chen | Distributional robust learning under the Wasserstein metric[END_REF]. It aims at finding the set of parameters that minimizes the worst possible error on a perturbation set. However, the theory does not currently provide a general algorithm and guarantees of convergence for robust nonlinear problems without additional hypothesis. Current empirical approaches differ on the perturbation they consider: either pointwise perturbations or distributional. These approaches are parameter-free for the perturbation set, in the sense that no hypothesis is made on its distribution. A common way to achieve this is by assuming a finite support for the possible perturbations without knowing its density. This aims at finding models that minimizes the objective for any possible perturbation lying in the uncertain set. These approaches are more compliant with our framework than previous methods due to the fact that industrial applications can have access to detailed information on the possible uncertainties of measures or approximation errors in computer codes. This approach to robust optimization that guarantees mitigation of the loss in the presence of uncertainty can be over-pessimistic if the uncertainty set is overspecified. It is therefore key to include all prior information in the learning process to avoid ending in a suboptimal solution of the optimization process.

Pointwise robustness

Adversarial attacks and trainings. A large amount of work on pointwise robustness was achieved through the scope of adversarial attacks [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF][START_REF] Goodfellow | Explaining and Harnessing Adversarial Examples[END_REF][START_REF] Gamaleldin | Adversarial Reprogramming of Neural Networks[END_REF], which we mentioned in the introduction as a serious menace to modern deep learning. Concerning the creation of these attacks, papers usually resort to local projected gradient ascents [START_REF] Goodfellow | Explaining and Harnessing Adversarial Examples[END_REF][START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF] in an either single step or multi-step fashion that, despite the lack of convergence guarantees, perform exceptionally well. Other notable approaches resort to GANs [START_REF] Xiao | Generating Adversarial Examples with Adversarial Networks[END_REF] or objectives that aim at diverting the prediction towards its second best choice [START_REF] Carlini | Towards Evaluating the Robustness of Neural Networks[END_REF]. Early attempts at making specific defenses included distillation [START_REF] Papernot | Distillation as a Defense to Adversarial Perturbations Against Deep Neural Networks[END_REF] that was debunked using strong attacks [START_REF] Carlini | Towards Evaluating the Robustness of Neural Networks[END_REF]. An efficient way to make models robust is to use adversarial samples to further train the model to design it less insensitive to gradient based attacks (see the dedicated section 2.4.2 in the prerequisites). This has been called adversarial training [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF][START_REF] Tramèr | Ensemble Adversarial Training: Attacks and Defenses[END_REF][START_REF] Xiao | Spatially transformed adversarial examples[END_REF][START_REF] Creswell | Denoising Adversarial Autoencoders[END_REF] as opposed to adversarial attacks. These methods remain as of today the most used methods for making a network robust to local perturbations due to their simplicity of use and their computational efficiency. When considering computer vision applications, adversarial attacks take a new dimension: indeed, it is expected that under light transformations such as light translation, rotation, cropping or brightness changes the prediction should not change (such transformations are called unrestricted attack as opposed to restricted attacks that are constrained in balls). To that purpose, several papers used the same idea from adversarial training by simply performing data augmentation with a broad range of these unrestricted attacks [START_REF] Raff | Barrage of random transforms for adversarially robust defense[END_REF][START_REF] Guo | Countering adversarial images using input transformations[END_REF]4]. These papers manage to build models that are reasonably adversarially robust without the use of adversarial attacks on images. As of today, adversarial training is the best empirical method for making DNN robust against adversarial attacks, despite all these advances. Ultimately, adversarial attacks and defense are broad empirical exploration of pointwise robustness with little theoretical results. This is not to downplay the contributions of the aforementioned authors as they paved the way for a more in depth study of robustness of neural networks but it showcases theoretical shortcomings in robustness.

Pointwise duality.

Other pointwise approach took the perspective of robust optimization and offered changed training procedures [START_REF] Wong | Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope[END_REF][START_REF] Wong | Scaling provable adversarial defenses[END_REF]. They presented theoretical guarantees on the result of their optimization: this has the advantage to provide bounds on the training error. [START_REF] Raghunathan | Certified defenses against adversarial examples[END_REF][START_REF] Hein | Formal guarantees on the robustness of a classifier against adversarial manipulation[END_REF] provide similarly certified bound on adversarial attacks on the training set. Both authors do not discuss the generalization on a test set of their approaches.

Distributional robustness

This approach has gained momentum as it is more general than the pointwise robustness [START_REF] Staib | Distributionally robust deep learning as a generalization of adversarial training[END_REF]. Distributional robust learning aims at minimizing a worst case expected loss, where the worst case is chosen among all possible distributions in a bounded perturbation set. This distributional perturbation set is often called an ambiguity set, the name coming from seminal works in robust optimization [START_REF] Ben-Tal | Robust Optimization[END_REF][START_REF] Delage | Distributionally robust optimization under moment uncertainty with application to data-driven problems[END_REF][START_REF] Calafiore | On Distributionally Robust Chance-Constrained Linear Programs[END_REF]. For linear regression, SVM [START_REF] Chen | Distributional robust learning under the Wasserstein metric[END_REF] or logistic regression [START_REF] Shafieezadeh-Abadeh | Distributionally Robust Logistic Regression[END_REF] the distributional robust problem is tractable and has links with regularization. But this does not hold true for non convex/non concave settings: generality comes at the cost of tractability. Distributional optimization problems are not always tractable and necessitate extra layers of approximations to solve them. Approaches differ in the definition of their perturbation set such as Wasserstein ambiguity sets [START_REF] Blanchet | Quantifying Distributional Model Risk via Optimal Transport[END_REF][START_REF] Blanchet | Robust Wasserstein profile inference and applications to machine learning[END_REF][START_REF] Kuhn | Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning[END_REF], Entropy regularized Wasserstein ambiguity sets [START_REF] Wang | Sinkhorn distributionally robust optimization[END_REF], MMD ambiguity sets [START_REF] Staib | Distributionally Robust Optimization and Generalization in Kernel Methods[END_REF], φ-divergence ones [START_REF] Duchi | Variance-based Regularization with Convex Objectives[END_REF][START_REF] Chouzenoux | General risk measures for robust machine learning[END_REF]. Changing the distance allows papers to trade generality for guarantees or tractability. For instance [START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF] deals with Wassertein distributional robustness and provides robustness bounds along with a training procedure. However, the algorithm for training the network resorts to an oracle that is able to find the maximum of a non convex/concave function on a compact set. This can be achieved reasonably accurately in small dimensions but, as dimension increases, it becomes more and more tedious to find the local extrema input since the problem is NP-hard. For a more exhaustive review on distributional robustness, see [START_REF] Rahimian | Distributionally Robust Optimization: A Review[END_REF]. We address the problem of approximating this NP-hard problem with smoothing and Monte Carlo sampling that insures convergence in the limit to the robust optimization problem in Chapter 6.

Parametric robustness

Bayesian approaches in deep learning usually deal with the epistemic uncertainty which, as already elaborated in section 1.1.1, is the uncertainty due to the lack of knowledge of our system (for instance if an explanatory variable is missing). Bayesian neural networks give a confidence interval on the prediction that can be used to appreciate the relevance and reliability of an output. Traditionally a prior distribution is assumed on the weight and this distribution is updated in the light of the incoming data. Pioneers papers date back to [START_REF] David | Bayesian Methods for Adaptive Models[END_REF][START_REF] Radford | Bayesian Learning for Neural Networks[END_REF]. They used costly methods for computing the posterior (Newton method or Hamiltonian Monte Carlo) to tackle their problems, but they are not scalable to larger models. In order to scale to larger models, variational inference was proposed [START_REF] Michael | An Introduction to Variational Methods for Graphical Models[END_REF][START_REF] Graves | Practical Variational Inference for Neural Networks[END_REF], where it assumes a parametric family of distributions for the posterior and tries to find the posterior parameters that fit the most the real posterior distribution. It reduces the amount of computation to perform on larger models but still remains computationally demanding. The latest takes aim at making this approach tractable for highly dimensional neural networks using Dropout [START_REF] Gal | Uncertainty in Deep Learning[END_REF] where the author presents the dropout mechanism as a form of Bernoulli Bayesian inference. This has the advantage of providing confidence bounds at a much lower cost. Prior assumptions on dense networks have some interpretation when considering one linear layer, however it remains unspecified what prior assumption should be made on convolutional layers: none of the aforementioned papers formally justify the use of priors on more complex structures than linear layers.

Robust learning precedes Verification and Testing as it seeks to improve the training procedures by incorporating uncertainties in the design process of the models. It has been the preferred way of dealing with robustness in the last decade in order to mitigate the effect of all three possible sources of uncertainties: uncertainties from the inputs, the labels or the models. Most of the work focused on input uncertainties i.e. possible changes in the input domain either in a pointwise manner or in a distributional manner. Traditional methods -inherited from classical robust linear learning-resort to regularization or constraint enforcing (such as enforcing Lipschitz constants) but do not always have a proper interpretation or meaning on nonlinear models, despite good empirical results. When it boils down to practical results, adversarial training remains unchallenged: it is computationally the most effective and it scales well to large dimensions. However, it does not provide any theoretical guarantees. Algorithms that are guaranteed to converge towards the optimal model suffer from high dimensions and/or have tractability issues. None of the approaches mentioned in this state of the art meet all the desired requirements of a robust training method: adaptable to all architectures, scalable, tractable, certified and, most importantly, mitigating the effect of uncertainties.

Introduction

thus resulting in infinite training times for these deep neural nets. The ReLU function keeps the norm of the gradient constant as it activates and thus allows updating efficiently deep neural structures. The smoothness and boundedness of traditional activation function was traded against computability and now major state of the art architectures in image recognition [START_REF] He | Deep residual learning for image recognition[END_REF]6,[START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF] are resorting to this activation function as part of their building blocks. However, the downside is that, in the processing of a finite number of inputs, some activations (outputs of hidden layers) might never overpass the 0 threshold and thus part of the weights may never have an impact on the prediction of the network. This results in having parameters of the model that remain unaltered during the whole process of training. Since the test distribution is different from the training one, these unused parameters (that have not been designed through the training procedure) may have an influence on the extrapolation result. Having a way to monitor the part of the network that is not used during training time could be an elaborated way of detecting erroneous behaviors at inference times.

Code coverage [START_REF] Miller | Systematic mistake analysis of digital computer programs[END_REF] is a relevant measure of code robustness since it quantifies the amount of source code that was not used while executing a test suite. It provides a good indicator on the possible presence of undetected errors in man-made programs and has become, over the years, a metric for code quality that it is advised to monitor before a code is to be used in a production environment.

In order to find potential erroneous behavior in deep learning models and in analogy to the concept of code coverage, researches sought to exploit the lack of coverage of these statistical models to trigger a wrong prediction. Usually, coverage guided testing aims at creating inputs altering the activation pattern (i.e. the activated units or the distribution of these activations). Thus, coverage testing produces perturbed datasets that maximize the coverage of a given network. Such modified inputs might eventually change the decision provided by the neural net. These perturbations can subsequently be used as a form of data augmentation and serve the purpose of retraining the network to increase the overall usage of the network parameters. Contributions to coverage testing assume that the lack of coverage is responsible for blind spots in the decision-making process and they usually attempt to find ways to reduce such occurrences by increasing coverage at training time.

Although tempting, the analogy does not hold entirely since code coverage seeks defaults of implementations whereas DNN coverage testing seeks ways to twist a perfectly working code. In the light of some recent researches, over-parametrization appears to improve generalization [START_REF] Behnam Neyshabur | The role of over-parametrization in generalization of neural networks[END_REF][START_REF] Peter | Spectrally-normalized margin bounds for neural networks[END_REF][START_REF] Belkin | Reconciling modern machine learning and the bias-variance trade-off[END_REF] which in turns allows for a more robust model [START_REF] Xu | Robustness and generalization[END_REF]. This result enters in sharp contrast with the coverage reasoning where having more parameters means more unused parameters. By having an extra amount of parameters a neural network should be more vulnerable and yet under some hypothesis (mostly norm constraints on the weights) it has generalization error that is lower than the one of small neural networks that should learn more sparse representations. Initial works on coverage [START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF][START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF][START_REF] Xie | DeepHunter: a coverage-guided fuzz testing framework for deep neural networks[END_REF] showcased experiments where adversarial attacks (i.e. fooling samples) tend to increase DNN coverage but the other way around does not hold according to more recent works. Indeed, the recent literature has been more skeptical with results that failed to showcase dependencies between robustness and coverage [START_REF] Yan | Correlations between deep neural network model coverage criteria and model quality[END_REF][START_REF] Harel-Canada | Is neuron coverage a meaningful measure for testing deep neural networks[END_REF]. Their conclusion is the following: increasing coverage does not provide significant improvements in terms of adversarial robustness. In order to provide additional enlightenment concerning this perspective, we explore in this contribution if an adversarial attack could exploit coverage information in order to improve its capacity at fooling the network. Former approaches on coverage considered the two aspects separately (coverage and adversarial attacks) by investigating correlations between one another whereas we want to assess the effect of mixing the both. In the light of these elements, we formulate the following questions that drive this research: can coverage be used jointly with adversarial attacks (resp. defenses) to efficiently perturb (resp. increase robustness of) neural networks? Can a happy medium where coverage helps shape a better attack (resp. model) be stricken? This chapter can be classified in the DNN testing literature reviewed in Section 3.2, more specifically the coverage based testing subsection. In order to clarify the contributions made in this chapter detailed hereinafter, we offer subsequently a brief reminder of similar approaches.

Contributions

We propose a novel subdifferentiable coverage metric that does not rely on hyperparameters such as thresholds or binning strategies that may influence the result significantly. This metric, in turns, enables to optimize concurrently coverage and robustness and to find out if they can be exploited altogether to fool a network. The end goal being to highlight a possible joined effect between coverage and adversarial training and/or a joined effect between coverage and adversarial attacks on the accuracy of the model. We will explore the problem following a double perspective: on the one hand, we adopt the point of view of an attacker that seeks to exploit the coverage of a model in order to create the most perturbing attack. On the other hand, we take on the perspective of the defender where we seek to use coverage at training times to make the model more robust. Following the attacker perspective in Section 4.3.1, we present testing of a pure coverage guided attack and explore numerically the effect of coverage used jointly with well known adversarial attacks. In the end, we did not manage to show any gain in using coverage in combination with adversarial attacks and that increasing coverage does not provide a reliable way of perturbing the accuracy of a model. Considering the defense problem, we provide a broad range of experiments in Section 4.3.2 that show the interest of introducing coverage guided metrics in the training and present its effect over a broad range of attackers. We managed to show experimentally that increasing coverage at training times provides some regularization that effectively increases robustness but only significantly compared to an unregularized model. Any attempts to make a training with combinations of adversarial samples made of combinations of coverage and adversarial attacks did not bring any gain compared to the pure adversarial training.

Related work

DeepXplore [START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF] has been the first paper drawing a parallel between coverage and adversarial attacks: following their logic, adversarial attacks should be exploiting parts of the DNN that were not used during training.

The layer-wise notation is quite unfit for defining neuron coverage, we will prefer the neuron-wise representation (introduced in 2.2): let us consider a neural network f (θ, •) equipped with the ReLU nonlinearity, with parameters θ ∈ Θ as a collection of neurons N = {n 1 , n 2 , ...}. For all i ∈ [|N |], n i : Θ × X → R is the function that returns the activation of neuron i before applying the nonlinearity for a given input x ∈ X of the neural net. Given a test set X = {x 1 , ..., x m } ∈ X m , m ∈ N, Pei et al. [START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF] defines neuron coverage as the percentage of activated neurons on the test set over the number of neurons:

NCov(X, θ) = | {n i |∀x ∈ X, n i (θ, x) > 0} | |N | . (4.1.1)
The authors then devise an algorithm that finds a negative activation n j (x), j ∈ [|N |] and they increase its value along with additional penalty terms using a gradient ascent algorithm on x until the activation turns positive. The algorithm then proceeds to increase another negative activation in an attempt to increase indirectly the overall NCov metric for a perturbed version of x.

However, this metric has been experimentally shown [START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF] to be inefficient in measuring diversity in activation distributions. Indeed, there is no sensitivity with respect to the number of times an activation has passed the 0 threshold over the test set and it does not account for how the activations are distributed over the reals. In order to palliate the latter, DeepGauge [START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF] introduced k-multi section coverage.

Recalling the notations from equation (4.1.1), for a neuron

n i , i ∈ [|N |] k-multi section coverage consists of making k subdivisions (S n i j ) j∈[k] of the closed activation interval [l i , u i ] of a neuron so that j∈[k] S n i j = [l i , u i ].
Ideally, the subdivisions are taken with equal length. Their coverage metric is a count of the subdivisions that actually contain an activation value when probed on the test set over the total number of subdivisions:

KMNCov(X, θ, k) = 1 |N | i∈[|N |] | S n i j |∃x ∈ X, n i (θ, x) ∈ S n i j | k . (4.1.2)
This metric is not differentiable either and thus cannot be optimized directly. On top of that, the influence of the parameter k on which heavily depends the metric is not assessed in the original paper: the authors leave the procedure for finding a suitable k for future work.

There is a growing concern from the software engineering community [START_REF] Li | Structural coverage criteria for neural networks could be misleading[END_REF][START_REF] Dong | There is Limited Correlation between Coverage and Robustness for Deep Neural Networks[END_REF][START_REF] Sekhon | Towards improved testing for deep learning[END_REF] that current coverage based testing might be unfit for testing neural networks as it seems not to be a good test generation framework for robustness. While undertaking this work, we became aware of parallel and independent researches [START_REF] Yan | Correlations between deep neural network model coverage criteria and model quality[END_REF][START_REF] Harel-Canada | Is neuron coverage a meaningful measure for testing deep neural networks[END_REF] on the same subject. These two papers are skeptical about a possible correlation between coverage and robustness and present a significant amount of empirical evidence to support their claims. [START_REF] Harel-Canada | Is neuron coverage a meaningful measure for testing deep neural networks[END_REF] is computing a KL divergence between layer-wise activation distribution and a uniform distribution. Although they display that the increase in layer coverage tend to increase neuron coverage as well, there could be pathological cases where layer-wise coverage is increased and neuron wise coverage is not. [START_REF] Yan | Correlations between deep neural network model coverage criteria and model quality[END_REF] provides a large pool of experiments in order to compute Pearson correlations between an extended range of robustness metrics and coverage metrics. They show that the well-used metrics of robustness and the metrics for coverage have little correlation, positive or negative. The literature has been focusing on comparing the correlations of coverage and robustness, however, there has been little consideration over their joined effect: two variables may be independent but can have a cross effect on a third variable. We therefore want to probe if adversarial attacks and coverage can be used jointly to perturb predictions. Our work is in the continuity of DeepGauge as we aim at quantifying the coverage on the whole support of activation distribution but in a rather continuous way. [START_REF] Kim | Guiding deep learning system testing using surprise adequacy[END_REF] and [START_REF] Feinman | Detecting adversarial samples from artifacts[END_REF] compute an approximation of the distribution of activations by using KDE (called the activation trace), the former does it in order to increase its entropy and study its effect on the KMNCov criteria, the latter uses it to detect potential out-of-distribution samples. We use the very same activation trace with the purpose of making it uniform since we want to balance the activation pattern. The discrepancy between the activation trace and the uniform distribution constitute our coverage metric on which we elaborate further in the next section.

Theoretical considerations

Coverage metric

We borrow the notation of part 2.2 for neural networks. The coverage metric from [START_REF] Harel-Canada | Is neuron coverage a meaningful measure for testing deep neural networks[END_REF] (a KL divergence layer-wise) presents the desirable property of being differentiable [START_REF] Rumelhart | Learning representations by backpropagating errors[END_REF] or at least subdifferentiable [START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF] in case activations are non-smooth. Subdifferentiability is key to finding a suitable set of parameters as the gradient descent (or subgradient descent) remains, as of the time of writing of these results, the major procedure for optimizing neural networks. However, this KL divergence is computed layer-wise, thus not accounting completely for the coverage of one specific neuron. A neuron coverage metric should be computed neuron-wise and aggregated throughout all activations in the same fashion that [START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF][START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF]. Subdifferentiability of our metric comes from the fact its definition as a divergence between two measures instead of an enumeration.

Keeping notation from equation (4.1.1), let a i ∈ P(R) be the activation distribution of one neuron i with i ∈ [|N |] over the input distribution. The activations a i are taken before applying the nonlinearity, therefore a i is the distribution of function n i (θ, •) : X → R assessed on the input distribution. We dropped the dependency with respect to θ in the notation of the activations a i for the sake of clarity. a i is supported on a compact set [l i , u i ] with (l i ≤ u i ) and (l i , u i ) ∈ R 2 since we considered the support of the input space to be bounded. Let

U (l i , u i )(•) = 1 u i -l i I [l i ,u i ] (•) ∈ P(R) be the uniform distribution over [l i , u i ]
where I A is the indicator function of a set A. Our coverage metric aims at making the activation distribution lean towards the uniform distribution on the activation interval, thus we define it as minus the KL divergence between U (l i , u i ) and a i (the coverage is maximal when the distribution is completely uniform, thus the KL is null):

Cov(a i , θ) = -KL(U (l i , u i ), a i ). (4.2.1)
Overall, this metric is appealing for many reasons: it does not resort to any parameters (such as the threshold in [START_REF] Pei | DeepXplore: Automated Whitebox Testing of Deep Learning Systems[END_REF] or the number of sections in [START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF]), apart from the bounds l i and u i that can be determined when the network is initialized by processing the input distribution. It provides a better sense of coverage than previous metrics: NCov and KMNCov only check if there is one occurrence of an activation among their respective binning strategy, whereas optimizing our coverage discrepancy aims at flattening evenly the activation pattern. The major caveat of our metric comes from the fact that the a i are not necessarily known since all practical use cases have finite datasets. Nevertheless, the distribution a i can be approximated using m samples (n i (θ, x 1 ), ..., n i (θ, x m )) = (a 1 i , ..., a m i ). We choose to perform a kernel density estimation presented in Section 2.6 for its simplicity and its plain dependency to activation values (a 1 i , ..., a m i ). We select the Gaussian kernel for approximating the density, we discuss the choice and relevance of the parameters at the end of this section. Let h > 0:

a i (t) ≈ 1 mh m j=1 K t -a j i h ,
where

K(x) = exp( -x 2 2 ) √ 2π .
This expression is the same as [START_REF] Feinman | Detecting adversarial samples from artifacts[END_REF][START_REF] Kim | Guiding deep learning system testing using surprise adequacy[END_REF] where they use it as a way to quantify surprise in an input. However, here we use it for the purpose of estimating our coverage metric. We approximate equation (4.2.1) using this estimation of the a i :

Cov(a i , θ) ≈ Cov (a i , θ) def = -KL   U (l i , u i ), 1 mh m j=1 K • -a j i h   . (4.2.2)
We define the coverage of a network as the mean of the coverage of all the neurons in the network:

Cov(f, θ) = 1 |N | i∈[|N |]
Cov(a i , θ). (4.2.

3)

The dependency in θ is key since we will further aim at designing the parameters of the model with respect to this coverage metric. It obviously depends on the unknown input distribution ρ ∈ P(X ) and can be approximated on a batch of data X = (x 1 , ..., x m ), here a j i = n i (x j ), i.e. the local sampled activation i for input sample j:

Cov(f, θ) ≈ Cov (f, θ)(X) = 1 |N | i∈[|N |] -KL   U (l i , u i ), 1 mh m j=1 K • -a j i ) h   . (4.2.4)

Selection of various hyperparameters and general remarks:

Some details on the different errors of approximation and the selection of some of the constants need to be discussed:

• Selection of the kernel function: for the optimization process, that resorts to subgradients, the kernel needs to be C 1 almost everywhere thus discarding the use of window kernels. In order to approximate a distribution on a closed using a kernel with finite support would have been more advised. However, the KL divergence requires the two measures to share the support of the first argument in order to be computed correctly: using a finite support kernel on an empirical distribution does not ensure that the KL divergence is well defined for any samples. For computational simplicity, the Gaussian kernel was much more suitable: it ensures the KL divergence to have a finite real value for any sampled activations.

• The selection of l i and u i : for each activation an l i and u i are needed for the computation of the KL divergence. One can select them arbitrarily but this would mean more control over the initialization of the parameters. Throughout our experiments we compute them after the initialization of the weights by processing the training set, l i and u i are then kept the same throughout the whole training procedure.

• Selection of the bandwidth h: h defines how smooth the approximated distribution should be. An h too large would make an estimated distribution that has consequent mass outside the [l i , u i ] interval that would introduce bias. On the other hand, a small bandwidth would not ensure a proper estimation of the activation distribution as it would be plagued by sampling errors from the input distribution. We followed [START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF] and selected h = 4σ 3k

1 5
where σ is the standard deviation of the data points from which we want to estimate the distribution. This choice is to ensure some regularity on the estimated distribution. Another possible choice would have been to make an optimization with respect to h in order to fit the target uniform distribution at each density estimation. This would have been a more expensive fitting step but more accurate. For an in-depth review on methods for bandwidth selection see [START_REF] Jones | A brief survey of bandwidth selection for density estimation[END_REF].

• The sampling error: in order to compute the activation distribution, the input sampling has to be representative enough of the input data, it is the case if the whole training set is used in order to compute the coverage metric. However, as deep learning usually resorts to stochastic subgradient descents, equation (4.2.4) is bound to be further approximated using mini-batches. Each mini-batch therefore needs to be representative enough to have small sampling error on the coverage metric.

• The approximation error of the KDE method: although we discussed the choice of the kernel and the bandwidth in previous remarks, it remains that any amount of Gaussian kernel cannot approximate exactly a bounded uniform distribution. Therefore, there will always be an error of approximation in the activation distribution as long as the KL is used jointly with a Gaussian kernel. Possible alternatives for a lower error could be using a distributional distance well defined in the case of disjointed supports such as the Maximum Mean Discrepancy (MMD) or the Wasserstein distance.

• Approximation of the KL divergence: in practice, we evaluate equation (4.2.2) using a rectangle rule for numerical integration. Of course, Cov(a i , θ) depends on the parameters θ of the network since the activation samples do and therefore so does the approximated activation distribution.

The expression of the coverage depends on both the parameters θ and the data batch X meaning that we can either seek to increase the coverage by perturbing slightly the input values or we can seek the adequate parameters that would ensure a well covered network. This give us two possible ways of exploiting this coverage metric: from the perspective of an attacker the coverage can be maximized by changing slightly the input in order to find erroneous behavior. From the perspective of a defender, it is possible to find the parameters that increase coverage during training times to mitigate the exploitation of blind spots by an attack. In order to put these hypotheses to the test in section 4.3 we have to define the attacks and trainings that we will be comparing.

Coverage as an attack on DNNs

In this section, we present different ways to perturb the prediction of a neural network by altering the input values within a given perturbation set. We first present an approach that resorts to coverage only and then we proceed to combine this coverage optimization with more traditional methods from adversarial attacks in an attempt to make the most of both world. Throughout this section we will be noting p ∈ N the input dimension and q ∈ N the output dimension.

Coverage attack. This "attack" is simply a search of a bounded local perturbation δ = {δ 1 , ..., δ m } ∈ (R p ) m of the input values of the test set X = {x 1 , ..., x m } ∈ (R p ) m in order to increase the coverage of the model. It corresponds to tackling the following problem:

max δ i ∞≤ǫ,i∈[m] Cov (f, θ)({x i + δ i , i ∈ [m]}). (4.2.5)
In practice, the (δ i ) i∈[m] are found by performing a PGD-like algorithm (see algorithm 1) on the coverage metric from equation (4.2.5). Due to our definition of our coverage metric, we can only compute it on a batch of data.

Hence the necessity of having m inputs and m perturbations.

FGSM and PGD attack with added coverage. We introduced the FGSM and PGD method in Chapter 2 Section 2.4 as heuristics for approximating the argument of equation (2.4.1). The batched version in equation (2.4.5) is key to adding a coverage penalty: in order to provide some sense of coverage to the adversarial attack, we concurrently increase the loss with the coverage objective of equation (4.2.5). We resort to a constant ν to balance the contribution of each of the objectives:

max δ i ∞≤ǫ,∀i∈[m] 1 m m i=1 ℓ(f (θ, x i + δ i ), y i ) + ν.Cov (f, θ)({x i + δ i , i ∈ [m]}) . (4.2.6)
ν allows exploring between the pure adversarial attack for ν = 0 and the pure coverage attack when ν → ∞. In practice, we seek the (δ i ) i∈[m] with a PGD-like algorithm as well by increasing this composed objective.

Carlini and Wagner attack with added coverage. The C&W attack can be as well processed in a batched manner thus allowing us to define a coverage version of this attack in the same fashion that we did in equation (4.2.6):

min δ i ∞≤ǫ,y ′ i =y i ,y ′ i ∈Y,∀i∈[m] 1 m m i=1 ℓ(f (θ, x i + δ i ), y ′ i ) -ν.Cov (f, θ)({x i + δ i , i ∈ [m]} . (4.2.7)
The sign before the coverage has changed since the C&W attack is solution to a minimization problem, not a maximization like FGSM or PGD.

Random attack. This "attack" serves the purpose of giving a baseline: it is adding a random noise to the input, thus perturbing the decision-making. Any perturbing δ ∈ R m is thus sampled uniformly on B ∞ ε (0).

Coverage as a defense for DNNs

We present two main strategies for improving a training procedure using coverage: the first one is similar to a regularized training where we add coverage in the form of a penalty function that helps to reduce the variance by introducing some bias in a vanilla training. The second approach is basically a data augmentation method where the noise introduced to perturb the dataset comes from the attacks that we defined in the previous section

Vanilla training with added coverage. A first logical approach when considering a coverage metric, is basically to increase coverage at training times in order to ensure that activations are well covered. More precisely, we act on the parameters θ ∈ Θ of the neural network in order to concurrently minimize an empirical loss and maximize the coverage. In the same manner than we did for adversarial attacks, we will here balance the objectives by resorting to a constant ν:

min θ∈Θ m i=1 ℓ(f (θ, x i ), y i ) -ν.Cov (f, θ)({x 1 , ..., x m }). (4.2.8)
This problem can be approximated using the classical tools from deep learning (i.e. diverse subgradient based optimizers).

Robust trainings against attacks. This approach resorts to the attacks elaborated in section 4.2.2 and uses them to perform adversarial training. For the sake of clarity we shall remind the readers of the method described in the preliminaries (Section 2.4.2): An attack (Attack ∈ {Coverage, PGD, FGSM, ...}) is a procedure that resorts to a loss function L (defined at the same time than the attack in section 4.2.2 or 2.4), parameters θ of the neural network, an input/output tuple (x, y) and a bounded perturbation C = B ∞ ε (x) set. It returns a perturbed input x = x + δ, the adversarial training writes:

min θ∈Θ E (x,y)∼ρ k [ℓ(f (θ, x + δ), y)]
where x + δ = Attack(L, θ, B ∞ ε (x), x, y).

(4.2.9)

In other words, it exploits adversarial attacks to create fooling samples that are later used as a part of the training set in order to design the parameters θ robust to perturbations. Ultimately, this approach allows building as many defenses as there are of attacks, namely: defense against the coverage attack, adversarial defense against FGSM, PGD and C&W and their versions with added coverage or even defense against random attacks. Since we are using subgradient based methods for computing the attacks, our applications do not come with guarantees of optimality.

The following section will elaborate empirically on the advantages/disadvantages of using coverage conjointly with adversarial attacks or adversarial training.

Experiments

Throughout these experiments we will perform tests on classification settings on public datasets such as MNIST [START_REF] Lecun | Handwritten Digit Recognition with a Back-Propagation Network[END_REF], FMNIST [START_REF] Xiao | Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms[END_REF], CIFAR10 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] and SVHN [START_REF] Netzer | Reading digits in natural images with unsupervised feature learning[END_REF]. We used the Cross Entropy loss between the prediction from the neural network and the real labels: ℓ(y pred , y real ) def = q i=1 y real,i log y pred,i . The classification setting has been chosen since it is a classical framework for comparing empirically the quality of different attacks and on top of that it is the only framework on which one can apply the C&W attack. We will first consider the point of view of an attacker trying to leverage coverage to fool the model in section 4.3.1. It has been showcased [START_REF] Ma | DeepGauge: multi-granularity testing criteria for deep learning systems[END_REF][START_REF] Xie | DeepHunter: a coverage-guided fuzz testing framework for deep neural networks[END_REF] that adversarial attacks tend to increase coverage, we intend to assess if the opposite holds true as well: whether increasing coverage makes good adversarial perturbations. Secondly we will take on the role of a defender that aims at building a reliable decision system with a limited number of blind spots in the activation pattern: our metric allows to perform trainings that maximize coverage conjointly with minimizing the objective. We will assess the benefits of using such a mixed approach in Section 4.3.2.

Assessing coverage attacks

Pure coverage against usual attacks

The first experiment aims at highlighting if the coverage metric is sufficient for generating adversarial samples, i.e. if solving problem (4.2.5) provides perturbations δ altering significantly the prediction of the model. We compare the performance of a vanilla trained model on this "Coverage attack" against performance on a pool of common adversarial attacks: FGSM, PGD (equation 2.4.1), C&W (equation 2.4.4). We add two performance metrics that will serve as our baselines: the accuracy (i.e. percentage of correctly classified samples) on an unaltered test set and the accuracy on a test set perturbed with bounded white noise. Currently, our interest lies in the capacity of an attack to perturb the model thus the lower is the performance of the model, the better is the attack.

We tested all the previously named attacks on a Resnet18 network (non-adversarially) trained with the ADAM optimizer [START_REF] Diederik | Adam: A method for stochastic optimization[END_REF] on different classification tasks: the MNIST [START_REF] Lecun | Handwritten Digit Recognition with a Back-Propagation Network[END_REF], FMNIST [START_REF] Xiao | Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms[END_REF], CIFAR10 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] and SVHN [START_REF] Netzer | Reading digits in natural images with unsupervised feature learning[END_REF] datasets. On all databases the network was trained for 20 epochs and a batch size of 50. The coverage attack uses the activations of the penultimate linear layer: this reduces the total computational load. The comparison between the coverage attack and the other approaches is slightly biased as the computation of the coverage can only be performed over a batch of data, whereas the computation of an adversarial attack can be performed input-wise.

On Table 4.1 the coverage on its own does not appear to perturb significantly the prediction since it is systematically the attack with the lowest success rate (i.e. the percentage of successful perturbations) for all the datasets considered. This result is not new [START_REF] Yan | Correlations between deep neural network model coverage criteria and model quality[END_REF] and simply shows that the task of perturbing models is performed better by algorithms whose aim is explicitly to fool the prediction. The performance on a perturbing set maximizing the coverage is quantitatively similar to the one of naive random noise: the increase in coverage does not appear to be perturbing the prediction of the model significantly. This does not prove that maximizing the coverage is equivalent to perturbing randomly the model, but it appears that increasing the coverage does not serve the exact purpose of changing the prediction.

Combining coverage and adversarial attacks

We have seen in section 4.3.1.1 that coverage on its own does not appear to be able to perturb the model efficiently compared to adversarial attacks. The next step is to assess if some combination of the two could provide a significant advantage. To that extent, we use the attacks defined in equations (4.2.6) and (4.2.7) that leverage the performance of adversarial attacks with some weighted contribution of coverage. By making ν vary we will explore if there exists a possible cross effect between adversarial attacks and coverage. Let us note that the magnitude of ν is not conditioning the step sizes of FGSM, PGD and C&W due to the fact that they are performing gradient steps using only the sign of the gradient (see algorithm 1). However, ν influences the prevalence of coverage over the objective: the higher the constant ν the greater the chance that the direction of the coverage will be selected for a given parameter update. The goal is to highlight if coverage can provide sensible perturbation directions that could be exploited by the adversarial attacks. We will be increasing ν progressively in order to see if any percentage of coverage insight can be beneficial or if it will simply degrade the performance of the attack. The protocol is the following: on a non adversarially trained Resnet18 on MNIST we will be measuring performance of the model under attack for varying values of ν. Since we are taking on the role of the attacker: the lower is the performance, the better is the attack. We display in Figure 4.1 the evolution of the adverse accuracy with respect to the coverage weight ν. To make asymptotic behaviors more visible we displayed as well the performance of the attacks without coverage and the coverage attack: they are constant in all the charts since they don't actually depend on the coverage weight ν.

Asymptotic behaviors are respected for the C&W attack (Figure 4.1, left) as the limits do converge towards the uncombined attacks when ν goes to 0 and converges towards the performance of the coverage attack when ν goes to infinity. Considering the FGSM and PGD attack (Figure 4.1, middle and right) the blue and red curves do not meet when ν goes to zero, after some extended testing we devised that this is caused by the fact that the gradient of the training loss on the training points are null due to the gradient of the loss function having a small norm. This is caused by the gradient descent method used for optimizing that enforces first order optimality conditions, whereas the coverage measure was not maximized during training. Therefore, the coverage always has gradients that surpass the one of the loss of the FGSM and PGD attack despite the very low multiplicative constant ν. The fact that it does not happen for the Carlini and Wagner attack comes from the fact that the gradients exploited by this attack concern another loss function than the one used for the training on which we did not enforce first order optimality conditions. As the C&W targets the second most probable outcome and increases its likelihood, it allows to have non-null first order information that is greater than the one from coverage when using a small ν. The main result of these graphs is that for no value of ν on the curve do we see an advantage in using a combination of adversarial attacks and coverage over using the adversarial attack on its own: it appears as if any scale of coverage gradient does not provide relevant information for perturbing the prediction of a model. On top of that, it is consistent over all three attacks: showing no improvement over the baseline (blue curve). These tests were performed on FMNIST and CIFAR10 and SVHN with similar results and we observed the same transitions between the pure attack and pure coverage and no positive effect of mixing the two approaches. These results advocate for the fact that coverage (as we defined it) does not relate conjointly with adversarial attacks to adversarial robustness.

Assessing coverage defenses

Maximizing coverage alongside an adversarial attack does not give any significant adversarial robustness as it has been showcased in section 4.3.1. Yet, it remains to devise whether coverage can bring a certain level of robustness when it is used as a mean for enhancing the training procedure. We would like to assess if there is a real advantage in using noise that increases coverage over naive white noise and/or adversarial noise to perform data augmentation.

The effect of vanilla training regularized with coverage

First, we test if increasing coverage during a vanilla training (equation (4.2.8)) increases robustness. We train a Resnet18 on MNIST, FMNIST, CIFAR and SVHN for 20 epochs and a batch size of 50. For the trainings, we selected two possible values of ν: ν = 0 (thus making the impact of the coverage null) and ν = 100. The value ν = 100 has been selected by cross validation: it was the value that resulted in the best trade-off between accuracy and robustness.

If we take a look to the results in Table 4.2 we see that, indeed, when coverage is used for the training we obtain a more robust network against adversarial attacks with a consistent gain in adversarial accuracy (16% gain for MNIST, 10% for FMNIST, 3% on CIFAR10 and 12% on SVHN). We do appear to degrade the test accuracy when doing so, however, the benefits on robustness out-weight the loss on accuracy. The coverage criterion appears to act just like a regularization: in the trade-off between bias and variance we increase the bias by adding an extra term in the loss function that aims at reducing the variance of the prediction. The gains are significant , they are much smaller than usual gains when performing adversarial training.

Training on coverage attacks

In an attempt to make the most of both world, we devised a second range of experiments where we use the attacks built in section 4.3.1 in order to perform adversarial training and then we probe the adversarial accuracy using reference attacks and coverage attacks. The list of the probed approaches for training and attacking is as follows:

• Unperturbed Coverage: corresponds to performing the training as described in paragraph 4.2.3, this is only a defense thus it cannot be found in the range of attacks.

• No Perturbation: corresponds to an unperturbed test set as an attack and to vanilla training as a defense.

• Random: corresponds to perturbing randomly with a uniform noise as an attack and to training against white noise as a defense.

• FGSM: corresponds to a single step approximation of the argument of problem (2.4.1) as an attack and an adversarial training on this attack as a defense.

• FGSM + Coverage: corresponds to a single step approximation of the argument of problem (4.2.6) as an attack and an adversarial training on this attack as a defense.

• PGD: corresponds to a multi-step approximation of the argument of problem (2.4.1) as an attack and an adversarial training on this attack as a defense.

• PGD + Coverage: corresponds to a multi-step approximation of the argument of problem (4.2.6) as an attack and an adversarial training on this attack as a defense.

• C&W: corresponds to a multi-step approximation of the argument of problem (2.4.4) as an attack and an adversarial training on this attack as a defense.

• C&W + Coverage: corresponds to a multi-step approximation of the argument of problem (4.2.7) as an attack and an adversarial training on this attack as a defense.

We display in Figures 4.2, 4.3, 4.4 and 4.5 the evolution of the adversarial robustness (i.e. accuracy against the corresponding attack) when making ν vary between 0.0001 and 10000 over our wide range of defenses and attacks. Considering, this time, the perspective of the defender, the higher the accuracy the better as it attests for a better resilience. The values of ν chosen were selected to assess the effect among different regimes for the composed attacks: a regime at low coverage and high prevalence of the adversarial training (ν = 0.001), a regime with prevalence of coverage over the adversarial training (ν = 1000), and two values that aim to bridge the gap between the two (ν = 1.0, ν = 100). Intermediate values between these regimes were assessed as well, however they did not bring any additional enlightenment for the discussion hereinafter. On all figures we observe a similar performance between the coverage used for adversarial training and the training procedure maximizing coverage (respectively line 4 and line 1) except for the coverage attack (column 3) hinting at the fact that both methods achieve the same goal: increasing neuron coverage. However, the gain in robustness is lower than the one using adversarial trainings. Both coverage methods (line 1 and 4) slightly outperform the vanilla training (line 2) on all adversarial robustness, the results of line 1 concerning robustness were already discussed in the previous experiment: coverage training proved to be just as effective Chapter 4 4.4. Conclusions as a regularization and does provide better results than an unconstrained training (line 2). One can also see that random noise manages to perturb pure adversarial trainings (FGSM, PGD and C&W) consistently whereas it hardly perturbs the coverage defenses. Adversarial trainings are still the best when considering adversarial robustness, since they all perform the best against all range of adversarial attacks.

Concerning low coverage contribution to adversarial attacks (Figures 4.2 and 4.

3) we see no change when combining adversarial attacks and coverage compared to the base attack. Except on the random noise attack (column 2) that appears to have a greater impact on adversarial trainings (FGSM, PGD and C&W) than compared to the versions with coverage.

Concerning high coverage contribution (Figures 4.4 and 4.5) we see that all combinations between an attack and coverage get similar result that the coverage trainings with no added robustness.

Overall, the main conclusions about this experiment are:

• Our different approaches of coverage perform similarly: there appears to have little difference in making a coverage guided training or coverage guided adversarial training. They only provide a better training than the vanilla training since it is more robust to adversarial noise.

• Coverage approaches are performing better than adding white noise to input data: it provides a sensible sense of robustness compared to white noise.

• Coverage approaches are outperformed by adversarial trainings when it comes to adversarial robustness: adversarial trainings are still working the best against adversarial attacks.

• There is no happy medium between coverage and adversarial approach: mixing coverage and adversarial training never outperforms, for any value of ν, the performance of pure adversarial training except for the white noise perturbation where the added coverage seems to bring some robustness.

These experiments tend to present coverage trainings or coverage adversarial training as approaches that provide more robustness than a vanilla training however when it comes to adversarial robustness they appear to be performing less than pure adversarial trainings. Our experiments showcase coverage approaches as a regularization that provides more suitable sets of parameters than vanilla training only. There appears to have little benefit of using coverage in conjunction with adversarial training.

Conclusions

Making an analogy between code coverage and neural network coverage for justifying the lack of robustness appears to be flawed. Even if it has been showed experimentally that adversarial attacks tend to increase coverage by exploiting some blind-spots in the model, however seeking to exploit all blind-spots by using coverage does not provide efficient information for the purpose of fooling the model. Indeed, the assumed connections between robustness and coverage do not hold following our double perspective: from the perspective of an attacker using coverage is not efficient as it does not give the directions for a proper perturbation of the prediction. There appears to be no cross effect between coverage and adversarial perturbation since combining both does not result in significant increase in performance of the attack over a wide range of datasets. This hints at the fact that coverage, even in a white box setting where the attacker has access to the model, is not an efficient attack method and a non completely covered neural network is not necessarily lacking robustness. From the perspective of a defender, training with coverage acts similarly to a regularizer and is preferable to a vanilla training when considering robustness metrics. However, it does not outperform adversarial training over targeted attacks: adversarial training is still preferable on a white box settings where the attacker as access to the learned function and can tailor the attack accordingly. Our work does not contradict DeepGauge or DeepXplore that claimed that adversarial attacks are increasing coverage, we add that the opposite does not appear to hold: increasing coverage is not an effective way of perturbing a model. Robustness in neural networks is a complex problem and it appears that there is little way to circumvent the challenges ahead in robust learning using analogies with traditional code diagnosis tools. Theoretical evidences of the presence or absence of a link between robustness and coverage are still missing but all recent experimental developments lean towards the absence of correlated behaviors.

Introduction definition)

. The Lipschitz constant plays an important role in generalization bounds that quantify the expected discrepancy between training error and test error [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF][START_REF] Weinan | The generalization error of the minimum-norm solutions for overparameterized neural networks[END_REF][START_REF] Weinan | Rademacher complexity and the generalization error of residual networks[END_REF]: classically, the generalization gap has a linear dependency to the Lipschitz constant. However, bridging the gap between training and testing error does not attest a better generalization power since shrinking the Lipschitz constant increases robustness but inevitably takes a toll on the capacity of the network to fit complex distributions (since it shrinks the size of the class of models considered). Ideally, one should seek the best compromise between robustness and generalization, however, such a trade-off is application-dependent.

We will distinguish two branches of the literature concerning the Lipschitz constant for neural networks. In the first one, the neural network is conditioned so as to be enforced various (more or less tight) bounds on its Lipschitz constant [START_REF] Miyato | Spectral normalization for generative adversarial networks[END_REF][START_REF] Yoshida | Spectral Norm Regularization for Improving the Generalizability of Deep Learning[END_REF][START_REF] Gouk | Regularisation of neural networks by enforcing Lipschitz continuity[END_REF][START_REF] Cissé | Parseval Networks: Improving Robustness to Adversarial Examples[END_REF][START_REF] Serrurier | Achieving Robustness in Classification Using Optimal Transport With Hinge Regularization[END_REF]; see Section 3.1.1 for a detailed exposition. In the second type of works, authors focus on designing algorithms to compute approximations of upper/lower bounds of the Lipschitz constant on given networks (see the overview in Section 5.1.2). The focus in this chapter will be within this second group.

Contributions

In Section 5.2 we present a constructive approach for designing a network with a prescribed Lipschitz constant. It has the advantage of giving an exact Lipschitz constant for the network but covers a small class of models. Section 5.3 provides a min-max optimization formulation of the problem of prescribing a Lipschitz constant together with a simple algorithm to solve it, though without any convergence guarantee. This is to the best of our knowledge the first attempt at designing a prescribed Lipschitz network without the use of Lipschitz layers. We show numerically the effectiveness of our approach by prescribing neural networks with different values of Lipschitz constant. The soundness of the approach is supported by the fact that the resulting Lipschitz value is close to the objective with small error, despite the lack of convergence guarantees of our algorithm. This method is general but it lacks the guarantees of the former. The exact method is then used to appreciate the approximation properties of Lipschitz assessing algorithms: we are then able to highlight effectively their respective properties and their dependencies to either input dimension and/or parameter dimension.

Relation to prior work

Estimating the Lipschitz constant of a neural network is an NP-hard problem [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF]. Researches started from loose estimations of the Lipschitz constant first with products of matrices norms [START_REF] Huster | Limitations of the Lipschitz Constant as a Defense Against Adversarial Examples[END_REF]. This estimation being increasingly loose with the depth of neural nets, [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF] provided tighter ones: the authors upper bound the Lipschitz constant by casting its estimation into a maximization problem on the gradient norm. However, the problem is NP-hard and their optimization algorithm is not guaranteed to provide the exact solution. [START_REF] Raghunathan | Certified defenses against adversarial examples[END_REF][START_REF] Fazlyab | Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks[END_REF] provide a guaranteed upper bound via semi definite relaxation that are computationally demanding. [START_REF] Latorre | Lipschitz constant estimation of Neural Networks via sparse polynomial optimization[END_REF][START_REF] Chen | Semialgebraic Optimization for Lipschitz Constants of ReLU Networks[END_REF] leverage polynomial optimization that allows to compute an uncertified upper bound of the Lipschitz constant, their performance is compared to a lower bound and a selected few similar approaches. Despite these methodological differences, a common ground of all these approaches are the tests they are performing: given random or trained networks the methods are probed one against another and the one providing the lowest constant is assumed to be the one performing the best (only if the estimation is a guaranteed upper bound). Although interesting for comparing methods, this simply does not answer a basic question: how close the estimation is to the real Lipschitz constant? Usually, the authors compute a lower bound that serves the purpose of giving a reference objective: the upper bound would ideally reach the lower bound if both bounds were tight. Classic computation of a certified lower bound resort to brute force Monte Carlo sampling or gradient based optimization [START_REF] Bungert | CLIP: Cheap Lipschitz Training of Neural Networks[END_REF] of a differential quotient, but the resulting estimation is plagued by approximation errors. Therefore, the discrepancy between the lower bound and the upper bound can never be bridged and cannot be traced back to either the upper or lower bound estimation. Our contribution aims at isolating the sources of errors to have a better view regarding the performance of the different algorithms computing the Lipschitz constant. The main purpose of this chapter is to provide procedures for designing diverse test cases (i.e., diverse neural networks) for which the Lipschitz constant is known. This allows to quantitatively compare and assess algorithms for estimating Lipschitz constants on test cases where the result is expected. The main difficulty is that, since computing the Lipschitz constant of a neural net is an NP-hard problem, so is building a general network with a given Lipschitz constant.

Designing specific networks with known Lipschitz constant

Let us take the notation of equation (2.5.2): we can simply upper bound the Lipschitz constant as done in [START_REF] Huster | Limitations of the Lipschitz Constant as a Defense Against Adversarial Examples[END_REF] by the product of the spectral norm in case the activation function φ is 1 Lipschitz:

L f,X (θ) ≤ d i=1 |||W i |||.
(5.2.1)

Our goal is to tailor (W 1 , ..., W d ) so that this inequality become an equality.

Construction

Let us constrain our weights with the following conditions:

• For all i ∈ [d], W i = O i S i O ⊤ i-1 ∈ R m×m , m ∈ N,
where S i are diagonal matrices of singular values and O i are square orthonormal matrices also of dimension m.

• Without loss of generality we can assume that the greatest value λ max i = max j ((S i ) j,j ) is along the first dimension.

We have to make slight changes to the matrices (O k ) k∈[n] in order to have each of their main direction aligned along a positive dimension.

Let us write O

i = (V 1 i , V 2 i , ...V m i )
with column vectors, we have by definition that

W i V 1 i-1 = λ max i V 1
i . We would like to have that for all i ∈ {1, ..., d}, V 1 i has positive or zero components (note that O 0 is not considered here) so that the ReLU activations do not change V 1 i when it is applied element-wise. To achieve so we simply define for all i ∈ {1, ..., d}:

O * i def = diag sign V 1 i O i = diag sign (O i e 1 ) O i , (5.2.2)
where e i is the i vector of the standard base of R m , sign is the element-wise function defined by:

sign(x) =    -1 if x < 0 1 otherwise.
For all i ∈ {1, ..., d}, O * i is orthonormal since the transformation depicted in equation (5.2.2) is only a symmetry on carefully chosen axes. For the special case of O 0 we select O * 0 = O 0 . Let us consider then the matrices

W * i = O * i S i O * i-1
⊤ and f * (x) neural network composed with the W * i weight matrices. We will now check that Proof. We will now check that we know the value of the Lipschitz constant of the designed network and its main direction:

L f * = d i=1 |||W * i ||| 2 with σ = ReLU.

Verification

d i=1 W * i = O * n d i=1 S i O ⊤ 0 = d i=1 S i = d i=1 λ max i = d i=1 |||S i ||| ≥ L f * .

Designing specific networks with known Lipschitz constant

On top of that for all i ∈ {1, ..., d} we have by construction V 1 i * (i.e. the main direction of matrix i for the singular value λ max i ) whose components are positive or null and thus stable by the ReLU operation σ.

On the other hand, we have for

x * = V 1 0 : f * (x * ) = W * d σ W * d-1 σ W * d-2 ...σ (W * 1 x * ) = W * d σ W * d-1 σ W * d-2 ...σ λ max 1 V * 1 1 = W * d σ W * d-1 σ W * d-2 ...λ max 1 V * 1 1 = d i=1 λ max i V * 1 d . Thus L f * ≥ f * (x * ) 2 x * 2 = d i=1 λ max i . Then L f * = d i=1 λ max i
, we have successfully constructed a neural network with a known Lipschitz constant. The subspace of maximum amplification is a half straight line of the form x = t.V 1 0 , t > 0.

Remark 5.2.2. We could have restricted the construction to only aligning the first singular vectors of the weight matrices and not the other ones: the verification would have remained the same. However, the construction and algorithm 2 (presented in section 5.2.3) would have been more complex for little benefit on the class of models used.

Algorithm for designing Lipschitz test cases

The algorithm presented here is composed of 2 main components:

• A sampling operator in the set of orthonormal matrices [START_REF] Mezzadri | How to generate random matrices from the classical compact groups[END_REF]. Named Orthonormal_Sampling in the algorithm.

• A procedure capable to change an orthonormal matrix in order to make a column indexed i positive (it is only the implementation of equation (5.2.2) for a parametrizable column i). Named Positiva-tion_by_symmetry in the algorithm.

V 0 = O old,1 ; for k = 1, d do O new = Orthonormal_Sampling(m); O new = Positivation_by_symmetry(O new , 1); D = Diag((u i ) i∈{1,2,...,m} ), u i ∼ U (0, 1); D 1,1 = 1; W k = O new .D.O ⊤ old ; O old = O new ; return V 0 , W 1 , W 2 , .., W d ;
Algorithm 2 gives the main directions, and gives matrices aligned along a positive direction. This makes the ReLUs applied between each layer unable to alter the output vector of the main directions and it allows the Lipschitz constant to be equal to the product of the spectral norms of the weight matrices. The numerical values in algorithm 2 make the designed network 1-Lipschitz. Remark 5.2.3. This algorithm can easily be changed for increasing slightly the broadness of the resulting model class:

• Having any Lipschitz constant L by changing the singular values.

• Not aligning the last layer can add an extra difficulty for Lipschitz assessing algorithms while not changing the main direction of the network, to that extent one should ensure that the singular values of the last layer do not shrink the main direction significantly compared to other directions. This feasible as there are no ReLUs after the last layer and thus the problem is linear. This does change the Lipschitz constant that can be computed by processing the main direction and checking the norm increase.

• Making different layer size on each layer to make more diverse structures. We kept the algorithm minimal to make it more understandable but some of the improvements listed above may seem necessary for increasing the diversity of the networks generated. Nevertheless, the most general networks are the one made by solving equation (5.3.2) which we discuss in section 5.3. Remark 5.2.4. Algorithm 2 is not an ideal case since the Lipschitz constant of a random neural network with normalized layers is actually shrunk by the nonlinearities (see [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF] lemma 2). On top of that, we are creating a very specific case where finding the Lipschitz constant can easily be achieved by finding the main direction of the first weight matrix. Consequently, we are expecting any greedy algorithm seeking the main direction to perform exceptionally well on these samples. Once again, let us emphasize that models made using algorithm 2 offer a biased test case for an algorithm computing the Lipschitz constant. However, if such algorithm fails this test, it is a good indicator that the method, as it is implemented, has difficulties for approximating correctly the Lipschitz constant.

In an attempt to attend to the lack of generality of our naive construction of matrix weights, we devise in the following section a method for making more diverse structures with the same goal of controlling the Lipschitz constant of the network.

Designing general networks with known Lipschitz constant

In this section, we propose an approach that initializes randomly a model (a neural network) with a given structure. Its parameters are then optimized in order to fit a fixed target Lipschitz constant. We start by introducing notations and elementary definitions, and then present the theoretical bi-level optimization problem to solve. We subsequently provide an algorithm for approximating a solution of this bi-level optimization problem. Finally, we test the algorithm by performing some prescriptions of various values of Lipschitz constant.

Formulation as an optimization problem

Given a prescribed target Lipschitz constant L, the objective becomes:

Find θ * such that L f,X (θ * ) = L. (5.3.1)
It is intended in equation (5.3.1) that such θ * exists. Observe also that θ * is not unique in general by obvious ambiguities (scale for instance). Thus, problem (5. Proof. Let us remind the expression of L f,X (θ) from equation (2.5.3):

L f,X (θ) = sup x∈X d-1 i=1 W ⊤ i diag (G φ (f i (θ, x))) W ⊤ d ,
where f i (θ, x) is the notation for intermediate layer activation from 2.2.

d-1 i=1 W ⊤ i diag (G φ (f i (θ, x))) W ⊤ d
is a continuous function in both x and θ as we assumed G φ (•) to be continuous. The spectral norm is continuous, hence lower semicontinuous. The supremum in x is thus a lower semicontinuous function in θ. This together with compactness of Θ entails that the minimization problem (5.3.2) has a nonempty compact set of minimizers.

The C 1 assumption might be weakened but we will stick with this assumption for now. The compactness assumption on Θ also makes sense at least for some of the parameters to remove the ambiguities.

Remark 5.3.2. In any approach above, one has to appeal to some second-order information on φ, i.e., at some point to differentiate G φ (z) with respect to z. In turn, this necessitates a higher order smoothness on φ compared to our work on robust optimization in Chapter 6 (which is not the case for the usual piece-wise linear activation functions).

Algorithm for solving equation (5.3.2)

A heuristic way to solve problem (5.3.2) is to alternatively maximize on x and then apply a generalized (sub)gradient descent step in θ. Our approach is summarized in algorithm 3, where the inner maximization step is replaced in practice by a PGD-like algorithm maximizing the spectral norm (equation (2.5.3)) with respect to the input x.

Algorithm 3: Pseudo-algorithm for approximating the prescription of a Lipschitz constant

Input:

θ 1 = (W 1 i , b 1 i ) i∈{1,.
..,d} initial parameters of the network Input: L the target Lipschitz constant Input: (γ k ) k∈N the decaying learning rate for k = 1, n do

x * k ∈ Argmax x∈X d-1 i=1 W k i ⊤ diag(G φ (f i (θ, x))) W k d ⊤ ; L(θ k , x * k , L) = ℓ( d-1 i=1 W k i ⊤ diag(G φ (f i (θ, x * k ))) W k d ⊤ , L); u k ∈ G L(•,x * k , L) (θ k ); θ k+1 = θ k -γ k u k ; return θ n ; In algorithm 3, G L(•,x, L) (θ) is a generalized derivative of L with respect to variable θ evaluated at (θ, x, L).
Clearly, it is hoped that algorithm (3) provides an approximation to a solution of problem (5.3.1), though we do not provide any guarantee on this.

Evaluation of algorithm 3

We first evaluated the performance of algorithm 3 for enforcing a Lipschitz constant on a given network by building networks with different targets L.

All the experiments were performed with a 6 layers linear neural network with 30 neurons on each layer. The input size is taken equal to the layer size: 30. We chose the ELU activation function as it is C 2 . We chose to prescribe the Lipschitz constant for the spectral norm by using power iterations for computing the operator norm. We noticed that enforcing a 1 spectral norm on all layers except the last one helps for convergence. It reduces the number of symmetries in the solution without any loss of generality. The optimization is performed using a stochastic gradient descent with a decaying learning rate. The initialization of the network [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF] is the same have a Lipschitz constant of 1, this is an arbitrary choice but it can be changed easily with an appropriate scaling of the layers.

Highlighting certified/uncertified bounds

Some algorithms are giving a certified upper bound; this bound can be reasonably loose depending on the approach used. Some other algorithms provide a certified lower bound: the returned value is always lower than the actual Lipschitz constant. Finally, there exists also uncertified upper/lower bounds that aim at approximating an upper/lower bound but with no guarantees to provide a value that is above/below the Lipschitz constant. These statements can be assessed empirically if we use models from algorithm 2 to observe the magnitude of the error. We will consider the following algorithms:

• The LipSDP-network algorithm [START_REF] Fazlyab | Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks[END_REF] in Figure 5.3: the algorithm gives a certified upper bound.

• The SeqLip algorithm [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF] using a greedy approach in Figure 5.4, the algorithm gives an uncertified upper bound.

• The SeqLip algorithm using a genetic optimizer in Figure 5.5, the algorithm gives an uncertified upper bound.

• A certified lower bound computed by sampling uniformly the input space in Figure 5.6. The protocol of the experiment is as follows: for a given layer size and depth, we design a network using algorithm 2 and assess the Lipschitz constant using all the methods enumerated above. We have chosen arbitrarily the dimension of the input to be equal to the layer size. We display the evolution of the estimation of the Lipschitz constant when making the layer size and depth vary for each Lipschitz assessing method. We decided not to average the evaluation over multiple experiments because we are trying to display the flaws in given executions of Lipschitz approximations, not an average behavior. Advocating on general performance of the algorithms on neural networks would be biased considering the specificity of networks that we are testing. Therefore, our goal resides in highlighting the dependencies between the methods and the characteristic dimensions of our designed neural networks: both dimension of the inputs and dimension of the parameters. The former solver is greedy -and therefore suboptimal for dealing with an NP-hard problem -and the latter is nondeterministic -and therefore finds the optimal solution provided it has iterated sufficiently. This shows that, although the theory ensures that SeqLip should ultimately provide an upper bound, it is not achieved if the problem is not solved suitably. On top of that, it showcases that the value given by this algorithm should be treated carefully and cannot be compared reliably to a lower bound. Figure 5.6 presents a method for computing a certified lower bound for the Lipschitz constant: a random approach to seek the maximum of the differential quotient. The random search depends only on the dimension of the sampling space (that is taken equal to the layer size in our specific case).

Our prescribed samples allow to appreciate the amplitude of the error without any other source of error plaguing the result. Our experiment is the first of its kind that quantifies the extent of the error of the Lipschitz assessing algorithm on known results. Comparing a value from an algorithm that gives a certified upper bound with an uncertified one hardly makes sense without further considerations on error bounds over the estimation. Indeed, cautions need to be taken when performing such comparisons: one should explicitly state the guarantees offered by a competing method and to which extent the two are comparable. Even though LipSDP and SeqLip are both able to provide a very good approximation on our designed use cases (see Figures 5.3 and 5.5), a poor optimizer on the former (see Figure 5.4) could have us believe it outperforms the latter if we did not know and expect the result (since its estimation of the constant is lower than the one of the two former charts). We advocate for more thorough and rigorous testing procedures and the test we are providing is a sound way to begin with. Ideally one should perform the test on more diverse structures like the ones solution to equation (5.3.2) provided it is solved exactly.

Highlighting computational limits

Our test cases can also serve the purpose of assessing the limits of Lipschitz assessing algorithms and their behaviors alongside validity boundaries: are their predictions still valid next to their validity limits, or are the algorithms already giving a degraded value of the Lipschitz constant? To that extent, we probe the four previous algorithms on a much larger range of values of depth and layer size that should trespass the range of validity of the algorithms. We display in hatches the zones that resulted in an error when executing the algorithms. These figures can be considered as zooming out in the figures from the previous section although the object of this study is more the validity domain rather than the error in the predictions.

On Figure 5.7 we see that the algorithm gives a very good approximation of the Lipschitz constant but on a small region. This is in conformity with the description in the original work from [START_REF] Fazlyab | Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks[END_REF]: this "network" version of LipSDP suffers greatly from the dimension. Figure 5.8 and 5.9 present two different optimizers on the same maximization problem. Figure 5.9 is clearly dependent on the dimension of the parameters as it is displaying similar quality of estimation along the iso-dimension curves (curves of the form: Depth × (Layer Size) 2 = constant) whereas Figure 5.7 displays similar performance along depth values. On the other hand, the random approach (Figure 5.10) seems to suffer drastically less from the dimension than the two previous algorithms making it a more viable choice for computing a lower bound in high parameter dimensions since it only depends on the dimension of the input.

Overall these experiments display that there is no free lunch when dealing with the complex problem of finding the Lipschitz constant: for instance, tractability of LipSDP is the cost for guarantees and accuracy in the result. For Seqlip guarantees and, to some extent, accuracy are the cost for tractability. Many characteristics could make a method preferable over another: the non-exhaustive list of properties are the presence of guarantees, the computational cost, the scope of application (if it is applicable on CNNs, Resnets or RNNs) or if it has error bounds on its estimation. The literature is generally focused on the performance of the algorithms compared to other methods, without any regards to others key properties. Our test allows to check empirically both the computational limits and the factors influencing the error over the estimation of the Lipschitz constant. Ultimately, we believe our method paves the way for a more rigorous and extensive testing of Lipschitz assessing algorithms. Such added testing provides a better perspective over the literature and the compromises it makes.

Conclusions and future work

This chapter introduced a novel paradigm for evaluating and understanding algorithms assessing the Lipschitz constant of neural networks. This work fills a gap in the evaluation of such algorithms, as none of the methods proposed to date have been evaluated on models for which the Lipschitz constant is known. In addition, our experiments allow a better analysis of the estimates given by the algorithms. It helps highlighting the specificity of some approaches, such as the dependency to the input dimension for some of the algorithms or the choice of the optimizer for others. Overall, it allows to improve and validate the parameters chosen for a given estimation algorithm.

In future work, we plan to soften the constraints that we enforced on the neural networks, without sacrificing our knowledge of the Lipschitz constant. Extensions to convolutional layers seems the logical path, but it has its own challenges as the Lipschitz constant depends not only on the parametrization of the convolution layer but also on the input size, which can differ from one sample to another. One could also consider, in the same fashion that we did in this contribution, slightly constrained special cases where it would be easier to actually know the Lipschitz constant of the convolutions beforehand.

Introduction

The need of robust models arises when we are considering modeling in the face of uncertainties. Building a reliable decision-making system in the face of uncertain inputs is central to many critical applications: not only the system has to prove it operates correctly on its operational design setting, but it also has to remain stable under some perturbation. In the literature, stability over some kind of perturbation is referred to as robustness and is one of the main challenges in many areas of science and engineering, for instance in statistical learning. Since there are growing applications in computer vision applied to critical systems, it is crucial to prove that a statistical model can operate under a given level of uncertainty. On some critical cases the model has to remain stable given any possible point in the uncertain set, as if the perturbation was tailored by an adversary to perturb our decision-making. In this context, Robust Optimization allows to optimize under uncertainty without an explicit model of the uncertainties and thus aims at limiting the scope of actions of any adversary perturbing the model.

Problem statement

Let (Z, d) be a (data) metric space with Z = X × Y ⊂ R m , where X (resp. Y) is the input (resp. output) space. Let ρ 0 be a probability measure on Z, Θ ⊂ R p the parameter/action space, L : Θ × Z → R + a loss function such that L(•, θ) is ρ 0 -measurable and integrable for all θ ∈ Θ. Throughout, we assume that Θ is closed. Consider the optimization problem:

min θ∈Θ E z∼ρ 0 [L(θ, z)] . (6.1.1)
Robust Optimization is one contemporary robustification approach to deal with the presence of data perturbations, adversarial attacks, or uncertainties in (6.1.1) [START_REF] Ben-Tal | Robust Optimization[END_REF][START_REF] Bertsimas | Theory and Applications of Robust Optimization[END_REF]. The origin of the RO approach can be traced back to the classical economic paradigm of a two-person zero-sum game formulated as a min-max problem (see e.g., [START_REF] Meisam Razaviyayn | Nonconvex min-max optimization: Applications, challenges, and recent theoretical advances[END_REF] the recent review paper on min-max problems and their applications from a signal processing and machine learning perspective). In this framework, an agent, considered as a defender, is subject to degradation of its performance by a secondary player, the attacker. The defending agent (here θ), whose goal is to minimize an objective function under action constraints Θ, aims at guarding against the degradation of the objective by optimizing its worst value under perturbation without changing the feasibility set of the actions. Put formally, the robust counterpart of (6.1.1) reads:

min θ∈Θ E z∼ρ 0 max d(z,z ′ )≤ε L(θ, z ′ ) , (6.1.2)
where ε > 0 is the size of uncertainty/perturbation/attack, and the perturbation acts pointwise on z in the adversarial risk, which justifies the terminology Pointwise Robust Optimization (PRO) for problem (6.1.2). A common choice is d(z, z ′ ) = z -z ′ q where • q is the ℓ q norm on R m with q ≥ 1 with the usual adaptation for q = ∞. PRO is one way of quantifying the impact of an adversary or perturbation, and other notions of adversarial risk have been proposed in the literature. In particular, in many areas, such as machine learning, the existence and pervasiveness of adversarial examples point to the limitations of the usual independent and identically distributed (i.i.d.) model of perturbations. This points to a more general perspective in which it is not the points themselves that are perturbed, but rather their underlying distribution ρ 0 . This approach is known as Distributionally Robust Optimization (DRO) which takes the form

min θ∈Θ max D(ρ,ρ 0 )≤ε E z∼ρ [L(θ, z)] , (6.1.3)
where D is a discrepancy on the space of probability measures supported on Z. Compared to PRO, DRO allows to consider a larger range of perturbations. The choice of D affects the richness of the uncertainty set and the tractability of the resulting optimization problem. Typical choices are the Wasserstein distances [START_REF] Shafieezadeh-Abadeh | Distributionally Robust Logistic Regression[END_REF][START_REF] Blanchet | Robust Wasserstein profile inference and applications to machine learning[END_REF][START_REF] Blanchet | Quantifying Distributional Model Risk via Optimal Transport[END_REF][START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF][START_REF] Chen | Distributional robust learning under the Wasserstein metric[END_REF], the Maximum Mean Discrepancy (MMD) [START_REF] Staib | Distributionally Robust Optimization and Generalization in Kernel Methods[END_REF] or φ-divergences including the Kullback-Leibler divergence [START_REF] Ben-Tal | Robust solutions of optimization problems affected by uncertain probabilities[END_REF][START_REF] Namkoong | Stochastic gradient methods for distributionally robust optimization with f-divergences[END_REF][START_REF] Duchi | Statistics of robust optimization: A generalized empirical likelihood approach[END_REF]. There are also other ways to parametrize the perturbation set in terms of the distribution moments, support, etc., [START_REF] Goh | Distributionally robust optimization and its tractable approximations[END_REF][START_REF] Delage | Distributionally robust optimization under moment uncertainty with application to data-driven problems[END_REF]. The Wasserstein distance has become very successful in this context, and unlike other distances/divergences, a Wasserstein distance enjoys the remarkable property that its ball around ρ 0 includes measures having a different support, which allows robustness to unseen data. In the rest of this paper, we focus on Wasserstein balls.

A useful observation at this stage is that the objective in the inner problem of the saddle point problem (6.1.3) is concave (actually linear) in ρ. Though this property is apparently appealing, this problem operates in infinite dimension (space of probability measures on Z), and thus is very challenging to solve. The natural question that arises is whether one can have a surrogate of problem (6.1.3) which operates in finitedimension under minimal assumptions on the problem data (for instance L), and if this can come up with provable guarantees. For instance, is there a relationship between DRO (6.1.3) and PRO (6.1.2) (or alike) and hence can we solve the latter as a surrogate for the former ? We will show later that this is indeed the case. On the other hand, the rigorous treatment of problem (6.1.2), though in finite dimension, remains very challenging for general losses L, especially in absence of the important properties of joint convexity-concavity in (θ, z)

6.1. Introduction and smoothness which are key to design efficient and provably convergent algorithms [START_REF] Ben-Tal | Robust Optimization[END_REF]. These assumptions are however stringent and unrealistic in applications we have in mind, for instance in adversarial training with neural networks [START_REF] Goodfellow | Explaining and Harnessing Adversarial Examples[END_REF][START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF][START_REF] Carlini | Towards Evaluating the Robustness of Neural Networks[END_REF][START_REF] Tramèr | Ensemble Adversarial Training: Attacks and Defenses[END_REF]. Iterative solvers used by many authors do not come up with any guarantee. In fact, in such applications, the inner maximization problem is generally non-concave in z and is even provably NP-hard with certain activations such as ReLU [START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF]. The goal pursued in this chapter is thus to design algorithms to solve problem (6.1.2), as a surrogate for problem (6.1.3) under minimal assumptions on the problem data (for instance, without need of joint convexity-concavity) while enjoying convergence guarantees.

Contributions

Our main contributions in this work are:

1. The DRO problem (6.1.3), when D is the Wasserstein distance with Lipschitz continuous ground cost, is approached with a PRO counterpart of the constrained form (6.1.2) with a controlled accuracy that depends on the perturbation radius.

2. To avoid solving the generally intractable inner maximization problem in equation (6.1.2), we first smooth the latter using entropic regularization and then use Monte Carlo integration to approximate integrals. We conduct an error analysis to precisely quantify these approximation errors and provide error bounds both on the objective values and its subgradients. Relying on the theory of Γ-convergence we show in particular that the minimizers of the approximate problems converge to those of PRO.

3. Capitalizing on the above results, we propose provably convergent stochastic (sub)gradient descent (SGD) algorithms to solve the PRO problem. The first algorithm supposes access to an oracle of the inner maximization problem. To avoid the latter, which can be challenging, we also provide an inexact SGD algorithm with asymptotically vanishing error/bias. The error/bias originates from the regularization and integration sampling parameters, and making them decay at an appropriate rate, convergence guarantees to critical points are established without any need of convexity-concavity assumptions on the loss L.

Relation to prior work

There is a substantial body of work on robust optimization dedicated to robust learning. Here we only review those closely related to ours. Many works have studied instances of (6.1.3) for which tractable algorithms can be designed. For D chosen as a φ-divergence, and under some assumptions on L, [START_REF] Ben-Tal | Robust Optimization[END_REF][START_REF] Namkoong | Stochastic gradient methods for distributionally robust optimization with f-divergences[END_REF][START_REF] Duchi | Variance-based Regularization with Convex Objectives[END_REF] propose convex optimization approaches. For the Wasserstein distance, and a limited class of convex losses L and ground costs, some authors convert (6.1.3) into a regularized empirical risk minimization problem [START_REF] Mohajerin | Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations[END_REF][START_REF] Shafieezadeh-Abadeh | Distributionally Robust Logistic Regression[END_REF][START_REF] Blanchet | Robust Wasserstein profile inference and applications to machine learning[END_REF][START_REF] Blanchet | Quantifying Distributional Model Risk via Optimal Transport[END_REF]. For a larger class of losses and ground costs c, (6.1.3) is converted in [START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF] to a Lagrangian form of (6.1.2). Stochastic gradient descent is then applied to this penalized form and convergence guarantees are established under the assumptions that the gradient of the loss L is bi-Lipschitz and the ground cost c is strongly convex. However, their algorithm resorts to an oracle corresponding to solving the inner supremum problem. This is again a challenging problem and even NP-hard. When ρ 0 is the empirical measure and L is Lipschitz continuous in z uniformly in θ the authors in [START_REF] Gao | Distributionally robust stochastic optimization with wasserstein distance[END_REF][START_REF] Staib | Distributionally Robust Optimization and Generalization in Kernel Methods[END_REF] convert (6.1.3) into a finite dimensional saddle point problem different from (6.1.2) (see detailed discussion in Section 6.2). Stochastic coordinate descent was advocated in [START_REF] Staib | Distributionally Robust Optimization and Generalization in Kernel Methods[END_REF] to solve the latter problem but without any guarantee. In this work, we treat a much larger class of losses and costs and use smoothing to translate the inner maximization problem into an integration problem that we approximate with Monte Carlo integration. Overall, this allows us to apply stochastic gradient descent while being able to prove convergence to critical points of (6.1.2). While we were finalizing this contribution, we became aware of the work of [START_REF] Meunier | Mixed Nash Equilibria in the Adversarial Examples Game[END_REF] who also used entropic smoothing to learn an optimally robust randomized mixture of classifiers. Their setting and motivation is however different and their algorithm does not enjoy convergence guarantees.

Organization of the chapter

Section 6.2 shows mild conditions under which DRO can be reasonably approximated using PRO. Section 6.3 is devoted to our smoothing approach and its key theoretical properties. In Section 6.4, we turn to studying provably convergent algorithms to solve the PRO problem. Finally, we illustrate these results on some use cases (Section 6.5) that show the advantages of using smoothing over other heuristics.

Robustness bounds

The goal here is to show how to go from the DRO problem (6.1.3) to the PRO one (6.1.2), provably, by bounding the corresponding objectives. This paves the way to using PRO as a surrogate for DRO provided that ε is not too large. In the rest of the chapter, we assume that L and the ground cost function c satisfy the standing assumption:

(H.1) L is continuous. (H.2) c : Z 2 → R + is continuous, symmetric (c(z, z ′ ) = c(z ′ , z)) and c(z, z ′ ) = 0 ⇔ z = z ′ . Proposition 6.2.1. Suppose that (H.1)-(H.2) hold. (i) If (H.3) for every θ ∈ Θ, ∀(z, z ′ ) ∈ Z 2 , |L(θ, z) -L(θ, z ′ )| ≤ L Z (θ)c(z, z ′ ) with 0 ≤ L Z def = sup L Z (Θ) < +∞. Then 0 ≤ sup Wc(ρ,ρ 0 )≤ε E ρ [(L(θ, z)] -E z∼ρ 0 sup c(z,z ′ )≤ε L(θ, z ′ ) ≤ L Z ε. (ii) If c(z, z ′ ) = z -z ′ q , q ≥ 1, where • is a norm on R m (i.e., W 1/q c
is the q-Wasserstein distance W q ), and L(θ, •) is L Z -Lipschitz continuous with respect to • uniformly in θ, then

0 ≤ sup Wq(ρ,ρ 0 )≤ε 1/q E ρ [(L(θ, z)] -E z∼ρ 0 sup z-z ′ ≤ε 1/q L(θ, z ′ ) ≤ C q,L Z ε 1/q ,
where C q,L Z is a non-negative constant that depends only on q and L Z .

See Appendix 6.7.1 for the proof.

In [START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF] (see also [START_REF] Blanchet | Robust Wasserstein profile inference and applications to machine learning[END_REF]), using Lagrangian duality arguments, it was shown that sup

Wc(ρ,ρ 0 )≤ε E ρ [(L(θ, z)] = inf γ≥0 γε + E z∼ρ 0 sup z ′ ∈Z L(θ; z ′ ) -γc(z, z ′ ) . (6.2.1)
For a fixed parameter γ > 0, this can be seen as a penalized form of the constrained form (6.1.2). Though (6.2.1) is an identity rather than a bound, it faces a few algorithmic challenges to solve. For instance, the joint presence of the expectation and the inner maximization problems makes minimization of the multiplier γ a difficult task. One can of course think of a simple procedure such as bisection but this will necessitate extrasmoothness assumptions and to solve for θ for each value of γ on the bisection. If L(θ, •) has a Lipschitz continuous gradient, and c is strongly convex in its second argument, then it can be easily shown that for γ large enough, L(θ, •)c(z, •) is strongly concave. This has been leveraged by [START_REF] Sinha | Certifying Some Distributional Robustness with Principled Adversarial Training[END_REF] to use gradient descent to minimize over θ, but only for a fixed (large enough) parameter γ. But still, choosing γ is not easy.

In [START_REF] Gao | Distributionally robust stochastic optimization with wasserstein distance[END_REF][START_REF] Staib | Distributionally Robust Optimization and Generalization in Kernel Methods[END_REF], taking c as the ℓ p cost, and ρ 0 the empirical measure on n points, the following bound was established

0 ≤ sup Wp(ρ,ρ 0 )≤ε E ρ [(L(θ, z)] - sup (z ′ i ) i : 1 n n i=1 z ′ i -z i p ≤ε p 1 n n i=1 L(θ, z ′ i ) ≤ L Z /n. (6.2.2)
As in our case, this gives access to a uniform bound, but which depends now on n rather than ε (and thus gets tighter as n increases). However, the price to pay is that, unlike problem (6.2.1), the inner maximization in the surrogate problem (6.2.2) is coupled between all variables in the objective and constraints, necessitating to optimize on a variable in R mn rather than R m .

Entropic regularization

Despite formulating surrogates as devised in (6.2.1) and (6.2.2) and discussed above, solving the resulting minmax problems remains a very challenging task unless stringent joint convexity/concavity assumptions are made. This is the motivation behind our smoothing hereafter.

From now on, we will denote

C ε z def = {z ′ : c(z ′ , z) ≤ ε}.
The PRO problem now reads

min θ∈Θ E z∼ρ 0 max z ′ ∈C ε z L(θ, z ′ ) . (6.3.1)
We will use the shorthand notation1

g(θ) def = max z ′ ∈C ε z L(θ, z ′ ).
Provided that C ε z is bounded, hence compact since it is closed by assumption on c, and recalling the continuity assumption (H.1), the set of maximizers in g is a non-empty compact set. The function g can also be equivalently rewritten as

g(θ) = max µ∈P(C ε z ) C ε z L(θ, z ′ )dµ(z ′ ), (6.3.2)
and the integral is a duality pairing between P(C ε z ) and C(C ε z ). We will show that (6.3.2) and its subgradients can be provably approximated following a two-step strategy: first, an entropic regularization followed by Monte-Carlo sampling to approximate the integrals.

Regularized objective

Problem (6.3.2) is concave in µ, but operates in infinite-dimension and is thus hard to solve. Approximating (6.3.2) by an atomic measure supported on a finite set (i.e., replace P(C ε z ) by a finite-dimensional simplex by sampling N points at random in C ε z ), as done by some authors (see e.g., [START_REF] Maher Nouiehed | Solving a class of non-convex min-max games using iterative first order methods[END_REF]), suffers an exponential dependence in 1/m. Indeed, an analysis using Lipschitzianity of L shows that this method achieves an approximation rate of O(N -1/m ), and essentially, this cannot be improved. Rather, we will consider the following regularized version of (6.3.2), namely:

g τ (θ) def = max µ∈P(C ε z ) C ε z L(θ, z ′ )dµ(z ′ ) -τ KL(µ, ν), (6.3.3)
where τ > 0 is the regularization parameter, and ν is a reference measure supported on C ε z . Entropic regularization has been used in several fields including optimal transport [START_REF] Peyré | Computational optimal transport: With applications to data science[END_REF] and semi-infinite programming [START_REF] Wei | An inexact primal-dual algorithm for semi-infinite programming[END_REF].

Observe that C ε z is Lebesgue measurable by continuity of c. In the sequel we also suppose that C ε z is of full dimension, and set ν as the uniform measure

µ U on C ε z , that is ν(z ′ ) = µ U (z ′ ) def = µ L (C ε z ) -1 < +∞ for all z ′ ∈ C ε z .
The KL regularization term then prevents solutions to be atomic measures as such measures are not absolutely continuous with respect to the uniform one.

Remarkably, (6.3.3) is well-posed under mild conditions and has a unique solution taking an explicit form. Proposition 6.3.1. Assume that (H.1)-(H.2) hold and that C ε z is bounded and full dimensional. Then (6.3.3) has a unique solution and

g τ (θ) = τ log E z ′ ∼µ U exp L(θ, z ′ ) τ = τ log   C ε z exp L(θ,z ′ ) τ dz ′ µ L (C ε z )   . (6.3.4)
The proof can be found in Appendix 6.7.2. Note that this is a generalization of the standard log-sum-exp formula for softmax smoothing of the maximum of a finite number of functions, where now the sum is replaced by an expectation wrt to the base measure µ U . Remark 6.3.2. The boundedness assumption on C ε z is very mild and verified in most applications we have in mind, for instance in robust training in machine learning. For instance, when c(z, z ′ ) = ϕ( z -z ′ ) where • is any norm on R m , and ϕ : R + → R + is a continuous increasing function.

Remark 6.3.3.

There have been recently very few papers replacing the Wasserstein distance by its entropic (KL) regularization in the DRO uncertainty set, see [START_REF] Blanchet | Semi-supervised Learning Based on Distributionally Robust Optimization[END_REF][START_REF] Wang | Sinkhorn distributionally robust optimization[END_REF]5]. In all these papers, the focus is on establishing strong duality and deriving the dual problem of DRO with the regularized Wasserstein distance, hence extending the dual problem (6.2.1) under various more or less stringent assumptions. The key property of the dual problem after entropic regularization of the Wasserstein distance is that the inner supremum problem in (6.2.1) is replaced by a smoothed approximation of the LIE (Log-Integration-Exp) type. This was used in [START_REF] Blanchet | Semi-supervised Learning Based on Distributionally Robust Optimization[END_REF] and [START_REF] Wang | Sinkhorn distributionally robust optimization[END_REF] for computational purposes, using for instance bisection on γ but fixed entropic regularization parameter, but with little/no guarantees. The LIE smoothing is reminiscent of ours but it has also distinctive properties. Our uniform base measure in the integration is the same as in [START_REF] Blanchet | Semi-supervised Learning Based on Distributionally Robust Optimization[END_REF], but different from [START_REF] Wang | Sinkhorn distributionally robust optimization[END_REF]. We also embark directly from the PRO problem where the uncertainty is in a constrained form rather than a penalized in the above papers. We thus do not need to optimize or choose γ. Moreover, we let our smoothing parameter decrease (this can be also done in those papers) and we provide strong convergence guarantees of SGD which is lacking in those papers.

Consistency of the regularization

We now turn to describing how g τ in equation (6.3.3) is a good surrogate for g in (6.3.1). We provide both a qualitative result as the regularization parameter τ vanishes, and a quantitative convergence rate. Theorem 6.3.4. Under the assumptions of Proposition 6.3.1, the following statements hold: (i) g τ (θ) ր g(θ) as τ ց 0 + . In turn, g τ Γ-converges to g as τ ց 0 + . (ii) If, moreover, C ε z is convex and full dimensional, and (H.3) holds with c(z, z ′ ) = z -z ′ , where • is a norm on R m . Then for any τ ∈]0, 1] :

g(θ) -h(τ ) ≤ g τ (θ) ≤ g(θ), (6.3.5)
where

h(τ ) = mτ log(τ -1 ) + τ log µ L (C ε z ) µ L (B R C ε z (0)) + τ L Z (R C ε z + D C ε z ), (6.3.6)
and R C ε z is the radius of the largest ball2 contained in C ε z and D C ε z is the diameter of C ε z .

See Appendix 6.7.3 for the proof.

Remark 6.3.5.

1. The convexity of C ε z is again usual in robust training in machine learning. It holds if the robustness cost c on Z is convex. 3. The dependence of the convergence rate function h(τ ) on τ is nearly linear (up to a logarithmic term).

4. For the dependence on the dimension of the convergence rate, the first term grows linearly. So does also the second term since it can be upper-bounded by mτ log RC ε z /R C ε z where RC ε z is the radius of the smallest ball containing C ε z . For the last term, the Lipschitz constant L z of the loss function may also depend on the dimension. This emphasizes the role of the Lipschitz constant of the loss in controlling the robustness of the model.

In view of Theorem 6.3.4, we obtain the following key result, which relates the minimizers of the smoothed problem to those of the original PRO problem. Theorem 6.3.6. Suppose that the assumptions of Proposition 6.3.1 hold. Assume also that

Θ is compact. Let θ ⋆ τ ∈ Argmin Θ (g τ ).
Then the following holds: (i) lim τ →0 + min θ∈Θ g τ (θ) = min θ∈Θ g(θ).

(ii) Each cluster point of θ ⋆ τ , as τ → 0 + , lies in Argmin Θ (g).

(iii) In particular, if Argmin Θ (g) = {θ ⋆ }, then lim τ →0 + θ ⋆ τ = θ ⋆ .
See Appendix 6.7.4 for the proof.

Monte Carlo approximation of the integral

Computing the values g τ (θ) in (6.3.4) necessitates to compute a possibly high dimensional integral. Our goal is to approximate the latter with Monte Carlo integration by uniformly drawing independent samples (z ′ k ) N k=1 in the set C ε z . This gives the approximation

g τ,N (θ) def = τ log   N k=1 exp L(θ,z ′ k ) τ N   .
(6.3.7)

We now provide an error bound for such an approximation. Theorem 6.3.7. Suppose that the assumptions of Theorem 6.3.4(ii) hold. Then, the following holds.

(i) For any t > 0 and every θ ∈ Θ,

|g τ,N (θ) -g(θ)| ≤ h(τ ) + τ e L-L τ t log N 2N , (6.3.8)
with probability at least 1 -2N -t , where h is given in (6.3.6),

L def = inf L(Θ, C ε z ) and L def = sup L(Θ, C ε z ). (ii) Suppose that τ is a function of N , say τ N , with h(τ N ) + τ N e L-L τ N log N N → 0 as N → +∞, then (a) for every θ ∈ Θ g τ N ,N (θ) -→ N →+∞ g(θ) almost surely. (b) If moreover, (H.4) for every z ∈ Z, |L(θ, z) -L(θ ′ , z)| ≤ L Θ (z) θ -θ ′ , ∀(θ, θ ′ ) ∈ Θ 2 , with 0 ≤ L Θ def = sup L Θ (Z) < +∞. Then, almost surely, g τ N ,N (θ) -→ N →+∞ g(θ) for all θ ∈ Θ.
The proof can be found in Appendix 6.7.5.

Remark 6.3.8.

• Observe that since L is continuous by (H.1) and C ε z is compact, L and L are well-defined as minimal and maximal values as soon as Θ is compact.

• If L also verifies assumption (H.5), the bound (6.3.8) can be extended to hold uniformly over θ on any convex compact subset C ⊂ Θ. Indeed, it can be shown, combining our proof in 6.7.5 with a covering argument, that

sup θ∈C |g τ,N (θ) -g(θ)| ≤ h(τ ) + τ e L-L τ (p + t) log N 2N + 8 L Θ,Z D C N ,
with probability at least 1 -2N -t .

• It is important to realize that the claim of Theorem 6.3.7(ii)(b) is different (and stronger) than that of Theorem 6.3.7(ii)(a); observe the order of quantifiers. In the latter, the set of events of probability one on which Theorem 6.3.7(ii)(a) holds actually depends on θ, while it is does not for claim (b). On the other hand getting this uniform claim requires some additional regularity. This discussion is very important when it will come to showing the convergence result of our SGD algorithm.

For fixed τ , the convergence rate in (6.3.8) is nearly O(N -1/2 ). But one has to keep in mind that we have not used any smoothness property of L(θ, •) and used a very simple (uniform) Monte Carlo integration. This could be possibly improved using the rich theory of Monte Carlo integration, see e.g., [START_REF] Caflisch | Monte Carlo and quasi-Monte Carlo methods[END_REF][START_REF] Dick | High-dimensional integration: The quasi-Monte Carlo way[END_REF], but probably at the price of a higher computation cost. Such improvements may also potentially necessitate more sophisticated deviation bounds in the proof instead of Hoeffding's inequality that we use here.

Note that the variance of the samples appears implicitly in (6.3.8) through the exponential term. One can alternatively use Bernstein's inequality instead of Hoeffding to show that

|g τ,N (θ) -g τ (θ)| = O τ σ S t log N N where S = 1 µ L (C ε z ) C ε z e L(θ,z ′ ) τ dz ′ and σ 2 = 1 µ L (C ε z ) C ε z e 2 L(θ,z ′ ) τ dz ′ -S2 .
The error bound (6.3.8) reveals an exponential dependence in τ , and thus for the right-hand side to vanish as τ → 0 + and N → +∞, there is trade-off between N and τ to enforce the term e L-L τ t log N 2N to converge to 0. Taking τ = O 1 κ log N , for any κ > 0 such that κ(L -L) < 1/2, the convergence rate in (6.3.8) is dominated by the first term h(τ ) which scales as O (log N ) -1 . This is obviously a slow convergence rate but reflects the difficulty of approximating the function g in (6.3.1).

Consistency of subgradient estimates

Equipped with the above results, a natural strategy now is to solve the PRO problem (6.3.1) by using g τ,N in (6.3.7) as a (provably controlled) approximation of g. Towards this goal, we would like to apply a first-order scheme, typically (sub)gradient descent. Such a scheme will involve a first-order oracle on g τ,N , the gradient

∇g τ,N (θ) = N k=1 ∇ θ L(θ, z ′ k ) exp L(θ,z ′ k ) τ N j=1 exp L(θ,z ′ j ) τ .
(6.3.9)

The natural question that arises is whether (6.3.9) behaves well as τ vanishes and is a consistent approximation of a Clarke subgradient of g (the latter being accessible via the formula (2.10.2) in Proposition 2.10.1 under mild assumptions). The result in Theorem 6.3.9 shows that this is indeed the case under appropriate assumptions that are stronger than those required for consistency of the (zero-th order oracle) function values established in Theorem 6.3.7.

Chapter 6

Entropic regularization

To show some of our results, in particular Theorem 6.3.9(ii), we will need some regularity properties on the set of maximizers M def = Argmax L(θ, C) = Argmax z∈C L(θ, z) (we drop the dependence of M on θ to lighten notation). We say that a set S ⊂ R m is C r -stratifiable, for some integer r ≥ 1, if there is a finite partition of

S into disjoint C r submanifolds (M i ) i∈I of R m , called strata, with m ≥ dim(M 1 ) > dim(M 2 ) > • • • > dim(M |I| ) ≥ 0.
Theorem 6.3.9. Suppose that the assumptions of Proposition 6.3.1 hold and that (H.5) L(•, z ′ ) is differentiable with ∇ θ L(•, •) continuous in its both arguments (θ, z ′ ) and uniformly bounded by L Θ,Z on Θ × Z.

Then L and g τ,N are continuously differentiable.

(i) If (H.3) also holds, then for every θ ∈ Θ and any t > 0, with probability at least 1 -

2(p + 1)N -t dist ∇g τ,N (θ), ∂ C g(θ) ≤ max(1, 2L Θ,Z √ p)e L-L τ t log N 2N + o τ (1). (6.3.10)
where

∂ C g(θ) = C ε z ∇ θ L(θ, z ′ )dµ(z ′ ) : µ ∈ P Argmax L(θ, C ε z ) . ( 6
dist ∇g τ N ,N (θ), ∂ C g(θ) -→ N →+∞ 0 for all θ ∈ Ξ.
The proof of this result follows from by a simple triangle inequality and using the following two lemmas whose proofs are deferred to Appendix 6.7.6. Lemma 6.3.10.

(i) Under the assumptions of Theorem 6.3.9(i), we have dist ∇g τ (θ), ∂ C g(θ) → 0 as τ → 0 + . (6.3.13)

(ii) Under the assumptions of Theorem 6.3.9(ii),

∇g τ (θ) -→ τ →0 + η(θ) def = M 1 ∇ θ L(θ, z)dµ(z) ⊂ ∂ C g(θ),
where µ ∈ P(M 1 ). 0 for all θ ∈ Ξ.

To show Lemma 6.3.10, one observes that under our assumptions,

∇g τ (θ) = C ε z ∇ θ L(θ, z ′ ) exp L(θ,z ′ ) τ C ε z exp L(θ,v) τ dv dz ′ , (6.3.15)
which is an expectation with respect to a Gibbs measure indexed by τ (and θ) and supported on C ε z . In view of the rule (2.10.2), the proof will then amount to showing that as τ → 0 + , the familty of such Gibbs measures has all its cluster points in the narrow topology (equivalent to the weak-* topology) in P Argmax L(θ, C ε z ) (first claim of Lemma 6.3.10), or that it even converges in the weak-* topology to a measure supported on Argmax z∈C L(θ, z) (second claim of Lemma 6.3.10) 3 .

Clearly, Theorem 6.3.9 tells us that, with high probability, ∇g τ,N (θ) is at most within a ball around the Clarke subdifferential of g at θ. The result also quantifies its radius and how it vanishes with N and τ , and shows the influence of p, the dimension of Θ. Arguing as above, this radius vanishes as N → +∞ by taking τ = O 1 κ log N , for any κ such that κ(L -L) ∈]0, 1/2 -α], α ∈]0, 1/2[. The convergence rate of the first term in (6.3.10) or (6.3.12) is then nearly O (N -α ) (up to logarithmic factors). As far as the o τ (1) term is concerned, we do not have any quantitative estimate for the corresponding rate in the case of (6.3.10). For (6.3.12), a close inspection of the proof Lemma 6.3.10(ii) reveals that the convergence rate in τ is at least

O τ -m-m 1 2 e -κ τ + i>1 τ m 1 -m i 2 + τ 1/2 = O τ 1/2 .
Remark 6.3.12. It is worth noting that the statement of Lemma 6.3.10(i), hence Theorem 6.3.9(i), requires less stringent assumptions than claim (i). However, it only ensures subsequential convergence of the gradient whose cluster points are Clarke subgradients of g. On the other hand, Lemma 6.3.10(ii) not only shows global convergence of the gradient but also gives the precise form of the limit Clarke subgradient, and characterizes the corresponding measure. This in turn necessitates the extra regularity assumptions above.

Remark 6.3.13. Similarly to the discussion in Remark 6.3.8, we again need a little bit more to ensure almost sure convergence simultaneously for all θ. This observation is very important when it will come to using almost sure unbiasedness of the (sub)gradient estimate in our SGD algorithm, which in turn will be crucial to prove our convergence result in Theorem 6.4.2.

Remark 6.3.14.

The assumption that the partition of M is disjoint can be removed by assuming in addition that each intersecting pair of submanifolds (M i , M j ), i = j, do so transversely [START_REF] Lee | Introduction to smooth manifolds[END_REF]Theorem 6.30]. Therefore, M i ∩ M j is also a submanifold whose dimension strictly smaller than that of M i and M j . The main change in our proof will lie in subtracting the contribution of these intersections in (6.7.5), and then use that their dimensions are strictly smaller than that of the largest submanifold.

Robust optimization algorithm via SGD

We are now ready to describe our algorithmic framework to solve the PRO problem (6.3.1) based on stochastic (sub)gradient descent. To make the presentation easier, we assume that Θ = R p though our algorithmic framework can be extended to the case where Θ is a convex closed set by including a projection step onto Θ (see e.g., [START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF][START_REF] Kushner | Stochastic Approximation Algorithms and Applications[END_REF] in different settings). Moreover, as considered in most applications, we take in this section

c(z, z ′ ) = ϕ(z -z ′ ),
where ϕ : R m → R + is a continuous coercive function. It is also even-symmetric and ϕ(0) = 0 by assumption (H.2). We now consider the standard setting where ρ 0 in (6.3.1) is the empirical measure on Z, hence leading to the finite sum minimization problem

min θ∈Θ G(θ) def = 1 M M i=1 g i (θ) where g i (θ) def = max u∈C ε L(θ, z i + u), (6.4.1)
where C ε def = {u ∈ R m : ϕ(u) ≤ ε} is obviously a nonempty compact and full dimensional set by the assumptions on ϕ. It is worth observing that convexity of ϕ is not needed in this section.

Without smoothing

As revealed by Proposition 2.10.1, the Clarke subdifferential has only inclusion rules under finite sum and pointwise maximization. Thus, if in addition to (H.1), is L(•, z i + u) is assumed locally Lipschitz continuous for each (z i , u), (2.10.1) gives us the inclusion

∂ C G(θ) = ∂ C 1 M M i=1 g i (θ) ⊂ 1 M M i=1 ∂ C g i (θ) ⊂ 1 M M i=1 D i (θ), (6.4.2)
where

D i (θ) = conv lim k→∞ ∇ θ L(θ k , z i + u k ) : θ k → θ, θ k ∈ S, u k ∈ C ε , L(θ, z i + u k ) → g i (θ) .
Remark 6.4.1. The inclusion above, for instance the one of the sum rule, is strict in many situations of interest in applications. For the sum rule, one may consider other generalized derivatives or even other (but closely related) fields than the Clarke subdifferential, e.g. the conservative fields proposed in [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF][START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF]. These fields enjoy nice sum and chain rules and coincide with the Clarke subdifferential almost everywhere. After a first version of this work was posted, we became aware of the recent work of [START_REF] Pauwels | The ridge method for tame min-max problems[END_REF] who established that conservative fields deriving from definable potentials also have a calculus rule under pointwise maximization involving again an inner maximization oracle. Thus in the rest of this subsection, we could just use the formula of that conservative field instead of D i and our convergence result will remain true. The advantage of using conservative fields is their rich calculus, including the sum and chain rules. Nevertheless, we will not elaborate more on this to keep the presentation simpler and since anyway, this would necessitate to have the inner maximization oracle.

We are now naturally led to consider the set of critical points:

crit-G def = 1 M M i=1 D i -1 (0). (6.4.3)
Clearly, this set is larger than the set of critical points (∂ C G) -1 (0).

Let (B k ) k∈N be a sequence of nonempty mini-batches sampled independently, uniformly at random in [M ]. We can then devise the following iteration

θ k+1 = θ k -γ k d k , where d k ∈ 1 |B k | i∈B k D i (θ k ), (6.4.4)
and (γ k ) k∈N is a positive step sequence decaying at an appropriate rate. A natural question now is whether the sequence (θ k ) k∈N in (6.4.4) enjoys some convergence guarantees to the set of critical points in crit-G. For this, we will rely on the stochastic approximation method for differential inclusions with compact and convexvalued operators developed in [START_REF] Benaïm | Stochastic Approximations and Differential Inclusions[END_REF], and used recently in [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF][START_REF] Castera | An inertial newton algorithm for deep learning[END_REF]. The idea is to view (θ k ) k∈N as a discretetime stochastic process which asymptotically behaves as the (absolutely continuous) solution trajectories of the differential inclusion

   0 ∈ θ(t) + 1 M M i=1 D i (θ(t))
for almost every t ∈ R,

θ(0) = θ 0 , (6.4.5)
whose stationary solutions are the critical points in (6.4.3). A key argument to invoke the results of [START_REF] Benaïm | Stochastic Approximations and Differential Inclusions[END_REF], is to build an appropriate Lyapunov function and show that the function G is path differentiable, that is, it obeys the chain rule

d dt G(θ(t)) = θ(t), v , ∀v ∈ 1 M M i=1 D i (θ(t)). (6.4.6)
While path differentiability can be shown (see later) for the finite sum under tameness/definability for the Clarke subdifferential, it seems very difficult to deal with the pointwise maximization and to prove path differentiability of g i with the field D i .

The situation however changes if we work under (a part of) assumption (H.5), in which case (6.3.11) applies and (6.4.2) becomes

∂ C G(θ) = ∂ C 1 M M i=1 g i (θ) ⊂ 1 M M i=1 ∂ C g i (θ), (6.4.7)
where .4.8) This gives the scheme in Algorithm 4.

∂ C g i (θ) = C ε ∇ θ L(θ, z i + u)dµ(u) : µ ∈ P Argmax L(θ, z i + C ε ) . ( 6
Algorithm 4: SGD for PRO without smoothing.

Input:

Step-sizes (γ k ) k∈N ; Input: Initialization θ 0 ; for k = 0, . . . do Draw independently uniformly at random a mini-batch

B k ⊂ [M ] ; for i ∈ B k do Solve ūi ∈ Argmax u∈C ε L(θ k , z i + u). d k = 1 |B k | i∈B k ∇ θ L(θ k , z i + ūi ) ; θ k+1 = θ k -γ k d k .
This algorithm enjoys the following guarantees. (0). Moreover (G(θ k )) k∈N converges and G is constant on crit-G. See Appendix 6.7.7 for the proof.

A caveat of Algorithm 4 is that one has to solve the inner maximization problems to compute the subgradient approximation d k as dictated by (6.4.8). We recall that this can be computationally challenging in general and iterative schemes do not come with any guarantees unless stringent assumptions are imposed on L. To avoid this, one can appeal to the smoothing strategy as we develop now.

With smoothing

In this section, we work under the assumptions of Theorem 6.3.9 and capitalize on the results there. This gives the scheme summarized in Algorithm 5.

d k = 1 |B k | i∈B k ∇g i τ k ,N k (θ k ), with ∇g i τ k ,N k (θ k ) def = N k j=1 ∇ θ L(θ, z i + u j ) e L(θ,z i +u j ) τ k N k l=1 e L(θ,z i +u l ) τ k ; θ k+1 = θ k -γ k d k .
The direction d k in Algorithm 5 can also be written as

d k = v k + e k + ζ k ,
where

• v k = 1 M M i=1 P ∂ C g i (θ k ) (∇g i τ k ,N k (θ k )); • e k = 1 |B k | i∈B k ∇g i τ k ,N k (θ k ) -P ∂ C g i (θ k ) (∇g i τ k ,N k (θ k )) ; • ζ k = 1 |B k | i∈B k P ∂ C g i (θ k ) (∇g i τ k ,N k (θ k )) -1 M M l=1 P ∂ C g l (θ k ) (∇g l τ k ,N k (θ k ))
; where all projectors above are well-defined since the Clarke subdifferential is closed (in fact compact) and convex-valued. We then have the following convergence result. (0). Moreover (G(θ k )) k∈N converges and G is constant on crit-G.

See Appendix 6.7.8 for the proof.

From the discussion after Lemma 6.3.10, the vanishing assumption on the bias holds provided one chooses N k an increasing function of k, and τ k decreasing as O 1 κ log N k for κ > 0 small enough. The algorithm remains simple and effective at making the learning robust, the initial value of the parameters N and T do not matter as long as we increase and decrease them respectively. However in practice it is better to select their initial values considering the dimension of the problem. We suggest reading the following sources for considerations on Monte Carlo integration or Quasi Monte Carlo [START_REF] Caflisch | Monte Carlo and quasi-Monte Carlo methods[END_REF] [START_REF] Dick | High-dimensional integration: The quasi-Monte Carlo way[END_REF]. Other algorithms can be used instead of SGD provided they are proven to converge with appropriate generalized subgradients (see [START_REF] Ruszczynski | Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization[END_REF] for instance).

Numerical results

Dataset, model and metrics

The following experiments were all performed on the Avila dataset, introduced in [START_REF] Stefano | Reliable writer identification in medieval manuscripts through page layout features: The "Avila" Bible case[END_REF]. This dataset is representative of a classification task -writer identification in medieval manuscripts through page layout features -with 8 input features and 12 classes. We centred and normalized the input features in a preprocessing step. The label distribution is uneven for the twelves classes (A:41%, B:0.048%, C:0.99%, D:3.4%, E:10%, F:19%, G:4.3%, H:5.0%, I:8.0%, W:0.43%, X:5.0%, Y:2.6%), with a class A that is far more present than the other labels. This dataset was selected for its moderate input dimension to keep Monte Carlo sampling needed for computing (6.3.7) reasonable, and because it has unevenly distributed labels which will help highlighting the compromise between generalization and robust learning. In these experiments, we build a 3 layer MLP network f : Θ × R 8 → R 12 with two hidden layers of 200 neurons each and an output layer, resulting in p = 44000 parameter vector θ; i.e., Θ ⊂ R 44000 . To comply with our regularity assumptions, we used the ELU activation function [START_REF] Clevert | Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)[END_REF]. The loss used for training the model is the cross-entropy loss after a softmax step on the network output, i.e., for a training example z = (x, y), where x ∈ R 8 is a feature vector and y ∈ [START_REF] Ben-Tal | Robust Optimization[END_REF] is the (true) label, the loss is given by

L(θ, z) = -f (θ, x) y + log   12 j=1 e f (θ,x) j   ,
where the subscript here stands for the corresponding entry of a vector. Note that this loss also verifies our assumptions.

All experiments were carried out with the same number of epochs, batch size and therefore the same number of updates (see Table 6.1 for details).

For comparison purposes, we trained the MLP network in 3 different ways: with a vanilla (non-robust) training, an adversarial training using PGD as a heuristic to solve the inner maximization problem [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF], and robust training using Algorithm 5. Our aim is to show that we can provably train a robust model using our algorithm, while being competitive with current state of the art procedures for robustifying neural networks such as adversarial training, for different values of the perturbation radius ε. Throughout this section, we take C ε = B q ε (0) with typically q = +∞ (see Table 6.1).

For a pair (x, y) ∈ R 8 × [START_REF] Ben-Tal | Robust Optimization[END_REF], let F θ (x) = Argmax j∈ [START_REF] Ben-Tal | Robust Optimization[END_REF] (f (θ, x)) j be the predicted label. We denote S : R 2 → {0, 1} the mapping that returns 1 if its arguments are equal and 0 otherwise. In the numerical results, we will report three different performance metrics.

• Test Accuracy: We define it as the accuracy on a test dataset {(x i , y i ) : i ∈ [N test ]}:

Test Accuracy = 1 N test Ntest i=1 S(F θ (x i ), y i ).
• Adversarial Accuracy: This metric is meant to represent the accuracy on an adversarial set given by applying a white-box PGD attack [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF]. The attack depends on the loss function L, a ball B q ε (0) in which the attack is constrained, and a tuple (x i , y i ) of data points to be attacked. It reads

Adversarial Accuracy = 1 N test Ntest i=1
S(F θ (x i ), y i ) where xi = PGD(L, B q ε (0), x i , y i ).

• Worst-case Robustness Accuracy: This is defined as the worst-case accuracy when the data points undergo perturbations within a ball B q ε (0) (the same ball as for the PGD attack). More precisely, recall that µ U is the uniform measure on B q ε (0). For N perturbation samples, this metric is defined as

Robust Accuracy = 1 N test Ntest i=1 min (u j ) N j=1 , u j ∼ i.i.d. µ U S(F θ (x i + u j ), y i ).
For large enough number of samples N , this metric is intended to show robustness as promoted when solving the PRO problem during the training.

We added to these metrics estimates of an upper-bound of the Lipschitz constant of the network. To this end, we chose the LipSDP method [START_REF] Fazlyab | Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks[END_REF] which is efficient, accurate and adequate for the size and structure of the networks used.

These metrics are to be evaluated on the three kinds of training, for different values of ε. We made 100 runs for each configuration with different initializations to account for statistical variability. The training and test sets have been sampled once for all runs to ensure that the variance of the results would come only from differences in the initialization of the model and dynamics of the optimization. The plots we will display show the median value and the quantiles at 0.1, 0.25, 0.75 and 0.9. Remark 6.5.1. Ultimately, the ideal metric for quantifying robustness is the population intractable robust 0-1 gain. It is closely linked to the adversarial frequency [START_REF] Bastani | Measuring neural net robustness with constraints[END_REF] E (x,y)∼ρ 0 min u∈B q ε (x)

S(F θ (u), y) .

The robust accuracy attempts to estimate this quantity by drawing random samples in both the min and expectation. This however may suffer the curse of dimensionality when estimating the min value. The adversarial accuracy uses a heuristic in the form of an adversarial attack obtained by PGD, but the latter does not enjoy any convergence guarantee to the minimal value. The robust accuracy metric appears as a better representative metric of the robust behavior of a model with the proviso that N is large.

Dependence of smoothing factor and number of samples for robust optimization

Following Theorem 6.3.9, we advocated that N , the number of samples used by Monte Carlo integration must increase during the execution of Algorithm 5 and that τ = O( 1 κ log N ), the regularization parameter, goes to zero. However in practice, making the sampling infinite is impossible due to hardware memory limitations. Some workarounds can be found to extend the batch size, however they drastically increase the computation time. Therefore we need to check experimentally how the algorithm behaves with different values of τ and N .

The sampling for the robust training is performed in B ∞ 0.05 (0) for various values of τ and N . The inner maximization problem is assessed and averaged on the test base resorting to a fixed sampling of the perturbation set. This sampling is chosen larger (10 6 ) than the biggest value explored in the set so as to maximize the chance that the metric is evaluated accurately when testing. Figure 6.1 shows the value of the loss for different values of τ and N , after a given number of iterations. The observed behavior is indeed the expected one with respect to the sampling: the more we shrink the temperature and increase the sampling the smaller the error on the robust problem we have.

Robustness to noise

In this section, we present a few experiments illustrating the robustness to noise a model trained with our method, and provide comparisons with alternative methods.

For these experiments, the adversarial training was performed in B ∞ ε (0) and so was the sampling for the robust training: we kept the same fixed sampling of N = 5.10 5 points and a fixed temperature of τ = 10 -4 . Fixing the sampling to the highest possible value ensures the smallest error possible on the estimation of the robust loss. We give in Section 6.7.8 more information about the parameters for these experiments.

We plot the evolution of the test accuracy (Figure 6.2), adversarial accuracy (Figure 6.3) and worst case accuracy (Figure 6.4) against the radius of robustness with median and quantiles. On top of this we also present the evolution of upper bounds of the Lipschitz constant of the learned network estimated using LipSDP [START_REF] Fazlyab | Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks[END_REF] (Figure 6.5) and SeqLip [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF] (Figure 6.6): the former is guaranteed but overestimates the upper bound, the later is not guaranteed but is closer to the real value. For the sake of completeness, and due to the fact that the loss values do not account for the complexity of the distribution of the predictions, we also provide three confusion matrices (i.e., percentage of predicted labels per each class in the test set). We normalized the confusion matrices column-wise as it allows to assess which percentage of the real label was split to which predicted label. The confusion matrices were computed for the vanilla training, for the robust training with ε = 0.3 and the adversarial training with the same value of ε. The results are displayed in Figure 6.7.

On all performance metric (Figures 6.2,6.3 and 6.4) the behavior of our robust training is competitive compared to the popular PGD-based adversarial training, and differences are in general small. We note that robust training is better on the test accuracy for moderate perturbations (Figure 6.2), while adversarial training appears to be slightly better in terms of adversarial accuracy (Figure 6.3). We note, as expected, a decrease in accuracy on the test dataset as the perturbation radius ε increases, but a better tolerance to perturbations/attacks since Chapter 6 6.6. Conclusions increasing the perturbation radius ε, we make the learned model stable to larger adversarial attacks. This is symptomatic of the trade-off between robustness and generalization, see e.g., [START_REF] Tsipras | Robustness May Be at Odds with Accuracy[END_REF][START_REF] Raghunathan | Adversarial Training Can Hurt Generalization[END_REF][START_REF] Yang | A closer look at accuracy vs. robustness[END_REF][START_REF] Dohmatob | On the (non-)robustness of two-layer neural networks in different learning regimes[END_REF]. Note also that the variability across runs is small (and highest for the vanilla training), confirming that the performance of all the trainings is reproducible from run to run and for different initializations.

The decrease in accuracy of the robust and adversarial training on the test dataset can be further understood when considering the confusion matrices in Figure 6.7. Indeed, we see that these two robust learning methods aggregated the labels that were close to label A, namely labels C, D, E, F, G and H: this is due to class A being overly represented as it leans toward aggregating samples that are close. The labelling performed by the robustly trained networks on a test point assigns the label that has the greatest mass in the ε perturbation ball around the test point. This clearly means that some feature vectors originally in classes C, D, E, F, G and H are in fact within a ball B q ε (0) around those of label A. Class B has a very limited number of samples (5, only 0.048% of the dataset), however, it appears to be far enough from the other classes not to be confused with them.

As far as Figures 6.5 and 6.6 are concerned, one can clearly (and unsurprisingly) see that the adversarial and robust training methods tend to monotonically reduce the Lipschitz constant of the learned networks as ε increases. The fact that, on an adversarial set, the vanilla model performs poorly compared to the adversarial one is expected (Figure 6.3), but the performance of the robust model is similar to the adversarial one on this dataset. Of course, adversarial attacks favor those models that have already been trained in an adversarial setting. Our experiments confirm that our approach via smoothing and Monte Carlo sampling on the perturbation set provably converges to a critical point of the PRO problem. This is in contrast to PGD-based adversarial training for which convergence guarantees are not available in such general setting. The main drawback of the robust training remains its computational cost compared to adversarial training. For instance, under the hyperparameters in Appendix 6.7.8 with ε = 0.3, both training methods were performed on the same GPU A100 with the same number of epochs and updates. Adversarial training took 47 min whereas robust training took 11 hours. Adversarial training remains a very effective method for solving empirically the PRO problem. Let us stress that, despite this increased cost, robust training can be more effectively parallelized as it only requires one expensive forward pass and one expensive backward pass whereas the adversarial training requires multiple iterations of both.

Conclusions

Solving numerically the DRO problem beyond stringent assumptions on the loss remains a challenging open problem. Here, we have shown that the DRO problem with sufficiently small error can be approached with a PRO problem. In order to solve the latter, we designed SGD-type algorithms hinging on smoothing of the inner maximization problem and Monte Carlo sampling. Our approach is one of the few that enjoys provable convergence guarantees at the expense of an overall higher computational cost. Our robust training has given performances similar to those of adversarial training on practical examples. This showcases the soundness of using robust training with an adequate sampling. However, in machine leaning applications with overparametrized models involving a very large number of parameters and high dimensional input space, scalability of our robust training framework is still a challenge due in particular to our simple Monte Carlo sampling step. More sophisticated sampling strategies, for instance those based on Langevin diffusion, is one direction that is worth investigating in a future work.

6.7 Appendix: Proofs 6.7.1 Proof of Proposition 6.2.1 (i) For any z ∈ Z and ε ≥ 0, we have

sup z ′ ∈Z L(θ, z ′ ) -γc(z, z ′ ) ≥ sup c(z,z ′ )≤ε L(θ, z ′ ) -γc(z, z ′ ) ≥ sup c(z,z ′ )≤ε L(θ, z ′ ) -γε.
Taking the expectation on both sides, we get

E z∼ρ 0 sup c(z ′ ,z)≤ε L(θ, z ′ ) ≤ γε + E z∼ρ 0 sup z ′ ∈Z L(θ, z ′ ) -γc(z ′ , z) .
In turn, since γ ≥ 0 was arbitrary, we take the infimum on the right-hand side and use the identity (6.2.1), which holds under assumptions (H.1) and (H.2), to get the lower bound.

Let us turn to the upper-bound. We embark from (6.2.1) and consider the case where γ = L Z :

sup Wc(ρ,ρ 0 )≤ε E z∼ρ [L(θ, z)] ≤ L Z ε + E z∼ρ 0 sup z ′ ∈Z L(θ, z ′ ) -L Z c(z ′ , z) ≤ L Z ε + E z∼ρ 0 [L(θ, z)] ≤ L Z ε + E z∼ρ 0 sup c(z,z ′ )≤ε L(θ, z ′ )
where we used the uniform Lipschitz continuity assumption (H.3) in the second inequality:

L(θ, z ′ ) - L(θ, z) ≤ |L(θ, z ′ ) -L(θ, z)| ≤ L Z c(z ′ , z
) and that z is a feasible solution in the last constrained supremum since c(z, z ′ ) = 0 when z = z ′ .

(ii) The proof of the lower-bound part is the same as in the first claim above. Let us turn to the upper-bound. We use again (6.2.1) and Lipschitz continuity of L(θ, •) to get that for any γ ≥ 0, sup

Wq(ρ,ρ 0 )≤ε 1/q E z∼ρ [L(θ, z)] ≤ γε + E z∼ρ 0 sup z ′ ∈Z L(θ, z ′ ) -γ z ′ -z q ≤ γε + E z∼ρ 0 sup z ′ ∈Z L Z z ′ -z -γ z ′ -z q + E z∼ρ 0 [L(θ, z)] = γε + E z∼ρ 0 sup t≥0 sup z ′ -z =t L Z z ′ -z -γ z ′ -z q + E z∼ρ 0 [L(θ, z)] = γε + sup t≥0 (L Z t -γt q ) + E z∼ρ 0 [L(θ, z)] ≤ γε + sup t≥0 (L Z t -γt q ) + E z∼ρ 0 sup z-z ′ ≤ε 1/q L(θ, z ′ ) .
Optimizing for t and after basic algebra, we get

sup Wq(ρ,ρ 0 )≤ε 1/q E z∼ρ [L(θ, z)] ≤ γε + (q -1) L Z q q q-1 γ -1 q-1 + E z∼ρ 0 sup z-z ′ ≤ε 1/q L(θ, z ′ ) .
This upper-bound is minimal for γ = c q,L Z ε -q-1 q , for an explicit constant c q,L Z . Plugging this value of γ in the upper-bound, we get the claim.

Proof of Proposition 6.3.1

We provide a concise self-contained proof as the arguments are standard. We equip P(C ε z ) with the weak-* topology. Continuity of c implies closedness of C ε z . This together with its boundedness assumption imply compactness of C ε z as it is finite dimensional. Thus P(C ε z ) is weak-* compact by [1,Theorem 15.11]. It is also convex. In addition, recall that the weak-* topology is the weakest topology which makes the integration against continuous bounded functions a continuous linear form. In then follows from continuity of L(θ, •) and compactness

of C ε z that µ → C ε z L(θ, z ′ )dµ(z ′ ) is weak-* continuous. It is known that KL(•, µ U
) is convex and lower semicontinuous in the weak-* topology on P(C ε z ). Thus, since τ > 0, the objective in (6.3.3) is convex and upper semicontinuous. This together with convex and weak-* compactness of P(C ε z ) entail that (6.3.3) has a non-empty convex and weak-* compact set of solutions. Uniqueness of the minimizer then follows from strong convexity of KL(•, µ U ) on P(C ε z ) thanks to the celebrated Pinsker's inequality. The closed form solution follows from standard calculus of variations and Lagrangian duality; see e.g., [START_REF] Wei | An inexact primal-dual algorithm for semi-infinite programming[END_REF]Lemma 6.6].

Proof of Theorem

6.3.4 (i) Define ψ τ (θ) def = C ε z L(θ, z ′ )dµ(z ′ ) -τ KL(µ, µ U ).
⋆ ∈ Argmax z ′ ∈C ε z L(θ, z ′ )
, where the latter is a non-empty compact set thanks to continuity of L(θ, •) and compactness of C ε z . We then have

τ log C ε z e L(θ,z ′ ) τ dz ′ = max ẑ∈C ε z L(θ, ẑ) + τ log C ε z e L(θ,z ′ )-L(θ,z ⋆ ) τ dz ′ = g(θ) + τ log C ε z e L(θ,z ′ )-L(θ,z ⋆ ) τ dz ′ ≥ g(θ) + τ log C ε z e -L Z z ′ -z ⋆ τ dz ′ . By definition of R C ε z , there exists z such that B R C ε z (z) ⊂ C ε z . Convexity of C ε z entails that: τ (B R C ε z (z) -z ⋆ ) + z ⋆ = (1 -τ )z ⋆ + τ B R C ε z (z) ⊂ C ε z , and thus: τ log C ε z e L(θ,z ′ ) τ dz ′ ≥ g(θ) + τ log τ (B R C ε z (z)-z ⋆ )+z ⋆ e -L Z z ′ -z ⋆ τ dz ′ = g(θ) + τ log   τ m B R C ε z (z) e -L Z z ′ -z ⋆ dz ′   ≥ g(θ) + τ log   τ m B R C ε z (z) e -L Z ( z ′ -z + z ⋆ -z ) dz ′   ≥ g(θ) + τ log   τ m B R C ε z (0) e -L Z (R C ε z +D C ε z ) dz ′   = g(θ) -mτ log(τ -1 ) + τ log(µ L (B R C ε z (0))) -τ L Z (R C ε z + D C ε z ). ( 6

Proof of Theorem 6.3.7

We have

|g τ,N (θ) -g(θ)| ≤ |g τ (θ) -g(θ)| + |g τ,N (θ) -g τ (θ)| ≤ h(τ ) + |g τ,N (θ) -g τ (θ)|
where we used (6.3.5). It remains to bound the last term. This is the subject of the following lemma.

Lemma 6.7.1. Under the assumptions of Theorem 6.3.4, the following holds.

(i) For any t > 0 and fixed θ ∈ Θ,

|g τ,N (θ) -g τ (θ)| ≤ τ e L-L τ t log N 2N , with probability at least 1 -2N -t . (ii) Suppose that τ is a function of N , say τ N , with τ N e L-L τ N log N N → 0 as N → +∞, then (a) for every θ ∈ Θ g τ N ,N (θ) -g τ N (θ) -→ N →+∞ 0 almost surely. (b) If moreover (H.4) holds then, almost surely, g τ N ,N (θ) -g τ N (θ) -→ N →+∞ 0 for all θ ∈ Θ.
Proof. To lighten the notation, denote

S N def = 1 N N k=1 e L(θ,z ′ k ) τ .
(i) Since the z ′ k 's are independent samples from the uniform distribution supported on C ε z , we have

E[S N ] = 1 µ L (C ε z ) C ε z e L(θ,z ′ ) τ dz ′ .
We then have

g τ,N (θ) -g τ (θ) = τ log S N E[S N ]
.

Using the standard inequality log(1 + t) ≤ t for t ≥ 0, we can write, for any ǫ ≥ 0 (b) Since R p is separable, there exists a countable set T whose closure is Θ. According to claim (a), for every θ ∈ Θ there exists a set of events Ω θ of probability one and, for every ω ∈ Ω θ , g τ N ,N (θ, ω)g τ N (θ, ω) → 0 as N → +∞. Set Ω = θ∈T Ω θ . Since T is countable, a union bound immediately shows that Ω is also of probability one. For fixed θ ∈ Θ, there exists a sequence (θ k ) k∈N in T such that θ k → θ. Let ω ∈ Ω. We have L(θ, z j (ω)) .

Pr (|g τ,N (θ) -g τ (θ)| ≥ ǫ) = Pr log S N E[S N ] ≥ ǫ/τ = Pr log S N E[S N ] > ǫ/τ 1(S N ≥ E[S N ]) + Pr log E[S N ] S N > ǫ/τ 1(S N ≤ E[S N ]) ≤ Pr S N -E[S N ] E[S N ] > ǫ/τ 1(S N ≥ E[S N ]) + Pr E[S N ] -S N S N > ǫ/τ 1(S N ≤ E[S N ]) ≤
We have We now invoke (6.3.5) to infer that

g τ N ,N (θ, ω) = max
|g τ N (θ k ) -g τ N (θ)| ≤ |g(θ k ) -g(θ)| + h(τ N ) ≤ L Θ θ k -θ + h(τ N ),
and thus lim sup

N →+∞ |g τ N (θ k ) -g τ N (θ)| ≤ L Θ θ k -θ .
Collecting the above estimates we get lim sup

N →+∞ |g τ N ,N (θ, ω) -g τ N (θ)| ≤ 2L Θ θ k -θ .
Taking the limit as k → +∞, we obtain g τ N ,N (θ, ω) -g τ N (θ) → 0. This completes the proof. µ L (C) µ L (U ǫ ) .

Passing to the limit as τ → 0 + we get µ τ (C \ U ǫ ) → 0.

Compactness of C implies that P(C) is weak-* compact by [1,Theorem 15.11]. The family (µ τ ) τ ≥0 is then sequentially precompact by Prokhorov's theorem. Let (µ τ k ) k∈N be a subsequence with weak-* cluster point μ. We then have μ(C \ U ǫ ) = 0, and since ǫ is arbitrary, we get that μ is supported on U 0 = Argmax L(θ, C). We thus infer, in view of continuity of ∇ θ L(θ, •) (by (H.5)) that

∇g τ k (θ) = C ∇ θ L(θ, z ′ )dµ τ k (z ′ ) ----→ k→+∞ C ∇ θ L(θ, z ′ )dμ(z ′ ) ∈ ∂ C g(θ),
where we used (2.10.2) in the last inclusion. This is being true for any subsequence (µ τ k ) k∈N , we conclude that all cluster points of (∇g τ k (θ)) k∈N belong to ∂ C g(θ) which is equivalent to (6.3.13). Since, for any i ∈ I, M i is a compact C r -smooth submanifold with r ≥ 2, it is a set with positive reach thanks to [START_REF] Federer | Curvature measures[END_REF]Theorem 4.12] (see [START_REF] Federer | Curvature measures[END_REF]Definition 4.1] for definition of sets of positive reach). Thus, it follows from [START_REF] Federer | Curvature measures[END_REF]Theorem 4.8] that P M i is single-valued and Lipschitz continuous on U i , hence C ∩ U i , for some ǫ > 0 small enough. This together with rectifiability and measurability of the sets C ∩ U i and M i allows to apply the coarea change of variable formula [START_REF] Federer | Geometric Measure Theory[END_REF]Theorem 3.2.22(3)] to get where (-λ j (v)) j are the m -m i eigenvalues of the Hessian ∇ 2 z ′ L(θ, v) for v ∈ M i , which are negative by (H.7)(b), α k is the k-dimensional Lebesgue measure of the unit ball in R k , and

β k def =    2 -k 2 (k -2)(k -4) • (2) for k even 2 -k 2 (k -2)(k -4) • (3) √ π for k odd,
Since the strata are ordered by strictly decreasing dimension, we have from (6.7.6) that for any i > j, Combining (6.7.7) (for j = 1) and (6.7.6) (for i = 1) with (6.7.3), (6.7.4) and (6. Applying this with f ≡ 1 and arbitrary f ∈ C, we get that µ τ converges in the narrow topology to the probability measure supported on M 1 ⊂ Argmax L(θ, C)

dµ(v) = 1 M 1 m-m 1 j=1 λ 1 (u) -1 2 dH m 1 (u)   m-m 1 j=1 λ 1 (v) -1 2   dH m 1 (v).
By the continuity assumption (H.5) on ∇ θ L(θ, z ′ ), we deduce that

lim τ →0 + ∇g τ (θ) = lim τ →0 + C ∇ θ L(θ, z ′ )dµ τ (z ′ ) = M 1 ∇ θ L(θ, v)dµ(v) ⊂ ∂ C g(θ),
where we used (2.10.2) in the inclusion. This concludes the proof. We have made here the dependence on θ, τ and N explicit as it will make our reasoning clearer especially for proving the last claim of the lemma.

(i) It follows from (6.3.9) and (6. + ∇g τ N ,N (θ k , ω) -∇g τ N ,N (θ, ω) . (6.7.9)

Since θ k ∈ T, Ω ⊂ Ω θ k , claim (a) gives us that the second term in the right hand side of (6.7.9) vanishes as N → +∞.

Let us turn to the first term. We have

∇g τ N (θ k ) -∇g τ N (θ) = C ∇L(θ, z ′ )dµ θ k τ N (z ′ ) - C ∇L(θ, z ′ )dµ θ τ N (z ′ ).
By Lemma 6.3.10(i), each weak-* cluster point of (µ θ k τ N ) N ∈N belongs to Argmin L(θ k , Z). Since the latter reduces to a single element z θ k by uniqueness of the maximizer, we get by Prokhorov's theorem that (µ θ k τ N ) N ∈N converges in the weak-* topology to the Dirac measure supported on z θ k . Similarly, (µ θ τ N ) N ∈N converges in the weak-* topology to the Dirac measure supported on the unique maximizer z θ of Argmin L(θ, Z). Consequently, A similar reasoning can be applied to arrive at the same conclusion for the third term in (6.7.9). Passing to the limit in N and then in k in (6.7.9), we have proved that for every ω ∈ Ω lim N →+∞ ∇g τ N ,N (θ, ω) -∇g τ N (θ) = 0, for all θ ∈ Θ.

∇g τ N (θ k ) -∇g τ N (θ) -----→ N →+∞ ∇ θ L(θ k , z θ k ) -∇ θ L(θ, z θ ).
This completes the proof.

Proof of Theorem 6.4.2

We first show that G is definable on an o-minimal structure. Indeed, o-minimal structures enjoy powerful stability results under many operations: for instance sublevel sets of definable functions are definable, finite sums of definable functions are definable, and functions of the type sup v∈S F (u, v) (resp. inf v∈S F (u, v)) where F and S are definable, are definable. Thus since ϕ is definable, so is C ε . This together with definability of L implies that g i is definable for each i. In turn, we get definability of G as a finite sum of definable functions. Chapter 7

Conclusion and perspectives

Robustness in deep learning is a hot topic of interest as regulators and industrials seek ways to open up the scope of applications of these algorithms. Enlarging to critical applications is a double-edged sword: on the one hand, it allows for real gains in performance and more accurate processes. On the other hand, consequences could be dire in the case of wrong prediction making or possible alteration of the decision process by an adversary. There are multiple notions revolving around robustness "certified", "verified", "robust","explainable" and "reliable" that may confound an inexperienced reader. To that extent, we offered clear distinctions that help to grasp the subtle shading between the different contributions and give an easier way to tap into the field of robustness.

Approaches to find an optimal robust model spurred experimentally at first: this had the benefit of providing user-friendly tools and unified frameworks that concentrated major developments and recent researches, however it produced a very large pool of papers that turned out to be outperformed on a short term by other, more accurate, experimental approaches. This trend will be pursuing while no theoretical framework would be able to guarantee and provide an optimal procedure. The theory has been lagging behind due to the rather complex setting of robust neural network learning. Indeed, the current problems considered in robust learning of neural networks are, in complete generality, bi-level optimization problems, non-smooth (and thus non-differentiable), non-convex in their parameters, non-concave in their input variables, thus partially explaining the slower pace of theoretical search on the topic. The results that we provided within the scope of this thesis follow also an experimental-theoretical pattern: we have shown that analogies with other systems can be useful to provide new axis of research but that they do not guarantee results, such assumptions can easily be proven wrong by a single counter example. We provided ways of evaluating in a more standard way algorithms meant for computing the Lipschitz constant of deep learning algorithms, in all generality, this requires solving a robust minmax problem that we approximated using common heuristics. Finally, for a more theoretical result, we presented an algorithm that can, in the limit, approximate arbitrary closely the robust problem against local perturbations. There are still open leads for improvement:

Finding a suitable distance for high dimensions. The main problem of nowadays deep learning comes from the fact that the distance metric that we are using are the exact same one that in small dimension, namely ℓ 2 or ℓ ∞ . Because metrics do not behave similarly with respect to the dimension, having an appropriate distance suited for images might be an asset that many learning procedures could exploit. This is linked to the notion of effective sampling in high dimensions as currently we are sampling on ℓ 2 or ℓ ∞ balls.

Develop Lipschitz constrained networks. We would like to emphasize on the word network as currently the Lipschitz constant is generally bounded layer-wise, this has an overall impact on the freedom that we give to the layers. This could speed up computation as Lipschitz layers are known to be slow to train. Of course scaling from the linear layer or convolution layer to the network itself increases the difficulty of the problem significantly but the overall gains could be drastic.

Scale robust learning to high dimensions. The Monte Carlo sampling that we used for our robust learning has the convenient property of having a sampling error independent to the dimension. However, according to our different tests in higher dimension the sampling needs to grow within unreasonable bounds to ensure the overall convergence. We were unsuccessful at having the same level of performance that we had on small dimensions to state of the art structures on common picture datasets. On top of that random perturbations cannot represent unrestricted attacks (i.e. transformations that do not alter the content of an image such as translations, slight rotations or brightness changes for instance): making robust learning with distances insensitive to transformations such as the Gromov-Wassertein distance [START_REF] Peyré | Computational optimal transport: With applications to data science[END_REF] could be beneficial for taking into account restricted and unrestricted attacks altogether.

The challenges ahead of modern deep learning have not changed ever since adversarial attacks emerged as a serious threat to certification. Yet, the progress has been steady and ever since the discovery of such vulnerabilities, the literature has introduced methods to verify robustness properties on training sets and developed robust training methods. However, a methodology for certifying the use of neural networks in critical applications is still missing. Our contribution strives towards the understanding and the making of robust models in a both theoretical and practical way. We believe this theoretical and empirical tandem can still make great advances as it brings relevant advances to the robustness problem.

Figure 1 . 1 :Figure 1 . 2 :

 1112 Figure 1.1: Building small robustness zones around samples Figure 1.2: Building large robustness zones Figure 1.3: Nearest neighbor classification

Algorithm 1 :

 1 Projected gradient descent Input: A loss function L that depends of θ,x,y Input: A bounded perturbation set C Input: A training sample (x, y) ∈ R m Input: A number of iterations N Input: (γ k ) k∈N a decaying learning rate δ := 0; for k = 1, N do L(θ, x + δ, y) := ℓ(f (θ, x + δ), y); u k ∈ G L(θ,•,y) (x + δ); δ := P C (δ + γ k sign(u k )); return x + δ;

Figure 3 . 1 :

 31 Figure 3.1: Summary of the state of the art on robustness of neural networks.

Chapter 3 3. 2 .

 32 Neural network testing

Figure 4 . 1 :

 41 Figure 4.1: Adversarial accuracy of the model when making ν vary (the lower the curve, the more efficient the attack is) for C&W (left), FGSM (middle), PGD (right) attack augmented with coverage on MNIST dataset. Coverage attack and pure adversarial attack plotted for reference.

Figure 4 . 2 :

 42 Figure 4.2: Adversarial performance of multiple adversarial trainings on MNIST, trainings horizontally and attacks vertically, ǫ = 0.1, ν = 0.001.

Figure 4 . 3 :

 43 Figure 4.3: Adversarial performance of multiple adversarial trainings on MNIST, trainings horizontally and attacks vertically, ǫ = 0.1, ν = 1.

Figure 4 . 4 :

 44 Figure 4.4: Adversarial performance of multiple adversarial trainings on MNIST, trainings horizontally and attacks vertically, ǫ = 0.1, ν = 100.

Figure 4 . 5 :

 45 Figure 4.5: Adversarial performance of multiple adversarial trainings on MNIST, trainings horizontally and attacks vertically, ǫ = 0.1, ν = 10000.

Algorithm 2 :

 2 Building a 1-Lipschitz network with d layers Input: Number of neurons per layer m Input: number of layers d O old = Orthonormal_Sampling(m);

Proposition 5 . 3 . 1 .

 531 3.1) can be solved only in an equivalence class. Let us fix a distance/divergence function d : R 2 + → R + such that d(a, b) = 0 ⇐⇒ a = b. One can then also formulate problem (5.3.1) as: min θ∈Θ d(L f,X (θ), L).(5.3.2)If θ * exists in the first problem then the minimum value in (5.3.2) is indeed 0. In addition to the above, assume that G φ (•) is continuous (hence φ is C 1 ), and that Θ is compact. Then the minimization problem (5.3.2) has a nonempty compact set of minimizers.

Figure 5 . 3 :

 53 Figure 5.3: Computation of the Lipschitz constant using the LipSDP algorithm for different depths (y axis) and different layer size (x axis).

Figure 5 . 4 :

 54 Figure 5.4: Computation of the Lipschitz constant using the Se-qLip algorithm for different depths (y axis) and different layer size (x axis) with numpy optimizer.

Figure 5 . 5 :

 55 Figure 5.5: Computation of the Lipschitz constant using the Se-qLip algorithm for different depths (y axis) and different layer size (x axis) with genetic optimizer.

Figure 5 . 6 :

 56 Figure 5.6: Computation of the Lipschitz constant using the random exploration for different depths (y axis) and different layer size (x axis).

Figure 5 .

 5 Figure5.3 and 5.5 provide the best landscape of estimation of the Lipschitz constant: according to the color scale, the methods appear to be finding accurately the value of the Lipschitz constant. One very interesting comparison to make is between Figures 5.4 and 5.5: they are both implementations of SeqLip however they are resorting to different solvers. The former solver is greedy -and therefore suboptimal for dealing with an NP-hard problem -and the latter is nondeterministic -and therefore finds the optimal solution provided it has iterated sufficiently. This shows that, although the theory ensures that SeqLip should ultimately provide an upper bound, it is not achieved if the problem is not solved suitably. On top of that, it showcases that the value given by this algorithm should be treated carefully and cannot be compared reliably to a lower bound. Figure5.6 presents a method for computing a certified lower bound for the Lipschitz constant: a random approach to seek the maximum of the differential quotient. The random search depends only on the dimension of the sampling space (that is taken equal to the layer size in our specific case).

Figure 5 . 7 :

 57 Figure 5.7: Computation of the Lipschitz constant using the LipSDP algorithm for larger depths (y axis) and larger layer size (x axis).

Figure 5 . 8 :

 58 Figure 5.8: Computation of the Lipschitz constant using the Se-qLip algorithm for larger depths (y axis) and larger layer size (x axis) with numpy optimizer.

Figure 5 . 9 :

 59 Figure 5.9: Computation of the Lipschitz constant using the Se-qLip algorithm for larger depths (y axis) and larger layer size (x axis) with genetic optimizer.

Figure 5 . 10 :

 510 Figure 5.10: Computation of the Lipschitz constant using random exploration for larger depths (y axis) and larger layer size (x axis).

2 .

 2 The bound(6.3.5) yields uniform convergence. The Γ-convergence claim in this case also follows from [128, Proposition 5.2 and Remark 5.3].

= M 1 ∇

 1 .3.11) (ii) Suppose in addition that (H.6) L(θ, .) is C 3 on an open set containing C ε z with Hölder continuous third-order derivative;(H.7) for r ≥ 3 (a) M is C r -stratifiable with closed strata; (b) for each i ∈ I, the Hessian ∇ 2 z ′ L(θ, z ′ ) is negative semidefinite for any z ′ ∈ M i with constant rank m -dim(M i ).Then for every θ ∈ Θ and any t > 0, with probability at least 1 -2(p + 1)N -t dist ∇g τ,N (θ), ∂ C g(θ) ≤ ∇g τ,N (θ) -η(θ) ≤ max(1, 2L Θ,Z √ p)e θ L(θ, z ′ )dµ(z ′ ) ⊂ ∂ C g(θ)and µ ∈ P(M 1 ). (iii) Under the assumptions of either statement (i) or (ii), if τ is a function of N , say τ N , with τ N → 0 and e L-L τ N log N N → 0 as N → +∞, then (a) for every θ ∈ Θ dist ∇g τ N ,N (θ), ∂ C g(θ) -→ N →+∞ 0 almost surely. (b) Let Ξ be any closed convex subset of Θ. If moreover Argmax L(θ, C z ε ) is a singleton for each θ ∈ Ξ, then almost surely,

( i )N

 i For any t > 0 ∇g τ (θ) -∇g τ,N (θ) ≤ max(1, 2L Θ,Z √ p)e with probability at least 1 -2(p + 1)N -t . (ii) Suppose that τ is a function of N , say τ N , with τ N e → 0 as N → +∞, then (a) for every θ ∈ Θ ∇g τ N (θ) -∇g τ N ,N (θ) -→ N →+∞ 0 almost surely. (b) Let Ξ be any closed convex subset of Θ. If moreover Argmax L(θ, C z ε ) is a singleton for each θ ∈ Ξ, then almost surely, ∇g τ N (θ) -∇g τ N ,N (θ) -→ N →+∞

Theorem 6 . 4 . 2 . 6 6. 4 .

 64264 Assume that (H.1) holds, that L(•, z i + u) is locally Lipschitz continuous for each (z i , u) ∈ Z ×C ε , and that L(•, z) is differentiable with ∇ θ L(θ, z) continuous in (θ, z). Suppose moreover that ϕ and L are definable, and that the step-sizes satisfy k∈N γ k = +∞ and γ k = o 1 log k . Consider the sequence (θ k ) k∈N generated by Algorithm 4 and suppose that there exists a constant C > 0 such that sup k∈N θ k ≤ C almost Chapter Robust optimization algorithm via SGD surely. Then, almost surely, the set of cluster points of (θ k ) k∈N belong to crit-G = 1 M M i=1 ∂ C g i -1

Algorithm 5 :

 5 SGD for PRO with smoothing. Input: Step-sizes (γ k ) k∈N ; number of integration points (N k ) k∈N ; smoothing parameters (τ k ) k∈N ; Input: Initialization θ 0 ; for k = 0, . . . do Draw independently uniformly at random a mini-batch B k ⊂ [M ] ; Draw N k samples (u j ) j∈[N k ] independently uniformly at random in C ε ;

Theorem 6 . 4 . 3 .→ 0 <

 6430 Assume that the assumptions of Theorem 6.3.9(ii)(b) hold. Suppose moreover that ϕ and L are definable, that the step-sizes satisfy k∈N γ k = +∞ and γ k = o 1 log k , and that (τ k , N k ) k∈N are such that τ k → 0 and e as k → +∞, and k∈N N -t k +∞ for some t > 0. Consider the sequence (θ k ) k∈N generated by Algorithm 5 and suppose that there exists a constant C > 0 such that sup k∈N θ k ≤ C almost surely. Then, almost surely, the set of cluster points of (θ k ) k∈N belong to crit-G =

Figure 6 . 1 :

 61 Figure 6.1: Influence of τ (x axis) and N (y axis) on the robust loss on test set (color scale). The darker the better.

Figure 6 . 2 :

 62 Figure 6.2: Test accuracy of the three trainings on Avila dataset: vanilla (blue), adversarial (green), robust (red) with median (plain line) and 10% and 90% quantiles for 50 trials.

Figure 6 . 3 :

 63 Figure 6.3: Adversarial accuracy of three trainings on Avila dataset: vanilla (blue), adversarial (green), robust (red) with median (plain line) and 10% and 90% quantiles for 50 trials.

Figure 6 . 4 :

 64 Figure 6.4: Worst-case robustness accuracy of three trainings on Avila dataset: vanilla (blue), adversarial (green), robust (red) with median (plain line) and 10% and 90% quantiles for 50 trials.

Figure 6 . 5 :

 65 Figure 6.5: Lipschitz constant upper bound of the learned network of the three training methods on Avila dataset computed using LipSDP: vanilla (blue), adversarial (green), robust (red) with median (plain line) and 10%, 25%, 75% and 90% quantiles for 50 trials.

Figure 6 . 6 :

 66 Figure 6.6: Lipschitz constant upper bound of the learned network of the three training methods on Avila dataset computed using SeqLip: vanilla (blue), adversarial (green), robust (red) with median (plain line) and 10%, 25%, 75% and 90% quantiles for 50 trials.

Figure 6 . 7 :

 67 Figure 6.7: Confusion matrix for the vanilla training (left), for the robust training (ε = 0.3) (middle) and for the adversarial training (ε = 0.3) (right). All matrices are normalized column-wise to display the percentage of predicted labels per each class in the test set.

  The function τ → ψ τ (θ) obviously increases as τ decreases and so is g τ . Continuity of L, compactness of C ε z and Proposition 6.3.1 entail that g τ is continuous and converges pointwise to g. The Γ-convergence claim in this case then follows from [128, Proposition 5.4 and Remark 5.5]. (ii) The upper bound in (6.3.5) is immediate by definition of g τ . Let us turn to the lower bound. Let us denote z

ǫ

  Pr S N -E[S N ] > e L/τ ǫ/τ 1(S N ≥ E[S N ]) + Pr S N -E[S N ] < -e L/τ ǫ/τ 1(S N ≤ E[S N ]) = Pr |S N -E[S N ]| > e L/τ ǫ/τ 1(S N ≥ E[S N ]) + Pr |S N -E[S N ]| > e L/τ ǫ/τ 1(S N ≤ E[S N ]) = Pr |S N -E[S N ]| > e L/τ ǫ/τ .Since the random variables e L(θ,z ′ i ) τ are independent and bounded (they live in the interval [e L/τ , e L/τ ]), we are in position to invoke Hoeffding's inequality to obtainPr (|g τ,N (θ) -g τ (θ)| ≥ ǫ) = τ e (L-L)/τ t log N 2N ,we getPr (|g τ,N (θ) -g τ (θ)| > ǫ) ≤ 2e -t log N = 2N -t (ii) Let ǫ N def = τ N e (L-L)/τ N log N N . (a)We have from the first claim above thatPr (|g τ N ,N (θ) -g τ N (θ)| > ǫ N ) ≤ 2N -2 .Since the right-hand side above is summable in N , we conclude by the (first) Borel-Cantelli lemma that with probability one lim sup N →+∞ |g τ N ,N (θ) -g τ N (θ)| = 0, whence almost sure convergence is immediate.

  |g τ N ,N (θ, ω) -g τ N (θ)| ≤ |g τ N ,N (θ k , ω) -g τ N ,N (θ, ω)| + |g τ N ,N (θ k , ω) -g τ N (θ k )| + |g τ N (θ k ) -g τ N (θ)|.Since θ k ∈ T, Ω ⊂ Ω θ k , and as just seen hereabove, the second term in the last inequality vanishes as N → +∞. Let us turn to the first term. LetI θ max (ω) = i ∈ [N ] : L(θ, z i (ω)) = max j∈[N ]

7 .≤

 7 i∈[N ] L(θ, z i (ω))+τ N log   |I θ max (ω)| N + 1 N i ∈I θ max (ω) e L(θ,z i (ω))-max i∈[N ] L(θ,z i (ω)) Appendix: ProofsLipschitz continuity of a family of functions implies that of their maximum. It then follows that|g τ N ,N (θ k , ω) -g τ N ,N (θ, ω)| ≤ | max i∈[N ] L(θ k , z i (ω)) -max i∈[N ] L(θ, z i (ω))| + τ N log   |I θ max (ω)| + i ∈I θ max (ω) e L(θ,z i (ω))-max i∈[N ] L(θ,z i (ω)) k ,z i (ω))-max i∈[N ] L(θ k ,z i (ω)) L Θ θ k -θ + 2τ N log N.Passing to the limit as N → +∞ we get lim supN →+∞ |g τ N ,N (θ k , ω) -g τ N ,N (θ, ω)| ≤ L Θ θ k -θ .

6. 7 . 6 9 6. 7 . 6 . 1 6 6. 7 .L

 76976167 Proof of Theorem 6.3.Proof of Lemma 6.3.10 To lighten notation in the proof, we drop the super-and subscript in C ε z . Let the (Gibbs) probability measure 4 dµ τ (z ′ ) Compactness of C and continuity of L(θ, •) imply that M is a non-empty compact set. Without loss of generality, we assume that max L(θ, C) = L(θ, M) = 0 (otherwise, one can use a simple translation argument). (i) The proof of this claim is inspired by standard arguments in the literature of simulated annealing and Markov chains (see e.g. [34, Proposition 1.2] or [100, Corollary 2.1 and Proposition 2.3])5 . We provide a self-contained proof adapted to our setting. Given ǫ > 0, we defineU ǫ = {u ∈ R m : L(θ, u) ≥ -ǫ} .By assumption (H.3), L(θ, •) is L Z -Lipschitz continuous, and thus U ǫ is contained in the open tubular Chapter Appendix: Proofs neighborhood of radius ǫ/L Z around Argmax L(θ, C). This implies that µ L (U ǫ ) > 0. We then haveµ τ (C \ U ǫ ) = C\U ǫ e

(L

  ii) For any Borel set C ⊂ R m and k ∈ N, H k (C) is the k-dimensional Hausdorff measure. It is normalized to coincide with the Lebesgue measure on R k . For a k-dimensional smooth submanifold of R m , its kdimensional Hausdorff measure coincides with the Riemannian volume measure. By (H.7)(a), for any r ≥ 3, M is C r -stratifiable and thus the strata (M i ) i∈I are C r -smooth compact submanifolds.Given ǫ > 0, for each M i , we define its open neighborhoodU i = {u ∈ R m : dist(u, M i ) < ǫ} . Let U def = i∈I U i . We then have for f ∈ C C f (z ′ )e L(θ,z ′ ) τ dz ′ = C∩U f (z ′ )e L(θ,z ′ ) τ dz ′ + C\(C∩U ) f (z)e L(θ,z ′ ) τ dz ′ . (6.7.3)Since f (C) is compact by compactness of C and continuity of f , and ∃κ > 0 such that ∀z ′ ∈ C \ (C ∩ U), L(θ, z ′ ) ≤ -κ < max L(θ, C) = 0, the second integral in (6.7.3) verifies, for any s ≥ 0,τ -s C\(C∩U ) f (z)e L(θ,z ′ ) τ dz ′ ≤ (µ L (C) sup |f (C)|) τ -s e -κ/τ → 0 uniformly as τ → 0 + . (6.7.4)Let us now turn to the first integral. We have, for ǫ sufficiently small C∩U f (z ′ )e

6 6. 7 . 2 m-m i 2 ( 2 

 67222 C∩U i f (z ′ )e L(θ,z ′ ) τ dz ′ = M i P -1 M i (v) f (u)e L(θ,u) τ (J m i (P M i )(u)) -1 dH m-m i (u) dH m i (v),Chapter Appendix: Proofswhere m i = dim(M i ), J m i (P M i ) is the m i -dimensional Jacobian of P M i , i.e., J m i (P M i )(u) = det (D(P M i )(u) D(P M i )(u) ⊤ )and D is the derivative operator. In addition, since M i is C r -smooth, we have from [161, Proposition 5.1] that P M i is C r-1 -smooth with Lipschitz derivative on U i (taking ǫ smaller if necessary). This entails that the key estimates of [50, Lemma 6.1] hold in our case. The rest of our argument follows then similar lines to those of [50, Theorem 3.1, starting from(9.3)]. This allows us to show that lim m -m i )α (m-m i ) β (m-m i ) dH m i (v), (6.7.6)

2 m-m 1 2 (m -m 1 1 j=1λ 1 (v) -1 2 

 221112 )α (m-m 1 ) β (m-m 1 ) dH m 1 (v).

6. 7 . 6 . 2 1 µ

 7621 Proof of Lemma 6.3.11To lighten notation in the proof, we drop the super-and subscript in C ε z . Denote the probability measuresdµ θ τ (z ′ ) def = 1 µ L (C) e L(θ,z ′ ) τ S θ τ dz ′ and dµ θ τ,N (z ′ ) L (C) C e L(θ,z ′ ) τdz ′ and S θ

  3.15) that∇g τ (θ) -∇g τ,N (θ) = C ∇ θ L(θ, z ′ )dµ θ τ (z ′ ) -C ∇ θ L(θ, z ′ )dµ θ τ,N (z ′ )and thus, by assumption (H.5), we get ∇g τ (θ) -∇g τ,N (θ) ≤ L Θ,Z 1 -

( 6 . 7 . 8 )∇ 6 6. 7 .

 67867 For the first term, since S θ τ = E[S θ τ,N ], we get from the proof of Lemma 6.7.1 that for any t > 0with probability at least 1 -2N -t .Let us now turn to the second term in (6.7.8). DenoteG θ τ def = 1 µ L (C) C ∇ θ L(θ, z ′ )e L(θ,z ′ ) τ dz ′ and G θ θ L(θ, z ′ k )e L(θ,z ′ k ) τ . We then have C ∇ θ L(θ, z ′ ) dµ θ τ (z ′ ) ] = G θ τ and the random vectors ∇L(θ, z ′ k )e L(θ,z ′ k ) τare independent and bounded, we apply Hoeffding's inequality and the union bound to obtainPr G θ τ,N -G θ τ > ǫ ≤ Pr max j |(G θ τ,N ) j -(G θ τ ) j | > ǫ/ √ p ≤ p max j Pr |(G θ τ,N ) j -(G θ τ ) j | > ǫ/ √ p . Taking ǫ = L Θ,Z e L/τ 2tp log N N , we infer that C ∇ θ L(θ, z ′ ) dµ θ τ (z ′ ) (z ′ ) ≤ L Θ,Z e L-L τ 2tp log N Nwith probability larger than 1 -2pN -t . Combining the above bounds with the union bound, we get the claim. We argue as in the proof of Lemma 6.7.1(ii)(a). We have from claim (i) thatPr ( ∇g τ N (θ) -∇g τ N ,N (θ) > ǫ N ) ≤ 2(p + 1)N -2 .Since the right-hand side above is summable in N , we conclude by the (first) Borel-Cantelli lemma that with probability one lim supN →+∞ ∇g τ N (θ) -∇g τ,N (θ) = 0.(b) We will follow a reasoning similar to the proof of Lemma 6.7.1(ii)(b) using separability of R p and a density argument. There exists a countable set T whose closure is Ξ. According to claim (a), for every θ ∈ Ξ ⊂ Θ, there exists a set of events Ω θ of probability one and, for every ω ∈ Ω θ , ∇g τ N ,N (θ, ω) -∇g τ N (θ, ω) → 0 as N → +∞. Set Ω = θ∈T Ω θ . Countability of T and a union Chapter Appendix: Proofs bound show that Ω is also of probability one. Moreover, for fixed θ ∈ Ξ, there exists a sequence (θ k ) k∈N in T such that θ k → θ. Let ω ∈ Ω. We have ∇g τ N ,N (θ, ω) -∇g τ N (θ) ≤ ∇g τ N (θ k ) -∇g τ N (θ) + ∇g τ N ,N (θ k , ω) -∇g τ N (θ k )

  (6.7.10) Now, observe that by (H.5) and convexity of Ξ, the mean value theorem yieldssup z ′ ∈C |L(θ k , z ′ ) -L(θ, z ′ )| ≤ sup z ′ ∈C,ξ∈Ξ ∇ θ L(ξ, z ′ ) θ k -θ ≤ L Θ,Z θ k -θ ,and taking the limit as k → +∞, we see that L(θ k , •) converges uniformly to L(θ, •), and thus by [128, Proposition 5.2 and Remark 5.3] L(θ k , •) Γ-converges to L(θ, •). Compactness of C also entails equi-coercivity of -L(θ k , •) on C. This together with Γ-convergence of L(θ k , •) seen just above allows to apply[START_REF] Maso | An Introduction to Γ-Convergence[END_REF] Corollary 7.20] to infer that z θ k → z θ as k → +∞. In view of this, taking the limit as k → +∞ in (6.7.10), using continuity of ∇ θ L in both arguments (see (H.5)), we get that lim k→+∞ lim N →+∞ ∇g τ N (θ k ) -∇g τ N (θ) = 0.

  Consider an absolutely continuous curve θ : R + → R p . The function G being locally Lipschitz continuous, t → G(θ(t)) is also absolutely continuous and thusd dt G(θ(t)) = 1 M M i=1 d dt g i (θ(t)) = 1 M M i=1 v i , θ(t) , for all v i ∈ ∂ C g i (θ(t)) and for a.e. t ≥ 0, where we used that the functions g i are path differentiable for the Clarke subdifferential by[START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF] Theorem 5.8]. Therefore, G is a Lyapunov function for the set crit-G. Moreover, by[START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF] Theorem 6], G(crit-G) has empty interior.

Table 4 .

 4 1: Accuracy of a vanilla trained ResNet model on MNIST, FashionMNIST, CIFAR10 and SVHN dataset against different attacks for different perturbation radius ε, from an attacker perspective the lower is the better.

Table 4 .

 4 2: Test accuracy and adversarial accuracy of coverage trained (ν = 100) and non coverage trained (ν = 0) networks on MNIST, FMNIST, CIFAR10 and SVHN, ǫ is the perturbation amplitude used for computing the PGD adversarial accuracy.

	Metric	Test Accuracy PGD adversarial accuracy
	MNIST, ν = 0, ǫ = 0.1	99.8%	57.5%
	MNIST, ν = 100, ǫ = 0.1	99.5%	73.7%
	FMNIST, ν = 0, ǫ = 0.1	92.6%	6%
	FMNIST, ν = 100, ǫ = 0.1	91.5%	16%
	CIFAR10, ν = 0, ǫ = 0.03	82%	11%
	CIFAR10, ν = 100, ǫ = 0.03	74%	14%
	SVHN, ν = 0, ǫ = 0.03	93%	22%
	SVHN, ν = 100, ǫ = 0.03	91%	34%

  Lemma 6.3.11. Suppose that the assumptions of Proposition 6.3.1 hold, and that L(•, z ′ ) is differentiable with ∇ θ L(θ, z ′ ) uniformly bounded by L Θ,Z on Θ × Z.

  Theorem 7.8]. The second claim is a consequence of Γ-convergence of g τ (Theorem 6.3.4), compactness of Θ and[START_REF] Maso | An Introduction to Γ-Convergence[END_REF] Corollary 7.20]. The last claim is immediate from the second as the cluster point is unique.

	.7.1)
	Inserting this into the expression of g τ (see (6.3.4)), we get the upper-bound.

6.7.4 Proof of Theorem 6.3.6

Compactness of Θ entails that g τ and g are equi-coercive (see

[START_REF] Maso | An Introduction to Γ-Convergence[END_REF] Definition 7.6 and Proposition 7.7

]. The first claim on convergence of the minimal values follows by combining the first claim in Theorem 6.

3.4 and [128,

Functions f such that these assumptions are verified are known as lower-C 1 functions; see[START_REF] Rockafellar | Variational analysis[END_REF].

g depends on z but we drop this in the notation to lighten the latter.

In the norm • of course.

This is reminiscent of works on simulated annealing where τ is the temperature parameter; see e.g.[START_REF] Hwang | Laplace's method revisited: Weak convergence of probability measures[END_REF][START_REF] Cox | Convergence of Gibbs Measures Associated with Simulated Annealing[END_REF]. Our context is however different and in particular, C ε z is not the whole space nor it is a finite set nor a compact submanifold.

Strictly speaking, we should also index it with θ. In this proof, we will drop this to lighten notation.

We thank the reviewer for raising similar arguments.

Acknowledgments

First and foremost I would like to thank my academic supervisors Frédéric Jurie and Jalal Fadili that truly had a broad vision on their academic fields and a rigor that I terribly lacked when I started off this journey. You lent me your vision that guided me through these years.

I would like to thank as well the members of my jury Elisa Fromont, Laurent Heutte and especially Béatrice Pesquet-Popescu and Franck Iutzeler that reviewed the manuscript and suggested improvements.

I am indebted to my (now former) industrial supervisor Sébastien Da Veiga that took on the challenge of putting me back on track after a rather peculiar year of remote working. Your honesty and plain speaking on top of your academic skills were always uplifting and motivating. Where others brought vision, you brought means.

Chapter 4

An experimental approach on robustness following coverage Main contributions of this chapter ◮ Provide a (sub)differentiable coverage metric that can be optimized efficiently and concurrently with the training loss.

◮ Provide empirical assessment of the effect of increasing coverage in conjunction with adversarial training.

◮ Disentangle the notion of neuron coverage and robustness.

Introduction

In the field of deep learning the ReLU activation function [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF] triggered a small revolution. It provided significant advantages compared to traditional smooth activation functions (for instance: sigmoid, tanh, softmax): there are no exponentials to compute thus reducing the computation load both of the forward pass (i.e. performing the prediction) and the backward pass (i.e. computation of the gradients for the update of the model). On top of this, the ReLU function is an elegant solution to the vanishing gradient problem: deep neural nets with sigmoid or tanh activation function are shrinking the value of the gradient exponentially in the depth of the network

Chapter 5

An explicit model of robustness via Lipschitz controlled networks

Main contributions of this chapter ◮ Providing a new general approach for designing neural networks with prescribed Lipschitz constant.

◮ Testing the performance and convergence of Lipschitz assessing algorithms on prescribed networks.

◮ Testing the validity domains of Lipschitz assessing algorithms.

The content of this chapter was presented in a workshop of ECML PKDD 2022.

throughout all the configurations but in order to converge properly for large Lipschitz constants the number of epochs had to be adapted accordingly. and8) since values lie under the target black curve, but for values 1, 5, 7 and 9 the lower bound is higher than the Lipschitz constant computed in Figure 5.1. This attests for an error in the convergence towards the target Lipschitz constant in Algorithm 3 despite the initial remarkable results in Figure 5.2. There are exactly two error-prone steps in our design process: the error coming from the PGD maximization step that approximate the argument of equation (2.5.3) and the error coming from our minimization of problem (5.3.2). The exact cause of an error on the prescription can not be traced back to either of the two sources of error and it may also be a combined effect of the two. We hypothesize that the inner maximization is to be blamed for the errors observed in Figure 5.2 since it combines a PGD-like algorithm and power iteration for the computation of the spectral norm. Similar results were obtained when using the dual form of the inner maximization of equation (2.5.4): this form allows to cast the spectral norm maximization into a single maximization problem instead of power iteration and maximization. This advocates for lingering error in the estimation of the Lipschitz constant caused by the PGD like algorithm. In order to solve exactly the inner maximization problem different approaches could have been undertaken, a first idea could have been to change the optimization algorithm for a non-deterministic one provided we have enough computational budget. This would have allowed to find a better maximizer in an unspecified execution time. Secondly we could have used entropic smoothing (this will be the subject of Chapter 6) in order to approximate and asymptotically lean towards the real maximizer, this approach is computationally demanding as well.

Comparing Lipschitz assessing algorithms

In this section we will use networks generated using algorithm 2 in order to compare Lipschitz assessing algorithms. This is motivated by two main reasons: on the one hand it is computationally cheap and allows us to run a greater variety of algorithms with an extended number of trials. On the other hand, it allows to split the sources of error as the approximation errors from the Lipschitz algorithms won't be spoiled by errors in the designing process: it ensures consistency of the result at the cost of generality. All the networks used in these experiments Chapter 6

Regularized Robust Optimization with Application to Robust Learning Main contributions of this chapter

◮ Bounding the distributionally robust objective with the pointwise robustness objective, this shows that provided some hypothesis on the class of function, one can approximate the former by the latter with arbitrary small error.

◮ Approximating the pointwise robust problem with a smoothed objective that trades complexity for computational cost. This smoothed objective is shown to have asymptotically the same optimal point than the non smooth problem.

◮ Presenting an algorithm for solving the smoothed approach with arbitrary small error, almost surely.

◮ Showing in a use case the benefits of using smoothing in terms of performance compared to other robust training methods that do not enjoy the same guarantees.

The content of this chapter is under review in the Journal of Optimization Theory and Applications.

Chapter 6 6.7. Appendix: Proofs By the almost sure boundedness assumption, max i ∂ C g i (θ k ) is also uniformly bounded almost surely. Moreover, the direction d k is such that

) and the random process ζ k is a zero-mean uniformly bounded martingale difference noise. These uniform boundedness properties and the choice of the sequence γ k allows to apply [14, Remark 1.5(ii) and Proposition 1.4] to get by [START_REF] Benaïm | Stochastic Approximations and Differential Inclusions[END_REF]Proposition 1.3] that the continuous-time affine interpolant of (θ k ) k∈N is almost surely an asymptotic pseudotrajectory of the flow (6.4.5). Combining this with [14, Theorem 3.6 and Proposition 3.27] gives the claimed results.

Proof of Theorem 6.4.3

We obviously have

In view of Theorem 6.3.9(ii)(b), if the sequence (τ k , N k ) k∈N is as devised, then almost surely, lim k→+∞ e k = 0 for all (θ k ) k∈N ⊂ B C (0). By independent and uniform sampling of the mini-batches, ζ k is a zero-mean martingale difference noise. We are then in position to invoke [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF]Remark 4.5] to get that the conclusions of [14, Remark 1.5(ii) and Proposition 1.4] still hold provided that γ k decays as devised. The rest of the proof is then same as that of Theorem 6.4.2.

Appendix: Additional information on the experiments

Following the recommendations of the paper that introduced the dataset [START_REF] Stefano | Reliable writer identification in medieval manuscripts through page layout features: The "Avila" Bible case[END_REF] we removed the columns with the modular ratios and the data was centered and normalized.