Exponential Separation between Two Learning Models and Adversarial Robustness
Year: 2021

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 ✏ exponentially (in ✏) 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.

heading: 1 Introduction
text: 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 an exponential separation for the sample/query complexity of two learning models. This result provides a theoretical confirmation for the experimental observations in Stutz et al. [2019] and points to a fresh research direction in the field of adversarial robustness.
Let us start with a discussion of our main technical contribution. The first model we consider is the PAC-learning introduced in Valiant [1984]. In this model the learner is given i.i.d. samples from an unknown distribution and is tasked with finding a hypothesis with low generalization error. The second model is a version of Equivalence-Query-learning (EQ-learning) introduced in [Angluin, 1988]. In this setting samples are acquired through an interaction between a teacher and a 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 we study were considered previously in Angluin and Dohrn [2017] and Bshouty and Gavinsky [2002]. In this setting the counterexamples produced by the teacher come from the data distribution constrained to being in the error set of the presented hypothesis. We use ideas similar to those used in boosting techniques [Schapire, 1990] to prove that in the EQ-learning model O(d · polylog(1/✏)) queries suffices to achieve a standard error of ✏, where d 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/✏). We refer the reader to Section 3 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/✏). 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 and generalization. In [Tsipras et al., 2019, Su et al., 2018] it is argued that there is an inherent trade-off between robustness and accuracy whereas in Gilmer et al. [2018], Rozsa et al. [2016] the authors make the case that robustness improves with accuracy. This seeming contradiction is partially resolved in Stutz et al. [2019] where it is pointed out that it crucially 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 off-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, Tramèr et al., 2018, Xiao et 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 `0, `2, or `1 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 an answer for some inputs (selective learning [Chu, 1965]) and that they see the test set upfront (transductive learning), thus the capabilities of the learner are enhanced. We follow a 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 to 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 on 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.

heading: 2 Models of learning and attack
text: We start by defining the models of learning considered in this paper.
Notation. For i 2 N we define [i] := [1, 2, . . . , i]. We use log to denote the log to the base 2. For a function f ! { 1,+1} and A ✓ X we define f A as a function that is equal to f at X \A and flips the prediction for points in A. For a distribution D on X and A ✓ X we denote by D|A the conditional distribution that is equal (up to scaling) to D on A and 0 on the complement.
Throughout the paper we consider only the realizable version of learning. That is, we assume that there is a feature space X , a distribution D on X , a hypothesis class H and a function h 2 H, h : X ! { 1,+1}, that defines the ground truth on D. The learner knows X and H but neither knows h nor D. The goal of the learner is to find an f : X ! { 1,+1} that has small risk. The risk is defined as RD,h(f) := Px⇠D[f(x) 6= h(x)]. We will consider algorithms that have access to one of the following two oracles:
Example Query Oracle according to D (EXD). When queried, EXD returns (x, h(x)), where x ⇠ D.
Equivalence Query Oracle according to D (EQD) [Angluin, 1988]. For every f : X ! { 1,+1} (not necessarily from H) the result of querying EQD(f) is a counterexample to f dis-
tributed according to D. More formally it is x ⇠ D|f 6=h. If RD,h(f) = 0 then EQD(f) returns "YES" indicating that f is equivalent to h. For every k 2 N we write EQD(f, k) to denote an oracle that returns k i.i.d. samples, each generated by EQD(f).
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 H if for every ✏, 2 (0, 1) there exists m(✏, ) 2 N such that for every h 2 H and distribution D algorithm L(✏, ) asks m(✏, ) queries to the Example Query Oracle EXD and with probability 1 returns a function f 2 H such that RD,h(f)  ✏.
EQ-learning We say that a learning algorithm L EQ-learns H if for every ✏, 2 (0, 1) there exists m(✏, ) 2 N such that for every h 2 H and distribution D algorithm L(✏, ) asks m(✏, ) queries to the Equivalence Query Oracle EQD and with probability 1 returns a function f : X ! { 1,+1} such that RD,h(f)  ✏.

heading: 3 Exponential Separation
text: We start this section with a short literature review.
It is worth mentioning that there is a slight difference between EQ-learning model and the model from Angluin and Dohrn [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 a 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 to 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/!(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 ✏ in detail.
In Angluin and Dohrn [2017] it 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 need to find the hypothesis exactly (apart from other differences mentioned above). In Bshouty and Gavinsky [2002], where the model considered is closer to ours, it is shown that PAC-learnability =) PAE-learnability. A direct application of their technique in our setting yields an upper bound on the query complexity, which is no better than O(d/✏). No simple modification of this technique would yield the desired O(d · polylog(1/✏)) query complexity. We significantly extend the ideas from Bshouty and Gavinsky [2002] to obtain our result.

heading: 3.1 Main result
text: We are now ready to state the main result of the paper, which is an exponential separation for the sample complexity between PAC-learning and EQ-learning. Theorem 1. There exists a learning algorithm (Algorithm 1) such that for every ✏ 2
0, 132 , 2
(0, 1), every hypothesis class H of VC-dimension d, for every distribution D the algorithm invoked with parameters ✏, ,H EQ-learns H asking
O((d+ log(1/ )) log9(1/✏)) 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 a hypothesis class H of VC-dimension d in order to learn (with constant probability) a classifier of risk ✏ it suffices to use O d
✏
samples. This result is
tight in a sense that there exist hypothesis classes and distributions for which that many samples are necessary. Theorem 1 guarantees that in the EQ-learning model O(d · polylog(1/✏)) many queries suffice. This is an exponential improvement. Why is this possible?
Imagine that there is a ground truth g 2 H that you try to learn and that you already found h 2 H such that RD,g(h)  ⌘. Then the counterexample oracle EQD(h, ·) provides you with samples from a distribution D|h 6=g. Querying the oracle O(d) times you get a sample S EQD(h,O(d)). You
can now use the PAC bound: if you find an h0 2 H that is consistent with S then you know that it has an error of at most 1/2 on D|h 6=g . It is then natural to define
Combine(h, h0)(x) = ⇢ h(x), if x 2 h = g h 0(x), if x 2 h 6= g .
Note that Combine(h, h0) has an error of at most ⌘/2. If we repeated this procedure log(1/✏) times, thus asking O(d log(1/✏)) queries, you would find a classifier with error ✏.
Unfortunately it is not possible to compute Combine(h, h0). Afterall, if you knew the region of the input space where h 6= g then you could just flip the prediction of h 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 O(d) queries can indeed be achieved. The key to this result is to find a computable version of Combine(h, h0, ...) 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 LPAC 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 LEQ that learns H in the EQ-model to an error 1
!(poly(d)) in time poly(time(d)).
Let us apply this boosting technique to our setting. Assume that LPAC 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 LEQ that learns H to error ✏. What bound on the run time of LEQ do we get? Unfortunately this bound is no better than O d
✏
. 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 a different proof technique. The main idea is to compute h1, . . . , hO(polylog(1/✏)) 2 H in a sequential manner and then to define the final hypothesis as a version of a majority vote of these functions.
The simplified, high level, structure of the algorithm is as follows. Repeat the following for t = O(polylog(1/✏)) steps: at step i ask the oracle for Si EQD("Majority"(h1, . . . , hi 1), O(d)) and then define hi := FindConsistent(Si,H) (FindConsistent returns a function from H that agrees with all samples from Si). At the end return "Majority"(h1, . . . , ht). To make this approach work we need to ensure that the error sets of h1, . . . , ht 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 i we include in the training set Si 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-negligible 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 1).
We start now with the formal definition of the algorithm.

heading: 3.2 The Algorithm
text: 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 1 (Vote and Majority). For ✏ 2 (0, 1) we define B✏ := 2dlog(1/✏)e+1 and clip✏ : Z ! Z as:
clip ✏ (x) := min(max( B✏, x), B✏).
Algorithm 1 EQlearner Input: hypothesis class H of VC-dimension d, target error ✏, target confidence , Equivalence query oracle EQD.
✏ 0 := ✏105 log4(1/✏) B✏0 := 2dlog(1/✏0)e+ 1 m := O (d+ log(B4
✏0) + log(1/ )) ·B 4 ✏0
t := O B 3 ✏0 h1 2 H for i = 2 to t do Si := EQD(Maj(h1, . . . , hi 1),m) for v 2 [B✏0 ] \ 2Z+ 1 do h 0 := Maj(h1, . . . , hi 1) [Vote(h1, . . . , hi 1) 2 {v, v}]
S v i := EQD(h0,m)
end for hi := FindConsistent ⇣ Si [ S v2[B✏0 ] S v i ,H ⌘
end for
Return Maj(h1, h2, . . . , ht)
For a sequence of functions h1, . . . , hi : X ! { 1,+1}, ✏ 2 (0, 1) and x 2 X , we define Vote(h1, . . . , hi)(x) recursively as:
Vote(h1, . . . , hi)(x) :=
clip ✏ (Vote(h1, . . . , hi 1)(x) + 2hi(x)) ,
Vote(h1)(x) := h1(x).
Similarly, for a sequence of functions h1, . . . , hi : X ! { 1,+1}, ✏ 2 (0, 1) and a ground truth function g we define Voteg(h1, . . . , hi)(x) recursively as:
Voteg(h1, . . . , hi)(x) :=
clip ✏ ⇣ Vote(h1, . . . , hi 1)(x) + 2 · ( 1) hi(x)=g(x) ⌘ ,
Voteg(h1)(x) := ( 1) h1(x)=g(x).
Note. Vote(h1, . . . , hi)(x) expresses our current estimate for a particular input (together with a level of confidence), whereas Voteg(h1, . . . , hi)(x) denotes the error of this current estimate with respect to the ground truth.
Finally, we define:
Maj(h1, . . . , hi)(x) := ⇢ +1, if Vote(h1, . . . , hi)(x) 0, 1, otherwise.
Observation 1. Observe that for all i 2 N, h1, . . . , hi, g : X ! { 1,+1} and x 2 X we have: Vote(h1, . . . , hi)(x) 2 2Z+ 1 \ [ B✏, B✏] and Vote(h1, . . . , hi)(x) = ±Voteg(h1, . . . , hi)(x).

heading: 3.3 EQ-learner as a Booster
text: Guarantees based on the VC-dimension are often not tight and as our result is phrased in these terms one might wonder how much it depends on this specific measure. As mentioned, our algorithm can be understood as a boosting technique and hence the result applies more generally. Next, we explain what we mean by that.
Let H be a hypothesis class and D be a distribution. Imagine that we have an algorithm A that for some distributions learns H. What we mean is that A is a "PAC-learner" for H but only for a class of
distributions D. Then imagine that we use A as a subroutine in the EQ-learning algorithm. I.e., instead of following the template of S := EQD(f,m), h := FindConsistent(S,H) (as in Algorithm 1) we use A to get an h that has a small error on distribution EQD(f). Now assume that all distributions EQD(f) for which A is run belong to D.
In this case a slight extension of Theorem 1 shows that we can boost A in the following sense. Assume that for every ✏, 2 (0, 1), every D0 2 D A learns H on D0 in QA(H, ✏, ) number of samples. Then there exists an EQ-learner (this is Algorithm 1, which uses A as a subroutine) that learns H up to error ✏ in number of queries upper-bounded by QA ⇣ H, 1 16 , polylog(1/✏) ⌘ ·polylog(1/✏). Now observe that if QA (H, ✏, )
QA
⇣ H,
1 16 , polylog(1/✏)
⌘ polylog(1/✏), (1)
then the constructed EQ-learner learns H to error ✏ with fewer queries than A does in the PACmodel. This is a 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-model such that fewer queries are required. The condition from (1) in words means that the dependence of the runtime of A on ✏ grows faster than polylog(1/✏). This is a reasonable assumption as in the PAC-learning model for every hypothesis one needs ⌦(1/✏) samples just to see a single point from the error set of this hypothesis. This suggests that the dependence of QA (H, ✏, ) on ✏ might grow like ⌦(1/✏) (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.

heading: 4 On-manifold adversarial training aids generalization
text: As we mentioned in the introduction, the relationship between adversarial robustness and generalization has been the subject of a robust scientific discussion, no pun intended. We focus here on Stutz et al. [2019] and argue that our result can be interpreted as providing a theoretical confirmation of the important empiricial findings in this paper. As we will see, the setting of Stutz et al. [2019] is close but not identical to ours. But the parallels are strong.
In Stutz et al. [2019] a 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 x0, which lies on the data manifold (x0 2 supp(D)) and on which the current hypothesis f makes an error. Thus we can associate with this procedure an induced distribution D0 on the error set of f , which is a result of the following process: x ⇠ D, generate adversarial example x0.
One of the methods to perform on-manifold adversarial training (as done in Stutz et al. [2019]) is to, first, learn class specific VAE-GANs 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(D0) ✓ supp(Df 6=h), 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 D0 and Df 6=h 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 1 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-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 et al. [2019] from a different perspective. They are an experimental confirmation that Theorem 1 holds, as discussed in Section 3.3, also in situations where VC-theory doesn’t describe learnability well. Indeed, for neural networks VC-dimension doesn’t determine their learnability as in modern settings the number of parameters in networks is much bigger than the number of samples.
Note that Algorithm 1 is likely not the same as the algorithms that are used for training neural networks. One of the bigger differences is that Algorithm 1 uses a majority vote-like classifier. But in a similar fashion we can think of these experimental results as arguments that Theorem 1 holds for a broader class of learning algorithms.

heading: 4.1 Experiments
text: For the convenience of the reader we replicate experiments from Stutz et al. [2019], adapting the representation to our needs. Using the code provided by the authors, we reproduced some of their findings on F-MNIST dataset [Xiao et al., 2017]. Results are presented in Figure 1, which reproduces some entries from Figure 5 in Stutz et al. [2019]. In Figure 1 (a) we see that standard risk for on-manifold adversarial training is lower for most settings of the number of samples than for normal training and standard adversarial training. This is consistent with Theorem 1, which states than in a similar model there is an improvement over the PAC-model, which corresponds here to the normal training. We will go back to Figure 1 (b) in Section 5. More details about the experiments is deferred to the appendix.

heading: 5 Adversarial robustness
text: Let us now discuss how our results can be seen through the lens of adversarial robustness. We start with a 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 a classifier f that an adversary A wants to attack. Having some type of access to f , A generates adversarial examples to f . To do so, first a sample x is generated according to x ⇠ D. Then A tries to find x 0 such that x and x0 are semantically indistinguishable and f misclassifies x0. A formal definition of what "semantically indistinguishable" means is 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 it by ourselves up front. Many proxies for "semantically indistinguishable" were used in the literature. Usually they come in 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 `0, `2, `1 norm or restrictions to rotations, shifts and many others.
As argued in Tramer and Boneh [2019] defenses often overfit to a particular set of allowed perturbations and the resulting classifiers remain basically undefended against other attacks. This result sparked interest in defenses that make models robust against a 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 in Bubeck et al. [2019] and Tsipras et al. [2019] finding defenses might not be possible even in a simple case of `2-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 of access that A has to f : instead of full knowledge of f (known as white-box model, see Biggio et al. [2013], Zheng et al. [2019]), a black-box model [Bhambri et al., 2019], partial white-box, where the adversary sees the logits of the output probabilities but doesn’t see the internal nodes of a network, oracle access to a gradient of f and others were considered. Unfortunately, even
in the most restrictive model, namely the black-box model, efficient attacks have been shown to exist [Papernot et al., 2017, Chen et al., 2017, Liu et al., 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 [2020] 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. [2020] 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.

heading: 5.1 Model of attack
text: As argued in point 1 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 a feature space X we define an adversary A as an algorithm1 (potentially randomized) that for every function f : X ! { 1,+1} and x 2 X returns A(f, x) 2 X . Moreover, for a distribution D, we denote by A(f,EXD) a distribution on X that is generated according to a process: sample x EXD, return A(f, x). For every f we say that A is a restricted adversary for f if:
A(f,EXD) = EQD.
Note. We define the adversary as having access to the Example Query Oracle (EXD). This setting mimics the situation from Section 4 where the adversary was constructing adversarial examples based on samples from the data distribution. Access to EXD can be seen as a resource for the adversary that he can but doesn’t have to use. Indeed, a priori there is no restriction on the relationship between samples from EXD and A(f,EXD). Thus we could also assume that A doesn’t have access to EXD but posses some approximate knowledge of D that allows him to satisfy A(f,EXD) = EQD.
Finally, let us define the model of attack. It is an adversarial-learning-like 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 t learner L sends a function ft to A and then A sends a point xt 2 X back to L. At every round A can query EXD once and use the result when generating xt. 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 depend on the history. At the end of the interaction L declares a function f .

heading: 5.2 Interpretation of Theorem 1 for adversarial robustness
text: 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 ✏ 2
0, 132 , for every d 2 N, for every hypothesis
class H on X of VC-dimension d there exists a learning algorithm L such that for every distribution

heading: D, for every ground truth h 2 H, for every adversary A the following holds. When L interacts with
text: A as described in Definition 3 then with probability 2/3 at least one of the two properties holds:
• L, after O(d · polylog(1/✏)) rounds of interaction with A, returns a function f such that RD,h(f)  ✏,
• there exists t 2 [O(d · polylog(1/✏))] such that at the interaction round t a function ft was presented to A and A(ft, EXD) 6= EQD(ft).
1We use algorithm here since this seems more natural. But we do not limit the attacker computationally nor are we concerned with questions of computability. Hence, function would be equally correct.
Moreover, throughout the interaction only O(polylog(1/✏)) different functions are presented to A.
Next we explain how one can understand Corollary 1.
The first point of view is that Corollary 1 explores implications on the existence of restricted adversaries. Interpreted as such, it shows that there exists an adversarial-learning-like scheme where restricted adversaries can be used to learn a 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 O(d·polylog(1/✏)) samples from D then the adversarial-learning scheme from Corollary 1 can be understood as a defense. It is because throughout the execution of the protocol there was a function ft that was presented to A such that A(ft, EXD) 6= EQD(ft). Thus the protocol generates a list of O(polylog(1/✏)) 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 1 (b) are consistent with our findings. The probability with which the on-manifold attacks succedes decreases faster than for normal training and standard adversarial training.
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 to protect your model against is a very good learner. More formally, assume that for a distribution D and a ground truth h 2 H the adversary can compute a classifier g of very small risk RD,h(g) ⇡ 0. Then when the adversary attacks f it can compute [f 6= g] ✓ X . Note that as the risk of g is close to 0 we know that Px⇠D[f(x) 6= g(x)] ⇡ RD,h(f), that is the region [f 6= 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 a classifier with low error, which doesn’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 x0 2 [f 6= g] that is semantically closest to x. 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 d
✏
samples. This resembles the types of separation results, which cryptogra-
phy is built on and gives hope for following this line of research to find provably secure defenses. Unfortunately this separation doesn’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 a boosting technique can be applied to any learning algorithm and thus the implications are not necessarily restricted to the VC-theory.

heading: 6 Conclusions and Open Problems
text: 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 a 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 defense. As discussed the models considered in Section 3 and 4 are different. It would be interesting to prove a 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 · log9 (1/✏) . This is most likely not
optimal and what we believe to be the true query complexity is O(d · log(1/✏)). Proving an upper or a lower-bound close to this expression is an interesting theoretical challenge.

Review summaries:
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. 

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. 

The paper studies the query complexity of learning a VC class under a certain query model called the Equivalence-Query (EQ) model by Angluin'98. In this model, given a distribution $\mathcal{D}$ and the ground truth $g$, the learner interacts with the data in the following way: (1) learner selects a function f and (2) learner receives a random counter-example distributed according to $\mathcal{D}$, that is, a random draw from $\mathcal{D}|_{f \ne g}$. Under this model, the authors prove an exponentially improved upper bound of $d \cdot \mathsf{polylog}(1/\epsilon)$ compared to the $d/\epsilon$ bound for PAC learning. The paper further draws connections between this model of learning and adversarial robustness. The main argument here relies on viewing the equivalence-query sample oracle as the adversary restricted to on-manifold attacks.

The main result of the paper is showing a separation between the sample complexity of PAC model and the query complexity of an interactive model called Equivalence-Query-learning. The interactive model requires exponentially fewer queries/samples (in the mistake parameter - epsilon). Further, the implication of this result on the adversarial robustness is discussed. 

This paper introduces a new abstract learning model called the EQ-learning, in which the oracle returns examples that the current classifier gets incorrect (rather than arbitrary examples drawn from the data distribution) and returns YES if no such examples exist (indicating the current classifier is correct). They then provide an algorithm which achieves a sample complexity (assuming finite VC dimension d)that is polylog in $1/\epsilon$ as opposed to $O(1/\epsilon)$. This is an exponential increase, and is a very interesting theoretical result on its own.  They then argue how their formalism plays a role in learning from on-manifold adversarial examples. In particular, each of these examples reveals a point that the classifier gets incorrect, and their result consequently suggests that learning from these results should improve the training procedure.