# Provable tradeoffs in adversarially robust classification

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 30 of 40)

- [SmoothLLM: Defending Large Language Models Against Jailbreaking Attacks](https://mlsanity.com/paper/2310.03684/) (2023)
- [Model-Based Domain Generalization](https://mlsanity.com/paper/2102.11436/) (2021)
- [Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training](https://mlsanity.com/paper/2102.04716/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [Gaussian Universality of Perceptrons with Random Labels](https://mlsanity.com/paper/2205.13303/) (2022)
- [Explicit Tradeoffs between Adversarial and Natural Distributional Robustness](https://mlsanity.com/paper/2209.07592/) (2022)
- [Why adversarial training can hurt robust accuracy](https://mlsanity.com/paper/2203.02006/) (2022)
- [Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels](https://mlsanity.com/paper/2302.01629/) (2023)
- [Adversarial Training Should Be Cast as a Non-Zero-Sum Game](https://mlsanity.com/paper/2306.11035/) (2023)
- [Fundamental Tradeoffs in Distributionally Adversarial Training](https://mlsanity.com/paper/2101.06309/) (2021)
- [Can Adversarial Training Be Manipulated By Non-Robust Features?](https://mlsanity.com/paper/2201.13329/) (2022)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)
- [On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes](https://mlsanity.com/paper/2203.11864/) (2022)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (2022)
- [Understanding the Impact of Adversarial Robustness on Accuracy Disparity](https://mlsanity.com/paper/2211.15762/) (2022)
- [Adversarial robustness for latent models: Revisiting the robust-standard accuracies tradeoff](https://mlsanity.com/paper/2110.11950/) (2021)
- [Efficient Optimization Algorithms for Linear Adversarial Training](https://mlsanity.com/paper/2410.12677/) (2024)
- [Bridging the Gap Between Adversarial Robustness and Optimization Bias](https://mlsanity.com/paper/2102.08868/) (2021)
- [Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model](https://mlsanity.com/paper/2104.02189/) (2021)
- [On Proper Learnability between Average- and Worst-case Robustness](https://mlsanity.com/paper/2211.05656/) (2022)
- [Efficient and Robust Mixed-Integer Optimization Methods for Training Binarized Deep Neural Networks](https://mlsanity.com/paper/2110.11382/) (2021)
- [Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond](https://mlsanity.com/paper/2301.13486/) (2023)
- [Adversarially Pretrained Transformers May Be Universally Robust In-Context Learners](https://mlsanity.com/paper/2505.14042/) (2025)
- [Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization](https://mlsanity.com/paper/2510.20883/) (2025)
- [SynBench: Task-Agnostic Benchmarking of Pretrained Representations using Synthetic Data](https://mlsanity.com/paper/2210.02989/) (2022)
- [Robust Linear Regression: Phase-Transitions and Precise Tradeoffs for General Norms](https://mlsanity.com/paper/2308.00556/) (2023)
- [Non-Asymptotic Bounds for Adversarial Excess Risk under Misspecified Models](https://mlsanity.com/paper/2309.00771/) (2023)
- [Minimax rates of convergence for nonparametric regression under adversarial attacks](https://mlsanity.com/paper/2410.09402/) (2024)

## Abstract (arXiv)

It is well known that machine learning methods can be vulnerable to adversarially-chosen perturbations of their inputs. Despite significant progress in the area, foundational open problems remain. In this paper, we address several key questions. We derive exact and approximate Bayes-optimal robust classifiers for the important setting of two- and three-class Gaussian classification problems with arbitrary imbalance, for ℓ2 and ℓ_∞ adversaries. In contrast to classical Bayes-optimal classifiers, determining the optimal decisions here cannot be made pointwise and new theoretical approaches are needed. We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry, which, to our knowledge, have not yet been used in the area. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced. We also show further results, including an analysis of classification calibration for convex losses in certain models, and finite sample rates for the robust risk.