Exponential Separation between Two Learning Models and Adversarial Robustness
Authors: Grzegorz Gluch
rudiger urbanke
Venue: NeurIPS 2021 Poster (2021)
Keywords: learning theory
adversarial training
adversarial robustness
generalization

Abstract: We prove an exponential separation for the sample/query complexity between the standard PAC-learning model and a version of the Equivalence-Query-learning model. In the PAC model all samples are provided at the beginning of the learning process. In the Equivalence-Query model the samples are acquired through an interaction between a teacher and a learner, where the teacher provides counterexamples to hypotheses given by the learner. It is intuitive that in an interactive setting fewer samples are needed. We make this formal and prove that in order to achieve an error $\epsilon$ {\em exponentially} (in $\epsilon$) fewer samples suffice than what the PAC bound requires. It was shown experimentally by Stutz, Hein, and Schiele that adversarial training with on-manifold adversarial examples aids generalization (compared to standard training). If we think of the adversarial examples as counterexamples to the current hypothesis then our result can be thought of as a theoretical confirmation of those findings.  We also discuss how our result relates to adversarial robustness. In the standard adversarial model one restricts the adversary by introducing a norm constraint. An alternative was pioneered by Goldwasser et. al. Rather than restricting the adversary the learner is enhanced. We pursue a third path. We require the adversary to return samples according to the Equivalance-Query model and show that this leads to robustness. Even though our model has its limitations it provides a fresh point of view on adversarial robustness.

Exponential Separation between Two Learning Models and Adversarial Robustness
Grzegorz Gluch
Ruediger Urbanke
EPFL Lausanne, Switzerland grzegorz. Seeegorz.glucheeee glwcchepfl..com .ch
EPFL Lausanne, Switzerland ruediger urbanke@epfl.cm ch
Abstract
We prove an exponential separation for the sample/query complexity between the standard PAC-learning model and version of the Agniivlenee--uer--lleami model. In the PAC model all samples are provided at the beginning the learning process. In the Equivalence- Query model the samples are acquired through inter- action between a teacher and learner, where the teacher provides counterexamples to hypotheses given by the learner. It is intuitive that in an interactive setting fewer samples are needed. We make this formal and prove that in order to achieve an exponentially (in e) fewer samples suffice than what the PAC bound requires. It was shown experimentally by Stutz, Hein, and Schiele that adversarial training with on-manifold adversarial examples aids generalization (compared to standard training). If we think of the adversarial examples as counterexamples to the current hypothesis then our result can be thought of theoretical confirmation of those findings. We also discuss how our result relates to adversarial robustness. In the standard adversarial model one restricts the adversary by introducing norm con- straint. An alternative was pioneered by Goldwasser et. al. Rather than restricting the adversary the learner is enhanced. We pursue a third path. We require the adversary to return samples according to the Equivalance- Query model and show that this leads robustness. Even though our model has limitations it provides fresh point of view on adversarial robustness.
Introduction
We analyze the connections between adversarial training, generalization and robustness. Our key technical contribution is a novel result in the field of learning theory, showing exponential separation for the sample/query complexity of two learning models. This result provides theoretical confirmation for the experimental observations in Stutz al. 2019 and points fresh research direction in the field of adversarial robustness.
Let us start with discussion of our main technical contribution. The first model we consider is the PAC-learning introduced in Valiant [984). J. In this model the learner given i.i.d. samples from an unknown distribution and is tasked with finding a hypothesis with low generalization error. The second model a version of Equivalence- wawlllence-uuryy-ee Query-learning (EQ-Iearning) introduced in [Agglun 1988). In interaction between teacher and learner. In each round of interaction the learner presents a hypothesis and the teacher replies with a counterexample for this hypothesis. Very close models to the model study were considered previously in Angluin and Dohrn [0017) and [Bshouty and Gavinsky [2002]. In this setting the counterexamples produced by the teacher come from the data distribution constrained to being the error set of the presented hypothesis. We use ideas similar to those used in boosting techniques [Schapire] [990] to prove of
this setting samples acquired through
that the EQ-learning model O(d polylog (1/e) queries suffices to achieve standard
where is the VC-dimension of the hypothesis class. This improves on the previously known
35th Conference on Neural Information Processing Systems (NeurIPS 2021), Sydney, Australia.

---

bounds of O(d/e). We refer the reader to Section B for an in depth review of previous literature on the subject. Standard results for the sample complexity in the PAC model yields an upper bound of O(d/c). Comparing the two results we see the advertised, exponential (in <), separation.
Let us discuss an "application" of our theorem to the relationship between adversarial robustness 2018] it is argued that there is an inherent and generalization. In (Tiipras et al., 2019 Su et al.
trade-off between robustness and accuracy whereas in Gilmer et al. 2018 Rozsa et al. 2 the authors make the case that robustness improves with accuracy. This seeming contradiction is partially resolved in Stutz et al. [019] where it is pointed out that it erucially depends on whether adversarial examples are on or off the data manifold. It is worth mentioning that at the beginning of the field of adversarial robustness it was argued that the reason for the existence of adversarial examples is
exactly that they are uff-manifold [Tanay and Griffin 2016]. However later on it was demonstrated
that adversarial examples do also exist on-manifold (Zhao et al., 2018 Song et al.) 2018 The
authors of [Stutz et al. [2019] argue that it is important to understand this distinction. They introduce a version of adversarial training (Goodfellow et al. 2014, Madry et al. 2018 Tramer al.) 2018
Xiao al. 2019]. which they call on-manifold adversarial training, where the adversarial examples are constrained to lie on the data manifold. They then show empirically that using on-manifold adversarial training one achieves better generalization in comparison to standard training (with the same number of samples). Our theorem can be seen as providing a theoretical support for this claim.
We also explore connections of our results to adversarial robustness. Before we describe these connections in detail, let us position this work in a broader context. Most of the literature on adversarial robustness considers adversaries whose perturbations are in some way restricted. A very common form of restriction is to bound the perturbation in the lg f2, or fox norm [Raghunathan et al., 2018 Wong and Kolter 2018). but other perturbations (rotations, shifts, etc.) were also considered Engstrom et al. 2019]. A recent paper [Goldwasser et al.) 2020] argues that in order to obtain security for real-world systems we need to consider models beyond these "restricted perturbations." Unfortunately this change comes at a price: e.g., the results in Goldwasser et al. 2020 are based on the assumption that the learner can decide not to give answer for some inputs (selective learning [Chul 1965)) ) and that they see the test set upfront (transductive learning), thus the capabilities of the learner enhanced. We follow third path. Instead of restricting the type of perturbations that can be applied by the adversary or enhancing the learner we require the adversary to return counterexamples according the EQ-model. We then show that the exponential separation theorem leads to robustness in our model in the following way: Th main idea of cryptography is to base security computational hardness of specific problems. We follows this idea and base the security of our scheme on the hardness of learning. More specifically, our adversarial learning scheme computes a classifier that is robust assuming that the underlying learning task is hard in the low error regime.
2 Models of learning and attack
We start by defining the models of learning considered in this paper.
Notation. For i E N we define : (1, i). We use log to denote the log to the base 2. For a function f - - +1) and A C X we define ʃ e A function that is equal flips the prediction for points in A. For a distribution D on X and A C X we denote by DIA the conditional distribution that is equal (up to scaling) to D on A and on the complement.
X \ A and
Throughout the paper we consider only the realizable version of learning. That is, we assume that there is feature space X, a distribution D X, hypothesis class H and function h E H. h X + { 1-1, 1,1,11] +1}, }, that defines the ground truth on D. The learner knows and H but neither knows h nor D. The goal of the learner is to find f X + (-1,+1] that has small risk. The risk is defined as
RD P an [f(x) A h(z)).
We will consider algorithms that have access to one of the following two oracles:
Example Query Oracle according to 'D (EXp). When queried, EXp returns (x, h(x)), where
I D.
Equivalence Query Oracle according to D (FQp) (Angluin 1988. For every f : X - +1} (not necessarily from H) the result of querying EQp ( is counterexample to f dis-

---

tributed according to D. More formally it is ~ Dls If (D) = 0 then (QD(f) returns "YES" indicating that f is equivalent to h. For every that returns & i.i.d. samples, each generated by (Q)()).
we write EQp (f. k) denote an oracle
Next we define the two learning models for which we later show the advertised exponential separation. All our results are based on them.
PAC-learning, We say that a learning algorithm L PAC-learns 7. if for every e, (0, there exists m(c, 6) E N such that for every h E H and distribution D algorithm L(c, 6) asks m(e, 6) queries the Example Query Oracle EXp and with probability 1 returns function f E H. such that (f) <.
EQ-learning We say that a learning algorithm L EQ-learns H. if for every e, E (0, 1) there exists m(c, 6) E N such that for every h E H and distribution D algorithm L(c, 6) asks m(c, 8) queries to the Equivalence Query Oracle EQp and with probability - returns function f :X - +13 such that RD, S.
Exponential Separation
We start this section with short literature review.
is worth mentioning that there is a slight difference between EQ-learning model and the model from Angluin and Dohr 2017]. In Angluin and Dohrn [2017] X and H are finite, the learner has to return the exact hypothesis h that was chosen by the teacher, and the distribution on counterexamples is known, For us, on the other hand, X and H may be infinite, our goal is to return function of small risk, and the distribution on counterexamples is not known.
The model from Bshouty and Gavinsky 2002]. which is called Probably Almost Exact (PAE) is almost equal the EQ-learning we consider. The difference is that in the PAE the goal of the learner is to return a hypothesis with negligible error (1/ (1/w(poly(n) where n measures measures the "size" of the input. In the EQ-learning on the other hand we want to explore the dependence on e in detail.
In Angluin and Dohrn [0177] is shown that for a concept class [H] = n it is enough to ask log(n) queries. As we mentioned the setting is different and it's not clear how to adapt this result to the EQ-learning, where we don't t need to find the hypothesis exactly (apart from other differences mentioned above). In |Bshouty and Gavinsky 2002) where the model considered is closer ours, it is shown that PAC-learnability = PAE-Icarnability. A direct application of their technique in our setting yields an upper bound on the query complexity, which is no better than Odd/e). No simple modification of this technique would yield the desired Od polylog(1/e) query complexity. We significantly extend the ideas from Bshouty and Gavinsky 2002
obtain our result.
3.1 Main result
We are now ready to state the main result of the paper, which is an exponential separation for the sample complexity between PAC-Icarning and EQ-learning.
Theorem 1. There exists a learning algorithm (Algorithm [ such that for every E (0, 1/ . E (0, 1). every hypothesis class H of VC-dimension d, for every distribution D the algorithm invoked with parameters 8, H EQ-learns H asking
((dd + [o[d+lo((//))) log(1/))) log (1/e)) queries.
To compare this result to the PAC model we recall that a slightly improved version of the PAC bound in the realizable case [Hanneke] 2016 states that for hypothesis class H of VC-dimension d in order to learn (with constant probability) a classifier of risk it suffices to use O ($) samples. This result is tight in a sense that there exist hypothesis classes and distributions for which that many samples are necessary. Theorem I
guarantees that in the EQ-learning model O(d polylog(1/c)) many queries suffice. This is an exponential improvement. Why is this possible?
Imagine that there is a ground truth H that you try to learn and that you already found h E H such that RD.g (h) S n.. Then the counterexample oracle EQ (h.,)) provides you with samples from distribution D) hegg- Querying the oracle ((d) times you get sample S <- EQp O(d)). You
3

---

can now use the PAC bound: if you find an h E P. that is consistent with S then you know that it has an error of at most 1/2 on D Plagg is then natural to define
ifreh=g (x) = h'xx), ir
[h(z),
Note that Combine(h,,) h() has an error of at most 2 If we repeated this procedure log(1/e) times, queries, you would find a classifier with error
thus asking (odlog)1/
Unfortunately it is not possible to compute Combine h²), Afterall, if you knew the region of the input space where h * g then you could just flip the prediction of ht in that region and the resulting classifier would have zero error. But it turns out that the general intuition of decreasing the error by a multiplicative factor after every ((d) queries can indeed be achieved. The key to this result is find a computable version of Combine /h. h' ...)) that guarantees an exponentially fast decay of the error.
Our algorithm is mainly inspired by boosting techniques, most notably by an approach from Bshouty and Gavinsky 2002]. In this work the authors consider capabilities of polynomially bounded learners. If we assume that the "complexity" of the hypothesis class H is measured by its VC-dimension then the relevant result from Bshouty and Gavinsky [2002] can be summarized as follows. If we have an algorithm L PAC that learns H. to a constant error in time (the authors focus on time but the time is of course an upper-bound for the sample complexity) time(d) then this algorithm can be boosted to an algorithm L FQ that learns H. in the EQ- cQ-model to error ((p in time poly(time(())
Let us apply this boosting technique to our setting. Assume that L PAC runs in time O(d) (as this is the number of samples that are required by the standard PAC bound to learn to constant error). Then the boosting algorithm can be used to produce _ that learns H to error e. What bound on the run time of L =2 do we get? Unfortunately this bound is no better than O ($). This is exactly what the standard PAC bound provides in the first place. Thus, disappointingly, a direct application of these ideas do not yield a benefit in using the EQ-model versus using the PAC-model.
To get the claimed exponential separation between the two models we develop a boosting-like algorithm that differs significantly in several important aspects and hence also requires different proof technique. The main idea is to compute hy,... poopolyoog( E H. in a sequential manner and then define the final hypothesis
version of majority vote of these functions.
The simplified, high level, structure of the algorithm is as follows. Repeat the following for t (polyyog (1/e)) steps: at step i ask the oracle for S: < EQp ( "Majorit""(11........ .t 1), (d)) and then define h, := FindConsistent (S,, H) (FindConsistent returns a function from H. that agrees with all samples from S,). At the end return "Majority" "(h1,... .he). To make this approach work we need to ensure that the error sets of h are sufficiently independent.
The following points need particular attention. First, note that the EQD provides the algorithm with samples from the error set only. Thus, correctly classified points at one stage will not automatically remain correctly classified at later stages. To make sure this happens, at every step we include in the training set S; samples from carefully chosen regions of the feature space that are already classified correctly (this is done in the inner "for" loop of the algorithm). Second, a simple majority vote of the previously constructed classifiers is not sufficient to get the desired result. This is true since a non-neg negligibee region of the feature space might become incorrectly classified with higher and higher confidence by such a majority vote. This is the reason we clip the values of votes to a fixed interval (for details see Definition D.
We start now with the formal definition of the algorithm.
3.2 The Algorithm
In this section we give formal definitions of the concepts used in the algorithm. The proof of correctness of the algorithm is deferred to the appendix. As discussed above we cannot define the final prediction as a simple majority vote. That is why we need to "clip" the votes in a particular way and use a non-standard majority vote-like procedure. Now we define these notions formally.
Definition (Vote and Majority). For E 10, we define B, = [[log(1/e]] +1 and clip, 2 - Z
as:
(x) == min(max( (on(maxx(BBeead B.).
4

---

Algorithm BQlearner
Input: hypothesis class H of VC-dimension d, target error target confidence 6, Equivalence query oracle EQD.
10s log (1/e)
B. = 2 [e')l +1
m = O ((d + log( (B) + log(1/6)) B3)
t = O (
h1 E H.
for i do do
S := 1QQ(Maa |, h1-1),
for E B2 n 27 + do
N' Maj(h1.... h:-1) @ [oote(h,.....b. -1-1))1 E (u,-r})
S = (Q
end for
h4 = FindConsistent
( S., S.
end for
Return Maj(hı,
h2,..., M2,
For sequence of functions hi....,hy hi X [-1,+1}, E (0,1) and x E X, define Vote(hi..... (h)))))).,,,)(()) recursively as:
Vote(hu,.... h.)(x) == clip, (Vote(h),.... (x-1)(x) + 2h,())).
Vote(t:1(()) h1
Similarly. for sequence of functions hi....,,yy hy X 1-1, E (0, 1) and a ground truth function we define Vote (hi,... Voleg(h,,... hz)(2)
recursively as:
Vote, (hi...., (x)
clip. (4 + 2. (-1) (-1)4s(0)=sla)))
Vote, (hi) == (-1))ut)==))))))
Note. Vote(h...... hz) expresses our current estimate for a particular input (together with hz)(x) denotes the error of this current estimate with
level of confidence), whereas respect to the ground truth.
Finally, we define:
= +1, if Vote(hh..... hx)(:.) 20,
1-, otherwise.
Observation 1. Observe that for all i N, hı...., hi X - +1] and X we have:
(x)(2) 22 + 1 n [-- B.] and Vote hx)(2)
(z).
3.3 EQ-learner Booster
Guarantees based on the VC-dimension are often not tight and as our result is phrased in these terms might wonder how much it depends this specific measure. As mentioned, algorithm be understood as boosting technique and hence the result applies more generally. Next, we explain what mean by that.
Let H be hypothesis class and D be a distribution. Imagine that we have an algorithm A that for some distributions learns H. What mean is that A is "PAC-learner" for H but only for class of

---

distributions D. Then imagine that we use A as a subroutine in the EQ-learning algorithm. I.c., instead of following the template of S := EQ ()) h := FindConsistent(S, H) (as in Algorithm ! we use A to get an h that has small error on distribution (QD( Now assume that all distributions [QD(f) for which A is run belong to D.
In this case slight extension of Theorem I shows that we can boost AA in the following sense. Assume that for every e, ó E (0, every D' D A learns H. on D' in QA e, number of samples. Then there exists an EQ-learner (this is Algorithm L which uses A as a subroutine) that learns H. up to error e in number of queries upper-bounded by QA (H, I6 polylog(1/e) ppolylog(//).. Now observe that if
Qa (H, QA H., T6 polylog(1/c)
polylog(1/e).
(1)
then the constructed EQ-Iearner learns H to error e with fewer queries than A does in the PAC- model. This is different type of separation result. In words it says that in some cases you can boost an algorithm from the PAC-model to the EQ- such that fewer queries are required. The condition from 1 in words means that the dependence of the runtime of A grows faster than polylog(1/c). This is a reasonable assumption as in the PAC-learning model for every hypothesis one needs (2(1/c) samples just to see single point from the error set of this hypothesis. This suggests that the dependence of QA (H, e, 5) on e might grow like ((1/e) (which is exactly what happens in the standard PAC-bound). To summarize, even in the cases when the VC-theory is far from reality one can still hope to get interesting results using our technique.
On-manifold adversarial training aids generalization
As we mentioned in the introduction, the relationship between adversarial robustness and generaliza- tion has been the subject of robust scientific discussion, no pun intended. We focus here on /Sutz et al. 2019) and argue that our result can be interpreted as providing theoretical confirmation of the important empiricial findings in this paper. As we will see, the setting of Stutz al. (2019) is close but not identical to ours. But the parallels are strong.
In Stutz al. 2019] version of adversarial training called on-manifold adversarial training is proposed. In this scheme at every step one takes a point x sampled from the data distribution D and generates an adversarial example x', which lies the data manifold (x' E supp(D)) and on which the current hypothesis f makes an error. Thus we can associate with this procedure an induced distribution D' on the error set of f, which is a result of the following process: x D, generate adversarial example x'.
One of the methods to perform on on-manifold adversarial training (as done in Stutz al. 2019 is to, first, learn class specific VAE-GAN and then when looking for adversarial examples, search for them in the latent space of the autoencoders.
Note that by construction (if the attacks are successful) supp(D") S supp(D)z*)) as adversarial examples are crucially constrained to being on the data manifold and they are points on which f makes errors. But there is also one important distinction. The distributions D' and Dr may be different. It is reasonable to assume that they are not too different in many applications and we will proceed under this assumption. With this caveat, the attacker in the on-manifold training procedure can be thought of as being the teacher in our EQ model. Under this assumption, Theorem guarantees that there exists an algorithm that learns faster than in the PAC model.
This is exactly what was experimentally found in Stutz et al. [2019) When on- on-manifold adversarial training was used the resulting classifier had lower standard error (generalized better) compared to the standard learning procedure.
Note. We can look at the results from Stutz al. 2019 from different perspective. They an experimental confirmation that Theorem I Tholds, as discussed in Section 3.3 also in situations where VC-theory doesn't 't describe learnability well. Indeed, for neural networks VC-dimension doesn't 'tt determine their learnability as in modern settings the number of parameters in networks is much bigger than the number of samples.

---

Note that Algorithm I is likely not the same as the algorithms that are used for training neural networks. One of the bigger differ- ences is that Algorithm ! uses majority vote-like classifier. But in a sim- ilar fashion can think of these experimental re- sults arguments that Theorem I holds for a broader class of learning al- gorithms.
8:00
Sard sa
Bard Dang
0.19
0133
6075
8:50
Humber sencko
(a) Standard risk
(b) On-manifold attack success rate
Figure 1: Comparison of standard training, adversarial training and
on-manifold adversarial training for F-MNIST dataset.
4.1 Experiments
For the convenience of the reader we replicate experiments from Stutz al. [201]]. adapting the representation to our needs. Using the code provided by the authors, we reproduced some of their findings on F-MNIST dataset (Xiao al. 2017 Results are presented in Figure D which reproduces some entries from Figure 5 in [Sutt et al. 2019). In Figure (a) we see that standard risk for on-manifold adversarial training lower for most settings of the number of samples than for normal training and standard adversarial training. This is consistent with Theorem I which states than in similar model there an improvement over the PAC-model, which corresponds here to the normal training. We will go back to Figure I (b) in Section 5 More details about the experiments is deferred to the appendix.
5 Adversarial robustness
Let us now discuss how our results can be seen through the lens of adversarial robustness. We start with brief review of previous approaches and the lessons we can draw from those.
The standard adversarial learning setup considered in the literature is as follows. There is classifier that an adversary A wants to attack. Having some type of access to f. A generates adversarial examples to f. To do so, first sample generated according to D. Then A tries to find x' such that and x' are semantically indistinguishable and f misclassifies x'. A formal definition of what "semantically indistinguishable" means difficult to furnish and it is thus the subject of considerably discussion. The reason for this difficulty is that we expect the machine learning model to learn what "semantically indistinguishable" means from the data and not to decide by ourselves up front. Many proxies for "semantically indistinguishable" were used in the literature. Usually they come the form of a restriction on the set of allowed perturbations. As we mentioned in the introduction, some of the most popular restrictions include bounds on the Lo, lg loo norm or restrictions to rotations, shifts and many others.
As argued in Tramer and Boneh [019 defenses often overfit to a particular set of allowed pertur- bations and the resulting classifiers remain basically undefended against other attacks. This result sparked interest in defenses that make models robust against wide variety of perturbations, even against unforeseen ones. A recent theoretical result [Goldwasser et al.) 2020 proposed a defense that make models robust against all possible perturbations. Unfortunately to achieve this the authors need to allow the learner not to give answers for some inputs and the learner sees the test set before computing the classifier.
As shown Bubeck et al.) 2019) and Tsipras et [209]] finding defenses might not be possible even in simple case of bounded perturbations, when the adversary is computationally all powerful. This means that limiting the capabilities of the attacker is very likely to be necessary. Different limitations on the model of attack and the power of the adversary were considered. Early papers limited the type access that A has to f: instead of full knowledge of (known as white-box model, see Biggio et al. (2013) Zheng et al. (2019)). black-box model [Bhambri et al.) 2019), partial white-box, where the adversary sees the logits the output probabilities but doesn't see the internal
nodes of network, oracle access to a gradient of f and others were considered. Unfortunately, even
7

---

in the most restrictive model, namely the black-bor box model, efficient attacks have been shown to exist
(Papernot al. 2017 Chen al. 2017 Liu et 2016 Xiao et al. 2018 Hayes and Danezis 2017). This lead the researches to explore models that limit the power of the adversary even further. In Gluch and Urbanke [2200] the authors consider a version of the black-box, where the attacker is limited by the number of evaluations of f it can perform. It is shown that classifiers with high entropy of decision boundaries are hard to attack. In Garg et al. [020) the authors consider an adversary that is
limited computationally. They show that there exist learning problems that can be attacked by an all powerful adversary but are secure against polynomially bounded attackers. These approaches however show security only for some synthetic distributions.
Summarizing this discussion we can formulate two conclusions
1. Introducing new attack models might be necessary for realizing adversarial robustness in the real world.
2. Limiting the power of the adversary is likely inevitable.
5.1 Model of attack
As argued in point | new attack models might be necessary. We introduce a definition of the adversary as an algorithm that has access to the function it wants to attack and also to the Example Query Oracle for distribution D and returns points from X. More formally:
Definition 2 (Adversary). For feature space X
define adversary A as algorithn (potentially randomized) that for every function f X + {-1,+1} and E X returns A(f, x) E X. Moreover, for distribution DD we denote by (f, EXp) distribution on X that is generated according to a process: sample x + EXD, return (f,x). For every f we say that A is restricted adversary for if:
A(f.EX, = EQ
Note. We define the adversary having access to the Example Query Oracle (EXp). This setting mimics the situation from Section where the adversary was constructing adversarial examples based on samples from the data distribution. Access EXD can be seen as a resource for the adversary that he can but doesn't tt have to use. Indeed, a priori there is no restriction on the relationship between samples from EXD and (f,, EXD). Thus could also assume that A doesn't 't have access to EXD but posses some approximate knowledge of DD that allows him to satisfy A(, EXx) EQD.
Finally, let us define the model of attack. It is an adversarial- learning--ie scheme where the learning algorithm uses the adversary to learn a more robust model.
Definition 3 (Adversarial learning game). For a distribution 'D on X, a learner L, and an adversary A we define an adversarial learning game as follows. Learner L interacts with A in rounds. In each round learner L sends function St to A and then A sends point Ię E X back to L. At every round A can query EX D once and use the result when generating T.. Decisions made by L at round t can depend on the messages exchanged before round t. For simplicity of the statements we assume that decisions of A don't 't depend on the history. At the end of the interaction L declares function f.
5.2 Interpretation of Theorem I for adversarial robustness
We now state a corollary of our main result. The proof is deferred to the appendix:
Corollary 1. For every feature space X, for every E (0, 1 ). every E N. every hypothesis class H on X of VC-dimension d there exists learning algorithm L such that for every distribution D. for every ground truth h E H. for every adversary A the following holds. When L interacts with A as described in Definition then with probability 2/3 at least one of the two properties holds:
. LL, after (d (dd-polyyog(1//) rounds of interaction with A, returns a function I such that (f) Se
there exists t [O(d- (nlylog(1/c))) such that the interaction round t a function fa was presented to A and ( EXp) + (f).
We use algorithu here since this seems more natural. But we do not limit the attacker computationally nor concerned with questions of computability. fience.function would be equally correct.
8

---

Moreover, throughout the interaction only O(polylog(1/e) functions are presented to A.
Next we explain how one can understand Corollary
The first point of view is that Corollary II explores implications on the existence of restricted adversaries. Interpreted as such, it shows that there exists an aelverssrilllleaminn---- scheme where restricted adversaries can be used to learn hypothesis of error exponentially faster than guaranteed by the standard learning theory results.
The second, and arguably the more interesting point of view is the following. If we assume that the adversary we want to defend against is unable to learn a classifier with error using D(d-polylog(1 (1)))og(//e)) samples from DD then the adversarial-leaming scheme from Corollary cean be understood is because throughout the execution of the protocol there was a function Sa that was presented to A such that (ft, EXD)) * FQD (ft). Thus the protocol generates list of ((polylog(1/e) many functions such that A is not a restricted adversary for at least one of them. We believe that this interpretation opens a door for designing defenses that are provably secure against adversaries that are limited by what they can learn. The results of experiments from Figure (bb) are consistent with our findings. The probability with which the on-manifold attacks succedes decreases faster than for normal training and standard adversarial training.
defense.
Why it makes sense to assume the learning problem is hard? As argued in point 2 above, limiting the power of the adversary is most likely unavoidable.
Imagine that the adversary you want protect your model against is a very good learner. More formally, assume that for distribution D and a ground truth h E H the adversary can compute a classifier g of very small risk RD, A (g) O. Then when the adversary attacks f it can compute [f & g] S X. Note that as the risk of is close to 0 we know that IP (=== # g(æ)] x RD.,()) that is the region [f A g] contains almost all errors of f. Even though A might not know the data distribution D (we only assumed that A is able to find classifier with low error, which doesn't 't necessarily imply the knowledge of the distribution) it is still able to attack f. To do that, for test example x ~ D, A can find x' E [f * 9] that is semantically closest to z. Then if the error set of f is semantically close to most of the data distribution then f is indefensible against all powerful learners.
Our result provides an exponential separation between sample/query complexities, as the standard PAC-bound requires O ( samples. This resembles the types of separation results, which cryptogra- phy is built and gives hope for following this line of research to find provably secure defenses. Unfortunately this separation doesn't 't happen for all distributions as the PAC guarantee is only an upper bound. We also know that VC-theory does not necessarily give tight bounds for distributions encountered in practice. We note however that, as discussed in Section 3.3 our result if understood as boosting technique can be applied to any learning algorithm and thus the implications not necessarily restricted to the VC-theory.
6 Conclusions and Open Problems
We study the interplay between adversarial training, generalization and robustness.
We start by proving an exponential separation between PAC and EQ-learning models. Then we show that our result provides theoretical justification of previous experimental findings that on-manifold adversarial training helps with generalization. Finally we explore the interpretation of our results for adversarial robustness. We introduce a learning setting where one can use the power of the adversary to evolve a learning scheme to become increasingly robust.
Our result does not yield a provable defense in real- world settings. But it provides a novel point of view on the adversarial robustness problem that hopefully, with further study, will provide such a S and g are different. It would be interesting
defense. As discussed the models considered in Section to prove version of exponential separation also in the setting from Section 4
Our result also poses some challenging technical questions. The query complexity upper-bound in the EQ-model we were able to prove is of the form O (d log (1/e)). This is most likely not optimal and what we believe to be the true query complexity O(d log()/))). Proving an upper or a power-bound close to this expression is an interesting theoretical challenge.

---

References
D. Angluin. Queries and concept learning. Mach. Learn., 2(4):319-342, Apr. 1988. ISSN 0885-6125. doi: 10.1023/A11022221188777 URL settps://doi.org////// 10221111111111112222222785
D. Angluin and T. Dohrn. The power of random counterexamples. In Hanneke and L. Reyzin, edi- tors, Proceedings of the 28th International Conference Algorithmic Learning Theory, volume 76 of Proceedings of Machine Learning Research, pages 452-465, Kyoto University, Kyoto, Japan, 15-17 Oct 2017. PMLR. htt.http://prrcceeeee
mlr wwwps//rs/e/eeeee attp////ngnuin11 html
S. Bhambri, Muku, S. Tulasi, and A. B. Buduru. study of black box adversarial attacks in computer vision. ArXiv, abs/1912.01667, 2019.
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šmndć P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In H. Blockeel, K. Kersting, S. Nijssen, and F. Zelezný, editors, Machine Learning and Knowledge Discovery in Databases, pages 387-402, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. ISBN 978-3-644-44994-33
N. H. Bshouty and D. Gavinsky. Pac=paexact and other equivalent models in learning. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 167-176, 2002. doi:
Bubeck, Y. Lee, E. Price, and Razenshteyn. Adversarial examples from computational constraints. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 831-840, Long Beach. California, USA, 09-15 Jun 2019. PMLR. URL mlr. http:////9//bubbb19e..aattae html
P.-Y. Chen, H. Zhang, Y. Sharma, J. Yi, and C.-J. Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AlSec '17, page 15-26, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781 9781450352024. doi: 10.1145/1288722314444 1ttt///tee////bboooo/////1111111
URL
J. Chu. Optimal decision functions for computer charateer recognition. ACM. 12(2):213-226 Apr. 1965. ISSN 0004-5411. doi: 10.1 10.1145/3212644321277 URL https://s://o...... http://to...og./////
321264. 321271
L. Engstrom, B. Tran, D. Tsipras, L. Schmidt, and A. Madry, A rotation and a translation suffice: Fooling CNNs with simple transformations, 2019. URL https://openreviin www.renrrriieeeene/fouuumm id=BJfvknCqFQ
S. Garg. S. Jha, S. Mahloujifar, and M. Mohammad. Adversarially robust learning could leverage computational hardness. In A. Kontorovich and G. Neu, editors, Proceedings of the 31st Inter- national Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 364-385, San Diego, California, USA, 08 Feb-11 Feb 2020. PMLR. URL http:://rooceddings http:/eeeddaaaamm...rreee//s/eee
mlr. wwwppppesssvi...eeeee 11 1ww.g///g...aaaaaa html
J. Gilmer, L. Metz, F. Faghri, S. S. Schoenholz, M. Raghu, M. Wattenberg, and I. Goodfellow. Adversarial spheres. In 6th International Conference Learning Representations, ICLR 2018, Vancouver. BC, Canada, April 30 May 3, 2018, Workshop Track Proceedings, 2018. URL https:///ppeneriev..ness wttp://wwww..eettooooioddddtaate
G. Gluch and R. L. Urbanke. Query complexity adversarial attacks. CoRR, abs/2010.01039, 2020. URL https: //tr//axvvvvvv/ wwwpsiiiv.rr/aaeoooo att./200...0....
S. Goldwasser, A. T. Kalai, Y. Kalai, and O. Montasser. Beyond perturbations: Learning guar- antees with arbitrary adversarial test examples. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https:
per.rrip...ccppppp///2000 /hash/ bbGG:444B372a00009556666222002 wwwp::swwo.obstttttttooo.oaaa... html
10

---

I. J. Goodfellow, J. Shlens, and C. Szegedy, Explaining and harnessing adversarial examples. 2014. URL
6572 cite arxiv:1412.6577
Hanneke. The optimal sample complexity of pac learning. Mach. Learn. Res., 17(1):1319-1333, Jan. 2016. ISSN 1532-4435.
J. Hayes and G. Danezis. Machine learning adversarial service: Learning black-box adversarial examples. 08 2017.
D. Kingma and Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Y. Liu, X. Chen, C. Liu, and D. Song. Delving into transferable adversarial examless and black-box attacks. CoRR, abs/161 /tt///111.220 .07770, 2016. URL UtL.http.//aara...rr//b///1111..
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. URL
https://openrevveer
N. Papernot, P. McDaniel, I. Goodfellow, S. Jha, Z. B. Celik, and A. Swami. Practical black-box attacks against machine learning- pages 106-519, 04 2017. doi: 10.1 00.1145/355293333330099
A. Raghunathan, Steinhardt, and Liang. Certified defenses against adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018. URL http:::/ /tttp:://openreviee net/ forum?id-Bys4ob-oi..
A. Rozsa, M. Günther, and T. E. Boult. Are accuracy and robustness correlated, In 2016 15th IEEE International Conference on Machine Learning and (IPCC (ICMLA), pages 227-232, 2016. doi: 10.1 N0.1109/CMMLA.2211.00000
R. E. Schapire. The strength of weak learnaillity. Mach. Learn., 5(2): July 1990. ISSN 0885- 6125. doi: 10. 10.3/23/ 11000//:111244800000000 1022448800760. https://::///o 1023//00010111110000 /020://000000/110022200000008000
Y. Song, R. Shu, N. Kushman, and S. Ermon. Constructing unrestricted adversarial examples with generative models. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnet,, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018 URL hhtpps: http://oooeeeinn.nnieeee / 0awaa599444effbbbb33322222222
Paper pdf
D. Stutz, M. Hein, and B. Schiele. Disentangling adversarial robustness and generalization. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society, 2019.
D. Su, H. Zhang, H. Chen, J. Yi, P.-Y. Chen, and Y. Gao. Is Robustness the Cost of Accuracy? - A Comprehensive Study the Robustness of 18 Deep Image Classification Models: 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XII, pages 644-661, 09 2018. ISBN 978-3-030-01257-1 doi: 10.1007/978-3-11 0-0000011588
T. Tanay and L. Griffin. A boundary tilting persepective the phenomenon of adversarial examples. 08 2016.
F. Tramer and D. Boneh. Adversarial training and robustness for multiple perturbations. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gamett, edi- tors, Advances in Neural Information Processing Systems, volume 32, pages 5866-5876. Cur- ran Associates, Inc., 2019. URL lhtpt::t////ptt htttps://proceedinggs neuri www.eeppp..pppppe//////./.. /o0p///e//219/filleee .pff
F. Tramèr, A. Kurakin, N. Papernot, I. Goodfellow, D. Bonch, and P. McDaniel. Ensemble adversarial training: Attacks and defenses. International Conference on Learning Representations, 2018.
URL http:://paaaneeerreeee////mmm22s
RZ
D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry. Robustness may be at odds
with accuracy. In International Conference on Learning Representations, 2019. URL. https

---

L. G. Valiant. A theory of the learnable. In Proceedings of the Sixteenth Anmual ACM Symposium on Theory of Computing, STOC 88, page 436-445 New York, NY, USA, 1984. Association for Computing Machinery. ISBN 089791 1334. doi: 10. 10.1145/800057.8888 808000 URL https
org/ 1145/800057 808710
E. Wong and J. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan. Stockholm, Sweden, July 10-15. 2018, pages 2283-5292, 2018. mlr URL http://proceedinng http://a......a///////////////o/ grress/v80xoong8aa html
C. Xiao, B. Li, J.-Y. Zhu, W. He, M. Liu, and D. Song. Generating adversarial examples with adversarial networks, 2018. URL hattps://openreviers wtw.://.eeeffoommmoeeem Hknbyy@C--bbbC---
H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
K. Y. Xiao, V. Tjeng, N. M. M. Shafiullah, and A. Madry. Training for faster adversarial robustness verification via inducing reL.U stability. In International Conference on Learning Representations, 2019. URL https:
Z. Zhao, D. Dua, and S. Singh. Generating natural adversarial examples. In International Conference on Learning Representations, 2018. URL https://openreevier nett/oormmidd-HBLLL
T. Zheng, C. Chen, and K. Ren. Distributionally adversarial attack. Proceedings of the AAAI Conference on Artificial Intelligence, 33:2253- 2260, 2019, doi: 030.0//anai..331.33300.3.0
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
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] Discussed mostly in Sections and 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our paper is of theoretical nature. Similar to the aim of PAC learning itself, we aim to develop theory of adversarial robustness. Our theoretical framework is not aimed at any particular application. But a better understanding of the limits of robustness will allow user make well-informed decision if automated system may or may be appropriate for a particular application.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you 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]
12

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material explained in Section 4.1 and Appendix B
URL)? [Yes] Details
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We use code provided in different work. We specify some the details in Appendix Further details are specified in Stutz et al. [2019].
(c) Did you report error bars (c.g.. with respect the random seed after running experi- ments multiple times)? [No] We used code provided in different work, where such emror bars
produced.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Explained in Appendix B
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] In Section
(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? [No]
We only included an appendix with proofs and explanation of experimental setup.
(d) 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": "zw7kgq4IOPP", "reviewer": "Reviewer_SBEU", "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.\n\nThe 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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\n\nOn 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.\n\nEdit: I thank the authors for their response but my opinion remains unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "rFUY9L32cTB", "reviewer": "Reviewer_mNRE", "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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nThe 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.\n\nIt 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. \n\nThe 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. \n\nThere are also some minor typos here and there. \n\n*after the rebuttal*\n\nThank 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am happy with the discussion that the authors have done in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "beKCraBIHuj", "reviewer": "Reviewer_X9Aw", "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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nI am a bit hesitant about the connection of this main result with the rest of the paper in Section 4 and 5. \nSpecifically, I do not see how Section 5 fits with the rest of the paper:\nThe 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?\n\nEven 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.   \n\nIn 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.  \n\nSome minor comments.\n- lines 282 and 283: the statement is not clear. Is it not possible computationally or statistically? \n- lines 371 and 372 are not accurate. There is no robustness guarantee presented in Section 5.\n---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nAfter Rebuttal.\nI 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)