VC Classes are Adversarially Robustly Learnable, but Only Improperly


Omar Montasser, Steve Hanneke, Nathan Srebro ;
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:2512-2530, 2019.


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 \emph{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 \emph{not} robustly PAC learnable with any \emph{proper} learning rule.

Related Material