Null Measurability at the Symmetrization Interface in VC Learning
Dhruv Gupta · 2026
Read Null Measurability at the Symmetrization Interface in VC Learning by Dhruv Gupta (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25028.txt.
Introduction
Gupta shows Borel measurability is stronger than necessary at the symmetrization interface in VC learning. For Borel-parameterized classes on a Polish domain, the bad event of excess ghost error over training error is analytic. He constructs a concept class with a bad event that is null-measurable yet not Borel, separating it from the Borel supremum condition. He proves closure under patching, interpolation and fiber-product merging. In the realizable setting, the results weaken the hypothesis needed to reach PAC learnability from finite VC dimension.
Catalog record
| CREATOR | Dhruv Gupta |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30515 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25028
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Null Measurability at the Symmetrization Interface in VC Learning Dhruv Gupta Abstract Recent work revisiting measurability in the fundamental theorem of statistical learning imposes Borel measurability of ghost-gap suprema. We show that, at the one-sided ghost-gap interface actually used by the standard symmetrization proof, this requirement is stronger than necessary. For any Borel-parameterized concept class on a Polish domain, the bad event “there exists a hypothesis whose ghost empirical error exceeds its training empirical error by at least ε / 2 \varepsilon/2 ” is analytic. By Choquet capacitability, it is therefore measurable in the completion of every finite Borel measure. We then construct a concept class whose bad event is null-measurable but not Borel, giving a strict separation from the Borel supremum condition. Finally, we prove closure under patching, fixed and countable interpolation, and fiber-product amalgamation, showing that the weaker regularity level is stable under natural concept-class constructors. In the realizable setting, where targets belong to the class and are measurable, these results weaken the measurability hypothesis needed by the symmetrization route from finite VC dimension to PAC learnability. The main results and the descriptive-set-theoretic infrastructure used by them are formalized in Lean 4. 1 Introduction The fundamental theorem of statistical learning identifies finite VC dimension as the exact combinatorial criterion for distribution-free PAC learnability in binary classification. The classical implication from finite VC dimension to learnability proceeds through double sampling and symmetrization: one controls a bad event on pairs of samples and then bounds its probability using the growth function and Sauer–Shelah estimates [ 21 , 1 , 15 , 17 , 16 ] . The proof is elementary in its combinatorial core, but it hides a measurability issue. The bad event is defined by an existential quantifier over an often uncountable concept class, and an uncountable union of measurable sets need not be Borel. Measurability problems of this kind are classical in empirical process theory. Pollard’s permissibility condition, Dudley’s image-admissible Suslin classes, and the framework of van der Vaart and Wellner all record ways to keep empirical-process suprema and outer-probability arguments mathematically meaningful [ 14 , 5 , 19 , 20 ] . Recent work of Krapp and Wirth revisits the fundamental theorem from this perspective and extracts explicit measurability assumptions for the learning-theoretic proof, with further applications to tame model theory [ 10 ] . Their intervention is important: it turns a tacit side condition in textbook proofs into a mathematical object. This paper makes a more local point. The one-sided ghost-gap event actually used by the standard symmetrization argument does not need to be Borel. It is enough that the event be measurable in the completion of the relevant product probability measure. In Lean 4 terminology [ 4 ] , the correct event-level hypothesis is NullMeasurableSet , not MeasurableSet . This weakening is not merely cosmetic. It admits Borel-parameterized classes whose ghost bad events are analytic but not Borel, and it is stable under the same constructor operations that naturally build larger classes from smaller ones. The mechanism is simple. Suppose that \Theta is a standard Borel space and that e:\Theta\times\mathcal{X}\to\{0,1\} is jointly measurable. For \theta\in\Theta , write e_{\theta}(x)=e(\theta,x) and let \mathcal{C}=\{e_{\theta}:\theta\in\Theta\} . For a target c , sample size m , and threshold \varepsilon , the witness set W_{e,c,m,\varepsilon}=\{(\theta,S,T):\widehat{L}_{T}(e_{\theta},c)-\widehat{L}_{S}(e_{\theta},c)\geq\varepsilon/2\} is Borel because it is a superlevel set of a finite sum of measurable functions. Its projection to (S,T) is the bad event. Suslin’s theorem says that this projection is analytic, and Choquet capacitability implies that analytic sets in Polish spaces are universally measurable. Thus the bad event is null-measurable under every finite Borel measure. The proof path is jointly measurable evaluator \displaystyle\Longrightarrow\text{Borel witness graph} \displaystyle\Longrightarrow\text{analytic bad event}\Longrightarrow\text{null-measurable bad event}. The descriptive-set-theoretic step is standard, but its placement is the point. Earlier empirical-process regularity conditions package this phenomenon globally through permissibility or image-admissible Suslin hypotheses. Krapp and Wirth package it through Borel measurability of gap maps. We isolate the precise event-level regularity used by the VC symmetrization proof and formalize it as an interface. This also clarifies what is, and is not, a new mathematical claim in this paper. The facts that analytic sets are universally measurable and that Borel projections are analytic are classical [ 18 , 3 , 8 ] . The contribution here is the localization of those facts at the one-sided symmetrization interface, the strict concept-class witness against the Borel condition, the closure algebra for Borel-parameterized constructors, and the Lean formalization certifying the translation. Our main contributions are as follows. (1) We prove a Borel–analytic bridge theorem for one-sided ghost-gap bad events of Borel-parameterized concept classes. (2) We construct a strict separation witness: a singleton concept class over an analytic non-Borel set whose one-sided ghost bad event is analytic and null-measurable but not Borel. (3) We prove closure under patching, fixed and countable interpolation, and fiber-product amalgamation. (4) We spell out the resulting weakened measurability interface for the realizable symmetrization route from finite VC dimension to PAC learnability. (5) We give a Lean 4 formalization of the main results, including the Choquet-capacitability route from analytic sets to null-measurability [ 7 ] . 1 1 1 Code and Lean kernel available at https://github.com/Zetetic-Dhruv/formal-learning-theory-kernel/tree/v3.3.0-paper . Two boundaries are important. First, our positive bridge is stated for measurable targets. This is the natural interface for realizable PAC learning, where the target belongs to the concept class and hypotheses are measurable. Extending the bridge to arbitrary nonmeasurable targets would require a different argument. Second, we do not claim to reprove every equivalent form of the fundamental theorem. In particular, the sample-compression direction associated with Moran and Yehudayoff is orthogonal to the measurability interface studied here [ 12 ] . 2 Setting and regularity notions Let (\mathcal{X},\mathcal{B}) be a measurable space. A binary concept is a function h:\mathcal{X}\to\{0,1\} , and a concept class is a set \mathcal{C}\subseteq\{0,1\}^{\mathcal{X}} . For a sample S=(x_{1},\ldots,x_{m})\in\mathcal{X}^{m} and target concept c:\mathcal{X}\to\{0,1\} , define the empirical zero-one error \widehat{L}_{S}(h,c)=\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}[h(x_{i})\neq c(x_{i})] for m>0 , and set the empty-sample empirical average to 0 when convenient. For a pair of samples p=(S,T)\in\mathcal{X}^{m}\times\mathcal{X}^{m} , define the one-sided ghost gap \Gamma^{c}_{h}(p)=\widehat{L}_{T}(h,c)-\widehat{L}_{S}(h,c). The corresponding one-sided bad event is E_{\mathcal{C},c,m,\varepsilon}=\{p\in\mathcal{X}^{m}\times\mathcal{X}^{m}:\exists h\in\mathcal{C}\;\Gamma^{c}_{h}(p)\geq\varepsilon/2\}. Definition 2.1 (Event-level null-measurability) . Let \mu be a probability measure on \mathcal{X} , and let \mu^{2m} denote the product measure on \mathcal{X}^{m}\times\mathcal{X}^{m} . (i) \mathrm{WB}(\mathcal{C}) holds if, for every probability measure \mu , every target c:\mathcal{X}\to\{0,1\} , every m\in\mathbb{N} , and every \varepsilon>0 , the event E_{\mathcal{C},c,m,\varepsilon} is measurable in the completion of \mu^{2m} . (ii) \mathrm{WB}_{\mathrm{meas}}(\mathcal{C}) holds if the same condition is required only for measurable targets c . In the Lean development, the unrestricted condition is WellBehavedVC ; the measurable-target variant is WellBehavedVCMeasTarget . The distinction matters only when one quantifies over arbitrary targets. In the realizable setting, if c\in\mathcal{C} and all concepts in \mathcal{C} are measurable, then c is measurable and \mathrm{WB}_{\mathrm{meas}} is the relevant interface. We compare this event-level condition to a Borel-level supremum condition. Define G_{\mathcal{C},c,m}(p)=\sup_{h\in\mathcal{C}}\Gamma^{c}_{h}(p), where the supremum is understood over the finite grid of possible empirical-gap values. The Lean development uses the finite-grid representation to avoid relying on non-attained suprema. Definition 2.2 (Borel ghost-gap condition) . We write \mathrm{KW}(\mathcal{C}) if for every target c and every m\in\mathbb{N} , the map p\mapsto