An Optimal Agnostic PAC Algorithm

arXiv:2608.06363v1 Announce Type: cross Abstract: Let Hsubseteq{-1,+1}^X be a class of finite VC dimension dge1. Writing L for the binary risk and L^=min_{hin 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<eltale 1/2, with probability at least 1-elta, [ L(widehat h) le L^+ 7dot10^8left( sqrt{frac{L^(d+log(1/elta))}{n}} +frac{d+log(1/elta)}{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, Gyorfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Source: arXiv cs.AI | 2026-08-07