Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization
Authors: Omar Montasser
Steve Hanneke
Nathan Srebro
Venue: NeurIPS 2022 Accept (2022)
Keywords: adversarially robust PAC learning
sample complexity

Abstract: We present a minimax optimal learner for the problem of learning predictors robust to adversarial examples at test-time. Interestingly, we find that this requires new algorithmic ideas and approaches to adversarially robust learning. In particular, we show, in a strong negative sense, the suboptimality of the robust learner proposed by Montasser, Hanneke, and Srebro [2019] and a broader family of learners we identify as local learners. Our results are enabled by adopting a global perspective, specifically, through a key technical contribution: the  the global one-inclusion graph, which may be of independent interest, that generalizes the classical one-inclusion graph due to Haussler, Littlestone, and Warmuth [1994]. Finally, as a byproduct, we identify a dimension characterizing qualitatively and quantitatively what classes of predictors $\mathcal{H}$ are robustly learnable. This resolves an open problem due to Montasser et al. [2019], and closes a (potentially) infinite gap between the established upper and lower bounds on the sample complexity of adversarially robust learning. 

Adversarially Robust Learning: A Generic Minimax
Optimal Learner and Characterization
Omar Montasser TTI-Chicago omar@ttic.edu
Steve Hanneke Purdue University steve. hawneke@gmiil.com
Nathan Srebro TTI-Chicago nati@ttic.edi
Abstract
We present minimax optimal learner for the problem of learning predictors robust to adversarial examples at test-time. Interestingly, we find that this requires new algorithmic ideas and approaches to adversarially robust learning. In particular, we show, in a strong negative sense, the suboptimality the robust learner proposed by [21] and broader family of learners identify as local learners. Our results are enabled by adopting a global perspective, specifically, through a key techni- cal contribution: the global one-inclusion graph, which may be of independent interest, that generalizes the classical one-inclusion graph due to [17]. Finally, as a byproduct, identify dimension characterizing qualitatively and quantitatively what classes of predictors H are robustly learnable. This resolves an open problem due to [21], and closes a (potentially) infinite gap between the established upper and lower bounds on the sample complexity of adversarially robust learning.
Introduction
We study the problem of learning predictors that are robust to adversarial examples at test-time. Adversarial examples can be thought of as carefully crafted input perturbations that cause predictors to misclassify. Learning predictors robust to adversarial examples a major contemporary challenge in machine learning. There has been significant interest lately in how deep learning predictors not robust to adversarial examples [30, 5, e.g. to adversarial perturbations of bounded f, -ormssss- leading to ongoing effort devise methods for learning predictors that adversarially robust.
The aim this paper is to put forward a theory precisely characterizing the complexity of robust learnability. We know from prior work that finite VC dimension is sufficient for robust learnability, but we also know that its finiteness not necessury [21]. Furthermore, there (potentially) infinite gap between the established quantitative upper and lower bounds the sample complexity of adversarially robust learning [21], and we do not know of any optimal learners for this problem. In this paper, address the following fundamental questions:
What classes of predictors H are robustly learnable with respect to an arbitrary perturbation set? Can we design generic optimal learners for adversarially robust learning?
The problem of characterizing learnability is the most basic question of statistical learning theory. In classical (non-robust) supervised learning, the fundamental theorem of statistical learning [32, 33, 6, 13] provides complete understanding of what is learnable: classes H. with finite VC dimension. and how to learn: by the generic learner empirical risk minimization (ERM₂). We also know that ERM is near-optimal learner for H with sample complexity that is quantified tightly by the VC dimension of H.
Problem setup. Given an instance space X' and label space y {+1), consider robustly learning an arbitrary hypothesis class H s y with respect to an arbitrary perturbation set 24
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

X' +222 2*, where U() S X' represents the set of perturbations that can be chosen by an adversary at test-time, as measured by the robust risk:
sup 1 [(((z) * y} =El(())
(I)
(0.M)
We denote by RE(H,U) 2) the set of distributions D over X' x y that are robustly realizable: 31" E
H. (D) 0. A learner A (X x )))= - y receives i.idd. examples S = { yi )== drawn from some unknown distribution
E RF((H, I,), and outputs a predictor ASS). The worst- case expected robust risk of learner A with respect H and U is defined as:
En (A; H,U)-
E DERE(HL)) SwDD
sup
(AS):
The minimax expected robust risk of learning H with respect to U is defined as:
(,H,, = inf (A; H.L)).
(3)
A
For any e (0, 1). the sample complexity of realizable robust e-PAC learning of H with respect U, denoted M (H, is defined as
min {n E [ & & S Se).
(4)
H is robustly PAC learnable realizably with respect to 2/ if Vee Mg. (H,U) is finite.
Related work and gaps. [21] showed that any class H. with finite VC dimension is robustly PAC
learnable with respect to any perturbation set Ut by establishing that. M (H, I Ö ((2))())) ) where ve(H)) denotes the VC dimension of H. While this gives a sufficient condition for robust learnability, they also showed that finite VC dimension is not necessary for robust learnability, indicating (potentially) infinite gap between the established upper and lower bounds on the sample complexity. We next provide simple motivating examples that highlight these gaps in this existing theory, and suggest that the learner witnessing this upper bound might be very sub-optimal:
Example 1. Consider an infinite domain X, the hypothesis class all possible predictors H. = y and an all-powerful perturbation (et X. In this case, the hypothesis minimizing the population robust risk (h; D) would always be the all-positive or the all-negative hypothesis, and so these the only two hypotheses we should compete with. And so, example suffices to inform the learner of whether to produce the all aol-positive or all-negative function.
though ve(H) oc, a single
Example 2. A less extreme and more natural example is to take X' R (an infinite dimensional space), and H the set of homogeneous halfspaces in X, and perturbation set (xx)) = {2 X (r, v) = (z, u) for v E V} where V is the set of the first standard basis vectors. In this example, an adversary is allowed to arbitrarily corrupt all but features. Note that ve(H) ao but we can robustly PAC learn H with (d) samples: simply project samples from X' onto the subspace spanned by V and learn d-dimensional halfspace.
Our contributions. In fact, even more strongly, we show in Theorem 1 that there are problem instances (H,2)) that are not robustly learnable by the learner proposed by [21], but are robustly learnable with a different generic learner. Beyond this, Theorem I actually illustrates, in strong negative sense, the suboptimality of any local learner a family of learners that we identify this work - which informally only has access to labeled training examples and perturbations of the training examples, but otherwise does not know the perturbation set 24 (defined formally in Definition 1).
In this work, we adopt global perspective on robust learning. In Section 3, we introduce novel graph construction, the global one-inclusion graph, that essence embodies the complexity of robust learnability. In Theorem 3, for any class H. and perturbation set W4 we utilize the global one-inclusion graph to construct a generic minimax optimal learner Gu,u satisfying 62n-1GGuLe H, < 4 E,, (H, Lf). Our global one-inclusion graph utilizes the structure of the class H. and the perturbation set lA in a global manner by considering all datasets of size n that are robustly realizable, where each dataset corresponds to a vertex in the graph. Edges in the graph correspond to pairs of datasets that agree on n datapoints, disagree on the th label, and overlap on the th datapoint according to their U sets. We arrive at optimal learner by orienting the edges of this graph to minimize notion

---

of cettariial-ut-degree that corresponds to the average leave-one-our robust error. Our learner avoids the lower bound in Theorem since is non-local and utilizes the structure of Ui at test-time.
In Section 5, we introduce a new complexity measure denoted Du (H) (defined in Equation 12) based on our global one-inclusion graph. We show in Theorem 5 that De((H) qualitatively characterizes robust learnability: a class H. is robustly learnable with respect to U if and only if Du (H) is finite. In Theorem 6, we show that Du (H) tightly quantifies the sample complexity of robust learnability: 2 (,(H)) ) < (H, S Ō ( This closes the (potentially) infinite gap previously established [21].
In Section 6, beyond the realizable setting, we show in Theorem that our complexity measure (H) bounds the sample complexity of agnostic robust learning: MM < Ō ( ). This shows that Du (H) tightly (up to log factors) characterizes the sample complexity of agnostic robust learning, since by definition, .M (H, 2 (H,
2 Local learners are suboptimal
In this section, we identify broad family of learners, which we term local learners, and show that such learners are suboptimal for adversarially robust learning. Informally, local learners only have access to labeled training examples and perturbations of the training examples, but otherwise do not know the perturbation set U. More formally.
Definition (Local Learners). For any class H. a local learner Ar (X y x 2** y for H takes as input a sequence Su {(11, (x;)) i=1 E X' x y x 2 consisting of labeled training examples and their corresponding perturbations according to some perturbation set U, and outputs predictor f E y In other words, A has full knowledge of H. but only local knowledge of U through the training examples.
We note that the robust learner proposed by [21], for example, is local learner: for given class H and input Sty {<x,, yr, (x;)) their learner outputs a majority-vote over predictors in H. that are carefully chosen based on the input Sz. Moreover, adversarial training methods in practice (e.g., 20, 35] are also examples of local learners (they only utilize the perturbations on the training examples). We provably show next that local learners are not optimal. We give construction where it is not possible to robustly learn without taking advantage of the information about Ut at test-time. Theorem 1. There is instance space X' and class H. such that for any local learner Av (X x y x )² + yd and any sample size m E N, there exists a perlurbation set U for which:
1. Au fails to robustly learn H with respect to U using samples.
2. There exists non-local learner Guu (X x y y which robustly learns H. with respect to U with samples.
This negative result highlights that there are limitations to what can be achieved with local learners. also highlights the importance of utilizing the structure of the perturbation set V at test-time, which has been observed in the context of transductive robust learning where the learner receives a training set of n labeled examples and test set of n unlabeled adversarial perturbations, and is asked to label the test set with few errors [23]. In practice, randomized smoothing [8] is example of non-local method in the sense that at prediction time, uses the perturbation set to compute predictions.
Proof of Theorem 1. We begin with describing the instance space X' and the class H. Pick three infinite unique sequences (x meN, (Ix )ee, and (Zn)neN from I2? such that for each n E N x = (n, 1), In (n, -1), 2n (n, 0), and let X' UnEN { 2, }. Consider the class H defined by
H H= -hy :y::g y ( where (zx) Yn hy +1 hx,,)) -1 -vn E N). (5)
Observe that all classifiers in H. are constant on (x JaeN and (I,))eet )NEN, but they shatter (Zx)NEN. We will consider a random perturbation set X' + 2 that is deñindd as follows:
1 Vn E N: [u(zt) { 2nd and (xx,)) = {. and U(2.) {xx 2, 2n w.p.
2
(6)
(u(xt) { and (x;,)) {., 2n and (z,,) { 2 2n w.p. 2.
3

---

For any sample size m E N. let P be uniform distribution on
[at (2 -.),...,
(I3m : +1), (33m 1)}
Observe that for any randomized (according to Equation 6), the distribution P is robustly realizable with respect to U: 3h E H. (h; P) = 0. Let A. be an arbitrary local learner (see Definition 1), i.e., A has full knowledge of the class H. but only partial knowledge of l through the training samples. Let S ~ pm be fixed random set of training examples drawn from P. Then,
E Ru (A(() P)
E
E (r.y)~
1 U(x) (z) + vl
2 Pr
(1 & S
E
[1: E ((()) (sSu) + v))( $ SS]
(a.)~~
(m.y)~
Pr (1 & S]
E
Pr
B2 E ((x) (z) + , & s]
(x.y)~
(z.D)~
111 1
3 6'
By law of total expectation, this implies that there exists a deterministic choice of U such that
Pm (A P) 2 This establishes that fails to robustly learn H with respect using
m samples.
On the other hand, H. is robustly learnable with respect to ll with 0 samples by means of our non-local learner Gz2u (see Section 4 and Theorem 3) which utilizes full knowledge of U. In particular, 0 samples are needed, since the graph GK will contain no edges by the definition of H (Equation 5) and UI (Equation 6).
3 A global one-inclusion graph
To go beyond the limitations of local learners from Section 2, in this section, we introduce: the global one-inclusion graph, the main mathematical object which allows us to adopt a global perspective on robust learning. Our global one- mecinclusion graph is inspired by the classical one-inclusion graph introduced by [17], which leads to an algorithm that is near-optimal for (non-robust) PAC learning. and has also been adapted and used in multi-class learning [26, 11, 7] and for learning partial concept classes! [2]. Before introducing our global one-inclusion graph, to ease the readers, we begin first with describing the construction of the classical one-inclue one-inclusion graph due to [17] and its use as
(non-robust) learner, and discuss its limitations for adversarially robust learning.
3.1 Background: classical one-inclusion graphs
For a given class H. and a finite dataset X = {o1,.... Lnn C X, the classical one-inclusion graph Gx,H consists of vertices V = ((h(z)).-- h(xa)) h E H) where each vertex v (h(2)),...,, M(x,)) E V is a realizable labeling of X, and two vertices u, v E V are connected with an edge if and only if they differ only in the labeling of single 2; E X. [17] showed that the edges in Gx.H can be oriented such that each vertex has out-degree at most ve(H), Now, how can the one-inclusion graph be used a learner? Given a training set of examples S= [11, B1)....
9an-)) and a test example In, we construct the one- one-inclusion graph on {#I..... _n-11 U fa,,) } using the class H and orient it such that maximum out-degree at most ve(H). Then, we use the orientation to predict the label of the test point Iy.- Specifically, if there exists h, Ni' H such that A1 < i n 1: h(x;) = h'(x,) and h(T,,) + h ((,,,, then we will have two vertices in the graph = (h(z1)..... h( 1), l(()..)) and u = (h(x1)..... h(Tn-1). h (x()))) with an edge connecting them (because they differ only in the label of xx)), and we predict the label of v., that this edge is directed towards. Since each vertex has out-degree at most vc vc(H), this implies that the average seuve-one-uuterroe (which bounds the expected risk from above) is at most ve(R)
At a first glance, it might seem that adversarially robust learning can be viewed as special case of learning partial concepts classes [2]. but we would like remark that this is not the case. The apparent similarity arises because it possible state the robust realizability assumption in the language of partial concept classes, as in the example mentioned [2] on leamingg linear separators with a margin, but this is just an assumption on the data-distribution. Specifically, a partial concept class learner is only guaranteedd to make few errors on samples drawn from the distribution (see Definition 2 in 2]. and not on their adversarial perturbations: i.e., performance is still measured under 0-1 loss, not robust risk.
4

---

What breaks in the adversarial learning setting? At test-time, we do not observe an i..d. test example D but rather only an adversarially chosen perturbation (x)). This completely breaks the exchangeability analysis of the classical one-inclusion graph, because the training points are i.i.d. but the perturbation of the test point the sense that it depends on the training data and the test point, and as such different perturbations 2, 2 E (())) could very well lead to different graphs, different orientations, and ultimately different predictions for z and 2 which by definition imply that the prediction is not robust on
not. Furthermore, the classical one-inclusion graph is local in
3.2 Our global one-inclusion graph
We now describe the construction of the global one-inclusion graph. For any class H. any perturbation set U1 and any dataset size E N, denote by G = (Vn. F.,) the global one-inclusion graph. In words, V, is the collection of all datasets of size n that can be robustly labeled by class H with respect to perturbation set U. Formally, each vertex E Vn is represented as a multiser of labeled examples (x, y) of size n.
Vn (((11,))), ... (2in; Un)) (3h E H) (Vi [n]) (Vz E ((())) y;)-
Two vertices (datasets) u, E Vn are connected by an edge if and only if there is unique labeled example (z, y) E that does not appear does not appear in satisfying: y F ÿ and (z) (U()) o D. Formally, u, E V, are connected by an edge and only their symmetric difference uAv = {(2, v), (), where + 1 and U(x) (+) o 0. Furthermore, we will additionally label edges by the perturbation E U(x) that witnesses this edge:
and there a unique labeled example (Ø, E u that
F,, ((1u, w) =): u, U, Anr ((x, (2, 5)) A # A =
For each vertex E Vn, denote by advdeg(v) the adversarial degree of which is defined as the number elements (2r; 3) E o that witness an edge incident on u:
advdeg(u) (( e Au Vn, E X s.t. (fr,
( =Aun]l- (9)
We want to emphasize that our notion of adversarial degree is different from the standard notion of degree used in graph theory, and in particular different from the degree notion in the classical one-inclusion graph used above. Specifically, we do not count all edges incident on vertex rather we count the number of datapoints (æ., y) in a vertex that witness an edge. This different notion of degree is more suitable for our purposes and is related to the average leave-one-out robust error.
3.3 From orientations to learners
An orientation O E., Vn of the global one-inclusion graph G4 (V,, En) is mapping that directs each edge = (fu, w} 2) E En towards a vertex O(e) E {u, Given orientation O E,, Vn of the global mncinnlusoon graph GM the adversarial out-degree of vertex V. denoted by adv-outdeg(r; O). is defined as the number of elements (I. E that witness an out-going edge incident on v according to orientation O:
Bu Vn, E s.t. (fv, 22.2) E, (I,z) vAu O(fee, 2))
}1. (10)
adv-outdeg(1; O) (1, e
Why are interested in orientations of the global one-inclusion graph G We show next that every orientation of Gy,, be used construct learner, and that the expected robust risk of this learner bounded from above by the maximum adversarial out-degree of the corresponding orientation. We will use this observation later in Section construct an optimal learner.
Lemma 2. For any class H. any perturbation set U, and any L, let G (Vns be the global one-inclusion graph. Then, for any orientation O: En + Vn of G2, there exists a learner Ao (X x y)n-1 + )²x such that
maX.ev, adv-outdeg(v; O)
(Ao0 H,2) <
n
Note that we allow a labeled example (x. y) to appear more than once in a vertex v. hence the multiset representation.
5

---

The proof is deferred to Appendix A. At high-level, we can use an orientation O of G% to make predictions in the following way: upon receiving training examples S and a (possibly adversarial) test instance 2, we consider all possible natural datapoints (I, y) of which is perturbation of x (i.e., 2 E (x)) such that U { (zz y)} can be labeled robustly using class H with respect to l (note that these are all vertices in G% by definition), and if two different robust labelings of are possible, the orientation O determines which label to predict. This is defined explicitly in Algorithm
Algorithm 1: Converting an Orientation O of G Learner Ao.
Input: Training dataset = ((11.11). (Ix-1. (Ix-1. 1) E (X x Vin-1, test instance z E X. and an orientation O En - V,, of C/ (En, Vn).
1 Let P+ = f2r E Vn= E E s.t. 2 ((()) A A== { 31
1n-11,0n-1) (z, +1]]
2 Let P_ = (v E Vn= : Ex E 2 E (1)))) Ar= ((.,,))) )...,))..... 1In- Un-1), (I. - -1]]]. 10n-1,9n-11
3 If (2y)()1)) (3vep,) (VuEP-.) (((u, =)) = =U, then output label y.
4 Otherwise, output +1.
4 A generic minimax optimal learner
We now present an optimal robust learner based on our global one-inclusion graph from Section 3.
For any class H. any perturbation set Ut and integer 1, let G (Vn, be the global one-inclusion graph (Equations 7 and 8). Let O be an orientation that minimizes the maximum adversarial out-degree of G2/=
O" argmin max adv-outdeg(:; O).
(11)
O.E.-Va
VVV,
Then, let Gu, be the learner implied by orientation O as described in Algorithm 1.
Theorem 3. For any H. U. any n E N, learner Gha described above satisfies for any learner A: 6 H, < 4-E, (A; H,,,,, & equivalently M (G H, < 2-M (A; (A;
Before proceeding to the proof of Theorem 3, we first prove key Lemma which basically shows that we can use an arbitrary learner A to orient the edges in the global one-inclusion graph G4,, and that the maximum adversarial out-degree of the resultant orientation is upper bounded by the robust error rate of A.
Lemma (Lowerbound on Error Rate of Learners). Let A. (X 3/* - y be any learner, and E N. Let G4 = (Vzn, Fe2)) be the globul one-inclusion graph as defined in Equation 7 and Equation& 8. Then, there exists an orientation O₃ Ez, + V2n of G4, such that
(A; 1 max adv-outdeg(v; Oz)
Proof. We begin with describing the orientation O₂ by orienting edges incident on each vertex V E Vzn- Consider an arbitrary vertex v = ((11, y1 ........ (I2n, V2n)] and let P. be a uniform distribution over (I1, 31) (n),..... (Z2n, V2n). For each 1 < < 2m, let
Pc(v)= = Pr [a U(x;) (S) + vel( we) S].
S~PP
For each (Zt, ye) E that witnesses an edge, i.e. Eu E V2n, 2 E X' s.t. (fv, u) ,2) E Egn and (t) E Auu if Pt < 2. then orient all edges incident on (It, Ve) inward, otherwise orient them arbitrarily. Note that this might yield edges that are oriented outwards from both their endpoint vertices, in which case, we arbitrarily orient such edge. Observe also that we will not encounter a situation where edges are oriented inwards towards both their endpoints (which is an invalid orientation). This is because for any two vertices v, V2, such that Ezo E & where ((u, v) 20) E
Een and vλu {II yr), (ā., }.)). we cannot have (v( and (r( < 3. since
pv(v)= 2 Pr. (zo) # VI y0) $ S] and pe( Z Pr. (2)) # -ullee, -v)) $ S]. Sm

---

and P. conditioned on (z,, ve) & S is the same distribution as Pa conditioned on (ă₁, -y) & S. This concludes describing the orientation On. We now bound the adversarial out-degree of vertices E V
2n
2n
adv-outdeg(r;; 02) -
1
2 2
<
1=1
1=1
2n
= 2
Pr Smin
32 (a())) A())(z) # y (,, $S
Pr (3z ((()) ((5) w) (x1, Ue) & S) Pr [1re y1) SS
2
t=1
< 4
Pr Soupn
[(3z ((())) (z))(z) + 9b) (I2, vc) $
4
E
Σ
1 E (xx)) (=))(=) Am
Sm
(E
< 4
E S~ Pm
Σ
D EU(x)) A=))(=) + vdl 8n E Ru(A(S);P) S 8nE, (A; H,,1). Sppp
Since the above holds for any vertex E V2n, by rearranging terms, get (A; H,l4) 22 (dv-outdegge::..) 2n
AI D
We are now ready proceed with the proof of Theorem 3.
Proof of Theorem 3. By invoking Lemma 4, we have that for any learner A,
1 maX adv-outdeg(1; Ox)
(A: H,,4)
4
2n
By Equation 11, an orientation O has smaller maximum adversarial out-degree, thus max,cV2, adv-outdeg(rr O+)
max adv-outdeg( ey O*)
IV
2n
2n
By invoking Lemma 2, it follows that our optimal learner GH.u satisfies
max adv-outdeg(;; O*)
- (.,,HHH H.21
2n
We arrive at the theorem statement by chaining the above inequalities and rearranging terms.
complexity measure and sample complexity bounds
In Section showed how global one-inclusion graph yields near-optimal learner for adversarially robust learning. We now turn to characterizing adversarially robust learnability.
Across learning theory, many fundamental learning problems can be surprisingly characterized by means of combinatorial complexity measures. Such characterizations are often quantitatively insightful in that they provide tight bounds the number of examples needed for learning, and also insightful for algorithm design. For example, for standard (non-robust) learning, the VC dimension characterizes what classes H. are PAC learnable [32, 33, 6, 13]. For multi-class learning, there are characterizations based on the Natarjan and Graph dimensions, and the Daniely- Shalev-Shwae (DS) [24, 10, 7]. For learning real-valued functions, the fat-shattering dimension plays similar role [1, 18, 29]. The Littlestone dimension characterizes online learnability [19], and the star number characterizes the label complexity of active learning [16].
[28] showed that Vapnik's "General Learning" problem [31], the loss class having finite VC dimension is sufficient but not, in general, necessary for Icarnability and asked whether there is
7

---

another dimension that characterizes learnability in this setting. But recently, [4] surprisingly exhibited statistical learning problem that can not be characterized with combinatorial VC-like dimension. In order to do so, they presented a formal definition of the notion of "dimension" or "complexity measure" (see Definition 4), that all previously proposed dimensions in statistical learning theory comply with. This raises the following natural question:
Is there a dimension that characterizes robust learnability, and if so, what is it?!
5.1 A dimension characterizing robust learning
We present next dimension for adversarialty robust learnability, which is inspired by our global one-inclusion graph described in Section 3.
3 finite subgraph G = EV, of G = (Vn, E,, s.t.
(H) max n [
orientations of G, 3u V where adv-outdeg(e) o; 0) 2 1
(12)
In Appendix D, we discuss how our dimension satisfies the formal definition proposed by [4]. We now show that (H) characterizes robust learnability qualitatively and quantitatively.
Theorem 5 (Qualitative Characterization). For any class H and any perturbation set U, H is robustly PAC learnable with respect to U if and only (H()) is finite.
Theorem (Quantitative Characterization). For any class H and any perturbation set U,
Du Du(H) (H)
S M. (H, 50 ( (Du(H)
(H) log(1/6)
Ω2
log
S
Theorem follows immediately from Theorem 6. To prove Theorem 6, we first prove the following key Lemma which provides upper and lower bounds on the minimax expected robust risk of learning class H. with respect to a perturbation set U (see Equation 3) as a function of our introduced dimension Du(H), Theorem 6 follows from an argument to boost the robust risk and the confidence as appeared in [21]. The proofs are deferred to Appendix B.
Lemma 7. For any class H. any perturbation set U, and any e (0, 1).
1. vn > Du((H) En-1 E $
2. 42 nn Du(H) Eg 18 (H,U) 2 :
5.2 Examples
We discuss a few ways of estimating or calculating our proposed dimension (z))... Proposition 8. For any class and perturbation set U:
(u( & min (Ö(ve(H)) (vc())())((44))
where ve" (H) denotes the dual VC dimension, and vo vc(C4)) denotes the VC dimension of the supzeu(x) [[h(2 # v)l h }.
robust-loss class Ct1 =
Proof. Set 60 = 3. We know from Theorem that tre (H, 2 (H))) We also know from [Theorem 4 in 21] that MIe (H,U)= Ö(ve(H))ve* (Pt). Finally, we know from [Theorem I in 9] that Mr co 2f) < ((ve((C)) Combining these together yields that stated bound.
The dual VC dimension satisfies: ve* (H)
+11 [3], and this exponential dependence tight for some classes, For many natural classes, however, such as linear predictors and some neural networks [see Lemma 3.2 22], the primal and dual VC dimensions are equal, or least polynomially related. Using Proposition 8, we can conclude that for such classes Der (H) I (7))( specifically, for H. being linear predictors, (H) < Ō(ve² Furthermore, for H. being linear predictors
8

---

and U = l perturbations, we know that vo(C4) (vvc(H)) [Theorem& 2 in 91, and so using Proposition 8 again, we get a tighter bound for these ep perturbations Du (H) - (vve(H)).
While Proposition 8 is certainly useful for estimating our dimension Due (7), we get vacuous bounds when the VC dimension ve(H) is infinite. To this end, recall the (H.24) examples in Example 1 and Example mentioned in Section 1, which satisfy vc(H)) = co. We can calculate Di (H) for these examples differently. In particular, in Example 1, by definition, the global one-inclusion graph C (Va, Fn) has no edges when n > because ((x) = X and thus (H)(H) S 1. In Example 2, we get that (H) I (d) since we can robustly learn with (dd) samples, but we can also calculate (?() directly by constructing the global one-inclusion graph G% = (V,, E,) for 3d and observing that we can orient G such that the adversarial out-degree is most d, which is possible because of the defimition of U.
5.3 Conjectures
While we have shown that our proposed dimension Du (H) in Equation 12 characterizes robust learnability, we believe that there are other equivalent dimensions that are simpler to describe. For a more appealing dimension, we may take inspiration from recent progress on multi-class learning [7], where it was shown that the DS dimension due [11] characterizes multi-class learnability, For a class H. S y (D'1 > 2), the DS dimension corresponds to the largest n s.t. there exists points P = x where the projection of H. onto induces a one-inclusion hyper graph where every vertex has full-degree. This inspires the full-degree dimension of the global one-inclusion graph:
3 a finite subgraph G = (V, E) of G4 = (Vn, Fr)) s.t. every (H) max {" E NU vertex has full-degree: Vu E V, advdeg(1; F)) n.
nn
This complexity measure avoids orientations, and thus, it is perhaps simpler to verify "3Du (H) 2 d' than (H) 2 d". Furthermore, when U(z)) [[z = {x} Vx E X. the full-degree dimension, F0i corresponds exactly to the VC dimension of H. ve(H).
Conjecture 1. For any class H and perturbation set U, (H, =., (H)).
[21] proposed the following combinatorial robust shattering dimension, denoted dimz and showed that M (H, 2 R2.5 (d.s((iim
Definition 2 (Robust Shattering Dimension). A sequence 21, 2k is said to be U-robustly shattered by H if Ex 21 ..... #x - E s.t. Vi E [k], 2, E ( nux()) and Vyi..... Ub E {+1} 3h E H such that hu(=)) V/ E Uu"""" S k. The U-robust shattering dimension dima (H) is defined as the largest A: for which there exist l points l1-robustly shattered by H.
In regards to the relationship between the robust shattering dimension dimey (H) and our dimension (H), we conjecture that our dimension can be arbitrarily larger. In other words, we conjecture that the robust shattering dimension dimu (H) does not characterize robust learnability.
Conjecture 2. Vn E N, 3X, H.U, such that dimy (H) O(1) but (H)(H) 2
We find this to be analogous to separation in multi-class learnability, where the Natarajan dimension was shown to not characterize multi-class Icarnability [7]. Because in both graphs, the one- inclusioninn hyper graph and our global one-inclusion graph, the Natarajan and robust shattering dimensions rep- resent a "cube" in their corresponding graph, while the DS dimension and our full-degree dimension represent a "pseudo-cube" in the terminology of [7]. To elaborate, the robust shattering dimension (Definition 2) gives rise to a "cube" in our global one-inclusion graph, meaning it is a subgraph isomorphic to the Boolean cube {0, 1}" Specifically, any Zi,..., Zu that are robustly shattered (as in Definition 2) can be used to construct a finite subgraph where the vertices are {<=²'). )..",, (*H"* }} for y E 11] By our definition of degree, these vertices will have full-degree, since every vertex will have a neighbour (with only single label flipped). In contrast, the full full-degree dimension that we propose (see Conjecture above) gives any finite subgraph where every vertex has full-degree. including those not isomorphic to the Boolean cube. Following the terminology in multiclass learning. we call this "pseudo-cube", as it needn't 't be isomorphic to the Boolean cube.
Another interesting and perhaps useful direction to explore is the relationship between our proposed complexity measure (H) and the VC dimension. We believe that is actually possible to orient the global one-inclusion graph such that the maximum adversarial out-degree is at most (vv(H))). Conjecture 3. For any class H and perturbation set U, Du (H)) < Ovve(H)).

---

Agnostic robust learnability
For the agnostic setting, we consider robust learnability with respect to arbitrary distributions that are not necessarily robustly realizable, i.e., D & RE(H, U)) (see Definition 3 in Appendix C). We can establish an upper bound in the agnostic setting via reduction to the realizable case, following an argument from [12] and later applied to agnostic robust learning by [21]:
Theorem 9. For any class H and any perturbation set U,
(u(HH)
Du(HH)
log (1)
(H, -
log" 2
This is achieved by applying the agnostic-to-realizabee reduction the optimal learner GH that get from orienting the graph G% (V)u(H)+1: (D The reduction is stated abstractly in the following Lemma whose proof is provided in Appendix C.
Lemma 10. For any well-defined realizable learner A, there is an agnostic learner B such that
M H,U1 & M. H,,U) 0o
Mi
Mi/3(A;H,
log²
(Mija(As (M
1 E2
log ()))
E2
Theorem immediately follows by combining Lemma 10 and Theorem 6.
Acknowledgments and Disclosure of Funding
We thank Shay Moran for numerous enlightening discussions about structures arising in the analysis of muliclass learning, concurrent this work, which seem tantalizingly related those arising here. This work is supported in part by DARPA under cooperative agreement HR001 12020003 3, and in part by the NSF/Simons sponsored Collaboration on the Theoretical Foundations of Deep Learning ai).
bettps://deepforee
References
[1] N. Alon, Ben-David, Cesa-Bianchi, and Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. J. ACM, 44(4):615-631 1997. 5
[2] N. Alon, S. Hanneke, R. Holzman, and S. Moran. A theory of PAC learnability of partial concept classes. In 62nd IEEE Annual Symposium Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 658-671. IEEE, 2021. 3,
[3] Assouad. Densité et dimension. Annales de I'Institut Fourier (Grenoble), 33(3):233-282, 1983. 5.2
[4] S. Ben-David, P. Hrubes, S. Moran, A. Shpilka, and A. Yehudayoff. Learnability can be undecidable. Nat. Mach. Intell., 1(1):4448,,, 2019. 5.1,
[5] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šindié, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in dutabuses, pages 387-402. Springer, 2013. 1
[6] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik- Chervonenkis dimension. Journal of the Association for Computing Machinery, 3645)999-965. 1989. 1,
[7] N. Brukhim, D. Carmon, I. Dinur, Moran, and A. Yehudayoff. characterization of multiclass learnability. CoRR, abs/2203.01 .050000,,,5,, 2022. 3, 5, 5.3, 5.3
'The views expressed in this work do not necessarily reflect the position or the policy of the Government and official endorsement should be inferred. Approved for public release; distribution is unlimited.
10

---

[8] J. M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1310-1320. PMLR, 2019. 2
[9] D. Cullina, A. N. Bhagoji, and P. Mittal. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pages 228- 239, 2018. 5.2
[10] A. Daniely, S. Sabato, S. Ben- Ben-David, and S. Shalev-Shwarde Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16:2377-2404, 2015. 5
[11] A. Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. In M. Balcan, V. Feldman, and C. Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, volume 35 of JMLR Workshop and Conference Proceedings, pages 287-316. JMLR.org. 2014. 5.3
[12] O. David, S. Moran, and A. Yehudayoff. Supervised learning through the lens of compression. In Advances in Neural Information Processing Systems 29, pages
2016. 6, C
[13] A. Ehrenfeucht, D. Haussler, M. Kearns, and I.. Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247-2611 1989. 1,5 5
[14] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[15] T. Graepel, R. Herbrich, and J. Taylor. PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning, 59(1-2):55-76. 2005. C
[16] S. Hanneke and L. Yang. Minimax analysis of active learning. Journal of Machine Learning Research, 16 1612))3487-3602 2015.
[17] D. Haussler, N. Littlestoee, and M. K. Warmuth. Predicting I0functusss on randomly drawn points. Inf. Comput., 11822)248--922, 1994. (document), 3, 3.1
[18] M. J. Kearns and R. E. Schapire. Efficient distribution -frett learning of probabilistic concepts. J. Comput. Syst. Sci., 48(3):464 497, 1994.
[19] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Much. Learn., 2(4):285-318, 1987. 5
[20] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 2018, Conference Track Proceedings. OpenReview.net, 2018.
[21] O. Montasser, S. Hanneke, and N. Srebro. Ve classes are adversarially robustly learnable, but only improperly. In A. Beygelzimer and D. Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2512-2530, Phoenix, USA, 25-28 Jun 2019. PMLR. (document), 1, 1, 2, 5.1, 5.2, 5.3, 6. 13, C
[22] O. Montasser, S. Hanneke, and N. Srebro. Reducing adversarially robust learning to non- robust PAC learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. 5.2
[23] O. Montasser, S. Hanneke, and N. Srebro. Transductive robust learning guarantees. arXiv preprint a0.iv:2 10602, 2021. 2
[24] B. K. Natarajan. On learning sets and functions, Machine Learning, 4:67-97, 1989.

---

[25] R. Rado. Axiomatic treatment of rank in infinite sets. Canadian Journal of Mathematics, 1(4):337-343, 1949. 11
[26] B. P. Rubinstein, L. Bartlett, and H. Rubinstein. Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds. In B. Schölkopf. J. C. Platt, and T. Hofmann, editors, Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference Neural Information Processing Systems. Vancouver, British Columbia, Canada, December 4-7, 2006, pages 1193-1200. MIT Press, 2006. 3
[27] R. E. Schapire and Y. Freund. Boosting. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2012. B, C
[28] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan, Learnability, stability and uniform convergence. J. Mach. Learn. Res., 11:2635-2670, 2010. 5
[29] H. U. Simon. Bounds on the number of examples needed for learning functions. SIAM J.
Comput., 26(3)7551-73,, 1997. 5
[30] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013. I
[31] V. Vapnik. Estimation of Dependencies Based on Empirical Data. Springer- Verlag, New York, 1982. 5
[32] V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971. 1,
[33] V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974. 1,
[34] E. S. Wolk. A note on" the comparability graph of tree". Proceedings of the American Mathematical Society, 16(1):17-20, 1965.
[35] H. Zhang, Y. Yu, J. Jiao, E. P. Xing, L. E. Ghaoui, and M. I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1472-7482. PMLR, 2019. 2
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 ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(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 to 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 (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
12

---

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 URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'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 or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "eIe6v6CvXuG", "reviewer": "Reviewer_pb28", "summary": "The authors give the first combinatorial characterization of adversarially robust PAC-learning (test-time adversarial perturbation), resolving an open problem of Montasser, Hanneke, and Srebro (2019) and closing an infinite gap in sample complexity seen by previous methods. The authors also provide a universal near-optimal algorithm based on a robust variant of the classical one-inclusion graph approach. In particular, the authors define an infinite object called the global inclusion graph G_n(H) roughly defined as follows:\n\n$G_n(H)$ has vertex set given by all robustly realizable multisets of labeled examples $(x_1,y_1), \\ldots, (x_n,y_n)$, and two vertices $z=(x,y)$,$z'=(x',y')$ have an edge if |z \\Delta z'| =1, $y \\neq y'$, and $U(x) \\cap U(x')$ is nonempty (in fact an edge is defined for each element in this intersection). Given an orientation of edges in $G_n(H)$, the \"out-degree\" of a vertex $z=(x_1,y_1), \\ldots, (x_n,y_n)$ is given by the number of indices that witness an edge.\n\nThe authors main result is to show that if there is an orientation of edges in $G_n(H)$ with small out-degree, then there exists a good robust learner. Moreover, if any good robust learner implies the existence of an orientation with small out-degree.\n\nNote that this itself does not give a combinatorial characterization in the traditional sense (due to the global inclusion graph being infinite). To circumvent this issue, the authors introduce a finite variant still capturing the out-degree structure, and show that this parameter exactly characterizes robust learnability (up to log factors). Finally, it is worth noting that both the algorithm and dimension given are \"global\" in the sense that they must see the perturbation sets of elements outside their training set. The authors show this is in fact necessary, there exist robustly learnable classes that cannot be learned by any `local' algorithm that is restricted to information about its training set.\n\n", "questions": "I have no major questions, but a few minor comments:\n\n1. It might be less confusing to change the name of your notion of degree rather than abusing notation. \n\n2. DS-dimension should be mentioned at the beginning of section 5 re: characterizing multiclass learning\n\n3. typo: integere", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work resolves an important open problem in the study of adversarially robust learning, and provides very interesting insight on the power of local vs global robust algorithms. Many of the techniques build on known analysis of the one-inclusion graph and seem inspired by recent work on partial and multi-class learning, but the generalization to robust learning is certainly a non-trivial contribution. Overall, the paper is well-written and is likely to have high impact in the (theoretical) study of adversarially robust learning.\n\nThe main weakness of this work is that the proposed combinatorial dimension is quite complicated, lacking the simplicity of other combinatorial notions like VC-dimension (or even say DS-dimension) that often help lend these notions their broad impact across the field. That said, the authors do a very nice job discussing this issue and give a number of relevant conjectures in this direction. ", "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": "bTSmY4nogJl", "reviewer": "Reviewer_bV2J", "summary": "The following points summarize the paper:\n- The paper starts with showing that there are problem instances $(\\mathcal{H}, \\mathcal{U})$ which are not learnable by local lernears (with access to $\\mathcal{U}(\\cdot)$ on only training points). Using construction from later sections, they show that global learners can learn such problem instances.\n- They introduce a novel global one-inclusion graph construction which uses $\\mathcal{H}$ and $\\mathcal{U}$ in a global manner.\n- Using global one-inclusion graph, they also derive an optimal learner by orienting the edges of this graph to minimize a specific notion of out-degree.\n-  They also propose a new dimension $\\mathfrak{D}_\\mathcal{U}$ and show that a problem instance $(\\mathcal{H}, \\mathcal{U})$ is robustly PAC-learnable iff $\\mathfrak{D}_\\mathcal{U}$ is finite. In particular, they provide tight (upto logarithmic factor) lower and upper bound of sample complexity based on $\\mathfrak{D}_\\mathcal{U}$. This closes potentially infinite gap of [21].\n- They provide some ways to compute $\\mathfrak{D}_\\mathcal{U}$ and extend their results to agnostc case.  ", "questions": "Please see the previous section.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It is a strong theoretical paper with many novel theoretical contributions. The paper not only establishes that it is impossible for local learners to learn some of the problem instances robustly, it also provides a dimesnion measure to characterize robust learnability. The results are well presented and contrasted well with the existing results in the literature.\n\nI did not notice any weaknesses. I have only one question: how easy/difficult is it to estimate $\\mathfrak{D}_\\mathcal{U}$ for a general case? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XihQS_EmFq", "reviewer": "Reviewer_VT2M", "summary": "This paper studies the problem of learning predictors robust to adversarial examples presented at test-time. The main goal of the paper is to characterize adversarially robust learning for binary hypothesis classes and design an optimal learning algorithm for this task.\n\nThe main contributions of the paper are on three axes: first, it is proved that local learners (which were proposed in previous work) are not optimal; second, a novel global learner is provided, which is based on the well-known one-inclusion graph algorithm; this algorithm yields a generic minimax optimal learner for the problem of interest; third, based on the structure of this algorithm, a tight complexity measure is given by the authors. This quantity characterizes adversarially robust learnability in both the realizable and the agnostic settings. Finally, various conjectures are proposed for future work.", "questions": "I find the observation between the lines 307-311 very interesting. I would appreciate if the authors further comment on this point in greater detail. \n\n", "limitations": "The authors have extensively discussed future directions in order to extend their results.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well-written and clearly structured. The results are clear and very interesting. The structure of the one-inclusion algorithm has found various applications recently (such as the characterization of multiclass learnability and partial concept classes) and it is appealing that this is also the case in adversarially robust learning. The idea of the global one-inclusion graph algorithm is novel to the best of my knowledge and the intuition provided is clear. The only point that I do not find completely satisfying is the provided complexity measure, which is not as intuitive as other dimensions in the literature; however, I believe that the proposed dimension is the starting point of a research direction aiming at simplifying the characterization of  adversarially robust learnability.\n\nIn general, I believe that the paper is a strong contribution to the area of statistical learning theory.", "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