Source-linked AI summary
A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira Rodrigues
TL;DR
The paper asks whether the well-behavedness assumption and the Continuum Hypothesis are necessary for the finite-VC consistent PAC theorem. It constructs a ZFC counterexample and shows that a consistent learner can have true risk one at every sample size on samples of outer probability one. Thus, finite VC dimension and Borel concepts alone do not guarantee that every consistent learner is PAC.
Problem
Under suitable measurability assumptions, finite VC dimension implies that every proper consistent learner is PAC, but earlier counterexamples required the Continuum Hypothesis.
Method
The paper replaces the CH construction’s countable initial segments with an increasing chain of Borel null sets and carries out the construction in ZFC alone.
Results
True risk is one at every sample size on a set of samples of outer probability 1 for a suitable Borel probability measure and target concept.
Takeaways & Limitations
Finite VC dimension and Borel measurability of individual concepts do not suffice to ensure that every proper consistent learning rule is PAC.
Takeaways & Limitations
The construction does not show that its concept class lacks every PAC learning rule; it only exhibits one consistent rule that is not PAC.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper removes the Continuum Hypothesis from a known counterexample: in ZFC alone, a Borel concept class of VC dimension one has a consistent learner that is not PAC. For a suitable measure and target, this learner has true risk one at every sample size on a set of samples of outer probability one.
- Earlier constructions showed under CH that well-behavedness cannot be omitted, while subsequent partial results assumed Martin’s Axiom.
- The paper constructs in ZFC a concept class of Borel sets with VC dimension one and a consistent learning rule that is not PAC.
- True risk is one at every sample size on a set of samples of outer probability 1 for a suitable Borel probability measure and target concept.
- The result shows that finite VC dimension and individual Borel measurability do not suffice for consistent PAC learnability without well-behavedness.
2. Preliminaries
The preliminaries define concepts, traces, VC dimension, samples, consistency, true risk, and PAC learning, then state that finite VC dimension yields consistent PAC learnability under well-behavedness.
- A concept class is a collection of subsets of a Polish space, and a Borel class contains only Borel sets.
- The trace of a concept class on a finite set F is the collection of intersections H ∩ F over all concepts H in the class.
- A finite set is shattered when the class realizes every subset of it; VC dimension measures the largest size of a shattered finite set.
- In the realizable setting, a target concept labels each point, and a proper learner outputs a hypothesis from the same concept class.
- Consistency requires the learner’s output to agree with every label in the sample, while true risk measures disagreement on an independent point drawn from the measure.
- Under finite VC dimension and well-behavedness, the fundamental theorem states that every consistent learning rule is PAC.
3. Proof of Theorem 1.1
The proof replaces the CH-based construction with an increasing chain of Borel null sets, then constructs a Borel concept class of VC dimension one and a proper consistent learner that is not PAC.
- Construction: The construction replaces CH-based countable initial segments with an increasing chain of Borel null sets indexed below add(N).The recursion is possible because unions of fewer than add(N) null sets remain null.
- Construction: A Borel probability measure is chosen so that the union Y of the chain has outer measure one.Every Borel superset of Y has measure one, yielding µ*(Y)=1.
- Concept class: The class C={∅, I}∪{Cα: α<add(N)} is Borel, forms a chain, and has VC dimension one.It shatters every singleton but no two-point set.
- Learner: The learner is proper and consistent: for every target concept and finite labeled sample, its output agrees with every sample label.The proof checks separately the targets ∅, Cβ, and I.
- Failure of PAC: For target I, every Cα is µ-null, and samples entirely in Y produce hypotheses with true risk one.Samples outside Y instead produce I and risk zero.
4. Conclusion
The construction establishes in ZFC alone that a Borel concept class of VC dimension one can admit a consistent learning rule that is not PAC. It also clarifies that finite VC dimension and individual Borel measurability do not by themselves yield consistent PAC learnability, while leaving PAC learnability by other rules unresolved.
- The result shows that finite VC dimension does not connect to consistent PAC learnability through combinatorial structure alone.The paper identifies measure-theoretic regularity as necessary for connecting VC trace bounds to probabilities of bad-sample events.
- Individual Borel measurability of concepts is insufficient to guarantee that every consistent learning rule is PAC.
- ZFC alone suffices to produce a counterexample to consistent PAC learnability for a Borel concept class of finite VC dimension.
Statements and declarations
The authors report no competing interests and no applicable data sharing because the article generated or analyzed no datasets. They also disclose using OpenAI’s GPT-5.6 Sol for several research and manuscript-support tasks.
- The authors declare no competing interests and state that data sharing is not applicable because no datasets were generated or analyzed.
- OpenAI’s GPT-5.6 Sol was used for brainstorming, proof drafting, bibliographic searches, proofreading, LaTeX editing, and manuscript revision.