{"id":"arxiv/2608.06363","url":"https://arxiv.org/abs/2608.06363","tags":["cs.LG","cs.AI","cs.DS","math.ST"],"score":0,"title":"An Optimal Agnostic PAC Algorithm","domain":"cs.LG","source":"arxiv","authors":["Markus Engelund Mathiasen","Jian Qian","Nikita Zhivotovskiy"],"reviews":0,"subject":"cs.LG","summary":"Let $H\\subseteq\\{-1,+1\\}^X$ be a class of finite VC dimension $d\\ge1$. Writing $L$ for the binary risk and $L^*=\\min_{h\\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\\ sample of size $n$, for every $0<δ\\le 1/2$, with probability at least $1-δ$, \\[ L(\\widehat h) \\le L^*+ 7\\cdot10^8\\left( \\sqrt{\\frac{L^*(d+\\log(1/δ))}{n}} +\\frac{d+\\log(1/δ)}{n} \\right). \\] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-06","reactions":{}}