Lower Bounds for Adversarially Robust PAC Learning

Abstract

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 adversarially perturbed sample point $\tilde{x}$, i.e., $h(\tilde{x})\ne c(\tilde{x})$, where $c$ is the ground truth concept and $h$ is the learned hypothesis. Previous work on PAC learning of adversarial examples have all modeled adversarial examples as corrupted inputs in which the goal of the adversary is to achieve $h(\tilde{x})\ne c(x)$, where $x$ is the original untampered instance. These two definitions of adversarial risk coincide for many natural distributions, such as images, but are incomparable in general. We first prove that for many theoretically natural input spaces of high dimension $n$ (e.g., isotropic Gaussian in dimension $n$ under ${\ell }_2$ perturbations), if the adversary is allowed to apply up to a sublinear $o(||x||)$ amount of perturbations on the test instances, PAC learning requires sample complexity that is exponential in $n$. This is in contrast with results proved using the corrupted-input framework, in which the sample complexity of robust learning is only polynomially more. We then formalize hybrid attacks in which the evasion attack is preceded by a poisoning attack. This is perhaps reminiscent of "trapdoor attacks" in which a poisoning phase is involved as well, but the evasion phase here uses the error-region definition of risk that aims at misclassifying the perturbed instances. In this case, we show PAC learning is sometimes impossible all together, even when it is possible without the attack (e.g., due to the bounded VC dimension).

References in corpus (8)

• BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain
• Poisoning Attacks against Support Vector Machines
• Security Evaluation of Pattern Classifiers under Attack
• Adversarial Examples Are a Natural Consequence of Test Error in Noise
• Adversarial examples from computational constraints
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• PAC-learning in the presence of evasion adversaries
• Adversarial Examples from Cryptographic Pseudo-Random Generators

Cited by in corpus (6)

• The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
• More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
• Towards Deep Learning Models Resistant to Large Perturbations
• Learning and Certification under Instance-targeted Poisoning
• Unique properties of adversarially trained linear classifiers on Gaussian data
• A Separation Result Between Data-oblivious and Data-aware Poisoning Attacks