# On the Hardness of Robust Classification

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2019.

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

- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Investigating Vulnerabilities of Deep Neural Policies](https://mlsanity.com/paper/2108.13093/) (2021)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Detecting Brittle Decisions for Free: Leveraging Margin Consistency in Deep Robust Classifiers](https://mlsanity.com/paper/2406.18451/) (2024)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Detecting Adversarial Directions in Deep Reinforcement Learning to Make Robust Decisions](https://mlsanity.com/paper/2306.05873/) (2023)
- [Towards the Worst-case Robustness of Large Language Models](https://mlsanity.com/paper/2501.19040/) (2025)
- [Who's Afraid of Adversarial Transferability?](https://mlsanity.com/paper/2105.00433/) (2021)
- [Certification of embedded systems based on Machine Learning: A survey](https://mlsanity.com/paper/2106.07221/) (2021)
- [When to Trust AI: Advances and Challenges for Certification of Neural Networks](https://mlsanity.com/paper/2309.11196/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks](https://mlsanity.com/paper/2205.06127/) (2022)
- [On the Role of Randomization in Adversarially Robust Classification](https://mlsanity.com/paper/2302.07221/) (2023)
- [Trustworthy Actionable Perturbations](https://mlsanity.com/paper/2405.11195/) (2024)
- [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026)
- [On the Hardness of Robustness Transfer: A Perspective from Rademacher Complexity over Symmetric Difference Hypothesis Space](https://mlsanity.com/paper/2302.12351/) (2023)
- [Attacking Bayes: On the Adversarial Robustness of Bayesian Neural Networks](https://mlsanity.com/paper/2404.19640/) (2024)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)
- [On the (Un-)Avoidability of Adversarial Examples](https://mlsanity.com/paper/2106.13326/) (2021)
- [The Double-Edged Nature of the Rashomon Set for Trustworthy Machine Learning](https://mlsanity.com/paper/2511.21799/) (2025)

## Abstract (arXiv)

It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. We start with two negative results. We show that no non-trivial concept class can be robustly learned in the distribution-free setting against an adversary who can perturb just a single input bit. We show moreover that the class of monotone conjunctions cannot be robustly learned under the uniform distribution against an adversary who can perturb ω(log n) input bits. However if the adversary is restricted to perturbing O(log n) bits, then the class of monotone conjunctions can be robustly learned with respect to a general class of distributions (that includes the uniform distribution). Finally, we provide a simple proof of the computational hardness of robust learning on the boolean hypercube. Unlike previous results of this nature, our result does not rely on another computational model (e.g. the statistical query model) nor on any hardness assumption other than the existence of a hard learning problem in the PAC framework.