Can Adversarially Robust Learning Leverage Computational Hardness?

Understand

Making learners robust to adversarial perturbation at test time (i.e., evasion attacks) or training time (i.e., poisoning attacks) has emerged as a challenging task.

• It is known that for some natural settings, sublinear perturbations in the training phase or the testing phase can drastically decrease the quality of the predictions.
• These negative results, however, are information theoretic and only prove the existence of such successful adversarial perturbations.
• A natural question for these settings is whether or not we can make classifiers computationally robust to polynomial-time attacks.