# On Achieving Optimal Adversarial Test Error

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 55 references that are in the map.
- First posted on arXiv 13 Jun 2023.

## Builds on (most cited first, 30 of 41)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Virtual Adversarial Training: A Regularization Method for Supervised and Semi-Supervised Learning](https://mlsanity.com/paper/1704.03976/) (2017)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Countering Adversarial Images using Input Transformations](https://mlsanity.com/paper/1711.00117/) (2017)
- [Overfitting in adversarially robust deep learning](https://mlsanity.com/paper/2002.11569/) (2020)
- [Mitigating Adversarial Effects Through Randomization](https://mlsanity.com/paper/1711.01991/) (2017)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Adversarial Logit Pairing](https://mlsanity.com/paper/1803.06373/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Stochastic Activation Pruning for Robust Adversarial Defense](https://mlsanity.com/paper/1803.01442/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [On the Convergence and Robustness of Adversarial Training](https://mlsanity.com/paper/2112.08304/) (2021)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks](https://mlsanity.com/paper/2004.13617/) (2020)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression](https://mlsanity.com/paper/2201.05149/) (2022)

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

- [Adversarial Consistency and the Uniqueness of the Adversarial Bayes Classifier](https://mlsanity.com/paper/2404.17358/) (2024)

## Abstract (arXiv)

We first elucidate various fundamental properties of optimal adversarial predictors: the structure of optimal adversarial convex predictors in terms of optimal adversarial zero-one predictors, bounds relating the adversarial convex loss to the adversarial zero-one loss, and the fact that continuous predictors can get arbitrarily close to the optimal adversarial error for both convex and zero-one losses. Applying these results along with new Rademacher complexity bounds for adversarial training near initialization, we prove that for general data distributions and perturbation sets, adversarial training on shallow networks with early stopping and an idealized optimal adversary is able to achieve optimal adversarial test error. By contrast, prior theoretical work either considered specialized data distributions or only provided training error guarantees.