Timezone: »

Adversarially Robust PAC Learnability of Real-Valued Functions
Idan Attias · Steve Hanneke

Tue Jul 25 02:00 PM -- 04:30 PM (PDT) @ Exhibit Hall 1 #604
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.

Author Information

Idan Attias (Ben-Gurion University)
Steve Hanneke (TTIC)
Steve Hanneke

Steve Hanneke is a Research Assistant Professor at the Toyota Technological Institute at Chicago. His research explores the theory of machine learning: designing new learning algorithms capable of learning from fewer samples, understanding the benefits and capabilities of interactive machine learning, developing new perspectives on transfer learning and life-long learning, and revisiting the basic probabilistic assumptions at the foundation of learning theory. Steve earned a Bachelor of Science degree in Computer Science from UIUC in 2005 and a Ph.D. in Machine Learning from Carnegie Mellon University in 2009 with a dissertation on the theoretical foundations of active learning.

More from the Same Authors