Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries

Abstract

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.

arXiv comment16 pages, 12 figures; Accepted to ICML 2021

References in corpus (19)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning
• Theoretically Principled Trade-off between Robustness and Accuracy
• Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks
• Adversarially Robust Generalization Requires More Data
• Motivating the Rules of the Game for Adversarial Example Research
• Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples
• Adversarial examples from computational constraints
• Rademacher Complexity for Adversarially Robust Generalization
• RobustBench: a standardized adversarial robustness benchmark
• Smooth Adversarial Training
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Adversarial Spheres
• Generalized No Free Lunch Theorem for Adversarial Robustness
• On Robustness to Adversarial Examples and Polynomial Optimization
• Adversarial Robustness via Label-Smoothing
• Adversarially Robust Learning Could Leverage Computational Hardness
• Security and Machine Learning in the Real World
• Efficiently Learning Adversarially Robust Halfspaces with Noise