# Sample Complexity of Adversarially Robust Linear Classification on Separated Data

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2020.

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

- [On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes](https://mlsanity.com/paper/2203.11864/) (2022)
- [Binary Classification Under ℓ0 Attacks for General Noise Distribution](https://mlsanity.com/paper/2203.04855/) (2022)
- [Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attacks](https://mlsanity.com/paper/2402.03576/) (2024)

## Abstract (arXiv)

We consider the sample complexity of learning with adversarial robustness. Most prior theoretical results for this problem have considered a setting where different classes in the data are close together or overlapping. Motivated by some real applications, we consider, in contrast, the well-separated case where there exists a classifier with perfect accuracy and robustness, and show that the sample complexity narrates an entirely different story. Specifically, for linear classifiers, we show a large class of well-separated distributions where the expected robust loss of any algorithm is at least Omega(fracdn), whereas the max margin algorithm has expected standard loss O(frac1n). This shows a gap in the standard and robust losses that cannot be obtained via prior techniques. Additionally, we present an algorithm that, given an instance where the robustness radius is much smaller than the gap between the classes, gives a solution with expected robust loss is O(frac1n). This shows that for very well-separated data, convergence rates of O(frac1n) are achievable, which is not the case otherwise. Our results apply to robustness measured in any ℓp norm with p > 1 (including p = ∞).