An Optimal Agnostic PAC Algorithm
2026-08-06 • Machine Learning
Machine LearningArtificial IntelligenceData Structures and Algorithms
AI summaryⓘ
The authors study a type of machine learning where the goal is to find a rule that predicts binary outcomes as accurately as possible. They focus on classes of rules characterized by a complexity measure called VC dimension. They propose a learning method that, given enough data, can predict almost as well as the best possible rule in the class, with precise bounds on how much data is needed depending on the noise level. Their results confirm known lower limits on learning accuracy, showing their method is optimally efficient in terms of sample size.
agnostic PAC learningVC dimensionbinary classificationsample complexityrisk boundi.i.d. samplesstatistical learning theoryempirical risk minimizationprobability boundspattern recognition
Authors
Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
Abstract
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].