Adversarially Robust PAC Learning with Optimal VC Rates

arXiv:2609.24260v1 Announce Type: cross Abstract: We study the problem of adversarially robust PAC learning. In this framework, the learner observes independent samples from an unknown distribution over X imes {0,1}, as in classical PAC learning. However, given a perturbation map U : X o 2^{X} known to the learner, the goal is to output, with high probability, a predictor that correctly classifies every perturbation z in U(x) of most future examples (x,y) drawn from the same underlying distribution. We determine the optimal U-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class H of operatorname{VC} dimension d, we prove upper bounds of O ig( d/epsilon + log(1/elta)/epsilon ig) in the realizable setting and O ig( d/epsilon^2 + log(1/elta)/epsilon^2 ig) 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 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 binomial-bagging. We believe that binomial-bagging and its analysis may be of independent interest.

Source: arXiv cs.LG | 2026-09-22