We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over
X×{0,1}, as in classical PAC learning. However, given a perturbation map
U:X→2X known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation
z∈U(x) of most future examples
(x,y) drawn from the same underlying distribution. We determine the \emph{optimal}
U-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class
H of
VC dimension
d, we prove upper bounds of
O(d/ε+log(1/δ)/ε) in the realizable setting and
O(d/ε2+log(1/δ)/ε2) 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.