cs.LGApr 27, 2026

Null Measurability at the Symmetrization Interface in VC Learning

Authors: Dhruv Gupta

Organizations: AI and Robotics Technology Park, Indian Institute of Science, Bengaluru

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" 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.

Explore similar work

CardsList
  1. A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

    Aug 31, 2026Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira RodriguesProbability Measures

  2. Surprises in Proper Positive-Only Learning

    Jun 26, 2026Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1Binary ClassificationOptimal Sample Complexity