Lower Bounds for Adversarially Robust PAC Learning

Dimitrios I. Diochnos, Saeed Mahloujifar, Mohammad Mahmoody

In this work, we initiate a formal study of probably approximately correct (PAC) learning under evasion attacks, where the adversary's goal is to \emph{misclassify} the adversarial…