Computational Limitations in Robust Classification and WinWin Results
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:9941028, 2019.
Abstract
We continue the study of statistical/computational tradeoffs in learning robust classifiers, following the recent work of Bubeck, Lee, Price and Razenshteyn who showed examples of classification tasks where (a) an efficient robust classifier exists, in the smallperturbation regime; (b) a nonrobust classifier can be learned efficiently; but (c) it is computationally hard to learn a robust classifier, assuming the hardness of factoring large numbers. Indeed, the question of whether a robust classifier for their task exists in the large perturbation regime seems related to important open questions in computational number theory. In this work, we extend their work in three directions. First, we demonstrate classification tasks where computationally efficient robust classification is impossible, even when computationally unbounded robust classifiers exist. For this, we rely on the existence of averagecase hard functions, requiring no cryptographic assumptions. Second, we show hardtorobustlylearn classification tasks in the largeperturbation regime. Namely, we show that even though an efficient classifier that is very robust (namely, tolerant to large perturbations) exists, it is computationally hard to learn any nontrivial robust classifier. Our first construction relies on the existence of oneway functions, a minimal assumption in cryptography, and the second on the hardness of the learning parity with noise problem. In the latter setting, not only does a nonrobust classifier exist, but also an efficient algorithm that generates fresh new labeled samples given access to polynomially many training examples (termed as generation by Kearns et al. (1994)). Third, we show that any such counterexample implies the existence of cryptographic primitives such as oneway functions or even forms of publickey encryption. This leads us to a winwin scenario: either we can quickly learn an efficient robust classifier, or we can construct new instances of popular and useful cryptographic primitives.
Related Material


