Adversarially Robust Learning with Uncertain Perturbation Sets
Authors: Tosca Lechner
Vinayak Pathak
Ruth Urner
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarially robust learning
TL;DR: We introduce a setting for adversarial robust learning that interpolates between a known perturbation type and entirely unknown perturbation types by providing a PAC type analysis with a class of perturbation types.

Abstract: In many real-world settings exact perturbation sets to be used by an adversary are not plausibly available to a learner. While prior literature has studied both scenarios with completely known and completely unknown perturbation sets, we propose an in-between setting of learning with respect to a class of perturbation sets. We show that in this setting we can improve on previous results with completely unknown perturbation sets, while still addressing the concerns of not having perfect knowledge of these sets in real life. In particular, we give the first positive results for the learnability of infinite Littlestone classes when having access to a perfect-attack oracle. We also consider a setting of learning with abstention, where predictions are considered robustness violations, only when the wrong prediction is made within the perturbation set. We show there are classes for which perturbation-set unaware learning without query access is possible, but abstention is required.

Adversarially Robust Learning with Uncertain Perturbation Sets
Tosca Lechner
University of Waterloo, Waterloo, Ontario, Canada, tlechner@uxaterloo.co
Vinayak Pathak
Layer 6 AI, Toronto, Ontario, Canada, vinayak@layer6.c
Ruth Urner
York University, Toronto, Ontario, Canada, uruth@eecs, yorku
Abstract
In many real-world settings exact perturbation are not plausibly available to learner. While prior literature has studied both scenarios with completely known and completely unknown perturbation sets, we propose an in-between setting of learning with respect to class of perturbation sets. We show that this setting we can improve on previous results with completely unknown perturbation sets, while still addressing the concerns of not having perfect knowledge of these sets real life. In particular, we give the first positive results for the learnability of infinite Littlestone classes when having access to a perfect-attack oracle. We also consider setting of learning with abstention, where predictions are considered robustness violations, only when the wrong label prediction is made within the perturbation set. We show there are classes for which perturbation-see unaware learning without query access is possible, but abstention is required.
be used by adversary
Introduction
Adversarial perturbations, imperceivably small manipulations input instances that cause unexpected failures of learned predictors, pose significant safety concerns for their employment. The phenomenon, first exposed a decade ago in image classification tasks [Szegedy et al. 2014), has since received substantial attention, both in the practical and theoretical machine learning research communities. Studies in both lines of research often skip over the question how to suitably model "imperceivable perturbations" and rather investigate how to defend against various (fixed) types of attacks. In theoretical studies, this typically modeled by defining an adversarial loss that, addition to misclassification, penalizes the existence of perturbed instance on which a classifier assigns different label. This type of loss definition then crucially depends on a given perturbation type, that some function X 2 that assigns every domain instance set of points that would be viewed as an admissible perturbation (often balls some radius with respect to some norm are considered).
However, in most realistic settings, exact perturbation sets to be used by an adversary are not plausibly available learner. Moreover, has been shown that encouraging robustness with respect perturbation type that is not suitable for the task easily degrades classification accuracy [Tsipras et al. 2019 Zhang al. 2019. Yang et al., 2020). In response, some work has then explored the question of learnability when the perturbation type is not known at all in advance [Montasser et al., 2021) information about possible perturbations can accessed through queries. not difficult be convinced though that without any restrictions or knowledge of the perturbations to be used, robust
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

learning from samples only is impossible. Even for small collection of possible perturbation types, as soon as these induce inconsistencies between optimal predictors a sample based learner cannot be simultaneously successful with respect to all options.
In this work we explore middle ground between fixed and unknown perturbation types, which we term learning with uncertain perturbation sets. We will assume that the true perturbation type is member of a fixed class of perturbation types. One can think of this knowing that we should encourage robustness with respect to some type of norm induced ball, but may not be certain about which type of norm or which radius is most suitable for the task. We then study which structures (on the interplay between perturbation type class and the class of predictors to be learned) allow for PAC-type learnability guarantees.
Given a class U/ of perturbation types and hypothesis class H. we define an H-induced partial order on U. We show that when V/ is actually totally ordered in this sense, statistical (PAC) learning is possible in the realizable case as soon as H has finite VC-dimension. 2/ being totally ordered applies to wide variety of settings, for example the case where the various perturbation types are balls in some metric space while the radius varies over U (and actually also does not need to be constant over domain X' for each U). However, we also show that, without the realizability assumption learning from samples alone is not feasible, even when V/ is totally ordered with respect to H.
We thus explore two natural remedies: (1) We allow the learner to interact with a perfect attack oracle [Montasser et al., [021]. I. Given an instance x and classifier f. such an oracle certifies robustness or provides adversarial perturbation of for f. Previous work on learning with unknown perturbation sets has employed such an oracle and shown learnability for classes with finite Littlestone dimension [Montasser al.. 2021]. In this work, we show that provided certain structures (lf being totally ordered or finite union of totally ordered perturbation type classes) learning with a perfect attack oracle becomes feasible for all classes of finite VC-dimension (which is a much wider space of natural hypothesis classes than those of finite Littlestone dimension). (2) We allow the learner to output classifier that sometimes abstains from prediction. For this, we define modification of the adversarial loss, where hypothesis does not suffer loss when it abstains on an instance that was actually manipulated. We show that this again yields learnability for VC-classes when the perturbation type class is finite union of totally ordered classes. We then consider the case in which H has finite teragreemeet-coefffcceee respect to every class of perturbation types. And finally, we define a notion of (c, Hovvr for a class of perturbation types 24, introduce learners for this kind of cover and show that a class H is robustly learnable with respect to U if there is finiteddisgrremmentccoeer learner for (H,
[Hanneke] 2007] and show that such H. can be learned with
Our results on learning with abstentions show that different strategies for guarantees for different kinds of robustness (for example different types of perturbation sets) can be combined into an abstention learner that only predicts in the agreement region. The guarantees for each learning strategy then yield guarantee for the combined classifier that depends on the number of strategies used. This highlights a different aspect to the power of abstention in adversarially robust learning from what has been established in prior work [Balcan et al.) 2020 2023]. We show that abstentions can also be used to address uncertainty in perturbation types.
1.1 Related work
Providing PAC type learning guarantees under adversarial robustness requirements has received an
enormous amount of research attention in the past decade [Feige et al.) 2015 Cullina et al.| 2018
Wang et al. [20T8] Awasthi et al. 2019 Montasser et al. 2019] Attias et al. 2019 Montasser et al.
2020
Ashtiani et al. 2020 Montasser et al. 2021 Gourdcau et al., 2021 2022 Montasser ct al.
2022
Attias and Hanneke 2022 Attias et al. 2022 B Bhattacharjee et al. 2021 Awasthi et al. 2022b
2023
Mao et al. 2023 We will locus here on aspects within this literature that are most relevant to
our settings.
Most prior works study the sample complexity of adversarial robustness with respect to a fixed type of adversarial perturbation (often a metric ball with certain radius). However, recent research has developed frameworks of analysis that go beyond learning with respect to a fixed type of perturbations. It has been argued that the "correct" type of admissible adversarial perturbations (which originally were "imperceivable" modifications to input instances that lead to misclassification by a learned predictor) should depend on the underlying data-generating process [Bhattacharjee and Chaudhuri
2

---

2021
Chowdhury and Urner 2022] These studies define notion of "adaptive robustness" with respect to which predictor should be evaluated. The drawback of these notions is that the correct perturbation type is not available to the learner and thus a predictor cannot be straighfforwardy evaluated with respect to this loss. different way of relaxing the assumption of fixed, known perturbation type is provided in the framework of tolerance [Ashtiani et al. [023] Bhattacharjee et al., 20233. Here, a learner is evaluated with respect to some fixed perturbation type, while being compared to the optimal achievable loss with respect to larger perturbation type, relaxing the requirement for the learner and reflecting that the exact relevant perturbation type is typically not known (or even uniquely existing).
Most relevant to our work is a recent study on PAC learning with respect to unknown perturbation sets [Montasser et al.] 202T]. This work provides learning guarantees for the case that the robustness requirement will be with respect to an entirely unknown perturbation type without any prior knowledge about the nature of these perturbations. Those learning bounds assume access to a perfect attack oracle (as we do in some parts of this work), and require the class to have finite Littlestone dimension. In this work, we show that adding some structure to the class of perturbation types (as well as the promise that the true perturbation type will be a member of this class), allows for sample and query complexity bounds that are independent of the hypothesis class's Littlestone dimension.
Finally, there is a long line of work studying the benefits of abstentions for classification tasks [Bartlett and Wegkamp| [2008] EII Yaniv and Wiener 2010 Wiener and El- Yaniv 2015 Yuan and Wegkamp 2010 Zhang and Chaudhuri [016]] Some recent studies have also shown that the ability to abstain from prediction for manipulated instances can be beneficial for adversarial robustness requirements
[Balcan et al., 2020 [2023). However, the former studies different setting for the generation of adversarial perturbations, and the latter considers fixed perturbation types.
1.2 Overview of results
In Section 2
we define our setup, introduce the notions of learnability and loss we investigate and provide an overview of the different kinds of prior knowledge and oracle access employ. In particular, we there define our partial order on classes of perturbation types.
In Section we analyze perturbation type classes for which this order is a total order. Theorem 1 states that every hypothesis class with finite VC dimension can be robustly learned in the realizable case with respect to any totally ordered perturtbation type class. We then prove that this result cannot be extended to the agnostic case (Observation TD. This motivates investigating the benefits of a perfect attack oracle. Theorem 2 shows that the impossibility can be overcome with access to a perfect attack oracle and provides a finite sample and oracle-query bound for the agnostic case.
In Section we investigate classes of perturbation types U that are not necessarily totally ordered. We first extend our previous results on learning with access to a perfect-attack -racle to the case where U is union of finitely many totally ordered perturbation classes (Theorem 33. We then establish that there are classes of perturbation types and hypothesis classes which cannot be learned without abstention, even with access to a perfect attack oracle (Observation 3). but which can be learned with abstention without the need for access to a perfect-attack--race investigations into learning with respect to our adversarial abstention loss (Definition) 5)
(Observation 4). This motivates our
We show that in the realizable case, every hypothesis class with finite VC-dimension can be learned with respect to finite union of totally ordered perturbation types in Theorem 4 We then consider the case in which H has finite disagreement-cocfffion to every class of perturbation types (Theorem 5). Lastly, we define notion of (c, HH) for a class of perturbation types 44, which states that for every u U there is a oo-timaal hypothesis for in the cover (Definition 7 and introduce the notion of learners for this kind of cover (Definition B). We then generalize our previous results by showing that a class H is robustly learnable with respect to if if there is imiie-disagreement-comm
and show that such H can be learned with respect
learner for (H,,() (Theorem 6). While we provide some proof sketches in the main body of the paper, the detailed proofs for all results are in the supplement.
2 Setup
For sets A and B, we let 24 denote the powerset of A and A the set of all functions from to A. Let X be domain and y {0, 1} be a label space. We model the data generation as a distribution
3

---

P over X' x V. and let Px denote its marginal over X. A hypothesis or predictor is function h: X' - {0, 1. Thus, on imput X E X, a hypothesis either predicts label 0 or or abstains by outputting We call hypothesis non-abstaining if h((x) + for all x E X. A hypothesis class H is a set of non-abstaining predictors. We will let J = {0, 1,* denote the set of all predictors over X.
The performance of a predictor h is measured by a loss function E F x x + R. For loss we use the notation (h(h) B(x.g)> [e(,, 2. y)], to denote the expected loss of predictor i=1 with respect to distribution P and (s(h) Tst E ((h, z4, 3k) the empirical loss dataset S = ((x1; ..),..., (Fm, Wm)). Further, for a hypothesis class H we will let opt pp)) = inlnew (r(h) denote the approximation error of class H with respect to P and loss f.
||] The standard loss for classification tasks is the binary loss /0/1 (h, I. 9) = 1 [h(x)) * vl, where 1 denotes the indicator function. The standard loss for adversarial robustness additionally penalizes h on instance (z, y) for the existence of a perturbation on x that h does not label with y. This loss is defined for a specified perturbation type, which is a function u X + 2 that assigns every instance x E X' a sel u(x) C X with x E u(x) of admissible perturbations. The adversarial loss with respect to is then defined
8 (h, x. v) = 1 [3 E u(x) : h(z) + vl.
We will use the notation en. (h, x) to denote the adversarial component loss, which indicates whether domain point lies close to the decision boundary with respect to the perturbation type ut
e" (h, x) = 1 [3x E u(x) h(2) + h(z)].
For hypotheses that have the option to abstain from prediction, we propose variation of the adversarial loss that allows for a predictor to abstain from prediction on perturbed instances (but not on unperturbed instances) without suffering loss. The following definition captures this modification:
Definition 1 (Adversarial abstention loss). For perturbation type u X + 2* the adversarial abstention loss is defined by
1 if((t))++))))))()))))))) Fy
gu,abst (h, 2) = 1 if E u(z) such that fi(z) # y and h(2) #
0 otherwise
The main difference with adversarial loss is that if h(2) = * for an adversarial point 2 E u(z) with * x, then there no penalty and gu.abst (h, xx.)) y) O, thus allowing the predictor to abstain on points that were perturbed. This definition models the scenario where if the predictor can correctly detect that an adversarial attack has happened and abstains, then it is not penalized. However, abstaining non-perturbed points is still penalized. Note that in case predictor l never abstains (that is (xx) * * for all x E X)) the two definitions of adversarial loss coincide. We let 2% (h), f.p. au.a (%) (h), L. abst (h) denote the corresponding expected and empirical losses, and opt.p(PP))).. abab opt.p (H) the corresponding approximation errors of class H and distribution P.
Uncertain pertur type In the literature, adversarial robustness mostly treated with respect to fixed (known) perturbation type u, while learning with respect to an entirely unknown perturbation type has also been investigated. In this work, we introduce a setting that naturally interpolates between these two extremes. We assume that the true perturbation type u" is unknown to the learner, but promised to lie within a fixed class 24 of perturbation types. That is, the learner has prior knowledge of class 2/ with u² E U, where u" is the perturbation type that the learner will be evaluated with (see Definition 3 below). We can think of u² as the perturbation type that the true adversarial environment will employ to manipulate input instances and induce misclassifications We let Ziail denote the class that contains all possible perturbation types.
It is easy to see that without any restrictions on the class lt and any capability of the learner to (interactively) gather information about u² and no option to abstain, a learner cannot succeed (see also Observations and below). To gain control over potentially infinite classes of perturbation types, we will now define a partial order on a class 2/ that is induced by a hypothesis class H. This structure will prove to be conducive for learnability.
4

---

Definition 2. Let H. S {0, be hypothesis class. For perturbation types u1, we say that u1 smaller than U2 with respect to class H. and write 41 Zn U2 if and only if for all h E H. and all E X we have
eu. (h, - pu (h,
We say a set of perturbation rypes U is totally ordered, with respect to In. for every in u2 E U, we have either u1 -H U2
U2 Iz U1-
We have M1 Zn U2 if, for every function h E H. the margin area (the points which receive positive adversarial component loss) with respect to in is included in the margin area with respect ug. This is, for example, the case if all perturbation sets with respect to in are included in those induced by u2-
Resources to learners and learnability A learner is a function A (X' x y)* + F that takes in a finite sequence S = ((z1,91).... (Im, Fm)) of labeled examples and outputs predictor A(S) : - {0, 1. We will study the following PAC-type [Valiant 1984) notion of learnability of hypothesis classes H with perturbation type classes U4
Definition 3 (Learnability without abstentions). Let H. S 13x be hypothesis class and U class of perturbation types. We say that H is robustly learnable with respect to perturbation class U if there exists a learner A and a function m (0, + N such that for every e, > 0, every m 2 m(c, 8), every u" E l and every data- generating distribution P we have
Pm- CP' (A(S)) S <ppt'' (H) + 2
We speak of learnability in the realizable case if the above requirement is relaxed to only hold for all distributions P with opt's (H-) = O. Without this assumption, we also speak of learnability in the agnostic case.
If the above definition is fulfilled for a class H. then the function m (0. N in the above definition an upper bound on the sample complexity of the learning task. Note that, while we don't t require the learner in the above definition to output a von-abstaining hypothesis, predicting will always cause loss with respect L". We can thus assume all considered predictors are non-abstaining classifiers for this setting.
Note that the above definition generalizes and unifies previous notions of adversarially robust learnability. We obtain learnability with respect a known perturbation type (the setting that is mostly considered in prior works) when U {u") } a singleton class. Learning with unknown perturbations |Montasser et al.) 2021] on the other hand, is the setting where V is the set of all possible perturbation types. In this work, we are interested in studying more fine-grained conditions on the structure of (the combination of) H. and ll that allow for learnability. We will call the case where U is neither a singleton set nor the set of all possible perturbation types learning with uncertain perturbation sets.
We will show that, even when the class of perturbation types 24 in consideration is totally ordered with respect to hypothesis class H. agnostically learning H with i/ is impossible even in very simple cases (see Observation D]. We will thus, as has been done in earlier studies [Ashtiani et al. 2020
Montasser al. 202T addition allow the learner access to a perfect atlack oracle, which we model as follows:
Definition 4 (Perfect Attack Oracle). A perfect attack oracle for perturbation type u is a function On : F x X + X U (robust), }. that takes as input a non-abstaining predictor f and domain point x and either certifies that ff is robust on x with respect to by outputting robust or returns an admissible perturbation for f. That is
On(f = robuss f(=) f(x) for all = E u(x)) E u(x) with (xx + f(z) otherwise
We say that a class H and perturbation class 1I are learnable with access to a perfect attack oracle if there exists a function (0, 1)2 + N such that the conditions in Definition 3 are satisfied for a learner that additionally makes at most nnc, 8) queries to the perfect attack oracle. The function -((:-) then is an upper bound on the attack oracle complexity of the learning problem.
In Section 4 we will consider more general pairs of hypothesis and perturbation classes H and 4. We will show that if ( is not necessarily totally ordered with respect to H (or a finite union of such totally
5

---

ordered classes) there are tasks on which no learner (even with access to perfect attack oracle) can succeed (see Observation beloow). For such cases we will explore learnability with respect to the adversarial abstention loss:
Definition 5 (Learnability with abstentions). Let H. S {0. 1) be a hypothesis class and U a class of perturbation types. We say that HH is robustly learnable with abstentions with respect to perturbation class U if there exists a learner A and function (0, 1)2 - N such that for every c, 5 > 0, every m 2 m(c, 8), every u² E u and every data generating distribution P we have
PS- [Cp [Cy"
,abst (A(S)) S opty (H) + 2 5
Note that since H. contains only non-abstaining predictors, have optiy' (H) optp abst (H).
Discussion on additional parameters and assumptions Throughout this paper, we will also work with various standard complexity measures, such bounded VC-dimension or bounded Littlestone dimension of the hypothesis class H. bounded VC-dimension of the loss class or the adversarial component loss class. We refer the reader the appendix for reminder of the definitions of these notions
We will further assume that learners have the capability identify empirical risk minimizing hypotheses from a class. It is standard (though often implicit) to assume this as oracle access for the learner as well. We consider the standard ERM oracle, a robust ERM (RERM) oracle (for fixed perturbation type u) and maximally robust ERM (MRERM) oracle (for a class U of perturbation types, and realizable samples only). We define the following oracles:
ERMH : S - hs E Brgmin 0/1 (
RERM : S - his E arg (5))
(h ug) with hgsh E argmin Cos (h), and utg is Zн maximal in the set {u E U minne (h) = 0} error if (h) 0 for all U and h H
MRERM : S +
That is, we will assume that MRERM will return an error if the sappee S is not e"-realizable for any u E U. If, on the other hand, there does exist a u E l for which S is L f"-realizable. then MRERM4 will return maximal (with respect to In) such perturbation type ug and corresponding
hypothesis hi with 2g (hg') = O. In particular, we assume that for every non-empty sample S there exists such a maximal element usg e L and corresponding ERM hypothesis from H. While these do not always exist in 22 and H. a priori, it has recently been shown that it is possible to embed 21 and H into slightly larger classes so that the MRERM², oracle is always well defined [Lechner et al. 2023]. See Appendix Section A for more details on this.
Since we focus on studying sample complexity (independently of computational considerations) and consider learners as functions throughout, assuming access to the above oracles is not restricting the validity of our bounds. It is still interesting to understand when their existence reasonable to assume. Both ERM and RERM oracles have been widely used in the literature and they are often computationally hard to implement. Assuming their existence, however, an MRERM oracle can be easily implemented for the case where 2/ is finite and totally ordered by running a binary search over U and calling RERM for the comparison step. If we assume U/ is parametrized by k-bit number, then this requires Okk queries to RERM.
3 Learning with totally ordered perturbation class
We will start with investigating the case where the perturbation class 14 is totally ordered with respect to hypothesis class H (see Definition D. Note that if two perturbation types i1 and U2 we satisfy un (I) C (z(x)) for all E X, then d1 is smaller than U22 h1 In U2 for every hypothesis class H C 10 1 This is, for example, the case when iı and u2 assign balls (with respect to some metric) centered at x to every domain point x and U2 always assigns ball of radius at least as large as the ball assigned by un (while the balls assigned by in and u2 are not necessarily required have the same radii uniformly over the space X').

---

In this section, we will focus on learning with respect to the standard adversarial loss and thus only consider non-abstaining predictors. We first show that for H. and totally ordered 24, whenever the class H has bounded VC-dimension we get learnability in the realizable case. This result is based on adapting a compression argument for adversarially robust learning [Montasser al. 2019] to the case of uncertain perturbation sets. A very similar adaptation has recently been made for the related problem of strategic classification [Lechner et al. 2023). The proof of this result can be found in the appendix.
Theorem 1. Let be a perturbation class that totally ordered with respect to a hypothesis class H with VC(H) d Then H is learnable in the realizable case with respect to l with sample complexity O (o2g-))
Recall that realizability here means opt (H) 0 for the true perturbation type u² (with respect to which the learner evaluated). We now show that without this assumption learning guarantees impossible without equipping the learner with additional resources (or weakening the success criteria).
Observation 1. There exists class H with VC(H) and perturbation class U that is totally ordered with respect to 'H that is not learnable (in the sense of Definition 3).
We will now show that allowing learner access to perfect attack oracle yields learnability in the agnostic case.
Theorem 2. Let U be perturbation class that is totally ordered with respect to a hypothesis class H with VC(H) = < co and assume access to a perfect attack oracle. Then H. is learnable in
the agnostic case with respect to U with sample complexity mle,5) = 0( d-2" complexity ((m(e,5)))
0( log(1/6) and oracle
Proof. We will employ well-known reduction from agnostic learning to realizable compression- based learning [Montasser et al. (201)). Since our proof for Theorem for the realizable case of learning with uncertain, totally ordered perturbation sets employs compression-based learner, for the agnostic case suffices to show that, given any sample S = ((x1, v1), (Ims Bm.),, we can identify a largest subsample S' of S that is realizable with respect to the underlying perturbation type u". We will now outline how the perfect attack oracle can be employed to achieve this.
Employing the FIRERM4-oraan ((S), hy, ui).... (S,, hy un ))) of subsamples of S that are realizable with respect to some u U. such that (h₃, uz) = MRERM M (S.) for all i and u, In Uj for all S j. Note that we have u* In u; if and only if the perfect attack oracle returns robust for all sample points in S, when tested on h, that is O.. (h.hh,, x) robust for all with (x, E S; for some y. Thus, using binary search over the list T, we can identify the smallest index e for which u' ZH u. Since we have S 2 and every test in the search employs at most calls to the perfect attack oracle, this search terminates after at most m² queries. Finally, note that all subsets S; from for which 2 i realizable with respect to u". Thus realizable subset with respect to the unknown perturbation type u².
the learner can generate an ordered list T
choose any largest among S.,... Sn maximal
In Section B we provide additional guarantees for the agnostic case.
4
Beyond totally ordered perturbation classes
We now consider a more general setting where U/ is not necessarily totally ordered with respect to H.
4.1 Learning with the standard adversarial loss
We will start by showing that H. 24 are learnable with access to a perfect attack oracle if U is the union of & sub-classes which are each totally ordered with respect H. This naturally contains the case that 24 is finite. Another natural case where this occurs is considering perturbation sets that are balls around domain points of certain radii and with respect one of number of possible norms. Consider X' = Rd and the set
U {ut I I BF(x) T IR, e 0, 0,1,2
7

---

where we let (x) denote the e" no-n ball around .r. Then the above class U is a union of 4 totally ordered perturbation classes (one for balls of each norm) with respect to any hypothesis class H.
Theorem 3.
oo, and let U be a perturbation class, which is union U = U1 UU2 U... U of k subclasses which are each totally ordered with respect to class H. Then H is learnable with access to a perfect attack oracle Ou- in the realizable case with log(k).logg (/) (e))+ and query complexity
Let H be a hypothesis class with VC(H)
respect to U with sample complexity O d:2" 1og(k/) O(( (og(())logg1////tggg///
Proof. We can generate hypotheses h1, b2...., , that are the output of an (c, -uccesssull learner for H. with respect to each of the Us Since each of the classes U; are totally ordered with
respect to H. the result of Theorem | tells us that O d-2" log(k/51) sample points suffice to guarantee that, with probability at least 1 - 8. we have en (h,) S for all i with u E U4 Thus the class Hss - (h. ; h } of these learning outputs has approximation error at most e with respect to the data generating distribution P. Note that, since we have [7al h. this class has also bounded L Littlestone dimension at most log(k)). Employing a result (Montasser et al. [202T]. Theorem 3) on agnostically learning finite Littlestone classes with access perfect attack oracle, an additional O (og(()))og((/e))))) (oo(///))+ooo(1/555) samples and the stated number of queries suffice to output hypothesis
with CP (h) & 3e.
It is not difficult to see that, even in the realizable case, and when 2/ is the union of just two totally ordered subclasses, learner without access to a perfect attack oracle cannot succeed with respect to the standard adversarial loss.
There exists a class H with VC(H) 1 and perturbation class Ui that is the union of two totally ordered subclasses with respect to H that are not learnable in the realizable case (in the sense of Definition 3) without access to perfect attack oracle.
Observation 2.
For the proof of this observation we refer the reader to the supplementary material. Now we show that if we remove even more structure from the set of perturbation types 2/ then learning success becomes impossible even with access to a perfect attack oracle. The following observation will then motivate to investigate learning with respect the adversarial abstention loss (rather than the standard adversarial loss).
There exists a class H with VC(H) = learnable (in the sense of Definition 3) even with access to a perfect atlack oracle.
Observation 3.
1 and a perturbation class U that are not
Proof. We consider the same domain, class, and distribution as in the proof of the previous observa- tion: X Pwih P((-3, 1) P((3, 0)) = 0.5, and
H {h+ x 1 | t) t E
Further, we consider the class U {unbb a, R} of perturbation types Wa,b, that assign all points x S O to a ball of radius a around x and all points x > 0 to a ball of radius b. Then, even when promised realizability, learner cannot distinguish the cases where u* Ma,b for some values a, with a + b < 6 from samples and any finite number of queries to the perfect attack oracle. In particular, if u² Ua.6 for some a, b with a + 6, predicting with respect to one such pair a, b will induce loss 0.5 for all other such pairs.
4.2 Learning with the adversarial abstention loss
We will now consider learning with respect to the adversarial abstention loss. We will first show that learning with abstentions can actually help overcome some of the impossibilities shown above. For this, let us revisit the example seen in Observation 3
Observation 4. There exists a class H with VC(H) = and a perturbation class U that are not learnable (in the sense of Desinition 3. even with access to a perfect altack oracle, but that is robustly learnable with abstentions (in the sense of Definition 5 in the realizable case (without access to perfect attack oracle).
8

---

Proof sketch. We consider the example from the proof of Observation Now consider the sub- classes 21 {ua,o
R] and 242 = fuo.s b RR. Since both Un and Uz are totally ordered we can learn successful hyptheses h1 and h2 respectively. We now define h : X' - {0, 1, }} by h(x)) = y b1 (x) = he(ar) = y and h(x) * otherwise. This is successful hypothesis. For more detail, we refer the reader to the appendix.
L
We will now continue by showing that, similar to the case where we have access to perfect-attack- oracle, finite union 4 - U, of totally ordered perturbation sets U4 is robustly learnable with abstention in the robustly realizable case.
Theorem 4.
Let - Us where every Us is totally ordered. Furthermore, let H have a finite VC dimension. Then H is robustly learnable with abstension with respect to U in the robustly realizable case with sample complexity Oe (-22*-2log(k/0))) log(k/6))
4.2.1 Abstention learning with disagreement coefficient
The proof of Theorem shows how bounding the mass of the region on which two learners with small 0/1-loss disagree, yields robust error guarantee for learning with abstentions. In this section, we will review the definition the disagreement coefficient (Hanneke) [2007], Hanneke et al. (2014), and show that hypothesis classes H. with finite disagreement coefficient robustly learnable with abstention in the realizable case with respect to every class of perturbation types U. For distribution Px over X, we let the -x-inddeed difference between two hypotheses be denoted by
d (h, h²) = Px (Mx) * (x))..
The ball in H around hypothesis h with radius then denoted by Bp (h, r) {h' H d (h, h') S r).
Lastly, the disagreement region of a set of hypotheses H be
DIS(H) = {a E X 3h, h' E H with h(x) + 1 (x)).
We can now state the definition of the disagreement coefficient.
Definition 6 (Hanneke et al. [2014).. For distribution P over X x y and class H C (0, 1)x, let h E arg minwen Lp(h'). The disagreement--coffiiionn of with respect to P defined by:
(xI(S((((I))
(r(H)
sup rE(0,1)
r
Furthermore, let the worst-case disagreement coefficient be 0(H) SUPPEA(XXX) (p(H).
Theorem's 5. Let H. be hypothesis class with ((H) < co and VC(H) oc. Then the class H. is robustly learnable with abstention in the realizable case with respect to the class of all perturbation rypes U with sample complexity O d+log(
The proof can be found in Appendix D.6 but the main idea is that for any point x, we return a y E {0,1) 1} if and only if every h with 071 (h) 0 agrees with y, otherwise abstain. Because of the bound on the disagreement coefficient, one can show that for a large enough S, this leads to hypothesis with low abstention loss.
4.2.2 Abstention learning via e-cover
We will now generalize our previous results, by introducing the concept of (e, -cover. Definition 7 ((e, H)-cover of U). Let H C {0, 1}x be a hypothesis class, distribution over X' x y and l a class of perturbation types. A set of hypotheses H' is a (e, Hovcover for it with respect P, if for every U, there exists an h' H' such that (%()h)) < inf (%)(h) +
We will now provide the definition of a successful cover learner.

---

Definition 8. Let H S {0, 1 be a hypothesis class, and U be class of perturbation types. We say a function Acover (X 37" 210,1)* that maps sample S hypothesis class H C J a suc- cessful finite- muitt--disgreement-oovvee learner for H,, there is a function M(H.24),cveer (0, + N, such that for every e. n. (0, 1), every m 2 MHH comeer (c. 5) and every distribution P over X x {0,1] 1} with probability 1 over ~ pm both of the following statements hold:
A(S) is (c, cover for U with respect P
Px((DIS(((S) n.
We note that any successful cover learner, that is guaranteed to output a finite set is a successful minte-disarreement cover learner. The case, where U is union of k totally ordered perturbation type classes UN we have seen before, can be interpreted first learning cover H of size k. where each of the element of the union "covers" one of the classes. The case in which H has a finite disagreement coefficient can furthermore be seen as a case where the set of all ERMH hypotheses constitute an (e, H) -cover H' for every class of perturbation types lt The mass of the disagreement region of H is then bounded by the disagreement coefficient. We now state our result generalizing these observations.
Theorem 6. A class H. is robustly learnable with abstentions with respect to U in the robustly realizable case, if there is successful fniite-disgrrement-covvrrr learner for (H, U). Furthermore, the sample complexity of robustly learning with abstentions is then bounded by muzule, 5) S mH coveer (c/2, c//2,(/2,5)
Inspired by considerations of adaptive robustness radii [Chowdhury and Umer 2022, Bhattacharjee and Chaudhuri| 2021). in Section of the appendix we discuss a setting of abstention learning in which we allow the size of the perturbation sets to vary locally between different regions of the domain. We provide a learning guarantee for this setting that is not covered by our previous results.
Conclusion
In this work we relaxed the assumption that we know exactly the perturbation sets that are to be used by an adversary. Our model provides an interpolation between knowing the perturbation sets exactly and not knowing them at all. Many of our results rely on realizability. We have also shown that without realizability, learning is not possible unless the learner receives other feedback, such as access to perfect attack oracle. It might be interesting to consider some milder relaxations of realizability. For example, instead of saying opty' (H) = O, what we only know that the adversarial Bayes loss is zero for some u² ti?
While our work focuses on statistical aspects, it will also be interesting understand the kinds of computation required for our results. For example, we rely on the existence of an MRERM oracle. When are they computationally feasible? Do we require accurate MRERM oracles or can approximate (and hence potentially more tractable) versions also be used for the learning task?
Another question is find a dimension that characterizes learning in various settings. This was only recently resolved for udversarially robust learning (for the case when u is known) Montasser et al. [022]. however, the dimension proposed in the paper is not easy to define. On the other hand, in the setting when the only information we can obtain about is through a perfect attack oracle, the Littlestone dimension of H has been shown to characterize adversarially robust learning Montasser et al. [2021]. It will be interesting to see if such a simple dimension can be obtained for the settings considered in our paper.
Acknowledgements
Ruth Urner is also a faculty affiliate member at Toronto's Vector institute, and acknowledges research support through an NSERC discovery grant. Tosca Lechner is supported by a Vector Research Grant and Waterloo Apple PhD Fellowship in Data Science and Machine Learning.
10

---

References
Hassan Ashtiani, Vinayak Pathak, and Ruth Urner. Black-box certification and learning under adversarial perturbations. In Proceedings of the 37th International Conference on Machine Learning, ICML, pages 388-398, 2020.
Hassan Ashtiani, Vinayak Pathak, and Ruth Umer. Adversarially robust learning with tolerance. In International Conference on Algorithmic Learning Theory, ALT, pages 115-135, 2023.
Idan Attias and Steve Hanneke. Adversarially robust pac learnability of real-valued functions. arXiv preprint arXiv:2206.12977 2022.
Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for robust
learning. In Algorithmic Learning Theory, ALT, pages 162-183, 2019.
Idan Attias, Steve Hanneke, and Yishay Mansour. A characterization of semi-supervised adversarially robust pac learnability. Advances in Neural Information Processing Systems, 35:23646-23659, 2022.
Pranjal Awasthi, Abhratanu Dutta, and Aravindan Vijayaraghavan. On robustness adversarial examples and polynomial optimization. In Advances in Neural Information Processing Systems, NeurIPS, pages 13760-13770, 2019.
Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. H-consistency bounds for surrogate loss minimizers. In International Conference 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.
Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, and Hongyang Zhang. On the power of abstention and data-driven decision making for adversarial robustness. CoRR, abs/2010.06154, 2020.
Maria-Florina Balcan, Steve Hanneke, Rattana Pukdee, and Dravyansh Sharma. Reliable learning for test-time attacks and distribution shift. CoRR, abs/2304.00370,, 2023.
Peter L. Bartlett and Marten H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 9(59):1823-1840 2008.
Robi Bhattacharjee and Kamalika Chaudhuri. Consistent non- non-par con-paraettric methods for maximizing robustness. In Advances in Neural Information Processing Systems 34 NeurlPS, pages 9036-9048 2021.
Robi Bhattacharjee, Somesh Jha, and Kamalika Chaudhuri. Sample complexity robust linear classification separated data. In International Conference on Machine Learning, pages 884-893 PMLR, 2021.
Robi Bhattacharjee, Max Hopkins, Akash Kumar, Hantao Yu, and Kamalika Chaudhuri. Robust empirical risk minimization with tolerance. International Conference on Algorithmic Learning Theory ALT, pages 182-203. 2023.
Sadia Chowdhury and Ruth Urner. Robustness should not be at odds with accuracy. In 3rd Symposium on Foundations of Responsible Computing, FORC, pages 5:1-5:20, 2022.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. In Advances Neural Information Processing Systems, NewrIPS, pages 230-241, 2018.
Ran El- Yaniv and Yair Wiener. On the foundations of noise-free selective classification. Mach. Learn. Res., 11:1605-1641, 2010.

---

Uriel Feige, Yishay Mansour, and Robert Schapire. Learning and inference in the presence of corrupted imputs. In Conference on Learning Theory. COLT, pages 637-657, 2015.
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell. On the hardness of robust classification. J. Mach. Learn. Res., 22:273:1-273:29 2021.
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell. Sample complexity bounds for robustly learning decision lists against evasion attacks. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI, pages 3022-3028, 2022.
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Machine Learning, Proceedings of the Swenty-Fourd International Conference ICML, pages 353-360, 2007.
Steve Hanneke et al. Theory of tisagreement-basee active learning, Foundations and Trends@ in Machine Learning, 7(2-3):13 131-))111-309 2014.
Tosca Lechner, Ruth Urner, and Shai Ben-David. Strategic classification with unknown user manipu- lations. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 18714-18732 PMLR, 2023.
Anqi Mao, Mehryar Mohri, and Yutao Zhong. Cross-entropy loss functions: Theoretical analysis and applications. arXiv preprint arXiv:2304.07288, 2023.
Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learnable, but only improperly. In Conference Learning Theory, COLT, pages 2512-2530, 2019.
Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro. Efficiently learning adversari- ally robust balfspaces with noise. arXiv preprint vrXiv:2005.076533 2020.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Adversarially robust learning with unknown perturbation sets. In Conference on Learning Theory, COLT, pages 3452-3483 2021.
Omar Montasser, Steve Hanneke, and Nati Srebro. Adversarially robust learning: A generic minimax optimal learner and characterization. Advances in Neural Information Processing Systems, 35: 37458-377 -74700, 2022.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference Learning Representations, ICLR, 2014.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. 7th International Conference on Learning Represen- tations, ICLR, 2019.
Leslie Valiant. theory of the learnable. Commun. ACM, 27(11): 1984.
Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. In Proceedings the 35th International Conference on Machine Learning, ICML, pages 5120-5129, 5299, 2018.
Yair Wiener and Ran El-Yaniv. Agnostic pointwise-compeetiive selective classification. Journal of Artificial Intelligence Research, 52:171-201, 2015.
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov. and Kamalika Chaud- huri. closer look at accuracy vs. robustness. In Advances in Neural Information Processing Systems 33, NeurIPS, 2020.
Ming Yuan and Marten H. Wegkamp. Classification methods with reject option based on convex risk minimization, J. Mach. Learn. Res., 11:111-130, 2010.
12

---

Chicheng Zhang and Kamalika Chaudhuri. mistakes and abstentions. Proceedings of the 29th Conference on Learning Theory, COLT, pages 1584-1616, 2016.
The extended littlestone's dimension for learning with
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference Machine Learning, ICML, pages 7472-7482, 2019.
13

---

A Maximally Robust Empirical Risk Minimization
Recall the definition of the empirical risk minimization oracles:
0/1 (h) ERMx: : S - hi E argmin S
RERME : S + his E argmin (h))
(h's uz)) with hss E argmin C (h),
MRERMA S +
and u'g In maximal in the set {u E U minsgh (b) 0} error if (h) for all U and h H
While there always exists functions hs and hy that are solutions to the queries in the first two oracles, the last one requires a bit more care.
Let be some labeled dataset and assume that H. and are hypothesis and perturbation type classes such that S is H-realizable for the true perturbation type u' U. We can then define maximal perturbation type usg for S, H and U as follows:
u's (x)
U
u(z).
weld such that minnew n 43()==0
This defines a perturbation type (2), which is not necessarily in Ui but does satisfy u² IH ug- which suffices for our purposes.
If, given ugg, the set argmingen Ch (h) is non-empty, the oracle can return any function in this set as hgg.. We will now argue that we can define a "closure" H of the hypothesis class H. which has the same VC-dimension as and such that h H.
We here show how such an embedding of H into the closure class H. can be constructed in the case of a countable domain X' and perturbation class U that is separable, in the sense that for every UI C U there exists a countable subset U1" C l', such that for every x E X Uweu u(x) Uneur u(x)) This is the case for a wide range of perturbation types, in particular in the case for which the sets (xx) are always open balls with respect to some lp- no-morm in Rd. In the general case (where X' may be uncountable and 24 not separable in the above sense) recent work has shown that the existence of closure class with identical VC-dimension is still guaranteed [Lechner al.) 2023). The more general construction there employs the set-theoretic concept of filters. It is shown in the context of strategic classification, but the technique is readily available adversarial perturbation sets. We here illustrate the intuition behind that abstract construction by focusing on countable and separable case.
We now assume that X' is countable and let (æt)ien be an enumeration of the elements of X. The separability assumption on the perturbation class 2 implies that for all S there is countable subset U C l such that for all x E X' we have
(z)
U
w(x)).
ueM such that minAg (3 (h)=0
For given sample S, let (ux) SeN be enumeration of the set
{u E ut
min (h) = 0}
NEW
and let (hi)seN be an enumeration of corresponding empirical risk minimizing hypotheses from H::
h4- = RERM
We will now define the function hī3 by successively choosing subsequences from the sequence (ha) as follows. We set Fu (he)se and Jo N. Then, for every i N, we define set of indices J, such that
Case 1: There exists a le E J:-1 such that (z,) = hx(2x) for all j 2 k,j E J-11 Then we define:
J: (ie J:-1 hy(x,) (x,))
14

---

Case 2: Both labels are assigned infinitely often to by the sequence (h1))EJi_,. Then we define
J4 = J4-1 (z f}
and we define subsequence F; = Je., Note that, by construction, in each resulting sequence Fú the first points #1; #1: ................................ I; receive the same label by all functions in the sequence. Now, by choosing indices to select the i-th function from each sequence F; (by choosing the first index of J1, the second index in J2, the third in J3 and on), and re-identifying these indices with the natural numbers, we obtain yet another subsequence F (fi)ee. In this sequence we now have for every i N and every h:
Ja (m:) f(())).
That is, this sequence of functions converges pointwise and we can use the above equation define the function hig as follows:
5 (z,) f((x)).
is not difficult to see that the so defined function hig satisfied L.g (h"²)) Let H be defined by adding these function his to H. for all possible S.
"5 E (0.13*1SE(xx))) H = = (1
We observe that every behavior that H exhibits on a finite subset C S X, is already witnessed by a function from H. Thus we get VC(H) = VC(H), and we can always let MRERM return function from H.
B Agnostic learning for finite unions of total orders
Let H a hypothesis class with VC(H) = < oo, and let U be a perturbation class, which is union U U2 UU2 U... Ully of k subclasses which are each totally ordered with respect to class H. Then H is agnostically learnable with access to a perfect attack oracle Ou- with respect 6)+ + m2(e, 8), and query complexity (I(E, () + T22 8) where: to U with sample complexity m (),6)
Theorem 7.
m)) = O(( d-2" 1ogg2l
m2(e,5) is the sample complexity of agnostically learning a hypothesis class of size k wrt u
mi(e,8) k (m (tni(e;6))
nz(c, 8) is the query complexity of agnostically learning hypothesis class of size wrt a
Proof. We can generate & hypotheses h1 h2...., h& that are the output of an (c, succcessfl learner for H with respect to each of the U4 Since each of the classes U4 are totally ordered with respect to H. the result of Theorem 2 (combined with a union bound) tells us that mi (e, 8) sample points and n (e, d) queries suffice to guarantee that, with probability least 1 - ō, we have ga (h₂) S opty (H) + for all with u E 24, Thus the class H4 {h1, fg...., , h23 of these learning outputs has approximation error at most opt (H() + c with respect to the data generating distribution P. Note that, since have [H4l k. this class has bounded Littlestone dimension at most log(k) k). VC-dimension at most log( and dual VC-dimension at most k. Employing result (Montasser al. 22021) Theorem 4) agnostically learning finite VC classes with access perfect attack oracle, get that both ma(e, 8) and n2(ee, 8) are finite and CB (h) opt (H) 2c. I
c-cover Learning
C.1
Abstention learning for regions with different radii
Let us now explore the case, where we allow our perturbation types to consist perturbation sets whose size varies throughout the domain. While a lot of work assumes that the size of the radius
15

---

is fixed throughout the domain, it is not prior clear that the distances in the domain correspond perfectly what humans find perceptible. This was noted in prior works (Bhatacharjee and Chaudhurij 2021 Chowdhury and Umer 2022] and motivated their adaptive adversarial loss. We explore such variation of local radii for the setting of uncertain perturbation sets. We have seen examples of this in Observation 3 and Observation 4. We will now generalize these perturbation types. Let = R. For a function f ; + [k]] let the perturbation type uf,a defined by:
uf (x) Ba)
That is, we have & different regions in the domain, which determined by f. Furthermore, assume that each perturbation set within a region is a ball with radius of a fixed size a, while radii vary between regions. For fixed function f. let us now consider
Uj {uf,ar.....a .1,.... Og E R].
Let VC(H) < VC(H x U)) S d. We note that in general, that is excluding particular hypothesis sets H and function J, this set of perturbation sets cannot be expressed as a finite union of totally ordered sets.
a, E RJ. Let P be a realizable For every i E [k] consider the classes U = {uJ,,,.... 0............ 0.................00
distribution with respect to H and u² E u. Let m(c, 5) = ( where C' is the constant o²
we require to get uniform-convergencc guarantee (which exists due to the corresponding VC- dimensions being finite, see -Shale--Shwarte and Ben- David (2014), D and let m m( ((262 )-
Now for a sample S and any i, let (h, u.) MRERM (S). We denote by a the maximum realizable radius for component i, i.e. Ao....0.amaa O.....0 h4- Now let u² = "fai.... be the ground true perturbation set. Then for every i, oj S Samuas Let u mar Uffaaaaz ,...,aa.e We note that for every E N, E 3' and h F, we have g" gumaa (h, v) I maxie[s| L" (h, v, Now let
h(x) = y if for all i: h₂(2)=
otherwise.
We note that by the PAC-learning guarantee with respect to 0/1-loss, with probability - 6, for 2: every i,j [k] we have a pairwise disagreement between h; and hy of most +2c* Thus the
risagreement-region of (hę : i E [ has mass at most the sample generation the abstention loss of we have
22. +1E
Thus, with probability 5 over
h [CE (h.)
Cp abst (h) S Cp
mam abst
(h) S
Cu' P
abst (h)
S
Px((x Px)) h(x) = x}))
1=1
2 =c.
< k(
k(2h2 +1)
k(2k2 +1)
Note, that we can thus view {h} as an (H, coover 2 with respect to and adversarial abstention loss.
D Proofs
D.1 Proof of Theorem
Proof. For this result we adapt a compression based argument for the case of fixed perturbation type [Montasser et al. 2019 to the case of class 1/ of perturbation types. similar adaptation has recently been shown for the setting of strategic classification [Lechner et al., 2023). The key difference to the original compression scheme is that we use the MRERM4 oracle for the weak leamner in each round of boosting, rather than the simple RERMY, oracle as is done in the original publication [Montasser et al. 2019]. Importantly, the maximal ERM paradigm is well defined on all subsets of an original given data sample. and thus each required weak hypothesis can be encoded with a finite number of samples. Finally, since the maximal perturbation type for any subsample is always at least as large as the true perturbation type (under the realizablity assumption), using MRERM for each boosting step we obtain the required guarantee for the true perturbation type (without the learner/compressor requiring knowledge of the true type). We thus obtain the same compression size and implied sample complexity in the case of totally ordered class of perturbation types as for fixed perturbation type.
16

---

D.2 Proof of Observation 1
Proof. Consider a finite domain X {21, 22, va} and distribution P over X' x {0, 1] with
P((a1, 1)) = 1/4, P((aa, 0)) 3/4 and P((x,)) = 0 for all (z, v) & {(x1, 1), (Iz, 0)}. We define a class = {ui, (a containing two perturbation types on and u2 defined as follows:
"1 (11) = 42h "n (x22) = {22). un "1(xs) = {2y}
and
Uy (2))))) = {01, x2), u2(x2) - {12), u2(2x) (x22 2z5
We let hyywgs denote the function that labels H; with yi on this domain (there are only different non-a con-abstanning predictors over X), and let H = (h110, h100} be a hypothesis class containing only two of these predictors. Clearly VC(H) = and In = Note that
opt'' (HL) = Lp (h110) = 0
while LP (ayy 2 1/4 for all predictors Nyive * h110- We further note that
o (H) cp (hoon) Lix (hooa) 1/4
while Cp (hy19 2 3/4 for all predictors h 2y1 & {hooo. h100 Samples from P will not allow distinguishing whether the true perturbation type is i1 or u2 (since we are not imposing a realizability assumption here). Thus, no learner will be able to output predictors that are (close to) optimal for all possible perturbation types in U.
D.3 Proof of Observation 2
Proof. We consider X' R and H. to be the class of threshold classifiers
H (h+ x [ S t) E RR.
Further consider 14 4_ UU4, where 4_ consists of perturbation types u, that assign each æ to ball (interval) of radius r around if 0 and ball of radius r/2 around if æ 0, and U_ similarly consists of perturbation types u, that assign each r to a ball (interval) of radius r around if æ >> and ball of radius r/2 around if x S 0. Both U_ and U totally ordered (with respect to any hypothesis class) but their union 2/ is not totally ordered with respect to H. Consider a distribution P with P((-3, 1) P((3, 0)) 0.5. Then, even when promised realizability, a learner cannot distinguish the cases u² W4 and u" = from samples; and performing well with respect to one of these perturbation types will induce loss 0.5 with respect to the other.
D.4 Proof of Observation 4
Proof. We consider the example from Observation 3 Now consider the classes Ui {ua,a R} and U2 {uo. R}. Since both U1 and U4 are totally ordered there are successful robust learners Ai for H with respect to ii and Ae with respect to U2. We run both learners on sample with a size to guarantee (e/2,8/2)-suce Succsss in both cases. We denote the resulting hypotheses with h1 and hz respectively. We now define X >> {0, 1,*) by huxx) = y if h1 h2(xx) = y and h(x) otherwise.
We now argue that with probability 1 6, h has adversarial abstention loss less than e. Let u² Uba E ld be the ground-truth perturbation type. Now let P be any f -realizable distribution. Let (t, Maa.0a .0) MRERM4 (S) and (,,0)) MRERM H (S). With probability 1, we have both a1 > a" and b2 > b* Further, we note every x e X and every Ua Ut g (h, æ, y) is either determined by f and y b, h and y, not both, since either < 0 or O. This means, that for every x E X, ( b2 (h, x, y) I max (f"ar ((, x. y), 000.00 (h, x, })
Combining these observations, we get
CD. .abst ab)) < Lt by abet (h) < May a,bbst o0, (h) + 20 abst (h)
6 E
+
2
2
17

---

D.5 Proof of Theorem 4
Proof. We assume robust realizabilityy with respect U. In particular this means that we are in the non-robustly realizable case. Thus for any U4 we know that the set U = U, U (f(x} x E } totally ordered and that it contains some u, E UJ such that H is robustly realizable with respect to the ground truth distribution P and u, We know from Theorem I that for every i, there is successful maximally robust learner A; for H with respect to Uj in the realizable case, since Ui totally ordered.
Now let A be defined by
iff for all i E [K] we have (z)) iff for all E [k] we have (z)
A(S)(a)
otherwise
Furthermore, let (h, us (S)) MRERM (S). Now let u² E U be the ground-truth perturbation type. We know that there is [k:), such that u" 3 up. Let P be a distribution with opt (H) 0.
Now if pm with 2 max4elk| ml _रेFI }) then with probability 1 6, for every E [k],
CP (A((S) S 2T and therefore. CPp (A)( S 2R" Thus, for any two i, E [k], we have
2E
Px(H A(()( + (,(S) & 21 +1
Thus,
Cp abst (A(S)) S Cp abstt (A,- (5)) Ex (()) = =+])
- Cp
(A) + Pr((=E X:
# ((())))))
2 E
2k +1 c.
2k +1
D.6 Proof of Theorem 5
Proof. Let E elall be any perturbation set and P any distribution with opty' (H) = 0. Furthermore,
let m 2 mx((, 8) where mı is the sample complexity function in O d log(
Let S pm Let
(
A {h E H: // (h) = 0}. Now we define our output hypothesis h by if for every h E H. : h(x)==)))))))()))) =
h
if for every h H : h(x) = 0 otherwise.
We note that there is some h²' E H with C3 (h1) = 22/1((1)) (h*) O. Since every h H is ERMs hypothesis and H has VC dimension d, the sample of ERMS gives us
Cp abst
(h) S cp ,ahst (h") + Px E X: (z) + h(x)))
S < (1t) + Px((2r X: x:)(s) = x])
0 (DIS((B(, ((T)))) 1) =c.
D.7 Proof of Theorem 6
Proof. metm 2 my H. Houoe
and S ~ pm, let E Ul the ground-truth perturbation (e/2,e/2,0) (e.ooeeee//,ee
set. We define the abstention learner as:
if for all h E Acooer (S): M(x)) 1 if for all h E Acover (8) h(x) 0 otherwise
A(S)(z)
0
18

---

Then with probability 1 6, Px (DIS(Accoee))) (coo))())) - and 3h E Acover (S) with < (h) 1
min h'eH
Cp (h') + c/2.
Since for every X' either (a)) (x) Acover (S). Thus,
cy abett (A(S)) S Cp abst
(h) + (x (S))) - min Cp NEW
..ssbbtt (hb) +
19


Reviews:
[{"review_id": "eGvZufTYr5", "reviewer": "Reviewer_o4ch", "summary": "In adversarially robust PAC learning to test time attacks, usually we assume that the learner knows the perturbation function. \nMontasser et al. ['21] studied a setting were the learner doesn't know the perturbation function, but can interact with it through some oracles. In this paper, the setting is in between, assuming that there is a class of possible perturbations $U$ known to the learner, and the performance of the learner is measured on the worst-case perturbation function in this set. For example, the perturbation can lie in a ball centered in the original input, but the norm isn't known. \n\nThe main contributions are as follows. \n\n- Considering an order on $U$ w.r.t. $H$, finite VC is sufficient for learning in the realizable case, but not in the agnostic case. \n\n- When the learner can interact with $U$ through a perfect attack oracle, and assuming some structure on $U$, finite VC is sufficient for learning. This is an improved result compared to the setting of an unknown perturbation function, where finite Littlestone dimension is sufficient, and $VC(H)\\leq Lit(H)$ and the gap can be arbitrarily large.\n\n- Introducing a setting where the learner can abstain, and showing that finite VC is sufficient for learning (assuming some structure on $U$).\n\n- Assuming that $H$  has a finite disagreement coefficient (a parameter that is related to active learning), then $H$ can be learned with respect to every class of perturbations.", "questions": "-", "limitations": "I don't see any.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The in-between setting of robust learning suggested in this paper is natural and complements the picture of the other two settings (known $U$ or completely unknown $U$).\nThis paper studies thoroughly various scenarios, showing some limitations of this model, and when we can guarantee robust learning. \nThe results look correct to me. \nI think that this paper could be of interest to the community of theoretical robust learning.", "weaknesses": "If I'm not missing anything, the technical contribution of the paper is moderate and mostly relies on standard ideas from PAC learning. \n\nMany references on theoretical robust learning are missing. For example, H-consistency bounds for surrogate loss minimizers (ICML 2022), Multi-class H-consistency bounds (NeurIPS 2022), Theoretically grounded loss functions and algorithms for adversarial robustness (AISTATS 2023), Cross-Entropy Loss Functions: Theoretical Analysis and Applications (ICML 2023), A Characterization of Semi-Supervised Adversarially Robust PAC Learnability (NeurIPS 2022), Adversarially Robust PAC Learnability of Real-Valued Functions (ICML 2023), Sample complexity of robust linear classification separated data (ICML 2021)...and many more!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the additional references! We will make sure to include them in the final version!\n"}, {"review_id": "sAyfQkH6Qa", "reviewer": "Reviewer_hPab", "summary": "The authors present theoretical results on classification in a version of the PAC model where an adversary can perturb input instances.  Previous work assumed either a fixed perturbation type, known to the learner, or an unknown perturbation type.  This paper explores a middle ground where the perturbation type is a member of a fixed class of perturbation types.  The learner knows the class, but does not know which perturbation type within that class is being used.  For example, the perturbation class might correspond to balls with different radii.\n\nThe paper presents results on learning for a class U of perturbation types and a hypothesis class H.  It defines a partial order on perturbation types in U, defined with respect to H.  It considers variants of the learning model where the learner can abstain from predicting the label of a given example (which is counted as a misclassification error unless the example has been perturbed).  It also considers a variant of the learning model where the learner can has query access to a \"perfect attack oracle,\" a type of oracle studied in previous work on learning with unknown perturbation sets.  \n\nThe results in the paper are all with regard to sample size.  (Computational complexity is not considered.). The first two main results are as follows.  (1) When the class U is totally ordered with respect to H, and H has finite VC dimension, then learning in the realizable case is possible with a polynomial-sized sample (treating VC-dimension as a constant). (2) For the unrealizable case, when U is totally ordered wrt H, a polynomial-sized sample also suffices if the learner can also make polynomially many calls to a perfect attack oracle.  \n\nThe next result considers a similar situation to that in (1) above, except in a more general setting where where U is a union of totally ordered subclasses.  In this setting, even with finite VC dimension and realizability, learning from (finitely many) examples is not possible, but can be achieved with a combination of a polynomial-sized sample and the ability to make polynomially many calls to a perfect attack oracle.  \n\nThe remaining results are concerned with learning with abstentions.  The main results are (1) Learnability in the realizable case, with abstentions, when U is totally ordered and H has finite VC dimension (2) Learnability in the realizable case, with abstentions, when U is the class of all perturbation, when the class has finite VC dimension and finite disagreement coefficient.  A result is also given on learning with abstentions in the realizable case if there is a successful finite-disagreement-cover learner for (H,U).\n\nThe paper also contains simple negative results demonstrating the need for abstentions, total order, etc.", "questions": "No specific questions.  It would be helpful to the reader to justify Definition 1, relating it to the possible behavior of an adversary.", "limitations": "I have no concerns in this area.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "A comprehensive exploration of uncertain perturbation sets, bridging work on unknown perturbation sets on the one hand, and a single known perturbation set on the other hand.  The paper is well-written.\n\nDiscussion phase:  I raised my score from 5 to 6.", "weaknesses": "From the presentation in the main paper, it does not seem that the paper introduces new techniques or that the presented results are surprising.  It seems as if the techniques have already been used in previous work on perturbations and that the results are similar.  Overall, the work seems like a solid contribution, but lacking in real novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It would be helpful to the reader to justify Definition 1, relating it to the possible behavior of an adversary.\n\nThanks for the feedback. We will add a justification in the final version. The intuition is that one way to handle adversarial attacks is to detect when an attack has happened and then abstain from making a prediction. The loss in Definition 1 allows the model to abstain when an attack has happened without penalty, but penalizes it if it makes a wrong prediction, thus incentivizing exactly the behavior described above.\n"}, {"review_id": "YMIoPSyRBw", "reviewer": "Reviewer_2e2f", "summary": "This paper studies robust classification when the perturbation region an adversary can access is unknown to the learner, but where it is guaranteed it comes from a certain class of perturbations, which is known to the learner. The authors show various results when the learner has access to a perfect attack oracle (PAO) (which either returns a robust loss of 0, or an admissible perturbation on which the hypothesis is not robust). \n\nFor perturbation classes with total order, without access to the PAO, finite VC dimension is sufficient in the realizable setting, but not in the agnostic one. With access to the PAO, this becomes possible, by a reduction from agnostic to realizable robust learning. \n\nWhen the perturbation class is a finite union of totally ordered perturbations, robust learning is also possible with the PAO (but in general, not without it). Removing structure on the perturbation class renders robust learning impossible (even with PAO). \n\nThe authors then consider robust learning with abstentions, where the learner cannot abstain on an unperturbed point, but can on a perturbed instance. They show that, in this set up,  robust learning is possible. They then relate robust learnability with the disagreement coefficient of a hypothesis class. ", "questions": "- Proof of theorem 2: the quantity $n$ is not defined. Do you mean $n=2^m$, the set of all potential subsamples of $S$ ?\n\nComment: \n- It would be worth adding on lines 124-125 and in the statement of Theorem 4 that the result holds for learning with abstentions.\n\nTypos/etc:\n- l.239 \"implicite\"\n- \"can not\" vs \"cannot\" (multiple times throughout the text): e.g., \"it can not be evaluated\" means \"it is possible that it is not evaluated\", while \"it cannot be evaluated\" means \"it is impossible to evaluate it\" - quite different semantics!", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Important question, nice set up that lies between unknown perturbation sets and models where the perturbation function is known a priori \n- The results are interesting and draw on multiples different concepts (learning with abstentions, disagreement coefficients, previous robust learning results, etc.)\n- The paper is clear and well-written\n- Meets the technical standards of NeurIPS", "weaknesses": "- No conclusion section - please add one for the final version!\n- MRERM: it seems to be quite a strong assumption to have access to this oracle? Especially since it returns the perturbation $u^*$! The existence of $u^*$ is fine, but that an algorithm can find it for any/most $\\mathcal{H}$ seems quite strong. Could you expand on this, and give examples? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the suggestions! We will add a conclusion section and discuss current limitations, open questions and future directions in the final version. We will also fix the typos and other edits suggested (the comment about “can not” vs “cannot” was particularly interesting, and we had not thought about it before!). Thank you! \n\nRegarding MRERM: \nSee the main comment addressed to all reviewers.\n\nRegarding the proof of Theorem 2: $n$ is simply the number of subsamples that are realizable with respect to some $u\\in\\mathcal{U}$. Thus $n\\leq 2^m$.\n"}, {"review_id": "Oe09ITvFNd", "reviewer": "Reviewer_uGK4", "summary": "- This paper bridges the gap of PAC learning theory for adversarially robust learning between completely known and completely unknown perturbation across various settings.\n- The authors introduce a notion of hypothesis class-induced partial ordering on the class of perturbation type which they use throughout the paper (setting 1).\n- They show that in a realizable setting, hypothesis class with finite VC dimension and setting 1 are robustly learnable. They show that the same is not valid for agnostic setting without extra assumptions such as access to perfect attack oracle.\n- They further show the existence of perturbation type and hypothesis class which cannot be robustly learned without abstention even with access to perfect attack oracle.\n- They also investigate hypothesis classes with finite disagreement coefficients and present results for this setting.\n- The define an $(\\epsilon, \\mathcal{H})$ cover for a class of perturbation types and use this definition to provide a generalization of their previous results.", "questions": "Are there any perturbation models (other than norm balls) which satisfy the setting of this paper?", "limitations": "The authors have addressed the limitations adequately. In that, this paper doesn't propose any (efficient) optimization algorithms, it rather presents sample complexity guarantees with Oracle access to the solution of the optimization problems.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written for the most part and provides a good explanation for the results. Furthermore, the claims seem mathematically sound and the authors have made good use of statistical learning theory to present their results. The results are interesting and close the gap between two known settings. They have also introduced some new notions such as the partial ordering of perturbation types with respect to hypothesis class and  $(\\epsilon, \\mathcal{H})$ cover for a class of perturbation types which are interesting concepts.", "weaknesses": "I liked the results and the general writing style of the paper. At times, the novelty seems to be a derivative of existing works with proofs being a clever extension of the proofs of existing settings. I believe this is bound to happen as the problem setting itself is an intermediary between two known settings. \n\nThe following is not a criticism but a remark - It would have been better to include some more mathematical proofs in a theoretical paper like this. However, I understand that space limitations sometimes prohibit this.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding other kinds of perturbation models: \n\nFirst, we should point out that “metric balls of given radius” already encodes many kinds of perturbation models we may want to use in practice. For example, consider perturbations only on a limited subset of features. Considering feature specific radii yield totally ordered classes, and considering differing collections of feature subsets yield finite unions of totally ordered perturbation type classes.\n\nFurthermore, note that our definition also allows one to define perturbation models where perturbations of different sizes are allowed at different data points. All we need is that if $u_i < u_j$, then $u_i(x)$ has a smaller radius than $u_j(x)$ for all $x$. This is more general than most models considered in the literature.\n\nIf we want to go beyond metric balls, that can also be done, for example, by starting with any arbitrary shape and “expanding” it gradually. "}, {"review_id": "MsGFv8GHe2", "reviewer": "Reviewer_wkxJ", "summary": "The paper studies adversarially robust learning with uncertain perturbation sets, where the set of points to which an adversary can perturb any test input is random, in contrast to previously studied settings of fixed known or unknown perturbation sets and unknown perturbation sets. The perturbation set is assumed to be coming from some fixed perturbation class.\n\nGiven a perfect attack oracle which certifies robustness or gives a successful attack, learnability is shown for concept classes with finite VC dimension with finite bounds on sample complexity and query complexity to the oracle, with some assumptions on U which are satisfied by commonly studied perturbation classes e.g. finite union of totally ordered perturbation sets which includes $L_p$ balls for a finite collection of $p$ values. \n\nWhen the classifier is equipped with abstention, learnability is possible under weaker assumptions e.g. finite disagreement coefficient of H wrt the data distribution. The authors further propose new notion of finite disagreement cover that depends on the perturbation class U, and reduce robust learning under abstentions to successful learning of a finite disagreement cover in the sense of their proposed notion.", "questions": "Questions:\n- Are there any practical examples or approximations of the oracle considered?\n- What is the sample complexity in Theorem 4?\n- Are the results applicable when the adversary uses a perturbation set outside of U?\n\nSuggestions:\n- It is not clear initially (e.g. lines 42-48) that the realizability being talked about is wrt U and not H. \n- Typos: lines 113, 358, 364.\n- Consider stating positive results in the agnostic case when learning with abstention in the main body (lines 408-413).", "limitations": "I do not anticipate potential negative impacts as the work is primarily theoretical, but encourage the authors to summarize limitations and further questions in a conclusion section e.g. lack of positive results in the agnostic case, tightness of sample complexity bounds, etc.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The work considers removing a common and unrealistic restriction in prior theoretical work that the adversary uses a fixed perturbation set.\n- The authors give examples demonstrating power of abstention and the difficulty of agnostic learning under their definitions.\n- Proofs or proof sketches of several major results are included and discussed.\n- Comparison to prior works and techniques e.g. Montasser et al. 2021 helps clarify the novelty and technical contributions of the present work.", "weaknesses": "- Realizability: Realizability of perturbation set seems like a strong assumption on the adversary and should be discussed. No positive results are given in the main body in the agnostic case, which could be a limitation of the model under study.\n- Some results are not adequately discussed, e.g. Theorem 5 and last paragraph on Pg 9.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> What is the sample complexity in Theorem 4?\n\nThanks for pointing out the missing bound! We will fix this in the final version. Currently, it’s in the proof in the supplementary material.\n\nThe bound is $O(\\frac{d\\cdot 2^d k^2 \\log (k/\\delta)}{\\epsilon})$, i.e., we get a quadratic dependence on $k$ in addition to the bound from Theorem 1.\n\n> Are the results applicable when the adversary uses a perturbation set outside of U?\n\nIf we know nothing about the perturbation type used by the adversary, then this is equivalent to assuming U to be the set of all perturbation types (except for agnostic learning with respect to U which we address below). Thus the known results for  “unknown perturbation sets” (which we reference, line 460) apply.\n\n> Some results are not adequately discussed, e.g. Theorem 5 and last paragraph on Pg 9.\n\nWe will add a discussion to Theorem 5. Basically this is an instance where we show that abstention learning can specifically help overcome the difficulties of robustness even if there is no prior knowledge on the perturbation sets. This is for particular classes for which abstention learning is easy, i.e. disagreement coefficient is finite. We will also make sure to clean up the last paragraph and add a proper conclusion section to the whole paper instead. \n\n\nRegarding the realizability assumption:\n\nWe agree that assuming that $\\exists u^*\\in\\mathcal{U}$ and $h^*\\in\\mathcal{H}$ such that $\\mathcal{L}^{u^*}_P(h^*) = 0$ is a strong assumption. However, as we show in Observation 1, not making any assumptions at all on $u^*$ makes the problem unsolvable (unless we have access to a perfect attack oracle). We further show in Theorem 2 that given access to a PAO, learning is possible in the agnostic case if we have a total order in $\\mathcal{U}$. We also have a discussion in the supplementary material on agnostic learning with access to a PAO when $\\mathcal{U}$ is a union of a finite number of total orders. \n\nIn light of Observation 1, it is an interesting question to define a reasonable model of agnostic learning (agnostic also with respect to the perturbation class U) when we are neither given access to a PAO, nor allowed to abstain. We potentially have two ways to relax the realizability assumption. We can either relax the assumption that $u^*\\in\\mathcal{U}$ or that $h^*\\in\\mathcal{H}$. We study the latter in our present work, but it would be interesting to find an appropriate way of studying the former. We leave that for future work.\n"}]

Author rebuttal:
We thank all reviewers for their positive reviews and appreciation of our work! 

Two common themes that appeared in the reviews are addressed here, while more specific points have been addressed as replies to individual reviews.

Regarding the MRERM oracle:

Investigating when an MRERM oracle actually exists in practice is indeed interesting and it is on our todo list for future work. For some simple scenarios, such as, when $\mathcal{H}$ is halfspaces, and $\mathcal{U}$ is L2-balls, it is a simple convex optimization problem. In general, we could consider encoding the radius of the true $u\in\mathcal{U}$ using k bits. In this case, if we have access to RERM, then we can solve MRERM using a binary search over the radii, thus requiring $O(k)$ queries to the RERM oracle. In addition to exact MRERM oracles, it will also be interesting to investigate to what degree our learning techniques are robust to approximate versions of MRERM.

Regarding technical contributions:

The issue of not knowing the true perturbation radius has been a concern in the adversarially robust learning literature. Picking the wrong radius for adversarial training can lead to reduced accuracy, and thus it is important that we use the correct radius. Our work presents methods where there is no need to guess the radius. We show that it is possible to automatically optimize for the unknown, correct radius in much more general settings that such results had been known for before.
We agree that our proof techniques build up on previously known techniques. However, we find the fact that an algorithm like the above exists to be quite interesting. Since in many practical settings, the uncertainty is over a set of perturbation types that’s totally ordered, our algorithm covers many scenarios of interest. We are also first to prove that abstentions can be used to address the challenge of unknown perturbation sets.


Meta-review: The reviewers agreed that this work is a solid contribution to robust learning theory.
Decision: Accept (poster)