Adversarially Robust PAC Learnability of Real-Valued Functions
This addresses the challenge of adversarial robustness in regression for machine learning practitioners, providing theoretical guarantees for learnability, though it is incremental as it extends existing concepts to adversarial settings.
The paper tackles the problem of PAC learnability for real-valued functions under test-time adversarial attacks with arbitrary perturbation sets, showing that classes with finite fat-shattering dimension are learnable in realizable and agnostic settings, and convex classes are properly learnable, while non-convex classes may require improper learning.
We study robustness to test-time adversarial attacks in the regression setting with $\ell_p$ losses and arbitrary perturbation sets. We address the question of which function classes are PAC learnable in this setting. We show that classes of finite fat-shattering dimension are learnable in both realizable and agnostic settings. Moreover, for convex function classes, they are even properly learnable. In contrast, some non-convex function classes provably require improper learning algorithms. Our main technique is based on a construction of an adversarially robust sample compression scheme of a size determined by the fat-shattering dimension. Along the way, we introduce a novel agnostic sample compression scheme for real-valued functions, which may be of independent interest.