A Characterization of Semi-Supervised Adversarially Robust PAC Learnability
Authors: Idan Attias
Steve Hanneke
Yishay Mansour
Venue: NeurIPS 2022 Accept (2022)
Keywords: Semi-Supervised Learning
Adversarial Robustness
PAC Learning
Sample Complexity
Combinatorial Dimensions
Partial Concept Classes

Abstract: We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model.
We address the question of how many labeled and unlabeled examples are required to ensure learning.
We show that having enough unlabeled data (the size of a labeled sample that a fully-supervised method would require),
the labeled sample complexity can be arbitrarily smaller compared to previous works, and is sharply characterized by a different complexity measure. We prove nearly matching upper and lower bounds on this sample complexity.
This shows that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model, and establishes a gap between supervised and semi-supervised label complexities which is known not to hold in standard non-robust PAC learning.

A Characterization of Semi-Supervised Adversarially Robust PAC Learnability
Idan Attias
Steve Hanneke
Department of Computer Science Ben-Gurion University of the Negev idanatti @ppost wwrposst.uu.c. bwg..accc... ac.u.ac... ac.il. il
Department of Computer Science
Purdue University
steve hannveehaneee@@rre gma com
Yishay Mansour
Blavatnik School of Computer Science Tel Aviv University and Google Research mansour, y siishhy@@maal com
Abstract
We study the problem of learning adversarially robust predictor to test time attacks in the semi-supervised PAC model. We address the question how many labeled and unlabeled examples are required to ensure learning. We show that having enough unlabeled data (the size of a labeled sample that supervsu method would require), the labeled sample complexity compared to previous works, and is sharply characterized by a different complexity measure. We prove nearly matching upper and lower bounds this sample complexity. This shows that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model, and establishes gap between supervised and semi-supervised label complexities which is known not to hold in standard non-robust PAC learning.
be arbitrarily smaller
Introduction
The problem of learning predictors that are immune to adversarial corruptions at inference time central in modern machine learning. The phenomenon of fooling learning models by adding imperceptible perturbations to their input illustrates a basic vulnerability of learning based models and is named adversarial examples. We study the model of adversarially-robus. PAC learning, in semi-supervised setting.
Adversarial robustness has been shown to significantly benefit from semi-supervised learning, mostly empirically, but also theoretically in some specific cases of distributions [e.g.. 18,58, 51, 46, 1,55, 36]. In this paper, we ask the following natural question. To what extent can we benefit from unlabeled data in the learning process of robust models in the general case? More specifically, what is the sample complexity in distribution-fres model?
Our semi-sso supervise model is formalized as follows. Let 7 C f0, 1 be a hypothesis class. We formalize the adversarial attack by perturbation function 21 X' + 2x where U(x) is the set of possible perturbations (attacks) on æ. In practice, we usually consider ld(x) to be the l ball centered at a. In this paper, have no restriction 24 besides E U(x).. The robust error of hypothesis h on a pair (I, y) suPsEu(2) T [h((2) # y). The learner has access to both labeled and unlabeled examples drawn i.i.d. from unknown distribution D, and the goal to find h E H with low robust error random point from D. The sample complexity in semi-supervised learning has two parameters, the number of labeled examples and the number of unlabeled examples which suffice to
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

ensure learning. The learner would like to restrict the amount of labeled data, which is significantly more expensive obtain than unlabeled data.
In this paper, we show a gap between supervised and semi-supervised lahel complexities of adversari- ally robust learning in distribution-free model. The label complexity in semi-supervised may be arbitrarily smaller compared to the supervised case and is characterized by a different complexity measure. Importantly, we are not using more data, just less labeled data. The unlabeled sample size is the same as how much labeled data a fully-supervised method would require, so this is a strict improvement. This kind of gap is known not to hold in standard (non-robust) PAC learning, this is unique property of robust learning.
Background. The following complexity measure VCu was introduced by Montasser et al. [40] (and denoted there by dimpxx as a candidate for determining the sample complexity of supervised robust learning. It was shown that indeed its finiteness is necessary, but not sufficient. This parameter is our primary object in this work, as we will show that it characterizes the labeled sample complexity of semi-supervised robust PAC-learning
Definition 1.1 (VCu dimension)) A sequence of points {II..... r& } is U-shattered by H if vy...... V/ E {0, 1}. 3h E H such that vi E [k]. Vz E U(;)), h(2) = ys. The (H)((H) is largest integer & for which there exists sequence (Z U-shattered by H.
Intuitively, this dimension relates to the shattering of the entire perturbation sets, instead of one point in the standard VC-dimension. When U(xx) = {z), this parameter coincides with the standard VC. Moreover, for any hypothesis class H. it holds that (H) S VC(H), and the gap can be arbitrarily large. That is, there exist Ho such that VC (Ha) and VC(Ho) = oo (see Proposition 3.2).
For an improved lower bound on the sample complexity, Montasser al. [40, Theorem 10] introduced the Robust Shattering dimension, denoted by RS4 (and denoted there by dimu).
Definition 1.2 ddmeeniii)) A sequence Fi..... Th is said to be UI U/rrbuutlyy shattered by F if Bef ,..,, = 2 such that xi E (2 n2 (=5) Vi E [k] and vyI...., : V/ E (+:-) 3ʃ E F with f(() = yt. J4 l (2 Vi E [k). The U-robust shattering dimension RS; is defined as the maximum size of a set that is M-robustly shattered by H.
Specifically, the lower bound on the sample complexity is Ω RSu + 1 log 4) for realizable robust learning, and ( RS + + log 3)) for agnostic robust learning. They also showed upper bounds of VV-ve" log 2²
δ VC-VV" + lox in the realizable case and δ
in the agnostic case, where VC* is the dual VC dimension (definitions are Appendix A). Montasser al. [40] showed that for any H. (H) < RS)(H)) < VC(H), and there can be an arbitrary gap between them. Specifically, there exists Ho with VCa (Ho) 0 and (S)( = oo, and there exists Hi with RSy (H,) 0 and VC(H,) oc.
2²
Main contributions.
In Section 3, we first analyze the simple case where the support of the marginal distribution on the inputs is fully known to the learner. In this case, we show a tight bound of θ (CH + log }
on the labeled complexity for learning H.
Section 4, we present a generic algorithm that can be applied both for the realizable and agnostic settings. We prove an upper bound and nearly matching lower bounds on the sample complexity in the realizable case. For semi-supervised robust learning, we prove a labeled sample complexity bound A 8 and compare it the sample complexity of supervised robust learning A Our algorithm uses A 99 Ō VC& + log }) labeled examples and ((*)) unlabeled examples. Recall that ^ ((RSs), and since RSy can be arbitrarily larger than VCa, this means our labeled sample complexity represents a strong improvement over the sample complexity of supervised learning.
(O()) stands for omitting poly-logarithmic factors of VC, VC*, VCu, RSa, 1/c,

---

Sample complesity womi-sperriie abvamarisll-mbbuu learning
VV"
Yes
Figure 1: Summary of the sample complexity regimes for semi-supervised robust learning, for the realizable model and the agnostic model with error 3n + where 17 is the minimal ag- nostic error in the hypothesis class.
No
Yisr
RSV
Obtaining an error of + requires at least RSu labeled examples, as the supervised case.
VG3
A denotes the sample complexity of super- vised robust learning. It is an open question whether A equals RSy.
Lobeled
VCar
RS5
A²
VC"
In Section 5, prove upper and lower bounds on the sample complexity in the agnostic setting. We reveal an interesting structure, which is inherently different than the realizable case. Let rj be the minimal agnostic error. If we allow an error of 3n + it is sufficient for our algorithm to have log
A
VC
labeled examples and (A*) unlabeled examples (as in the realizable
case). If we insist on having error + then there is a lower bound of A 2 ( A log $) labeled examples. Furthermore, an error of 3 -)) + is unavoidable if the learner is restricted to ((CCu) labeled examples, for any > Ó. We also show that improper learning is necessary, similar to the supervised case. We summarize the results in Fig. 1 showing for which labeled and unlabeled samples we have a robust learner.
The above results show that there is a significant benefit in semi-supervised robust learning. For example, take Ho with VC2, (Ha) 0 and (S4))))) n. The labeled sample size for learning Ho in supervised learning is 22n). In contrast, in semi-supervised learning our algorithms requires only (1) labeled examples and (n) unlabeled examples. We not using more data, just less labeled data. Note that n can be arbitrarily large.
byproduct of our result that if we assume that the distribution is robustly realizable by a hypothesis class (i.e., there exists hypothesis with zero robust error) then, with respect to the non-robust loss (i.e., the standard 0-1 loss) we can learn with only δ (CH((H) + log )
labeled examples, even if the VC is infinite. Recall that there exists Ho with (Co(HH) = O. (Ho) = do and VC(Ho) = co. Learning linear functions with margin is a special case of this data-dependent assumption. Moreover, we show that this is obtained only by improper learning. (See Section 6.)
Related work. Adversarially robust learning. The work of Montasser al. [40] studied the setting of fully-supervised robust PAC learning. In this paper, we propose a semi-supervised method with a significant improvement in the labeled sample size. We show that the labeled and unlabeled sample complexities are controlled by different complexity measures. Adversarially robust learning has been extensively studied in several supervised learning models [e.g., 25, 49, 34, 57, 20, 7, 35, 6, 10, 44, 41- 43, 3, 11, 21, 9, 15, 56, 4]. For semi-supervised robust learning, Ashtiani et al. [3] showed that under some assumptions, robust PAC learning is possible with ((V((H)) labeled examples and additional unlabeled samples. Carmon et al. [18] studied a robust semi-supervised setting where the distribution is a mixture of Gaussians and the hypothesis class is linear separators.
(non-robust) learning. There is substantial interest in semi-supervised (non-robust) learning, and many contemporary practical problems significantly benefit from it [e.g., 16, 19, 59]. This was formalized in theoretical frameworks. Urner et al. [52] suggested (non-robust) framework, with an algorithmic idea that similar to our method. Their framework consists of two steps; using labeled data to learn a classifier with a small error (not necessarily a member of the target class H), and then labeling an unlabeled input sample order to use a sully-supervised proper learner. They investigate scenarios where the saving of labeled examples occurs. In our paper, we are interested the robust loss function. We use laheled data in order to learn a classifier (with the 0-1 loss function) from class with potentially smaller complexity
remi-supervisedd learning
3

---

measure, then we label an unlabeled input sample, and use a supey-su method using the robust loss function. The sample complexity of learning the robust loss class controlled by larger complexity measure. Fortunately, this affects our unlabeled sample size and not the labeled sample size as in the fully-supervised setting. Göpfert et al. [27] studied circumstances where the learning rate can be improved given unlabeled data. Darnstädt et al. [23] showed that the label complexity gap between the semi-supervised and the fully supervised setting can become arbitrarily large for concept classes of infinite VC-dimension, and this gap is bounded when function class contains the constant zero and the constant one functions. Balcan and Blum [13, 12] introduced an augmented version of the PAC model designed for semi superviiee learning and analyzed when unlabeled data can help. The main idea is to augment the notion of learning a concept class, with a notion of compatibility between function and the data distribution that we hope the target function will satisfy.
2 Preliminaries
Let X' be the instance space, ) a label space, and H C yx a hypothesis class. A pertur- bation function U X + 2 maps an input to set U(x) S X. Denote the 0-1 loss of hypothesis h on (2r, y) by (,; = [M(x) A yl. and the robust loss with respect to U by bu (1; y) =E((Z)
sup [[((2) y). Denote the support of distribution D over X x ) by
: SDpp(D) = ((x, v) X x:: D(r,y) y) > 0}. Denote the marginal distribution Dx on X' and
its support by supp with respect to distribution D over X x V.
fz E X: D(z,y) 0}. Define the robust risk of hypothesis h H
Ru (h; D) = (s.y)/ [lu (h; x. y)] = B( [E((())
sup I [h(2) + y]
The approximation error of H. on D, namely, the optimal robust error achievable by a hypothesis in H. on D is denoted by,
(H; = inf Re D), hER
We say that a distribution D is robustly realizuble by class H if Re D) = O.
Define the empirical robust risk of hypothesis h H with respect sequence S (X 2))"
Rei (h; S) = JS|
Σ
(u(h;
1
Σ
sup [[h(z) + w]
(E.))ES
(E.E)S
=E((()
The robust empirical risk minimizer learning algorithm RERM: (X x y))* + H. for a class H on a sequence S is defined by
RERM+(S) arginin Ru S): 4EH
When the perturbation function is the identity, ((xx) = (r), we recover the standard notions. The
risk of hypothesis h E H with respect distribution D over X' x y is defined by R (h;
((x,))= [fo-1 (h; x, 3)] = ( [I [h(x)) # vll. and the empirical risk of hypothesis h E H
with respect to a sequence S E (X x y)" defined by R (h; S) | Exewres la-1 2,
[hx)) + vll The empirical risk minimizer learning algorithm ERM (X x )²) H for class H on a sequence S is defined by (RMH(S) E argminnen Í (1;
[S] E(wwes
A learning algorithm A : (X' x 3 - y for class H. is called proper if it always outputs hypothesis in H. otherwise it is called improper.
Realizable robust PAC learning. We define the supervised and semi cemi-supervised settings.
Definition 2.1 (Realizable robust PAC learnability) For any e, 8 (0, 1). the sample complexity of realizable robust (e, 8)- learning for a class H. with respect to perturbation function U, denoted by ARg(e, 6, ((), is the smallest integer for which there exists learning algorithm A : (X x y)² + y such that for every distribution D over X' x y robustly realizable by H. namely Ru (H; D) 0, for random sample S ~ D it holds that
P (Bu (A(S); D) < 1-8.

---

If no such m exists, define 6 6, = oc, and H. is not robustly 6e, learnable with respect Ut
For the standard (non-robust) learning with the 0-1 loss function, we omit the dependence on U and denote the sample complexity of class H. by ARE(E, 6, H).
Definition 2.2 (Realizable semi-supervised robust PAC learnability) A hypothesis class H is
semi-supervised realizable robust (e, 8)-PAC learnable, with respect to perturbation function 44 if for any e, E (0, 1), there exists m,, my E N U {0), and a learning algorithm A A (X x )) U (X)) my
y such that for every distribution over X' ) robustly realizable by H. namely Ru (H; D)
for random samples 8 Drm and S
n it holds that
IP (Ru (A(S 5x) D) <c>>->
The sample complexity MR H, includes all such pairs (me, mi). If no such (ma, mi) exist, then MnE(C, 6, H,24) 0.
Agnostic robust PAC learning. In this compete with the optimal E H. We add a parameter to the sample complexity, denoted by n, which is the optimal robust error of hypothesis in H. namely 17 Ru (H: D). We say that function is (a, -opptiaall if Ry D) S oz) + c.
have Ru (H; O, and would like to
Definition 2.3 (Agnostic robust PAC learnability) For any e, E (0, 1), the sample complexity of agnostic robust (ar e, O) learning for a class H. with respect to perturbation function 4. denoted by A Aa 6,6, H,U, 17). is the smallest integer m, for which there exists learning algorithm A: (X' x y) - yaa such that for every distribution D over X' x y, for a random sample S ~ Dmm,
holds that
P Ru (A(S)) S a inf Ru (h; + > 1 MEH
no such m exists, define AaG(a, c, 6, 11.1.1) oc, and H is not robustly (a, c, 8) learnable in the agnostic setting with respect to U. Note that for 1 recover the standard agnostic definition, our notation allows for a more relaxed approximation.
Analogously, we define the semi-supervised case.
Definition 2.4 (Agnostic semi-supervised robust PAC learnability) A hypothesis class 7t is semi-
supervised agnostically robust (a, c, 8AC learnable, with respect perturbation function U, if for any ,, E (0, 1), there exists mu, my E N U {0), and a learning algorithm A: (X' x 3/) U (X) + y such that for every distribution D over X' x V, for random samples S Dm,, and S ~ D it holds that
P Ru (A(S", S a inf Ru (h; + > 1-8. 8. WEH
The sample complexity MAG 6, H, 7) includes all such pairs (m,, mi). If no such (m,, mi) exist, then MAG(a, (a, o, H,U,,)) 0.
Partial concept classes [2]. Let partial concept class H C {0, 1, 1, For h H and input & such that h(xx)) = *, we say that h is undefined on x. The support of a partial hypothesis ) is the preimage of {0, 1). formally, ( 1}) = {i E X h(x)) & *). The main motivation for introducing partial concept classes is that data-dependent assumptions can be modeled in natural way that extends the classic theory of total concepts. The VC dimension of partial class H is defined as the maximum size of shattered set S C X, where S is shattered by H if the projection of H on S contains all possible binary patterns, (0, 1) C H|s. The VC-dimension also characterizes verbatim the PAC learnability of partial concept classes, even though uniform convergence does not hold in this setting.
h X -> 1,
5

---

We use the notation (-) for omitting poly-logarithmic factors of VC, VC", VCu, RSy, 1/c, 1/6. See Appendix A for additional preliminaries on complexity measures, sample compression schemes, and partial concept classes.
3 Warm-up: knowing the support of the marginal distribution
In this section, we provide a tight bound on the labeled sample complexity when the support of marginal distribution is fully known the learner, under the robust realizable assumption. Studying this setting gives an intuition for the general semi-supervised model. The main idea is that as long as we know the support of the marginal distribution, supp(Dx) far X' By E V/ D(x, v) 0], we can restrict our search to subspace of functions that are robustly self self-consistent, Hir-cons C H, where
Huu-cons {h E H Vr E supp(Dx), Vz, x' (((x)),(2)) h(2)))
As long as the distribution robustly realizable, i.e., (H; O, we are guaranteed that the target hypothesis belongs to Har-coms- As a result, it suffices to learn the class Haz-cons with the 0-1 loss function, in order to robustly learn the original class H. We observe that,
VC(Hu--cons) (C)(H) VC(H).
(see Proposition 3.2). Fortunately, moving from VC(H) to (H) implies a significant sample complexity improvement. Since supp(2x) is known, This leads eventually to robustly learning H with labeled sample complexity that scales linearly with VCu (instead of the VC). Formally,
Moreover, there exists Ho with (Ho) 0 and VC(Hg)
now employ any algorithm for learning the hypothesis class cums
Theorem 3.1 For hypothesis class H and adversary U, when the support of the marginal distribution Dx is known, the labeled sample complexity is θ (C,(H)
log 2
The statement in the theorem is about the labeled sample size that is required for learning when the marginal distribution is known. This different than the sample complexity in Definition 2.2, where we ask about the labeled and unlabeled sample sizes required for learning. Here make strong assumption of knowing the marginal distribution, instead of having access to an unlabeled sample.
Remark.
The following Proposition demonstrates that semi-supervised robust learning requires much fewer labeled samples compared to the supervised counterpart. Recall the lower bound on the sample com- plexity of supervised robust learning, ARE(E, 6, H, = Ω (S)(()) + log } given by Montasser al. [40, Theorem 10]. For completeness, we prove the following in Appendix B.
Proposition 3.2 ([40], Proposition 9) There exists a hypothesis class Hy such that VCu(Ho) = 0, RSu(Ha) oc, and VC(Hu) oo.
We can now conclude the following separation result on supervised and semi-supervised label complexities.
Corollary 3.3 The hypothesis class in Proposition 3.2 is not learnable in supervised robust learning (i.e., need to the entire data distribution). However, when supp(Dx) is known, this class can be learned with O log })) labeled examples.
In the next section, we prove stronger separation in the general supe-supe setting. The size of the labeled data required in the supervised case lower bounded by RSy, whereas in the semi-supervise case, the labeled sample complexity depends only on VC and the unlabeled data is
"See Mohri et al. [39, Chapter for standard upper and lower bounds. In order remove the superfluous log
log } factor of the standard uniform convergence based upper bound, (VC)( log
we can use the learning algorithm and its analysis from Hanneke [30] that applies for any 71 and D, or some other algorithms that are doing so while restricting the hypothesis class the data distribution [e.g.. 8, 22, 31, 29, 37, 26, 17, 14).

---

lower bounded by RSy. Moreover, note that in Theorem 3.1, when supp(Dx) is known, we can use any proper learner. Section 4 we show that in the general supeevieee model this not the case, and sometimes improper learning is necessary, similar to supervised robust learning.
4 Near-optimal semi-supervised sample complexity
In this section, we present our algorithm and its guarantees for the realizable setting. We also prove nearly matching lower bounds on the sample complexity. Finally, we show that improper learning is necessary in semi-supervised robust learning, similar to the supervised case.
We present a generic semi-supervised robust learner, that can be applied in both realizable and agnostic settings. The algorithm uses the following two subroutines. The first one is any algorithm for learning partial concept classes, which controls our labeled sample size. (In Appendix we discuss in detail the algorithm suggested by Alon et al. [2].) The second subroutine is any algorithm for the agnostic adversarially robust supervised learning, which controls our unlabeled sample size. (In Appendix G we discuss in detail the algorithm suggested by Montasser et al. [40].) Any progress on one of these problems improves directly the guarantees of our algorithm. We use the following definition that explains how to convert total concept class into partial one, in way that preserves the idea of the robust loss function.
Definition 4.1 Let a hypothesis class H S 10 and perturbation function U X - 2 For any h E H. we define a corresponding partial concept h X + {0, 1, *), and denote this the entire set ((x), i.e.,
h-_ For x X, whenever h is not consistent Bz, x' E U(x). h(z) & h(z'), define (x) = *. Otherwise, h is robustly self-consistent on æ, i.c., Vz, z E (z), h(z) h(2") and h remains unchanged, h (x)) = h(x). The corresponding partial concept class is defined by Hig {h* (h)) = ht, vh E H}.
mapping by (phh)
The main motivation for the above definition is the following. Fix hypothesis h. For any point x, as defined above, the adversary can force a mistake on h. regardless of the prediction of h. We would like to mark such points as mistake. We do this by defining a partial concept h" and setting h (x) = *, which, for partial concepts, implies mistake. The benefit of this preprocessing is that we reduce the complexity of the hypothesis class from VC to VCu, which potentially can reduce the labeled sample complexity. We are now ready to describe the algorithm.
Algorithm 1 Generic iiversarially-Robuur Semi-SSpee (GRASS) learner
Input: Labeled data set S ~ DD!,,, unlabeled data set 5x D hypothesis class H. perturbation function U, parameters e, d.
Algorithms used: leanerr A for partial concept classes, agnostic adversarially robust supervised PAC learner I.
1. Given the class H. construct the hypothesis class H using Definition 4.1.
2. Execute the learning algorithm for partial concepts A on Hig and sample S with the 0-1 loss and parameters 3 2- Denote the resulting hypothesis h1.
3. Label the unlabeled data set 5% with h1, denote the labeled sample by S". (On points where h predicts +, we can arbitrarily choose label of O or 1.)
4. Execute the agnostic adversarially robust supervised PAC learner B on S with parameters Denote the resulting hypothesis h2.
e 3:2-
Output: h2-
Algorithm motivation. The main idea behind the algorithm is the following. Given the class Hi we would like to find hypothesis h1 E Hÿ which has a small error, whose existence follows from our realizability assumption. The required sample size scales with VCu, which is the complexity of Hig rather than VC. This is where we make a significant gain the labeled sample complexity. Note that /1 does not guarantee small robust error, although it does guarantee a small non-robust error. We utilize an additional unlabeled sample for this task, which we label using h1- If we would simply minimize the non-robust error on this sample would simply get back h1. The main insight
7

---

is that we would like to minimize the robust error over this sample, which will result in hypothesis hz. We now need to bound the robust error of h2 The optimal function hopt has only a slightly increased robust error on this sample, namely, at most on the sample points where it disagrees with h1, Note that by might have a large robust error due to the perturbation 4. However, a robust supervised PAC learner would return a hypothesis h2 which has robust error similar to hops> which is at most c.
Algorithm outline and guarantees. In the first step, we convert H to Hig- Then we employ learning algorithm A for partial concepts on Hiy with labeled sample St ~ Dmm, The output of the algorithm is function hy with c/3 on the 0-1 error. Crucially, O(VCu(HH)e labeled examples for learning the partial concept Hig since VC(H;,) = VCu (H). So our labeled sample size is controlled by the sample complexity for learning partial concepts with the 0-1 loss. In step 3. we label an independent unlabeled sample Sx Dit with h2, denote his labeled sample by 5 Define a distribution D over X' x y by (()))i(() = -x(()), and so S is an i.idd. sample from D. We argue that the robust error of H. with respect to D is at most 5. ie.. Ra D) 3. Indeed, the function with zero robust error on D, hopt argmin (h; D) has a robust error of at most on D. Finally, we employ an agnostic adversarially robust supervised PAC learner B for the class H on S ~ DDm, that should be of size of the sample complexity of agnostically robust learn H. with respect to U, when the optimal robust error of hypothesis from H on D is at most &. Moreover, the total variation distance between D and D is at most 5. We are guaranteed that the resulting hypothesis h2 has robust error of at most & + $ + 3 =e on D. We conclude that a size of I = my = AAG (I, 3. 5 H, = 5) unlabeled samples suffices, this completes the proof for Theorem 4.2. For specific instantiation of such an algorithm ([40)), we deduce the sample complexity in Theorem 4.4. A simple analysis of the latter yields dependence of e² for the unlabeled sample size. However, by applying a suitable data-dependent generalization bound, we reduce this dependence to c. (Full proofs appear in Appendix C).
needed for this step |S
We now formally present the sample complexity of the generic semi-supervised learner for the robust realizable setting. First, in the case of using a generic agnostic robust supervised learner as subroutine (step 4 in the algorithm). Then we deduce the sample complexity of a specific instantiation of such an algorithm.
Theorem 4.2 For any hypothesis class H. and adversary U, algorithm GRASS (c, 8P-CC learns H. with respect to the robust loss function, in the realizable robust case, with samples of size
my my= =0 ( ( (CL)
log² VCu(H) log
8 m.,, = AAG 1 21,42. -
e
where AAG (at,e, Ō, H,),,n) is the sample complexity of adversarially-robus agnostic supervised 8)-PAC learning, such that is the error of the optimal hypothesis in H. i.e., = Ru (H: D).
Remark 4.3 Note that if we simply invoke a PAC learner (for total concept classes) on H. with the 0-1 loss, instead of steps 1 and 2 in the algorithm, we would get labeled sample complexity of roughly (VC(H))) This is already an exponential improvement upon previous results that require roughly (2VC(H)) labeled samples. The purpose of using partial concept classes is to further reduce the labeled sample complexity to (H)))
The following result follows by using the agnostic supervised robust learner suggested by Montasser et al. [40]. A simple analysis of the latter yields a dependence of 2² for the unlabeled sample size. However, by applying a suitable date-depen generalization bound, we reduce this dependence to
Theorem 4.4 For any hypothesis class H and adversary U, Algorithm GRASS (e, 8)-AC learns H with respect to the robust loss fascsiontiin in the realizable robust case, with samples of size
my = O VCu log² VCu(H)
log
m. = Ō VC(H) VC (H) log
We present nearly matching lower bounds for the realizable setting. The following Corollary stems from Theorem 3.1 and Montasser et al. [40, Theorem 10].
8

---

Corollary 4.5 For any e, E (0. the sample complexity of realizable robust (c, 6)- learning for a class H. with respect to perturbation function U is
(H)
log x
RSu (H)
log
my =
My = 00, or my + mu = S2
Proper vs. improper. In Section 3, we have seen that when the support of the marginal distribution
Dx is known, the labeled sample complexity is θ (CCx(H) + log H. This was obtained by proper learner: keep the robustly self-consistent hypotheses, Hyr.cons S H. and then use ERM on this class. The case when Dx is unknown is different. We know that there exists perturbation function U and a hypothesis class H with finite VC-dimension that is not robustly PAC learnable by any proper learning rule [40, Lemma 3]. The same proof holds in the semi-supervised case. Note that both algorithms A and B used in Algorithm I are improper. (The proof appears in Appendix C.)
Theorem 4.6 There exists H with VC(H) = 0 such that for any proper learning rule A (X x U (x)" + H. there exists distribution D over xy that is robustly realizable by H. i.e., Ru (H; D) O. It holds that Ru (A(S), S) > with probability least 1 over St DDm and S D where m,, Th E UNU (0} is the size of the labeled and unlabeled samples respectively. Moreover, when the support of the marginal distribution x is known, there exists a proper learning rule for any H.
Agnostic robust learning
In this section, we prove the guarantees of Algorithm I in the more challenging agnostic robust setting. We then prove lower bounds on the sample complexity which exhibit that it is inherently different from the realizable case.
We follow the same steps as in the proof of the realizable case, with the following important difference. In the first two steps of the algorithm, we learn a partial concept class with respect to the 0-1 loss and obtain a hypothesis with an error of 3 + e/3 (1) is the optimal robust error of hypothesis in and not 0). This leads eventually to error of 3n + for learning with respect to the robust loss.
We then present two negative results. In Theorem 5.2 we show that for obtaining error 1j + there is a lower bound of ((RSy) labeled examples, this result coincides with the lower bound of supervised robust learning.
Theorem 5.3, we show that for any 7 >> there exists hypothesis class, such that having access only to (VCCz) labeled examples, leads to an error ( >)) + e. (All proofs for this section are in Appendix D.)
We start with the upper bounds. First, we analyze the case of using a generic agnostic robust learner, then we deduce the sample complexity of specific instantiation of such an algorithm.
Theorem 5.1 For any hypothesis class H and adversary U. Algorithm GRASS (3, e, PAC learns H with respect to the robust loss function, in the agnostic robust case, with samples of size
COVV 2
(VCu(H)) log?
(Cu(H)) 2
log
6 m. = AAG 1. 1 H.u, 2n
mi =0
2
3
where AAG (a, e, 5, H. 142 n) is the sample complexity of adversarially-robutt agnostic supervised learning, such that v is the error of the optimal hypothesis H. namely r) = Ru (H;D).
By using the agnostic supervised robust learner suggested by Montasser et al. [40], have the following upper bound on the unlabeled sample size, = ô (VC(H) VC* (X)
log
We now present two negative results.
Theorem 5.2 For any e, 8 E (0,1), 1), the sample complexity of agnostic robust (1,e, (),,8) learning for a class H. with respect to perturbation function lt is (even if Dx is known),
(H)
1
1
my = Ω
22
+
log
m, = Do.

---

Theorem 5.3 For any O, there exists hypothesis class H and adversary UA, such that the sample -,,,,,)-PAC 6)-PAC learn H is
complexity for (3 7,5,
(CC((H)
+ +2 log 108 3) Mhx = 00.
my = Ω
2
Open question.
What the optimal error rate in the agnostic setting when using only O(VCu) labeled examples?
6 Learning with the 0-1 loss assuming robust realizability
In this section, we learn with respect to the 0-1 loss, under robust realizability assumption. Distribution D over X' x Y is robustly realizable by H. given perturbation function 4, if there is H such that not only h classifies all points in D correctly, it also does so with respect to the robust loss function, that is. Rz (H; D) O. Note that our guarantees, only in this section, are with respect to the non-robust risk. The formal definition is in Appendix
A simple example of this model is the following. Let H. be linear separators on X' the unit ball in Rdd, and LI l balls of radius 7, the robustly realizable distributions are separable with margin 7/s where (H) = 7o VC(H) d + 1 can be arbitrarily larger. Moreover, we have the following example. (All proofs are in appendix Appendix E.)
+ but
Proposition 6.1 For any m E N. there exist a hypothesis class Hm and distribution DD such that 'D robustly realizable by Hin (Cu(H and VC(Hm) 2m.
Standard VC theory does not ensure learning in this case. In this section, we explain how we can learn in such a scenario with a small sample complexity (scales linearly in VCu). Moreover, we show that it cannot be achieved via proper learners.
Theorem 6.2 The sample complexity for learning a hypothesis class H. with respect to the 0-1 loss, for any distribution D that is robustly realizable by H. namely Ryi (H: D) 0,
VCu(?()
log" VCu((I) log
( (VC((H)
log
This Theorem was an intermediate step in the proof of Theorem 4.2, and the sample complexity is the same as Theorem C.I, O (ARE(e, 8, H)). We show that there exists robust ERM that fails in this setting (Proposition E.2 Appendix E). Then, we claim that every proper learner fails.
Theorem 6.3 There exists H. with VC,(H) = 1, such that for any proper learning rule A (X x y) - H. there exists a distribution D over X y that robustly realizable by H. i.e. Re (H:D) = O, and it holds that R (A(S); D) > g with probability at least over S ~ Dm.
Acknowledgments
We are grateful to Omar Montasser for his helpful input, particularly inspiring steps 3 and 4 of the GRASS learning algorithm. We would like to thank Vinod Raman for his enlightening comments regarding the correctness of our algorithm. Finally, we thank the anonymous reviewers for their thoughtful comments, which helped us improve the presentation of our paper.
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grants 993/17, 1602/19), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University. I.A. is supported by the Vatat Scholarship from the Israeli Council for Higher Education and by the Kreitman School of Advanced Graduate Studies.
10

---

References
[1] J.-B. Alayrac, J. Uesato, P.-S. Huang, A. Fawzi, R. Stanforth, and P. Kohli. Are labels required for improving adversarial robustness? Advances in Neural Information Processing Systems, 32, 2019.
[2] N. Alon, S. Hanneke, R. Holzman, and Moran. A theory of pac learnability of partial concept classes. arXiv preprint arXiv:2107.0844 2021.
[3] H. Ashtiani, V. Pathak, and R. Urner. Black-box certification and learning under adversarial perturbations. In International Conference on Machine Learning, pages 388-398. PMLR, 2020.
[4] H. Ashtiani, V. Pathak, and R. Urner. Adversarially robust learning with tolerance. arXiv preprint arXiv:2203.000 220.00089, 2022.
[5] P. Assouad. Densité et dimension. In Annales de l'institut Fourier, volume 33, pages 233-282
1983.
[6] I. Attias and S. Hanneke. Adversarially robust learning real-valued functions. arXiv preprint arXiv:2206.12 12977, 2022.
[7] I. Attias, A. Kontorovich, and Y. Mansour. Improved generalization bounds for robust learning. In Algorithmic Learning Theory, pages 162-183. PMLR, 2019.
[8] Auer and Ortner. A new pac bound for intersection-closed concept classes. Learning, 66(2):151-163, 2007.
Machine
[9] P. Awasthi, N. Frank, and M. Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. International Conference on Muchine Learming, pages 431-441, PMLR, 2020.
[10] P. Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. Advances in Neural Information Processing Systems, 34, 2021.
[11] Awasthi, N. Frank, and M. Mohri. On the existence of the adversarial bayes classifier. Advances in Neural Information Processing Systems, 34, 2021.
[12] M.-F. Balcan and A. Blum. 21 an augmented pac model for semi-supervised learning. 2006.
[13] M.-F. Balcan and A. Blum. A discriminative model for semi-supervised learning. Journal of the ACM (JACM), 57(3):1-46, 2010.
[14] M.-F. Balean and P. Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pages 288-316. PMLR, 2013.
[15] R. Bhattacharjee, S. Jha, and K. Chaudhuri. Sample complexity of robust linear classification on separated data. In International Conference on Machine Learning, pages 884-893. PMLR, 2021.
[16] A. Blum. Semi-supervised learning. In Encyclopedia of Algorithms, pages 1936-1941, 2016.
[17] N. H. Bshouty, Y. L.,, and P. M. Long. Using the doubling dimension to analyze the generalization of learning algorithms. Journal of Computer and System Sciences, 35(6)33 2009.
[18] Y. Carmon, A. Raghunathan, L. Schmidt, J. C. Duchi, and Liang. Unlabeled data improves adversarial robustness. Advances in Neural Information Processing Systems, 32, 2019.
[19] O. Chapelle, B. Scholkopf, and A. Zien. Semi-supervised learning (chapelle, o. et al., eds.; 2006)]book reviews]. IEEE Transactions on Neural Networks, 20(3)5442-542, 2009.
[20] D. Cullina, A. N. Bhagoji, and Mittal. Pac-learning in the presence of adversaries. In Advances in Neural Information Processing Systems, pages 230-241, 2018.
[21] C. Dan, Y. Wei, and P. Ravikumar. Sharp statistical guaratees for adversarially robust gaussian classification. In International Conference on Machine Learning, pages 2345-2355. PMLR, 2020.
11

---

[22] M. Darnstädt. The optimal pac bound for intersection-closed concept classes Information Processing Letters, 115(4):58-44)) 461, 2015.
[23] M. Darnstädt,
Simon, and B. Szörényi. Unlabeled data does provably help. 2013.
[24] O. David, S. Moran, and A. Yehudayoff. Supervised learning through the lens of compression. Advances in Neural Information Processing Systems, 29:2784-2792. 2016.
[25] U. Feige, Y. Mansour, and R. Schapire. Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory. pages 637-657, 2015.
[26] E. Giné and V. Koltchinskii. Concentration inequalities and asymptotic results for ratio type empirical processes. The Annals of Probability, 34(3): 1400)11141121... 2006.
[27] C. Göpfert, S. Ben-David, O. Bousquet, S. Gelly, I. Tolstikhin, and R. Urner. When can unlabeled data improve the learning rate? In Conference on Learning Theory, pages 1500-1518. PMLR, 2019.
[28] T. Graepel, R. Herbrich, and J. Shawe- Taylor. Pac-bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning, 59(1-2):55-76. 2005.
[29] S. Hanneke. Theoretical foundations of active learning. Carnegie Mellon University, 2009,
[30] S. Hanneke. The optimal sample complexity of pac learning. The Journal of Machine Learning Research, 17(1):11191333, 2016.
[31] S. Hanneke. Refined error bounds for several learning algorithms. The Journal of Machine Learning Research, 17(1)4667-4721, 2016.
[32] S. Hanneke, A. Kontorovich, and M. Sadigurschi. Sample compression for real-valued learners. In Algorithmic Learning Theory, pages 466-488, 2019.
[33] D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting (0. 1)-functions randomly drawn points. Information and Computation, 115(():248 1994.
[34] J. Khim and P.-L. Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv: 1800.098,, 2018.
[35] A. Kontorovich and I. Attias. Fat-shattering dimension of k-fold maxima. arXiv preprint arXiv:2110.04763, 2021.
[36] M. Levi, I. Attias, and A. Kontorovich. Domain invariant adversarial learning. arXiv preprint arXiv:2/04.00322 2021.
[37] P. M. Long. An upper bound on the sample complexity of pac-learning halfspaces with respect to the uniform distribution. Information Processing Letters, 87(5):229- 2244, 2003.
[38] A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740,2200 2009.
[39] M. Mohri, A. Rostamizadeh. and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
[40] O. Montasser, Hanneke, and N. Srebro. Ve classes are adversarially robustly learnable, but only improperly. arXiv preprint arXiv:1902.042177 2019.
[41] O. Montasser, S. Goel, I. Diakonikolas, and N. Srebro. Efficiently learning adversarially robust halfspaces with noise. In International Conference on Machine Learning, pages 7010-7021. PMLR, 2020.
[42] O. Montasser, S. Hanneke, and N. Srebro. Reducing adversarially robust learning to non-robust pac learning. Advances in Neural Information Processing Systems, 33: 01111466-166377 2020.
[43] O. Montasser, Hanneke, and Srebro. Adversarially robust learning with unknown pertur- bation sets. In Conference on Learning Theory, pages 3452-3482. PMLR, 2021.
12

---

[44] O. Montasser, S. Hanneke, and N. Srebro. Transductive robust learning guarantees. arXiv preprint arXiv:2110.10602 2021.
[45] Moran and A. Yehudayoff. Sample compression schemes for vo classes, Journal of the ACM (JACM), 63(3):1-10, 2016.
[46] A. Najafi, S.-i. Maeda, M. Koyama, and T. Miyato. Robustmess to adversarial perturbations in learning from incomplete data. Advances Neural Information Processing Systems, 32, 2019.
[47] N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
[48] R. Schapire and Y. Freund. Boosting: Foundations and algorithms. Kybernetes, 2013.
[49] L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry. Adversarially robust generaliza-
tion requires more data. Advances in neural information processing systems, 31, 2018.
[50] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[51] J. Uesato, J.-B. Alayrac, P.S. Huang, R. Stanforth, A. Fawzi, and P. Kohli. Are labels required for improving adversarial robustness? arXiv preprint arXiv: 1905. 13725, 2019.
[52] R. Umerr Shalev-Shwartz. and S. Ben-David. Access unlabeled data can speed up prediction time. In ICML, 2011.
[53] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Measures of complexity, pages 11-30. Springer, 2015.
[54] M. K. Warmuth. The optimal pac algorithm. In International Conference on Computational Learning Theory, pages 641-642 Springer, 2004.
[55] C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical analysis of self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622,, 2020.
[56] Y. Xing, R. Zhang, and G. Cheng. Adversarially robust estimate and risk analysis in linear regression. International Conference on Artificial Intelligence and Statistics, pages 514-522. PMLR, 2021.
[57] D. Yin, R. Kannan, and P. Bartlett. Rademacher complexity for adversarially robust gen- eralization. International Conference on Machine Learning, pages 7085-7094. PMLR, 2019.
[58) R. Zhai, T. Cai, D. He, C. Dan, K. He, J. Hoperoft, and L. Wang. Adversarially robust generalization just requires more unlabeled data. arXiv preprint arXiv:9066. 00555, 2019.
[59] X. Zhu and A. B. Goldberg. Introduction to semi-supervised learning. Synthesis lectures on artificial intelligence and machine learning, 3(1):1-130, 2009.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "YvHYqlmYW0", "reviewer": "Reviewer_tNtE", "summary": "The authors tackle the learning of an adversarially robust predictor in the semi-supervised PAC model. They study the sample complexity for labeled and unlabeled examples for PAC learning. Their main focus is to control sample complexity of labeled examples which are more expensive to obtain than unlabeled examples. The sample complexity of unlabeled examples matches with that of labeled examples in supervised learning. Their main contribution is to bound sample complexity of labeled examples by a different complexity measure $VC_{\\mathcal{U}}$. They provide new bounds for the following cases (I am mentioning only the labeled complexity):\n1. Realizable and known support of the marginal distribution: $\\Theta(\\frac{VC_{\\mathcal{U}}}{\\epsilon} + \\frac{log \\frac{1}{\\delta}}{\\epsilon})$. \n2. General realizable case: $\\tilde{\\mathcal{O}}(\\frac{VC_{\\mathcal{U}}}{\\epsilon} + \\frac{log \\frac{1}{\\delta}}{\\epsilon})$. \n3. General agnostic case: $\\tilde{\\mathcal{O}}(\\frac{VC_{\\mathcal{U}}}{\\epsilon^2} + \\frac{log \\frac{1}{\\delta}}{\\epsilon^2})$ with error $2 \\eta + \\epsilon$ or $\\tilde{\\mathcal{O}}(\\frac{RS_{\\mathcal{U}}}{\\epsilon^2} + \\frac{log \\frac{1}{\\delta}}{\\epsilon^2})$ with error $\\eta + \\epsilon$. They also show that $(\\frac{3}{2} - \\gamma)\\eta + \\epsilon$ error is unavoidable if the learner has access to only $\\mathcal{O}(VC_{\\mathcal{U}})$ labeled examples.\n\nOn a high-level the analysis can be summarized in the following steps:\n1. Given the class $\\mathcal{H}$, construct the partial concept class $\\mathcal{H}_\\mathcal{U}^*$.\n2. Execute the learning algorithm for partial concepts to learn hypothesis $h_1$ for partial concept class $\\mathcal{H}_\\mathcal{U}^*$ . Bound sample complexity in terms of $\\mathcal{O}(VC_\\mathcal{U})$.\n3. Label the unlabeled data set using $h_1$ .\n4. Execute the agnostic adversarially robust supervised PAC learner to learn hypothesis $h_2$. Provide bounds on robust error.\n", "questions": "I liked the way the paper is presented and written. I will rephrase the weaknesses mentioned in previous section as questions, so that authors can respond to them.\n\n1. Consider that results in [2] and [39] are well-known. Could you specify particular places (in concepts or theoretical analysis) where contribution is novel and is independent of contribution in [2] and [39]?\n2. Could you provide some useful examples for specific $\\mathcal{H}$ and $\\mathcal{U}$ when $VC_\\mathcal{U}$ is strictly smaller than $VC$ and the gain in complexity is significant? ", "limitations": "The limitations have been adequately addressed. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper provides novel theoretical bounds for semi-supervised learning setting and is able to keep the labeled sample complexity down for the case when  $VC_\\mathcal{U}$ is strictly smaller than $VC$.\n- The paper is well written and theoretical results are presented in a manner which is easy to follow. In my opinion, the main contribution is in Definition 4.1 where they construct a partial concept class.\n\nWeakness:\n- The paper reads like an extension (although non-trivial) of ideas first mentioned in [2] and [39] to semi supervised learning setting. Once Definition 4.1 is established, the analysis directly borrows ideas from [2] and [39]. \n- The paper lacks some concrete examples for specific $\\mathcal{H}$ and $\\mathcal{U}$ when $VC_\\mathcal{U}$ is strictly smaller than $VC$ and the gain in complexity is significant.", "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": "I-lFO2Q1mTI", "reviewer": "Reviewer_czBH", "summary": "The authors consider the problem of adversarial PAC learning in a semisupervised setting. \n\n+ they show that having access to marginal distribution can provide provable benefits for this setting for some concept classes\n+ they give a semi-supervised learner that uses labeled samples to learn an accurate but non-robust hypothesis (using partial concept learning). \n+ They then show that one can use unlabeled data and label them with the learned hypothesis to come up with a larger labeled data from a distribution that is close to the actual labeled distribution. They then use the known results for adversarially robust pac learning on this data\n+ their analysis shows provable benefits of unlabeled data for adversarial pac learning (for some hypothesis classes).\n+ the analysis is extended to the agnostic setting", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ the main paper is written quite nicely\n+ the results are interesting: they show provable benefits of unlabeled data for pac learning under adversarial perturbations\n+ the idea of using the framework of partial concepts as well as labeling the unlabeled data is quite nice. Since this work builds on the existence of partial concept learners and robust pac learners, any future improvements will likely improve this result too. \n+ Because the work build on the two building blocks (partial concepts and adversarial learning), the analysis is rather simple, clean, and intuitive. I like that the authors do not try to overcomplicate things, offering a good ground for future advancements.\n\nWeaknesses:\n\n+ The work of M Darnstädt, HU Simon and B Szörényi on \"Unlabeled data does provably help\" provides some provable benefits of semisupervsed learning in the non-adversarial setting. I think it would make sense to mention this result especially since the reader may think that in the non-adversarial distribution-free setting there is no benefit in knowing the marginal or having unlabeled data. \n+ The work of H Ashtiani, V Pathak, R Urner  on \"Black-box certification and learning under adversarial perturbations\" provides some results on semi-supervised adversarial pac learning. It would help to discuss or compare the results.", "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": "4RR6XJkL-aI", "reviewer": "Reviewer_LSj4", "summary": "The paper considers realizable and agnostic semi-supervised PAC learning models. A common algorithm for robust semi-supervised learning is provided which first learns a partial concept class which predicts * (undefined) on points for which the concept may change prediction under an adversarial perturbation, using the labeled examples. This concept is used to extrapolate labels for the unlabeled examples on which an agnostic robust supervised learner is trained. Upper and lower bounds on the number of labeled examples needed are given in terms of the adversarial VC dimension, VC_U, in both realizable and agnostic settings. Further an application is provided, where the non-robust sample complexity is improved under a robust realizability assumption.", "questions": "Knowledge of supp(D_X) seems like a strong assumption. Are the authors aware of instances of this assumption in prior work?\nLines 253 vs 263: what does it mean that D_x is known? Is it the same as supp(D_x) is known?\n\nWhat is 'labeled sampled complexity' (e.g. in Theorem 3.1)? Not defined in Sec 2. It seems like a bound on m_l in Definitions 2.2 and 2.4 but for what m_u (since definition is for pairs m_l,m_u)?\n\nSimilarly, in Theorem 5.2,5.3 what does m_u=\\infty mean? Does it imply that m_l satisfies the lower bound for any (finite) m_u? Should be useful to add a remark in the context of Definitions 2.2 and 2.4.\n\nIn algorithm 1, h_1 is a partial concept class, right? How is the agnostic robust supervised learner applied to partially labeled sample S^u?\n\nTypos:\n155: exists\nFirst para of Sec 2: definition of supp(D_X) should probably have an existential quantifier? \\exists y\\in Y s.t. D(x,y)>0?\n", "limitations": "I do not expect negative societal impact from this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper shows a remarkable result for the number of labeled examples needed for robust semi-supervised learning - the results are somewhat surprising since finite VC_U is known to be not sufficient in the supervised setting (this is a strength).\n\nUpper and lower bounds are provided in both realizable and agnostic settings. In the agnostic setting, the learner's goal is to have error const*OPT+epsilon since improvement over the supervised setting is not possible with OPT+epsilon.\n\nTechnically, the paper is an application of prior works on learning partial concept classes and agnostic robust supervised learning. The main novelty is combining the techniques.\n\nIt is not clear if one can say that VC_U is the correct sample complexity measure for the problem in all regimes of unlabeled sample size. It seems true in the sufficient unlabeled examples regime, so perhaps the stated results (e.g. in the abstract) should be qualified further.\n\nProof of Theorem 3.1 is not presented. The paragraph leading to it gives an explanation, but a formal proof should still ideally be included for completeness.", "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": "0LteekPH8tj", "reviewer": "Reviewer_tkTj", "summary": "The authors study semi-supervised learning for adversarially robust classification and claim upper bounds on labelled and unlabelled sample complexity of their learner. In particular, for the case when the data distribution is robustly realizable wrt (H, U) (i.e. when the robust loss is 0), they claim that their learner needs only a linear (in VC-dimension) number of labelled samples, as long as it's given a potentially exponential (in VC) number of unlabelled samples. More specifically, they show a linear dependence on a dimension that is defined in term of \"robust shattering\" with respect to the general perturbation sets U. It is known that this dimension can be significantly smaller than the VC-dimension. They also claim similar results for the agnostic case, and make additional remarks on special cases when their sample complexity can be improved further, and complement their upper bounds with corresponding lower bounds on the labeled and unlabeled samples.", "questions": "I think if we just want to show a linear dependence on VC-dimension for the number of labelled samples, we do not need to invoke the partial concepts paper? ", "limitations": "The authors have addressed limitations adequately.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is sound and makes interesting new contributions.", "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: Accept