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. 
abstractText: 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.
authors.name: Grzegorz Głuch
authors.name: Ruediger Urbanke
references.authors: D. Angluin
references.title: Queries and concept learning
references.venue: ISSN 0885-6125. doi: 10.1023/A:1022821128753. URL https://doi.org/10.1023/A:1022821128753
references.authors: D. Angluin T. Dohrn
references.title: The power of random counterexamples
references.venue: Proceedings of the 28th International Conference on Algorithmic Learning Theory,
references.authors: S. Bhambri S. Muku A.S. Tulasi A.B. Buduru
references.title: A study of black box adversarial attacks in computer
references.venue: vision. ArXiv,
references.authors: B. Biggio I. Corona D. Maiorca B. Nelson N. Šrndić P. Laskov G. Giacinto F. Roli
references.title: Evasion attacks against machine learning at test time
references.venue: Machine Learning and Knowledge Discovery in Databases,
references.authors: N.H. Bshouty D. Gavinsky
references.title: Pac=paexact and other equivalent models in learning
references.venue: In The 43rd Annual IEEE Symposium on Foundations of Computer Science,
references.authors: S. Bubeck Y.T. Lee E. Price I. Razenshteyn
references.title: Adversarial examples from computational constraints
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: P.-Y. Chen H. Zhang Y. Sharma J. Yi C.-J. Hsieh
references.title: Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models
references.venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec
references.authors: J.T. Chu
references.title: Optimal decision functions for computer character recognition
references.venue: J. ACM,
references.authors: L. Engstrom B. Tran D. Tsipras L. Schmidt A. Madry
references.title: A rotation and a translation suffice: Fooling CNNs with simple transformations, 2019
references.venue: URL https://openreview.net/forum? id=BJfvknCqFQ
references.authors: S. Garg S. Jha S. Mahloujifar M. Mohammad
references.title: Adversarially robust learning could leverage computational hardness
references.venue: Proceedings of the 31st International Conference on Algorithmic Learning Theory,
references.authors: J. Gilmer L. Metz F. Faghri S.S. Schoenholz M. Raghu M. Wattenberg I.J. Goodfellow
references.title: Adversarial spheres
references.venue: In 6th International Conference on Learning Representations,
references.authors: G. Gluch R.L. Urbanke
references.title: Query complexity of adversarial attacks
references.venue: CoRR, abs/2010.01039,
references.authors: I.J. Goodfellow J. Shlens C. Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: URL http://arxiv.org/abs/1412.6572. cite arxiv:1412.6572
references.authors: S. Hanneke
references.title: The optimal sample complexity of pac learning
references.venue: J. Mach. Learn. Res.,
references.authors: J. Hayes G. Danezis
references.title: Machine learning as an adversarial service: Learning black-box adversarial examples
references.authors: D. Kingma J. Ba
references.title: Adam: A method for stochastic optimization
references.venue: International Conference on Learning Representations,
references.authors: Y. Liu X. Chen C. Liu D. Song
references.title: Delving into transferable adversarial examples and black-box attacks
references.venue: CoRR, abs/1611.02770,
references.authors: A. Madry A. Makelov L. Schmidt D. Tsipras A. Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: In International Conference on Learning Representations,
references.authors: N. Papernot P. McDaniel I. Goodfellow S. Jha Z.B. Celik A. Swami
references.title: Practical black-box attacks against machine learning
references.authors: A. Rozsa M. Günther T.E. Boult
references.title: Are accuracy and robustness correlated
references.venue: In 2016 15th IEEE International Conference on Machine Learning and Applications (ICMLA),
references.authors: R.E. Schapire
references.title: The strength of weak learnability
references.venue: Mach. Learn.,
references.authors: Y. Song R. Shu N. Kushman S. Ermon
references.title: Constructing unrestricted adversarial examples with generative models
references.venue: Advances in Neural Information Processing Systems,
references.authors: D. Stutz M. Hein B. Schiele
references.title: Disentangling adversarial robustness and generalization
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society,
references.authors: F. Tramer D. Boneh
references.title: Adversarial training and robustness for multiple perturbations
references.venue: Advances in Neural Information Processing Systems,
references.authors: F. Tramèr A. Kurakin N. Papernot I. Goodfellow D. Boneh P. McDaniel
references.title: Ensemble adversarial training: Attacks and defenses
references.venue: In International Conference on Learning Representations,
references.authors: D. Tsipras S. Santurkar L. Engstrom A. Turner A. Madry
references.title: Robustness may be at odds with accuracy
references.venue: In International Conference on Learning Representations,
references.authors: L.G. Valiant
references.title: A theory of the learnable
references.venue: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing,
references.authors: E. Wong J.Z. Kolter
references.title: Provable defenses against adversarial examples via the convex outer adversarial polytope
references.venue: In Proceedings of the 35th International Conference on Machine Learning,
references.authors: C. Xiao B. Li J.-Y. Zhu W. He M. Liu D. Song
references.title: Generating adversarial examples with adversarial networks, 2018
references.venue: URL https://openreview.net/forum?id=HknbyQbC-
references.authors: H. Xiao K. Rasul R. Vollgraf
references.title: Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017
references.authors: K.Y. Xiao V. Tjeng N.M.M. Shafiullah A. Madry
references.title: Training for faster adversarial robustness verification via inducing reLU stability
references.venue: In International Conference on Learning Representations,
references.authors: Z. Zhao D. Dua S. Singh
references.title: Generating natural adversarial examples
references.venue: In International Conference on Learning Representations,
references.authors: T. Zheng C. Chen K. Ren
references.title: Distributionally adversarial attack
references.venue: Proceedings of the AAAI Conference on Artificial Intelligence, 33:2253–2260,
references.authors: Stutz
references.title: Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No] We used code provided in different work, where such error bars are not produced. (d) Did you include the total amount of compute and the type of resources used (e.g., type
sections.heading: 1 Introduction
sections.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.
sections.heading: 2 Models of learning and attack
sections.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)  ✏.
sections.heading: 3 Exponential Separation
sections.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.
sections.heading: 3.1 Main result
sections.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.
sections.heading: 3.2 The Algorithm
sections.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).
sections.heading: 3.3 EQ-learner as a Booster
sections.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.
sections.heading: 4 On-manifold adversarial training aids generalization
sections.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.
sections.heading: 4.1 Experiments
sections.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.
sections.heading: 5 Adversarial robustness
sections.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.
sections.heading: 5.1 Model of attack
sections.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 .
sections.heading: 5.2 Interpretation of Theorem 1 for adversarial robustness
sections.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
sections.heading: D, for every ground truth h 2 H, for every adversary A the following holds. When L interacts with
sections.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.
sections.heading: 6 Conclusions and Open Problems
sections.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.
title: Exponential Separation between Two Learning Models and Adversarial Robustness