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 (1)

• Explaining and Harnessing Adversarial Examples

Cited by in corpus (8)

• Lower Bounds for Adversarially Robust PAC Learning
• Proper Learning, Helly Number, and an Optimal SVM Bound
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• Efficiently Learning Adversarially Robust Halfspaces with Noise
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks
• Adversarial Risk Bounds for Neural Networks through Sparsity based Compression
• Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
• Unique properties of adversarially trained linear classifiers on Gaussian data