Generalized No Free Lunch Theorem for Adversarial Robustness

Abstract

This manuscript presents some new impossibility results on adversarial robustness in machine learning, a very important yet largely open problem. We show that if conditioned on a class label the data distribution satisfies the $W_2$ Talagrand transportation-cost inequality (for example, this condition is satisfied if the conditional distribution has density which is log-concave; is the uniform measure on a compact Riemannian manifold with positive Ricci curvature, any classifier can be adversarially fooled with high probability once the perturbations are slightly greater than the natural noise level in the problem. We call this result The Strong "No Free Lunch" Theorem as some recent results (Tsipras et al. 2018, Fawzi et al. 2018, etc.) on the subject can be immediately recovered as very particular cases. Our theoretical bounds are demonstrated on both simulated and real data (MNIST). We conclude the manuscript with some speculation on possible future research directions.

Cited by in corpus (14)

• Rademacher Complexity for Adversarially Robust Generalization
• A Closer Look at Accuracy vs. Robustness
• PatchGuard: A Provably Robust Defense against Adversarial Patches via Small Receptive Fields and Masking
• The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning
• Towards Security Threats of Deep Learning Systems: A Survey
• SoK: Machine Learning Governance
• Adversarial Machine Learning Phases of Matter
• A Bayes-Optimal View on Adversarial Examples
• Understanding the Intrinsic Robustness of Image Distributions using Conditional Generative Models
• Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries
• Classifier-independent Lower-Bounds for Adversarial Robustness
• Improved Estimation of Concentration Under ${\ell }_p$-Norm Distance Metrics Using Half Spaces