A PAC-Bayes Analysis of Adversarial Robustness
Authors: Paul Viallard
Guillaume Eric VIDOT
Amaury Habrard
Emilie Morvant
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial Robustness
PAC-Bayesian
Generalization Bound

Abstract: We propose the first general PAC-Bayesian generalization bounds for adversarial robustness, that estimate, at test time, how much a model will be invariant to imperceptible perturbations in the input. Instead of deriving a worst-case analysis of the risk of a hypothesis over all the possible perturbations, we leverage the PAC-Bayesian framework to bound the averaged risk on the perturbations for majority votes (over the whole class of hypotheses). Our theoretically founded analysis has the advantage to provide general bounds (i) that are valid for any kind of attacks (i.e., the adversarial attacks), (ii) that are tight thanks to the PAC-Bayesian framework, (iii) that can be directly minimized during the learning phase to obtain a robust model on different attacks at test time.

A PAC-Bayes Analysis of Adversarial Robustness
Paul Viallard'; Univ Lyon, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE France
Guillaume Vidot Amaury Habrard', Emilie Morvant'
CNRS. Institut Optique Graduate School,
Airbus Opération S.A.S
University of Toulouse, Institut de Recherche en Informatique de Toulouse, France
Abstract
We propose the first general PAC-Bayesiar generalization bounds for adversarial robustness, that estimate, at test time, how much a model will be invariant imperceptible perturbations in the input. Instead of deriving worst-case analysis of the risk of hypothesis over all the possible perturbations, we leverage the PAC- Bayesian framework to bound the averaged risk on the perturbations for majority votes (over the whole class of hypotheses). Our theoretically founded analysis has the advantage to provide general bounds (i) that are valid for any kind attacks (i.e., the adversarial attacks), (ii) that tight thanks the PAC-Bayesian framework, (ii)) that can be directly minimized during the learning phase to obtain robust model different attacks test time.
Introduction
While machine learning algorithms are able to solve huge variety of tasks, Szegedy et al. [014]] pointed out erucial weakness: the possibility to generate samples similar the originals (i.e., with no or insignificant change recognizable by the human eyes) but with different outcome from the algorithm. This phenomenon, known as "adversarial examples", contributes to the impossibility to ensure the safety of machine learning algorithms for safety-critical applications such aeronautic functions (e.g., vision-basee navigation), autonomous driving, or medical diagnosis (see, e.g., Huang et al. 2020 Adversarial robustness is thus critical issue in machine learning that studies the ability of a model to be robust or invariant to perturbations of its input. A perturbed input that fools the model is usually called adversarial example. In other words, adversarial example be defined as an example that has been modified by an imperceptible noise (or that does not exceed a threshold) but which leads to misclassification One line of research referred to adversarial robustness verification [e-g., Gehr et al.] 20188 Huang et al., 2017] Singh et all 2019 Tsuzuku et al.) (018). where the objective is formally check whether the neighborhood of each sample does not contain any adversarial examples. This kind of method comes with some limitations such as scalability or
overapproximation [Gehr al. 2018 Katz al. 2017 Singh al. 2019]. In this paper we stand in
another setting called adversarial attack/defense (e.g.. Papernot et al. 2016 Goodfellow et al. 2015
Madry et al. 2018 Carlini and Wagner 2017| Zantedeschi et al. [017]] Kurakin et al.) 2017 An
adversarial attack consists in finding perturbed examples that defeat machine learning algorithms while the adversarial defense techniques enhance their adversarial robustness to make the attacks useless. While lot of methods exist, adversarial robustness suffers from a lack of general theoretical understandings (see Section 2.2)
To tackle this issue, we propose in this paper to formulate the adversarial robustness through the lens of well-founded statistical machine learning theory called PAC-Bayes and introduced by SShaee Taylor and Williamson [199], McAllester (998). This theory has the advantage to provide tight
Paul Viallard and Guillaume Vidot contributed equally to this work
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

generalization bounds in average over the set of hypotheses considered (leading to bounds for weighted majority vote over this set), contrast to other theories such VC-dimension or Rademacher-based approaches that give worst-case analysis, i.e., for all the hypotheses. We start by defining our setting called adversarially robust PAC-Bayes. The idea consists in considering an averaged adversarial robustness risk which corresponds to the probability that the model misclassifies a perturbed example (this can be seen as an averaged risk over the perturbations). This measure can be too optimistic and not enough informative since for each example we sample only one perturbation. adversarial risk as the probability that there exists at least
Thus we also define an averaged-men one perturbation (taken in set of sampled perturbations) that leads to a misclassification. These definitions, based on averaged quantities, have the advantage (i) of still being suitable for the PAC- Bayesian framework and majority vote classifiers and (ii) to be related to the classical adversarial robustness risk. Then, for each of our adversarial risks, we derive a PAC-Bayesian generalization bound that can valid any kind of attack. From algorithmic point of view, these bounds can be directly minimized in order to learn a majority vote robust in average to attacks. We empirically illustrate that framework is able to provide generalization guarantees with non-vacuous bounds for the adversarial risk while ensuring efficient protection to adversarial attacks.
Organization of the paper. Section 2 recalls basics on usual adversarial robustness. We state our new adversarial robustness PAC-Bayesia setting along with our theoretical results in Section Bl and we empirically show its soundness in Section
g
All the proofs of the results are deferred in Appendix.
2 Basics on adversarial robustness
2.1 General setting
We tackle binary classification tasks with the input space X-R' and the output/label space (=1-1,+1). We assume that D is fixed but unknown distribution XxY. An example is denoted by (x, y) XY. Let S= ( 31) })) be the learning sample consisted of m examples i.i.d. from D; We denote the distribution of such m-sample by D Let H be a of real-valued functions from X to [-1, +1] called voters or hypotheses. Usually, given a learning sample S~ Dm", learner aims at finding the best hypothesis h from H. that commits as few errors as possible on unseen data from D. One wants to find h E H. that minimizes the true risk Rp (h) on D defined as
(h) (a.y)~
E é (h, (1,,21))) (I,
where e:HxXxY-II is the loss function. In practice since D is unknown we cannot compute (h), we usually deal with the empirical risk (h) estimated on S and defined as
Rs(h) 1 Σ E(h, (4t, 8:)).
From a classic ideal machine learning standpoint, we are able to learn a well-performing classifier with strong guarantees on unseen data, and even to measure how much the model will be able to generalize on D (e.g., with generalization bounds).
However, in real-life applications at classification time, an imperceptible perturbation of the input (e.g., due to a malicious attack or a noise) can have a bad influence on the classification performance on unseen data (Szegedy et al.) [014]: the usual guarantees do not stand anymore. Such imperceptible perturbation can be modeled by (relatively small) noise in the input. Let b> and ||-I| be an arbitrary norm (the most used norms are the f,, Eg and E nnorms,, the set of possible noises B is defined by
B B=fEE E Rdd ||||| 6).
The learner aims to find an adversarial robust classifier that is robust in average to all noises in B over (x., y) ~ D. More formally, one wants to minimize the adversarial robust true risk R (h) defined as
R80B (h)
max.eB (h, (x+e,y)).
(2)
(
Similarly as in the classic setting, since D is unknown, RBg8 (h) cannot be directly computed, and then one usually deals with the empirical adversarial risk
1
B80B R
(h)
m l (h, (x++c,ys))

---

That being said, a learned classifier h should be robust to adversarial attacks that aim at finding an adversarial example z+t"(zzy) to fool h for given example (z. y), where c'(z.y) defined as
c² (z.y) E argmax,en E(h, (x+cc.))
In consequence, adversarial defense mechanisms often rely on the adversarial attacks by replacing the original examples with the adversarial ones during the learning phase; This procedure is called adversarial training. Even if there are other defenses, adversarial training appears to be one of the most efficient defense mechanisms [Ren et al. 2020
2.2 Related works
Adversarial Attacks/Defenses Numerous method exist to solve-or approximate- the optimiza- tion of Equation (3). Among them, the Fast Gradient Sign Method (FGSM GGodfellow et al. (2013) is an attack consisting in generating a noise e in the direction of the gradient of the loss function with respect the input x. Kurakin al. 2017] introduced IFGSM, an iterative version of FGSM: at each iteration, one repeats FGSM and adds to x a noise, that is the sign of the gradient of the loss with respect to z. Following the same principle as IFGSM, JFGG,,,aarry et al. [2018] proposed a method based on Projected Gradient Descent (PGD) that includes a random initialization of æ before the optimization. Another technique known as the Carlini and Wagner Attack (Carlini and Wagner 2017) aims at finding adversarial examples z+ry(xxy)) that are as close as possible to the original J, Le., they want an attack being the most imperceptible as possible. However, producing such imperceptible perturbation leads to a high-running time in practice. Contrary to the most popular techniques that look for a model with a low adversarial robust risk (Equation ) D. our work stands in another line of research where the idea is to relax this worst-case risk measure by considering an averaged adversarial robust risk over the noises instead of a max-based formulation [see, e.g., Zantedeschi et al. 2017 Hendrycks and Dietterich, 2019]. Our averaged formulation is introduced in the Section
Generalization Bounds. Recently, few generalization bounds for adversarial robustness have been
introduced [e.g. Khim and Loh, 2018 8 Yin et al. [019 Montasser et al. 2019 2020 Cohen et al.
2019 Salman et al..222..0 2019]. Khim and Loh| and Yin et al. (s results are Rademacher complexity-ban
bounds. The former makes use of a surrogate of the adversarial risk; The latter provides bounds in the specific case of neural networks and linear classifiers, and involves an unavoidable polynomial dependence on the dimension of the input. Montasser et al.] study robust PAC-learning for PAC- learnable classes with finite VC-dimension for unweighted majority votes that have been "robustified" with a boosting algorithm. However, their algorithm requires to consider all possible adversarial perturbations for each example which is intractable in practice, and their bound suffers also from large constant as indicated at the end of the Montasser et al. [Theorem 3.1 2019]'s proof. Cohen et al. provide bounds that estimate what is the minimum noise to get an adversarial example (in the case of perturbations expressed Gaussian noise) while results give the probability to be fooled by an adversarial example. [almann et al.] leverage Cohen et al. method and adversarial training in order to get tighter bounds. Moreover, Farnia et al. present margin- basedd bounds on the adversarial robust risk for specific neural networks and attacks (such as FGSM or PGD). While they made use of a classical PAC-Bayes bound, their result is not PAC-Bayesian analysis and stands in the family of bounds [see Nagarajan and Kolter, 2019 Ap. J for details). In this paper, we provide PAC-Bayes bounds for general models expressed as majority votes, their bounds thus not directly comparable to ours.
3 Adversarially robust PAC-Bayes
Although few theoretical results exist, the majority of works come either without theoretical guarantee or with very specific theoretical justifications. In the following, we aim giving a different point of view on adversarial robustness based on the so-called PAC- PAC-Bayesian framework. By leveraging this framework, we derive general generalization bound for adversarial robustness based on an averaged notion of risk that allows us to learn robust models at test time. We introduce below our new setting referred to as adversarially robust PAC-Bayes.
'The reader can refer to Ren et al. 2020 for survey on adversarial attacks and defenses.
3

---

3.1 Adversarially robust majority vote
The PAC-Bayesian framework provides practical and theoretical tools to analyze majority vote classifiers. Assuming the voters set '4 and a learning sample S as defined in Section our goal is anymore learn one classifier from H. but learn well-performing weighted combination of the voters involved in H. the weights being modeled by distribution Q on H. This distribution is called the posterior distribution and learned from given prior distribution P on H. The learned weighted combination is called a Q-weighted majority vote and is defined by
Vx X, Hz(z) sign
h(z) h~2
In the rest the paper, we consider the 0-1 loss function classically used for majority votes in PAC-Bayes and defined as L(h, (z. y))= (h(x)) * y) with I(a)=1 if is true, and 0 otherwise. In this context, the adversarial perturbation related to Equation
becomes
<'(x.y) argmax, I (2 y).
(5)
Optimizing this problem is intractable due to the non-convexity of Hg induced by the sign function. Note that the adversarial attacks the literature (like PGD or IFGSM) aim at finding the optimal perturbation e" (rr.), but, in practice
considers approximation of this perturbation.
Hence, instead of searching for the noise that maximizes the chance of fooling the algorithm, we propose to model the perturbation according to example-dependent distribution. First let us define wia,y) a distribution, on the set of possible noises B, that is dependent on an example (x,, y) XxY. Then we denote as the distribution on (XxY)x defined as D((2, v), = D(x, v) (().y(()) which further permits to generate perturbed examples. To es- timate our risks (defined below) for given example (I,, DD we consider set of n perturbations sampled from (x)))))) denoted by E Then we consider learning set the m n-splele In other words, each ((I y.), E,) E sampled from
= {(1,, y:). ) E (XxY distribution that we denote by D such that
n
D ("((,, E,), D(r v.) II w (as (c)).
Then, inspired by the works of Zantedeschi et al. 2017 Hendrycks and Dietterich (009 we define robustness averaged adversarial risk as follows.
Definition (Averaged Adversarial Risk). For any distribution on (XxY) X. for any distribu-
tion Q on H. the averaged adversarial risk of Hg is defined as
Rp (H2) ((x.)),c)-D
Pr
(Ho(x ())
E
I(Ho( + + y).
((>.)).))>D
The empirical averaged adversarial risk is computed on a m Xn-sample S [((,,, (((,,,,))) E.) is
Rs(Ho) 1
mn I(Ho(z,te)) # y1).
As we will show in Proposition the risk (D(H)) can considered optimistic regarding c"(x.y) of Equation (5). Indeed, instead of taking the maximizing the loss, unique drawn from distribution. Hence, it can lead to a non-informative risk regarding the occurrence of adversarial examples. To overcome this, we propose an extension that we refer as averaged-max adversarial risk.
Definition 2 (Averaged-Max Adversarial Risk), For any distribution on (XxY) B, for any distribution Q on H. the averaged-max adversarial risk of HQ is defined as
AD=(Ho)= Pr (Ac &, Holx + +) $ F ()=.D)
The empirical averaged-max adversarial risk computed on m m--saplee ((I,, (i)),
As(He)
max.se, I(Ho(m; + +c) 4t).
For an example (ar, y),y) instead of checking if one perturbed example aht is adversarial, we sample perturbed examples z z+t tE,, and we check if at least one example is adversarial.

---

3.2 Relations between the adversarial risks
Proposition below shows the intrinsic relationships between the classical adversarial risk RD (He) and our two relaxations RD ( and AD-(Ho). In particular, Proposition B shows that the larger the number of perturbed examples. the higher is the chance get an adversarial example and then to be close to the adversarial risk D (H)).
Proposition 3. For any distribution D on (XXY)xB, for any distribution Q on H. for any nn,n') N2, with n' 2 we have
(D( S ADo I AD (Hl) <
R (Ho).
(6)
The left-hand side of Equation
C confirms that the averaged adversarial risk RD (H)) is optimistic regarding the classical Rh (Ho)). Proposition estimates how close Rp (H2) can be R (H2).
Proposition 4. For any distribution D on (X Y) x B, for any distribution Q on H. we have
R He) TV S RD(HO):
where A and II are distributions on XxY, and Ax',y'), respectively IT(x' v/), corresponds to the probability of drawing perturbed example (a++) with ((),)),e)-D, respectively un adversarial example (x++"(x,,), y) with (2.y)~D We have
A(x' Pr ((a.)).))-DD
[x+e=xx' .==/), and ITd' ,/) (a.y)=
Pr (x+t (x, v)-.)) (7)
II(x's ./) A x .yy)
and (V(IT]A)
E (x' (>'
is the Total Variation (TV) distance between II and A.
Note that e* (z.y) depends Q, and hence II depends Q. From Equation 7 Rp (He) (H)) can be rewritten (see Lemmas and 9 in Appendix respectively with and as
and
(H2
Pr [Ho(x') + vl. and RCBB (He)
Pr
Ho (x') * y'].
(xe' (e'gg))~
(e' (e'1"')-11
Finally, Propositions 3 and relate the adversarial risk RD (H2) to the "standard" adversarial risk RD (H)). Indeed, by merging the two propositions we obtain
RBBB (H2) TV (H2) s AD=(H)) S RD (HQ).
Hence, the smaller the TV distance (A)), the closer the averaged adversarial risk Ri (Hl) is from 1280 (Ho) and the more probable example ((x, v),e) sampled from D would be adversarial, Le., when our "averaged" adversarial example looks like a "specific" adversarial example. Moreover, Equation 8 justifies that the PAC-Bayesian point of view makes sense for adversarial learning with theoretical guarantees: the PAC- MAC-Bayesian guarantees we derive in the next section for our adversarial risks also give some guarantees on the "standard risk" RRRB (H2)-
3.3 PAC-Bayesian bounds the adversarially robust majority vote
First of all, since RD (H2) and Ap- (Ho) risks are not differentiable due to the indicator function, we propose use common surrogate in PAC-Bayes (known as the Gibbs risk): instead of considering the risk of the @-weighted majority vote, we consider the expectation over Q of the individual risks of the voters involved in H. In our case, we define the surrogates with the linear loss as
Macto)
RD RDo) =
E
1 1- E h
((x.)).)<D D
2
and AD (H²)
E (().)))))~
1- min
(y E REE h
Mote))
2
The next theorem relates these surrogates RD (Hl)), resp. for AD=(H leads to generalization bound for RD (H))), resp. AD=(HQ):
risks, implying that generalization bound for
Theorem 5. For any distributions D on (X xY)x and Q on H. for any n >> 1, we have
HD( < 2RD(H2),
and AD=)H2) s 2AD
5

---

Theorem below presents our PAC-Bayesiie generalization bounds for RD(Ho), Before that, it is important to mention that the empirical counterpart of (D(H is computed on S which is composed of non identically independently distributed samples, meaning that "classical" proof technique is not applicable. The trick here is to make use of a result of Raaaivola et al.) (2010) that provides chromatic PAC-Bayes bound, i.e., a bound which supports non -on-independent data.
Theorem 6. For any distribution D on (X (XxY)x BB, for any set of voters H. for any prior P on H. for any n, with probability at least 1-8 over S. for all posteriors Q on H. we have
+ m +++1
(I(Rs(H))) RD -
KL(Q)I))
(9)
5
1
m7 m+11
and (D S Rs (HH) +
KL(OIIP) + In
(10)
2m
8
where [H())))
1
m
12
1 3/ live
E h Morte))
mn
kl(allb)=aln f (1 In t and (L()))
E In hwp 2(1
P(h)
the KL-divergence between P and Q
Surprisingly, this theorem states bounds that do not depend on the number of perturbed examples but only the number of original examples m. The reason is that the perturbed examples
inter-dependent (see the proof in Appendix). Note that Equation ( is expressed as a SSeeerr [2022]
bound and is tighter but less interpretable than Equation (TO) expressed as a McAllester [9988
bound; These bounds involve the usual trade-off between the empirical risk Rs (H)) and KL(Q)
We now state a generalization bound for AD HQ). Since this value involves a minimum term, cannot the same trick for Theorem To bypass this issue, between two "artificial" distributions on &, Given ((I,, E,) E S, let т. be an arbitrary dis- tribution on E,, and given E H. let p be a Dirac distribution on &; such that (c)=1 al
the TV distance
e= argmaxx [1),(((tttet (i.e., if e is maximizing the linear loss), and 0 otherwise.
Theorem 7. For any distribution D on (X xx)xYxxX x B, for any set of voters H. for any prior P on H. for any n, with probability at least 1-ō over for all posteriors Q on H. for all i E {l,...,,m m) for all distributions T; on E, independent from voter h H. we have
(Do) <
1
E
m
max (1 (1-9:ho=+t))) E3E,
KL(Q|IP) In
2/m
(11)
m h~D
2m
< As HQ)
E TV(P)TT)) +
1
KL(Q]IP) + In 2ym
(12)
h~2
2m
where (H
1 m m
min
Vi E h(oett)) and (pl) = E love
plE)
<EE,
To minimize the true average-max risk AD=(HH) from Equation 11 have to minimize a trade-off between betweenKKLQQ) ((I)) (i.e., how much the posterior weights are close to the prior ones) and the empirical risk 1 @ En max,ce; (1 (c) However, to compute the empirical risk, the loss for
7n
each voter and each perturbation has to be calculated and can be time-consuming, With Equation (2) we propose an alternative, which be efficiently optimized using m Σ En~ TV (p (T) and
the empirical average- max risk As (H2). Intuitively, Equation 12 can be seen as a trade-off between the empirical risk, which reflects the robustness of the majority vote, and two penalization terms: the KL term and the TV term. The KL-divergence ( Ql(P) controls how much the posterior Q can differ from the prior ones P. While the TV term E, TV [[=;)) controls the diversity of the voters, i.e,, the ability of the voters to be fooled on the same adversarial example. From an algorithmic view, an interesting behavior is that the bound of Equation (12 stands for all distributions म; on E.. This suggests that given y1). we want to find n. minimizing Ex~o TV [m))) Ideally,

---

this term tends to 0 when Te is close to d and all voters have their loss maximized by the same perturbation e E..
To learn a well-performing majority vote, one solution is to minimize the right-hand side of the bounds, meaning that we would like to find good trade-off between a low empirical risk Rs (H)) or As(H)) and a low divergence between the prior weights and the learned posterior ones KL ([
4 Experimental evaluation on differentiable decision trees
In this section, we illustrate the soundness of our framework in the context of differentiable decision trees learning. First of all, we describe our learning procedure designed from our theoretical results.
4.1 From the bounds to an algorithm
We consider finite voters set H. consisting of differentiable decision trees Kontschieder al. 2016
where each / H is parametrized by weight vector w", Inspired by Masegosa et al. [2020] we
learn the decision trees of H. and a data-dependent prior distribution P from a first learning set S (independent from S); This is a common approach in PAC- B-yyess
et al. 2012
Lever al.) 2013 Dziugaite and Roy 2018 Dziugaite et al., [02T]. Then, the posterior distribution learned from the second learning set S by minimizing the bounds. This means we need to minimize the risk and the Kl.-divergence term. Our two-step learning procedure is summarized Algorithm [
Step 1. Starting from an initial prior Po and an initial set of voters Ho. where each voter la is parametrized by weight vector wh. the objective of this step is construct the hypothesis set H and the prior distribution P to give as input to Step 2 for minimizing the bound. To do so, at each epoch of the Step I, we learn from S' an "intermediate" prior Pe on an "intermediate" hypothesis set Hi consisting of voters h parametrized by the weights wh: Note that the optimization in Line 9 is done with respect to ( NEH. At each iteration of the optimizer, from Lines to 7, for each (Ir, y) of the current batch S attack the majority vote Hp, obtain perturbed example x+c. Then, in Lines and 9, we perform a forward pass in the majority vote with the perturbed examples and update the weights w, and the prior P, according to the linear loss. To sum up, from Lines 11 to 20 at the end of Step 1, the prior P and the hypothesis set H constructed for Step 2 are the ones associated to the best epoch t* E {l..... TT') that permits to minimize Rss, (Hp,). ). where S, y) (Ir,)) E E) is the perturbed set obtained by attacking the majority vote Hp,
Step Starting from the prior P on H and the learning set S, we perform the same process as in Step 1 except that the considered objective function corresponds to the desired bound to optimize (Line 30, denoted B (-)). ), For the sake readability, we deferred in Appendix G the definition of (-)) for Equations (9) and 12 Note that the "intermediate" priors do not depend on S, since they are learned from S: the bounds are then valid.
4.2 Experiments
In this section, we empirically illustrate that our PAC-Bayesian framework for adversarial robustness is able to provide generalization guarantees with non-vacuos bounds for the adversarial risk.
Setting. We stand in white-box setting meaning that the attacker knows the voters set H. the prior distribution P. and the posterior one Q. We empirically study attacks with the fg-norm and l. -no-morm the Projected Gradient Descent (PGD, Madry et al. (2018)) and the iterative version of FGSM (IFGSM, Kurakin et al. (2017). We fix the number of iterations at k=20 and the step size at ī for PGD and IFGSM (where 6=1 for f2-norm and b=0.1 for foo -nom)) One specificity of our setting is that we deal with the perturbation distribution w'rr,)). We propose PGDu and IFGSMy, two variants of PGD and IFGSM. To attack an example with PGDg or IFGSMy we proceed with the following steps: (I) We attack the prior majority vote Hp with the attack PGD IFGSM: we will obtain first perturbation e' (2) We sample n uniform noises 17....., The between -10 - and +10 2 2; (3) We set
Note that, since p is a Dirac distribution, we have T. TV [
1 - T. म. (c R. Eejg ((())
with ef = argmax.es, [[ [[=,,l(x;++]]..
'The source code is available at https: http:////wh.hh..o//aaa//aaaaaaaa
Roobuustnees
7

---

Algorithm/ 1 Average Adversarial Training with Guarantee
Require: S, disjoint learning sets - T number of epochs Po: initial prior Ho (with wo): initial hypothesis set attack(): the attack function B-)) the objective function associated to bound Step 2 - bound minimization
Step 1- prior and voters' set construction
1: for from to T do
21:
(P. H) + Output of Step 1
2: P and H (wi+-wi-1)
22:
2o --p
3:
for all batches S (from 8') do
23:
for from 1 to T' do for all batches S (from S) do
4:
for all (z, y) E S' do
24:
5:
(x+e, v) attack(r,
25:
Q 6- Q1-1
6:
S' s ((z,,))) U ((++,,)))
26:
for all (z. y) E E do
7:
end for
27:
(x+c, y) attack(r, y)
8:
Update P. with Vp, Roy Hp,)
28:
S (S v(), U ((x+e,
9: Update we with Vw, Rg Hp,)
29:
end for
10:
end for
30: Update 2r with o Bs (
11:
S. -
31: end for
for (z, do
32: S. 5
13:
(x+t,, t- attack((r v)
33: for all (z, 9) E S
14:
S. S S, ((x+te)))
34: (x+e, + attack(r,))
15:
end for
35: S S, ((x+cyy)
16:
t" argmin (1.,.....))) Rs (Hp.)
36: end for
17:
P P.-
37:
argmin Bs, (Ho.)
18:
H + Hr-
38: Q Qr
end for
39: end for
20:
return (P,H)
40: return (Q, H)
the i-th perturbation as E; é' Tj. Note that, for PGDy and IFGSMu, after one attack we end up with n=100 perturbed examples. We set n-1 when these attacks are used as a defense mechanism in Algorithm
M Indeed since the adversarial training iterative, we do not need to sample numerous perturbations for each example: we sample a new perturbation each time the example is forwarded through the decision trees. We also consider a naive defense referred to as UNIF that only adds a noise uniformly such that the E,- -n-norm of the added noise is lower than b.
We study the following scenarios of defense/attack. These scenarios correspond to all the pairs (Defense, Attack) belonging to the set {-, UNIF, PGD, IFGSM] x (-, PGD, IFGSM) for the baseline, and {-, UNIF, PGDr, IFGSMy] x (-- PGDy, 1FGSMy), where " means that we do not defend, i.e., the attack returns the original example (note that PGDu and IFGSM when "Attack without U" refers to PGD and IFGSM for computing the classical adversarial risk 18 ()).
Datasets and algorithm description. We perform our experiment on six binary classification tasks from MNIST [LeCun et al. [998] (Ivs7, 4vs9, 5vs6) and Fashion MNIST [Xiao et al.) 2017] (Coat vs Shirt, Sandal vs Ankle Boot, Top vs Pullover). We decompose the learning set into two disjoint subsets S' of around 7, 000 examples (to learn the prior and the voters) and S of exactly 5, 000 examples (to learn the posterior). We keep as test set T the original test set that contains around 2, 000 examples. Moreover, we need a perturbed test set, denoted by T, to compute our averaged adversarial risks. Depending on the scenario, T is constructed from T by attacking the prior model Hp with PGDy or IFGSMy with n=100 (more details are given in Appendix). We our Algorithm T for Equation g (Theorem 6). respectively Equation (12) (Theorem 7. and we compute our risk RT (H2)) respectively AT HH)), the bound value and the usual adversarial risk associated to the model learned R8p0 (Ho).. Note that, during the evaluation of the bounds, we have to compute our relaxed adversarial risks Rs (HO) and As (Ho) on S. For Step 1. the initial prior Po is fixed the uniform distribution, the initial set of voters Ho is constructed with weights initialized with Xavier Initializer [Glorot and Bengio 2010 and bias initialized at O (more details are given in Appendix). During Step 2, to optimize the bound, we fix the confidence parameter 5-0.05, and we consider as the set of voters H two settings: H. as it is output by Step 1, and the set HSSGG = (!((.) = sign (I())) h E H} for which the theoretical results are still valid (we will see that in this latter situation we are able to better minimize the TV term of Theorem 7 For the two steps, we use Adam optimizer (Kingma and Ba. 2015 for T=''=20 epochs with a learning rate at 10-2 and batch size at 64.
8

---

Table 1: Test risks and bounds for MNIST 1vs7 with n=100 perturbations for all pairs (De fetse,Attack) with the two voters' set H and HSION. The results in bold correspond to the best values between results for H6 and H To quantify the gap between our risks and the classical definition we put in italic the risk of our models against the classical attacks: we replace PGDu and IFGSMy by PGD or IFGSM (i.e., we did not sample from the uniform distribution). Since Eq. 12
upper-bounds Eq. T thanks to the TV term, we compute the two bound values of Theorem
Fg norm b=1
Algo
with Eq.
Algo
with Eq.
P2
Atuck witheus (H2)
Attack R7 (Hg)
Ry (Hz)
Th. G
Ar(Ha)
Th.
Eq.
12
Th.
Eq.
Defense
Attack
H
H
H
F(
76
H
7
005
.005
.005
.005
.017
.019
.005
.055
.005
.005
.099
0.100
.099
.100
PGDU
.245
255
.263
.276
.577
.448
.315
.313
.325
326
.801
1.667
684
.515
1PGSMg
.96
.80
.185
.106
.356
.2%
UNIF
022
.015
005
.015
.018
.019
.005
0025
.015
005
.999
0.100
.099
.100
UNIF
PGDμ
.146
.58
.292
.190
.531
1.620
.454
UNIF
063
.961
.031
.035
.088
.14
.071
.970
.U56
.054
.248
1.405
2000
.186
PODE
.006
.007
.066
.623
022
.066
TV77
.0666
TX77
.102
D.TO3
.102
.TO
PGDF
PGDμ
.028
.030
.021
.025
0165
.064
.028
.029
.025
028
.143
1.389
.137
.136
PGDj
IPGSM
.022
0045
.018
.125
1.362
MUGSMu
.006
.007
.906
.007
.019
021
.006
.07
.006
.077
.100
0.102
.100
.102
.040
.047
.033
.035
.086
.094
.040
.0:39
.040
.0.38
.184
1.368
.666
.163
IPGSMg
JFGSMg
.021
.022
.013
.014
.039
.049
.021
.022
.018
.021
.131
1.329
.122
.123
(remy pons)
(1aat) aro. grosste
LurcsN pobe?
mecost (NTF
UNEE Fun
(UNEE
(POD)
(UNER
HSION
H
Figure 1: Visualization of the impact of the TV term in Equation 12 The left, respectively the right, bar plot show the bounds for the set of voters HSIGN respectively H. We plot the bounds for all the scenarios of Table I that use the TV distance, i.e., all except the pairs (-, -). In orange we represent the value of the TV term while in blue represent all the remaining terms of the bound.
Analysis of the results. For the sake of readability, we exhibit the detailed results for one task (MNIST: Ivs7) and all the pairs (Defense,Attack)) with f--norm in Table D and report in Figure [ the influence of the TV term in the bound of Theorem / (Equation (12)) The detailed results on the
overview of the results we obtained on all the tasks for the pairs (Defense,Attack, where ADttckse=Attack" and with HSsaN
other tasks are reported in Appendix; We provide in Figure
First of all, from Table the bounds of Theorem 6 are tighter than the ones of Theorem this is an
expected result since we showed that the averaged- max adversarial risk AD (2)) is more pessimistic than its averaged counterpart RD (He). Note that the bound values of Equation 1 are tighter than
the ones of Equation 12 This is expected since Equation (I]) is a lower bound on Equation (12).
Second, the bounds with HSSGGN are all informative (lower than 1) and give insightful guarantees for our models. For Theorem 7 (Equation (2)) with H. while the risks are comparable to the risks obtained with HSIGN, the bound values are greater than 1, meaning that we have no more guarantee on the model learned. As we can observe in Figure D this is due to the TV term involved in the bound. Considering HSIGN when optimizing (-)) helps to control the TV term. Even if the bounds are non-vacuous for Theorem 6 with H. the best models with the best guarantees are obtained with HSIGN This is confirmed by the columns (11g) that are always worse than (Tl)))) and mostly worse than Ar HQ) with HSIGN The performance obtained with HSIGN can be explained by the fact that the sign "saturates" the output of the voters which makes the majority vote more robust to noises. Thus, we focus the rest of the analysis on results obtained with HSINN
Third, we observe that the naive defense UNIF is able to improve the risks RT and AT (H)), but the improvement with the defenses based on PGDy and IFGSMG is much more significant specifically against PGDU attack (up to 13 times better). We observe the same phenomenon for both bounds

---

COvhh
Fashion SAvaBO
Fashion:TovaPe
1s7
MNIST:4v29
5v56
R (HQ)
0.0
0.1
0.2 0.3 0.0
0.2
0.80,0
0.1
0.2
0.3
0.0
0.4
0.6 0.8
Rr (H))
Bound of Theorem 6
Ar HQ)
Bound of Equation
Figure 2: Visualization of the risk and bound values when "Defense=Attack" when the set of voters is H Results obtained with the PGDu, respectively IFGSMr. defense are represented by a star *. respectively a circle (reminder: I2 (H₂) is computed with PGD, rexpectively IFGSM, atlack). The dashed line corresponds to bisecting line y=r. For Rr( Hg) and AT H2), the closer the datasets are the bisecting line, the more accurate our relaxed risk compared the classical adversarial risk R808 (Ho). For the bounds, the closer the datasets are to the bisecting line, the tighter the bound.
(Theorems 6 and 7 This is an interesting fact because this behavior confirms that we are able to learn models that are robust against the attacks tested with theoretical guarantees.
Lastly, from Figure Table [ is important to notice that the gap between the classical risk and relaxed risks is small, meaning that our relaxation not too optimistic. Despite the pessimism of the classical risk (Ho), it remains consistent with our bounds, i.e., it is lower than the bounds. In other words, in addition to giving upper bounds for our risks RT (Hq) and Ar give non-vacuous guarantees on the classical risks RBBB (H2).
Ar(Ho) (HQ), our bounds
5 Conclusion
To the best of our knowledge, our work is the first one that studies from general standpoint adversarial robustness through the lens of the PAC-Bayesian framework. We have started by formalizing new adversarial robustness setting (for binary classification) specialized for models that can be expressed as a weighted majority vote; we referred to this setting as Adversarially Robust PAC-Bayes. This formulation allowed us to derive PAC- -AC-saaesi generalization bounds on the adversarial risk of general majority votes. We illustrated the usefulness of this setting on the training of (differentiable) decision trees. Our contribution is mainly theoretical and it does not appear to directly lead to potentially negative social impact.
This work gives rise to many interesting questions and lines of future research. Some perspectives will focus extending our results to other classification settings such multiclass multilabel. Another line of research could focus on taking advantage of other tools of the PAC-Bayesian literature. Among them,
make of other bounds on the risk of the majority vote that take into consideration the diversity between the individual voters; For example, the C-bound [Lacasse et al., 2006), or more recently the tandem loss [Masegosa et al., 2020). Another very recent PAC-Bayesian bound for majority votes that needs investigation in the case of adversarial robustness is the one proposed by Zantedeschi et al. [202T] that has the advantage be directly optimizable with the 0-1 loss. Last but not least, in real life applications, one often wants to combine different input sources (from different sensors, cameras, etc). Being able to combine these sources in an effective way then key issue. We believe that our new adversarial robustness setting can offer theoretical guarantees and well-founded algorithms when the model we learn is expressed as a majority vote, whether for
ensemble methods with weak voters [e.g. Roy et al. 201T Lorenzen et al. 2019 or for fusion of
classifiers [e.g. Morvant et al. 2014 or for multimodal/multiee learning [e.g. Sun et al. 2017
Goyal et al. 2019].
10

---

Acknowledgments and Disclosure of Funding
This work was partially funded supported by the French Project APRIORI ANR-I8 18- 10--88--CHE CE23-0015. G. Vidot is supported by the ANRT with the convention "CIFRE" Nº2019/0507. We also thank all anonymous reviewers for their constructive comments, and the time they took review our work.
References
Nicholas Carlini and David Wagner. Towards Evaluating the Robustness of Neural Networks. In IEEE Symposium Security and Privacy, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified Adversarial Robustness via Randomized Smoothing. In ICML, 2019.
Gintare Karolina Dziugaite and Daniel Roy. Data-dependent PAC-Bayes priors via differential privacy. In NeurIPS, 2018.
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in PAC-Bayes. AISTATS, 2021.
Farzan Farnia, Jesse Zhang, and David Tse. Generalizable Adversarial Training via Spectral Normal- ization. In ICLR, 2019.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. A12: Safety and Robustness Certification of Neural Networks with Abstract Interpretation. In IEEE Symposium on Security and Privacy, 2018.
Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy. Risk Bounds for the Majority Vote: From PAC-Bayesian Analysis to Learning Algorithm. JMLR, 2015.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, 2010.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. In ICLR, 2015.
Anil Goyal, Emilie Morvant, Pascal Germain, and Massih-Reza Amini. Multiview Boosting by Controlling the Diversity and the Accuracy of View-specific Voters. Neurocomputing. 2019.
Dan Hendrycks and Thomas Dietterich. Benchmarking Neural Network Robustness to Common Corruptions and Perturbations. In ICLR, 2019.
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety Verification of Deep Neural Networks. CAV, 2017.
Xiaowei Huang, Daniel Kroening, Wenjie Ruan, James Sharp, Youcheng Sun, Emese Thamo, Min Wu, and Xinping Yi. A survey of safety and trustworthiness of deep neural networks: Verification, testing, adversarial attack and defence, and interpretabiliity. Computer Science Review, 2020.
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. CAV, 2017.
Justin Khim and Po-Ling Loh. Adversarial Risk Bounds for Binary Classification via Function Transformation. CoRR, 2018.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In ICLR, 2015.
Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Buld. Deep Neural Decision Forests. In IJCAI, 2016.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial Machine Learning at Scale. In ICLR, 2017.

---

Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usunier. PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier, In NIPS, 2006.
Yann LeCun, Corinna Cortes, and Christopher Burges. THE MNIST DATASET of handwritten digits, 1998. URL htttp://yann.eeaun www.uam.ccooeeeeeeeeeeeeee www.coommeeeeeeee wewe/edddmnssseeeeeeeeeeeeedmsie
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter PAC-Bayes bounds through distribution-dependeer priors. Theoretical Computer Science, 2013.
Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. On PAC-Bayesiae bounds for random forests. Machine Learning. 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks, In ICLR, 2018.
Andrés Masegosa, Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. Second Order PAC-Bayesian Bounds for the Weighted Majority Vote. In NeurIPS, 2020.
David McAllester. Some PAC-Bayesian Theorems. In COLT, 1998.
Omar Montasser, Steve Hanneke, and Nathan Srebro. VC Classes are Adversarially Robustly Learnable, but Only Improperly. In COLT, 2019.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Reducing Adversarially Robust Learning to Non-Robust PAC Learning. In NeurIPS, 2020.
Emilie Morvant, Amaury Habrard, and Stéphane Ayache. Majority Vote of Diverse Classifiers for Late Fusion. In S+SSPR, 2014.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain generaliza- tion in deep learning. In NeurIPS, 2019.
Yuki Ohnishi and Jean Honorio. Novel Change of Measure Inequalities with Applications to PAC- Bayesian Bounds and Monte Carlo Estimation. In AISTATS, 2021.
Nicolas Papernot. Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The I. Limitations of Deep Learning in Adversarial Settings. In IEEE EuroS&P. 2016.
Emilio Parrado-Hente Hernández, Amiran Ambroladze, John Taylor, and Shiliang Sun. PAC-bayes bounds with data dependent priors. JMLR, 2012.
Liva Ralaivola, Marie Szafranski, and Guillaume Stempfel. Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary B-Mixing Processes. JMLR, 2010.
David Reeb, Andreas Doerr. Sebastian Gerwinn, and Barbara Rakitsch. Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds. In NeurIPS, 2018.
Kui Ren, Tianhang Zheng, and Xue Liu. Adversarial Attacks and Defenses in Deep Learning. Engineering, 2020.
Jean-Francis Roy, François Laviolette, and Mario Marchand. From PAC-Bayes Bounds to Quadratic Programs for Majority Votes. In ICML, 2011.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. In NeurIPS, 2019.
Edward Scheinerman and Daniel Ullman. Fractional Graph Theory: A Rational Approach to the Theory of Graphs. Courier Corporation, 2011.
Matthias Seeger. PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification. JMLR, 2002.
John Shawe-Taylos and Robert Williamson. A PAC Analysis of Bayesian Estimator. COLT, 1997.
12

---

Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. Boosting Robustness Certifica- tion of Neural Networks. In ICLR, 2019.
Shiliang Sun, John Shawe-Taylor, and Liang Mao. PAC-Bayes analysis of multi-view learning. Inf. Fusion, 2017.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-Margin Training: Scalable Certifica- tion of Perturbation Invariance for Deep Neural Networks. In NeurIPS, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Rashion-MNISTY Novel Image Dataset for Bench- marking Machine Learning Algorithms. CoRR. 2017.
Dong Yin, Kannan Ramchandran, and Peter Bartlett. Rademacher Complexity for Adversarially Robust Generalization. ICML, 2019.
Valentina Zantedeschi, Maria-Irina Nicolae, and Ambrish Rawat. Efficient Defenses Against Adver- sarial Attacks. In ACM Workshop Artificial Intelligence and Security, AlSec CCS, 2017.
Valentina Zantedeschi, Paul Viallard, Emilie Morvant, Rémi Emonet, Amaury Habrard, Pascal Germain, and Benjamin Guedj. Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound. In NeurIPS, 2021.
13


Reviews:
[{"review_id": "ei4Xug6LH5c", "reviewer": "Reviewer_y2sg", "summary": "The paper studies robust generalization using the PAC-Bayes framework. Specifically, the authors establish bounds on relaxations of the worst-case adversarial risk. In the first relaxation (Theorem 6), they are concerned with the average-risk with respect to a distribution over adversarial distributions (instead of worst-case). The second relaxation (Theorem 7), is concerned with an average-max risk, where instead of drawing a single adversarial perturbation, n adversarial perturbations are drawn and then the worst-case among them is counted. The authors also provide a bound on the gap between their relaxations and the worst-case adversarial risk (Proposition), which depends on the total-variation distance between the fixed distribution and the worst-case. \n\nThe authors also ran empirical experiments with an adversarial learning procedure that is inspired by the theoretical bounds.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Applying Bac-Bayes analysis to obtain robust generalization bounds is new and hasn’t been considered in prior work to the best of my knowledge. However, what is concerning is the fact that the bounds established are on relaxations of the worst-case adversarial risk. \n\nThe authors do not provide strong justification for why such relaxations are considered, e.g., is it the case that the analysis breaks down when studying the worst-case adversarial risk? \n\nWhile the relaxations may still be useful, I am not totally convinced of that yet. For example, the total-variation distance in Proposition 4 can be arbitrarily large, and will really depend on how good the choice of distribution D is. Even though the authors empirically show that the gap is small on datasets of MNIST and Fashion-MNIST, I am not sure if these are appropriate datasets to compare the gap between the relaxations and the worst-case since they are in a sense \"easy\" datasets that we can train robust models against.\n\nCan the results in Theorems 6 and 7 be extended to obtain generalization guarantees against a specific attacking algorithm? For example, what if in distribution D the adversarial perturbations are generated by the PGD attack. The challenge that I see is that in this case the distribution over adversarial perturbations will depend on the specific predictor/classifier that is being attacked. But this is really what is sort of happening in the experiments in Section 4. Where a prior P_0 is chosen, then distribution D over adversarial perturbations is determined as a function of this prior (and PGD attack), then a posterior Q_0 is learned, then this is repeated again with prior P_1=Q_0, and so on. It would be nice if the theoretical guarantees in Theorems 6 and 7 can be extended to capture this dynamic.\n\nIn Section 4.2, I believe that including the simple baseline of adversarial training with a single classifier (compared to a majority-vote) would be useful. Also, how is the majority-vote predictor attacked? It would be good to include details of this.\n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nAfter Rebuttal. \n\nI thank the authors for their response. After consideration, I decided to keep my score the same.\nI do think that this would be a stronger contribution if perhaps the authors could strengthen their results in Theorems 6 and 7 to obtain generalization guarantees against specific attacking algorithms. This would be one way to show case the usefulness of considering the PAC-Bayes framework, and the relaxations to adversarial risk considered in this work. \n\nWhile the authors comment in their response that this is possible, I am not fully sure that it follows immediately, and perhaps some care is needed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, the authors have adequately addressed the limitations of their work. Also, while it is true that the work is mainly theoretical, the authors should address how their theoretical guarantees can impact society.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dIo1Jw7o0b", "reviewer": "Reviewer_KAbu", "summary": "The paper studies the adversarial robustness of the majority vote method by deriving PAC-Bayesian generalization bounds in the adversarial settings.\nIn details,  the adversarial robustness means that an algorithm can still work well when the input covariates \"X\" is adding some noise but not the labels \"Y\".\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper, itself, introduces two novel definitions for (and relates to) the classical adversarial risk, which are \"Averaged adversarial risk\" and \"Averaged-max adversarial risk\".\nPAC-Bayesian empirical bounds are derived with respect to these two risks for the \"surrogates linear loss\" of the weighted majority vote. \nAn algorithm is also given by minimizing these empirical bounds and some applications to real data sets are given to illustrate the soundness. \n\nAlthough the used Pac-Bayesian bound technique in this paper is known, the settings considered is novel. Thus, I believe these theoretical results are an important contribution.\n\nHowever, my main concern is that: \nAs in Theorem 6, the authors noted that the result does not depend on \"n\". \nWhile Theorem 7 is stated for all 'n', So, could you compare these bounds?\n\nOther comments:\n1. (line 15-17) any reference for this claim? \"This phenomenon known as adversarial robustness contributes to the impossibility to ensure the safety of machine learning algorithms for safety-critical applications such as aeronautics functions (e.g., vision-based navigation), autonomous driving or medical diagnosis.\"\n2. (line 19) is badly written, I can not understand this \"...of its input; We talk about adversarial examples. In other words, .......\"\n3. (line 74) \"The learner objective is then to....\" should be \"The learner's objective.....\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Z4Qf4VpkrtE", "reviewer": "Reviewer_N9WH", "summary": "This paper provides a PAC-Bayes analysis of adversarial robustness. In opposite to standard techniques that derive a worst-case analysis of the risk over all the possible perturbations, the authors use PAC-Bayes bounds to design a learning algorithm that minimizes an adversarial risk. They also provide numerical evidence to support their theoretical results.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clear and well written, and the theoretical analysis is sound, and technically quite solid. These are nice results. I enjoyed the idea of using PAC-Bayes to analyze adversarial robustness and obtain theoretical guarantees on the adversarial risk. However, I'm not convinced that in general, considering the averaged-risk can really help much for adversarial attack as it is generally a classifier- and sample-dependent risk.\n\nI enjoyed the experimental section as well. However, a point that I do not understand (and that I think quite important as the aim of PAC-Bayes is to provide a learning algorithm through the bound) is why the authors do not optimize the TV distance in the bound. They say in the supplementary material that \"this term is 0 when we sample one noise for each example\", but this is not a requirement, and the TV distance is a key quantity in the bounds of the authors, specific to their analysis. Also, I would have liked seeing experiments on more complicated datasets like CIFAR-10.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No specific societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "1hLDfo6hdkh", "reviewer": "Reviewer_Jhjk", "summary": "This paper studies the problem of robustness to evasion attacks from a learning theory point of view. Unlike most existing works from the literature, the authors do not study the uniform bounds on the worst-case risk under attack (a.k.a. adversarial risk). Instead they introduce a new analytical framework that considers less powerful randomized adversaries and majority vote classifiers.  This new setting allows them to leverage existing results from the PAC-Bayes literature; hence providing generalization bounds on the averaged risk under attacks of a majority vote classifier (where the average is taken over the randomness of the adversary). ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Relevance: The topic of evasion attacks is still lacking some theoretical ground. Accordingly, presenting new theoretical results to this community is an interesting and relevant line of research.\n\nClarity: The paper is well written and understandable. Nevertheless I feel like some statements (listed below) lack justification or at least were not perfectly clear to me.\n- In line 44. The authors say that their definition has the advantage of being suited to majority voting. While I agree with this statement, it is unclear to me why previous definitions were not. Indeed, I can always define my hypothesis space as being a set of classifiers that have been constructed by majority voting, which allows me to apply every classical definition from adversarial learning theory (including adversarial risk). Did I misunderstood something here? \n- In line 46. The authors claim that their bounds are independent from the kinds of attacks they consider. However, it seems to me that the attack they consider does have an impact in the bound presented in Theorem 7. Indeed the TV term depends on $\\mathcal{E}_i$ which is directly sampled from $D$ (i.e., the distribution characterizing the set of randomized attacks considered).\n- In lines 208-209. It was a bit unclear to me what the TV term in Theorem 7 stands for. The authors state that this term goes to $0$ when the voters are fooled by the same attack $\\epsilon \\in \\mathcal{E}_i$, but such a setting seems counterproductive to me. If all the classifiers are fooled by the same attack, then I don’t see how building majority vote classifiers with them will bring robustness to the system. \n- In line 249, the authors present their randomized adaptation of $PGD$ and $IFGSM$ attacks, namely $PGD_U$ and $IFGSM_U$. I felt like the definition of these new attacks was a bit confusing. More precisely, it was a bit unclear to me whether the uniform noise was injected before performing the attack or after (i.e., directly adversarial example computed with $PGD$ or $IFGSM$). I think it is the latter, but to make this clearer, the author could present these attacks a bit more formally (only one line explaining where the uniform noise is injected). \n\nQuality: The technical part of the paper looks sound to me. The main issue I have with this part is that it does not clearly relate to the problem of adversarial examples usually considered by the ML community. In general, in the problem we are interested in (even for a fixed model and not a class of models), we study a worst-case scenario, i.e., if the attacker can find the solution to (5). Here the authors consider a much weaker model where the attacker can only select the best attack from a fixed-size set of random points. While the authors claim that their definition can be connected to the classical problem (Propositions 3 and 4), this connection seems quite loose to me and not very informative. Indeed, as there is no concrete values for $TV(\\Pi,\\Delta)$, the left-hand term in (8) could be arbitrarily small. I think it would have been much more convincing to present a connection that depends on the number of samples one considers, not only an inequality like in Proposition 3, but a true dynamic depending on $n$ and $D$. \n\nSimilarly, I think the experimental part of the paper was not convincingly illustrating the connection between the adversarial risk and the averaged risks the paper introduces. The authors are only studying an empirical version of the adversarial risk, that has been calculated using a specific attack (that might as well be suboptimal). Accordingly, I don’t think that the author should claim to provide non-vacuous bound on the adversarial risk. On the randomized attack part, if my understanding of the adversarial attack $PGD_U$ and $IFGSM_U$ is right, I think these attacks are suboptimal. In fact, there is no clear reason to me why injecting uniform noise on an existing attack could provide stronger examples. To consider randomized attacks in a stronger scenario, I suggest that the author uses random restart instead (i.e., inject the uniform noise before computing the attack) which is a well-known technique to improve the efficiency of PGD and IFGSM. More generally, the authors could strengthen the experimental protocol by following some good practices to guarantee that the attacks have been correctly computed (see e.g. [1]).\n\nOriginality: To the best of my knowledge, this work is the first one to consider adversarial robustness through the lens of the PAC-Bayes Learning. Nevertheless, I feel like the authors failed to compare with (or at least to discuss) some important lines of research that are connected to the present work. \n- The classifiers considered in the paper are built by a majority voting rule as $\\text{sign}(E_{h\\sim\\mathcal{Q} }[h(x)])$. This formulation is very similar to certifiable defenses based on randomized smoothing (see e.g. [3,4]). Let us for example consider a real-valued hypothesis $h$, and $h_\\delta$ the function defined as $h_\\delta(x) := h(x+\\delta)$. Let us also set $\\mathcal{Q}$ to be the distribution that samples $\\delta$ from a Gaussian distribution $\\mathcal{N}(0,\\sigma^2)$ and outputs $h_\\delta$. Then $\\text{sign}(E_{h\\sim\\mathcal{Q}}[h(x)])$ reduces to applying randomized smoothing with Gaussian noise $\\mathcal{N}(0,\\sigma^2)$. Accordingly, it would be interesting if the author could explain how these techniques differ from theirs, if their bounds are applicable to randomly smoothed classifiers and how their bounds can be compared to the certificates presented in previous works. \n- One of the originality of this paper is to consider randomized attackers. In this context, it could be interesting to compare to some recent theoretical works (see e.g. [4,5] ) investigating adversarial robustness from a distributional point of view (i.e., where the attacker can be random).\n\n[1] Florian Tramèr, Nicholas Carlini, Wieland Brendel, Aleksander Madry. On Adaptive Attacks to Adversarial Example Defenses. NeurIPS 2020. \n\n[2] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. ICML 2019.\n\n[3] Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, Sebastien Bubeck. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. NeurIPS 2020.\n\n[4] Muni Sreenivas Pydi, Varun Jog. Adversarial Risk via Optimal Transport and Optimal Couplings. ICML 2020.\n\n[5] Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, Yann Chevaleyre. Mixed Nash Equilibria in the Adversarial Examples Game. ICML 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don’t see any possibly negative social impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 to 8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The author(s) provide the 1st PAC-Bayes bounds proving robust generalization in the context of adversarial robustness. The risk they consider is not the usual "worst-case adversarial risk", but randomized versions (or relaxations), that imply a less powerful adversary. Two versions are considered: Theorem 6 is a bound on an average risk with respect to the distribution on the adversary, while Theorem 7 considers the worst case of n random attacks.

The paper relies on standard PAC-Bayes techniques, but they are applied to a new setting: adversarial robustness. Given the lack of theoretical results in this setting, all Reviewers agree that such results are potentially very interesting.

On the other hand, the relaxations studied in Theorem 6 and Theorem 7 are not standard in the literature on adversarial robustness. Three Reviewers: y2sg, Jhjk and N9WH, questioned these definitions and expressed doubt that they would be of interest to researchers in the field of adversarial robustness. The discussion allowed some clarifications, but overall, it remains clear that, while these results are new, the authors failed to convince that they will be useful for the community of adversarial robustness.

For this reason, I recommend to reject the paper. I encourage the author(s) to work on a new version of the paper, but you should either work on the worst-case risk, or explain to what extend the average risks they introduce is related to the worst-case risk. You should also take into account the typos found by Reviewer KAbu and the many comments of Reviewer Jhjk. I wish you good luck with the revision of the paper.
Decision: Accept (Poster)