Jordan Frecon

Paul Viallard

Emilie Morvant

Gilles Gasso

Amaury Habrard

Stéphane Canu

Semi-Universal Adversarial Perturbations

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Embedded technologies using artificial Neural Networks (NN) are increasingly present in our daily lives. Their high expressive power has shown a great success in various complex tasks [START_REF] Miotto | Deep learning for healthcare: review, opportunities and challenges[END_REF][START_REF] Grigorescu | A survey of deep learning techniques for autonomous driving[END_REF]. However, some concerns have been raised about their safety and more particularly for the safety of the user [START_REF] Huang | A survey of safety and trustworthiness of deep neural networks: Verification, testing, adversarial attack and defence, and interpretability[END_REF] since the pioneer work of Szegedy et al. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] which has shown the existence of adversarial attacks. The most striking example is that of automated vehicles, where malicious attacks could lead the car to take unwanted action with dramatic consequences [START_REF] Qayyum | Securing connected amp; autonomous vehicles: Challenges posed by adversarial machine learning and the way forward[END_REF][START_REF] Nassi | Phantom of the adas: Securing advanced driver-assistance systems from split-second phantom attacks[END_REF].

Most of the adversarial attacks are quasi-negligible perturbations that fool the NN prediction. From a fast one-shot method [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] to the first iterative procedures [START_REF] Papernot | The limitations of deep learning in adversarial settings[END_REF][START_REF] Moosavi-Dezfooli | Deepfool: A simple and accurate method to fool deep neural networks[END_REF][START_REF] Bengio | Adversarial examples in the physical world[END_REF][START_REF] Wagner | Towards of neural networks[END_REF][START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF], the crafting of adversarial perturbations has lately received a lot of attention from the machine learning community. To this regard, momentum-based methods [START_REF] Dong | Boosting adversarial attacks with momentum[END_REF][START_REF] Wang | Boosting adversarial transferability through enhanced momentum[END_REF] have shown a promising boost in the transferability of the attacks learned on one NN to other NNs. In addition, various contributions have investigated algorithmic concerns leading to accelerated and scale-invariant attacks [START_REF] Lin | Nesterov accelerated gradient and scale invariance for adversarial attacks[END_REF] as well as parameter-free attacks [START_REF] Croce | Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks[END_REF]. In another line of research, Finlay et al. [START_REF] Finlay | The logbarrier adversarial attack: making effective use of decision boundary information[END_REF] designed attacks exploiting the decision boundary of NNs, while Zhang et al. [START_REF] Zhang | Principal component adversarial example[END_REF] proposed to take into account the structure of images through a principal component analysis. A key particularity of all the above attacks is that they are specific (or example-based), meaning that they are crafted to attack a single example. Henceforth, to attack a new example, one needs to learn the associated perturbation once again. Although they are very effective, they have the major drawback of being time consuming.

On the other end of the spectrum, universal (or example-agnostic) attacks [START_REF] Zhang | A survey on universal adversarial attack[END_REF] aim to find an attack which, once learned, can be applied to every new example. Moosavi-Dezfooli et al. [START_REF] Moosavi-Dezfooli | Universal adversarial perturbations[END_REF] first demonstrated that there exists a single perturbation, coined universal adversarial perturbation (UAP), which, when added to any new example, is very likely to fool the classifier; a variant exploiting the orientations of the perturbation vectors was proposed by Dai and Shu [START_REF] Dai | Fast-UAP: An algorithm for expediting universal adversarial perturbation generation using the orientations of perturbation vectors[END_REF]. Later, Shafahi et al. [START_REF] Shafahi | Universal adversarial training[END_REF] devised a more efficient method by hinging on a projected gradient descent algorithm. In addition, inspired by the observation that UAP does not attack all classes equally, Benz et al. [START_REF] Benz | Universal adversarial training with class-wise perturbations[END_REF] proposed a class-based universal perturbation. Although these perturbations are universal, it is hard to interpret why they work on a case-to-case basis. In general, current state-of-the-art universal attacks remain hardly interpretable out-of-the-box and require a posteriori tailored studies [START_REF] Zhang | Understanding adversarial examples from the mutual influence of images and perturbations[END_REF]. These works have suggested that a reasonable assumption is that the perturbations should live in a low-dimensional manifold. This assumption has been justified by Gu and Rigazio [START_REF] Gu | Towards deep neural network architectures robust to adversarial examples[END_REF], and later by Tabacof and Valle [START_REF] Tabacof | Exploring the space of adversarial images[END_REF]. Some works proposed solutions to learn such a manifold [START_REF] Khrulkov | Art of singular vectors and universal adversarial perturbations[END_REF][START_REF] Zhang | Principal component adversarial example[END_REF][START_REF] Baluja | Learning to attack: Adversarial transformation networks[END_REF][START_REF] Hayes | Learning universal adversarial perturbations with generative models[END_REF][START_REF] Xiao | Generating adversarial examples with adversarial networks[END_REF]. Finally, Zhang et al. [START_REF] Zhang | A survey on universal adversarial attack[END_REF] suggest that simple gradient-based UAP methods may lead to better fooling performance.

Contributions. We propose a new kind of perturbations, that we call semi-universal perturbations and intend to bridge the gap between specific and universal perturbations. The original idea is to specifically craft an attack for each example by choosing, in an unsupervised manner, a perturbation among a set of L different universal perturbations. To do so, we define an optimization problem to jointly learn the L perturbations allowing each example to choose its own perturbation (L can be seen as a tuning parameter controlling the amount of diversity between the perturbations). To solve it, we derive a gradient-based solution with convergence guarantees. Additionally, to justify that the L semi-universal perturbations learned can be used to attack a model on unseen examples, we derive a generalization bound on the deviation between the true and the empirical fooling risks. Put into words, we get a bound on how much the learned perturbations are able to fool new examples, confirming that we can use the learned perturbations to attack a model on data coming from the same task. We then propose a simple attack procedure. Lastly, our experiments confirm the effectiveness of the semi-universal perturbations over previous gradient-based UAP, in line with the conclusion of [START_REF] Zhang | A survey on universal adversarial attack[END_REF]. Our results additionally show that they lead to more interpretable and transferable attacks. Outline. We recall the general framework of adversarial perturbations in Section 2. We introduce in Section 3 our semi-universal perturbations as well as an algorithmic solution to learn them. Then Section 4 is devoted to attacking with these perturbations: we derive a generalization bound on the quality of the perturbations to attack unseen examples in order to justify our attack procedure. Before concluding, numerical experiments are conducted in Section 5 on multiple benchmark datasets.

Preliminaries and related works 2.1 Adversarial perturbations

We stand in a multiclass setting where X ⊆ R P is a P -dimensional input space and Y = {1, . . . , c} is the set of c ∈ N + classes. We consider an unknown data distribution D on X ×Y that models the task; the associated marginal distribution on X is D X . We use the notation D n , resp. D n X , for the distribution of a sample constituted of n data points i.i.d. sampled from D, resp. D X .

We consider a trained model f : R P →R c which associates each example 4 x ∈ X to its probabilities f (x) ∈ R c to belong to any of the c classes from Y. The predicted class of x by f is then defined as C f (x) = argmax y∈Y f (x) y . Adversarial learning aims to find for each original example x ∼ D X a point a ∈ X close to x such that C f (a) ̸ = C f (x). Since a is close to x, one can expect f to predict the same class for both examples. Thus, a is called adversarial example and said to fool the classifier C f .

There exists a vast literature on the ways to build adversarial examples, measure their closeness to original examples, and quantify how much they affect the decision process of f . Here, we embrace the common setting of adversarial example a = x+ε built by adding an adversarial perturbation ε to an original example x. We consider that the two are close if the ℓ p -norm of the added perturbation is small enough [START_REF] Laidlaw | Perceptual adversarial robustness: Defense against unseen threat models[END_REF], i.e., ∥ε∥ p ≤ δ, for some small budget δ > 0. In addition, since asking C f (a) ̸ = C f (x) can lead to numerical instabilities [START_REF] Moosavi-Dezfooli | Deepfool: A simple and accurate method to fool deep neural networks[END_REF] during the learning of ε, we consider a loss function H : R c ×Y→R taking as inputs f (a) and a class k from Y that is either C f (x) or the original class y of x. In this paper, we use the cross-entropy loss (or its [0, 1]-bounded counterpart [START_REF] Gintare | Data-dependent pac-bayes priors via differential privacy[END_REF]).

Given the model f , and an unlabeled data set S X = {x i } n i=1 ∼ D n X , there exist two current paradigms for crafting adversarial perturbations: (i) specific attacks, where for each x ∈ S X we look for a perturbation ε(x) ∈ B p (δ) = {e ∈ R P | ∥e∥ p ≤ δ}, specifically tailored to attack the example x (hereafter, we drop the dependency on x and simply denote ε); (ii) universal attacks, where we look for a perturbation ε such that a = x+ε is an adversarial example for all x from S X . To learn such adversarial perturbations, we assume that we have a labeled sample S = {(x i , y i )} n i=1 ∈ (X ×Y) n consisting of n data points. We recall in the next subsections the most popular specific and universal attacks [START_REF] Zhang | A survey on universal adversarial attack[END_REF]. Note that, given some convex set C, we denote by Proj C the projection onto C.

Most popular specific attacks

DeepFool [START_REF] Moosavi-Dezfooli | Deepfool: A simple and accurate method to fool deep neural networks[END_REF]. For a given x ∈ S X , the DeepFool attack is the smallest ℓ p perturbation managing to fool the classifier C f . More formally, it solves minimize ε∈R P ∥ε∥ p s.t. C f (x+ε) ̸ = C f (x). PGD [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF]. Given S, and a loss function H, the adversarial perturbation for a given (x, y) ∈ S is defined as the one inside the ℓ p -ball which maximizes the loss between x+ε and y, i.e., maximize

ε∈R P H(f (x + ε), y) s.t. ∥ε∥ p ≤ δ. (1)
In practice, the opposite of the objective in Equation ( 1) is minimized by resorting to a projected gradient method, hence the name of the attack.

Most popular universal attacks

UAP [START_REF] Moosavi-Dezfooli | Universal adversarial perturbations[END_REF]. The first universal perturbation ε was crafted by aggregating the DeepFool perturbations ∆ε i associated to all samples

x i ∈ {x ∈ S X | C f (x+ε) = C f (x)}.
The aggregation step is defined as ε ← Proj Bp(δ) (ε+∆ε i ) and is repeated until some fooling rate is reached. Fast-UAP [START_REF] Dai | Fast-UAP: An algorithm for expediting universal adversarial perturbation generation using the orientations of perturbation vectors[END_REF]. This attack follows the UAP procedure but, instead of aggregating all the perturbations ∆ε i , it only adds the perturbation with the closest orientation to the current iterate ε. UAP-PGD [START_REF] Shafahi | Universal adversarial training[END_REF]. Given S, the UAP-PGD attack elaborates upon PGD by framing the universal perturbation as the solution of the following optimization problem

maximize ε∈R P 1 n (xi,yi)∈S H(f (x i + ε), y i ) s.t. ∥ε∥ p ≤ δ. (2)
CW-UAP [START_REF] Benz | Universal adversarial training with class-wise perturbations[END_REF].

1 n k xi∈S k H(f (x i + ε k ), k) s.t. ∀k ∈ Y, ∥ε k ∥ p ≤ δ. (3)
The solution amounts in learning multiple independent UAP-PGD perturbations, one for each class.

Our contribution starts from this principle of learning one perturbation per class, or at least learning a set of perturbations. Our original idea is to craft a specific perturbation by choosing it among a set of universal perturbations, that we call semi-universal perturbations. To do so, instead of learning the perturbations independently, we propose in Section 3 an approach that consists of learning L ∈ N + perturbations jointly. We believe that this increases the chances of attacking each example by providing a better expressiveness implied by the facts (i) that the perturbations are learned jointly and (ii) that for each example we choose the perturbation maximizing H the most. This is confirmed by our experiments in Section 5 which supports the ability to efficiently attack with L < c perturbations.

3 Crafting semi-universal perturbations

Learning the set of semi-universal perturbations

The originality of our work is to jointly learn L ∈ N + universal adversarial perturbations {ε 1 , . . . , ε L } where each ε l ∈ B p (δ). To do so, we propose to frame the learning procedure as follows.

Problem 1 (Learning semi-universal ℓ p -perturbations). Let L be the number of semi-universal perturbations to learn. Given S = {(x i , y i )} n i=1 , and the model f

, find ε = [ε 1 , . . . , ε L ] solving maximize ε∈Bp(δ) L L(ε) : = 1 n n i=1 max ε l ∈ε H(f (x i + ε l ), y i ) , (4)
For each pair (x i , y i ) ∈ S, the objective in Equation ( 4) only picks one of the L perturbations in ε which maximizes the loss between f (x i +ε l ) and y i the most. In other words, learning aims at being specific enough for each example while being sufficiently universal to cover all the pairs in S. As later shown in Section 5, it results that ε shows a great diversity. Note that when L = 1 (i.e., for a single perturbation) Equation ( 4) boils down to Equation (2). In addition, it bears similarities with Equation (3) when L equals the number of classes and each ε l is independently learned on S l .

Due to the model f , it is worth stressing that Problem 1 is a difficult non-concave maximization problem. Finding its global solution is thus out of reach. To tackle this challenge, we detail below an algorithmic solution to efficiently find an approximate solution. Note that we defer in Appendix A an alternative solution based on a stochastic solver fully exploiting the finite-sum nature of Problem 1.

Gradient-based numerical solution

To maximize L in Problem 1, we embrace a projected gradient ascent algorithm augmented with an Armijo-like line-search strategy (for ensuring some sufficient increase at each iteration). Its principle is inspired from the minorizemaximization algorithm where, at each step, a lower bound of the objective function

L is maximized. Let ε = Algorithm 1 L-SUAP Require: Parameter ρ ∈]0, 1[ Initialize ε (0) = [ε (0) l ] L l=1 for k = 0 to K -1 do Provide a rough estimate of γ k > 0 Projected gradient step: ε (k+1/2) = Proj Bp(δ) L (ε (k) + γ k ∇L(ε (k) )) Choice of relaxation parameter i k = 0 repeat ε (k+1) = (1 -ρ i k )ε (k) + ρ i k ε (k+1/2) i k = i k + 1 until L(ε (k+1) ) ≥ L(ε (k) ) + ρ i k -1 h (k) (ε (k+1/2) ) end for return ε (K)
[ε 1 , . . . , ε L ] and some sequence of step-sizes {γ k } k∈N+ . Then, at each iteration k ∈ N + the algorithm looks for

ε (k+1/2) ∈ B p (δ) L which maximizes the linearized surrogate h (k) (ε) = L(ε (k) )+ ∇L(ε (k) ), ε-ε (k) -(1/2γ k )∥ε- ε (k) ∥ 2 with ⟨•,
•⟩ the Frobenius inner product and ∥•∥ the induced norm. Such choice is motivated by the fact that, for concave and µ-smooth functions L, and for all γ k ≤ 1 µ , we have L(ε) ≥ h (k) (ε). Henceforth, we have

ε (k+1/2) = argmax ε∈Bp(δ) L h (k) (ε) = Proj Bp(δ) L ε (k) + γ k ∇L(ε (k) ) , (5)
which recasts into one projected gradient ascent step. Note that the differentiability of L depends on the choice H and on the NN f to attack. For instance, for ReLu-based NN, it is likely that ∇L(ε (k) ) is not well-defined 5 . In that case and whenever L is not differentiable, we resort to a sub-gradient instead. We additionally consider a relaxation step of the form

ε (k+1) = (1 -α k )ε (k) + α k ε (k+1/2)
, where the relaxation parameter α k ∈ (0, 1] is appropriately chosen by an Armijo-like line-search strategy to ensure [START_REF] Bonettini | On the convergence of a linesearch based proximal-gradient method for nonconvex optimization[END_REF] some sufficient increase in L. This algorithmic procedure is sketched in Algorithm 1 and referred as L-SUAP. In practice, we suggest initializing the L universal perturbations in a non-informative manner by randomly sampling each ε (0)

l ∼ [-δ, δ] P and additionally projecting onto the ball B p (δ). This procedure comes with convergence guarantees stated below.

Theorem 1 (Convergence [START_REF] Bonettini | On the convergence of a linesearch based proximal-gradient method for nonconvex optimization[END_REF]). Let {ε (k) } k∈N be the sequence of Algorithm 1. Suppose that ∇L is Lipschitz continuous. Then each limit point of {ε (k) } k∈N is a stationary point of Problem 1 and {L(ε (k) )} k∈N converges towards the objective value at the limit point. If L satisfies the Kurdyka-Łojasiewicz (KŁ) property at any point, then the sequence converges to a stationary point of Problem 1.

The existence of the Lipschitz constant is central to ensure convergence guarantees. Note that studying the Lipschitz continuity of NN and obtaining sharp Lipschitz constant is difficult (e.g., [START_REF] Patrick | Lipschitz certificates for layered network structures driven by averaged activation operators[END_REF][START_REF] Gouk | Regularisation of neural networks by enforcing lipschitz continuity[END_REF]).

Remark 1. Many functions met in NNs (e.g., activation functions, loss) are semi-algebraic or tame, and thus, satisfy the KŁ property [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF][START_REF] Zeng | Global convergence of block coordinate descent in deep learning[END_REF]. Since these concepts are stable under many operations, it is reasonable to assume that many deep NNs f are likely to satisfy the KŁ property and so does L.

While little attention is usually devoted to these concerns for crafting adversarial attacks, we empirically show in Section 5 the superiority of the corresponding principled algorithmic solution even though these assumptions do not always hold. Now we detail a solution to attack unseen examples with semi-universal perturbations. To justify our procedure presented in Section 4.2, we first provide in Section 4.1 a bound on the generalization capacities of the learned perturbations on unseen examples.

Attacking unseen examples 4.1 Generalization guarantees: we can attack on unseen examples

The performance of the learned semi-universal perturbations on unseen examples can be approximated through generalization bounds [START_REF] Mohri | Foundations of Machine Learning[END_REF]. Formally, given a model f : R P →R c , and a loss function H : R c ×Y→[0, 1], we are interested in the quality of the learned perturbations ε ∈ B p (δ) L on new examples that we call the true fooling risk and defined as R f D (ε) = E (x,y)∼D max ε l ∈ε H(f (x+ε l ), y). Since D is unknown, we have no access to its value, but we can compute its empirical counterpart on a dataset S∼D n that we call empirical fooling risk and defined by

R f S (ε) = 1 n n i=1 max ε l ∈ε H(f (x i +ε l ), y i ).
Note that these definitions extend the fooling rate, for which H is the 0-1-loss. Since our objective is to learn perturbations that fool the model, our goal is to maximize the risk. To ensure that R f S (ε) is a good estimate of R f D (ε), we prove the following theorem based on the Rademacher complexity [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF]. This theorem is a generalization bound on the deviation between the two values. For the sake of completeness, we provide in Appendix the version of the bound based on the empirical Rademacher complexity. Theorem 2 (Proof deferred in Appendix). For any distribution D on X ×Y, for any loss function

H : R c × Y → [0, 1],
for any model f : R P →R c , for any L ∈ N + , for any budget δ > 0, for any ℓ p -norm with p ≥ 0, for any λ ∈ (0, 1], we have

P S∼D n   ∀ε ∈ B p (δ) L , R f D (ε) -R f S (ε) ≤ 2 R σ S B p (δ) L + 3 ln 4 λ 2n   ≥ 1 -λ, (6)
where we define the Rademacher complexity [START_REF] Peter | Model selection and error estimation[END_REF] of the "family of perturbations" B p (δ) L as

R S B p (δ) L = E σ∼Σ n sup ε∈Bp(δ) L 1 n n i=1 σ i max ε l ∈ε H(f (x i +ε l ), y i ) , (7)
with σ = {σ i } n i=1 ∼ Σ n , and Σ being the Rademacher distribution, i.e., Σ(-1)= 1 2 and Σ(+1)= 1 2 .

Equation ( 6) tells us that for all the possible sets of L ∈ N + perturbations ε belonging to B p (δ) L , the empirical risk R f S (ε) does not deviate too much from the true risk R f D (ε) when the Rademacher complexity R σ S [B p (δ) L ] is small. From the attacker's point of view, the associated lower bound on R f D (ε) is of interest and gives an estimate of the "chances" to fool the model. Put into words, the more the perturbations learned manage to fool a model on S and the lower the Rademacher complexity, the higher the chances to fool the model on new examples.

Note that Theorem 2 is valid for any perturbations ε that live in B p (δ) L (whatever the value of L, the budget δ and the p-norm), implying that our result is general enough to stand not only for the classical universal perturbations from B p (δ) (e.g., for UAP-PGD with L=1), but also for semi-universal perturbations learned from Problem 1. It is important to notice that Theorem 2 holds for any model f we want to attack that is not necessarily the one we used to learn ε. Hence, the bound holds in the context of adversarial transferability.

The form of this bound is quite classical, but it has the originality to state a theoretical certification from the attacker's point of view to estimate-given a model f -the true fooling risk R f D (ε) to quantify how much the learned perturbations are able to fool a given model on unseen examples. Indeed, in the literature many recent works aim to understand the generalization abilities in an adversarial setting, but they take the defender's point of view and provide generalization bounds for the so-called true adversarial risk that measures how much the learned model is able to face adversarial attacks on unseen examples. In other words, while we study the fooling abilities of the perturbations for a given model, they study the performance (or robustness) of the model when this latter is attacked by adversarial perturbations (without knowing the attack). Among these works, we can mention Yin et al. [START_REF] Yin | Rademacher complexity for adversarially robust generalization[END_REF], Khim and Loh [START_REF] Khim | Adversarial risk bounds via function transformation[END_REF], Awasthi et al. [START_REF] Awasthi | Adversarial learning guarantees for linear hypotheses and neural networks[END_REF] that are based on an adversarial Rademacher complexity of the class of the models. Other generalization bounds have been derived for the adversarial risk, such as with VC-dimension [START_REF] Attias | Improved generalization bounds for adversarially robust learning[END_REF][START_REF] Montasser | Vc classes are adversarially robustly learnable, but only improperly[END_REF], with covering numbers [START_REF] Mustafa | On the generalization analysis of adversarial learning[END_REF], with algorithmic stability [START_REF] Xing | On the algorithmic stability of adversarial training[END_REF], or in PAC-Bayes [START_REF] Eric | A pac-bayes analysis of adversarial robustness[END_REF].

Methodology: how to attack unseen examples

According to Theorem 2, once ε has been learned with Algorithm 1 from a sample S ∼ D n , we can attack a new example by picking one perturbation amongst the L perturbations as follows. Problem 2 (Attacking unseen example). Given some data pair (x, y) ∼ D, given a model f , the corresponding adversarial attack reads a = Proj X (x+ ε) where ε = argmax ε l ∈ε H(f (x+ε l ), y). If we do not have access to y, and assuming that f is a well-performing model, then y is replaced by C f (x). Pred. When f is a NN, in order to evaluate which perturbation from ε = [ε 1 , . . . , ε L ] maximizes the loss function, solving Problem 2 requires performing L independent forward passes through f . Note that, since they are independent, they can be performed in parallel to accelerate the computation. We provide below a complexity comparison between specific, semi-universal and universal attacks. Hence, from the standpoint of computational complexity, universal attacks are the most efficient. To a lesser extent, one-shot specific attacks (i.e., K=1, such as in FGSM [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]) and our proposed semi-universal attack achieve comparable complexity for small L.

Adversarial label

Numerical experiments

We now conduct experiments on 3 popular benchmark classification datasets and 2 NN architectures: a differentiable multi-layer perceptron (MNIST) and ResNets (CIFAR-10 and ImageNet). Hereafter, we consider ℓ ∞ -attacks with a maximum budget δ = 8/255. For reproducibility purposes we report implementation details such as pre-processing, data splitting and models tuning in the supplementary material, as well as results on ℓ 2 -attacks.

MNIST Experiments

We first consider the MNIST dataset [START_REF] Lecun | MNIST handwritten digit database[END_REF] useful to interpret the learned adversarial perturbations.

Illustration and role of the universal perturbations. We report in Figure 1 (left) the learned universal perturbations of 5-SUAP. Interestingly, they all exhibit strong patterns. In particular, we observe that ε 1 and ε 5 are very similar up to the sign difference. Indeed, since our framework does not handle the tuning of the sign of the perturbation, it might happen that 2 perturbations are the opposite of each others. It is worth noticing that the universal perturbations learned are consistent throughout multiple splits and random initializations. Moreover, we report in Figure 1 (right) the fooling matrices associated to each of the perturbations {ε l } 5 l=1 . The latter shows the correspondence between the predicted target C f (x) of some image x (in lines) and the label of the associated adversarial attack (in columns), i.e., C f (x+ ε) (see Problem 2). The fooling matrices highlight that each universal perturbation plays a different role. For instance, ε 1 mostly allows to attack images of digits "3" and "9" into being misclassified as "5" and "4", respectively. Instead, ε 3 is mainly used to attack images of "5" into "3". Coincidentally, one can distinguish the tilted digit "3" in ε 3 . As opposed to CW-UAP, our SUAP attack automatically captures the similarity between multiple digits such as "3" and "9". Illustration of the behavior of the generalization bound. We report in Figure 3 an estimation of the lower and upper bounds on R f D (ε) from Theorem 2. The Rademacher complexity is approximated by resorting to the maximization Algorithm 1 where L is replaced by the quantity inside the sup of Equation [START_REF] Benz | Universal adversarial training with class-wise perturbations[END_REF]. The maximum value of the objective is then averaged over multiple draw of σ ∼ Σ n . As expected, we observe that the empirical fooling risk increases with L. While the Rademacher complexity (and so the generalization gap between R f D (ε) and R f S (ε)) increases also with L it is interesting to remark that the lower bound on R f D (ε) tends to grow, suggesting that considering semi-universal perturbations can increase the chances to fool a model.

CIFAR-10 experiments

We turn to CIFAR-10 dataset [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] and compare the performance of our attack with the baselines. Baselines. Our L-SUAP attack is brought into comparison against the following universal attacks 6 .

• We compare with the UAP-PGD proposed by Shafahi et al. [START_REF] Shafahi | Universal adversarial training[END_REF] which is closely related to our 1-SUAP with a single perturbation, but differs from two aspects. First, the authors have considered a capped loss with parameter β to prevent any single sample from dominating the objective (hereafter we use the value β = 9 that was found to be the best in [START_REF] Shafahi | Universal adversarial training[END_REF]).

Second, the authors resort to the stochastic normalized gradient method ADAM to learn the perturbation. Since their code is not publicly available, we tried to reproduce their version as closely as possible.

• For the sake of consistency, we implemented a Pytorch version of the FAST-UAP [START_REF] Dai | Fast-UAP: An algorithm for expediting universal adversarial perturbation generation using the orientations of perturbation vectors[END_REF] originally designed for TensorFlow. We use the same hyper-parameters as in their code: a desired fooling rate of 80%, a maximum of 10 iterations for DeepFool, an overshoot of 0.02 to prevent vanishing updates.

• We compare against the CW-UAP [START_REF] Benz | Universal adversarial training with class-wise perturbations[END_REF] method whose code was kindly granted by the authors.

• We consider standard specific attacks such as FGSM [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] and PGD [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF] as well as more advanced techniques, i.e., MI-FGSM [START_REF] Dong | Boosting adversarial attacks with momentum[END_REF] and AutoAttack [START_REF] Croce | Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks[END_REF], in order to grasp the existing gap of performance between specific and universal attacks. To this effect, we resort to the TorchAttacks repository [START_REF] Kim | Torchattacks: A pytorch repository for adversarial attacks[END_REF].

Illustration and insights about SUAP attacks. Similarly to the MNIST experiment, we report in Figure 2a the learned 5-SUAP universal perturbations (left) and their fooling matrices (right). We observe that each SUAP universal perturbation plays a different role and illustrates diversity in perturbations. Indeed, for instance, ε 2 is mostly used to attack images of animals (bird, cat, dog, frog, horse) so that they become misclassified as deer: in ε 2 one can distinguish two deer facing each other. Another example is ε 3 that is mostly used to misclassify images of airplane and ship as bird; in ε 3 one can distinguish a bird. In addition, we report in Figures 2b and2c the fooling matrices and some universal perturbations of the CW-UAP attack and UAP attack, respectively. Contrary to SUAP, we have merged all 10 fooling matrices of CW-UAP (one for each class) into a single one since they are all disjointed. Thus, each row of Figure 2b (left) corresponds to the adversarial label obtained for each of 10 independent class-wise attacks. Unsurprisingly, many of the same couples (predicted label, adversarial label) appear in the fooling matrices of SUAP, CW-UAP and UAP. This makes sense since, ultimately, each couple (predicted label, adversarial label) depends on the similarity between images classes and how the classifier proceeds to distinguish between the classes. Despite this resemblance, the key point here is that all three methods operate differently. Especially, by its construction L-SUAP is able to find overlapping decomposition of the (predicted label, adversarial label) couple. As such, it automatically unveils the similarity between examples belonging to two different classes.

Impact of the numbers of training samples. Herein, we take a deeper look at the impact of two parameters on the performance of SUAP attacks. More precisely, we study the influence of the amount of training samples n and the number of perturbations L (see Problem 1) on the test fooling rate. To this end, we let n and L vary in {1K, 2K, 3K, 4K} and {1, 3, 5, 7, 10}, respectively. All learned L-SUAP attacks are evaluated on a distinct test set. Results, averaged over multiple splits, are reported in Figure 4. Overall, we observe that increasing L improves the performance, thus confirming that having more perturbations is beneficial to attack the network f . This observation has to be contrasted with the fact that the amount of data n required to achieve good performance goes in pair with the complexity of the learning Problem 1, hence with L. As such, for n = 1K or 2K, the performance does not significantly improve (or worse, decrease) with larger L. In what follows, we restrict to a setting made of few samples (i.e., n = 2K). Comparison with baselines. We report in Table 1 the performances of ℓ ∞ -attacks, in terms of fooling rate. First of all, 1-SUAP outperforms all universal attacks (i.e., UAP-PGD, FAST-UAP and CW-UAP) and, most importantly, it surpasses UAP-PGD which is closely related. We believe that this is due to our algorithmic solution which benefits from better optimization guarantees. In addition, as L grows, we observe an increase in performance of SUAP attacks, thus justifying the advantages of having more degrees of freedom. Interestingly, the SUAP attacks manage to improve upon the one-shot specific FGSM attack. However, the performances are still very far behind the more advanced specific attacks. Nonetheless, such difference in performance have to be contrasted with their associated computational complexity (see Remark 2). Overall, L-SUAP yields a competitive trade-off between universality and specificity by tuning the number L of universal perturbations. Transferability of attacks. We further evaluate how the learned attacks on the ResNet18 model manage to fool more complex architectures such as the pre-trained ResNet50 and MobileNetv2 [START_REF] Sandler | Mobilenetv2: Inverted residuals and linear bottlenecks[END_REF] models. We additionally consider two robust models from the RobustBench repository [START_REF] Croce | Robustbench: adversarial robustness benchmark[END_REF], namely r-ResNet18 [START_REF] Sehwag | Robust learning meets generative models: Can proxy distributions improve adversarial robustness[END_REF] and r-ResNet50 [START_REF] Chen | Adversarial robustness: From self-supervised pre-training to fine-tuning[END_REF], which are trained with some defense mechanisms against ℓ ∞ -attacks of budget δ = 8/255. Results are reported in Table 1. Overall, L-SUAP systematically yields a better transferability than all universal attacks, as shown by the higher fooling rates. In addition, it manages to outperform specific attacks when the target model architecture is significantly different than the base model on which the attacks have been learned (i.e., Mobilenetv2 vs. ResNet18). Note that this is precisely the setting where most universal attacks also show greater transferability than specific attacks. Interestingly, L-SUAP shows competitive results on robust models.

ImageNet experiments

We tackle a large scale scenario made of 1K classes. Such setting is problematic for CW-UAP as computing or storing 1K perturbations exceeds most memory storage spaces: It is not studied here. Results. We report the performances in Table 2. Once again, we a drastic gap of performance between UAP-PGD and 1-SUAP, confirming the superiority of the numerical solution of Algorithm 2 for L = 1 perturbation over the standard UAP-PGD solver [START_REF] Shafahi | Universal adversarial training[END_REF]. Overall, SUAP achieves performance of the order of magnitude as specific attacks (e.g., MI-FGSM). It suggests that, for large-scale settings with numerous classes, solely a few universal perturbations are enough to attack most of images.

Conclusion

This paper introduces a framework for crafting semi-universal attacks. This new family of attacks is halfway between specific and universal attacks by jointly leaning multiple universal perturbations. When facing an unseen example, an adversarial example is built by selecting, in an unsupervised manner, the appropriate perturbation among all. Numerical experiments support that the number of perturbations does act as a trade-off between universality and specificity. Beyond the gain in performance, semi-universal attacks pull out of existing attacks by capturing meaningful patterns

ATTACK

ResNet18 FGSM [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] 84.53 ± 0.05 MI-FGSM [START_REF] Dong | Boosting adversarial attacks with momentum[END_REF] 90.04 ± 0.02 PGD [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF] 94.99 ± 0.06 AutoAttack [START_REF] Croce | Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks[END_REF] 88.23 ± 0.05 describing the most common flaws to fool the classifier. The latter shed some light both on how the classifier operates and on the existing similarities between the training instances. Future works will be devoted to the design of defense mechanisms against semi-universal attacks as well as the derivation of the associated generalization bounds. Indeed, we believe that such results open directions to improve the robustness of models against various and diverse attacks. Theorem 3.3 Mohri et al. [START_REF] Mohri | Foundations of Machine Learning[END_REF]. D on X × Y, for any set G of functions g : X × Y → [0, 1], for any λ ∈ (0, 1], we have

P S∼D n ∀g ∈ G, E (x,y)∼D g(x, y) - 1 n n i=1 g(x i , y i ) ≤ 2 E S ′ ∼D n E σ∼Σ n sup g ′ ∈G 1 n n i=1 σ i g ′ (x ′ i , y ′ i ) + ln 1 λ 2n   ≥ 1 -λ, (9)
and

P S∼D n ∀g ∈ G, E (x,y)∼D g(x, y) - 1 n n i=1 g(x i , y i ) ≤ 2 E σ∼Σ n sup g ′ ∈G 2 n n i=1 σ i g ′ (x i , y i ) + 3 ln 2 λ 2n   ≥ 1 -λ. ( 10
)
Before proving Theorem 2 in Section B.2, we recall how we can obtain two-sided generalization bounds from Mohri et al. [START_REF] Mohri | Foundations of Machine Learning[END_REF]'s Theorem 3.3.

B.1 From one-sided to two-sided generalization bounds Mohri et al. [START_REF] Mohri | Foundations of Machine Learning[END_REF]'s Theorem 3.3 brings a one-sided generalization bound, i.e., an upper bound on E (x,y)∼D g(x, y) -

1 n n i=1 g(x i , y i ).
That being said, Theorem 2 provides a two-sided bound, i.e., an upper bound on the term E (x,y)∼D g(x, y) -1 n n i=1 g(x i , y i ) . To do so, one common solution is to use the union bound (e.g. [START_REF] Nishant | Machine learning theory (csc 482a/581a) -lectures[END_REF]). For the sake of completeness, we state the two-sided bound associated to Theorem 3.3. of Mohri et al. [START_REF] Mohri | Foundations of Machine Learning[END_REF] in the following lemma. Lemma 1 (Two-sided generalization bounds). For any distribution D on X × Y, for any set G of functions g : X × Y → [0, 1], for any λ ∈ (0, 1], we have

P S∼D n ∀g ∈ G, E (x,y)∼D g(x, y) - 1 n n i=1 g(x i , y i ) ≤ 2 E S ′ ∼D n E σ∼Σ n sup g ′ ∈G 1 n n i=1 σ i g ′ (x ′ i , y ′ i ) + ln 2 λ 2n   ≥ 1 -λ, (11)
and

P S∼D n ∀g ∈ G, E (x,y)∼D g(x, y) - 1 n n i=1 g(x i , y i ) ≤ 2 E σ∼Σ n sup g ′ ∈G 1 n n i=1 σ i g ′ (x i , y i ) + 3 ln 4 λ 2n   ≥ 1 -λ. (12)
Proof. We can go through the exact same proof of Mohri et al. [START_REF] Mohri | Foundations of Machine Learning[END_REF]'s Theorem 3.3 but with

1 n n i=1 g(x i , y i ) - E (x,y)∼D g(x, y) instead of E (x,y)∼D g(x, y) -1 n n i=1 g(x i , y i ). Hence, we obtain with probability at least 1-λ 2 over S ∼ D n ∀g ∈ G, 1 n n i=1 g(x i , y i ) -E (x,y)∼D g(x, y) ≤ 2 E S ′ ∼D n E σ∼Σ n sup g ′ ∈G 1 n n i=1 σ i g ′ (x ′ i , y ′ i ) + ln 2 λ 2n , (13)
and ∀g ∈ G,

1 n n i=1 g(x i , y i ) -E (x,y)∼D g(x, y) ≤ 2 E σ∼Σ n sup g ′ ∈G 1 n n i=1 σ i g ′ (x i , y i ) + 3 ln 4 λ 2n . (14)
Hence, by combining Equations ( 13) and ( 9) from a union bound (and with λ/2 instead of λ), we obtain [START_REF] Claudiu Cireşan | Deep, Big, Simple Neural Nets for Handwritten Digit Recognition[END_REF].

Similarly, from Equations and we get Equation [START_REF] Patrick | Lipschitz certificates for layered network structures driven by averaged activation operators[END_REF].

B.2 Proof Theorem 2

We are now ready to prove Theorem 2.

Theorem 2. For any distribution D on X ×Y, for any loss function H : R c × Y → [0, 1], for any model f : R P →R c , for any L ∈ N + , for any budget δ > 0, for any ℓ p -norm with p ≥ 0, for any λ ∈ (0, 1], we have

P S∼D n   ∀ε ∈ B p (δ) L , R f D (ε) -R f S (ε) ≤ 2 R S B p (δ) L + 3 ln 4 λ 2n   ≥ 1-λ, (6)
and

P S∼D n   ∀ε ∈ B p (δ) L , R f D (ε) -R f S (ε) ≤ 2 E S ′ ∼D n R S ′ B p (δ) L + ln 2 λ 2n   ≥ 1-λ, (15)
where we define the Rademacher complexity [START_REF] Peter | Model selection and error estimation[END_REF] of the "family of perturbations" B p (δ) L as

R S B p (δ) L = E σ∼Σ sup ε∈Bp(δ) L 1 n n i=1 σ i max ε l ∈ε H(f (x i +ε l ), y i ) ,
with σ = {σ i } n i=1 ∼ Σ n , and Σ being the Rademacher distribution, i.e., Σ(-1)= 1 2 and Σ(+1)= 1 2 . Note that Equation ( 15) is not in the main paper and involves the Rademacher complexity defined by E S ′ ∼D n R S ′ B p (δ) L ; the remarks in the main paper for Equation ( 6) also apply for Equation [START_REF] Dai | Fast-UAP: An algorithm for expediting universal adversarial perturbation generation using the orientations of perturbation vectors[END_REF].

Proof. Given L > 0, we define the set of function G by

G = g : (x, y) → max ε l ∈ε H ′ (f (x + ε l ), y) ε = [ε 1 , . . . , ε L ] ∈ B p (δ) L .
By applying Lemma 1 on the set G, we have the desired results.

C Experimental settings

In this section, we further detail how the numerical experiments were conducted.

C.1 MNIST experiments

Data splitting and pre-processing. The 60K samples of the training set undergo random affine transformations keeping the center invariant. To this effect, we use random rotations between [11.25, +11.25] degrees and a random scaling selected in [-0.825, +0.825]. These deformed samples are used to learn f while we randomly pick 500 original un-deformed images from the training dataset to learn the (semi-)universal attacks. The 10K images of the test set are used to evaluate the performance of the attacks. All images are flatten into 784 dimensional rescaled vectors so that the pixel intensity lies within [0, 1].

Model to attack. We consider a differentiable model satisfying the KŁ property assumed in Theorem 1 (see Remark 1). To this effect, we resort to the simple multi-layer perceptron from [START_REF] Claudiu Cireşan | Deep, Big, Simple Neural Nets for Handwritten Digit Recognition[END_REF] which manages to achieve under 1% test accuracy. It is made of scaled hyperbolic tangent activation functions as well of an input layer, 8 hidden layers and an output linear layer of sizes 784 × 1000, 1000 × 1000 and 1000 × 10, respectively. The network is trained using a stochastic gradient descent with batch size 100 with a learning rate linearly decreasing from 10 -3 to 10 -6 over 10 3 epochs.

C.2 CIFAR10 experiments

Data splitting and pre-processing. If not mentioned otherwise, we split CIFAR10 test set into 2K images for learning (semi-)universal perturbations and 8K independent images for evaluating the attacks.

Model to attack. We consider the trained ResNet18 model from [START_REF] Phan | huyvnphan/pytorch_cifar10[END_REF] augmented with an input normalizing layer of channel-wise means (0.4914, 0.4822, 0.4465) and channel-wise standard deviations (0.2471, 0.2435, 0.2616).

D Additional results

In the next sections, we provide complementary results on both MNIST and CIFAR10 datasets.

D.1 MNIST experiments

We analyze the training behavior of L-SUAP attacks with L ∈ {1, 3, 5, 10} universal perturbations learned with the Algorithm 1. The experiment is repeated over 5 independent seeds and the averaged training loss is reported in Figure 5. Independently of L, it shows the well-behaved increasing behavior of the loss along the number of epochs. In addition, it supports the fact that having more universal perturbations does permit to achieve higher dissimilarity hence higher loss values. This is seconded by the mean test fooling rate reported for each of the L-SUAP attacks since we observe an increased fooling rate as L grows. On a side note, on this simple dataset, it is difficult to fool the studied network f , hence justifying the small fooling rates depicted in Figure 5.

D.2 CIFAR10 experiments

We report in Table 3 the performance comparison of both ℓ ∞ and ℓ 2 -attacks with a maximum allowable budget of δ = 8/255 and δ = 0.5, respectively. 53.82 (± 0.00) N/A MI-FGSM [START_REF] Dong | Boosting adversarial attacks with momentum[END_REF] 80.76 (± 0.00) N/A PGD [START_REF] Madry | Towards deep learning models resistant to adversarial attacks[END_REF] 93.61 (± 0.06) 89.23 (± 0.02) AutoAttack [START_REF] Croce | Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks[END_REF] 93.07 (± 0.00) 92.41 (± 0.01)

Figure 1 :

 1 Figure 1: ℓ ∞ -based SUAP attacks on MNIST. (Left panel) Learned adversarial perturbations. (Right panel) In the fooling matrix, labels range from 0 to 9 from top to bottom and from left to right.

Remark 2 .

 2 Given a model f that is a neural network whose forward complexity is of O(d) for a single input sample, then the complexity to compute ∇H(f (x), y) is of order O(2d), since the backward pass is also of order O(d). Then, it follows that (specific) for K iterations, cost ∼ O(2Kd ); and (semi-universal) for L perturbations, cost ∼ O(Ld ); (universal) cost ∼ O(1 ).

  CW-UAP attacks. Each row of the fooling matrix indicates the adversarial label obtained for each 10 class-wise attacks.

Figure 2 :

 2 Figure 2: ℓ ∞ -based attacks on CIFAR-10. In the fooling matrices, labels range {airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck} from top to bottom and left to right.

Figure 3 :Figure 4 :

 34 Figure 3: Generalization bound. The top of the orange bar, resp. the bottom, is the approximation of the upper, resp. lower, bound of R f D .

Figure 5 :

 5 Figure 5: Training behavior of ℓ ∞ -based SUAP on MNIST. The averaged training loss is reported 1, 5 and 10 universal perturbations along the associated test fooling rate.

  Recently, UAP-PGD has been extended to class-wise UAP where a universal perturbation is built for each class. Let us denote ∀k ∈ Y, S k = {x i | (x i , k) ∈ S} the set of training points of the k-th class and n k the size of S k , then CW-UAP aims at solving maximize {ε k ∈R P } k∈Y k∈Y

Table 1 :

 1 Performance and transferability ∞ -attacks on a ResNet18 trained on CIFAR-10. divided into universal (top), semi-universal (middle) and specific (bottom) attacks. Bold fonts highlight the best fooling rate in each attack category for each target model (along the columns). ± 0.06 30.47 ± 0.12 38.17 ± 0.37 1.94 ± 0.05 2.53 ± 0.08 AutoAttack [13] 93.07 ± 0.00 31.79 ± 0.16 38.08 ± 0.27 1.91 ± 0.02 2.41 ± 0.02

	ATTACK	SOURCE ResNet18	ResNet50	TRANSFER MobileNetv2 r-ResNet18 r-ResNet50
	UAP-PGD [49]	12.53 ± 0.60 21.51 ± 0.18 39.37 ± 0.19 2.01 ± 0.01 2.54 ± 0.05
	FAST-UAP [15] 11.16 ± 1.03 19.65 ± 1.22 36.51 ± 0.30 1.94 ± 0.01 2.33 ± 0.05
	CW-UAP [7]	13.85 ± 0.18 21.95 ± 0.28 39.62 ± 0.33 2.26 ± 0.07 2.26 ± 0.06
	1-SUAP	36.83 ± 0.93 27.45 ± 0.81 44.11 ± 0.35 2.27 ± 0.02 2.27 ± 0.08
	3-SUAP	54.03 ± 0.54 28.49 ± 0.56 45.42 ± 0.32 2.55 ± 0.03 2.95 ± 0.08
	5-SUAP	55.56 ± 0.57 28.87 ± 0.07 46.09 ± 0.10 2.56 ± 0.05 3.10 ± 0.05
	FGSM [19]	53.82 ± 0.00 28.55 ± 0.00 38.10 ± 0.00 3.02 ± 0.00 3.14 ± 0.00
	MI-FGSM [16]	80.76 ± 0.00 29.95 ± 0.01 35.46 ± 0.01 2.60 ± 0.00 3.41 ± 0.00
	PGD [34]	93.61

Table 2 :

 2 Performance of ℓ ∞ -attacks on a ResNet18 trained on ImageNet. Bold fonts highlight the best fooling rate in universal (left), semi-universal (middle) and specific (right) attacks.

	ATTACK	ResNet18	ATTACK	ResNet18
	UAP-PGD [49] 27.36 ± 0.00	1-SUAP	83.17 ± 2.62
	FAST-UAP [15] 23.46 ± 0.25	5-SUAP	88.98 ± 1.06
			10-SUAP 87.24 ± 1.16

Table 3 :

 3 Performance of attacks on a ResNet18 trained on CIFAR-10. Bold fonts highlight the best fooling rate in universal (top), semi-universal (middle) and specific (bottom) attacks.

	Attack	ℓ ∞ rate (%) ℓ 2 rate
	UAP-PGD [49]	12.53 (± 0.60)	2.67 0.21)
	FAST-UAP [15]	11.16 (± 1.03)	2.53 (± 0.19)
	CW-UAP [7]	13.85 (± 0.18)	2.77 (± 0.09)
	1-SUAP	36.83 (± 0.93)	3.43 (± 0.26)
	3-SUAP	54.03 (± 0.54)	4.93 (± 0.50)
	5-SUAP	55.56 (± 0.57)	7.09 (± 1.22)
	FGSM [19]

We make the distinction between X and R P since the input data can live inside a manifold (e.g., the space of images whose pixels' intensity lies within [0,1]).

Note that L is first and foremost not differentiable because of the max term. However, empirically, iterates almost never lie at such singularities. To avoid this concern, one can replace max by a smooth approximation.

Pytorch codes of UAP and Fast-UAP baselines will be made publicly available along with our proposed SUAP attack in order to contribute to the TorchAttacks repository[START_REF] Kim | Torchattacks: A pytorch repository for adversarial attacks[END_REF].

Notations. For and I ⊆ {1, . . . , P }, x I stands for the restriction of x to the indices in I.

A Stochastic solver

We propose an additional solver fully exploiting the finite-sum nature of the loss in Problem 1. To this regard, we begin by rewriting it by means of the sample-wise losses ℓ i , i.e.,

Hereafter, we resort to a stochastic solver based on the well-known variance reduction techniques (see [START_REF] Sashank | Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization[END_REF][START_REF] Wang | SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms[END_REF][START_REF] Nhan | Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization[END_REF]).

Since the main computational load comes from the backpropagation through the neural network, we favor the proxSAGA algorithm [START_REF] Sashank | Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization[END_REF] which does not require an additional loop over multiple epochs. The corresponding algorithmic solution is summarized in Algorithm 2.

Such solver should become particularly useful to deal with large datasets by treating one sample at a time. We recall below the convergence guarantees under the assumption of Lipschitz continuity.

Theorem 3 (J. Reddi et al. [START_REF] Sashank | Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization[END_REF]). Suppose that ∇L is Lipschitz continuous with Lipschitz constant β. Let {ε (k) } k∈N be the sequence of Algorithm 2 with fixed step-size γ k = γ ≤ 1/(5βn) and batch-size b = 1. Then, for k uniformly sampled from {1, . . . , K}, the following holds:

where ε ⋆ is a maximizer of L and G γ : ε → γ -1 (ε -P Bp(δ) (ε + γ∇L(ε))) is the gradient mapping.

Note that Theorem 3 relies on the Lipschitz constant β whose calculation is out of reach. Instead, in practice we suggest either to choose β large enough or to compute rough estimate at each iteration.

B About Theorem 2

The proof of Theorem 2 relies on Theorem 3.3 of Mohri et al. [START_REF] Mohri | Foundations of Machine Learning[END_REF] recalled below.