On Proper Learnability between Average- and Worst-case Robustness
Authors: Vinod Raman
UNIQUE SUBEDI
Ambuj Tewari
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial Robustness
PAC Learning
TL;DR: We study proper PAC learnability under relaxed notions of adversarial robustness.

Abstract: Recently, Montasser at al. (2019) showed that finite VC dimension is not sufficient for proper adversarially robust PAC learning. In light of this hardness, there is a growing effort to study what type of relaxations to the adversarially robust PAC learning setup can enable proper learnability. In this work, we initiate the study of proper learning under relaxations of the worst-case robust loss. We give a family of robust loss relaxations under which VC classes are properly PAC learnable with sample complexity close to what one would require in the standard PAC learning setup. On the other hand, we show that for an existing and natural relaxation of the worst-case robust loss, finite VC dimension is not sufficient for proper learning. Lastly, we give new generalization guarantees for the adversarially robust empirical risk minimizer.

On Proper Learnability between Average- and Worst-case Robustness
Vinod Raman" Department of Statistics University of Michigan Ann Arbor, MI 48104 vkramanQumich edu
Unique Subedi" Department of Statistics University of Michigan Ann Arbor, MI 48 104 subedi @umi ch. edu
Ambuj Tewari
Department of Statistics University of Michigan Ann Arbor, MI 48 104 tewar awariaauuica ch. edu
Abstract
Recently, Montasser et al. 2019) showed that finite VC dimension is sufficient for proper adversarially robust PAC learning. In light of this hardness, there is a growing effort to study what type of relaxations to the adversarially robust PAC learning setup can enable proper learnability. In this work, we initiate the study of proper learning under relaxations of the adversarially robust loss. We give a family of robust loss relaxations under which VC classes are properly PAC Iearnable with sample complexity close to what one would require in the standard PAC learning setup. On the other hand, we show that for an existing and natural relaxation of the adversarially robust loss, finite VC dimension is not sufficient for proper learning. Lastly, we give new generalization guarantees for the adversarially robust empirical risk minimizer.
1 Introduction
As deep neural networks become increasingly ubiquitous, their susceptibility to test-time adversarial attacks has become more and more apparent. Designing learning algorithms that are robust to these test-time adversarial perturbations has garnered increasing attention by machine learning researchers and practitioners alike. Prior work on adversarially robust learning has mainly focused on learnability under the worst-case adversarially robust risk [Montasser et al. 2019 Attias et al. 2021 Cullina
al. 2018
Re (h; D) = (D.U)~D
sup 1(((2) + y} =EU(())
where ((x) C X' an arbitrary but fixed perturbation set (for example é, balls). practice, worst- case robustness is commonly achieved via Empirical Risk Minimization (ERM) of the adversarially robust loss or some convex surrogate [Madry et al., 2017 [Wong and Kolter 2018 Raghunathan et al.] 2018 Bao et al. 2020 However, seminal result by Montasser et al. 2019] shows that any proper learning rule, including ERM, even when trained on an arbitrarily large number of samples, may not return classifier with small adversarially robust risk. These high generalization gaps for the adversarially robust loss have also been observed in practice (Schmidt et al.) 2018). Even worse, empirical studies have shown that classifiers trained achieve worst-case adversarial robustness Raghunathan el al. 2019 Su et al.
exhibit degraded nominal performance (Dobriban et al. 2020
2018
Tsipras et al. 2018 Yang al. 2020 Zhang al.
2019 Robey al. 2022
In light of these difficulties, there has been a recent push to study when proper learning, and more specifically, when learning via ERM is possible for achieving adversarial robustness. The ability to achieve test-time robustness via proper learning rules is important from practical standpoint.
"qqual contributions
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

aligns better with the current approaches used in practice (e.g. (S)GD-trained deep nets), and proper learning algorithms are often simpler to implement than improper ones. In this vain, AAstiani et al.
[2022] and Bhhatacharjee et al. [022] consider adversarial robust learning in the tolerunt setting, where the error of the learner is compared with the best achievable error with respect to a slightly larger perturbation set. They show that the sample complexity of tolerant robust learning can be significantly lower than the current known sample complexity for adversarially robust learning and that proper learning via ERM can be possible under certain assumptions. Additionally, Ashtiani et al. 2020 provide some sufficient conditions under which proper robust learnability of VC classes becomes possible under a PAC-type framework of semi superviie learning. More recently, AAtias 2022 show that finite VC dimension is sufficient for proper semi- supervvie adversarially robust PAC learning if the support of the marginal distribution instances is known. On the other hand. Attias and Hanneke 2023) study the adversarially robust PAC learnability of real-valued functions and show that every convex function class is properly learnable.
eet al.
In a different direction, several works have studied the consistency of various surrogates of the
adversarially robust loss (h, (z, u)) ())==M((x) 1 [1h(z) + y} [Awasthi et al. 2022a b 2023
Mao et al.
2023]. while others have considered relaxing its worst-case nature [Robey et al. 2022
ct al. 2020 2021 Laidlaw and Feizi 2019 Rice et al. 2021]. However, the PAC learnabiiyyy of these
relaxed notions of the adversarially robust loss has not been well-studied.
In this paper, study relaxations of the worst-case adversarially robust learning setup from learning-theoretie standpoint. We classify existing relaxations of worst-case adversarially robust learning into two approaches: one based on relaxing the loss function and the other based on relaxing the benchmark competitor. Much of the existing learning theory work studying relaxations of adversarial robustness focus on the latter approach. These works answer the question of whether proper PAC learning is feasible if the learner is evaluated against a stronger notion of robustness. In contrast, we focus on the former relaxation and pose the question: can proper PAC learning be feasible if we relax the adversarially robust loss function itself? In answering this question, we make the following main contributions:
We show that the finiteness of the VC dimension is not sufficient for properly learning natural relaxation of the adversarially robust loss proposed by RRbbyy et al. (2022). Our proof techniques involve constructing a VC class that is not properly learnable.
We give a family of adversarially robust loss relaxations that interpolate between average- and worst-case robustness. For these losses, we use Rademacher complexity arguments relying on the Ledoux -Talagrnd contraction to show that all VC classes are learnable via ERM.
We extend property implicitly appearing in margin theory (e.g., see Mohri et al. 2018 Section 5.4]), which we term "Sandwich Uniform Convergence" (SUC), to show new generalization guarantees for the adversarially robust empirical risk minimizer.
2 Preliminaries and Notation
Throughout this paper we let [k]] denote the set of integers {l....,k] X' denote an instance space. y = (-1,1) 1} denote our label space, and 'D be any distribution over X' x y. Let H C ) denote a hypothesis class mapping examples in X to labels in )
2.1 Problem Setting
In the standard adversarially robust learning setting, the learner, during training time, picks set g C x Of perturbation functions g X' - X' against which they wish to be robust. At test time, an adversary intercepts the labeled example (rr, y), exhaustively searches over the perturbation set to find the worst g E G. and then passes the perturbed instance g(x) to the learner. The learner makes a prediction ÿ and then suffers the loss 1(0 A y}. The goal of the learner is to find hypothesis h E yxx that minimizes the adversarially robust risk Ro D) = B(z,g>~ (,, (x, n))] where (o (Ir, v)) = supges ()((())) # y) is the adversarially robust loss.
"We highlgght that our use of perturbation functions & instead of perturbation sets 24 is without loss of generality (see Appendix foror equivalence).
2

---

In practice, however, such a worst adversary may be too strong and unnatural, especially in high-dimension. Accordingly, we relax this model by considering a lazy, computationally-bounn -ouunded adversary that is unable to exhaustively search over G, but can randomly sample perturbation function 9 ~ μ given access to a measure j over G. this setup, the learner picks both a perturbation set 9 and a measure ls over G. At test-time, the lazy adversary intercepts the labeled example (1,, v). randomly samples a perturbation function ~ μt, and then passes the perturbed instance g(z) to the learner. From this perspective, the goal of the learner is to output hypothesis such that the probability that the lazy adversary succeeds in sampling a bad perturbation function, for any labeled example in the support of D, is small. In other words, the learner strives to be robust to most, but not all, perturbation functions in G.
We highlight that the set 9 and the measure are fixed and chosen by the learner at training time. As a result, the measure μ does not depend on the unperturbed point æ. Allowing the measure to depend on the unperturbed point x: is an interesting future direction that lies between our model and adversarial robustness. Nevertheless, fixing the measure jr is still relevant from a practical standpoint and non-trivial from theoretical standpoint. Indeed, a popular choice for G and μ are l, balls and the uniform measure respectively. These choices have been shown experimentally to strike better balance between robustness and nominal performance [Robey et al. 2022]. Moreover, in Section 3 we show that even when the measure ja is fixed apriori, there are learning problems for which ERM does not always work. This parallels the hardness result from Montasser et al. [019]] who prove an analogous result for adversarially robust PAC learning.
2.2 Probabilistically Robust Losses and Proper Learnability
Given a perturbation set 9 and measure μr, we quantify the probabilistic robustness of a hypothesis h on a labeled example (z, y) by considering losses that are a function of F (g~=[(((((z)) + y). For a labeled example (zz, y) E X' x V. IP g~ [f)) # y] measures the fraction of perturbations in for which the classifier h is non-robust. Observe that Pow [h(g(z)) * y)
- y-y [h(g()))]
is an affine transformation of quantity y/gg-u [xx]] the probabilistically robust margin of h on (xr, y) with respect to (g. (t). Thus, we focus on loss functions that operate over the margin yB [h(g(z))]. One important loss function is the p-probabilistically robust loss.
Gg (I, v)) = (1P (M(g(z)) * v) > p}:
where م E [0. 1). is selected apriori. The p-probabilisstially robust loss was first introduced by Robey al. (2022) for the case when X' R ge(x) I + c. and the set of perturbations (0c : c A for some A C IR. In this paper, we generalize this loss space X' and perturbation set G. As highlighted by Robey et al. (2022). this notion of robustness is desirable it nicely interpolates between worst- and average-case robustness via interpretable parameter while being more computationally tractable compared to existing relaxations.
arbitrary instance
In this work, we are primarily interested in understanding whether probabilistic relaxations of the adversarially robust loss enable proper learning. That is, given hypothesis class H. perturbation set and measure (G, (u), loss function l (h, (z, y)) (yllEgg [f)((=))]) and labeled samples from an unknown distribution D, our goal is to design a learning algorithm A:: : (X' x x))" + H such that for any distribution D over X' V. the algorithm A. given sample of labeled examples from D, finds a hypothesis h E H. with low risk with regards to (g (z)
Definition (Proper Probabilistically Robust PAC Learnability). Let (h, (I, denote an arbitrary probabilistically robust loss function. For any e, (0, 1), the sample complexity of probabilistically robust (e, 5)-lrrnnn H with respect to fg denoted ri(e, o; H, lg is the smallest number m E IN for which there exists a proper learning rule A: (X x xY)) H such that for every distribution D over X x V, with probability at least 1 - ô over S ~ Dm,
ED [Lg. (A(S), (x. v))l < inf ED (& (h, (2. 9))l cc.
NEH
We say that H is proper probabilistically robustly PAC learnable with respect to lg if 5 E (0. 1), nl(e, 8; H. Eg.u) is finite.
3

---

An important class of proper learning rules is ERMs which simply output the hypothesis h E 7 that minimizes the loss f.., over the training sample. In this paper, we ultimately show that for wide family of probabilistically robust loss functions, ERM is a proper learner according to Definition [ On the other hand, in Section S we show that proper probabilistically robust PAC learning is not always possible for the loss function e (h, v)).
2.3 Complexity Measures
Under the standard 0-1 risk, the Vapnik-Chervonente dimension (VC dimension) plays an important role in characterizing PAC learnability, and more specifically, when ERM is possible. A hypothesis class H is PAC learnable with respect to the 0-1 loss if and only if its VC dimension is finite (Vapnik and Chervonenkis [971].
Definition 2 (VC dimension). A set (21,..,, In) X is shattered by H. vy Un E V. 3h H. such that Vi E [n], h(x;)) = yı. The VC dimension of H. denoted (C(H), defined as the largest natural number IN such that there exists set (01,...,,a.) E X that is shattered by H.
One sufficient condition for proper learning, based on Vapnik's s "General Learning" is the finiteness of the VC dimension of binary loss class
Vapnik 2006
C = ((x,))) - E(h, (x, : h E H)
where e(h. (z, y)) is some loss function mapping to f0. 1}. In particular, if the VC dimension of the loss class L finite, then H is PAC learnable with respect
using ERM with sample complexity that scales linearly with VC(C**. ). In this sense, if one can upper bound VC([*) in terms of VC(H), then finite VC dimension sufficient for proper learnability. Unfortunately, for adversarially robust learning. Montasser et al. [2019] show that there can be an arbitrary gap between the VC dimension of the adversarially robust loss class 2 = ((x, y) ~ &g (I, h E H) and the VC dimension
of H. Likewise, in Section 3 we show that for the p-probabilistically robust loss &G... there can also
be an arbitrarily large gap between the VC dimension of the loss class and the VC dimension of the hypothesis class.
As many of the loss functions consider will actually map to values in IR, the VC dimension of the loss class will not be well-defined. Instead, we can capture the complexity of the loss class via the empirical Rademacher complexity.
Definition 3 (Empirical Rademacher Complexity of Loss Class). Let l be loss function, S = {(11, 91 ..., (Ins }n)) E (X' x)y) be any sequence of examples, and L ((x,y) + E(h, (z. v)) h E H) be a loss class. The empirical Rademacher complexity of CH is defined as
(C*) E.
Corf(rs vi)
sup JEEN
i=1
where 01,..., Om are independent Rademacher random variables.
standard result relates the empirical Rademacher complexity to the generalization error of hypothe- ses in H with respect to a real-valued bounded loss function E(h, (æ,,)) Bartlett and Mendelson 2002
Theorem 2.1 (Rademacher-based Uniform Convergence). Lei D be distribution over X x y and (h, (x, y)) < c be a bounded loss function. With probability at least 1 over the sample S ~ D for all h E H. simultaneously.
In(t))
En]((h(z). v) - (s(((((()). w) s 2mm (F)+ +0
(eV
where (s(((((()))))) v)] [s] Einyys {(h(z),)) y) the empirical average of the loss over S.
3 Not All Robust Loss Relaxations Enable Proper Learning
Recall the p-probabillstically robust loss

---

G (h, (z.
== 1(T gnype (h(g(z)) + pt.
and its corresponding risk (h; := ( -Baa))) fo n (h, (z, v)) At a high-level, proper learn- ing under the &G requires finding hypothesis h E H that is robust to at least a p fraction of the perturbations in 9 for each example in the support of the data distribution D.
Which hypothesis classes are properly learnable with respect to L. according to Definition 1 In Appendix B.1 we show that if G is finite, then finite VC dimension is sufficient for proper learning with respect to g. On the other hand, in this section, we show that if G is allowed to be arbitrary, VC dimension is not sufficient for proper learning with respect to & let alone learning via ERM.
Theorem 3.1. There exists (g. such that for every p E [0.1), there exists a hypothesis class H S y with VC(H) S such that H is not properly probabilistically robust PAC learnable with respect to G.
To prove Theorem 3.1 we fix X' = RR, g {gs for all x X' for some 7 > O, and j to be the uniform measure over G. In other words, we are picking our perturbation sets to be l, balls of radius y and our perturbation measures to be uniform over each perturbation set. Note that by construction of G. uniform measure μ over G also induces a uniform measure H, over ((x) == (gs(x)) 9s E g} C RR,, We start by showing that for every P [0, 1), there can be an arbitrary gap between the VC dimension of H and the loss class G = {xx, y) + +G (h (z, : H}.
R |01| S S such that gs(x) x +
Lemma 3.2. For every p E 10,1) and m N, there exists hypothesis class H. S ya such that VC(H) < 1 but VC(C)),)) m.
The proof of Lemma 3.2 is found in Appendix B.2 We highlight two key differences between Lemma 3.2 and its analog, Lemma 2, in Montasser et al. 2019]. First, we need to provide both perturbation set and a perturbation measure. The interplay between these two objects is not present in Montasser et al. (2019) and, apriori, it is not clear that these would indeed be lp balls and the uniform measure. Second, order for a hypothesis to be probabilistically non-robust there needs exist large enough region of perturbations over which it makes mistakes. This is in contrast to Montasser et al. (2019), where hypothesis is adversarially non-robust long there exists one non-robust perturbation. Constructing a hypothesis class that achieves all possible probabilistically robust loss behaviors while also having low VC dimension is non-trivial- large regions of non-robustness while not being too expressive such that VC dimension increases.
need hypotheses be expressive enough have
Next, we show that the hypothesis class construction in Lemma 3.2 can be used to show the existence of hypothesis class that cannot be learned properly. Lemma 3.3 similar to Lemma in Montasser
al. 2019] and is proved in Appendix B.3
Lemma 3.3. For every E [0, and m E N there exists H C yx with VC(H) < such that
for any proper learner A (X x ))* + H: (1) there is a distribution over X x y and
hypothesis h E H. where R g (h*;D) = 0 and (2) with probability at least 1/7 over S ~ D
R (A(S): 1/8.
Finally, the proof of Theorem 3.1 Jses Lemma 3.3
3.d and follows similar idea its analog in Montasser
et al. [2019] (Theorem 1). However, since our hypothesis class construction Lemma 3.2 is different,
some subtle modifications need to be made. We include complete proof in Appendix B.4
4 Proper Learnability Under Relaxed Losses
Despite the fact that VC classes are not p-probabilisstially robust learnable using proper learning rules, framework still enables us to capture wide range of relaxations to the adversarially robust loss for which proper learning is possible.
In particular, consider robust loss relaxations of the form lg, (h, (æ,, v)) = ll [x)(()))) where E(I) R - R a T--Lipschitz function. This class of loss functions general, capturing many natural robust loss relaxations like the hinge loss 1 - yT [h(g(=))], squared loss (y
5

---

Eygny [h(g()))))² - (1 yBu [h(g(=))])? and exponential loss e (Euu-u(( Furthermore, the class of Lipschitz functions R R on the margin ylgggu [b(g(z))) enables us capture levels of robustness between the average- and worst-case. For example, taking (t) -- results in the loss (h, (x, v)) f [h(g())))) g [h(g(x)) & v). corresponding to average- case robustness, or data augmentation. On the other hand, taking ((t) = min( 1 1) for some 2p
p E (0, 1), results in the loss
(ogy [h(g())) + yl
( (h, (x, v)) EyyEgrn [h(g(=)))) min
which corresponds to a notion of robustness that becomes stricter as approaches O. We note that some of the losses in our family were studied by Rice al. [202T]. However, their focus was on evaluating robustness, while ours is about (proper) learnability.
Lemma shows that for hypothesis classes H with finite VC dimension, for any (G, all L-Lipschitz loss functions & (h, (at, y)) enjoy the uniform convergence property.
Lemma 4.1 (Uniform Convergence of Lipschitz Loss). Let H. be a hypothesis class with finite VC
dimension, (G,p) p.) be a perturbation set and measure, and fg.uh, (h, v)) = e (ylBgr [h(g(>)))) such that 8 IR + IR is
With probability at least 8 over sample ~ D
of size 0 (VC(H))2 lnf ()il(())) )). f.oo all h E H simultaneously.
EDD (, (2, (2, Iss (6g.p (ar, []) Sc.
Proof. Let VC(H) = d and S = (111111),,..........)))),))))1,, (Im, Vm }mm) be a set of examples drawn i.i.d from D. Define the loss class L ((x,)) la (I, h H). Observe that can reparameterize -y as the composition of L-Lipschitz function {(x) and the function class F = {1z, v) yrg [h(g(z))] h E H}. By Proposition 2.1 to show the uniform convergence property of (h, (x, y)), it suffices to upper bound Rm ( = Am o F(r the empirical Rademacher complexity the loss class. Since is L-Lipschitz, by Ledoux- Maaluu--aaaggand'ss contraction principle [Ledoux and Talagrand 1991 it follows that 2tm (L = Rm FLo S L. (F
Thus, it actually suffices to upperbound Rm (F( instead. Starting with the definition of the empirical Rademacher complexity:
Rmm (FH,
E Eow
sup hE7
Σ B.yy (M(((x)))
m
E Baw
sup he7
I Eynu
ash(o(z;))
m
1 m
< Eggn
Bowf
sup bCH
xch(((aa)))
where the last inequality follows from Jensen's incquality and Fubini's Theorem. Note that the
quantity 1, [= (SuPRc Em ozh(g(2x))] is the empirical Rademacher complexity of the hypothesis class H over the sample (g(x1) (((=)))...g9(mm)) drawn i.i.d from the distribution defined by first sampling from the marginal data distribution, x Dxx and then applying the transformation
g(x). By standard VC arguments, (H) < 0 ( (V /din : which implies that (FH g.p) S
E Syny
Rm (70)
<
din( m
Putting things together, we get R (F2,,) Rm (l FH g, <
0 Int 7
Proposition 2.1 then implies that with probability 1 - 8 over sample S ~ n
Ar2 In( In(
of size m 0
have
Ep (e ())) - EEs 16g,11 (x, (2,,)))] se

---

for all h E H. simultaneously.
Uniform convergence of Lipschitz-losses immediately implies proper learning via ERM.
Theorem 4.2. Let (h, (x,y)) function. For every hypothesis class H. perturbation set and measure (G, p.), and (c, (0, the proper learning rule A(S) arg meH FEs ( (z. for any distribution D over X x V, achieves, with probability at least å over a sample S ~ DD of size n 2 O (VC(H)) luf 4 +(u the guarantee
&yyTEru [+(g())]]) such that & R. + R L-Lipschitz
ED (A(S), (2,, v))l S inf ED (&g. (1, (1r, v)) + NEH
At a high-level, Theorem 4.2 shows finite VC dimension is sufficient for achieving robustness between the average- and worst-case using ERM. In fact, the next theorem, whose proof can be found in Appendix C.2 shows that finite VC dimension may not even be necessary for this to be true. The proof of Theorem 4.3 involves considering the well-known infinite VC class H = {ar -> sign(sin( (wx)) w E IR and picking (G, ()) such that Egny [h(g(z)) is essentially constant in x for all hypothesis E H.
Theorem 4.3. Let (h, v)) EyyTog [x(g()))] such that & : + IR is L-Lipschitz function. There exists H. and (G.p) such that VC(H) = co but H is still properly learnable with respect to fg (h, v)).
Together, Theorems and showcase an interesting trade-off. Theorem indicates that by carefully choosing (L), the complexity of H can be essentially smoothed out. On the other hand, Theorem 4.2 shows that any complexity in (G, jt) can be smoothed out if H has finite VC dimension. This interplay between the complexities of H. and (G, p.) closely matches the intuition of Chappelee et al. [2000] in their work on Vicinal Risk Minimization. Note that the results in this section do not contradict that of Section because fg (h. (z. 3)) is non-Lipschitz function of yl [h(g(z))]
11),
We end this section by noting that Lipschitzness of l... is sufficient but, in full generality, not necessary for proper learnability. For example, the loss function that completely ignores (G, μ) and just computes the 0-1 loss is not Lipschitz, however, it is learnable via ERM when the VC dimension of H. is finite.
5 Proper Learnability Under Relaxed Competition
The results of Section show that relaxing the adversarially robust loss may not always enable proper learning, even for very natural robust loss relaxations. In this section, we show that this bottleneck can be alleviated if we also allow the learner compete against a slightly stronger notion of robustness. Furthermore, we expand on this idea by exploring other robust learning settings where allowing the learner to compete against a stronger notion of robustness enables proper learnability. We denote this type of modification to the standard adversarially and probabilistically robust leaning settings as robust learning under relaxed competition. Prior works on Tolerantly Robust PAC Learning [Ashtiani] 2022 Bhattacharjee et al. 2022 mentioned in the introduction fit under this umbrella.
et al.
which we term as Sandwich Uniform Convergence (SUC). Roughly speaking. SUC provides a sufficient condition under which ERM outputs a predictor that generalizes well with respect a stricter notion of loss. A special case of SUC has implicitly appeared in margin theory (c.g., see Mohri et al. [2018, Section 5.4]), where one evaluates the 0-1 risk of the output hypothesis against the optimal margin 0-1 risk.
Our main tool in this section is Lemma
Lemma 5.1 (Sandwich Uniform Convergence). Let e (h, (x. v)) and (h, (I. v)) be bounded, non- negative loss fiunciinns such that for all h E H and (x, v) E X' x Y, we have & (h, (x. v)) S (2 (I, v)) < 1. If there exists a loss function E(h, (x,v) such that (i (2, v)) S E(h, (I, v)) < E2(h, (z, v)) and E(h, (a,, v)) enjoys the uniform convergence property with sample complexity nle, 8), then the learning rule A(S) infReM IEs [E2 (h, (x. v))l achieves, with probability 8 over sample S ~ DD of size m 2 n(c/2, 8/2) + O In( the guarantee
Ep (A((), (z. m) <
inf ED (Ba,,, (a, w))l + NER
7

---

Proof. Let A(S) infaen Es (6, (z, By uniform convergence of E(h, (a, B)), we have that for sample size m = n( à. } with probability at least - 2. over sample S ~ Dm,, for every hypothesis h E H simultaneously,
ED [(hh, (z, w))} - Es [(ch, (1),)))))))
2
In particular, this implies that for h A(S), we have
ED ((h, (z, m))} S Es [(ch (1, (v. 2
Since, (h, (2, (x, v)) s E(h, (z, y) - (2 (z. B)). we have that Ep E (h, (ar, I Bs [62(h" (x,,)))
2
where h- infneH Ep (h, (z. v))]. It now remains to upper bound Eg [f2(h" (x. y))l with high probability. However, standard Hoeffding bound tells us that with probability 1 1- over a sample S of size ( (1_( iEs (62("", (x. y))] s ED (e2(h", (r, v))l + 5- Thus, by union bound, we get that with probability at least 1 - 6, ED (h, (a, v)) & IED (E2 (x. + e, using a sample of size m(c/2,6/2) + +0( + 2)).
Lemma 5. only requires the existence of such sandwiched loss function that enjoys uniform convergence we do not actually require it to be computable. In the next two sections, we ex- ploit this fact to give three new generalization guarantees for the empirical risk minimizer the adversarially robust loss (h, (zz, v)) and p-probabilisstcally robust loss C, (z, y)), here- after denoted by RERM(S;9) = arg min Iss (h, ())] and PRERM (9, p) = arg argmin Es (6,,(h,, (s. (1) respectively.
5.1 (p.p" (o.p"))-Prbabbilssttcall Robust PAC Learning
In light of the hardness result of Section 3 we slightly tweak the learning setup in Definition by allowing AA to compete against the hypothesis minimizing the probabilistic robust risk at a level p² p. Under this further relaxation, we show that proper learning becomes possible, and that too, via PRERM. In particular, Theorem 5.2 shows that while VC classes are not properly p p-probabilisticaly robust PAC learnable, they properly (p.p"")-rrbbbbill probabiliisticall robust PAC learnable.
Theorem 5.2 (Proper (p, p" prrobabbiiiisstccccl Robust PAC Learner). Let 0 S p² <. Then, for every hypothesis class H. perturbation set and measure (), and (c, learning rule A(S) = PRERM(S; (G, p), p²), for any distribution D over X' x Y, achieves, with
(0,1),, the proper
VE00
In( To-o ye -m(())
probability at least - 6 over sample S ~ DD of size T 2 0
the
guarantee
(A(S):) S inf Re REH R
(h; +
In contrast to Section where proper learning is not always possible, Theorem 5.2 shows that if we compare our learner to the best hypothesis for slightly stronger level of probabilistic robustness, then not only is proper learning possible for VC classes, but it is possible via ERM. Our main technique to prove Theorem 5.2 is to consider a different probabilistically robust loss function that is (I) Lipschitz function of yEgrr [h(g(z)) + y] and (2) can be sandwiched in between G. and 60 &. Then, Theorem
5.2 follows from Lemma 5.1 The full proof is in Appendix D.I
5.2 (p. Proballlbballll Robust PAC Learning
Can measure-indepeedeet learning guarantees be achieved if we instead compare the learner's s probabilistically robust risk Re to the best adversarially robust risk Rg over H? We answer this in the affirmative by using SUC. We show that if one wants to compete against the best hypothesis for the worst-case ad adversarially robust risk, it is sufficient to run RERM.
8

---

Theorem 5.3 (Proper (p. Prooaabbbilissllllly Robust PAC Learner). For every hypothesis class H. perturbation set 9, and (c, E (0. the proper learning rule A(S) RERM(S; for any measure Is over G and any distribution DD over X x Y, achieves, with probability at least 1 5 over veg0
In( 1 )11(()))
a sample S ~ DD size n 2 0
the guarantee
R2 (A(S):
& inf Rg(h; + hEHt
The proof of Theorem 5.3 can be found in Appendix D.2 which follows directly from Lemma 5.1 by suitable choice of the sandwiched loss f. We make few remarks about the practical importance of Theorem 5.3] Theorem 5.3 implies that for any pre-specified perturbation function class G (for example bp balls), running RERM is sufficient to obtain a hypothesis that is probabilistically robust with respect to any fixed measure μ over G. Moreover, the level of robustness of the predictor output by RERM, as measured by 1- p. scales directly with the sample size- the more samples one has, the smaller can be made. Alternatively, for fixed sample size m, desired error and confidence 5, one to back-solve the robustness guarantee p.
can use the sample complexity guarantee in Theorem 5.3
We highlight that the generalization bound in Theorem 5.3 is a measure- greassreeiideppndeev guarantee. This means that p does not quantify the level of robustness of the output hypothesis with respect any one particular measure, but for any measure. This is desirable, as in contrast to the previous section, the here more succinctly quantifies the level of robustness achieved by the output classifier. Lastly, we highlight that while the sample complexity of ad aevrsaarilly robust PAC learning can be exponential in the VC dimension of H. [Montasser al., 2019), this is not the case for (p, probabbiiiittclll robust PAC learning, where we only get a linear dependence on VC dimension.
5.3 Tolerantly Robust PAC Learning
In Tolerantly Robust PAC Learning (Bhattacharjee al.) 2022 Ashtiani al. 2022
the learner's
adversarially robust risk under a perturbation set G is compared with the best achievable adversarially robust risk for a larger perturbation set G' D G. AAshtaaii et al. (2022 study the setting where both G and G' induce Ep balls with radius r and (1 + 7) respectively. In the work of BBattacharjee et al. [2022). G is arbitrary, but G' is constructed such that induces perturbation sets that are the union of balls with radius that cover G. Critically, [Bhattacharjee et al. (2022) show that, under certain assumptions, running RERM over a larger perturbation set G is sufficient for Tolerantly Robust PAC learning. In this section, we take slightly different approach to Tolerantly Robust PAC learning. Instead of having the learner compete against the best possible risk for a larger perturbation set, we have the learner still compete against the best possible adversarially robust risk over G, but evaluate the learner's adversarially robust risk using a smaller perturbation set g' C G.
For what G' C G is Tolerantly Robust PAC learning via RERM possible? As an immediate result of Lemma 5.1 and Vapnik's "General Learning", finite VC dimension of the loss class D3 {(x., y) + fg- (xr y)) h E H3 is sufficient. Note that finite VC dimension of Z3 implies that the loss function kg. (h, (z,z)) enjoys the uniform convergence property with sample complexity
) e²
O
Thus, taking (h, (I, v)) = E(h, (I, = lg (h, (z, v)) and (2,,, (s, v)) =
(g v)) in Lemma 5.1 we have that if there exists a G' c 9 such that VC(CK) cc, then with probability 1 8 over sample S ~ D of size = vC(c3))+n(3))
Rg (A()::) S inf Rg (h; D) +e,
heH
where A(S) RE).
Alternatively, if g' C G such that there exists finite subset G C 9 where (h, (xc, v)) S (g, (I), then Tolerantly Robust PAC learning via RERM is possible with sample complexity that scales according to O VC(H) (og((())+ ). This result essentially comes from the fact that 2
the VC dimension of the loss class for any finite perturbation set ğ incurs only a log(le)) blow-up from the VC dimension of H. (see Lemma 1.1 in Attias et al. 2021 Thus, finite VC dimension of

---

H. implies finite VC dimension of the loss class Cx which implies uniform convergence of the loss (g, (z, y)), as needed for Lemma 5.1 to hold.
We now give an example where such a finite approximation of G' is possible. In order to do so, we will need to consider metric space of perturbation functions (g. d) and define a notion of "nice" perturbation sets, similar "regular" hypothesis classes from Bhattacharjee
al. 2022
Definition 4 (r-Nice Perturbation Set). Let H be a hypothesis class and (G, d) metric space of perturbation functions. Let Br(g) := {g' E G d(g,g') S r denote closed ball of radius centered around g G. We say that G' E G', there exists g" E G, such that E (r(g") and (z)()) h(g' (x)) for all g' E B,(gg).
r-Nice with respect to H. ifr all E X, H. and
Definition 4 prevents a situation where a hypothesis h E H is non-robust to an isolated perturbation function g G' for any given labelled example (x, y) E X x V. If hypothesis h is non-robust to a perturbation g E G". then Definition asserts that there must exist a small ball of perturbation functions in over which h is also non-robust. Next, define the covering number.
Definition 5 (Covering Number). Let (M, d) be metric space, let K. C M be subset, and > 0. Let (x) = {a' E M: d(x,x') S r denote the ball of radius r centered around x E M. subset C C C.Mi is r-covering of K. if C Uoec B,(c). The covering number K, denoted (K, d), is the smallest cardinality of any r-covering of K.
Finally, let G2y USER (2r denote the union over all balls of radius 2r with centers in G'. Theorem th4 then states that if there exists a set G' that is r-Nice with respect H. then Tolerantly Robust PAC learning is possible via RERM with sample complexity that scales logarithmically with (g d).
Theorem 5.4 (Tolerantly Robust PAC learning under Nice Perturbations). Let H yx be hypothesis class and (g, d) be metric space of perturbation functions. Given a subset G' C G such that g' r-Nice with respect H. then the proper learning rule A(S) RERM(S; 9), for any distribution D over X x V, achieves, with probability at least - 5 over a sample S ~ DD of size VC(H) log(N, (g +l)++
n 2 0
the guarantee
Rg (A(S):D) I inf Rg(h; D) +
NEH
In Appendix D we give full proof and show that Cp balls are r-Nice perturbation sets for robustly learning halfspaces. Note that Theorem 5.4 does not require apriori knowledge of the r-Nice perturbation set G', but just its existence. Therefore, Theorem 5.4 applies the largest possible r-Nice perturbation subset of G. This is important from practical standpoint as computing an r-Nice perturbation set might not be computationally tractable. Accordingly, while RERM may not be proper adversarially robust PAC learner [Mnnaasser et al., 2019) Theorem 5.4 shows that RERM is proper tolerantly robust PAC learner.
Discussion
In this work, we show that there exists natural relaxations of the adversarially robust loss for which finite VC dimension is still not sufficient for proper learning. On the other hand, we identify large set of Lipschitz robust loss relaxations for which finite VC dimension is sufficient for proper learning. In addition, we give new generalization guarantees for RERM. As future work, we are interested in understanding whether our robust loss relaxations can be used mitigate the tradeoff between achieving adversarial robustness and maintaining high nominal performance. In addition, it is also interesting to find a combinatorial characterization proper probabilistically robust PAC learning with respect to "
Acknowledgements
We acknowledge the support of NSF via grant IIS-2007055. We also acknowledge Idan Attias for introducing us to Tolerantly Robust PAC Learning. VR acknowledges the support of the NSF Graduate Research Fellowship.
10

---

References
Hassan Ashtiani. Vinayak Pathak, and Ruth Urner. Black-box certification and learning under adversarial perturbations. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 388-398. PMLR, 13-18 Jul 2020.
Hassan Ashtiani, Vinayak Pathak, and Ruth Urner. Adversarially robust learning with tolerance. arXiv preprint arXiv:2203.0000 2022.
Idan Attias and Steve Hanneke. Adversarially robust pac learnability of real-valued functions. 2023.
Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for adversari- ally robust learning. 2021.
Idan Attias, Steve Hanneke, and Yishay Mansour. A characterization of semi-supervised adversarially robust pac learnability. Advances in Neural Information Processing Systems, 35:23646-23633 2022.
Pranjal Awasthi, Angi Mao, Mehryar Mohri, and Yutao Zhong. H-consistency bounds for surrogate loss minimizers. In International Conference on Machine Learning, pages 1117-1174. PMLR, 2022a.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Multi-class h-consistency bounds. Advances in neural information processing systems, 35:782-795, 2022b.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statistics, pages 10077-10094. PMLR, 2023.
Han Bao, Clay Scott, and Masashi Sugiyama. Calibrated surrogate losses for adversarially robust classification. In Conference on Learning Theory, pages 408 158-451. PMLR, 2020.
Peter Bartlett. Lecture notes in theoretical statisties, 2013.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3NNo)):4633433 2002.
Robi Bhattacharjee, Max Hopkins, Akash Kumar, Hantao Yu, and Kamalika Chaudhuri. Robust empirical risk minimization with tolerance. arXiv preprint 2X.x:22200000335 2022.
Olivier Chapelle, Jason Weston, Léon Bottou, and Vladimir Vapnik. Vicinal risk minimization.
Advances in neural information processing systems, 13, 2000.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 31, 2018.
Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey. Provable tradcoff's in adversar- ially robust classification. arXiv preprint arXiv:2006. 05 161, 2020.
Cassidy Laidlaw and Soheil Feizi. Funetional adversarial attacks. Advances neural information processing systems, 32, 2019.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. arXiv preprint vrXiv:2007.01162. 2020.
Tian Li, Ahmad Beirami, Maziar Sanjabi. and Virginia Smith. On tilted losses in machine learning: Theory and applications. arXiv preprint arXiv:2109.0614) 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 776600603. 2017.
11

---

A Mao, M Mohri, and Y Zhong. Cross-entropy loss functions: Theoretical analysis and applications. arxiv. arXiv preprint arXiv:2304.07288, 2023.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Ve classes adversarially robustly learnable, but only improperly. Conference on Learning Theory, pages 2512-2530. PMLR, 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. arXiv preprint arXiv:1801.099 100118801..94,,, 2018.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Adversarial training can hurt generalization. arXiv preprint arXiv:9906.000
2019.
Leslie Rice, Anna Bair, Huan Zhang, and J Zico Kolter. Robustness between the worst and average case. Advances Neural Information Processing Systems, 34:27840-27851, 2021.
Alexander Robey, Luiz FO Chamon, George J Pappas, and Hamed Hassani. Probabilistically robust learning: Balancing average-and worst-case performance. arXiv preprint arXiv:2202.01 /36, 2022.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. Advances in neural information processing systems, 31, 2018.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin- Yu Chen, and Yupeng Gao. Is robustness the cost of accuracy?-a comprehensive study on the robustness of 18 deep image classification models. In Proceedings of the European Conference on Computer Vision (ECCV), pages 631 2018.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint 1rXiv:1805.12133 2018.
Vladimir Vapnik. Estimation of dependences based empirical data. Springer Science & Business Media, 2006.
Vladimir Naumovich Vapnik and Aleksei Yakovlevich Chervonenkis. On uniform convergence of the frequencies of events their probabilities. Teoriya Veroyatnostei i Primemeniya, 16(2):264-279, 1971.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International conference on machine learning, pages 5286-5295. PMLR, 2018.
Yao- Yuan Yang. Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. Advances in neural information processing systems, 33:8588-8601. 2020.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pages 7472-7482. PMLR, 2019.
12


Reviews:
[{"review_id": "zfn3zDDahk", "reviewer": "Reviewer_yAnv", "summary": "This paper studies the setting of robust PAC learning to test time attacks, using a relaxed notion of robustness on average instead of robustness to the worst-case attack.  \n\nThe contributions are as follows. \n\n-Negative result: even when using the relaxed notion of robustness, improper learning is impossible. This is a stronger result from the example in the worst-case setting [Montasser et al. 2019]. Moreover, this is achieved by a natural example of $\\ell_p$ balls and the uniform measure. \nThe intuition is that the non-Lipschitzness of the 0-1 loss enforces to use improper learning. \n\n-Positive results: \n1. When considering Lipschitz loss functions, uniform convergence hold, and as a result, ERM is sufficient for learnability. \n2. Instead of relaxing the robust loss, it is possible to relax the benchmark we compare to, i.e. the best function in the class but with a smaller parameter in the probabilistic loss. This is similar to the setup of Tolerant Robust PAC Learning. ", "questions": "The description of the model might be confusing. I will explain my point of view. \nIn the standard setting, the set of possible perturbations is fixed and known to the learner. It's not chosen by an adversary, it's just the possible attacks the learner is aiming to protect from at test time. An adversary would just pick the set of all possible perturbations. \n\nIn this model, is the set G and measure $\\mu$ being chosen at training time and known to the learner? If so, that makes sense to me and should be clear in the model.\nWhat's a reasonable choice measure? is it representing the importance of each $g$? I think that some motivation is missing.\n\nThe connection between the average case and worst case model is through using the  $\\rho$-probabilistically robust loss, maybe it should be mentioned before section 3. This is a very important explanation for defining the model of robustness on average!\n\nSome definitions are used throughout the paper. It could improve the readability if those be numbered and referred to when used. \nFor example, the risk under the probabilistic robust loss (line 116) is used in section 5. It takes some time to find the definition. \n\nMany references are missing. For example, \nH-consistency bounds for surrogate loss minimizers (ICML 2022),\nMulti-class H-consistency bounds (NeurIPS 2022),\nTheoretically grounded loss functions and algorithms for adversarial robustness (AISTATS 2023),\nCross-Entropy Loss Functions: Theoretical Analysis and Applications (ICML 2023),\nA Characterization of Semi-Supervised Adversarially Robust PAC Learnability (NeurIPS 2022),\nAdversarially Robust PAC Learnability of Real-Valued Functions (ICML 2023),\nOn the hardness of robust classification (JMLR)\n...and many more!", "limitations": "There are no limitations. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper provides nice contributions to the literature on robust learning, by finding natural relaxations on the robust model that allows learning similar to non-robust learning. ", "weaknesses": "See Questions. \nThe writing can be improved. This paper has many good ideas, but sometimes it is hard to follow them.\nAlso, many relevant references from theory on robust learning are missing that should be included as related work. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding that this paper provides a nice contribution to the literature on robust learning. \n\n**Q1**:  *\"In this model, is the set G and measure μ being chosen at training time and known to the learner?\"*\n\nA1: Yes, the set G and the measure \\mu are chosen at training time and known to the learner. Moreover, the same G and measure \\mu are used to evaluate the model at test time. We will make this more clear in the main text of the camera-ready version. \n\n**Q2**: *\"What's a reasonable choice measure? is it representing the importance of each g?\"*\n\nA2: If G encodes a \\ell_p ball, then a reasonable choice of measure \\mu over G could be the uniform measure. In this case, this measure would encode the idea that every perturbation is equally important. For example, Robey et al. use \\ell_infty balls with the uniform measure in their experiments training probabilistically robust neural networks. Another reasonable choice of measure \\mu could be one whose mass concentrates at the center of the ball but decays radially as you move out towards the edge of the ball. This measure would encode the idea that perturbations near the center of the ball are more important than those further out. We will make sure to include this motivation/intuition in the main text of the camera-ready version. \n\n**Q3**: *\"The connection between the average case and worst case model is through using the  ρ-probabilistically robust loss, maybe it should be mentioned before section 3.\"* \n\nA3: We thank the reviewer for this comment and will make sure to include a discussion of this connection before Section 3 in the camera-ready version. \n\n**Q4**: *\"Some definitions are used throughout the paper. It could improve the readability if those be numbered and referred to when used.\"* \n\nA4: We agree with the reviewer and will make the recommended changes in the camera-ready version. \n\n**Q5**: *\"Many references are missing\"*\n\nA5: We thank the reviewer for pointing out these missing references. We will make sure to discuss these works and reference them in the camera-ready version. \n\n\n\n\n"}, {"review_id": "HLcwOl8eHD", "reviewer": "Reviewer_8idw", "summary": "This paper studies the proper robust learnability under relaxation of the (usual) worst-case/all powerful adversary assumption. \n\n- The authors first show that finite VC dimension is not sufficient to enable proper learnability under the relaxation proposed by Robey et al. (2022).\n- For another generalization of worst-case relaxations, the authors show that finite VC dimension enables proper robust learnability \n- The authors study the \"relaxed competition\" setting where the hypothesis is compared to the optimal hypothesis under a slightly stronger notion of robustness, proper learning guarantees are possible \n", "questions": "Could you address point 2 above? ", "limitations": "If point 2 in \"Weaknesses\" is correct, it would be worth including as a limitation of the work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written, clear and easy to follow\n- I believe the topic and results are of interest to the learning theory community, \n- Relaxing the worst-case analysis is well-motivated", "weaknesses": "1. It seems perhaps a considerable number of proofs rely on standard techniques\n2. Is it a limitation / too big of a relaxation to have the adversary pick a perturbation independently of the unperturbed point $x$? (l.70-71) Unless $\\mu$ can be defined for each $x$. Either way, it would be worth discussing and clarifying this point in the main body (unless I have missed this somewhere).  \n\nOverall I think even if the potential limitations pointed out above are right, the paper still offers a good contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting that the results in this work are of interest to the learning theory community and that relaxing the worst-case analysis is well-motivated. \n\n**Q**: *\"Is it a limitation / too big of a relaxation to have the adversary pick a perturbation independently of the unperturbed point x? (l.70-71) Unless μ can be defined for each x. Either way, it would be worth discussing and clarifying this point in the main body (unless I have missed this somewhere).\"*\n\nA: In our model, the measure \\mu is fixed beforehand and does not depend on the unperturbed point x. We will make sure to clarify this point in the main text of the camera-ready version. Allowing the measure to depend on the unperturbed point x is an interesting future direction that lies between our model and adversarial robustness. That said, we believe that having one fixed measure is natural from a practical perspective.  In practice, both G and \\mu will be picked during training time (for example Robey et al. pick \\ell_infty balls and the uniform measure), and it is unclear why one would want to weight different perturbations differently for different instances. One would also need to then define a measure for each instance, which might not be computationally feasible. In addition, even when the same fixed measure \\mu is used for all unperturbed points x, we show that there are natural losses where proper learning is not always possible. Lastly, we note that our model of having the measure \\mu fixed beforehand can be motivated by considering a computationally lazy/bounded adversary who may not be able to define and sample from different measures. We provide this motivation in lines 68-74 of the main text. We will further discuss and clarify these points in the main text of the camera-ready version. \n"}, {"review_id": "j2Qum7a9Hz", "reviewer": "Reviewer_rPBv", "summary": "This paper investigates the relaxations of the worst-case robust loss to make VC classes properly PAC learnable. Firstly, this paper shows that an exsiting and natural relaxation does not work. Then, the paper gives a family of robust loss relaxations that interpolate between average- and worst-case robustness. Finally, the paper studies the generalization guarantees for the adversarially robust empirical risk minimizer.", "questions": "- Would you please show some ideas about the proof of Lemma 3.2? When considering this problem, is it the case that you first consider giving an upper bound of the VC dimension of $\\mathcal{L}$ in terms of the VC dimension of $\\mathcal{H}$ or the case that you directly try to construct the counterexample? Would you please show some high-level thoughts about adapting the proof of Omar to the case in this paper?\n- Would you please provide some high-level insights about the construction of the counterexample in Theorem 4.3?", "limitations": "No.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper shows that an exsiting and natural relaxation does not work.\n- This paper gives a family of robust loss relaxations that interpolate between average- and worst-case robustness and shows that they make the VC classes properly learnable. The results are interesting.\n", "weaknesses": "- Lack of descriptions about the high-level intuitions (please refer to the questions part).\n- Some minor issues. The label space is defined as $\\mathcal{Y} = \\\\{ -1, 1 \\\\}$, however, in the proof of Lemma 3.2, the paper uses $\\\\{ 0,1 \\\\}$. In Lemma 4.1, it seems that $\\ell$ needs to be bounded but the paper ignores it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding the results in this work to be interesting. \n\n**Q1**: *\"Minor issues.\"* \n\nA1: We thank the reviewer for pointing out these issues. We will fix them in the camera-ready version. \n\n**Q2**: *\"Would you please show some ideas about the proof of Lemma 3.2? When considering this problem, is it the case that you first consider giving an upper bound of the VC dimension of L in terms of the VC dimension of H, or the case that you directly try to construct the counterexample? Would you please show some high-level thoughts about adapting the proof of Omar to the case in this paper?\"*\n\nA2: We will make sure to include a proof sketch of Lemma 3.2 in the camera-ready version of the paper. In order to prove Lemma 3.2, we directly construct a counter-example where VC(H) <=1 but VC(L) >= m. We do include some high-level thoughts about the differences between our construction and Montasser et. al's construction in Lines 162-173. However, we will expand more on this in the camera-ready version. In Montasser et. al's proof, in order for a hypothesis to have an adversarial robust loss of 1 on an instance x, it was sufficient to have just one perturbation in the ball on which the hypothesis was non-robust. However, in our case, in order for a hypothesis to have a probabilistic robust loss of 1 on an instance x, we need the hypothesis to be non-robust on a sufficiently large number of perturbations in the ball. Accordingly, the main challenge/contribution in our paper is how to construct these regions of non-robustness such that the VC dimension of the probabilistic robust loss class can be made arbitrarily large, yet the VC dimension of H remains small. \n\n\n**Q3**: *\"Would you please provide some high-level insights about the construction of the counterexample in Theorem 4.3?\"*\n\nA3: We thank the reviewer for pointing this out. For the camera-ready version, we will include a proof sketch and some high-level insights about the construction of the example relevant to Theorem 4.3. The idea is to consider the well-known infinite VC class H = {sign(sin(wx)) : w in R }, but to pick a G and \\mu, such that the expectation E[h(g(x))] is essentially constant in x for all hypothesis h in H. We provide the exact example in Appendix B.2. \n"}, {"review_id": "iPZfsoUzjY", "reviewer": "Reviewer_dXD9", "summary": "This paper initiates the study of a new kind of PAC learning: probabilistically robust PAC learning.  The authors show that the finiteness of the VC dimension of the function class is not sufficient to obtain a proper learning rule in this new PAC learning setup.  However, they show that for Lipschitz losses that interpolate between the average and worst case, proper learning is possible given finite VC dimension.  They also consider the settings of adversarially robust PAC learning and tolerant PAC learning; ultimately, this results in several extensions to previous works on these topics.", "questions": "Is it fair to say that the fact that the probabilistic robustness loss function is non-Lipschitz is the reason behind Theorem 3.1.  In other words, is Lipschitzness a necessary condition?  My understand from Section 4 is that it is sufficient, but it may not be necessary.\n\n**Overall assessment.**  Overall, I do not see a strong reason for this paper not to be accepted.  It studies a new problem and the insights are novel and interesting.  There are some drawbacks regarding the presentation, but one imagines that these can be easily ironed out.  ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**New problem setting.**  This is a new problem.  The authors consider several recent results in the robustness literature concerning robustness between the average and worst case, and they form a new definition of probabilistically robust PAC learning.  I imagine that this is a direction that other may be interested in, and therefore this constitutes an interesting contribution.\n\n**Non-proper learnability.**  Perhaps the most interesting/surprising result here is that the finiteness of the VC dimension of the function class is not sufficient for proper $\\rho$-probabilistic robust PAC learning.  This implies that both probabilistic and adversarial robustness do not easily admit proper learning rules.  This is somewhat surprising, given previous empirical results that find that probabilistic robustness does not come at the cost of degraded nominal performance with respect to an empirical risk minimizer.  Building on this, it is also interesting that there do exist interpolation schemes that do admit proper learning rules given finite VC dimension.  In this way, this paper is a first step toward characterizing a hierarchy of interpolating losses based on which ones admit proper learning rules.  It would be interesting to know whether other interpolation methods, e.g., those in [Rice et al., 2021] and [Li et al., 2020] also engender proper learning rules.\n\n**Technical rigor.**  The paper seems technically sound to me.  The proofs in the appendix are well-structured, and the array of tools used in the appendix may be of broader interest to the community.", "weaknesses": "**Unevenness of the presentation.**  There's a certain unevenness about the presentation of the main results.  In general, the trend is that as one gets further into the paper, the results get harder to parse.  This doesn't seem to be a function of the complexity of the results; rather, it seems as if less space was dedicated to fully explaining the results that appear later in the paper.  \n\nFor instance, the results in Section 3 are outlined in detail.  Theorem 3 tells us that there exists hypothesis classes for which $\\rho$-probabilistically robust PAC learning is not possible, and the proof is sketched almost in full.  However, by the time we reach Section 5, the results are stated with less explanation.  The text becomes quite difficult to read because nearly every equation on pages 8-9 is inline.  Definitions and theorems seem to be crammed in, and the paper ends without discussing the implications of the final theorem.  I think that readibility would be greatly improved if the authors moved the proofs from Section 3 to the appendix, and (i) expanded more on the results later in the paper, (ii) broke up the texts by putting long equations on their own lines (i.e., not in-line), and (iii) adding a discussion section where the implications of the results are discussed.  In its current form, the paper ends rather abruptly, and I think point (iii) would help to ameliorate this.  \n\n**Writing and notation.**  I think that the presentation could be improved in several ways.  Here are some points that occurred to me while reading the paper:\n\n* It would also be helpful if the authors could use equation numbers.\n* It's confusing that the authors introduce VC dimension and Rademacher complexity, but a definition arguably more central to this paper -- the definition of a *proper* learning rule -- was omitted.\n* ERM seems to be used to denote \"empirical risk minimization\" (throughout) and \"empirical risk minimizer\" (line 95).  I think it'd be worth picking one.\n* What is $(\\mathcal{X}\\times\\mathcal{Y})^\\star$, i.e., what does the *\\star* denote?\n* Why is there a change in notation from $\\mathcal{L}^{\\mathcal{H}}$ to to $\\mathcal{F}$ in Definition 2?\n\n**Section 5.3.**  When reading, I wasn't sure how Section 5.3 fit in with the rest of the paper.  Whereas the other sections of the paper focus on proper learnability for probabilistic robustness and generalizations which interpolate between average and worst-case robustness, Section 5.3 seems to address questions that are somewhat different in spirit.  I suppose one could argue that in the tolerance setting, reducing $\\mathcal{G}$ to a singleton set containing the identify function would show that this paradigm can interpolate between the standard PAC model and robust variants, but this connection feels tenuous.  Perhaps the authors could elaborate more on why this section fits in with this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding the results to be a surprising/interesting contribution, this setting to be interesting to others, and the array of tools used to be of broader interest to the community. \n\n**Q1**: *\"Unevenness of the presentation.\"* \n\nA1: We agree with the reviewer and will make sure to incorporate all three recommended changes:  (i) expand more on the results later in the paper, (ii) break up the texts by putting long equations on their own lines (i.e., not in-line), and (iii) add a discussion section where the implications of the results are discussed. \n\n**Q2**: *\"Writing and notation.\"* \n\nA2: We agree with all of the reviewer's comments and will make the recommended changes in the camera-ready version. The star in (X \\times Y)^* is used to denote the space of arbitrarily long, but finite, sequences of labeled instances. The change in notation from L^H to F s a typo and will be fixed in the camera-ready version. \n\n**Q3**: *\"How does Section 5.3 fit in the paper?\"*\n\nA3: One central theme of the paper is identifying settings where proper learners, and more specifically,  ERM works. In Section 4, we showed that ERM works when \\ell is a Lipschitz loss function of the probabilistic margin. In Section 5.1, we showed that PRERM works if you allow the learner to compete against a slightly stronger notion of probabilistic robustness. In Section 5.2, we showed that RERM works if you compare the learner's probabilistic robust risk to the best adversarially robust risk over hypothesis in H. Likewise, in Section 5.3, we identify another setting where the RERM works. Sections 5.1, 5.2, and 5.3 are further unified in the sense that they all consider a learning setting where the learner competes against a slightly stronger notion of robustness. Finally, another unifying theme throughout Section 5 is the use of Lemma 5.1, named Sandwich Uniform Convergence. Indeed, Lemma 5.1 is used to prove all results in Sections 5.1, 5.2, and 5.3.\n\n**Q4**: *\"Is it fair to say that the fact that the probabilistic robustness loss function is non-Lipschitz is the reason behind Theorem 3.1. In other words, is Lipschitzness a necessary condition? My understand from Section 4 is that it is sufficient, but it may not be necessary.\"*\n\nA4: Lipschitzness is sufficient but, in full generality, not necessary for proper learnability.  For example, the loss function that completely ignores G and \\mu and just computes the 0-1 loss is not Lipschitz, however, it is learnable via ERM. That said, among those losses that are a function of the probabilistic robust margin, it is an interesting open question to understand whether Lipschitzness is necessary for proper probabilistic robust learnability. if the loss function \\ell is not a Lipschitzness function of the probabilistic robust margin, we may be able to construct a counterexample similar to the one in Lemma 3.2 by having the probabilistically robust loss class \"spike\" in all possible combinations across the sample while maintaining low overall complexity of the original hypothesis class. We will include a discussion of this in the camera-ready version. \n"}]

Author rebuttal:

Meta-review: The paper makes (theoretical) contributions to the problem of proper learning under test-time adversarial perturbations. They show that a (previously proposed) natural relaxation of the problem is not enough for proper learning, but another relaxation can be sufficient. 

The reviewers are positive about this paper and its contributions. Some minor shortcomings in terms of the presentation and missing references are expected to be addressed in the camera ready.
Decision: Accept (poster)