Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers (adversarial) robust learning in the PAC learning framework. As opposite to the "standard" notion of adversarial robustness, where the hypothesis $h$ is considered to be robust at point $x$ with radius $\epsilon$ if the target concept is $c$ and it holds that $||x'-x|| \leq \epsilon \implies h(x')= c(x)$. Here, the hypothesis needs to be correct in the epsilon ball to be considered robust. That is, it needs to satisfy $||x'-x|| \leq \epsilon \implies h(x')= c(x')$. To achieve this, the learner is allowed to use "Local membership queries" in at-most $\lambda$ distance from the observed point. The paper then shows that when $\lambda < \epsilon$, there is a distribution not learnable by any learner (thm 2). Then they provide several robust learnability results (thms 7,9,10,11) on classes such as linear threshold functions and conjunctions.
strengths_and_weaknesses: 

# originality, clarity, quality, significance
- Originality - The proof techniques seem to be standard (often the proofs are trivial modification of analogical proofs in the standard setting) but the considered problems are original, so I think the originality is ok. However, if there is some original technique that I have missed, I suggest the authors to emphasize it.
- Clarity - Clearly written. Only that there are used lots of abbreviations which slows down the reading, but their presence is understandable.
- Quality - I haven't found a problem.
- Significance - I don't consider this work to be "too" significant, especially because the results are often unsurprising and easy to derive, but I think it has its place.


# Pros
- Easy to read
- Extensive amount of previous work in the appendix, although something is superfluous.
- Quite a lot of results.

# Cons
- The results are sometimes too simple, such as thm 2. which is claimed as one of the main contributions essentially says that when we cannot observe c(x) during training, then we don't know it. For lemma 3, I don't see a difference between the proof and a proof of the lemma in the standard (non-robust) setting (and then thm 9 is a corollary of lemma 3), Similarly lemma 5 seems to only replace VC dimension with robsut VC dimension, but there is almos no discussion on RVC (e.g., what is the RVC of standrd function classes) and so on.

questions: - Please define the distribution-free setting. Does it mean that there are no assumptions on the distribution?  The term suggests that there is no underlying distribution, but then the notion of random sample would be meaningless.  Also I think it would be good if all definitions were in the appendix. Now the majority is there, but consistency is in the main text. 

- Why is correct-in-the-ball notion of robustness interesting? Specially, in this setting, we would like to be correct at every point (which is the same goal as we usually have, as opposite to the constant-in-the-ball risk), thus, the learning is basically the same as in the standard setting. I think there should be at least a brief discussion in the paper about this.

- Feel free to point out any potential errors in the review.

## misc
- footnote 4 - why is Hamming distance the only meaningful distance here? While I agree that is a reasonable distance, I think there are many others and the space can have a special structure which can be of interest. E.g., If there is an underlying graph structure (other than a hypercube) which would induce the distances so that the "adversarial neighborhood" may contain e.g., neighboring nodes.




limitations: -
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study adversarially robust learning in the "exact-in-a-ball" model when the learner has access to additional types of local queries. The `exact-in-a-ball' robustness model replaces the standard PAC classification error with

$$\Pr_{x \sim D}[\exists z \in B(x,r): h(z) \neq c(z)]$$

This differs from the widely studied "constant-in-a-ball" model that instead uses $h(x) \neq c(z)$. Since learning even basic concepts in this model is typically impossible, the authors examine two types of enriched query algorithms: local membership queries and local equivalence queries. The former allows the learner to query any point in a small ball around any training example, and the latter allows the learner to ask whether a given hypothesis h is robust on a small ball around the point.

The authors show that while local membership queries do not help robust learning even in basic cases such as conjuctions over the uniform distribution, local equivalence queries can be used to robustly learn several non-trivial hypothesis classes such as conjuctions and halfspaces with margin, even in the distribution-free setting. In fact, the authors more generally show it is possible to robustly learn any finite class or class with finite robust VC dimension that has an online learner in the mistake bound model. Their algorithm is computationally efficient as long as the online learner is as well, which leads to statistically and computationally efficient robust learners for conjunctions and halfspaces with margin.

strengths_and_weaknesses: The `exact-in-a-ball' model of adversarial robustness is a challenging learning model, and this work gives the first efficient robust learners for important classes such as halfspaces with margin. While most of the general techniques in the work are not particularly novel (e.g. Robust VC, use of online learning), the eventual application and analysis showing halfspaces actually satisfy these conditions (namely Robust VC) is nice. Overall, the results are a bit niche, but may be of interest to the adversarial learning sub-community.

On the other hand, the paper can be a bit confusing at places, and also seems to have some small errors. Most of the sample complexities for instance seem to be missing a $\log(1/\varepsilon)$ term that should appear from applying Sauer-Shelah. The statement of results in Section 3.2 are also a bit confusing and stated in a non-standard fashion (perhaps a more typical presentation would be to say any RERM on m samples is a robust learner or something of this sort). Finally, while the authors largely do a good job placing the result in prior literature, it should probably also be mentioned that online learning (namely perceptron) has also been used in other work on robust learning, e.g. in [BJC21] “Sample Complexity of Robust Linear Classification on Separated Data.” 
questions: A few typos: attaks, dimensino, ispoerimetric
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies adversarial robustness of learning basic concepts when the learner is allowed to make local queries. It shows that

- Using local membership queries of Awasthi et al (2013) does not help too much on reducing the robust risk. This is in stark contrast to results established under the standard PAC model.

- It then shows that with access to a new query type, equivalence query, the robust risk can be reduced.

In terms of merit, this paper gives the first robust ERM algorithm when robust risk is defined as being exact-in-the-ball.

In terms of techniques, this paper leverages many useful prior results and seems to combine them nicely.
strengths_and_weaknesses: Strength:

+ The paper studies a timely topic and gives full proof to its main results.
+ It is interesting to consider various oracles to tackle the essentially hard problem of learning with adversarial examples. In particular, the separation result for local membership query appears interesting.

Weakness:

- It turns out that the main positive result is the improvement from using equivalence queries. However, I feel such query type was not well motivated, and seems too strong to find practical applications.

- There are prior works studying the problem through the lens of online learning, which does not rely on the strong oracles, see e.g.

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise, I. Diakonikolas, D. Kane, P. Manurangsi, NeurIPS 2020

The above paper already sets out PAC learnability of large-margin halfspaces via L_p-norm Perceptron. I would like to see a close comparison to Theorem 11 in the submission.

- While the paper presents a handful set of theoretical results, a highlight of the core techniques is missing. Thus, it is unclear to me whether the developed techniques are novel or the established results are just simple sandwich of prior works.

- It turns out that the main claim is a robust ERM when adversarial examples reside exact-in-the-ball while prior works have built upon the regime constant-in-the-ball. I wonder what is the key challenge in the current setting and why existing results cannot be easily adapted.
questions: Please address the weakness part above.
limitations: Yes.
review_title: null

Meta-review: metareview: Solid contribution to NTK theory
confidence: Certain
Decision: Accept