# A Fundamental Performance Limitation for Adversarial Classification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2019.

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

- [Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model](https://mlsanity.com/paper/2104.02189/) (2021)
- [Robust Adversarial Classification via Abstaining](https://mlsanity.com/paper/2104.02334/) (2021)

## Abstract (arXiv)

Despite the widespread use of machine learning algorithms to solve problems of technological, economic, and social relevance, provable guarantees on the performance of these data-driven algorithms are critically lacking, especially when the data originates from unreliable sources and is transmitted over unprotected and easily accessible channels. In this paper we take an important step to bridge this gap and formally show that, in a quest to optimize their accuracy, binary classification algorithms -- including those based on machine-learning techniques -- inevitably become more sensitive to adversarial manipulation of the data. Further, for a given class of algorithms with the same complexity (i.e., number of classification boundaries), the fundamental tradeoff curve between accuracy and sensitivity depends solely on the statistics of the data, and cannot be improved by tuning the algorithm.