When are Local Queries Useful for Robust Learning?
Authors: Pascale Gourdeau
Varun Kanade
Marta Kwiatkowska
James Worrell
Venue: NeurIPS 2022 Accept (2022)
Keywords: Learning Theory
Robustness
Classification

Abstract: Distributional assumptions have been shown to be necessary for the robust learnability of concept classes when considering the exact-in-the-ball robust risk and access to random examples by Gourdeau et al. (2019). In this paper, we study learning models where the learner is given more power through the use of local queries, and give the first distribution-free algorithms that perform robust empirical risk minimization (ERM) for this notion of robustness. The first learning model we consider uses local membership queries (LMQ), where the learner can query the label of points near the training sample. We show that, under the uniform distribution, LMQs do not increase the robustness threshold of conjunctions and any superclass, e.g., decision lists and halfspaces. Faced with this negative result, we introduce the local equivalence query (LEQ) oracle, which returns whether the hypothesis and target concept agree in the perturbation region around a point in the training sample, as well as a counterexample if it exists. We show a separation result: on one hand, if the query radius $\lambda$ is strictly smaller than the adversary's perturbation budget $\rho$, then distribution-free robust learning is impossible for a wide variety of concept classes; on the other hand, the setting $\lambda=\rho$ allows us to develop robust ERM algorithms. We then bound the query complexity of these algorithms based on online learning guarantees and further improve these bounds for the special case of conjunctions. We finish by giving robust learning algorithms for halfspaces with margins on both $\{0,1\}^n$ and $\mathbb{R}^n$.

When are Local Queries Useful for Robust Learning?
Pascale Gourdeau University Oxford
Varun Kanade University of Oxford varunkēcs. ac. uk
pascale gourdeaudss ox uuk
Marta Kwiatkowska
James Worrell University of Oxford woresl.orrellee. ox. uk
University of Oxford
Marta.wwatkosee ac. uk
Abstract
Distributional assumptions have been shown to be necessary for the robust learn- ability of concept classes when considering the exact-in-the-ball robust risk and access to random examples by Gourdeau et al. (2019). In this paper, we study learning models where the learner is given more power through the use of local queries, and give the first distribution-free algorithms that perform robust empirical risk minimization (ERM) for this notion of robustness. The first learning model we consider uses local membership queries (LMQ), where the learner can query the label of points near the training sample. We show that, under the uniform distribution, LMQs do not increase the robustness threshold of conjunctions and any superclass, e.g., decision lists and halfspaces. Faced with this negative result, we introduce the local equivalence query (LEQ) oracle, which returns whether the hypothesis and target concept agree in the perturbation region around a point the training sample, well as a counterexample if it exists. We show separation result: on one hand, if the query radius À is strictly smaller than the adversary' s perturbation budget p. then distribution-free robust learning is impossible for wide variety of concept classes; on the other hand, the setting = p allows us to develop robust ERM algorithms. We then bound the query complexity of these algorithms based on online learning guarantees and further improve these bounds for the special case of conjunctions. We finish by giving robust learning algorithms for halfspaces with margins on both {0, 1}" and R..
Introduction
Adversarial examples have been widely studied since the work of (Dalvi al. 2004 Lowd and
Meek] 2005a b). and later (Biggio et al. 2013, Szegedy et al. 2013). the latter having coined the term. As presented Biggio and Roli (2017). main settings exist for adversarial machine learning: evasion attacks, where an adversary perturbs data at test time, and poisoning attacks, where the data modified at training time.
The majority of the guarantees and impossibility results for evasion attacks are based on the existence of adversarial examples, potentially crafted by all-powerful adversary. However, what is considered to be an adversarial example has been defined in two different, and in some respects contradictory. ways in the literature. The exact-in-the-bal notion of robustness (also known error region risk in Diochnos et al. (2018) requires that the hypothesis and the ground truth agree in the perturbation region around each test point; the ground truth must thus be specified on all input points in the perturbation region. On the other hand, the constant-in-the ball notion of robustness (which is also known as corrupted input robustness from the work of Feige et al. (2015)) requires that the unperturbed point be correctly classified and that the points in the perturbation region share its label,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

meaning that we only need access to the test point labels; see, e.g., @Dochhoss et al., 2018 Dreossi et 2019 Gourdeau et al. 202T Pydi and Jog 202T) for thorough discussions on the subject.
We study the problem of robust classification against evasion attacks under the exact-in-the-be definition of robustness. Previous work for this problem, e.g., (Diochnos et al. 2020 Gourdeau et al. 202T). has considered the setting where the learner only has access to random examples. However, many defences against evasion attacks have used adversarial training, the practice by which a dataset is augmented with previously misclassified points. Moreover, in the learning theory literature, some learning models give more power to the learner, e-g., by using membership and equivalence queries. Our work studies the robust learning problem mentioned above from learning theory point of view, and investigates the power of local queries in this setting.
1.1 Our Contributions
We outline our contributions below. All our results use the exact-in-the-ball definition of robustness. Conceptually, we study the powers and limitations of robust learning with access oracles that only reveal information nearby the training sample. Our results are particularly relevant as they contrast with the impossibility of robust learning in the distribution-free setting when only random examples are given, as demonstrated in Gourdeau et al. (201))
Limitations of the Local Membership Query Model. In the local membership query (LMQ) model, the learner is allowed to query the label of points in the vicinity of the training sample. This model was introduced by Awasthi et al. (2013) and shown to guarantee the PAC learnability of various concept classes (which are believed or known to be hard to learn with only random examples) under distributional assumptions. However, we show that LMQs do not improve the robustness threshold of the class of conjunctions under the uniform distribution. Indeed, any p-robust learning algorithm will need a joint sample and query complexity that is exponential in p. and thus superpolynomial in the input dimension n against an adversary that can flip p = w wlog n2) input bits at test time.
The Local Equivalence Query Model. Faced with the query lower bound for LMQ above, one may consider giving a different power to the learner to improve robust learning guarantees. We thus introduce the local equivalence query (LEQ) model, where the learner is allowed to query whether hypothesis and the ground truth agree in the vicinity of points in the training sample. The LEQ oracle is the natural exact-in-the-ball analogue of the Perfect Attack Oracle introduced in Montasser let al. (2021), which was developed for the constant-in-the-bee robustness. It is also a variant of the equivalence query oracle introduced by Ang luin (1987).
Distribution-Free Robust ERM with an LEQ Oracle. We show that having access to robustly consistent learner (i.e., one that can get zero robust risk on the training sample) gives sample complexity upper bounds that are logarithmic in the size of the hypothesis class or linear in its robust VC dimension-a complexity measure adapted from Cullina et al. (018) for our notion of robustness, which we present in this paper. We study the setting where the learner has access to random examples and an LEQ oracle. In the case where the query radius X of the LEQ oracle is strictly smaller than the adversarial perturbation budget p. show that, for wide variety of concept classes, distribution-free robust learning is impossible, regardless of the training sample size. In contrast, when = P we exhibit robustly consistent learners that use an LEQ oracle. This separation result further validates the need for an LEQ oracle in the distribution- setting. We furthermore use online learning setting results to exhibit upper bounds the LEQ oracle query complexity and then improve these bounds in the specific case of conjunctions. Finally, we study the sample and query complexity of halfspaces on both (0, 1)" and R" To our knowledge, the results presented in this paper feature the first robust empirical risk minimization (ERM) algorithms for the exact-in-the-bal robust risk in the literature []
1.2 Related Work
Learning with Membership and Equivalence Queries. Membership and equivalence queries (MQ and EQ, respectively) have been widely used in learning theory. Membership queries allow the
Note that previous work, e.g.. Gourdeau et al. 2021 used PAC learning algorithms as black boxes, which are not in general robust risk minimizers, unless they also happen to be exact learning algorithms, and that Montasser et al. 2019 2021 use the constant-in- in-the-ball definition of robustness.

---

learner to query the label of any point in the input space A', namely, if the target concept is c, MQ returns c(z) when queried with x X. The goal is usually to learn the target e exactly, Recall that, in the probabilistically approximately correct (PAC) learning model of Valiant 1984). the learner has access to the example oracle (X(e, D). which upon being queried returns a point x ~ D sampled from the underlying distribution and its label c(r), and the goal is to output h such that with high probability / has low error P The EQ oracle takes as input a hypothesis and returns whether = C. and provides a counterexample such that h(z) A c(z) otherwise. The seminal work of Angluin (197)) showed that deterministic finite automata (DFA) are exactly learnable with a polynomial number of queries to MQ and EQ in the size of the DFA. Many classes were then showed to be learnable in this setting as well as others, see e.g.. (Bshouty 1993 Angluin 1988 Dackson 1997).
Moreover, the MQ EQ model has recently been used for recurrent and binarized neural networks
(Weiss et al. 2018 1 2019 Okudono et al.] 2020 Shih et al. 2019). and interpretability (Camacho and Mcllraith] 2019). But even these powerful learning models have limitations: learning DFAs only with EQ is hard (Angluin 1990) and, under cryptographic assumptions, they are also hard to learn solely with the MQ oracle (Angluin and Kharitonov (995). It is also worth noting that the MQ learning model has been criticized by the applied machine learning community, as labels can be queried in the whole input space, irrespective of the distribution that generates the data. In particular, (Baum and Lang 1992) observed that query points generated by a learning algorithm on the handwritten characters oftentimes appeared meaningless human labellers. Awasthi al. (013)) thus offered an alternative learning model to Valiant's ' original model, the PAC and local membership query (EX- + LMQ) model, where the learning algorithm is only allowed to query the label of points that are close to examples from the training sample. Baar- Weisherg et al. (2020) later showed that
many concept classes, including DFAs, remain hard to learn in the EX + LMQ model.
Existence of Adversarial Examples. has been shown that, in many instances, the vulnerability of learning models to adversarial examples is inevitable due to the nature of the learning problem. The majority of the results have been shown for the constant-in- iettaant--ithe--tte thal notion of robustness, see
e.g., (Fawzi et al. 2016 2018a b Gilmer et al. 2018 Shafahi et al., 2018 Tsipra et al. 2019). As for the exact-in-thee ball definition of robustness, Diochnos et al. (2018) consider the robustness of monotone conjunctions under the uniform distribution. Using the isoperimetric inequality for the boolean hypercube, they show that an adversary that can perturb O(yn) bits can increase the misclassification error from 0.01 to 1/2. Mahloujifar et al. (2019) then generalize this result to Normal Lévy families and a class of behl-behaved classification problems (i.e., ones where the error regions are measurable and average distances exist).
Sample Complexity of Robust Learning. Our work uses similar approach to Cullina al. (2018), who define the notion of adversarial VC dimension to derive sample complexity upper bounds for robust ERM algorithms, with respect to the constant-in-the-bal robust risk. |Mnntasser al. (201)) use the same notion of robustness and show sample complexity upper bounds for robust ERM algorithms that are polynomial in the VC and dual VC dimensions of concept classes, giving general upper bounds that are exponential in the VC dimension-though they sometimes must be achieved by an improper learner. [Ashtiani et al. 2020) build on their work and delineate when proper robust learning is possible. On the other hand, (Khim et al., 2019 Yin et al. 2019 Awasthi et al. 2020) study adversarial Rademacher complexity bounds for robust learning, giving results for linear classifiers and neural networks when the robust risk can be minimized (in practice, this is approximated with adversarial training). VVallard et al. (202T) derive PAC-Bayesian generalization bounds for the averaged risk on the perturbations, rather than working in a worst-case scenario. As for the exact-in-the-bal definition of robustness, Diochnos et al.) (2020) show that, for a wide family of concept classes, any learning algorithm that is robust against all p o(n) attacks must have a sample complexity that is at least an exponential in the input dimension n. They also show a superpolynomial lower bound in case p @(VR), Gourdeau et al. (211)) show that distribution-free robust learning is generally impossible. They also show that monotone conjunctions have a robustness threshold of (log n) under Lipschitt distributions. meaning that this class is efficiently robustly learnable against an adversary that can perturb log n bits of the input, but an adversary is allowed to perturb p w(oo n.) bits of the input, there does not exist a sample-efficient learning algorithm for this problem. (Gurreau et al. (2021) extended this result to the class of monotone decision lists
Viallard
"This is known as the realizable setting, It is also possible to have a distribution over the labels, in which case we are working in the agnostic setting.
3

---

and Gourdeau et al. (2022) showed sample complexity lower bound for monotone conjunctions that is exponential p and that the robustness threshold of decision lists is also (log n)). Finally, Diakonikolas et al. (2020) and [Bhattacharjee et al. (2021) have used online learning algorithms for robust learning with respect to the constant-in-ther ball notion of robustness.
Restricting the Power of the Learner and the Adversary. Most adversarial learning guarantees and impossibility results in the literature have focused on all-powerful adversaries. Recent work has studied learning problems where the adversary's 's power is curtailed. E.g. MMhlluuifaar and Mahmoody (2019) and Garg al. (2000) study the robustness of classifiers to polynomial-time attacks. Closest to our work. Montasser et al. 2020, 202T) study the sample and query complexity of robust learning with respect the constant-in -n-the-balll robust risk when the learner has access to a Perfect Attack Oracle (PAO). For a perturbation type U : X - 2*, hypothesis h and labelled point (z, y), the PAO returns the constant-ing ceestant-in-the-eeee in-the-ball robust loss of h in the perturbation region (zx) and a counterexample where h22) # if it exists. Our LEQ oracle is the natural analogue of the PAO oracle for our notion of robustness. In the constant-in-the-te show sample and query complexity bounds that are linear and quadratic in the Littlestone dimension of concept classes, respectively (Montasser et al. 2020). Montasser et al. (202T moreover use the
realizable setting the authors use online learning results to
algorithm from (Montasser et al. 2019) to get sample complexity of Ô VCC
and query complexity of ((2VC (Re)² log" (VC* (t0))it))))) Finally, they extend their results to the agnostic setting and derive lower bounds. As in the setting with having only access to the examplc oracle. different notions of robustness have vastly different implications in terms of robust learnability of certain concept classes. Whenever relevant, we will draw a thorough comparison in the next sections between our work and that of Montasser et al. 20211
2 Problem Set Up
We work in the PAC learning framework (see Appendix A.I with the distinction that robust risk function is used instead of the standard risk. We will study metric spaces (Kn, d) of input dimension n with a perturbation budget function p : + R defining the perturbation region Bx(x):= = (z E Xx d(x, 2) S p(n)}. When the input space is the boolean hypercube Xx = (0, 1)". the metric is the Hamming distance.
We use the exact-in-the-ball robust risk, which is defined w.r.t. a hypothesis h, target and dis- tribution D the probability RD (h, = Pr (3z E B,(x) (()=) A h(=)) that h and e disagree =nD in the perturbation region. On the other hand, the constant-in intt-iin-tth in-the-ball robust risk is defined as Pr (3x E (+) c(x) & l((z). Note that it is possible to adapt the latter to a joint distribution on a>D
the input and label spaces, but that there is an implicit realizability assumption in the former as the prediction perturbed points' labels are compared to the ground truth c. We emphasize that choosing a robust risk function should depend on the learning problem at hand. The constant-in -etttti---tt-alll-e-e notion of robustness requires certain form of stability: the hypothesis should be correct example and not change label in the perturbation region; this robust risk function may be more appropriate in settings with strong margin assumption. In contrast, the exact-in-the-baat notion of robustness speaks to the fidelity of the hypothesis to the ground truth, and may be more suitable when considerable portion of the probability mass is in the vicinity of the decision boundary. Diochnos et al. 8); Dreossi et al. (2119; Gourdeau et al. (20TT) Pydi and Jog (202T) offer a thorough comparison between different notions of robustness.
random
In the face of the impossibility or hardness of robustly learning certain concept classes, either through statistical computational limitations, it is natural to study whether these issues can be circumvented by giving more power to the learner. The X-local membership query (A-LMQ) set up of Awasthi et al. (2013), which is formally defined in Appendix A.3] allows the learner query the label of points that are at distance at most À from a sample 5 drawn randomly from D. Inspired by this learning model, we define the X-local equivalence query (X-LEQ) model where, for a point in sample S drawn from the underlying distribution D, the learner is allowed to query an oracle that returns
Le.., there exists hypothesis that has zero constant in ball robust loss.

---

whether h agrees with the ground truth in the ball (x of radius À around If they disagree, counterexample in Bx (z) returned as well. Clearly, by setting À = n, we recover the EQ oracle Note moreover that when À p. this is equivalent to querying the (exact-in-the-bart around a point. We will show a separation result for robust learning algorithms between models that only allow random examples and ones that allow random examples and access to LEQ.
robust loss
Definition 1 (A-LEQ Robust Learning). Lel Xn be the instance space, C a concept class over Xn, and D class of distributions over Xn. We say that C is p-robustly learnable using X-local equivalence queries with respect to distribution class, DD if there exists a learning algorithm, A, such that for everv E > 0, 6 > 0, for every distribution D E and every target concept e E C. the following hold
1. A draws a sample of size m. polplnl 1/6, using the example oracle EX(c, D)
2. Each query made by A at x E S and for candidate hypothesis h X-LEQ either confirms that e and h coincide on (x)x) or returns 2 E Bx(x) such that c(z) # l(z)). A is allowed update h after seeing a counterexample
3. A outputs hypothesis h that satisfies R. (h,c) e probability at least 1 5
4. The running time of A (hence also the number of oracle accesses) polynomial in n, 1/c, 1/8 and the output hypothesis h is polynomially evaluable.
We remark that this model evokes the online learning setting, where the learner receives counterex- amples after making prediction, but with a few key differences. Contrary to the online setting (and the exact learning framework with MQ and EQ), there is an underlying distribution with which the performance of the hypothesis is evaluated in both the LMQ and LEQ models. Morcover, in online learning, when receiving a counterexample. the only requirement is that there is concept that correctly classifies all the data given to the learner up until that point, and so the counterexamples can be given in an adversarial fashion, in order to maximize the regret. However, both the LMQ and LEQ models require that target concept be chosen priori. Note though that the LEQ oracle can give any counterexample for the robust loss at a given point.
In practice, one always has to find way to approximately implement oracles studied in theory. A possible way to generate counterexamples with respect to the exact-in-the-ball notion of robustness is as follows. Suppose that there is an adversary that can generate points 2 B2(x) such that h(2)) o c(z). Provided such an adversary can be simulated, there a way to (imperfectly) implement the LEQ oracle in practice.
Both the LMQ and LEQ models are particularly well-suited for the standard and exact-in-the-ball risks, as they address cetrmattion-hhorre limitations of learning with random examples only. On the other hand, while information theoretic limitations of robust learning with respect to the constant-in-the inttht-iitthhh-aee bbll notion of robustness arise when the perturbation function 24 is unknown to the learner, computational obstacles can also occur even when the definition of 24 is available. Indeed, determining whether the hypothesis changes label in the perturbation region could be intractable. In these cases, the Perfect Attack Oracle of Montasser et al. (20TT) can be used to remedy these limitations for robust learning with respect to the constant-in-the ball robust risk. Crucially, in their setting, counterexamples could have a different label to the ground truth: a counterexample x E (xx) for æ is such that h22)= / c(z), not necessarily h=z)) &f c(z). This could compromise the standard accuracy of the hypothesis (see e.g.. Tsipras et al. (2019) for a learning problem where robustness and accuracy are at odds). Finally, an LMQ analogue for the constant-in iirtaantt-itte--ba ball risk is not needed:
the only information we need for a perturbed point 2 E B,(2) (x) is the label of x (given by the example oracle) and h(z). Given that one of the requirements of PAC learning is that the hypothesis is efficiently evaluatable, we can easily compute h(()).
'Similarly to p. we implicitly consider À as a function of the input dimension n. It also possible to extend this definition to an arbitrary perturbation function 24 X - x*x
'This evidently not the case for the Perfect Attack Oracle Montasser et al. 2021
"We implicitly assume that concept E C can be represented in size polynomial in where n is the input dimension: otherwise parameter size(c) can be introduced in the sample and query complexity requirements.
5

---

3 Distribution-Free Robust Learning with Local Equivalence Queries
In this section, we show that having access local equivalence query oracle can guarantee the efficient distribution-free robust learnability of certain concept classes, We start with a negative result which shows that for a wide variety of concept classes, if À < p. then distribution-free robust learnability is impossible with EX + X-LEQ regardless of how many queries are allowed. However, the regime À = p. which implies giving similar power to the learner as the adversary, enables robust learnability guarantees. Indeed, Section exhibbiss upper bounds on sample sizes that will guarantee robust generalization. These bounds are logarithmic in the size of the hypothesis class (finite case) and linear in the robus! VC dimension of a concept class (infinite case). Section 3.3 draws a comparison between our framework and the online learning setting, and exhibits robustly consistent learners. Section 3.4 studies conjunctions and presents robust learning algorithm that is both statistically and computationally efficient. Finally, Section 3.5 looks at linear classifiers in the discrete and continuous cases, and adapts the Winnow and Perceptron algorithms to both settings.
3.1 Impossibility of Distribution-Free Robust Learning When À < P
We start with negative result, saying that whenever the local query radius is strictly smaller than the adversary's 's budget, monotone conjunctions are not distribution-fiee free robustly learnable, which in contrast to the standard PAC setting where guarantees hold for any distribution. Note that our result goes beyond efficiency: no query can distinguish between two potential targets. Choosing the target uniformly at random lower bounds the expected robust risk, and hence renders robust learning impossible in this setting. The proof of this theorem can be found in Appendix C.1
Theorem 2. For locality and robustness parameters X. P E N with < p. monotone conjunctions (and any superclass) are not distribution-free p-robustly learnable with access to a X-LEQ oracle.
The result holds for monotone conjunctions and all superclasses (c.g.. decision lists and halfspaces). but, in fact, we can generalize this reasoning for any concept class that has certain form of stability: if we can find concepts e1 and C2 in C and points x; x' X' such that ej and 02 agree on (x)x) but disagree on x', then if X < p. the concept class C is not distribution-fre freee p-robustly learnable with access a X-LEQ oracle. It suffices "move" the center of the ball x until we find a point in the set (a) (x) where e₁ and 02 disagree, which is guaranteed to happen by the existence of x'.
3.2 General Sample Complexity Bounds for Robustly-Consiste Learners
In this section, we show that we can derive sample complexity upper bounds for robustly consistent learners, i.e., learning algorithms that return a robust loss of zero on a training sample. Note that, crucially, the exact-in-the-ball notion of robustness and its realizability imply that any robust ERM algorithm will achieve zero empirical robust loss on a given training sample. As we will see in the next sections, the challenge is to find a robustly consistent learning algorithm that uses queries to p-LEQ. The first bound is for finite classes, where the dependency is logarithmic in the size of the hypothesis class. The proof is simple application of Occam's razor and is included in Appendix for completeness. The reasoning is similar to Bubeck et al. (2019).
Lemma 3. Let C be concept class and H a hypothesis class. Any p-robust ERM algorithm using H on sample of size m 2 \ (log [Hml + log !)) is p-robust leurner for C.
For the infinite case, we cannot immediately use the VC dimension as a tool for bounding the sample complexity of robust learning. To this end, we define the robust VC dimension of a concept class, which is the VC dimension of the class of functions representing the p-expansion of the error region between any possible target and hypothesis. This definition is analogous to the adversarial VC dimension defined by Cullina et al. (208)) for the constant-in-the-ban definition of robustness.
Definition 4 (Robust VC dimension). Given target concept class C, hypothesis class H and robustness parameter p. the robust VC dimension defined as RVC, H) = VC((C + H)p)), where (C 4 H)p {( h),, z + 1|3z Bx(x) c(z) # h(2)] c C, h E H}. Whenever C = H. we
simply write (C).
We now show that we can use the robust VC dimension to upper bound the sample complexity of robustly-consisten learning algorithms. We will use this result Section 3.5 when dealing with an infinite concept class: halfspaces on R

---

Lemma 5. Let C be concept class and 'H. hypothesis class, Any p-robust ERM algorithm using H. on a sample of size m 22 (RVC,(C, H) log(1/e) + log 1)) ) is p-robust learner for C.
Proof Sketch of Lemma 5 The proof is very similar to the VC dimension upper bound in PAC learning. The main distinction is that, instead of looking at the error region of the target and any function in H. we look at its p-expansion. Namely, let the target e E C be fixed and, for h E H. consider the function (c @ h)p : x + [[3z E BB(()) c(z) + h((2)] and define a new concept class (H)) = {[c @ h)p h E H]. It is easy to show that VC(Ac,p (H)) S (VC, H)), as any sign pattern achieved on the LHS can be achieved on the RHS. The rest of the proof follows from
the definition of an e-net and the bound the growth function of Ac,p see Appendix C.3 for
details.
Remark Note that, as p(n)/n tends to 1, we move towards the exact and online learning settings, and the underlying distribution becomes less important. In this case, the robust VC dimension starts to decrease. Indeed, say p = n, then (C ())) only contains the constant functions 0 and 1. We thus only need a single example to query the LEQ oracle (which has become the EQ oracle). However, this comes at cost: the query complexity upper bounds presented the next sections could be tight. Understanding the behaviour of the robust VC dimension as a function of p and deriving joint sample and query complexity bounds are both avenues for future research.
3.3 Query Complexity Bounds Using Online Learning Results
In the previous section, we derived sample complexity upper bounds for robustly consistent learners. The challenge is thus create algorithms that perform robust empirical risk minimization, as we are operating in the realizable setting. We begin by showing that, if one can ignore computational limitations, then online learning results can used to guarantee robust learnability. We recall the online learning setting in Appendix AA.3 We denote by Lit(C) the Littlestone dimension of a concept class C, which defined in Appendix A.4 and appears the query complexity bound in the theorem below, whose proof can be found in Appendix
Theorem 7. A concept class C is p-robustly learnable with the Standard Optimal Algorithu Lir- Alestone 7 1988) using the EX and p-LEQ oracles with sample and query complexity m(n,c.8) ( (C) log(1/e) + log t) and r(n, 6) mnn, e, 8) Lit(C), respectively. Furthermore, if C is a finite concept class {0, 1)", .thn C is p-robustly learnable with sample and query complexity m(n, c, 8) (log(IC) + log }) and r(n, c, p) m(n, c, 6) Lit(C).
Of course, some concept classes, e.g., thresholds, have infinite Littlestone dimension, so our bounds are not useful in these settings. In Section we study distributional assumptions that give reasonable query upper bounds for linear classifiers, using the theorem below. It exhibits a query upper bound for robustly learning with an online algorithm A with given mistake upper bound M. This is moreover particularly useful case M is polynomial in the input dimension and A is computationally efficient (which is not the case for the Standard Optimal Algorithm in Theorem D
Lemma 8. Let C be a concept class learnable in the online setting with mistake bound ((n. Then C. is p-robustly learnable using the EX and p-LEQ oracles with sample complexity m(n, (RVC,,H, + log 2) and query complexity r(n, c) mmn,,, M(n).
Proof. The sample complexity bound is obtained from Lemma and, for each point in the sample, a query to LEQ can either return robust loss of 0 or 1 and give counterexample. Since the mistake bound is M (n)), we have a query upper bound of r = m M, as required.
3.4 Improved Query Complexity Bounds: Conjunctions
In this section, we show how to improve the query upper bound from the previous section in the special case of conjunctions. Moreover, the algorithm used to robustly learn conjunctions is both statistically and computationally efficient, which is not the case of the Standard Optimal Algorithm. The proof of the following theorem can be found in Appendix C.S)
Theorem 9. The class CONJUNCTIONS is efficiently p-robustly learnable in the distribution-free setting using the EX and p-LEQ oracles with at most O (: (n + log b)) random examples and O [ (n + log 1)) queries to P-LEQ.
7

---

Note that the query upper bound that we get is of the form m + M, as opposed to m M from Lemma (where m is the sample complexity and M the mistake bound). This is because we have adapted the PAC learning algorithm for conjunctions to our setting. Any update to its hypothesis will not affect the consistency of previously queried points with robust loss of zero, and thus once zero robust loss is achieved on a point, it does not need to be queried again.
3.5 Linear Classifiers
In this section, we derive sample and query complexity upper bounds for restricted subclasses of linear classifiers. We start with linear classifiers on {0, 1 with bounded weights, and continue with linear classifiers on R" with a margin condition. We use the well-known Winnow and Perceptron algorithms. Note that the robustness threshold of linear classifiers on {0,1)" without access to the LEQ oracle remains an open problem (Gourdeau et al. 2022).
Let LTFW [0.1]" be the class of linear threshold functions on {0, 13" with integer weights such that the sum of the absolute values of the weights and the bias is bounded above by W. We have the following theorem, whose proof relies on bounding the size of LTFW (0.1)" and using the mistake bound for Winnow (Littlestone) 1988 The proof can be found in Appendix C.6
Theorem 10. The class LTF (0.13" is p-robustly learnable with access to the EX and p-LEQ oracles by using the Winnow algorithm with sample complexity m(n, = O (2 (n min {n, W} log(W n)) + log !)) and query complexity Omm(n, c. W log(n)).
Now, we derive sample and query complexity upper bounds for the robust learnability of linear classifiers LTFg on R2. Note that, unlike in previous results, the distribution family is restricted to guarantee the existence of margin for each concept and distribution pair, and distribution- free robust learning in this case. This is because the Littlestone dimension of thresholds, and thus halfippaces, is infinite if there are distributional assumptions on this concept class. We remark that whenever the margin is greater than p/2, the constant and exact-in-thee the- notions of robustness could coincide in which case the results from (Diakonikolas et al. 2020 Montasser et al. 202T apply. However, unlike in Diakonikolas et al. (020); Montasser et al. (202)) under our notion of robustness, y < p/2, we may still be in the realizable setting (there exists at least one concept that is robustly consistent with the data), while when considering the constant-in-ther
cannot guarantee
risk, we necessarily in the non-realizableeagoosii setting. As mentioned earlier, guarantees obtained in the latter do not necessarily translate to the former. The full proof of the theorem below appears in Appendix C.7
Theorem 11. Fix constants B,y > O. Let L [(c,D) CE LTF D E D) be family of halfspace and distribution pairs, where each pair (c, D) with c(z) a x + dg is such that if E supp(D), then (i) ||=||| I B and (ii) 7 S <=>)a==> i.e., D has support bounded by B and induces a margin of y w.r.t Let the adversary's budget be measured by the &g norm. Then, L is p-robustly learnable using the EX and p-LEQ oracles with sample complexity m = ( + +lg((1/))) and
Note that this query-efficiens if B² 72 poly(n). query complexity r 7
mB²
Proof Sketch. The first step is to derive the sample complexity bound. To this end, we use Lemma 5 and bound the robust VC dimension of linear classifiers on R", We do this using result of Goldberg and Jerrum 1995) (Theorem 28 in Appendix C.7). D. which bounds the VC dimension of concept classes expressible as boolean combinations of polynomial inequalities. We first express the p- expansion of the error region, i.c., the robust loss, between two linear classifiers as a first order logical polynomial inequalities. We then the method from Renegar (992) to transform vb into a quantifier-free formula y This method allows to show an upper bound the number of atomic predicates, their degree, and the number of variables in yo We can apply the result of Goldberg and Jerrum (1955) on ş to get a robust VC dimension of (ne)).
formula ie over the reals where the atomic predicates quantifer-eliminatie
The second step is to derive the query upper bound, which follows from Lemma 3 and the mistake bound for the Perceptron algorithm, which appears in Appendix B
With respect to the exact-in-than -all definition of robustness. GGiven that the choice of target implies constant-in in-tattttiite----ee the ball realizabilitty
8

---

4 A Local Membership Query Lower Bound for Conjunctions
In this section, show that the amount of data needed to p-robustly learn conjunctions under the uniform distribution has an exponential dependence on the adversary's budget p when the learner only has access to the EX and LMQ oracles. Here, the lower bound on the sample drawn from the example oracle is 2P, which is the same as the lower bound for monotone conjunctions derived in Gourdeau al. 2022), and the local membership query lower bound is 20-1, The result relies on showing there there exists a family of conjunctions that remain indistinguishable from each other on any sample of size 2 and any sequence of 20 LMQs with constant probability.
Theorem 12. Fix monotone increasing robustness function p N + N satisfying 2 S p(n) I n/4 for all n. Then, for any query radius X. any p(n) -robust learning algorithm for the class CONJUNCTIONS with access to the EX and X-LMQ oracles has joint sample and query complexity lower bounds 2 and 2 under the uniform distribution.
Proof. Let D be the uniform distribution and WLOG let p 2 2. Fix two disjoint sets I and Iz of 2p indices in [n], which will be the set of variables appearing in potential target conjunctions ej and cg- respectively (i.e., their support). We have 2 possible pairs of such conjunctions, as each variable can appear as a positive or negative literal.
Let us consider a randomly drawn sample S of size 2", We will first consider what happens when all the examples S and the queried inputs S' are negatively labelled. Each negative example E S allows us to remove at most 2 pairs from the possible set of pairs of conjunctions, as cach component rı, and F7, removes most one conjunction from the possible targets. By the same reasoning, each LMQ that returns a negative example can remove at most 2 pairs of conjunctions. Note that the parameter is irrelevant in this setting as each LMQ can only test one concept pair. Thus, after seeing any random sample of size 2" and querying any 20-1 points, there remains
24 23p+1 23p
1/4
24
of the initial conjunction pairs that label all points in S and S' negatively. Then, fixing S, and choosing a pair (c1,02) 62) of possible target conjunctions uniformly at random and then choosing uniformly at random between the two gives at least a 1/4 chance that S and S" only contain negative examples (both conjunctions are consistent with this).
Moreover, note that any two conjunctions pair will have a robust risk lower bounded by 15/32
against each other under the uniform distribution (see Lemma 23 in Appendix Bp. Thus, any learning algorithm A with LMQ query budget m' = 2--1 and strategy o (40,
(0, + (10, 1]" x
{0, 1))m (note that the queries can be adaptive) can do no better than to guess which of c: or 0o is the target if they
both consistent on the augmented sample S (S)), giving an expected robust risk lower bounded by a constant. Letting & be the event that all points in both S and (SS) are labelled zero, we get
E [R (A(S c,
Pr c,5
(E
E E.
R (A(S
|
(Law of Total Expectation)
>
E (()(((S
(Equation
c.S
1 2
| ((((A((UU())) (A(SUO(S)) 02) E]
(Random choice of c)
2
E [RØ (c),
(Lemma 22
1 15
(Lemma A
8 32
15
256
which completes the proof.
We use the term robustness threshold from Gourdeau et al. (20TT) to denote an adversarial budget function p N + IR of the input dimension such that, if the adversary is allowed perturbations

---

of magnitude p(n), then there exists sample-efii efficient p(n)) learning algorithm, and if the adversary's budget is (p(n)), then there does not exist such an algorithm. Robustness thresholds are distribution-denee dependent when the learner only has access to the example oracle EX, as seen in (Gourdeau al. 202T, 2022). Now, since the local membership query lower bound above has an exponential dependence on p. any perturbation budget w (logn) n.) will require sample and query complexity that is superpolynomial in n, giving the following corollary.
Corollary 13. The robustness threshold of the class CONJUNCTIONS under the uniform distribu- tion with access to EX and an LMQ oracle is (log(n))
The robustness threshold above the same as when only using the EX oracle (Gourdeau al. 2021). Finally, since decision lists and halfspaces both subsume conjunctions, the lower bound of Theorem 12 also holds for these classes.
Conclusion
We have shown that local membership queries do not change the robustness threshold of conjunctions, or any superclass, under the uniform distribution. However, access to a p-local equivalence query oracle allows us to develop robust ERM algorithmss. We have introduced the notion of robust VC dimension to determine sample complexity bounds and have used online learning results to derive query complexity bounds. We have moreover adapted the PAC learning algorithm for conjunctions for this setting and have greatly improved its query complexity compared to the general case. Finally, have studied halfspaces, both in the boolean hypercube and continuous settings. The latter is, to our knowledge, the first robust learning algorithm with respect to the exact-in ieett-inttheee the-ball notion of robustness for non-trivial concept class in I Overall, we have shown that the LEQ oracle is essential to ensure the distribution-free robust learning of commonly studied concept classes in our setting. Note that this is in contrast with standard PAC learning with the EX and EQ oracles, where equivalence queries don't I give more power to learner.
We finally outline various avenues for future research:
1. Can we give a more fine-grained picture the sample and query complexity tradeoff outlined in Remark e.g., by improving LEQ query upper bounds when p is small?
2. Can we derive sample and query lower bounds for robust learning with an LEQ oracle?
3. The LMQ lower bound from Section was derived for conjunctions. The technique does not work for monotone conjunctions Can get a similar LMQ lower bound where the dependence on is exponential for monotone conjunctions, or it is possible to robustly learn them with (29) local membership queries?
Acknowledgements
MK and PG received funding from the ERC under the European Union's Horizon 2020 research and innovation programme (FUN2MODEL, grant agreement No. 834115).
References
Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and computation, 75(2):87-106.
Angluin, D. (1988). Queries and concept learning. Machine learning, 2(4):319-342.
Angluin, D. (1990). Negative results for equivalence queries. Machine Learning, 5(2):121-150.
Angluin, D. and Kharitonov, M. (1995). When won't membership queries help? Journal of Computer and System Sciences, 50(2):336-355
Ashtiani, H., Pathak, V., and Urner, (2020). Black-box certification and learning under adversarial perturbations. In International Conference on Machine Learning, pages 388 398. PMLR
For given set of indices I, there exists only monotone conjunction using all indices in L.
10

---

Awasthi, P., Feldman, V., and Kanade, V. (2013). Learning using local membership queries. In COLT, volume 30, pages 1-34.
Awasthi, P., Frank, N., and Mohri, M. (2020). Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pages 431 1414..1. PMLR.
Stry-Weisberg, G., Daniely, A., and Shalev-Shwartz, S. (2020). Distribution free learning with local queries. In Algorithmic Learning Theory, pages 133-147. PMLR.
Baum, E. B. and Lang. K. (1992). Query learning can work poorly when human oracle is used. In International joint conference on neural networks, volume 8, page 8. Beijing China.
Bhattacharjee, R., Jha, S., and Chaudhuri, K. (2021). Sample complexity of robust linear classification on separated data. In International Conference Machine Learning, pages 884-893, PMLR.
Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šmdić N., Laskov, P., Giacinto, G., and Roli, F. (2013). Evasion attacks against machine learning test time. In Joint European conference machine learning and knowledge discovery in databases, pages 287-402. Springer.
Biggio, B. and Roli, F. (2017). Wild patterns: Ten years after the rise of adversarial machine learning. arXiv preprint arXiv: 172.03311.
Bshouty, N. H. (1993). Exact learning via the monotone theory. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 302-311. IEEE.
Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. (2019). Adversarial examples from compu- tational constraints. In Proceedings of the 36th International Conference Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 831-840, Long Beach, California, USA. PMLR.
Camacho, A. and Mcllraith, S. A. (2019). Learning interpretable models expressed in linear temporal logic. In Proceedings of the International Conference on Automated Planning and Scheduling. volume 29, pages
Cullina, D., Bhagoji, A. N., and Mittal, P. (2018). PAC-learning in the presence of evasion adversaries. Advances in Neural Information Processing Systems.
Dalvi, N., Domingos, P., Sanghai, S., Verma, D., et al. (2004). Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference Knowledge discovery and data mining, pages 99-108. ACM.
Diakonikolas, I., Kane, D. M., and Manurangsi, P. (2020). The complexity adversarially robust proper learning of halfspaces with agnostic noise. Advances in Neural Information Processing Systems, 33:20449 -04411
Diochnos, D., Mahloujifar, S., and Mahmoody, M. (2018). Adversarial risk and robustness: General definitions and implications for the uniform distribution. In Advances in Neural Information Processing Systems.
Diochnos, D. L., Mahloujifar, S., and Mahmoody, M. (2020). Lower bounds for adversarially robust PAC learning under evasion and hybrid attacks. In 2020 19th IEEE International Conference Machine Learning and Applications (ICMLA), pages 717-722.
Dreossi, T., Ghosh, S., Sangiovanni-Vineee
A., and Seshia, S. A. (2019). A formalization of robustness for deep neural networks. arXiv preprint arXiv:1903.10033
Fawzi, A., Fawzi, H., and Fawzi, O. (2018a). Adversarial vulnerability for any classifier. arXiv preprint arXiv: 1002::880.006600 08686.
Fawzi, A., Fawzi, O., and Frossard, (2018b). Analysis of classifiers? robustness to adversarial perturbations. Machine Learning, 107(3)481-508.
Fawzi, A., Moosavi-Dezfooli, S.-M., and Frossard, P. (2016). Robustness of classifiers: from adversarial to random noise. In Advances in Neural Information Processing Systems, pages 1632-1640.
11

---

Feige, U., Mansour, Y., and Schapire, R. (2015). Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory, pages 637-657.
Garg, S., Jha, S., Mahloujifar, S., and Mohammad, M. (2020). Adversarially robust learning could leverage computational hardness. In Algorithmic Learning Theoor, pages 364-388 PMLR.
Gilmer, J., Metz, I.., Faghri, F., Schoenholz, S. S., Raghu, M.. Wattenberg, M., and Goodfellow, I. (2018). Adversarial spheres. arXiv preprint arXiv:1801.0 1801.02774
Goldberg, P. W. and Jerrum, M. R. (1995). Bounding the chppii--hervvnenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18(2-3):131-148
Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2019). On the hardness of robust classification. In Advances in Neural Information Processing Systems, pages 7444 7453.
Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2021). On the hardness of robust classification. Journal of Machine Learning Research, 22.
Gourdeau, P., Kanade, V., Kwiatkowska, M., and Worrell, J. (2022). Sample complexity bounds for robustly learning decision lists against evasion attacks. In International Joint Conference in Artificial Intelligence.
Jackson, J. C. (1997). An efficient membership-query algorithm for learning dnf with respect the uniform distribution. Journal of Computer and System Sciences, 55(3):414 440.
Khim, J., Jog, V.. and Loh, P.-L. (2019). Adversarial influence maximization. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1-5, IEEE.
Littlestone, N. (1988). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4):285-318.
Lowd, D. and Meek, C. (2005a). Adversarial learning. In Proceedings of the eleventh ACM SIGKDD international conference Knowledge discovery in data mining, pages 641-647. ACM.
Lowd, D. and Meek, C. (2005b). Good word attacks statistical spam filters. In CEAS, volume 2005.
Mahloujifar, S., Diochnos, D. I., and Mahmoody, M. (2019). The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. AAAI Conference Artificial Intelligence.
Mahloujifar, S. and Mahmoody, M. (2019). Can adversarially robust learning leveragecomputational hardness? In Algorithmic Learning Theory, pages 58 581-609. PMLR.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2012). Foundations of machine learning. MIT press.
Montasser, O., Hanneke, S., and Srebro, N. (2019). VC classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pages 2512-2530. PMLR.
Montasser, O., Hanneke, S., and Srebro, N. (2020). Reducing adversarially robust learning to non-robust pac learning, Advances Neural Information Processing Systems, 33:14626-14637.
Montasser, O., Hanneke, S., and Srebro, N. (2021). Adversarially robust learning with unknown perturbation sets. In Conference on Learning Theory, pages 3452-3482. PMLR.
Okudono, T., Waga, M., Sekiyama, T., and Hasuo, I. (2020). Weighted automata extraction from recurrent neural networks via regression state spaces. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5306-5314
Pydi, M. and Jog, V. (2021). The many faces adversarial risk. Advances in Neural Information Processing Systems, 34.
Renegar, J. (1992). On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of symbolic computation, 13(3):255-299,
12

---

Shafahi, A., Huang, W. R., Studer, C.. Feizi, S., and Goldstein, T. (2018). Are adversarial examples inevitable? arXiv preprint wrxiv:189.02104.
Shih, A., Darwiche, A., and Choi, A. (2019). Verifying binarized neural networks by angluin-style learning. In International Conference on Theory and Applications of Satisfiability Testing, pages 354-370. Springer.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2013). Intriguing properties of neural networks. In International Conference on Learning Representations.
Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. (2019). Robustness may be at odds with accuracy. In International Conference Learning Representations.
Valiant, L. G. (1984). A theory of the learnable. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 436-445, ACM.
Viallard, P., VIDOT, E. G., Habrard, A., and Morvant, E. (2021). A PAC-Bayes analysis of adversarial robustness. Advances Neural Information Processing Systems, 34.
Weiss, G., Goldberg, Y., and Yahav, E. (2018). Extracting automata from recurrent neural networks using queries and counterexamples. In International Conference on Machine Learning, pages 5247-5256. PMLR.
Weiss, G., Goldberg, Y., and Yahav, E. (2019). Learning deterministic weighted automata with queries and counterexamples. Advances in Neural Information Processing Systems, 32.
Yin, D., Kannan, R., and Bartlett, P. (2019). Rademacher complexity for adversarially robust generalization. In International conference machine learning, pages 7085-7094, PMLR.
Checklist
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]
Computational limitations for the Standard Optimal Algorithm in Section
Concept classes with infinite Littlestone dimension in Section 3.3
Margin requirement for linear classifiers on the reals in Section 3.5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
13

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you 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 deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "OMON6HmkTei", "reviewer": "Reviewer_5J5m", "summary": "The paper studies adversarial robustness of learning basic concepts when the learner is allowed to make local queries. It shows that\n\n- Using local membership queries of Awasthi et al (2013) does not help too much on reducing the robust risk. This is in stark contrast to results established under the standard PAC model.\n\n- It then shows that with access to a new query type, equivalence query, the robust risk can be reduced.\n\nIn terms of merit, this paper gives the first robust ERM algorithm when robust risk is defined as being exact-in-the-ball.\n\nIn terms of techniques, this paper leverages many useful prior results and seems to combine them nicely.", "questions": "Please address the weakness part above.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n+ The paper studies a timely topic and gives full proof to its main results.\n+ It is interesting to consider various oracles to tackle the essentially hard problem of learning with adversarial examples. In particular, the separation result for local membership query appears interesting.\n\nWeakness:\n\n- It turns out that the main positive result is the improvement from using equivalence queries. However, I feel such query type was not well motivated, and seems too strong to find practical applications.\n\n- There are prior works studying the problem through the lens of online learning, which does not rely on the strong oracles, see e.g.\n\nThe Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise, I. Diakonikolas, D. Kane, P. Manurangsi, NeurIPS 2020\n\nThe above paper already sets out PAC learnability of large-margin halfspaces via L_p-norm Perceptron. I would like to see a close comparison to Theorem 11 in the submission.\n\n- While the paper presents a handful set of theoretical results, a highlight of the core techniques is missing. Thus, it is unclear to me whether the developed techniques are novel or the established results are just simple sandwich of prior works.\n\n- It turns out that the main claim is a robust ERM when adversarial examples reside exact-in-the-ball while prior works have built upon the regime constant-in-the-ball. I wonder what is the key challenge in the current setting and why existing results cannot be easily adapted.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "CIXvv6V2wlJ", "reviewer": "Reviewer_u9Eu", "summary": "The authors study adversarially robust learning in the \"exact-in-a-ball\" model when the learner has access to additional types of local queries. The `exact-in-a-ball' robustness model replaces the standard PAC classification error with\n\n$$\\Pr_{x \\sim D}[\\exists z \\in B(x,r): h(z) \\neq c(z)]$$\n\nThis differs from the widely studied \"constant-in-a-ball\" model that instead uses $h(x) \\neq c(z)$. Since learning even basic concepts in this model is typically impossible, the authors examine two types of enriched query algorithms: local membership queries and local equivalence queries. The former allows the learner to query any point in a small ball around any training example, and the latter allows the learner to ask whether a given hypothesis h is robust on a small ball around the point.\n\nThe authors show that while local membership queries do not help robust learning even in basic cases such as conjuctions over the uniform distribution, local equivalence queries can be used to robustly learn several non-trivial hypothesis classes such as conjuctions and halfspaces with margin, even in the distribution-free setting. In fact, the authors more generally show it is possible to robustly learn any finite class or class with finite robust VC dimension that has an online learner in the mistake bound model. Their algorithm is computationally efficient as long as the online learner is as well, which leads to statistically and computationally efficient robust learners for conjunctions and halfspaces with margin.\n", "questions": "A few typos: attaks, dimensino, ispoerimetric", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The `exact-in-a-ball' model of adversarial robustness is a challenging learning model, and this work gives the first efficient robust learners for important classes such as halfspaces with margin. While most of the general techniques in the work are not particularly novel (e.g. Robust VC, use of online learning), the eventual application and analysis showing halfspaces actually satisfy these conditions (namely Robust VC) is nice. Overall, the results are a bit niche, but may be of interest to the adversarial learning sub-community.\n\nOn the other hand, the paper can be a bit confusing at places, and also seems to have some small errors. Most of the sample complexities for instance seem to be missing a $\\log(1/\\varepsilon)$ term that should appear from applying Sauer-Shelah. The statement of results in Section 3.2 are also a bit confusing and stated in a non-standard fashion (perhaps a more typical presentation would be to say any RERM on m samples is a robust learner or something of this sort). Finally, while the authors largely do a good job placing the result in prior literature, it should probably also be mentioned that online learning (namely perceptron) has also been used in other work on robust learning, e.g. in [BJC21] “Sample Complexity of Robust Linear Classification on Separated Data.” ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ADwOdiJwsb", "reviewer": "Reviewer_n77F", "summary": "The paper considers (adversarial) robust learning in the PAC learning framework. As opposite to the \"standard\" notion of adversarial robustness, where the hypothesis $h$ is considered to be robust at point $x$ with radius $\\epsilon$ if the target concept is $c$ and it holds that $||x'-x|| \\leq \\epsilon \\implies h(x')= c(x)$. Here, the hypothesis needs to be correct in the epsilon ball to be considered robust. That is, it needs to satisfy $||x'-x|| \\leq \\epsilon \\implies h(x')= c(x')$. To achieve this, the learner is allowed to use \"Local membership queries\" in at-most $\\lambda$ distance from the observed point. The paper then shows that when $\\lambda < \\epsilon$, there is a distribution not learnable by any learner (thm 2). Then they provide several robust learnability results (thms 7,9,10,11) on classes such as linear threshold functions and conjunctions.", "questions": "- Please define the distribution-free setting. Does it mean that there are no assumptions on the distribution?  The term suggests that there is no underlying distribution, but then the notion of random sample would be meaningless.  Also I think it would be good if all definitions were in the appendix. Now the majority is there, but consistency is in the main text. \n\n- Why is correct-in-the-ball notion of robustness interesting? Specially, in this setting, we would like to be correct at every point (which is the same goal as we usually have, as opposite to the constant-in-the-ball risk), thus, the learning is basically the same as in the standard setting. I think there should be at least a brief discussion in the paper about this.\n\n- Feel free to point out any potential errors in the review.\n\n## misc\n- footnote 4 - why is Hamming distance the only meaningful distance here? While I agree that is a reasonable distance, I think there are many others and the space can have a special structure which can be of interest. E.g., If there is an underlying graph structure (other than a hypercube) which would induce the distances so that the \"adversarial neighborhood\" may contain e.g., neighboring nodes.\n\n\n\n", "limitations": "-", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\n# originality, clarity, quality, significance\n- Originality - The proof techniques seem to be standard (often the proofs are trivial modification of analogical proofs in the standard setting) but the considered problems are original, so I think the originality is ok. However, if there is some original technique that I have missed, I suggest the authors to emphasize it.\n- Clarity - Clearly written. Only that there are used lots of abbreviations which slows down the reading, but their presence is understandable.\n- Quality - I haven't found a problem.\n- Significance - I don't consider this work to be \"too\" significant, especially because the results are often unsurprising and easy to derive, but I think it has its place.\n\n\n# Pros\n- Easy to read\n- Extensive amount of previous work in the appendix, although something is superfluous.\n- Quite a lot of results.\n\n# Cons\n- The results are sometimes too simple, such as thm 2. which is claimed as one of the main contributions essentially says that when we cannot observe c(x) during training, then we don't know it. For lemma 3, I don't see a difference between the proof and a proof of the lemma in the standard (non-robust) setting (and then thm 9 is a corollary of lemma 3), Similarly lemma 5 seems to only replace VC dimension with robsut VC dimension, but there is almos no discussion on RVC (e.g., what is the RVC of standrd function classes) and so on.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept