🤖 machine learning

Null Measurability at the Symmetrization Interface in VC Learning

This paper demonstrates that the Borel measurability requirement for ghost-gap suprema in the standard symmetrization proof of VC learning is stronger than necessary, showing instead that the relevant bad events are analytic and thus measurable in the completion of any finite Borel measure, a result formalized in Lean 4 that weakens the measurability hypotheses needed to establish PAC learnability.

Original authors: Dhruv Gupta

Published 2026-04-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Dhruv Gupta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize cats in photos. You have a huge library of possible "rules" (hypotheses) the robot could use to decide if an image is a cat. Some rules are simple, some are incredibly complex. The goal is to prove that if your library isn't too chaotic (has a finite "VC dimension"), the robot will eventually learn the right rule just by looking at a few examples.

For decades, mathematicians have had a standard proof for this, called Symmetrization. It's like a magic trick where you compare the robot's performance on a "training set" (photos it saw) against a "ghost set" (photos it hasn't seen yet). If the robot does much better on the training photos than the ghost photos, it's cheating (overfitting).

However, there's a hidden snag in this magic trick. To make the math work, the proof usually demands that the "bad event" (the moment the robot cheats) must be a Borel set. In the world of advanced math, a Borel set is a very well-behaved, tidy shape. It's like a perfect circle or a square.

The Problem:
The authors of this paper, Dhruv Gupta, realized that the standard proof is being too picky. It insists on a "perfectly tidy" shape for the bad event, but the math doesn't actually need that level of perfection. It's like insisting you can only cross a river if you have a pristine, marble bridge, when a sturdy, slightly rough wooden plank would actually get you across just fine.

The Discovery:
Gupta shows that for the specific "ghost gap" used in this proof, the bad event doesn't need to be a perfect Borel set. It just needs to be Null-Measurable.

Here is the analogy:

Borel Set: A shape you can draw with a ruler and compass. It's perfectly defined.
Analytic Set: A shape that is the "shadow" of a higher-dimensional object. It might be a bit fuzzy or complex, but it's still a real shape.
Null-Measurable: A shape that might be fuzzy, but if you try to measure it with a standard ruler (probability), it behaves just like a normal shape. It's "good enough" for the math to work.

Gupta proves that the "bad event" in the robot's learning process is always an Analytic set. Thanks to a famous mathematical tool called Choquet capacitability, we know that all Analytic sets are "Null-Measurable."

Why does this matter?

It's a Looser Rule: The paper proves that the "Borel" requirement is too strict. There are concept classes (libraries of rules) that are perfectly fine for learning but fail the "Borel" test because their bad events are "fuzzy" (Analytic but not Borel). Under the old rules, these libraries would be rejected as "unlearnable" just because of a technicality. Under Gupta's new rules, they are accepted.
It's Stable: The paper shows that if you take two "good" libraries and combine them (by patching them together or mixing them), the result is still "good" under this new, looser rule. You don't accidentally create a "bad" library just by combining good ones.
It's Verified by a Robot: The author didn't just write this on paper; they used a computer proof assistant called Lean 4 to check every single step. This ensures there are no human errors in the logic.

The Strict Separation:
To prove that the old rule was indeed too strict, Gupta built a specific example (a "witness"). He created a library of rules where the "bad event" is a shape that is Analytic but not Borel.

Under the old rules: This library is "illegal" because the bad event isn't a perfect Borel set.
Under the new rules: This library is "legal" because the bad event is Null-Measurable.
This proves that the new rule is strictly weaker (more inclusive) than the old one.

In Summary:
This paper is about cleaning up the foundation of machine learning theory. It says, "We've been requiring a diamond to build a house, but a high-quality brick works just as well and lets us build more houses." It relaxes the mathematical requirements for proving that a machine learning algorithm will work, making the theory applicable to a wider range of scenarios without breaking the math. The authors have even built a digital "safety net" (using Lean 4) to ensure this new foundation is rock solid.

1. Problem Statement

The paper addresses a subtle but critical measurability issue in the proof of the Fundamental Theorem of Statistical Learning (FTSL).

Context: The standard proof that finite VC dimension implies PAC learnability relies on the symmetrization argument (double sampling). This involves bounding the probability of a "bad event" where the "ghost" error (on a second sample) exceeds the training error by a certain margin.
The Issue: The bad event is defined by an existential quantifier over a concept class $\mathcal{C}$ . If $\mathcal{C}$ is uncountable, the union of measurable sets defining this event is not necessarily Borel measurable.
Current State: Recent work (Krapp and Wirth) has formalized the need for Borel measurability of the supremum of the "ghost-gap" function to ensure the proof holds mathematically.
The Gap: The author argues that requiring the bad event to be Borel is stronger than necessary. The symmetrization proof only requires the event to be measurable with respect to the completion of the product probability measure (i.e., null-measurable). The paper investigates whether this weaker condition is sufficient and stable under natural concept-class constructions.

2. Methodology

The paper employs tools from Descriptive Set Theory and Measure Theory, formalized within the Lean 4 proof assistant.

Theoretical Framework:
- Polish Spaces: The domain $X$ is assumed to be a Polish space (separable, completely metrizable) with its Borel $\sigma$ -algebra.
- Borel-Parameterized Classes: Concept classes are defined via a measurable evaluation map $e: \Theta \times X \to \{0,1\}$ , where $\Theta$ is a standard Borel space.
- Descriptive Hierarchy: The analysis tracks the complexity of the "bad event" through the hierarchy:
  1. Borel Witness Set: The set of parameters and samples satisfying the gap condition is Borel.
  2. Analytic Projection: The bad event is the projection of the Borel witness set onto the sample space. By Suslin's Theorem, this projection is an Analytic Set.
  3. Null-Measurability: By Choquet Capacitability, analytic sets in Polish spaces are universally measurable (measurable in the completion of any finite Borel measure).
Formalization: All main results, including the bridge from analytic sets to null-measurability, are formally verified in Lean 4. This serves not just as a check, but as a "forcing device" to ensure the regularity conditions are stated at the precise necessary level (distinguishing between MeasurableSet and NullMeasurableSet).

3. Key Contributions

A. The Borel–Analytic Bridge Theorem

The paper proves that for any Borel-parameterized concept class with a measurable target, the one-sided ghost-gap bad event is Analytic.

Result: Consequently, the event is null-measurable (measurable in the completion of the product measure) for every finite Borel measure.
Implication: This establishes that the Borel measurability of the supremum map (a condition required by Krapp and Wirth) is not necessary for the symmetrization proof to hold. The weaker NullMeasurableSet condition suffices.

B. Strict Separation Witness

The author constructs a specific counterexample to show that the gap between "Borel" and "Null-Measurable" is strict in this context.

Construction: A concept class $\mathcal{C}_A$ parameterized by an Analytic but non-Borel set $A \subseteq \mathbb{R}$ .
Result: The bad event for this class is Analytic and null-measurable, but not Borel.
Significance: This proves that the Borel condition (KW) is strictly stronger than the necessary condition (WBmeas) for the symmetrization route.

C. Closure Under Constructors

The paper demonstrates that the property of being "Null-Measurable" (specifically, satisfying the WellBehavedVCMeasTarget interface) is stable under natural operations used to build complex concept classes:

Patching: Combining classes based on a measurable routing function.
Interpolation: Fixed-region and countable interpolation of classes.
Fiber-Product Amalgamation: Merging classes based on a common parameter space.

Result: These operations preserve the weaker null-measurability condition, even though they might destroy Borel measurability.

D. Lean 4 Formalization

The results are fully formalized in Lean 4. The formalization includes:

The Choquet capacitability route from analytic sets to null-measurability.
The specific interface definitions (WellBehavedVC vs. WellBehavedVCMeasTarget).
Verification that the symmetrization proof works with the weaker interface.

4. Key Results

Theorem 3.1 (Borel–Analytic Bridge): For Borel-parameterized classes, the bad event is Analytic and thus universally measurable (null-measurable).
Theorem 4.1 (Strict Separation): There exists a concept class where the bad event is null-measurable but not Borel, proving the Borel condition is too strong.
Corollary 6.1 (Weakened Interface): In the realizable setting (where the target concept is in the class and is measurable), the standard symmetrization proof from finite VC dimension to PAC learnability only requires the Null-Measurable condition, not the Borel supremum condition.
Stability: The class of concept classes satisfying the null-measurable condition forms a robust algebra closed under patching, interpolation, and amalgamation.

5. Significance and Impact

Refining the Fundamental Theorem: The paper clarifies the exact measurability hypothesis needed for the VC dimension $\implies$ PAC learnability implication. It removes an unnecessary "Borel" constraint, allowing for a broader class of concept classes (those with analytic but non-Borel bad events) to be considered learnable under standard proofs.
Descriptive Set Theory in ML: It highlights the utility of descriptive set theory (Analytic sets, Suslin's theorem, Choquet capacity) in resolving foundational issues in statistical learning theory, moving beyond simple combinatorial arguments.
Formal Verification: By formalizing these results in Lean 4, the paper provides a rigorous, machine-checked foundation for learning theory. It demonstrates that formal methods can uncover subtle distinctions (like Borel vs. Null-measurable) that are often glossed over in informal textbook proofs.
Practical Implications: While the counterexamples involve pathological sets, the closure results suggest that many natural constructions of concept classes (which might inadvertently produce non-Borel bad events) are still valid for PAC learning proofs, provided the target is measurable.

Conclusion

Dhruv Gupta's paper successfully isolates the precise regularity condition required for the symmetrization step in VC learning. By proving that null-measurability (derived from the analytic nature of the bad event) is sufficient, the author weakens the hypotheses of the Fundamental Theorem of Statistical Learning. This work bridges the gap between classical empirical process theory and modern formal verification, providing a more accurate and robust mathematical foundation for learning theory.