💬 NLP

Lean Formalization of Generalization Error Bound by Rademacher Complexity and Dudley's Entropy Integral

This paper presents a formalization in Lean 4 of generalization error bounds based on Rademacher complexity and Dudley's entropy integral, featuring a mechanically verified pipeline from measure-theoretic foundations to high-probability uniform deviation bounds and their application to linear predictors.

Original authors: Sho Sonoda, Kazumi Kasaura, Yuma Mizuno, Kei Tsukamoto, Naoto Onda

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sho Sonoda, Kazumi Kasaura, Yuma Mizuno, Kei Tsukamoto, Naoto Onda

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 a chef who has just invented a new recipe. You've cooked it 100 times in your kitchen (the training data) and it tasted perfect every time. But you want to know: if you cook this same recipe for a million strangers at a restaurant (the test data), will it still taste good?

In the world of machine learning, this is called the Generalization Problem. The paper you are asking about is a rigorous, computer-checked proof that helps us answer this question with mathematical certainty.

Here is the story of the paper, broken down into simple concepts and analogies.

1. The Problem: The "Kitchen vs. Restaurant" Gap

When a computer learns, it tries to find a rule (a hypothesis) that fits the data it sees.

Training Error: How well the rule fits the data it has already seen (your 100 kitchen trials).
Test Error: How well the rule works on new data it hasn't seen yet (the restaurant customers).

The danger is overfitting. This is like a chef who memorizes the exact taste of their 100 trials but fails to understand the principles of cooking. If they encounter a slightly different ingredient at the restaurant, the dish fails. We need a way to guarantee that the "kitchen success" translates to "restaurant success."

2. The Tool: Rademacher Complexity (The "Coin Flip Test")

To measure how likely a recipe is to overfit, mathematicians use a tool called Rademacher Complexity.

Imagine you have a bag of coins. You flip them, and they land on Heads (+1) or Tails (-1) completely at random.

The Test: You ask your recipe (the learning algorithm), "Can you predict these random coin flips?"
The Logic: If your recipe is a simple, robust rule, it shouldn't be able to predict random noise. It should get about 50% right, just by chance.
The Red Flag: If your recipe is too complex (like a chef who memorized every single detail), it might accidentally "find a pattern" in the random coin flips and predict them better than chance.

Rademacher Complexity measures exactly how well a model can "cheat" by fitting random noise. The lower this number, the more likely the model will generalize well to new data.

3. The Achievement: The "Digital Double-Check"

The authors of this paper didn't just write these math proofs on paper; they built them inside a computer program called Lean 4.

Think of Lean 4 as a super-strict, unblinking editor.

The Old Way: A mathematician writes a proof on paper. A human reviewer reads it. If the human misses a tiny logical gap, the proof might be accepted even if it's slightly wrong.
The New Way (This Paper): The authors fed their entire proof into Lean. The computer checked every single step, every definition, and every assumption. If there was even a tiny missing link (like "Is this function measurable?"), the computer would reject it.

The paper claims to have built a mechanically verified pipeline. It starts with the basic definitions, runs through a "symmetrization" trick (a clever mathematical shuffle), and ends with a high-confidence guarantee that the test error won't be much worse than the training error.

4. The Big Hurdle: The "Infinite Library" Problem

In the real world, machine learning models often have infinite possibilities (like a continuous range of numbers for weights).

The Problem: In math, it's easy to check a finite list of items (like 100 recipes). It's much harder to check an infinite list. In computer terms, checking the "maximum" of an infinite list can sometimes break the rules of logic (measurability issues).
The Paper's Solution: The authors created a clever "bridge." They proved the math first for a countable (finite or listable) set of hypotheses. Then, they showed that for many real-world models (which are "separable" topological spaces), you can approximate the infinite set using a countable dense subset (like using a very fine grid to approximate a smooth curve).
The Analogy: Imagine trying to measure the height of every possible person in the world. It's impossible to measure everyone. But if you measure every person who is exactly 1cm apart in height, you can mathematically prove that your measurement covers everyone else with high precision. The paper formalized this "grid" trick so the computer accepts it.

5. The Results: What Did They Prove?

Once the "engine" was built, they drove it through three specific scenarios to show it works:

Linear Predictors with $\ell_2$ Regularization: This is like a model that is forced to keep its "ingredients" (weights) small and balanced. The paper proved the standard math bound for this.
Linear Predictors with $\ell_1$ Regularization: This forces the model to be "sparse" (using only a few ingredients). They proved the bound for this, which involves a slightly different calculation (involving the square root of the number of features).
Dudley's Entropy Integral: This is a more advanced, general tool. Imagine you have a very messy, complex shape. Instead of measuring the whole thing, you cover it with smaller, simpler shapes (like covering a bumpy rock with smooth pebbles). The paper formalized how to calculate the complexity based on how many "pebbles" you need to cover the shape.

Summary

This paper is a foundational engineering feat.

What they did: They took complex, textbook theories about how machine learning models generalize (Rademacher complexity) and translated them into a language a computer can verify with 100% certainty.
Why it matters: It removes the "human error" from the most critical safety guarantees of AI. It proves that if you follow these specific mathematical rules, your model won't just memorize the past; it will actually learn for the future.
The Metaphor: They didn't just write a recipe for a safe cake; they built a robot that checks every single ingredient and step of the recipe to ensure the cake will never collapse, no matter who eats it.

Technical Summary: Lean Formalization of Generalization Error Bound by Rademacher Complexity and Dudley's Entropy Integral

Problem Statement

The central challenge addressed is the formal verification of generalization performance in machine learning. Specifically, the authors aim to derive theoretical estimates of test error (population risk) from training error (empirical risk) using a measure-theoretic framework. While classical approaches rely on Vapnik–Chervonenkis (VC) dimension, these are often data-independent and tailored to binary classification. Modern learning theory increasingly utilizes Rademacher complexity, which provides sharp, data-dependent bounds applicable to real-valued losses and diverse function classes (e.g., deep learning, kernel methods). However, formalizing these arguments in proof assistants is difficult due to the need for rigorous handling of measurability (particularly for suprema over uncountable hypothesis classes), product measures, and concentration inequalities.

Methodology

The authors formalize the generalization error bound in Lean 4, leveraging the Mathlib library's extensive measure-theoretic probability infrastructure. The development follows the standard "symmetrization + bounded differences" pipeline found in textbooks (e.g., Mohri et al., Wainwright) but adapts it to the constraints of formal verification:

Measure-Theoretic Setup: The framework models data generation via a probability space $(\Omega, m_\Omega, \mu)$ and a random variable $X: \Omega \to \mathcal{X}$ . Samples are modeled as functions $\omega: \text{Fin } n \to \Omega$ , pushed forward to obtain $S = X \circ \omega$ .
Core Definitions:
- Rademacher Complexity: Defined for both empirical (over a fixed sample $S$ ) and expected (over the product measure $\mu^n$ ) cases. The empirical version averages over all sign vectors $\sigma \in \{-1, 1\}^n$ .
- Uniform Deviation: Defined as the supremum of the absolute difference between empirical and population means over a hypothesis class $F = \{f_i\}_{i \in \iota}$ .
Symmetrization: A formal theorem (abs_symmetrization_equation) replaces the supremum of differences between two independent samples with an average over sign-flipped sums, linking uniform deviation to Rademacher complexity.
Concentration: The authors prove a McDiarmid inequality from scratch within Lean. They establish that the uniform deviation functional satisfies the bounded-differences property (changing one sample point alters the value by at most $2b/n$ ), allowing the derivation of high-probability tail bounds.
Handling Uncountable Index Sets: A critical technical hurdle is the measurability of suprema over uncountable index sets $\iota$ $ι$ . Mathlib provides measurability for countable indices but not automatically for uncountable ones. The authors resolve this by:
- First proving theorems for countable index sets.
- Extending results to separable topological index sets via a countable dense reduction. This involves proving that for continuous functions, the supremum over a separable space equals the supremum over a countable dense subset, provided continuity is preserved under integration (ensured by uniform domination).

Key Contributions

The paper presents the first systematic formalization of generalization analysis via Rademacher complexity. The specific contributions include:

Reusable Formal Infrastructure: A mechanically checked pipeline covering empirical/expected Rademacher complexity, symmetrization, bounded-differences analysis, and McDiarmid's inequality.
Measurability Resolution: A reusable mechanism for lifting results from countable hypothesis classes to separable topological parameter spaces. This explicitly packages the sufficient conditions (separability, first-countability, uniform domination, and continuity under integration) required to make uncountable suprema measurable, a step often implicit in informal proofs.
Formalized Concentration Tools: A full proof of McDiarmid's inequality and supporting lemmas for maximal inequalities, Massart's lemma, and covering numbers.
Worked Applications:
- Linear Predictors: Formalization of standard $O(1/\sqrt{n})$ bounds for $\ell_2$ -regularized predictors and $O(\sqrt{\log(d)/n})$ bounds for $\ell_1$ -regularized predictors.
- Dudley's Entropy Integral: A formalization of the Dudley-type bound relating Rademacher complexity to covering numbers via a chaining construction. This required defining empirical pseudo-metrics and handling the transition from discrete chaining sums to integral bounds.

Results

The formalization yields mechanically verified versions of standard learning-theoretic bounds:

Expected Bound: $E[\text{UD}_n(F)] \leq 2 R_n(F)$ , where $R_n(F)$ is the Rademacher complexity.
High-Probability Bound: For any $\delta \in (0, 1)$ , with probability at least $1-\delta$ :
$\text{UD}_n(F) \leq 2 R_n(F) + b \sqrt{\frac{2 \log(1/\delta)}{n}}$
Specific Bounds: The repository provides concrete proofs for the empirical Rademacher complexity of linear predictors under $\ell_2$ and $\ell_1$ constraints, as well as the Dudley entropy integral bound.

Significance and Claims

The authors position this work as a foundational step toward trustworthy, certified machine learning theory.

Bridging Theory and Verification: The work demonstrates that modern, measure-theoretic learning theory (which relies on product measures, integrability of envelopes, and concentration) can be formalized in a proof assistant without resorting to overly simplified discrete proxies.
Clarification of Implicit Assumptions: A primary contribution is the explicit identification of the conditions required to handle uncountable hypothesis classes. The formalization isolates the "countable-dense reduction" and the specific continuity/integrability hypotheses needed, which are often glossed over in standard textbooks.
Modularity: The development is designed so that the abstract Rademacher pipeline can be reused. Concrete bounds become "executable corollaries" obtained by instantiating the function class and discharging specific analytic estimates (e.g., norm constraints).
Comparison to Prior Work: Unlike previous formalizations that were limited to finite hypothesis classes (e.g., Bagnall & Stewart) or specific algorithmic cases (e.g., decision stumps), this work handles general, potentially uncountable, function classes with real-valued losses.

The paper concludes that while the mathematical bounds themselves are classical, the formalization clarifies the precise logical structure and side conditions necessary for their validity in a rigorous setting, providing a foundation for future extensions such as Lipschitz contraction inequalities and connections to Gaussian complexity.