VC Classes are Adversarially Robustly Learnable, but Only Improperly

Abstract

We study the question of learning an adversarially robust predictor. We show that any hypothesis class $\mathcal{H}$ with finite VC dimension is robustly PAC learnable with an improper learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes $\mathcal{H}$ with finite VC dimension that are not robustly PAC learnable with any proper learning rule.

COLT 2019 Camera Ready

References in corpus (10)

• Explaining and Harnessing Adversarial Examples
• Intriguing properties of neural networks
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Certified Defenses against Adversarial Examples
• Adversarially Robust Generalization Requires More Data
• Adversarial examples from computational constraints
• Rademacher Complexity for Adversarially Robust Generalization
• Multiclass learnability and the ERM principle
• Adversarial Risk Bounds via Function Transformation
• PAC-learning in the presence of evasion adversaries

Cited by in corpus (34)

• Adversarial Weight Perturbation Helps Robust Generalization
• Adversarial Training Can Hurt Generalization
• Unlabeled Data Improves Adversarial Robustness
• 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
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• Lower Bounds for Adversarially Robust PAC Learning
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Quantum Coupon Collector
• Proper Learning, Helly Number, and an Optimal SVM Bound
• Calibration and Consistency of Adversarial Surrogate Losses
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks
• Efficiently Learning Adversarially Robust Halfspaces with Noise
• Adversarially Robust Low Dimensional Representations
• A PAC-Bayes Analysis of Adversarial Robustness
• Adversarial Risk Bounds for Neural Networks through Sparsity based Compression
• Reducing Adversarially Robust Learning to Non-Robust PAC Learning
• Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
• Robust learning under clean-label attack
• Towards Deep Learning Models Resistant to Large Perturbations
• Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
• Coverage-Guaranteed Prediction Sets for Out-of-Distribution Data
• Learning and Certification under Instance-targeted Poisoning
• Query complexity of adversarial attacks
• When are Non-Parametric Methods Robust?
• Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries
• Domain Invariant Adversarial Learning
• Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness
• Sample Complexity of Adversarially Robust Linear Classification on Separated Data
• A Le Cam Type Bound for Adversarial Learning and Applications
• Realizable Learning is All You Need
• Unique properties of adversarially trained linear classifiers on Gaussian data