VC Classes are Adversarially Robustly Learnable, but Only Improperly
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the Computability of Robust PAC Learning
We initiate the study of computability requirements for adversarially robust learning. Adversarially robust PAC-type learnability is by now an established field of research. However, the effects of computability requirem…
PAC learningBagging Robustly Learns VC Classes with Linear Sample Complexity
We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an…
Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization
We present a minimax optimal learner for the problem of learning predictors robust to adversarial examples at test-time. Interestingly, we find that this requires new algorithmic ideas and approaches to adversarially rob…
Adversarially Robust PAC Learnability of Real-Valued Functions
We study robustness to test-time adversarial attacks in the regression setting with $\ell_p$ losses and arbitrary perturbation sets. We address the question of which function classes are PAC learnable in this setting. We…
regressionEfficiently Learning Adversarially Robust Halfspaces with Noise
We study the problem of learning adversarially robust halfspaces in the distribution-independent setting. In the realizable setting, we provide necessary and sufficient conditions on the adversarial perturbation sets und…