mlsanityData to 7 Oct 2026

Provable tradeoffs in adversarially robust classification

arXiv 2006.05161 ↗First posted 9 Jun 2020cs.LG stat.MLcited by 39

Not on the map. Why?

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.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 11; 2023: 8; 2024: 4; 2025: 4; 2026: 1.

39 papers.

Sort:

By area:

  1. 2023SmoothLLM: Defending Large Language Models Against Jailbreaking Attackscited by 434
  2. 2021Model-Based Domain Generalizationcited by 103
  3. 2021Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Trainingcited by 58
  4. 2021Adversarial Robustness with Semi-Infinite Constrained Learningcited by 39
  5. 2022Probabilistically Robust Learning: Balancing Average- and Worst-case Performancecited by 36
  6. 2022Gaussian Universality of Perceptrons with Random Labelscited by 26
  7. 2022Explicit Tradeoffs between Adversarial and Natural Distributional Robustnesscited by 20
  8. 2023Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernelscited by 13
  9. 2023Adversarial Training Should Be Cast as a Non-Zero-Sum Gamecited by 13
  10. 2021Fundamental Tradeoffs in Distributionally Adversarial Trainingcited by 12
  11. 2022Can Adversarial Training Be Manipulated By Non-Robust Features?cited by 12
  12. 2022Why adversarial training can hurt robust accuracycited by 12
27 more
  1. 2021Benign Overfitting in Adversarially Robust Linear Classificationcited by 11
  2. 2021Understanding Generalization in Adversarial Training via the Bias-Variance Decompositioncited by 10
  3. 2022On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimescited by 10
  4. 2022A Law of Robustness beyond Isoperimetrycited by 9
  5. 2022Understanding the Impact of Adversarial Robustness on Accuracy Disparitycited by 9
  6. 2021Adversarial robustness for latent models: Revisiting the robust-standard accuracies tradeoffcited by 8
  7. 2024Efficient Optimization Algorithms for Linear Adversarial Trainingcited by 6
  8. 2021Bridging the Gap Between Adversarial Robustness and Optimization Biascited by 5
  9. 2021Robust Classification Under ℓ0 Attack for the Gaussian Mixture Modelcited by 5
  10. 2022On Proper Learnability between Average- and Worst-case Robustnesscited by 5
  11. 2021Efficient and Robust Mixed-Integer Optimization Methods for Training Binarized Deep Neural Networkscited by 4
  12. 2023Robust Linear Regression: Gradient-descent, Early-stopping, and Beyondcited by 4
  13. 2025Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularizationcited by 3
  14. 2022SynBench: Task-Agnostic Benchmarking of Pretrained Representations using Synthetic Datacited by 2
  15. 2023Non-Asymptotic Bounds for Adversarial Excess Risk under Misspecified Modelscited by 2
  16. 2024Minimax rates of convergence for nonparametric regression under adversarial attackscited by 2
  17. 2024Learning Fair Robustness via Domain Mixupcited by 2
  18. 2025Adversarially Pretrained Transformers May Be Universally Robust In-Context Learnerscited by 2
  19. 2023Robust Linear Regression: Phase-Transitions and Precise Tradeoffs for General Normscited by 1
  20. 2024Asymptotic Behavior of Adversarial Training Estimator under ℓ_∞-Perturbationcited by 1
  21. 2025Adversarial Robustness of Nonparametric Regressioncited by 1
  22. 2025Towards Better Generalization via Distributional Input Projection Networkcited by 1
  23. 2021Generalized Likelihood Ratio Test for Adversarially Robust Hypothesis Testingcited by 0
  24. 2022Ensemble Methods for Robust Support Vector Machines using Integer Programmingcited by 0
  25. 2023On Continuity of Robust and Accurate Classifierscited by 0
  26. 2023Training Image Derivatives: Increased Accuracy and Universal Robustnesscited by 0
  27. 2026Statistical Inference for Adversarial Training: Central Limit Theorems via Optimal Transportcited by 0