Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness
This work addresses adversarial robustness in machine learning, providing a foundational perspective that could impact all of ML/AI, though it appears incremental in building on existing barely robust learning concepts.
The paper tackles the problem of boosting adversarial robustness for barely robust learners, which are robust only on a small fraction of the data distribution, by introducing an oracle-efficient algorithm and showing a qualitative and quantitative equivalence between strongly robust and barely robust learning.
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 $β\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.