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 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
originals (i.e., with
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= (1 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-basee
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 a 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 X 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 are 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 betweenKLLQQ) ((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.h...o//aaa//aaaaaaaa
Roobuustness
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, 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 a 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
022
.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) grosste
LurcsN pobe?
mecost (NTF
UNEE Fun
(UNER 31
(UNEE
(POD)
HSION
H
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.
Figure 1: Visualization of the impact of the TV term in Equation 12
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 "Dttckse=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

---

COshh
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 Ar(Ho) (HQ), our bounds give non-vacuous guarantees on the classical risks RBBB (H2).
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.eecun 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": "m8Ot5dG3w5", "reviewer": "Reviewer_mbWu", "summary": "Adversarial examples are test time attacks on machine learning models that add small imperceptible noise to examples with the goal of having them misclassified. This paper studies the problem in the \"PAC-Bayes\" framework where the learner produces a distribution Q over the models (and some way of combining their decisions) and generalization bounds are produced based on picking some priori distribution P (perhaps based on the instance distribution D) to derive generalization bounds. The novel part is the PAC-Bayes form, as the final proved results are either for random noise or are “conditional” and depend on some parameters that are not quite clear how to bound (see my comments below).", "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 adversarial examples is a worst-case phenomenon where the noise can completely depend on the instance x (or even its true label y) and the produced model h. This paper’s approach is to first consider an average case noise where eps (the onise) is a random variable only depending on the instance x. Then, it considers a “strengthening” of this noise that allows sampling it n times and picking the one that gives the worst loss (based on hte model h). It is easy to see that when n goes to infinity, the n-sampled version converges to worst-case adversarial noise (assuming they have the same support set). So the paper uses this connection and provides some generalization bounds in the form of PAC Bayes for the random noise and n-sample noise. The bounds relate the generalization error of the “Q majority based” classifier to its KL divergence from an a priori distribution P -- that can in turn be selected based on the distribution D to get a good bound on the error.\n\nOne issue is that the generalization bounds are either for random noise (that does not depend on the “model” or “model ensemble”) or have extra terms that are hard to interpret (see my comments below). Moreover, since the results of the paper use an “ensemble model” where majority is taken, it is in spirit similar to recent (not cited) results that use Boosting style techniques for getting generalization bounds for adversarially robust learning. See:\nhttps://arxiv.org/abs/2010.12039\nhttps://arxiv.org/abs/1902.04217\n\nThe paper also presents some experiments for particular models, and it shows robustness achieved against specific attacks. Note that this is not really a proof that the employed methods are robust, as that can only happen using a “complete” attack or proofs, and the experiments are more like weak evidence that the methods of the paper can potentially be used to obtain generalization for adversarial setting.\n\nEvaluation: On the down side, the generalization bounds still do not resolve the main question (as explained above) but they are a step in a new interesting direction. Assuming that the authors can provide a good comparison of their results with the two papers above I can see it being accepted.\n\nComments:\n\nBeginning of Section 4, it says “we illustrate the soundness of our framework”. But I am not sure exactly what it means. In addition to giving the details of the experiment and the numbers, the paper lacks a high level discussion of how the experiments relate to the theory section and how their results should be interpreted.\n\nLine 114: “of existing works comes either without theoretical guarantee or with very specific theoretical justifications. ” \nAs mentioned above, there is actually some progress on the theory side that needs to be cited and compared with.\n\nLine 15: “This phenomenon known as adversarial robustness” maybe here it is more suitable to be called adversarial vulnerability. Robustness is the opposite.\n\nLine 38: “adversarial robust PAC-Bayes.” it seems “adversarially robust” is more accurate.\n\nLine 73: it seems the definition of B is not quite accurate, because what is important is that x+\\eps belongs to X (not eps).\n\nLine 130: the sentence needs to be rewritten.\n\nLine 137: B^n at the end of the line needs correction: the whole thing (including B^n) needs to be raised to power m.\n\nLine 138: notation D^n was already defined for a different thing (product distribution) and hence should be avoided!\n\nMany definitions, claims and results are written for H_Q while they hold for any randomized classifier. This is a matter of taste, but maybe it is better to state them in the simpler sense for any randomized verifier h. In particular, Theorem 5 looks like a new theorem while the relation between this surrogate loss and its original variant is a simple (well known) fact that does not have to do with H_Q being a majority-based model.\n\nWhy is A also defined for risk? Why not use the letter R again?\n\nLine 193 and 194: the sentences are not clear and might need to be clarified.\n\nTheorem 7: how should we interpret the term TV(rho_i,pi_i)? How trivial/nontrivial does it make the inequality? This seems to be the term that needs to go away to get a meaningful generalization result?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No direct societal impact, and the long term impact is positive.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Nc-m5SQtONI", "reviewer": "Reviewer_YUnr", "summary": "This paper studies the generalization of adversarial error in the context of PAC-Bayes. Interestingly, the authors obtain generalization bounds that are independent of the type and budget of perturbations. These bounds are obtained for majority-based classifiers in the PAC-Bayes framework. Further, the authors use the results to optimize the obtain generalization bound for an ensemble of decision trees and they show that their method is actually effective and can provide non-vacuous bounds.\n\n\n", "questions": "", "limitations": "", "rating": 7, "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 studies the generalization gap of adversarial risk for majority-based classifiers. Namely, we have hypothesis class H, and a prior distribution P, and a posterior distribution Q. Then, the goal is to find ou the maximum difference between empirical, adversarial risk, and population adversarial risk for such a classifier based on the deviation of Q from P.\n\n\nThe authors take the following steps:\n\n1- [Definition 2] They first define a new notion of advRisk_n that is something between random noise and adversarial noise. This definition samples n perturbations from a noise distribution (that could depend on the original point, but not the classifier in hand) and then takes the maximum of loss over all those perturbations. \n\n2- [Theorem 7] They provide an upper bound on the difference between empirical adversarial risk and the population adversarial risk using the PAC-Bayes framework. Their generalization gap depends on the KL divergence of P and Q, the sample complexity, and another non-standard term which deals with the entropy of the worst-case adversarial examples on different classifiers. Their theorem is interesting in that it does not depend on n, which means you can get the limit in the infinity without the theorem changing much. Their bound is also independent of the type and degree of perturbation which is important.\n\n3- They study their bound in Theorem 7 and observe that they can optimize the bound for simple random forest classifiers and obtain non-trivial robustness and generalization gaps.\n\n\nEvaluation: I find this paper interesting. It introduces a new way to study generalization in adversarial settings. I doubt their result will be of any help for a state-of-the-art classifier but it's a nice step in the understanding of the adversarial generalization. The paper is written well with a good amount of explanations. The work is also novel in that it uses the PAC-Bayes framework for the analysis of adversarial risk.  However, I have some concerns/questions mentioned below. I will update the score after hearing back from the authors.\n\n\nComments to the authors: \n\n1- Proposition 3: Does A_{D_n} converge to adversarial risk as n grows, at least for some specific settings? I think that is a crucial thing to argue, otherwise the obtained bounds will not have any connection to adversarial risk.\n\n2-Proposition 4: the distribution \\Pi is dependent on Q, right? It will be better to clarify that as it looks confusing now.\n\n\n3- After reading Theorem 6, I did not expect the bound to depend on n, as nothing in the statement of theorem depends on n. But after reading the text after the theorem and checking the proof I realized that set S is still defined based on n samples from the perturbation distribution. This is not clear from the statement of theorem at all. I think defining the notion of A_S^n would help the readability of the theorems. \n\n4- Theorem 7: Is there any intuitive way of thinking about the annoying middle part of the generalization gap? e.g. entropy of adversarial examples? Also, is there any hope to get rid of that part?\n\n5- It seems the bounds in Theorem 7 are independent of n. So one can potentially push n to infinity. It would be great if authors can provide such a corollary. Also, what are the implications of such a corollary on adversarial risk? Can you prove that the notion of average-max-risk will converge to adversarial risk, at least for certain spaces (e.g., when the instance space is discrete.)? \n\n6- In algorithm 1, the distribution \\pi_i is completely replaced by adversarial training. It seems that \\pi_i is chosen in a way that the bounds are valid. But unfortunately, this approach could lead the definition of average-max adversarial risk to be completely irrelevant to adversarial risk. For instance, if \\pi_i is defined to be a Dirac distribution, then increasing n would not have any effect and making it closer to adversarial risk.  This must be clarified in Table 1, Figure 1 and Figure 2. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "DMAY2nVWAJ", "reviewer": "Reviewer_pSP3", "summary": "The authors provide a PAC-Bayes analysis of two relaxations of the adversarial robust risk, the averaged adversarial robustness risk, and the averaged-max adversarial robustness risk.  They derive a series of relationships between these adversarial risks, in particular showing that the difference from the true risk and adversarial robust risk can be bounded by a total variation term.  This analysis is used to derive PAC-Bayes bounds on the two relaxed forms, which in turn are used to motivate adversarially robust training algorithms via minimizing the proposed bounds.  These are shown to be effective empirically in adversarial learning on several datasets.", "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": "The paper provides an elegant analysis of adversarial learning in a PAC-Bayes setting, providing a principled approach to adversarial training with theoretical guarantees.  The relaxations proposed are novel, and lead to a novel form of bound including a total variation term.  The submission appears to be technically sound and is accompanied by an informative empirical study.  Additional comparisons could have been made to other adversarial learning approaches in the experimentation, although the primary goal was to empirically compare different versions of the bound.  The presentation is clear and the paper well written.  The analysis is significant for providing a PAC-Bayes viewpoint to complement previous approaches to generalization analysis in the adversarial setting using Radamacher complexity and margin-based analysis.\n\nThere are a few minor typos which should be addressed in the final version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not relevant.", "review_text": "", "extra_scores": {"ethical_concerns": "Not relevant.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the generalization of adversarial error using the PAC-Bayes framework. The authors provide generalization bounds that are independent of the type of perturbations. 

The reviewers see this direction as novel and the results of interest. The more important concerns initially raised by the reviewers were addressed in the rebuttal (some reviewers increased their scores as a result). Overall, I think this paper makes an interesting contribution and I, therefore, recommend acceptance. Some reviewers still pointed out some limitations of the results and I would thus encourage the authors to add a discussion in the revised version.


Decision: Accept (Poster)