An Optimal Agnostic PAC Algorithm

Abstract

Let $H\subseteq \{-1,+1{\}}^X$ be a class of finite VC dimension $d\ge 1$. Writing $L$ for the binary risk and $L^{\ast }={\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<\delta \le 1/2$, with probability at least $1-\delta$, \[ 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^{\ast }$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

18 pages