Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The main contribution of this paper is showing that in the Equivalence-Query Learning model, the query complexity depends only poly-log on 1/epsilon, versus the 1/epsilon dependence in the PAC learning model.

main_review: I believe that the main result (Theorem 3.1) is novel. In Section 3.3, this presentation of the main result is also interesting: taking any black-box PAC learner and converting it to a learner in the EQ-model but with improved dependence on (1/epsilon). I suggest making this a bit more formal, e.g. as a Corollary. 

I am a bit hesitant about the connection of this main result with the rest of the paper in Section 4 and 5. 
Specifically, I do not see how Section 5 fits with the rest of the paper:
The problem of adversarial robustness is not formally defined. What is the goal here? Even the discussion (lines 282-299) about the attacks, and needing to introduce new attack models, it is not clear why that is necessary without even defining the goal. Is the goal to generalize against any adversary that is restricted to some perturbation set, or to a fixed specific adversary that we can interact with during training time?

Even with the  model of attack (definition 2) in Section 5.1, there are no guarantees given in the paper, except for Corollary 1, which is not very meaningful in terms of robustness guarantees. Because all it says is that we can view the adversary as an equivalence query oracle. This has already been presented in Section 3, so I am not sure if its adding anything new.   

In Section 5.1, the authors should discuss the related work of Montasser, Hanneke, Srebro (2021). That work introduces similar learning models where the learner interacts with an adversary (similar to Definition 3), with the addition that an end goal is specified which is either obtaining: robustness guarantees against *any* adversary that is constrained to some perturbation set,  or robustness guarantees against a *fixed* adversary that the learner can interact with at training time. This is currently lacking in this work, and I encourage the authors to think further about their end-goal in the adversarial learning setup.  

Some minor comments.
- lines 282 and 283: the statement is not clear. Is it not possible computationally or statistically? 
- lines 371 and 372 are not accurate. There is no robustness guarantee presented in Section 5.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

After Rebuttal.
I thank the authors for their response. After consideration, I decided to keep my score the same. The connection to adversarial robustness is a bit under-developed in my opinion. One of my main concerns is that the result presented in Corollary 1 (Section 5) lacks any robust learning guarantees. Specifically, at best, the learned predictor will have low standard generalization error (but it won't necessarily be robust to adversarial perturbations). I encourage the authors to think further about the robust learning guarantees they are considering. 
limitations_and_societal_impact: In my opinion, the authors have adequately addressed the limitations of their work and negative societal impacts of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies the query complexity of learning general hypothesis classes $(X,H)$ in the randomized equivalence query model (w/ PAC guarantees). In this interactive model, the learner has access to the “EQ oracle” which upon input of a hypothesis in H, outputs a random counterexample (based upon the target concept and marginal distribution chosen originally by the adversary). The authors use a boosting procedure to show that learning in the randomized EQ model requires only $d*\text{polylog}(1/\varepsilon)$ queries where $d$ is the VC-dimension of $(X,H)$. This provides an exponential separation with the PAC model, which takes $\Omega(d/\varepsilon)$ queries to achieve the same guarantees.

The authors motivate this theoretical result by tying it to recent research in adversarial robustness. They argue that the EQ model can be seen as adversarial training against a restricted adversary. They claim that their results give a theoretical explanation of recent experimental work showing that (on-manifold) adversarial training achieves good generalization, and argue that the exponential separation could be used as a potential tool to prove robustness against such adversaries. 
main_review: The randomized EQ-model is well studied in the regime of finite hypothesis classes (where it is known that perfectly identifying any $h \in H$ requires $\log(|H|)$ queries), but to my knowledge this is the first work giving PAC-style guarantees for general hypothesis classes. The model is mathematically natural in this regime, and the obtained exponential speedup (in query complexity) is quite interesting. In fact, since active learning with a sample oracle fails in many natural scenarios, this result is the first I know of giving an exponential speedup for all PAC learnable classes (albeit in a much stronger interactive model). The proof technique is a novel twist on majority boosting, and can sort of be thought of as a (much trickier) version of known connections between perfect selective classification (or RPU learning) and standard active learning. My only complaint on the theory side is that there is no discussion of lower bounds for the model. The query complexity is also obviously off (exponent of 9), but this is discussed by the authors and not really a major concern, as the main point is to show a polylog bound. This result alone is likely of broad interest to the learning community.


On the other hand, I find the rest of the paper, mostly the proposed connections with adversarial robustness, to be hand-wavy and very confusing. The authors make a number of assumptions without much justification, e.g. that the distribution of adversarial attack is random. The claimed connection to robustness against adversaries with restricted learning power is interesting, but not formalized at all. Formally, the authors focus more on adversarial training, but don’t discuss how this leads to adversarial robustness, or even really define the adversary/attack at all in the sense discussed at the beginning of the section (where an adversary attempts to find $x’$ that is misclassified and “semantically indistinguishable” from the input $x$). Overall the writing is too informal, and the exposition doesn’t clearly match up to the definitions and formal statements.

Edit: I thank the authors for their response but my opinion remains unchanged.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the problem of approximately learning a target function (in the realizable case) when having access to an equivalence-query oracle. In this direction an exponential separation is shown between the two learning models by using an algorithm that borrows ideas from boosting techniques. Furthermore, the authors connect the counterexamples returned from the equivalence query oracle to adversarial examples and thus try to connect their work with adversarially robust learning.

main_review: I have not checked in detail the various proofs, but for the largest part the paper is clearly written. The exponential improvement on the query complexity is not very surprising given that the counter-examples are coming from the symmetric difference between the hypothesis and the target. 

The authors discuss adversarial training based on adversarial instances that are drawn from the manifold of the data, and draw a parallel between that model and the model of learning by using equivalence queries. The point is that the the improved complexity bound in the PAC-EQ model that is discussed in the paper can help explain the faster rate of learning that can be observed in adversarial training based on on-manifold adversarial instances.

It is this last idea that the authors discuss in more detail in the latter part of the paper, where the adversary may now generate adversarial examples as if these were returned by an equivalence query oracle and naturally they exploit the result from the main part of the paper. 

The exponential improvement result that the authors find between the query complexity of PAC learning and of the PAC-EQ model that they introduce is not very surprising, given that the examples are coming from the symmetric difference between the hypothesis and the target. Furthermore, the authors appear to be introducing a new attack model (based on equivalence queries) and it appears that the justification is in line 300, where they say that "introducing new attack models might be necessary for realizing adversarial robustness in the real world." While it appears that a good discussion has been made earlier in Section 5, nevertheless, I do not quite understand the adversary of the paper and how feasible it can be in a real-world setting. 

There are also some minor typos here and there. 

*after the rebuttal*

Thank you for the response. Having read the reviews of others, and based on the discussion offline, I have concluded that we are all a bit concerned with the latter part of the paper on adversarial robustness. For this reason, my evaluation on this paper has not changed.
limitations_and_societal_impact: I am happy with the discussion that the authors have done in the paper.
review_title: null

Meta-review: This paper studies the problem of PAC learning from equivalence queries (EQs), i.e., counterexamples. It is shown that d*polylog(1/eps) EQs suffice to learn concept classes of VC dimension d within eps. In contrast, in the standard i.i.d. statistical learning setting, the answer is ~ d/eps. This result appeared to be novel to the reviewers. The second part of the paper attempts to draw some connections to adversarial robustness. This part was rather confusing for all the reviewers and raised a number of concerns. After the discussion, all the reviewers recommended rejecting the paper in its current form.
Decision: Accept (Poster)