Adversarially Robust Learnability: Characterization and Reductions

Abstract: We study the question of learning an adversarially robust predictor from uncorrupted samples. We show that any VC class H is robustly PAC learnable, but we also show that such learning must sometimes be improper (i.e. use predictors from outside the class), as some VC classes are not robustly properly learnable. In particular, the popular robust empirical risk minimization approach (also known as adversarial training), which is proper, cannot robustly learn all VC classes. After establishing learnability, we turn to ask whether having a tractable non-robust learning algorithm is sufficient for tractable robust learnability and give a reduction algorithm for robustly learning any hypothesis class H using a non-robust PAC learner for H, with nearly-optimal oracle complexity.

This is based on joint work with Steve Hanneke and Nati Srebro, available at arxiv.org/abs/1902.04217 and arxiv.org/abs/2010.12039..

computational complexitycomputational geometrycryptography and securitydiscrete mathematicsdata structures and algorithmsgame theorymachine learningquantum computing and informationcombinatoricsinformation theoryoptimization and controlprobability

Audience: researchers in the topic

TCS+

Series comments: Description: Theoretical Computer Science

People can register to a talk via our webpage sites.google.com/site/plustcs/livetalk , or subscribe to our calendar and mailing list at sites.google.com/site/plustcs/rss-feeds