Adversarially Robust Learning with Tolerance
Authors: Hassan Ashtiani
Vinayak Pathak
Ruth Urner
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Statistical Learning Theory
PAC Learning
Adversarial Learning
Compression
Perturb and Smooth

Abstract: We initiate the study of tolerant adversarial PAC learning with respect to metric perturbation sets. In adversarial PAC learning, an adversary is allowed to replace a test point $x$ with an arbitrary point in a closed ball of radius $r$ centered at $x$. In the tolerant version, the error of the learner is compared with the best achievable error with respect to a slightly larger perturbation radius $(1+\gamma)r$. This simple tweak helps us bridge the gap between theory and practice and obtain the first PAC-type guarantees for algorithmic techniques that are popular in practice. Furthermore, our sample complexity bounds improve exponentially over best known (non-tolerant) bounds in terms of the VC dimension of the hypothesis class. In particular, for perturbation sets with doubling dimension $d$, we show that a variant of the  ``perturb-and-smooth'' algorithm PAC learns any hypothesis class $H$ with VC dimension $v$ in the $\gamma$-tolerant adversarial setting with $O\left(\frac{v(1+1/\gamma)^{O(d)}}{\varepsilon}\right)$ samples. This guarantee holds in the tolerant robust realizable setting. We extend this to the agnostic case by designing a novel sample compression scheme based on the perturb-and-smooth approach. This compression-based algorithm has a linear dependence on the doubling dimension as well as the VC-dimension. 

Adversarially Robust Learning with Tolerance
Anonymous Author(s) Affiliation Address email
Abstract
We initiate the study of tolerant adversarial PAC learning with respect to metric perturbation sets. In adversarial PAC learning, an adversary allowed to replace a test point with arbitrary point in closed ball of radius centered at æ. In the tolerant version, the error the learner is compared with the best achievable error with respect to slightly larger perturbation radius (1 + 7)r This simple tweak helps us bridge the gap between theory and practice and obtain the first PAC-type guarantees for algorithmic techniques that popular in practice. Furthermore, our sample complexity bounds improve exponentially over best known (non-tolerant) bounds in terms of the VC dimension of the hypothesis class. In particular, for perturbation sets with doubling dimension d, we show that a variant of the "perturb- and-smooth algorithm PAC learns any hypothesis class with VC dimension
2
4
6
10
11
the 7-tolerant adversarial setting with O (((+11/)) samples. This guarantee
13
holds in the tolerant robust realizable setting. We extend this to the agnostic case by designing novel sample compression scheme based on the perturb-and -eo--andd--oootd approach. This compression- based algorithm has a linear dependence on the doubling dimension well the VC-dimension.
15
Introduction
17
18 Several empirical studies (Szegedy et al., 2014 Goodfellow et al. 2018) have demonstrated that models trained have low accuracy data often have the undesirable property that small perturbation to an imput instance can change the label outputted by the model. For most domains this does not align with human intuition and thus indicates that the learned models
20
representing
22 the ground truth despite obtaining good accuracy on test sets.
23
The theory of PAC-leaming characterizes the conditions under which learning is possible. For binary classification, the following conditions are sufficient: a) unseen data should arrive from the same distribution as training data, and b) the class of models should have a low capacity (as measured, for example, by its VC dimension). these conditions are met, an Empirical Risk Minimizer (ERM) that simply optimizes model parameters maximize accuracy the training set learns successfully.
24
26
28 Recent work has studied test-time adversarial perturbations under the PAC-learnin framework. If
29 an adversary is allowed to perturb data during test time then the conditions above do not hold, and
30 we cannot hope for the model learn be robust just by running ERM. Thus, the goal here is to
31 bias the learning process towards finding models where label-changing perturbations are rare. This is
32 achieved by defining loss function that combines both classification error and the probability of
33 seeing label-changing perturbations, and learning models that minimize this loss on unseen data. It
34 has been shown that even though (robust) ERM can fail in this setting, PAC learning still possible as long we know during training the kinds of perturbations we want to guard against at test
36 time Montasser et al. 2019). This result holds for all perturbation sets. However, the learning
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37 algorithm is significantly more complex than robust ERM and requires large number of samples (with the best known sample complexity bounds potentially being exponential in the VC-dimension).
38
39 We study a tolerant version of the adversarially robust learning framework and restrict the perturba- tions to balls in a general metric space with finite doubling dimension. We show this slight shift in the learning objective yields significantly improved sample complexity bounds through a simpler learning paradigm than what was previously known. In fact, we show that a version of the common "perturb-and-smoode" paradigm successfully PAC-learns any class of bounded VC dimension in this setting.
40
41
42
43
44
45
Learning in general metric spaces. What kinds of perturbations should a learning algorithm guard against? Any transformation of the imput that we believe should not change its label could be viable perturbation for the adversary to use. The early works in this area considered perturbations contained within small bp-ball of the input. More recent work has considered other transformations such as a small rotation, or translation of an input image (Engstrom et al. 2019) Fawzi & Frossard [0055] Kanbak al.] 2018 Xiao et al. 2018). or even adding small amounts of fog or snow (Kang et al.
47
48
49
50
51
2019). It has also been argued that small perturbations in some feature space should be allowed as
52
opposed the input space (Inkawhich al. 2019: Sabour al., 2016 Xu et al. 2020, (Sng et al.
53
2018
Hosseini & Poovendran] 2018). This motivates the study of more general perturbations.
We consider setting where the input comes from domain that is equipped with distance metric and allows perturbations to be within a small metric ball around the input. Earlier work on general perturbation sets (for example, (Montasser et al. 2019)) considered arbitrary perturbations. In this setting one does not quantify the magnitude of a perturbation and thus cannot talk about small versus large perturbations. Modeling perturbations using a metric space enables us to do that while also keeping the setup general enough to be able to encode a large variety of perturbation sets by choosing appropriate distance functions.
55
56
57
58
59
80
61
Learning with tolerance. In practice, we often believe that small perturbations of the input should not change its label but we do not know precisely what small means. However, in the PAC-learning framework for adversarially robust classification, we are required to define a precise perturbation set and learn model that has error arbitrarily close to the smallest error that can be achieved with respect to that perturbation set. In other words, we aim to be arbitrarily close to a target that was picked somewhat arbitrarily begin with. Due to the uncertainty about the correct perturbation size, it is more meaningful to allow for a wider range of error values. To achieve this, we introduce the concept of tolerance. In the tolerant setting, in addition to specifying perturbation size r, we introduce tolerance parameter ? that encodes our uncertainty about the size of allowed perturbations. Then, for any given O, we aim to learn model whose error with respect perturbations of size is at most more than the smallest error achievable with respect to perturbations of size r(1 + 7).
63
65
67
89
70
71
72
2
Our results
73 In this paper we formalize and initiate the study of the problem of adversarially robust learning in the tolerant setting for general metric spaces and provide two algorithms for the task. Both of our
75 algorithms rely on: 1) modifying the training data by randomly sampling points from the perturbation
76 sets around each data point, and 2) smoothing the output of the model by taking a majority over the labels returned by the model for nearby points.
77
78 Our first algorithm starts by modifying the training set by randomly perturbing each training point
79 using& a certain distribution (see Scction5 for details). It then trains a (non-robust) PAC learner (such as ERM) on the perturbed training set to find hypothesis h. Finally, it outputs smooth version 81 of h. The smoothing step replaces (x)) at each point æ with the a majority label outputted by on the points around x. We show that for metric spaces of fixed doubling dimension, this algorithm successfully learns in the (robustly realizable) tolerant setting.
83
Let (X, dist) be metric space with doubling dimension d and H a hypothesis class. Assuming robust realizability, H can be learned tolerantly in 85
Theorem 1 (Informal version of Theorem 10
86 the adversarially robust setting using O (1- 1(4)) samples, where yy encodes the amount
of allowed tolerance, and is the desired accuracy.

---

88 An interesting feature of the above result is the linear dependence of the sample complexity with respect to VC(H). This is in contrast to the best known upper bound for non-tolerant adversarial 89
setting (Montasser et al. 2019) which depends on the dual VC dimension of the hypothesis class and in general is exponential in VC(H). Moreover, this is the first PAC type guarantee for the general perturb-and-smooth paradigm, indicating that the tolerant adversarial learning is the "right" learning model for studying these approaches. While the above method enjoys simplicity and can 94 be computationally efficient, one downside is that its sample complexity grows exponentially with
90
91
92
93
95 the doubling dimension. For instance, such algorithm cannot be used on high-dimensional data in the Euclidean space. Another limitation is that the guarantee holds only in the (robustly) realizable setting. We propose another algorithm that improves the dependence on doubling dimension, and works in the general agnostic setting.
97
98
99
Theorem 2 (Informal version of Corollary 16). Let (X, dist) be metric space with doubling dimension d and H. a hypothesis class. Then HL can be learned tolerantly in the adversarially robust setting using Ö (O())O(H)) log(1 (o1(1+1/7)) samples, where Ô hides logarithmic factors,,,, Y encodes the amount of allowed tolerance, and c is the desired accuracy.
100
101
102
103
This algorithm exploits the connection between sample compression and adversarially robust learn- ing Montasser et al. (2019). However, unlike Montasser al. (019)). our new compression scheme sidesteps the dependence on the dual VC dimension. As a result, we get an exponential improvement over the best known (nontolerant) sample complexity in terms of dependence on VC dimension.
104
105
108
3
Related work
107
108
PAC-learning for adversarially robust classification has been studied extensively in recent years (Cul-
lina et al. 2018 Awasthi et al. 22199; Montasser et al.) 2019 Feige et al. 2015 Attias et al. 2019
110
Montasser et al. 2020a; Ashtiani et al. 2020). These works provide learning algorithms that guaran- tee low generalization error in the presence of adversarial perturbations in various settings. The most general result is due to (Montasser et al.] 2019) which is proved for general hypothesis classes and perturbation sets. All of the above results assume that the learner knows the kinds of perturbations allowed for the adversary. Some more recent papers have considered scenarios where the learner does not even need to know that. Goldwasser et al. (2020) allow the adversary perturb test data in unrestricted ways and are still able to provide learning guarantees. The catch is that it only works in the transductive setting and only if the learner is allowed to abstain from making a prediction on some test points. Montasser et al. (2021a) consider the case where the learner needs to infer the set of allowed perturbations by observing the actions of the adversary.
112
114
115
116
117
118
119
120
Tolerance was introduced by Ashtiani et al. (020)) but in the context of certification. They provide examples where certification not possible unless allow some tolerance. MMntasser et al. (2021b) study transductive adversarial learning and provide a "tolerant" guarantee. Note that unlike our work, the main focus of this paper is on the transductive setting. Moreover, they do not specifically study tolerance with respect to metric perturbation sets. Without a metric, it is not meaningful to expand perturbation sets by factor (1 + 7) (as we do in the our definition of tolerance). Instead, they expand their perturbation sets by applying two perturbations in succession, which is akin to setting 7 = 1. In contrast, our results hold in the more common inductive setting, and capture a more realistic setting where y is any (small) real number larger than zero
122
123
124
125
128
127
128
Like many recent ad adversarially robust learning algorithms (Feige et al. 2015 Attias al. 2019). our first algorithm relies on calls to a non-so PAC-Ieamnr. Montasser et al. (2020b) formalize the question of reducing adversarially robust learning to non-robust learning and study finite perturbation sets of size k. They show a reduction that makes Ollog" 2 k) calls to the non-robust learner and also prove a lower bound of (log k). It will be interesting to see if our algorithms can be used to obtain better bounds for the tolerant setting. Our first algorithm makes one call to the non-robust PAC-learner
130
132
133
135
at training time, but needs to perform potentially expensive smoothing for making actual predictions
136
(see Theorem 10
137
The techniques of randomly perturbing the training data and smoothing the output classifier has been extensively used in practice and has shown good empirical success. Augmenting the training data with some randomly perturbed samples was used for handwriting recognition as early as in (Yaeger et al.
139
1996). More recently, "stability training" was introduced in (Zheng et al. 2016) for state of the art
3

---

141
to denote image classifiers where training data is augmented with Gaussian perturbations. Empirical evidence was provided that the technique improved the accuracy against naturally occurring perturbations. Augmentations with non-Gaussian perturbations of a large variety were considered in (Hendrycks)
142
143
144
al. 2019).
145
Smoothing the output classifier using random samples around the test point is popular technique for producing certifiably robust classifiers. A certification, in this context, is a guarantee that given test point x, all points within certain radius of x receive the same label as z. Several papers have
148
147
148
provided theoretical analyses to show that smoothing produces certifiably robust classifiers (Cao &
149
Gong 2017. Cohen et al. [0199] Lecuyer et al., 2019 Li et al. 2019 Liu et al., 2018 Salman et al.
150
2019
Levine Feizi| 2020).
151
However, to the best of our knowledge, a PAC-like guarantee has not been shown for any algorithm that employs training data perturbations output classifier smoothing, and our paper provides the
152
153
first such analysis.
Notations and setup
154
155
We denote by X the input domain and by Y {0, }} the binary label space. We assume that X + Y is a function that assigns a label to each point in the domain. A hypothesis class H is set of such hypotheses. For a sample
156
X is equipped with a metric dist. A hypothesis
157
S = ((x1, Mi...... ..... (Ie, Un)) E (X x Y)", we use the notation S = {Ii, ..,..., Zn
158
159
the collection of domain points x, occurring in S. The binary (also called 0-1) loss of h data point
180
(z. y) E X x Y is defined by
(01(,, v) [M(x)) y).
161
where [-] is the indicator function. expected binary loss of h with respect to P is defined by
Let P by a probability distribution over X Y. Then the
162
Cp (h)
2%/(()) Egg.n)> (h,
163
Similarly, the empirical binary loss of h on sample $ =
(In, E (X x Y)" is defined as C. (h) 1 Ei= 00/1 (h, F4, y:). We also define the approximation error of H with respect P Cp (H) inf <%1(1) (h).
184
165
166
function that takes in a finite sequence of labeled instances (1 v1),... ... (1 Un)) and outputs hypothesis h = A(S). The following definition abstracts the notion of PAC learning Vapnik & Chervonenkis (197I); Valiant (1984).
learner A
168
169
Definition 3 (PAC Learner). Let P be a set of distributions over X x Y and H hypothesis class. We say A PAC learns (H, with mA : (0, 1)2 + N samples if the following holds: for every distribution P P over X Y, and every e, 5 E (0,1), if is an i.idd sample of size at least (e, 8) from P, then with probability at least 8 (over the randomness of S) we have
170
172
Cp(A(S)) < CP(H) t
173
A is called an agnostic learner if is the set of all distributions on X Y, and realizable learner if P- = (PH = 0}.
174
175
The smallest function m : (0. 1) > N for which there exists learner that satisfies the above definition with m. m is referred to as the (realizable or agnostic) sample complexity of learning
176
177
H.
178
The existence of sample-efficient PAC learners for VC classes is a standard result Vapnik & Chervo nenkis 1971). We state the results formally in Appendix A
179
4.1
Tolerant adversarial PAC learning
Let u: : X + 2x be a function that maps each point in the domain to the set of its "admissible" perturbations. We call this function the perturbation type. The adversarial loss of h with respect to U on (I,z) E X x Y is defined by
181
183
e (h, x. v) = max (0 (h, 2,,,,,,0 2,3)3
sEU(Z)
4

---

The expected adversarial loss with respect to P is defined by (h) = B (h, v). The empirical adversarial loss of h on sample = ((11,)1)..... (Zn, Bn)) E (X x )) is defined by 2/33 (h) + Ei= ed (h, 24, yt). Finally, the adversarial approximation error of H. with respect to U and P defined by 2/ = infncH (h).
184
185
186
197
188
The following definition generalizes the setting of PAC adversarial learning to what we call the tolerant setting, where we consider two perturbation types U and V. We say U is contained in V and and write it as U1 < V (x) c. V(x) for all x E X.
189
190
191
Definition 4 (Tolerant Adversarial PAC Learner). Let P be a of distributions over X x Y, H hypothesis class, and U < V two perturbation types. We say A tolerantly PAC learns (H. P, u, V) with m : (0, 1)2 + N samples if the following holds: for every distribution P P and every from P, then with probability at least
192
193
194
é, 5 E (0, 1), if S is an ii.dd sample of size at least mAle, 8)
195
1 (over the randomness of S) we have
(((A(S)) S (H) +e.
198
We say A is a tolerant PAC learner in the agnostic setting if P is the set of all distributions over X Y, and in the tolerantly realizable setting if (P: (H) = 0}.
197
198
In the above context, we refer to Ul as the actual perturbation type and to V as the reference perturbation rype. The case where U(x)) Vzz) for all X corresponds to the usual adversarial learning scenario (with no tolerance).
199
200
201
4.2
Tolerant adversarial PAC learning in metric spaces
202
If X is equipped with a metric dist(...). then ((z) can be naturally defined by a ball of radius r dist(xr, 2) S r]. To simplify the notation, we sometimes use E" (h, x. y) instead of B (h, x. y) to denote the adversarial loss with respect to B,.
203
around x, i.e., Le..((()) = (x) = {= X
204
In the tolerant setting, we consider the perturbation sets (xx) (x) and (xx) = B() (2),
206
where y > 0 is called the tolerance parameter. Note that 21 < V. We now define PAC learning with respect to the metric space.
207
208
Definition 5 (Tolerant Adversarial Learning in metric spaces). Let (X, dist) be a metric space, H a hypothesis class, and P a set of distributions of x Y. We say (H, P, dist) is tolerantly PAC learnable with m (0, 1)3 - N samples when for every r, > 0 there exist a PAC learner Ar, for (H. P. B,, Be(1+2)) that uses mlc, 8, 7) samples.
209
210
211
212
Remark 6. In this definition the learner receives y and r as input but its sample complexity does not depend on r (but can depend on 7)- Also, as in Definition f the tolerantly realizable setting
213
corresponds to P = (P: - cr(1+)) (H) = 0} while in the agnostic setting P is the set of all distributions over X Y.
214
215
216
The doubling dimension and the doubling measure of the metric space will play important roles in analysis. We refer the reader to Appendix B for their definitions.
218
We will use the following lemma in our analysis, whose proof can be found in Appendix B
219
Lemma 7. For any family M of complete, doubling metric spaces, there exist constants C1, C2 > 0 such that for any metric space (X, dist) E M with doubling dimension d, there exists a measure J such that if ball B, of radius r >> 0 is completely contained inside a ball Bar of radius or (with potentially a different center) for any a > 1, then < p(Bar) S (c10) (xd))) have a constant on > 1 such that we know that a 2 ao then the bound can be simplified to < p(Bor) S ad ((B.). where Ç depends on M and ox-
220
222
Furthermore, if
224
225
Later, we will set a 1 + 1/7 where y is the tolerance parameter. Since we are mostly interested in small values of 7, suppose we decide on some loose upper bound I' > y. This corresponds to saying that there exists some aep > such that 2 ag.
226
227
It is worth noting that in the special case of Euclidean metric spaces,
set both cı and co be 1. In the rest of the paper, we will assume we have a loose upper bound I >> ry and use the simpler
229
230
bound from Lemma 24 extensively.
231
Given a metric space (X, d) and measure μ defined over it, for any subset S X for which (z()) is non-zero and finite, μ induces a probability measure P% over Z as follows. For any set Z' 2 in
5

---

233
the o-algebra over Z. we define Pž(Z") = #(Z")/u(Z). With slight abuse of notation, we write to mean Pz whenever we know μr from the context.
234
235
Our learners rely on being able to sample from Piz- Thus we define the following oracle, which can be implemented efficiently for lp spaces.
Definition 8 (Sampling Oracle). Given metric space (X, dist) equipped with doubling measure sampling oracle is an algorithm that when queried with a Z S X such that p(Z) is finite, returns sample drawn from Pz We will use the notation z for queries this oracle.
238
239
The perturb-and-smoone approach for tolerant adversarial learning
240
241
In this section we focus on tolerant adversarial PAC learning in metric spaces (Definition 5). and show that VC classes are tolerantly PAC learnable in the tolerantly realizable setting. Interestingly, we prove this result using an approach that resembles the "perturb-anndsmoooth" paradigm which
243
used in practice (for example, (Cohen al., (209)). The overall idea is to "perturb" each training
245
point v, train a classifier on the "perturbed" points, and "smooth out" the final hypothesis using a certain majority rule.
248
247
For this, we employ three perturbation types: 2 and V play the role of the actual and the reference perturbation type respectively. Additionally, we consider a perturbation type W X 2* which is used for smoothing. We assume < V and W < V. For this section, we will use metric balls for the three types. Specifically, if u consists of balls of radius for some O, then W will consists of balls of radius "rr and V will consist of balls radius (1 11+7 y)r.
249
251
Definition (Smoothed classifier). For a hypothesis h X - {0, 1), we let hw denote the classifier resulting from replacing the label h(x)) with the average label over W(x), that
252
hw(()) = (Ee=)Wes)h((')) 2 1/2]
For metric perturbation types, where is a bull of some radius r, we also use the notation Typ and when the type W is clear from context, we may omit the subscript altogether and simply write h for the smoothed classifier.
254
256
The tolerant perturb-ande -nntuur---d---mooth algorithm We propose the following learning algorithm, TPaS, for tolerant learning in metric spaces. Let the perturbation radius be > 0 for the actual type UI = B,, and let S = (I1.8)),.... (xm- Dm)) be the training sample. For each æ, E S.X the learner samples point 2 (y+(1+) (z;) (using the sampling oracle) from the expanded reference perturbation set ((x.)) = ((14))) (2,). Let 5' = ((21 V1).... (I'm. ym)). TPaS then invokes (standard, non- 261
257
259
robust) PAC learner Az for the hypothesis class on the perturbed data S'. We let h (s') denote the output of this PAC learner. Finally, TPaS outputs the W-smoothed version of hyr for W Byr. That is, (xx) is simply the majority label in ball of radius "yr around æ with respect to the distribution defined by μ. see also Definition 9 We will prove below that this Ker has small U- advevrrsaaial loss, Algorithm beloow summarizes our learning procedure.
262
264
285
286
Algorithm Tolerant Perturb and Smooth (TPaS)
Input: Radius r, tolerance parameter 7, data S = ((x1,81),.... Bi)...,, (Xms vmn)), accesss to sampling oracle O for f and PAC learner AH-
Initialize S'
f m do
Sample æ! (()+))r
Add (αr4, U/) to S
end for
Set h== Ax(5))
Output: byy defined by
(x) (E) 2 1/2
The following is the main result of this section.

---

268
Theorem 10. Let (X, dist) be an any metric space with doubling dimension d and doubling measure
269
μ. Let O be a sampling oracle for μ. Let H. be hypothesis class and P a set of distributions over
X xxY. Y. Assume Ay PAC learns H with ( 5) samples in the realizable setting. Then there exists
271
a learner A, namely TPaS, that
Tolerantly PAC learns (H, P, dist) in the tolerantly realizable setting with sample complexity bounded by m(e, 6, = O (mx(e,)) (1+ 1/7))44) =O (CCH)) 1/8 (1+ 1/7)(a).
273
274
where y is the tolerance parameter and is the doubling dimension.
275
Makes only one query to Au
278
Makes 6,), queries to sampling oracle O
277
The proof of this theorem uses the following key technical lemma (proof can be found in Appendix O
278
Lemma 11. Letr O be a perturbation radius, y 0 tolerance parameter, and g X Y classifier. For x E X and E E = =(0, 1}, we define
(g
(Bx 1 [g(2)) # y] and g) B.- [g(2) * v].
-Cd
279
Then Eg.y S
1+2
implies that og (2) S for all (x)
280
Proof Theorem 10 Consider some co > and 0 < < to be given (we will pick suitable value of co later), and assume the PAC learner Ah was invoked on the perturbed sample S' of size least m 8). According to definition 3
282
this implies that with probability 1- 8, the output Axx has (binary) loss at most En with respect to the data genteraing distribution. Note that the relevant distribution here is the two-stage process of the original data generating distribution P and the perturbation sampling according to V = B()+)))- Since P is V-robustly realizable, the two-stage process yields a realizable distribution with respect to the standard 0/ 0/1-loss. Thus, we have
283
285
286
(( (1))
[[=)) # y S co.
287
With Lemma 11 this becomes B( P (x) S 60- For A > 0, Markov's inequality then yields:
E(a [nnn (x) s 2] >1 1 co/A
Thus setting x = Y/4 (1+2)
cd
and plugging in the result of the Lemma 11 equation (1 get
E B(z,))=11 (Yz E B,), nn (=) S 1/3] ca/
288 Since (h,y(2) < 1/3 implies that n [Ber 1(>²) 2 1/2 = using the definition of the smoothed classifier hay we get
289
E( [32 E (x),). Ry + v] S co/A,
(2)
which implies (pp(h)))) S Eo Thus, for the robust learning problem, if we given desired accuracy c and we want (hyr) I c, we can pick co = Ac. Putting it all together, we get 291
sample complexity m < 0 VC(H)+ where en = de, and X = 14.7
-Cd
282
Therefore,
YOrH)+ 1/6 + 117)/))
293
m
< O
294
Since the dependence on is exponential, the algorithm becomes impractical for high dimensions if y is very small. However, since represents our uncertainty in the value of the true perturbation radius,
296 is natural to assume that a small but positive number. We can therefore ask whether there exists threshold for each dimension such that if y is above the threshold we can learn efficiently. In
7

---

particular, for any constant C > O, we can ensure that (1 (1+1/))<² I If we set y 2 <d Thus the
298
sample complexity of our learner does not depend on the dimension as long as y z <d For example,
299
300
for a Euclidean space with the &o metric, we have Ç = 1. Therefore setting = 1000 would let us
301
use a small y for dimensions up 1000.
302
Computational complexity of the learner. Assuming we have access to and an efficient algorithm for non-robust PAC-learning in the realizable setting, we can compute efficiently. Therefore, the learning can be done efficiently in this case. However, the prediction time, we need to compute hx)) on new test points which requires us to compute an expectation. We can instead estimate the 305
303
304
306
expectations using random samples from the sampling oracle. For single test point z, if the number of samples we draw is 2loo 1 /66) then with probability at least - 5 we get the same result as that of the optimal h(x). Using more samples we can boost this probability to guarantee a similar output
307
308
309
to that of h on larger set of test points.
Improved tolerant learning guarantees through sample compression
310
The perturb-and-smooth approach discussed in the previous section offers general method for tolerant robust learning. However, one shortcoming of this approach is the exponential dependence of its sample complexity with respect to the doubling dimension of the metric space. Furthermore, the tolerant robust guarantee relied on the data generating distribution being tolerantly realizable. In this section, we propose another approach that addresses both of these issues. The idea is to adopt the geturb-and-smoon approach within a sample compression argument. We introduce the notion of (24, V)-tolerant sample compression scheme and present a learning bound based on such a compression scheme, starting with the realizable case. We then show that this implies learnability
312
314
315
316
317
318
319
in the agnostic case well. Remarkably, this tolerant compression based analysis will yield bounds on the sample complexity that avoid the exponential dependence on the doubling dimension.
320
For compact representation, will use the general notation Ut, V, and W for the three perturbation types (actual, reference and smoothing type) in this section and will assume that they satisfy the Property| below for some parameter 3 >> O. Lemma 11 implies that, in the metric setting, for any radius+ r and tolerance parameter y the perturbation types u = B,, V B(1+))) and W =B.y have -cd
322
323
324
this property for 3 = (14))
325
326
Property 1. For a fixed < B 1/2, we assume that the perturbation types V,Ul 7 and W so that for any classifier h and any x E X, any y E 13, if
327
Ez~V(a) [h(2) = y) 2 1 3
328
then W-smoothed class classifier how satisfies hw(z) )) = y for all = E U(x).
329
compression scheme of size k is a pair of functions (n, (k, where the compression function
(X x Yy + U x Y)² maps samples S = ((11, y1), (2), (Im, Unm) of arbitrary size to sub-samples of of size at most k and p: U. x xY y is a decompression function that maps samples to classifiers. The pair (s, p) is a sample compression scheme for loss f
330
331
333
and class H. if for any samples S realizable by H. we recover the correct labels for all (x, y) E S, that is, Ls(H) (H) O implies that L.( p(S)) = 0.
334
335
For tolerant learning, we introduce the following generalization of compression schemes:
336
Definition 12 (Tolerant sample compression scheme). A sample compression scheme (K. p) is a
U V-tolerant sample compression scheme for class H. if for any samples S that are C" realizable by H. that is 23 = 0, we have Z' (K o p(5)) = 0.
338
339
The next lemma establishes that the existence of a sufficiently small tolerant compression scheme for the class H yields bounds on the sample complexity of tolerantly learning H. The proof of the lemma is based on a modification of standard compression based generalization bound. Appendix Section provides more details.
340
341
342
343
Lemma 13. Let H be a hypothesis class and U and be perturbation types with U included in V. If the class H admits a (U, V)-tolerant compression scheme of size bounded by k &n(()) for sample of size m. then the class is (U, tooleraayyyy learnable in the realizable case with sample complexity
344
345
bounded by mi(e, 6) = = [44n(1188)
346
8

---

347
We next establish bound on the tolerant compression size for general VC-classes, which will then immediately yield the improved sample complexity bounds for tolerant learning in the realizable case. The proof is sketched here; its full version has been moved to the Appendix for lack of space.
348
Lemma 14. Let H. C YX be some hypothesis class with finite VC-dimension VC(H) < oc, and let U, V,W W satisfy the conditions Property for some 3 > Then there exists a (I, -tooleran
350
351
sample compression scheme for H of size Ô (VC(H) In(
352
353
Proof Sketch. We will employ a boosting- based approach to establish the claimed compression sizes. Let S = ((x1,30 31 (22, :.)...., (mm. Bm)) be data-set that is l rearelizablle with respect H. We let Sy denote an "inflated data-set" that contains all domain points in the V-perturbation sets of the 24 Sx that is Sz = V(rz). Every point S is assigned the label y = yt of the
355
356
357
minimally-indexed (ri, ya) E with E Vix)), and we set Sy to be the resulting collection of
358
labeled data-points.
359
We then use the boost-by-majortty method to encode a classifier that (roughly speaking) has error bounded by 3/m over (a suitable measure over) Sy. This boosting method outputs 7 1'-majority vote y(x) = 11 (={=)(((x)) 2 1/2 over weak learners 14, which in our case will be hypotheses from H. We prove that this error can be achieved with T 18 In( 8 rounds of boosting, We prove that each weak learner that is used in the boosting procedure can be encoded with Ō(VC(H)) many sample points from S. The resulting compression size is thus n T = Ô (VC(H) lm())
384
385
Finally, the error bound 8/m of g over Sy implies that the error in each perturbation set ((x;) of a sample point (at,, ys) E S is at most 3. Property 1 then implies 2 (ūw) = 0 for the W-smoothed classifier Gw. establishing the (44, V/)-tolerant correctness of the compression scheme.
367
388
This yields the following result
369
Theorem 15. Let H be a hypothesis class of finite VC-dimension and V H, W be three perturbation
types (actual, reference and smoothing) satisfying Property for some >> O. Then the sample complexity (omitting log-factors) of (M, (),,V))tolee V)ttolrrnntly learning H is bounded by
370
m(e, 8) ò (VC(H) lm(1/3) Im(1/))
in the realizable case, and in the agnostic case by
m(e, 8) Ō (C(()) + mn(/8)
22
373
Proof. The bound for the realizable case follows immediately from Lemma 14jand the subsequent discussion (in the Appendix). For the agnostic case, we employ reduction from agnostic robust learnabilty to realizable robust learnability (Montasser et al.) 2019 Moran & Yehudayoff 2016). The reduction is analogous the one presented in Appendix C Montasse al. (2019) for usual (non-tolerant) robust learnablity with some minor modifications. Namely, for a sample S, we choose the largest subsample S' that is é'-realizable (this will result in competitiveness with l opptimall classifier), and we will use the boosting procedure described there for the & loss. For the sample sizes employed for the weak learners in that procedure, we can use the sample complexity for e
375
376
377
378
379
380
1/3 of an optimal (24, V) -tolerrtttt learner in the realizable case (note that each learning problem during the boosting procedure is a realizable (44, -)otolerant learning task). These modifications result the stated sample complexity for agnostic tolerant learnability.
382
383
384
In particular, for the doubling measure scenario (as considered in the previous section), we obtain Corollary 16. For metric tolerant learning with tolerance parameter Y in doubling di- mension d the sample complexity of learning in the realizable case is bounded by m(c,5) 5) Ö (XCC)))da(()))))+
386
387
and in the agnostic case by m(c,8)
388 δ VCCH)//ln(1-11)))A/LI 6

---

References
390
Ashtiani, H., Pathak, V., and Urner, R. Black-box certification and learning under adversarial perturbations. In International Conference on Machine Learning, pp. 388-398. PMLR, 2020.
392
Attias, I., Kontorovich, A.. and Mansour, Y. Improved generalization bounds for robust learning, In
383
Algorithmic Learning T'heory, ALT,, pp. 162-183, 2019.
Awasthi, P., Dutta, A., and Vijayaraghavan, A. On robustness adversarial examples and polynomial
385
optimization. In Advances in Neural Information Processing Systems, NewrIPS, pp. 13760-13770, 2019.
387 Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. Learnability and the vapnik- chervonenkis dimension. Journal of the ACM (JACM), 36(4):929-966 1989.
399
Cao, X. and Gong, N. Z. Mitigating evasion attacks to deep neural networks via region-based
400
classification. In Proceedings of the 33rd Annual Computer Security Applications Conference, pp. 278-287, 2017.
402
Cohen, J. M., Rosenfeld, E., and Kolter, J. Z. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 1310-1320, 2019.
404
405
Cullina, D., Bhagoji, A. N., and Mittal, P. Pac-learning in the presence of adversaries. In Advances in
406
Neural Information Processing Systems, NeurIPS, pp. 230-241, 2018.
407 Engstrom, L., Tran, B., Tsipras, D., Schmidt, L., and Madry, A. Exploring the landscape of spatial
robustness. In International Conference Machine Learning, pp. 1802-1811, PMLR, 2019.
409
Fawzi, A. and Frossard, Manitest: Are classifiers really invariant? In British Machine Vision Conference (BMVC), number CONF, 2015.
410
Feige, U., Mansour, Y., and Schapire, R. Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory, COLT, pp. 637-657, 2015.
412
413
Goldwasser, S.. Kalai, A. T., Kalai, Y. T., and Montasser, O. Beyond perturbations: Learning
414
guarantees with arbitrary adversarial test examples. arXiv preprint arXiv:2007.0514 2020.
415
Goodfellow, I. J., McDaniel, D., and Papernot, N. Making machine learning robust against
adversarial inputs. Commun. ACM, 61(7):56-66, 2018.
417
Hanneke, S. The optimal sample complexity of pac learning. The Journal of Machine Learning Research, 101119111333 2016.
418
Haussler, D. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and computation, (00(1):78-155)) 1992.
420
Haussler, D. and Welzl, E. epsilon-nets and simplex range queries. Discret. Comput. Geom., 2:
422
127-151, 1987.
423
Hendrycks, D., Mu, N., Cubuk, E. D., Zoph, B., Gilmer, J., and Lakshminarayanan, B. Augmix: A
simple data processing method to improve robustness and uncertainty. In International Conference on Learning Representations, 2019.
425
426
Hosseini, H. and Poovendran, R. Semantic adversarial examples. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 1614-1619, 2018.
427
428
Inkawhich, N., Wen, W., Li, H. H., and Chen, Y. Feature space perturbations yield more transferable adversarial examples. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pp. 7066-7074, 2019.
430
Kanbak, C., Moosavi-Dezfooll, S.-.., and Frossard, P. Geometric robustness of deep networks:
432
Analysis and improvement. 2018 IEFF/CVF Conference on Computer Vision and Pattern Recognition, pp. 4441-4449. IEEE, 2018.
10

---

434
Kang, D., Sun, Y., Hendrycks, D., Brown, T., and Steinhardt, J. Testing robustness against unforeseen adversaries. arXiv preprint /90Ki 08016, 2019.
435
436
Lecuyer, M., Atlidakis, V., Geambasu, R., Hsu, D., and Jana, S. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium Security and Privacy (SP), pp. 656-672. IEEE, 2019.
438
439
Levine, A. and Feizi, S. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp- 4585-4593, 2020.
Li, B., Chen, C.,, Wang, W., and Carin, L. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems, 32:9464- 12:9464-9474, 2019.
442
443
Liu, X., Cheng, M., Zhang, H.. and Hsieh, C.-J. Towards robust neural networks via random self-
444
ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 369-385, 2018.
445
Luukkainen, J. and Saksman, E. Every complete doubling metric space carries doubling measure. Proceedings of the American Mathematicul Society, 126(2):531-534, 1998.
447
448
Montasser, O., Hanneke, S., and Srebro, N. VC classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, COLT, pp. 2512-2530, 2019.
Montasser, O., Goel, S., Diakonikolas, I., and Srebro, N. Efficiently learning adversarially robust halfspaces with noise. arXiv preprint (xXiv:2005.07652. 2020a.
451
452
Montasser, O., Hanneke, S., and Srebro, N. Reducing adversarially robust learning to non-robust pac
453
learning, NeurlPS, 2020b.
Montasser, O., Hanneke, S., and Srebro. N. Adversarially robust learning with unknown perturbation 454
455
sets. arXiv preprint 102.:2200..02155, 2021a.
456
Montasser, O.,, Hanneke, S., and Srebro, N. Transductive robust learning guarantees. arXiv preprint a0. 10602, 2021b.
457
458
Moran, S. and Ychudayoff, A. Sample compression schemes for vo classes. Journal of the ACM
(JACM), 63(3):1-10, 2016.
Sabour, S., Cao, Y., Faghri, F., and Fleet, D. J. Adversarial manipulation of deep representations, In
461
ICLR (Poster), 2016.
462
Salman, H., Li, J., Razenshteyn, I. P., Zhang, P., Zhang, H., Bubeck, S., and Yang, G. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems 32, NeurlPS, pp. 11289-11300 2019.
484
465
Schapire, R. E. and Freund, Y. Boosting: Foundations and algorithms. Kybernetes, 2013.
Shalev-Shwart,, S. and Ben-David, S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
467
488
Simon, H. U. An almost optimal pac algorithm. In Conference on Learning Theory, pp. 1552-1563. PMLR, 2015.
Song, Y., Shu, R., Kushman, N., and Ermon, S. Constructing unrestricted adversarial examples with generative models. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 3322-8333, 2018.
471
472
473
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, J., and Fergus, R. Intrigu- ing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR, 2014.
474
475
476
Valiant, L. G. A theory of the learnable. Commun, 211 1984.
477
Vapnik, V. N. and Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-280, 1971.

---

479
Xiao, C., Zhu, Li, He, W., Liu, M., and Song, D. Spatially transformed adversarial examples. In International Conference on Learning Representations. 2018.
480
481
Xu, Q. Tao, G., Cheng, S., and Zhang, X. Towards feature space adversarial attack. arXiv preprint arXiv:2004. 12385, 2020.
482
483
Yaeger, L., Lyon, R., and Webb, B. Effective training of neural network character classifier for
484
word recognition. Advances in neural information processing systems, 9:807-816, 1996.
485
Zheng. S., Song. Y.. Leung, T., and Goodfellow. I. Improving the robustness of deep neural networks via stability training. In Proceedings of the ieee conference on computer vision and pattern recognition, pp. 4488,4488, 2016.
486
487
Checklist
488
1. For all authors...
490
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] Yes, the claims are supported by actual theorems and proof' in the main text.
491
488
(b) Did you describe the limitations of your work? [Yes] We have discussed the limitations of our main two results (theorems), including the dependency of the sample complexity on each of the parameters and the computational costs.
494
485
496
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is a theoretical paper and we do not foresee any immediate negative impacts.
497
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
499
500
2.
If you are including theoretical results...
501
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Yes, the assumptions are clearly stated. Also, wherever we had an informal theorem, we have linked the full version of the theorem too (with all the necessary details and assumptions).
502
503
504
(b) Did you include complete proof's of all theoretical results? [Yes] Yes. Some of the proof's are deferred to the appendix for space constraints.
506
507
3. If you ran experiments...
508
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
509
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
511
512
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
514
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
515
516
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
517
(a) If your work uses existing assets, did you cite the creators? [N/A]
518
(b) Did you mention the license of the assets? [N/A]
519
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
$20
521
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
523
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
524
825
5. If you used crowdsourcing or conducted research with human subjects...
526
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
12

---

528
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
529
530
(c) Did you include the estimated hourly wage paid to participants and the total amount
spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "yYqK_-tScga", "reviewer": "Reviewer_MDPr", "summary": "This paper introduce adversarial robust learning based on tolerance (i.e., training with larger random perturbation), estimator smoothing and sample compression. It present a rigorous sample complexity analysis. This paper focuses solely on theoretical analysis, and doesn't provide any concrete algorithm or simulation result.", "questions": "1. How realistic is the assumption of that \"P is V-robustly realizable\"? what happens if we let gamma go to infinity?\n2. Property 1, the equation should be the expectation of an indicator function.\n3. Theorem 10 implicitly requires A_H to be an optimal PAC learning, which is not clearly mentioned. ", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Strength: the results are mathematically sound.\n2. Weakness: despite the rigorous mathematical derivation, I am not sure how the presented PAC analysis result helps the community. One can directly apply the sample complexity analysis on the adversarial loss (say via Rademacher complexity). Does the presented result provide more insights or a better rate?\n3. Weakness: the paper doesn't actually provide an executable algorithm, but only an existence results, i.e., the existence of measure mu, the existence of sample compression scheme. Whether the rate results pair with a computational feasible algorithm is unclear, and there is no simulation to demonstrate empirical performance/comparison.\n4 Weakness: in conclusion, the paper neither provide a theoretical information limit result, nor an executable adversarial training algorithm.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dQy6nts8qO", "reviewer": "Reviewer_FjcX", "summary": "Setting and contributions:\nThe authors suggest a new realistic setting of adversarially robust PAC learning (to test time attacks) in metric spaces, \nsuch that the learner is tested at inference time on a slightly bigger perturbation set that is controlled by a parameter (gamma>0) for his choice. We refer to it as the tolerance parameter.\nObviously, by choosing a smaller gamma, the perturbation set at test time is getting closer to the one on training time, which is a harder benchmark. As a result, there is a trade-off between sample complexity and competing with a better benchmark. \n\nThe main results are two algorithms. \nThe first one is in the robust realizable setting, with sample complexity that depends exponentially on the metric space dimension (doubling dimension) and linearly in the VC dimension. The algorithm is simple and efficient.\n\nThe second algorithm, for the agnostic setting, incorporates the idea of the first one (perturb and smooth) with a sample compression scheme argument, suitable for the model with tolerance. The sample complexity is improved exponentially (linear in the doubling dimension), due to the strong generalization guarantees of sample compression. ", "questions": "-What is the support of the distribution? Is it the clean examples, and for sampling from a perturbation set you first sample from a clean example?\nMore specifically, is it defined similarly to the previous papers on theoretical robust learning?\n\n-Can you please give a short explanation of how you avoid the dual VC in Lemma 14? I know why it pops up in the case of arbitrary perturbation sets.\nI read the proof, but not sure about the answer.\n\nI would be happy to figure it out and recommend the paper for acceptance. ", "limitations": "-", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This theoretical setting is natural, and well-motivated by empirical work on adversarial examples.\n\nThe results are satisfying, specifically exploiting the metric space assumption for removing the dual VC that pops up in the case of general perturbation sets.\n\nI find the techniques simple and elegant.\n\nOverall, I think that it is a nice idea for studying robustness.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Uao_QZ3HJMZ", "reviewer": "Reviewer_xynd", "summary": "The paper studies the PAC learnability of adversarial robustness in the tolerant setting. The paper reveals a learnability result showing that VC hypothesis sets are tolerantly PAC learnable in the realizable case using a ``perturb-and-smooth'’ algorithm. As compared to previous non-tolerant results, their sample complexity has an exponential improvement on the dependence of VC dimension. The paper also reveals a learnability result in the agnostic setting through sample compression. \n", "questions": "See the weaknesses.", "limitations": "The discussion was adequate.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* Well-written assumptions and theorems.\n* New tolerant framework is considered.\n\nWeaknesses:\n\nThe significance is limited. The major issue is that their tolerance framework is not justified.\n\nOn the one hand, they do not specify how to choose a reasonable *reference* perturbation type V(x) given an *actual* perturbation type U(x) in definition 4. More precisely, the choice of tolerance parameter \\gamma in line 206 is unclear. I think this is very crucial and necessary in this framework. Consider the case where V(x)=0 and U(x) = B_{\\gamma}(x). Then the inequality between line 195 and 196 tells that the algorithm can find a classifier with clean error smaller than the adversarial bayes error within ball B_{\\gamma}(x), which is actually meaningless for any \\gamma since we know that the clean bayes error must be less than the adversarial bayes error and the sample-efficient PAC learners for clean bayes classifier is known.\n\nIn line 298 - 301, they want to set gamma to be above some threshold. Using their parameters of \\zeta=1, c =1000 and d=1000 in the provided example, the gamma is required to be larger than 1. It is hard to believe that such a large gamma is meaningful in terms of the tolerance of perbutation size.\n\nOn the other hand, they do not show negative results like \"some tolerance is necessary otherwise adversarial robustness is not possible\", which further limits the significance.\n\nTheir sample complexity such as that in Theorem 10 is independent of the actual perturbation size r for adversarial robustness. Their proposed algorithm does not train on the worst case perturbed samples. Instead, the algorithm only trains on the randomly perturbed samples, which I think is not useful for adversarial robustness. These facts suggest that such a tolerance framework seems not reliable.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8tvdz6jsRXk", "reviewer": "Reviewer_Lxpv", "summary": "The paper introduces an algorithm called “tolerant perturb and smooth” and analyzes it with the lens of tolerant PAC learning. The analysis applies to the robustly realizable setting. This analysis is able to tighter sample complexity bounds than previous work.", "questions": "Is there an argument that this work has higher significance than I've thought, despite the algorithm itself not working well? For example, is it a step on a path to performing an analysis of one of the methods from the related work section that works well?", "limitations": "My main objection to this paper is that I think it does not make the limitations clear enough to an audience that is interested in adversarial examples but not expert in PAC learning theory. I'm concerned that the paper comes across as proving that TPAS \"works\" as a defense when that's not the case and I think that's not technically what the paper is claiming.\n\nOne other limitation I didn't discuss above is Algorithm 1 uses an analytical expectation over x’, rather than a finite number of samples, so the algorithm cannot be implemented in practice for most interesting models. I see that this is discussed at line 135 but I think the discussion should be more prominent, I think the problem is worse than being “potentially expensive” for many models such as neural networks.\n", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\n\tPros:\n\t\t- I don’t have the expertise to check the proofs, but I think the proofs in the paper are non-trivial and are likely to be correct\n\n\tCons:\n\t\t- I’m fairly confident that the algorithm TPAS algorithm does not work at all. I implemented the algorithm for linear models on MNIST and it got 5% adversarial test accuracy. That’s worse than random guessing! I didn’t even implement the real adversarial example algorithm that’s aware of the random smoothing, I just generated adversarial examples off a single instantiation of the model on clean examples, so presumably the true adversarial error rate is even worse. Most of what I say in the review is low confidence but I am confident that the algorithm simply does not work.\n\t\t- Similar algorithms that do work, as correctly discussed in the related work section, do things like train on more than one noisy sample per example, and use different aggregation metrics, rather than just the simple mean.\n\t\t- To be clear, I’m not saying that the PAC analysis in the paper is wrong, or that the paper over claims performance anywhere. It’s possible to have low sample complexity by converging rapidly (as a function of dataset size) to very bad performance. The analysis in the paper is also restricted to the robustly realizable setting, meaning the final performance should be good, but this also restricts the applicability of the work significantly. For example, it means the paper is not actually applicable to my linear MNIST experiment.\n\t\t- It’s unclear to me whether there is any interesting data distribution (ImageNet etc) which is known to have a model class that satisfies robust realizability. For MNIST and small max norm balls, robust realizability may be possible, though it’s not totally clear that the norm ball convolved with the true data distribution for one class does not overlap with the norm ball convolved with the true data distribution of another class. Certainly the norm balls centered on the finite MNIST test sets don’t overlap, for the size of norm balls commonly used in the literature. Small convolutional neural networks are able to memorize the (adversarial) test set, so maybe these satisfy robust realizability.\n\t\t- I also trained a small CNN using TPAS and it got ~1% accuracy against adversarial examples. Once again, this was with a non-adaptive attacker (not aware of the test time noise smoothing).\n\t\t\t- I’m assuming this result is still compatible with the claims in the paper, but I haven’t spent any time trying to work out how so.\n\t\t- Overall, I argue for rejection because I’m concerned that as presented, the paper would be misinterpreted as arguing that TPAS is an effective defense against adversarial examples. The adversarial example topic has repeatedly proved to be prone to false memes spreading rapidly, becoming ingrained, and requiring people working on the topic to waste a lot of time and effort arguing against misconceptions. This could potentially be addressed by substantially revising the paper to be extremely up front about the limitations of TPAS and explaining the interpretation of the PAC theory in a way that makes it clear that the PAC theory does not imply that TPAS would result in good performance or even better than chance performance on, say an ImageNet benchmark. Another way of stating this objection is that, while the paper does not over claim, I feel like it omits too much discussion of (very significant) limitations.\n\t\t- I have a second, weaker reason for arguing for rejection, which is simply that NeurIPS is a selective venue, publishing particularly interesting results rather than merely correct results. Due to the poor performance of the TPAS algorithm, I argue that theoretical analysis of the algorithm is not interesting enough to be ranked high enough for NeurIPS acceptance, regardless of the correctness of that analysis.\n\nComments on the dimensions:\n- I don't know enough about PAC theory to assess originality or quality well.\n- I argue that the work has poor clarity because it will appear to many readers to endorse TPAS as a defense against adversarial examples, when in fact I think it technically does not claim that this method will achieve good performance.\n- I argue that the work has low significance because the algorithm analyzed does not work\n\n\n\nOne sentence I do think is mistaken: I think this sentence should be revised: “These works provide learning algorithms that guarantee low generalization error in the presence of adversarial perturbations in various settings.” Unless I’m mistaken, these algorithms guarantee that the generalization error is nearly optimal within the hypothesis space, but the optimal generalization error within the hypothesis space for many standard hypothesis spaces (like linear models, or some neural network) could be worse than random guessing. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject