A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
Abstract
The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on [0,1] of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.
Related
- Finite Borel asymptotic dimension of bounded-to-one commutative monoid actions
- Manifold Hypothesis: Conditional Certificates and Consistent Intrinsic Dimension Estimation
- The proper geometric dimension of the mapping class groups of non-orientable surfaces with punctures
- Superdiffusive central limit theorem for a class of driven diffusive systems at the critical dimension
- Decomposing A Neural Learner
BibTeX
@misc{campos2026borel,
title = {{A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC}},
author = {Mateus Jesus de Arruda Campos and Gabriel Fernandes and Vinicius de Oliveira Rodrigues},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30246},
eprint = {2608.30246},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30246},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
AU - Mateus Jesus de Arruda Campos
AU - Gabriel Fernandes
AU - Vinicius de Oliveira Rodrigues
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30246
UR - https://arxiv.org/abs/2608.30246
AB - The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on [0,1] of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.
ER -