Reducing Adversarially Robust Learning to Non-Robust PAC Learning

2020/10/22 by Montasser, Omar, Hanneke, Steve, Srebro, Nathan
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2010.12039

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.

Related

• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Simplifying Adversarially Robust PAC Learning with Tolerance
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
• On Proper Learnability between Average- and Worst-case Robustness
• Adversarially Robust Learning with Tolerance