Reducing Adversarially Robust Learning to Non-Robust PAC Learning

Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

Authors

Omar Montasser, Steve Hanneke, Nati Srebro

Abstract

We study the problem of reducing adversarially robust learning to standard PAC learning, i.e. the complexity of learning adversarially robust predictors using access to only a black-box non-robust learner. We give a reduction that can robustly learn any hypothesis class C using any non-robust learner A for C. The number of calls to A depends logarithmically on the number of allowed adversarial perturbations per example, and we give a lower bound showing this is unavoidable.