An Optimal Agnostic PAC Algorithm

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 of Pattern Recognition, Springer, 1996].

Source: arXiv:2608.06363v1 - http://arxiv.org/abs/2608.06363v1 PDF: https://arxiv.org/pdf/2608.06363v1 Original Link: http://arxiv.org/abs/2608.06363v1