Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries
Not on the map. Why?
Abstract (arXiv)
Understanding the fundamental limits of robust supervised learning has emerged as a problem of immense interest, from both practical and theoretical standpoints. In particular, it is critical to determine classifier-agnostic bounds on the training loss to establish when learning is possible. In this paper, we determine optimal lower bounds on the cross-entropy loss in the presence of test-time adversaries, along with the corresponding optimal classification outputs. Our formulation of the bound as a solution to an optimization problem is general enough to encompass any loss function depending on soft classifier outputs. We also propose and provide a proof of correctness for a bespoke algorithm to compute this lower bound efficiently, allowing us to determine lower bounds for multiple practical datasets of interest. We use our lower bounds as a diagnostic tool to determine the effectiveness of current robust training methods and find a gap from optimality at larger budgets. Finally, we investigate the possibility of using of optimal classification outputs as soft labels to empirically improve robust training.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 31 of its 51 references that are in the map. First posted on arXiv 16 Apr 2021.
Builds on
31 of 51 references.
References · 31
- 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
- 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
- 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
- 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
- 2020Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attackscited by 1,442
- 2020RobustBench: a standardized adversarial robustness benchmarkcited by 659
- 2020Overfitting in adversarially robust deep learningcited by 504
- 2019Unlabeled Data Improves Adversarial Robustnesscited by 415
- 2017Wild Patterns: Ten Years After the Rise of Adversarial Machine Learningcited by 411
- 2018Adversarially Robust Generalization Requires More Datacited by 318
19 more
- 2020Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examplescited by 275
- 2020Bag of Tricks for Adversarial Trainingcited by 199
- 2016Improving the Robustness of Deep Neural Networks via Stability Trainingcited by 156
- 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
- 2020SoK: Certified Robustness for Deep Neural Networkscited by 100
- 2016Towards the Science of Security and Privacy in Machine Learningcited by 89
- 2020Smooth Adversarial Trainingcited by 89
- 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
- 2018Adversarial examples from computational constraintscited by 79
- 2020Precise Tradeoffs in Adversarial Training for Linear Regressioncited by 76
- 2018Motivating the Rules of the Game for Adversarial Example Researchcited by 57
- 2019Lower Bounds on Adversarial Robustness from Optimal Transportcited by 52
- 2018The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measurecited by 44
- 2019Adversarial Risk via Optimal Transport and Optimal Couplingscited by 36
- 2018Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distributioncited by 32
- 2020Efficiently Learning Adversarially Robust Halfspaces with Noisecited by 22
- 2019On Robustness to Adversarial Examples and Polynomial Optimizationcited by 14
- 2019Adversarially Robust Learning Could Leverage Computational Hardnesscited by 13
- 2020Security and Machine Learning in the Real Worldcited by 9
Built on by
Citing papers per year: 2023: 1.
1 paper.