[edit]

# Adversarially Robust Learning Could Leverage Computational Hardness.

*Proceedings of the 31st International Conference on Algorithmic Learning Theory*, PMLR 117:364-385, 2020.

#### Abstract

Over recent years, devising classification algorithms that are robust to adversarial perturbations has emerged as a challenging problem. In particular, deep neural nets (DNNs) seem to be susceptible to small imperceptible changes over test instances. However, the line of work in

*provable*robustness, so far, has been focused on*information theoretic*robustness, ruling out even the*existence*of any adversarial examples. In this work, we study whether there is a hope to benefit from*algorithmic*nature of an attacker that searches for adversarial examples, and ask whether there is*any*learning task for which it is possible to design classifiers that are only robust against*polynomial-time*adversaries. Indeed, numerous cryptographic tasks (e.g. encryption of long messages) can only be secure against computationally bounded adversaries, and are indeed*impossible*for computationally unbounded attackers. Thus, it is natural to ask if the same strategy could help robust learning. We show that computational limitation of attackers can indeed be useful in robust learning by demonstrating the possibility of a classifier for some learning task for which computational and information theoretic adversaries of bounded perturbations have very different power. Namely, while computationally unbounded adversaries can attack successfully and find adversarial examples with small perturbation, polynomial time adversaries are unable to do so unless they can break standard cryptographic hardness assumptions. Our results, therefore, indicate that perhaps a similar approach to cryptography (relying on computational hardness) holds promise for achieving computationally robust machine learning. On the reverse directions, we also show that the existence of such learning task in which computational robustness beats information theoretic robustness requires computational hardness by implying (average-case) hardness of NP.