{"id":"arxiv/2609.24260","url":"https://arxiv.org/abs/2609.24260","tags":["stat.ML","cs.LG","math.ST"],"score":0,"title":"Adversarially Robust PAC Learning with Optimal VC Rates","domain":"stat.ML","source":"arxiv","authors":["Steve Hanneke","Amirreza Shaeiri"],"reviews":0,"subject":"stat.ML","summary":"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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-09-21","reactions":{}}