Adversarially Robust PAC Learning with Optimal VC Rates
Abstract
We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over π³ Γ {0,1}, as in classical PAC learning. However, given a perturbation map π° : π³ β 2π³ known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation z β π°(x) of most future examples (x,y) drawn from the same underlying distribution. We determine the \emph{optimal} π°-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class β of VC dimension d, we prove upper bounds of πͺ ( d/Ξ΅+ log(1/Ξ΄)/Ξ΅) in the realizable setting and πͺ ( 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.
Related
- Adversarially Trained Linear Transformers Are Optimal Robust In-Context Learners for Gaussian Mixtures
- On the Gradient Heterogeneity Dynamics of Adversarially Robust Federated Regression
- Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
- Learning Optimal Robust-Pathwise Control of Elliptic Equations with Random Coefficients
- Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data
BibTeX
@misc{hanneke2026adversarially,
title = {{Adversarially Robust PAC Learning with Optimal VC Rates}},
author = {Steve Hanneke and Amirreza Shaeiri},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24260},
eprint = {2609.24260},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24260},
}
RIS
TY - UNPB
TI - Adversarially Robust PAC Learning with Optimal VC Rates
AU - Steve Hanneke
AU - Amirreza Shaeiri
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.24260
UR - https://arxiv.org/abs/2609.24260
AB - We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over π³ Γ {0,1}, as in classical PAC learning. However, given a perturbation map π° : π³ β 2^π³ known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation z β π°(x) of most future examples (x,y) drawn from the same underlying distribution. We determine the \emph{optimal} π°-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class β of VC dimension d, we prove upper bounds of πͺ ( d/Ξ΅+ log(1/Ξ΄)/Ξ΅) in the realizable setting and πͺ ( 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.
ER -