Adversarially robust learning matches classical sample efficiency rates
Adversarially Robust PAC Learning with Optimal VC Rates
Machine Learning
Summary
This work studies teaching computers to correctly recognize things even when those things are slightly changed to trick the computer. The authors found that it is possible to train these robust computers using about the same amount of examples as usual, without needing extra data. They developed a simple new method to prove this, which could be useful in other areas too. This means making computers focus on worst-case changes can be done efficiently from a data perspective.
What this means in practice
- •For machine learning engineers: Design training processes that achieve adversarial robustness without needing more training samples than standard methods.
- •For cybersecurity teams: Build more reliable threat detection systems that maintain accuracy against adversarial changes without requiring extra data collection.
A theory result. No direct application yet.
Authors
Steve Hanneke, Amirreza Shaeiri
Abstract
We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over $\mathcal{X} \times \{0,1\}$, as in classical PAC learning. However, given a perturbation map $\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}}$ known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation $z \in \mathcal{U}(x)$ of most future examples $(x,y)$ drawn from the same underlying distribution. We determine the \emph{optimal} $\mathcal{U}$-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class $\mathcal{H}$ of $\operatorname{VC}$ dimension $d$, we prove upper bounds of $\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)$ in the realizable setting and $\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big)$ in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs \emph{no additional} distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.