Rademacher Complexity for Adversarially Robust Generalization

Abstract

Many machine learning models are vulnerable to adversarial attacks; for example, adding adversarial perturbations that are imperceptible to humans can often make machine learning models produce wrong predictions with high confidence. Moreover, although we may obtain robust models on the training dataset via adversarial training, in some problems the learned models cannot generalize well to the test data. In this paper, we focus on ${\ell }_{\infty }$ attacks, and study the adversarially robust generalization problem through the lens of Rademacher complexity. For binary linear classifiers, we prove tight bounds for the adversarial Rademacher complexity, and show that the adversarial Rademacher complexity is never smaller than its natural counterpart, and it has an unavoidable dimension dependence, unless the weight vector has bounded ${\ell }_1$ norm. The results also extend to multi-class linear classifiers. For (nonlinear) neural networks, we show that the dimension dependence in the adversarial Rademacher complexity also exists. We further consider a surrogate adversarial loss for one-hidden layer ReLU network and prove margin bounds for this setting. Our results indicate that having ${\ell }_1$ norm constraints on the weight matrices might be a potential way to improve generalization in the adversarial setting. We demonstrate experimental results that validate our theoretical findings.

arXiv commentICML 2019

References in corpus (25)

• Towards Deep Learning Models Resistant to Adversarial Attacks
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Understanding deep learning requires rethinking generalization
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Towards Deep Neural Network Architectures Robust to Adversarial Examples
• Certified Defenses against Adversarial Examples
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Adversarially Robust Generalization Requires More Data
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization
• Robustness May Be at Odds with Accuracy
• Robustness and Regularization of Support Vector Machines
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Learning with a Strong Adversary
• Defensive Distillation is Not Robust to Adversarial Examples
• Semidefinite relaxations for certifying robustness to adversarial examples
• Motivating the Rules of the Game for Adversarial Example Research
• Adversarial vulnerability for any classifier
• Adversarial examples from computational constraints
• Robustness of classifiers: from adversarial to random noise
• Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
• Generalizable Adversarial Training via Spectral Normalization
• Generalized No Free Lunch Theorem for Adversarial Robustness
• PAC-learning in the presence of evasion adversaries
• Tight Risk Bounds for Multi-Class Margin Classifiers

Cited by in corpus (43)

• Theoretically Principled Trade-off between Robustness and Accuracy
• Adversarial Weight Perturbation Helps Robust Generalization
• Are Labels Required for Improving Adversarial Robustness?
• Adversarial Training Can Hurt Generalization
• Attacks Which Do Not Kill Training Make Adversarial Learning Stronger
• Unlabeled Data Improves Adversarial Robustness
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Overfitting in adversarially robust deep learning
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• PatchGuard: A Provably Robust Defense against Adversarial Patches via Small Receptive Fields and Masking
• Adversarial Unlearning of Backdoors via Implicit Hypergradient
• Auto-weighted Robust Federated Learning with Corrupted Data Sources
• The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• Interpolated Adversarial Training: Achieving Robust Neural Networks without Sacrificing Too Much Accuracy
• Adversarial Risk Bounds via Function Transformation
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies
• Exploring Memorization in Adversarial Training
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• On the Generalization Properties of Adversarial Training
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Adversarial Robustness of Supervised Sparse Coding
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• Model Complexity of Deep Learning: A Survey
• Formalizing Generalization and Robustness of Neural Networks to Weight Perturbations
• Calibration and Consistency of Adversarial Surrogate Losses
• Adversarially Robust Low Dimensional Representations
• Trust but Verify: An Information-Theoretic Explanation for the Adversarial Fragility of Machine Learning Systems, and a General Defense against Adversarial Attacks
• A PAC-Bayes Analysis of Adversarial Robustness
• ATRO: Adversarial Training with a Rejection Option
• Understanding the Generalization Benefit of Model Invariance from a Data Perspective
• Statistically Robust Neural Network Classification
• Robust Sensible Adversarial Learning of Deep Neural Networks for Image Classification
• Towards Deep Learning Models Resistant to Large Perturbations
• Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries
• Sample Complexity of Adversarially Robust Linear Classification on Separated Data
• Domain Invariant Adversarial Learning
• Genetic-algorithm-optimized neural networks for gravitational wave classification
• Query complexity of adversarial attacks
• Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
• Unique properties of adversarially trained linear classifiers on Gaussian data
• Estimating Principal Components under Adversarial Perturbations