Null Measurability at the Symmetrization Interface in VC Learning
For learning theorists, this paper clarifies the minimal measurability conditions needed for the standard symmetrization proof, showing that Borel measurability can be relaxed to null-measurability.
The authors show that the Borel measurability requirement for ghost-gap suprema in VC learning is unnecessarily strong; the bad event in the symmetrization proof is analytic and thus measurable in the completion of any finite Borel measure. They construct a concept class where the bad event is null-measurable but not Borel, and prove closure properties, weakening the measurability hypothesis for PAC learnability via symmetrization.
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" 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.