An Optimal Agnostic PAC Algorithm

Let Hsubseteq-1,+1X be a class of finite VC dimension d≥1. Writing L for the binary risk and L^*=minh∈ HL(h), we construct a learner achieving the statistically optimal risk bound: from an i.i.d. sample of size n, for every 0<δ≤ 1/2, with probability at least 1-δ, [ L(widehat h) ≤ L^*+ 7·108left( √fracL^*(d+log(1/δ))n +fracd+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"orfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].