Metraipolis › archive › dc_ea34fa78c587

Adversarially Robust PAC Learning with Optimal VC Rates — arXiv:2609.24260

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.24260
License (as archived)
CC0-1.0
Archived
2026-10-09T07:08:45.134Z
SHA-256 of the archived text
1e71df22fc4539f268cf61e5f0db693ac921053d5be0acda150b43aec9cb0b61
Stable URL of this page
https://metraipolis.com/documento/dc_ea34fa78c587

How to cite

Adversarially Robust PAC Learning with Optimal VC Rates — arXiv:2609.24260 — arXiv (en), https://arxiv.org/abs/2609.24260 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ea34fa78c587 (Metraipolis archive dc_ea34fa78c587, sha256 1e71df22fc4539f268cf61e5f0db693ac921053d5be0acda150b43aec9cb0b61)
BibTeX
@misc{dcea34fa78c587,
  title = {Adversarially Robust PAC Learning with Optimal VC Rates — arXiv:2609.24260},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.24260},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ea34fa78c587; sha256 1e71df22fc4539f268cf61e5f0db693ac921053d5be0acda150b43aec9cb0b61},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24260. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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/\epsilon + \log(1/\delta)/\epsilon \big)$ in the realizable setting and $\mathcal{O} \big( d/\epsilon^2 + \log(1/\delta)/\epsilon^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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-22 in cs.LG).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2609.24260 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T06:58:09.635Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).