Search papers, labs, and topics across Lattice.
This paper constructs a learner that achieves the statistically optimal risk bound for agnostic PAC learning with finite VC dimension, demonstrating that the sample complexity can be precisely characterized. The authors derive a bound that holds with high probability, showing that the learner's risk converges to the optimal risk plus a term dependent on the sample size and VC dimension. This result not only matches existing lower bounds but also provides a comprehensive understanding of the sample complexity in this learning framework.
Achieving the statistically optimal risk bound in agnostic PAC learning finally clarifies the sample complexity landscape, matching lower bounds precisely.
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<\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/\delta))}{n}} +\frac{d+\log(1/\delta)}{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].
