On Robust Multiclass Learnability
Authors: Jingyuan Xu
Weiwei Liu
Venue: NeurIPS 2022 Accept (2022)

Abstract: This work analyzes the robust learning problem in the multiclass setting. Under the framework of Probably Approximately Correct (PAC) learning, we first show that the graph dimension and the Natarajan dimension, which characterize the standard multiclass learnability, are no longer applicable in robust learning problem. We then generalize these notions to the robust learning setting, denoted as the adversarial graph dimension (AG-dimension) and the adversarial Natarajan dimension (AN-dimension). Upper and lower bounds of the sample complexity of robust multiclass learning are rigorously derived based on the AG-dimension and AN-dimension, respectively. Moreover, we calculate the AG-dimension and AN-dimension of the class of linear multiclass predictors, and show that the graph (Natarajan) dimension is of the same order as the AG(AN)-dimension. Finally, we prove that the AG-dimension and AN-dimension are not equivalent.

On Robust Multiclass Learnability
Jingyuan Xu
Weiwei Liu" School of Computer Science Wuhan University 1iuveiwei com
School of Computer Science Wuhan University j inngyaaxa7770@gmai.. com
Abstract
This work analyzes the robust learning problem in the multiclass setting. Under the framework of Probably Approximately Correct (PAC) learning, we first show that the graph dimension and the Natarajan dimension, which characterize the standard multiclass learnability, are no longer applicable in robust learning problem. We then generalize these notions to the robust learning setting, denoted the adversarial graph dimension (AG-dimension) and the adversarial Natarajan dimension (AN- dimension). Upper and lower bounds of the sample complexity of robust multiclass learning rigorously derived based the AG-dimension and AN-dimension, respectively. Moreover, we calculate the AG-dimension and AN-dimension of the class of linear multiclass predictors, and show that the graph (Natarajan) dimension is of the same order as the AG(AN)-dimension Finally, we prove that the AG- dimension and AN-dimension not equivalent.
Introduction
Learning models that are robust to adversarial perturbations has attracted significant research attention in recent years I 2 3). Notably, prior work on this subject has largely studied the theory of robust learnability in the context of binary supervised learning. However, many important problems require classification into great number of target classes. For example, in image object recognition and language models building
9], the number of classes scales as the number of possible objects or the dictionary size respectively. It is thus of both practical and theoretical interest to generalize the robust binary learning theory to the robust multiclass setting.
In the standard multiclass learning setting, the finiteness of the Natarajan dimension or graph dimension 10 (both of which are generalized from the VC-dimension (M]) is necessary and sufficient to ensure learnability [12]. Recent work has shown that the finiteness of the VC-dimension neither sufficient nor necessary for (proper) robust binary classification [3] Inspired by [33, this paper demonstrates that the hatarajan/graph dimension can no longer characterize robust learnability in the multiclass problem. Meanwhile, some questions naturally arise: In multiclass setting, how can robust learning be ensured? And what is necessary for robust learning?
To answer these questions, generalize the corrupted hypothesis classes 14 standard hypothesis classes in the binary setting in the presence of an adversary, and use them to reduce the robust learning problem non-robust one. By considering the graph dimension and Natarajan dimension of the corrupted hypothesis classes-which are defined as the adversarial graph dimension (AG-dimension) and adversarial Natarajan dimension (AN-dimension) respectively-we derive the upper and lower bounds of sample complexity of the robust multiclass learning problem. We then analyze the AG-dimension and the AN-dimension of linear multiclass predictor class, showing that the dimenninnnnnio and the graph (Natarajan) dimension are of the same order. Since proven that the graph dimension and the Natarajan dimension are equivalent when
which arise from
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

target class is finite [2]] is it possible to use the AG-dimension and AN-dimension to bound each other? Our work suggests that the equivalent relationship does not hold, which is illustrated by constructing a hypothesis class with finite AN-dimension but not robustly learnable.
Related work. [3 16 18 focus on the robust binary classification problem. [T)] characterize
the multiclass Icarnability in non-robust setting. [99 12 20] define a large family of notions of dimen- sions, all of which generalize the VC-dimension and may be used to estimate the sample complexity
of multiclass classification. [2]] calculate the graph dimension and the Natarajan dimension of linear
multiclass predictor class. [22] upper bounds the adversarial risk of linear multiclass classifiers
based on Rademacher complexity. which cannot directly derive bounds of sample complexity of general robust multiclass learning problems. The theory on robust multiclass learnability for general hypothesis class is less explored. This work takes some steps towards solving this problem.
2 Preliminaries
This section introduces some basic notations and concepts used throughout the present study.
In the remainder of this article, IR, N. IR+ and Rd represent the sets of real numbers, natural numbers, non-negative real numbers and d-dimensional vectors over RR respectively. We denote the set (1.....n) (for n E N) by [n].- If A and B are sets, we use B to denote the collection of all mappings from A to B and 2 denote the power set of A, that the collection of all subsets of A. Let C = {cl,.... Cm } C X and C' C C' be a subset of C, then Ic E [m] denotes the index set of C" Let H be class of functions defined in X, then H|c represents the restriction of H C, that is h E H}. We denote the indicator function by 1 (eventt), that is 1 if an
He {(h(c))..... h(cm)) (h(la))........)))) event happens and 0 otherwise. Finally, || llp represents the lp norm.
The robust learning problem is formalized as follows. Let X IRd be the instance space and y (1.....k) k} be the label space. For an unknown distribution D over X' x >n a hypothesis class H y the goal of robust learning is find function f H. based on n labeled training samples S = {(x;, }/ drawn independent and identically distributed (i.i.d.) from D, such that under a small perturbation U X + 2 the adversarial risk
Ru(f: D) A E (a.))) ('E((x)
sup ((f(x').))
minimal for the 0-1 loss ((), v) A 100 + y).
The perturbation (zx) is required to be nonempty, so some choice of x' is always available. One choice for the perturbation is the p-norm ball (p 2 1) with a small radius r, i.e. U(x) {= E X 0 gives the identity perturbation: I(x) & {x) Note that in this case, the problem is reduced to a standard learning problem, and Rz D) is called the standard risk of f over D.
||2 æ=Ip I r). Selecting
The mechanism of finding a function is called a learning algorithm. In this paper, we focus on proper learning algorithms, that is, learning algorithms will always pick a function from H. Formally, o x 7)"" + H. A common choice of robust learning
learning algorithm is a function algorithm is to lear through adversarial empirical risk mininization AERM for short:
f E SH; arg (f:
JEH
where D,, is the empirical distribution generated by S, i.e. for (z, v) ~ Dn, (I,y) is equal to (I;, y1) with probability 1/n for each E [I,...,,).
Learning algorithms like AERM do not always produce a function that achieves the optimal adver- sarial risk, because training set consisting of finite samples is not always sufficiently informative to represent D. Thus, we introduce the definition of robust probably approximately correct (PAC)
learability, in the realizable and agnostic setting [14 13:
Definition 1 (Agnostic Robust PAC Learnability). Under perturbation U, a hypothesis class H. is
robustly PAC learnable in the agnostic setting if there is a function m4.u : (0, 1)2 + and
Formally, there is sigma algebra F C XxX of events and D is probability measure on (X F)F).

---

learning algorithm A : U on x " - H. with the following property. For every e, E (0,
and every distribution over X x V, let S {(r,, b)) be samples i.id generated by D s.t. ug
>> mHHu (c, Then with probability at least 6,
JEH Ru(A(S):)) S min Ru +
The function maL is defined as the sample complexity learning H. under perturbation U in the agnostic setting.
Definition 2 (Realizable Robust PAC Learnability). Under perturbation U, a hypothesis class H is robustly PAC learnable in the realizable setting there is finction mH, (0, 1)2 N and learning algorithm A - (X' 3 H with the following property. For every c, (0, 1) and every distribution over X x y, let S {(Ti.))) be n samples i.dd generated by 'D s.f. (H, Then with probability at least 6,
(A(A) D) c.
The function m is defined as the sample complexity of learning H. under perturbation U in the realizable setting.
These definitions agree with the standard PAC learnability when 4 = I, which has been widely studied in both hinary (k 2) and multiclass (k 2) setting. We recall the known result regarding the sample complexity of binary learning. Recall the definition of the SopnikkChervoneniis dimension (VC-dimension) [I]
Definition (VC-dimension). Let H C 10, be hypothesis class and let S C X. We say that S shattered by H H|ss = {0, 1 The VC-dimension of H. denoted by VC (H) is the maximal cardinality of set that is shattered by H.
The following theorem, based on the VC-dimension, characterizes the sample complexity of learning binary hypothesis classes.
Theorem 1 {0, 1)x
and (23]
There are absolute constants C1, C2 such that for every H. C
VC (H) + In
VC (H) In + In
Ci
m (H, 5
and
VC VC (H) + In S (e, C2
VC (H) + In
Ci
2²
2
It is natural to seek generalization of the VC-dimension to hypothesis classes of non-binary functions. We recall two generalizations, both introduced by (10):
Definition 4 (Graph dimension). Let 7 C yd be hypothesis class and let S X. We say that H G-shatters S if there exists an f y such that for every T C S, there is g E H such that
Vx Tzg(z) = f(x), and Wx E STT.g()) # f(x).
The graph dimension of H. denoted by da(H), is the maximal cardinality of a set that G-shattered by H.
Definition 5 (Natarajan dimension). Let H. C yd be hypothesis class and let S C X. We say that H N- N-shatters there exists f1.f2 T C S, there is 9 E H such that
y such that Vx E S.fi(x) + f2(z), and for every
Yx E T. T.g(r)) (1),, and Vr E ST.. g(x) f2(x).
The Natarajan dimension of H. denoted by dy (H), is the maximal cardinality of a set that is N-shattered by H.
Both the graph dimension and the Natarajan dimension coincide with the VC-dimension for k = 2. Based on these notions, the following theorem provides the upper and lower bounds of sample complexity of standard multiclass learning:
3

---

Theorem 2 (110 and [2]). There are absolute constants C1, C2 > 0 such that for every H. C v
d2 (H) + In
( S (H) In 1 + In
Ci
and
dy(H)) + +lmg < m mZ, C2
do(H)) 1
C
2²
22
AG-dimension and upper bounds for robust multiclass learning
We start by showing that finite graph dimension is not sufficient for robust multiclass learnability, We then introduce the notion of corrupted hypotheses, presented by [14]. By computing the graph dimension of these hypotheses, which is defined adversarial graph dimension, the sample complexity robust multiclass learning problem in both realizable and agnostic settings.
upper bound
3.1 Finite graph dimension not sufficient for robust multiclass learning
Theorem 2 shows that the finiteness of the graph dimension is sufficient condition for multiclass learnability in non-robust setting. While in adversarial setting, for hypothesis classes with finite graph dimension, one cannot ensure the robust PAC learnability of H. even if (H) = 1.
Theorem 3. There exists hypothesis class H. with dc(H) = 1 and an adversary U such that H. is not robustly PAC learnable with respect U.
To prove this theorem, We first present a lemma, which is generalized from Lemma 3 in [1). Lemma 1. m E Then, there exists hypothesis class H C y such that for any learning rule A: (X x Vyn > H. there exists distribution D over X such that:
1. There exists a function f E H with ;u(f";;) 0.
With probability of at least 1/7 over the choice of S ~ D we have that (A(S))): 2 1/8.
The proof of this lemma is presented in Appendix. We now proceed with the proof of Theorem
Proof of Theorem 3 The argument follows closely a proof of an analogous result by 13 for binary robust learning, but generalizes the constructions and analyzes to match the definition of graph
dimension in the multiclass setting. For each m E N, let Xm
(m)) be a set that (a(") ..... J3m
contains 3m distinct points in X subject to Vz,, 23 E U X if IG # æz, then ((;;) n((x)) 0. And we construct Hm on Xm as follows. For each b E (0, 1,33m 3m we construct set 2, Initialize Z, 0, for each i [3m], if b; + b, and add it to Z, Let h2 : X' - y be a hypothesis such that (x( = and only if x & Z, and x & Xm for m' o m. Furthermore, for fixed m N and & E Xm m' o m, we need all ha map x into a same label yz 1), where is consistent for all m. That is,
then pick point
(aa(m)) such that & Zy for each
11 Vo 1), 1,
Zb. 3m' # m, Xm', otherwise.
(x)))
where -1 is some label that is not equal to 1. Then define
3m
Hm (hb b E (0, 1m
by m).
1=1
Let 76 = Up0 Hm. We claim that dd(H)) < 1. That is, if pick two points 21, E X such that I1 F x22 H. cannot G-shatters {x1, since for all h H and E X, there are at most two cases of h(r), one of which is 1. Hence the only f [[1,22)] - y in Definition 4 that needs to be considered is f(x1) f = f(x2) = There are six cases to consider:
(1) There exists E N such that ø1, 22 E X... Then Vhg E Hmm, 21,02 22 $ Zo by the construction of
7b. Hence has (x1))) = hx(22) = And Vh Hmn for m' + m, we have h(())) ya + 1,h(222) =
Ye # 1. So only obtain labelings (1, 1) and (-1,-1)

---

mm) ) ) There are two sub-cases to consider. (i) 36 (2) There exists m E N such that 01,42 E (
s.t. ha E Hm and 21 22 E Zo then we have (2 + and hg (x2) & 1. For the remaining h e H we have h(m1) h(z2) ) = 1. So we only obtain labelings (1, 1) and (-1, -1) in this sub-case. (ii) For the remaining sub-cases, labeling (-1-11) cannot be obtained since x1, 22 & Xm for all and there is no such that #22 are in Z in the same time.
(3) # E Xm and 22 E Xm for m o m'. In this case, we have h(z1) = 1, (22) o for E Hms and h(z1) o 1, h((22) = 1 for h E Hm. For those predictors that are in neither Hm nor Hmy we have h(x1) # I, h(x2) * 1. Hence we cannot label both points æ and x2 with (1, 1).
(4) x1 E Xm and 22 E ((mmm )mm for m # m'. Observe that h(æ1)
1 if and only if Hm- But for all E Hm. h always labels I2 with 1. Hence labeling (1, -1) cannot be obtained.
(5) E (Xm))) and 22 ((Xm))))) XmX for # m'. Similar to the discussion above, for all E H. either h(z)) = or h(r2) = So we cannot obtain labeling (-1,-1)
(6) The remaining cases, i.e. ,1,42 & (((m for all E N. In this case
only obtain labeling
(1,1) since for all h E H. we have h(x)) = h(22) = 1.
The arguments above show that (H) < 1. It remains to show H is not robustly PAC learnable. By Lemma [1 follows that for any learning rule A - (X' exists distribution D over Xm y where there exists predictor ht E H with Ry(h"; D) = 0, but with probability at least 1/7 over S D (u(() where m' *
7) + H and for any m E N, there
> 1/8 if A(S) E Hm. Classifiers in Hm also non-robust since they make mistakes points in Xm. This concludes that H is not robustly PAC learnable, which completes the proof.
3.2 Adversarial graph dimension
Consider given hypothesis f X - y. labeled adversarial sample (á. y) is classified correctly
ã E (1) A labeled example (ır, v) is classified correctly ((r) C s [--1 (y). Following [14, let ) = [-), where 1 is the special "always wrong" output, i.c. ((y, 1) ((L,)) v) = 1 for every
y E y. We define the mapping Ny yx yx:
Ke (N) = Su, U(x)) (
(1. otherwise.
(1)
The corrupted set of hypotheses induced by perturbation U is then defined by H - (mu()) H}. Lemma 2 (Lemma 2 in [1] For any perturbation U and distribution D, Bu((fD) RT D))
This lemma bridges the equivalence between robustly learning H and learning H without adversary. which enables to use standard techniques to bound the sample complexity. Intuitively, we can derive a sufficient condition by considering the graph dimension of H. which can be equivalently formalized as follows:
Definition 6 (Adversarial Graph Dimension). Let H C y be hypothesis class and let S C X. We say that H adversarially G-shatters S if there exists an f X + +Y such that for every T C S, there is E H. such that
Ya E T, V,' E =U(x),9(x)) f(x)
and
Vr E STT EU(I), + f(x).
The adversarial graph dimension (AG- Aimdemmnnio of denoted by dH))), ( is the maximal cardinality of set thut is udversarially G-shattered by H.
Proposition 1. Let H. C. yx be a hypothesis class and let H. be the corrupted set of hypotheses induced by perturbation U. Then we have
= =g
The proof is presented in Appendix.
Intuitively, by combining the above proposition with Lemma 2 and Theorem 2 the sample complexity of robust multiclass learning. Formally:
we can upper bound
5

---

Theorem 4. There are absolute constants C' > O such that for every H. C c)x,
(, S 0 (H) In()) + I and
(C(H) (l((2))
2g (e, S SO
6²
Proof. Let H C C be a hypothesis class with (H) = d. For every f E H. define f X' x y - (0. 13 by setting f(x,y) y) = 1 if and only if f(x') = for all a' E EU(x). Note that according to our construction, we have
F(EN)) (2 8) + 1] E (z.))>D
1(f(²') + w) Lx))(()))
sup
(2)
In the realizable case, let H [f: f H}. From the definition, can see that VC (H))
By Theorem I there exists C > 0 such that when draw C( ln(3) 1 In (n)))) samples iid from some distribution D on X' y/, then with probability at least 1 5 we have ((.,)) (x, v) + 1] S c. Plugging 2 into this inequality, we complete the proof for the realizable case and it is similar for the agnostic case.
AN-dimension and lower bounds for robust multiclass learning
In this section, we discuss the necessary conditions for robust multiclass learnability.
4.1 Finite Natarajan dimension is not necessary for robust multiclass learning
We first show that the finiteness of ordinary Natarajan dimension also not necessary for robust multiclass learnability.
Theorem 5, There exist H.ll such that y (H) = 0o but is robustly PAC learnable under U, i.e. m (e, <
Proof. The proof follows the construction from 13 which shows that finite VC-dimension is not necessary for robust binary learnability. Let = y be the family of mappings from X' to y and (xx) X be an aol-powerful adversary. It is easy to see that Vn E N, there exist n distinct points in Rd that are N-shattered by H. hence (?H) = co. Given a distribution D on X x V, let = {(2,, y4)) be m samples drawn i.i.d from D and be a learning rule such that A(S) returns a constant-label predictor h:
h(x) km == arg max (11 Sis m 1/: =k]]/
Va X.
kEY
According to the weak law of large numbers, Dm + as m - 0c, where D,,, is the empirical distribution generated by S, have P [km. arg max P ((ey))DDy k]] Hence for all 8 E (0, 1) there exists mg E N such that when mo. Ru (h: D) reaches the optimal adversarial risk in H. iec () = arg minjen D) with probability at least 1 6.
as m - xo.
4.2 Adversarial Natarajan dimension
Following the idea of generalizing the graph dimension to the AG-dimension, for given hypothesis class H. one can consider the Natarajan dimension of its corrupted hypothesis class to lower bound the sample complexity of robust learnability. However, there are several natural but different ways in which the notion of N-shattering can be generalized: that is, we can either let f2 that witnesses H. N-shattering S take the value $1" or not. Both notions derive necessary condition for robust learnability. In this work, we choose the stronger notion, i.e. we need the entire perturbation sets to be N-shattered by H.
Definition 7 (Adversarial Natarajan Dimension), Let H. C yx be a hypothesis class and let C X. We say that H adversarially N-shatters S if there exist fi, f2 X + + such that Vy E f, #
f2(y), and every T C S, there is g E H such that
Vz E T, Vx' E U(z).g(z)) = fi())

---

and
Vr E SY g( f2(x).
The adversarial Natarajan dimension dimeesinoo of H. denoted by d (H), is the maximal cardinality of set that is adversarially N-shttereed by H.
Based on this definition, we present that:
Theorem 6. There are absolute constants C' 0 such that for every H. y
Te m () 2 C (% +ln())) and (e, 2
d (7( + In(
2
Proof. Let H yd be hypothesis class such that d% (H) d, and let Ha (0, 1 1 be the family of all mappings from [d] to {0, 1). We want to show that for every learning algorithm for H. and every e, ô E (0, 1), there exists learning algorithm A satisfying: if there exists function ""A (0, 1)a + N such that when A witnesses m > "x (c, 5) samples (denoted as S) drawn ii.d from some distribution D, P.P( D) <c] > 1 1-6 6. Then when À witnesses samples (denoted as S') drawn iid from some distribution D' on [d] x {0,1}. (A((") D') S
1- holds. By this claim, we have xx I ", thus IH.I maa Note that VC (H.a) = d, so by
Theorem we have (e, (n, similarly for the agnostic case.
C( d+In(1/61) for some constant C (independent of H.), and
We now prove the claim. Let {si...., fas X' be set and let fur fi be functions that witness the adversarial N-shattering of H. Given sample set S' & {(x;, y.) C [d] {0, 1}, let = A((s2.) fur ($,, ()m)))))))) Consider the learning algorithm A o 13) - Ha :
A(S) = { - L otherwise.
g(s))= f(()), Vsy e U(s)).
Denote A(S") by f. By the definition of adversarial N-shattering, it can be derived that f() = 0 if and only g((5)) = fa(s,), Vey E ((s)). . By the construction we have
E B ( + y)] E (.:))ar )EE(()z))
[
sup 1(g(8/) + [x(+)))] = (L.N)/Di Rec Dr D'n),
where D' is defined by Poy (X = = = (o(;)) (J = B, B= = y).
The AG/AN-dimension of linear multiclass predictors
In this section, calculate the AG-dimension and AN-dimension for linear multiclass predictors
under bounded Ip perturbation, motivated by the binary results of [14) and the non-adversarial results of [21] Recall the definition linear multiclass predictors. Let : X x y + Rd be a class-sensitive feature mapping
24
xz, y) O0. 10....,0.2
0,
(d)
O,....O,,
EB19-12a
ER4
ER(A-WDd Pid
where z00) represents the ,th coordinate of x. The class linear multiclass predictors is defined as Hy = {x + arg max(w, (x i)) E Rd
(3)
vey
We cite that the graph dimension and Natarajan dimension of Hy is given by (d 1)(k- 1) < d (Hv) S (Hv)) < O(dk (ndk)) (21]. We will demonstrate that the AG-dimension and AN- dimension also satisfy this bound in the remainder of this section. To this end, start by calculating the AN-dimension of He. Specifically, one can show that the AN-dimension of Ho equals to the standard Natarajan dimension of Ha.
Theorem 7. Let u(x)
{2 X 1|2- zllp S r for some E Rt and p E R+ U (0o), and let Hy be defined in 3 Then, the AN-dimension of Hu satisfies & (H₂) = dN
7

---

Proof. Since adversarial N- shatterring implies N-shattering, we have d (Hw) S (Hy)) ). To prove the inverse inequality, it should be noted that the classifiers Hy are linear, hence if Hy N-shatters S, it also N-shatters the set with some I: E S replaced by Vr' E l2, where 1, is the half-line which terminates and goes through z. For those x E that cannot be adversarially N-shattered by Hv, we can always find some x' E l such that (x²) does not cross the decision boundary of gr that witnesses the N-shattering for all T E S.
Note that the Natarajan dimension of Hy satisfies 10-1)(k- 1) S dy (Hv) S dk (Corollary 29.8 in (25)). Combine this result with Theorem 7 we have;
Corollary 1. Under the conditions of Theorem 7 (d 1)(k - 1) S d% (Hw) S dk.
Next, we present the AG-dimension of Hyy
Theorem 8. Let U(x) {2 X' ||2 zllp I r for some E R+ and p E R- U (oo), and let Hy be as defined in Then, the AG-dimension Ho satisfies
(d - 1) - 1) - (Hww) I Odk (n(k)).
To prove this result, we first present a lemma, which can be viewed as the generalization of Sauer's Lemma [26] the adversarial setting. We first define the restriction of a corrupted class, Let H be the corrupted hypothesis class induced by U. Let S {x1,,-.. Imm) } C. Fix a ʃ E ys, for each H. define h S + {0, }} such that h (ara) = if and only (x)))) = [wx),, i [m].
Define Hj
{hy= : h E H}. The restriction of H to S is defined by:
H|s Hyols: where l" arg max feys
Hyls
Lemma 3. Let U be an adversary and H be a hypothesis class with dg (H) S da cc. Let H. be the corrupted hypothesis class induced by U. Let S {21,..., Imf C X. Then, for all m > do + 1 we have
de
em
Ais s
dG
Proof. By Sauer's Lemma 26 and the fact that VC(H,)) S (H) for all f e ys.
We now prove Theorem g The construction idea follows the proof of the non-adversarial results in 21
Proof of Theorem 8 The lower bound follows from Theorem and the fact that dz((H) 2 & (H) for all H. To upper bound de dz (7), let S (.1,.... de E Rd be which is adversarially G-shattered by Ho, and let f : 5 + y be a function that witnesses the shattering. For every (i,j) E [da] [k], define ži.j V (x;, J (a.)) ((x,,,)) Denote Z {2 (i.jj [de] []] We now show that there exists injective mapping from subsets of 5 Wy z. where Wick is the class of halfspace classifiers over Rdlk
For each T c. S, by the definition of adversarial G-shattering, 3hr E Hy such that
Vo E T, E((x), (x') = f(x), and Vo E SVT,3r' E (T(()) 4 f(x). (4)
Let wr E didk be the vector defines hr. implies
Vx E T,V Eu(x), Vj E [k), (wT, ((x,)(())) 2 (wr, ((4',1));
and
(5) It can be easily derived from 5 that Vi E TS 3j E [M] V(zig) s.t. (WT, z²) < 0, where V is the p-norm ball in IRdk with radius r. And from 5 we can assume w.l.o.g that E [T, Vj E [k), V2' e V(zLs); ). (wT, =²) 2 O. This is because if there exists some z' E (=)) s.t. (WT,2") < O, notice that V(e')+z,,) + for some bounded é', we can replace x; by some x/ without destroying the adversarial G-shattering (see the trick used in proof of Theorem 7), to ensure (WT, (2), fxx)) (2(,
Ve SVT ((()),
[k], (WT, (a f(z))) (WT, (a',j))
8

---

(wr,c), VC E V(0). Consequently, for every T E S we obtain label pattern Pr : [de] x [k] + (0.1):
Pr(2ss) = 1 min (uT, =²) 2 0). ='E((H.))
satisfies that Vi E Ir,j E Ps..) = and Vi E Isyr, E Pr..Pr(i.)) 0, which implies
Pr + Pry for T + T". And by definition Pr connected with a unique element in W 12, which completes the proof of our claim.
Note that the AG-dimension of halfspace classifier class with respect to u coincides with the definition of adversarial VC-dimension in [14. Thus it satisfies that d' (Wilk) dk by Theorem 2 in 14 Consequently, we have
& (WWdk)
e
12 = 2
With l
<
Walk
S (kda)) dktt1
(Mrc))
where we have used Lemma in step (i). We conclude that de S (dk In dk)..
AG-dimension and AN-dimension are not equivalent
In previous sections, we have shown that the finiteness of the AN-dimension is a necessary condition for robust learnability, and the finiteness of the AG-dimension learnability. Furthermore, we analyze these definitions on the linear multiclass predictor class, finding that the AG-dimension (AN-dimension) matches the order of the graph dimension (Natarajan dimension) for this class. The following question therefore naturally arises: are these two quantities equivalent? 12 is proven that for every hypotheses class H C c
sufficient condition for robust
dx S dc < 4.67 log2 (H) That is, in standard learning setting, if oo then the definition of the Natarajan dimension and the graph dimension are indeed equivalent, hence both the Natarajan dimension and graph dimension can characterize the standard learnability of a hypothesis class. However, in the adversarial setting (M & I), the generalized definitions derived above cannot bound each other. To show this, we claim that finite AN-dimension not sufficient for robust learnability.
(6)
Theorem 9. There exist H. U such that & (H) = 0 but H is not robustly PAC learnable under U. i.e. mz (e, 00.
x112 S r) for all E X and some 0. We construct H as follow. Pick a sequence )e C X' such that for any i + (2; 0. Let : X + y be function satisfying: there exists 2, E ((x;)) 2 such that f(z)) + f(x;) for each i E N. For each sequence b = {b. C (000 define hS X + +
Proof. Let 2 be the 2-norm ball: u(x) E X'
[(x;), x E ((x))== i N,
2; and b; 1, f(z), x = 2, and b; O. otherwise.
f(xa),
hx(z)=
1.
Let H = {hh 6 a sequence in {0, 1}}. Using the same approach employed in the proof of Lemma 1. for any learning rule A J (X' 1) + H. there exists distribution D over X' x )/ such that there exists a function f E H with () = 0, and with probability of at least 1/7 over the choice of S ~ Dm we have that (A(A(S);
1/8, by considering the distribution family D containing distributions that are uniform over 2m points in ((1)))()))
(Nam (I)mm }) We complete the proof by noting that d (H) O, since there is no single r-ball that is adversarially N-shattered by H.
Conclusion
In this work, we construct the concepts of AG-dimension and AN-dimension to upper bound and lower bound the sample complexity of robust multiclass learning, respectively. We further analyze the AG/ANN-dimensinn of linear multiclass predictors and prove that AG-dimension and AN-dimension are not equivalent general. However, establishing a complexity measure that characterizes robust lcarnailiiyy still remains an open question.

---

Acknowledgements
This work is supported by the National Natural Science Foundation of China under Grant 61976161.
References
[1] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[2] Hongyang Zhang. Yaodong Yu, Jiantao Jiao, Eric P. Xing. Laurent Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 7472-7482, 2019.
[3] Zekai Wang and Weiwei Liu. Robustness verification for contrastive learning. In JCML, volume 162 of Proceedings of Machine Learning Research, pages 22865-22883, 2022.
[4] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In IEEE SP, pages 39-57, 2017.
[5] Nicholas Carlini and David A. Wagner. Audio adversarial examples: Targeted attacks on speech-to-text. In IEEE SP, pages 1-7, 2018.
[6] Weiwei Liu, Donna Xu, Ivor W. Tsang, and Wenjie Zhang. Metric learning for multi-output tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(2):008-422, 2019,
[7] Weiwei Liu, Ivor W. Tsang, and Klaus-Robert Müller. An easy-to-hard learning paradigm for multiple classes and multiple labels. Journal of Machine Learning Research, 18:94:1-94:38 2017.
[8] Xiuwen Gong, Dong Yuan, and Wei Bao. Discriminative metric learning for partial label learning. IEEE Transactions on Neural Networks and Learning Systems, pages 1-12, 2021.
[9] Xiuwen Gong, Dong Yuan, and Wei Bao. Top-k partial label machine. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[10] B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67-97, 1989.
[11] Vladimir Naumovich Vapni. The Nature of Statistical Learning Theory. Springer, 1995.
[12] Shai Ben-David, Nicolò Besa-Bianchh, David Haussler, and Philip M. Long. Characterizations of learnability for classes of {0, .... n)-valued functions. Journal of Computer and System Sciences, 50(1):744 86, 1995.
[13] Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learnable, but only improperly. COLT, volume 99, pages 2512-2530, 2019.
[14] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. In NeurlPS, pages 228-239, 2018.
[15] Justin Khim and Po-Ling Loh. Adversarial risk bounds for binary classification via function transformation. CORR, abs/1 /e//1180009119 2018.
[16] Robi Bhattacharjee, Somesh Jha, and Kamalika Chaudhuri. Sample complexity of robust linear classification on separated data. In JCML, volume 139 of Proceedings of Machine Learning Research, pages 884-893, 2021.
[17] Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Lower bounds adversarial robustness from optimal transport. In NeurlPS, pages 7496-7508, 2019.
[18] Dimitrios I. Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Lower bounds for adversarially robust PAC learning under evasion and hybrid attacks. In ICMLA, pages 717-722, 2020.
[19] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
10

---

[20] David Haussler and Philip M. Long. A generalization of sauer's lemma. Journal of Combinato- rial Theory, Series A, 71(2):219-240 1995.
[21] Amit Daniely, Sivan Sabato, and Shai Shalev-Shwartz. Multiclass learning approaches: A theoretical comparison with implications. In NeurIPS, pages 494-502, 2012.
[22] Dong Yin, Kannan Ramchandran, and Peter L. Bartlett. Rademacher complexity for adversari- ally robust generalization. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 7085-7094, 2019.
[23] Peter I., Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
[24] Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kemel- based vector machines. Journal of Machine Learning Research, 2:265-292, 2001.
[25] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
[26] Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A. 13(1):145-1444 147, 1972.
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? [N/A]
(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]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing 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'r 're using/curating? [N/A]
(c) 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 to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "ZHKxJzu-AsU", "reviewer": "Reviewer_PJsj", "summary": "\nThis work considers the adversarially robust PAC-learnability in the context of muulticlass learning. The main contributions are the following. \n\n- First the authors show that the usual G-dimension (\"G\" for \"graph\") and N-dimension (\"N\" for \"Natarajan) notions of complexity which are sufficient to gaurantee ordinary multiclass PAC-learnability, are in general, neither sufficient nor necessary nor adversarial PAC-learnability. Refer to Theorems 3 and 5.\n\n- Then, the authors extend the G-dimension / N-dimension complexity measures to the adversarial setting, namely: adversarial G-dimension, or AG-dimension for short, and adversarial N-dimension, or AN-dimension for short. The authors show that finite AG-dimension (resp. finite AN-dimension) is sufficient (resp. necessary) for adversarial multiclass PAC-learnability. See Theorems 4 and 6.\n\n\n- For bounded $\\ell_p$-norm attacks, the AG-dimension and AN-dimension of linear multiclass predictors is computed to be rough $\\tilde \\Theta (d\\cdot k)$, where $d$ is the input-dimension and $k$ is the number of classes. See Theorems 7 and 8.\n\n- Finally, the authors prove (Theorem 9) that AG-dimension and AN-dimension are not equivalent because unlike AG-dimension, finite AN-dimension is not sufficient for adversarial PAC-learnability. This is in stack contrast with the ordinary / non-adversarial scenario finiteness of G-dimension and N-dimension each fully characterize PAC-learnability, and so, these dimensions are equivalent to each  other.", "questions": "For the binary-case where $k=2$, do the results presented in this paper fully recover the existing literature ?", "limitations": "This is a purely theoretical work about understanding the algorithmic gap between ordinary and adversarial learnability. There are no social / societal issues here.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n---\n- First work to fully characterize multiclass PAC-learnability in adversarial setting.\n- Paper is extremely well-written and contributions are clearly developed. Also ordinary / non-adversarial multiclass PAC-learnability theory is conveniently reviewed before presenting main contributions. This helps the reader crispy see the gaps between ordinary and adversarial theory (developed here).\n\nWeaknesses\n---\nI could find no real weaknesses, just a few typos, etc.:\n\n- Line 73: \"$\\hat D_n$ is equal to $(x_i,y_i)$ w.p $1/n$\" doesn't seem to make sense. Indeed, $\\hat D_n$ is a (random) distribution on $X \\times Y$, while $(x_i,y_i)$ is a point of $X \\times Y$.", "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": "AD9zp1O6N0q", "reviewer": "Reviewer_A37A", "summary": "This work analyzes the robust learning problem in the multiclass setting and then derives the adversarial graph dimension (AG-dimension) and the adversarial Natarajan dimension (AN6 dimension) from the graph dimension and the Natarajan dimension.\n", "questions": "\"We then analyze the AG-dimension and the AN-dimension of linear multiclass predictor class, showing that the AG(AN)-dimension and the graph (Natarajan) dimension are of the same order.\" can these results hold for the non-linear models? \n\nSince the AG-dimension and AN-dimension are not equivalent, which one is better? ", "limitations": "\nPlease see the comment above.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper shows that the graph dimension and the Natarajan dimension are no longer applicable in robust learning problem and then generalize these notions to the robust learning setting, denoted as the adversarial graph dimension (AG-dimension) and the adversarial Natarajan dimension (AN dimension).\n\nIf there provide some experimental results to verify the theoretical analysis will be more convincing.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "6M0lYqkNmEn", "reviewer": "Reviewer_mVKM", "summary": "The paper defines multiclass robust learnability and makes progress towards obtaining necessary and sufficient conditions on hypothesis classes for it. Adversarial versions of graph and Natarajan dimensions are defined to this end and used to give sufficient and necessary conditions respectively. It is also shown that the known non-adversarial graph and Natarajan dimensions do not give the respective learnability conditions. Near tight estimates of the proposed dimensions are given for linear multiclass predictors under bounded Lp perturbations, the bounds happen to match known bounds for the non-adversarial variants. Finally, it is shown that (in contrast to their non-adversarial versions) the proposed adversarial dimensions are not equivalent (for finite number of classes).\n", "questions": "Questions for the authors:\n\nThere is a subtle difference in the quantifiers over U(x) in the definitions of adversarial graph and Natarajan dimensions (existential in AG but forall in AN). Can the authors give some intuition for this difference?\n\nTheorem 6: What is the definition of $m_{A,U}^{re}$ where A is a learning algorithm instead of a hypothesis class? In the proof of Theorem 6, how Theorem 2 is used?\n\nIs it correct to conclude from Section 5 that sample complexity for robust and standard learning of linear predictors is about the same?\n\nLine 280: should it be $m^{re}_{H,U} = \\infty$ since the proof has $R_U(f^*,D)=0$?\n\nOther comments/typos:\nProof of Theorem 7 repeatedly uses ideas from Theorem 8, consider switching them around for readability?\n\n\nLine 71: worth commenting that only proper learning is considered, improper learning rules can output any function in Y^X not just H.\n\nLine 133: statement is somewhat unreadable. Do you mean \"if \" x_i\\ne x_j \"then\" U(x_i)\\capU(x_j)=\\emptyset?\n\nTheorem 8: It seems more informative to state the theorem as 'robust natarajan dimension coincides with its non-adversarial counterpart for linear classifiers under bounded lp perturbation', and the current statement as a corollary of this result and previously known bounds.\n\nP(x) should be U(x) in equation (1)\nLine 224: S' \\in (Y \\times {0,1})^m\nLines 284,285 {0,1}^*\nLine 290: \"adversarially\" N-shattered\n", "limitations": "It could be worth stating explicity that as a consequence of Theorem 9 this work does not fully characterize robust multiclass learnability and determining necessary and sufficient conditions is an open problem.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Robust learnability in the multiclass setting captures an interesting and relevant learning setting. The paper provides a necessary and a sufficient condition for general hypothesis classes and also provides instantiations for linear classifiers.\n\nAn important contribution is defining the adversarial graph and natarajan dimensions, which are used to show upper and lower bounds on sample complexity of robust multiclass learning. The results seem sound.\n\nTheorem 9 is interesting, it shows an example where the robust graph dimension is infinite but the robust Natarajan dimension is finite/zero. This implies that multiclass robust learnability is not completely characterized in this work.\n\nMy major concern is about the presentation of the results - in particular inadequate referencing to known proofs/techniques - which also makes it harder to assess the originality of the contribution. This is particularly important for this work since a lot of the presented results have known two-class and/or non-adversarial counterparts.\n\nSome concrete examples about the reference to prior work in some of the results:\nLemma 1: The lemma looks identical to Lemma 3 of [6], even the proof is the same. You should simply cite the original lemma in this case.\nTypos: should be H\\subseteq Y^X instead of H\\in Y^X. The expression A(S) in (2.) should have calligraphic A and S.\nTheorem 3 looks like an extension of Theorem 1 of [6]. It is worth pointing out the main differences in the proof technique (i.e. in construction of h_b and bounding its graph dimension) relative to Theorem 1, [6] since the overall idea looks very similar.\nTheorem 5 extends the construction in section 5 (para 1) of [6] which shows finite VC dimension is not necessary for (two-class) robust learnability.\n\nAlso, in my opinion, the novel proof/technical insights relative to prior work are not properly indicated/summarized. For example in section 5, it would be nice to summarize the novel ideas needed to extend/combine the non-adversarial results of [14] and k=2 results of [7].", "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": "1h8MgxH-kf-", "reviewer": "Reviewer_u7Pp", "summary": "This paper aims to characterize the PAC learnability of robust learning problem in the multi-class setting. To this end, define the AG dimension and AN dimension, and provide both upper and lower bounds for sample complexity of robust multi-class learning. Thereafter, they give the AG dimension and AN dimension of linear multi-class predictor class. Lastly, they show that AG dimension and AN dimension are not equivalent.", "questions": "1. I feel the notations in the proof of Theorem 3 is a little confusing. In the expression of $h_b$,  can the first and second cases be combined, since $y_x\\neq 1$? I would appreciate it if you can define $h_b$ more clearly.\n2. In section 4.2, the authors discuss alternatives to generalize the AN dimension, but I am confused about the claim “we choose the stronger notion” in Line 210. Why is the chosen notion stronger?\n\n\n\n----------------\nThanks for the reply. The response has addressed my concerns well.", "limitations": "N/A", "rating": 9, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1.\tThis paper is novel in the sense that the robust multi-class learning under PAC framework is not studied in the literature. \n2.\tThe motivation of this paper is strong.\n3.\tIt is well-written and easy to follow. The logic of this paper is clear and natural.\n4.\tThe theoretical proof seems to be sound based on my judgment.\n\nWeakness: \n1.\tThe authors rarely discuss the insight of the theorems and the construction in proofs.\n2.\tIt seems that the theory in this paper can hardly help us foresee whether we can train a model that is robust to adversarial perturbations.\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": {}}]

Author rebuttal:

Decision: Accept