Timezone: »

 
Poster
Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness
Avrim Blum · Omar Montasser · Greg Shakhnarovich · Hongyang Zhang

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #1036
in Poster Session 3 »
We present an oracle-efficient algorithm for boosting the adversarial robustness of barely robust learners. Barely robust learning algorithms learn predictors that are adversarially robust only on a small fraction $\beta \ll 1$ of the data distribution. Our proposed notion of barely robust learning requires robustness with respect to a ``larger'' perturbation set; which we show is necessary for strongly robust learning, and that weaker relaxations are not sufficient for strongly robust learning. Our results reveal a qualitative and quantitative equivalence between two seemingly unrelated problems: strongly robust learning and barely robust learning.
Keywords: Sample Complexity · Adversarial Robustness · boosting · Oracle complexity

Author Information

Avrim Blum (Toyota Technological Institute at Chicago)
Omar Montasser (Toyota Technological Institute at Chicago)
Greg Shakhnarovich (TTI-Chicago)
Hongyang Zhang (School of Computer Science, University of Waterloo)

More from the Same Authors