VC Classes are Adversarially Robustly Learnable, but Only Improperly
This addresses the theoretical foundations of adversarial robustness in machine learning, providing a fundamental result on learnability but is incremental in the context of existing VC theory.
The paper tackles the problem of learning adversarially robust predictors, showing that any hypothesis class with finite VC dimension is robustly PAC learnable using an improper learning rule, but not with proper learning rules, as demonstrated by counterexamples.
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.