# When are Local Queries Useful for Robust Learning?

arXiv: https://arxiv.org/abs/2210.06089 · HTML: https://mlsanity.com/paper/2210.06089/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 71 references that are in the map.
- First posted on arXiv 12 Oct 2022.

## Builds on (most cited first, 30 of 31)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Robustness of classifiers: from adversarial to random noise](https://mlsanity.com/paper/1608.08967/) (2016)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Adversarial vulnerability for any classifier](https://mlsanity.com/paper/1802.08686/) (2018)
- [Analysis of classifiers' robustness to adversarial perturbations](https://mlsanity.com/paper/1502.02590/) (2015)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks](https://mlsanity.com/paper/2004.13617/) (2020)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution](https://mlsanity.com/paper/1810.12272/) (2018)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)
- [On the Hardness of Robust Classification](https://mlsanity.com/paper/1909.05822/) (2019)
- [Learning Deterministic Weighted Automata with Queries and Counterexamples](https://mlsanity.com/paper/1910.13895/) (2019)
- [Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces](https://mlsanity.com/paper/1904.02931/) (2019)
- [The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise](https://mlsanity.com/paper/2007.15220/) (2020)
- [Adversarially Robust Learning Could Leverage Computational Hardness](https://mlsanity.com/paper/1905.11564/) (2019)
- [Black-box Certification and Learning under Adversarial Perturbations](https://mlsanity.com/paper/2006.16520/) (2020)
- [A PAC-Bayes Analysis of Adversarial Robustness](https://mlsanity.com/paper/2102.11069/) (2021)
- [Lower Bounds for Adversarially Robust PAC Learning](https://mlsanity.com/paper/1906.05815/) (2019)
- [Can Adversarially Robust Learning Leverage Computational Hardness?](https://mlsanity.com/paper/1810.01407/) (2018)
- [A Formalization of Robustness for Deep Neural Networks](https://mlsanity.com/paper/1903.10033/) (2019)
- [Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks](https://mlsanity.com/paper/2205.06127/) (2022)

## Built on by (most cited first, 1 of 1)

- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)

## Abstract (arXiv)

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 (mathsfLEQ) 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 the one hand, if the query radius λ is strictly smaller than the adversary's perturbation budget ρ, then distribution-free robust learning is impossible for a wide variety of concept classes; on the other hand, the setting λ=ρ 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 on 0,1n and then obtaining robustness guarantees for halfspaces in ℝn against precision-bounded adversaries.