Timezone: »

 
Poster
A Characterization of Semi-Supervised Adversarially Robust PAC Learnability
Idan Attias · Steve Hanneke · Yishay Mansour

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #810
in Poster Session 5 »

We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model.We address the question of how many labeled and unlabeled examples are required to ensure learning.We show that having enough unlabeled data (the size of a labeled sample that a fully-supervised method would require),the labeled sample complexity can be arbitrarily smaller compared to previous works, and is sharply characterized by a different complexity measure. We prove nearly matching upper and lower bounds on this sample complexity.This shows that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model, and establishes a gap between supervised and semi-supervised label complexities which is known not to hold in standard non-robust PAC learning.

Keywords: Semi-Supervised Learning · Sample Complexity · Adversarial Robustness · Combinatorial Dimensions · PAC Learning · Partial Concept Classes
[ Paper]  [ Slides]  [ Poster]  [ OpenReview] 

Author Information

Idan Attias (Ben Gurion University)
Steve Hanneke (Toyota Technological Institute at Chicago)
Yishay Mansour (Tel Aviv University & Google)

More from the Same Authors