Adversarially Robust PAC Learnability of Real-Valued Functions

Idan Attias, Steve Hanneke
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:1172-1199, 2023.

Abstract

We study robustness to test-time adversarial attacks in the regression setting with ℓ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 the 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-attias23a, title = {Adversarially Robust {PAC} Learnability of Real-Valued Functions}, author = {Attias, Idan and Hanneke, Steve}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {1172--1199}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/attias23a/attias23a.pdf}, url = {https://proceedings.mlr.press/v202/attias23a.html}, abstract = {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 the 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.} }
Endnote
%0 Conference Paper %T Adversarially Robust PAC Learnability of Real-Valued Functions %A Idan Attias %A Steve Hanneke %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-attias23a %I PMLR %P 1172--1199 %U https://proceedings.mlr.press/v202/attias23a.html %V 202 %X 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 the 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.
APA
Attias, I. & Hanneke, S.. (2023). Adversarially Robust PAC Learnability of Real-Valued Functions. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:1172-1199 Available from https://proceedings.mlr.press/v202/attias23a.html.

Related Material