{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.24260",
  "author_total": 2,
  "authors": [
    {
      "name": "Steve Hanneke"
    },
    {
      "name": "Amirreza Shaeiri"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/ahr5gjzs83e9e.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.24260",
  "fulltext_url": null,
  "id": "ahr5gjzs83e9e",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.24260",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "math.ST"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "arxiv",
      "stat.TH"
    ],
    [
      "openalex",
      "1702|Adversarial Robustness in Machine Learning"
    ]
  ],
  "openalex": "W7214043332",
  "pdf_url": "https://arxiv.org/pdf/2609.24260",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-21",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/ahr5gjzs83e9e.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:23:27Z",
      "native_id": "2609.24260",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.24260"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.ST",
      "subfield": "statistics"
    }
  ],
  "title": "Adversarially Robust PAC Learning with Optimal VC Rates",
  "title_text": "Adversarially Robust PAC Learning with Optimal VC Rates",
  "type": "preprint",
  "updated_at": "2026-10-30T12:23:33Z",
  "url": "https://research.draconitic.com/paper/ahr5gjzs83e9e",
  "venue": "arXiv",
  "versions": []
}