Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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).

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.

An 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.

Theorem 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.

My 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.

Some concrete examples about the reference to prior work in some of the results:
Lemma 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.
Typos: should be H\subseteq Y^X instead of H\in Y^X. The expression A(S) in (2.) should have calligraphic A and S.
Theorem 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.
Theorem 5 extends the construction in section 5 (para 1) of [6] which shows finite VC dimension is not necessary for (two-class) robust learnability.

Also, 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].
questions: Questions for the authors:

There 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?

Theorem 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?

Is it correct to conclude from Section 5 that sample complexity for robust and standard learning of linear predictors is about the same?

Line 280: should it be $m^{re}_{H,U} = \infty$ since the proof has $R_U(f^*,D)=0$?

Other comments/typos:
Proof of Theorem 7 repeatedly uses ideas from Theorem 8, consider switching them around for readability?


Line 71: worth commenting that only proper learning is considered, improper learning rules can output any function in Y^X not just H.

Line 133: statement is somewhat unreadable. Do you mean "if " x_i\ne x_j "then" U(x_i)\capU(x_j)=\emptyset?

Theorem 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.

P(x) should be U(x) in equation (1)
Line 224: S' \in (Y \times {0,1})^m
Lines 284,285 {0,1}^*
Line 290: "adversarially" N-shattered

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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
This work considers the adversarially robust PAC-learnability in the context of muulticlass learning. The main contributions are the following. 

- 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.

- 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.


- 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.

- 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.
strengths_and_weaknesses: Strengths
---
- First work to fully characterize multiclass PAC-learnability in adversarial setting.
- 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).

Weaknesses
---
I could find no real weaknesses, just a few typos, etc.:

- 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$.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

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).

If there provide some experimental results to verify the theoretical analysis will be more convincing.

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? 

Since the AG-dimension and AN-dimension are not equivalent, which one is better? 
limitations: 
Please see the comment above.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength: 
1.	This paper is novel in the sense that the robust multi-class learning under PAC framework is not studied in the literature. 
2.	The motivation of this paper is strong.
3.	It is well-written and easy to follow. The logic of this paper is clear and natural.
4.	The theoretical proof seems to be sound based on my judgment.

Weakness: 
1.	The authors rarely discuss the insight of the theorems and the construction in proofs.
2.	It seems that the theory in this paper can hardly help us foresee whether we can train a model that is robust to adversarial perturbations.

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.
2. 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?



----------------
Thanks for the reply. The response has addressed my concerns well.
limitations: N/A
review_title: null

Meta-review: metareview: Exceptional contribution to multi-class theory
confidence: Certain
Decision: Accept