A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
2026-08-31 • Machine Learning
Machine Learning
AI summaryⓘ
The authors show that having a finite VC dimension and Borel measurable concepts isn't enough to ensure that all learning rules work well in the PAC sense, without needing extra mathematical assumptions like the Continuum Hypothesis. They build an example in standard set theory where a proper consistent learning rule fails badly, meaning it almost always makes errors no matter how much data it sees. This means some technical conditions assumed in the fundamental theorem of statistical learning really are necessary. Their work clarifies that these extra conditions can’t just be ignored.
Vapnik–Chervonenkis dimensionPAC learningBorel setsconsistent learning ruleproper learning ruleContinuum HypothesisZermelo–Fraenkel set theoryAxiom of Choicestatistical learning theorymeasurability
Authors
Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira Rodrigues
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.