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].