On Achieving Optimal Adversarial Test Error
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 41 of its 55 references that are in the map. First posted on arXiv 13 Jun 2023.
Builds on
41 of 55 references.
References · 41
- 2014Explaining and Harnessing Adversarial Examplescited by 7,287
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
- 2013Intriguing properties of neural networkscited by 5,114
- 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
- 2016Adversarial examples in the physical worldcited by 1,762
- 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
- 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
- 2017Virtual Adversarial Training: A Regularization Method for Supervised and Semi-Supervised Learningcited by 918
- 2018Robustness May Be at Odds with Accuracycited by 873
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
29 more
- 2017Countering Adversarial Images using Input Transformationscited by 517
- 2020Overfitting in adversarially robust deep learningcited by 504
- 2017Mitigating Adversarial Effects Through Randomizationcited by 382
- 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
- 2018Adversarial Logit Pairingcited by 224
- 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
- 2018Stochastic Activation Pruning for Robust Adversarial Defensecited by 171
- 2020Randomized Smoothing of All Shapes and Sizescited by 146
- 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
- 2021On the Convergence and Robustness of Adversarial Trainingcited by 127
- 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
- 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
- 2018Risk and parameter convergence of logistic regressioncited by 81
- 2020Precise Tradeoffs in Adversarial Training for Linear Regressioncited by 76
- 2019Lower Bounds on Adversarial Robustness from Optimal Transportcited by 52
- 2020Adversarial Learning Guarantees for Linear Hypotheses and Neural Networkscited by 47
- 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
- 2022The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regressioncited by 40
- 2019Adversarial Risk via Optimal Transport and Optimal Couplingscited by 36
- 2020Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionalitycited by 36
- 2020Calibrated Surrogate Losses for Adversarially Robust Classificationcited by 36
- 2021Early-stopped neural networks are consistentcited by 34
- 2018Theoretical Analysis of Adversarial Learning: A Minimax Approachcited by 31
- 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
- 2021A Finer Calibration Analysis for Adversarial Robustnesscited by 26
- 2021On the Existence of the Adversarial Bayes Classifier (Extended Version)cited by 25
- 2019Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problemscited by 23
- 2021Interpolation can hurt robust generalization even when there is no noisecited by 15
- 2019Adversarial Risk Bounds for Neural Networks through Sparsity based Compressioncited by 4
Built on by
Citing papers per year: 2024: 1.
1 paper.