Null Measurability at the Symmetrization Interface in VC Learning

A new paper from Dhruv Gupta revisits a foundational assumption in statistical learning theory: the measurability of ghost-gap suprema in the VC dimension symmetrization proof. The standard route to PAC learnability requires Borel measurability, but Gupta shows this is stronger than necessary. At the one-sided ghost-gap interface actually used, the bad event—where a hypothesis's ghost error exceeds its training error by at least ε/2—is analytic, making it measurable in the completion of every finite Borel measure by Choquet capacitability. This weakens the measurability hypothesis needed for the symmetrization route from finite VC dimension to PAC learnability in the realizable setting.

Gupta goes further, constructing a concept class where the bad event is null-measurable but not Borel, establishing a strict separation from the Borel supremum condition. He also proves closure under patching, fixed and countable interpolation, and fiber-product amalgamation, showing the weaker regularity level is stable under natural concept-class constructors. All main results and the descriptive-set-theoretic infrastructure are formalized in Lean 4, providing a machine-checked foundation for these insights. This work tightens the theoretical underpinnings of VC learning, potentially simplifying future proofs and extending their applicability to broader classes of problems.