💬 NLP

AI4SLT: Empirical Processes in Lean 4 for Formal Statistical Learning Theory

This paper presents the first comprehensive Lean 4 formalization of statistical learning theory grounded in empirical processes, developed through a human-AI collaborative workflow to establish a reusable formal foundation that resolves implicit assumptions in standard textbooks and enables future machine learning theory developments.

Original authors: Yuanhe Zhang, Jason D. Lee, Fanghui Liu

Published 2026-06-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuanhe Zhang, Jason D. Lee, Fanghui Liu

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 computer to learn from data, like a student studying for a math exam. Statistical Learning Theory (SLT) is the rulebook that tells us why this student will likely pass the exam and how well they will do. It's the "physics" behind machine learning.

However, this rulebook is written in a very complex, high-level language (advanced mathematics). For decades, humans have read it, understood the big picture, and moved on. But because the proofs are so long and rely on subtle, hidden assumptions, it's easy to miss a tiny logical gap. It's like reading a recipe that says "mix until smooth" without defining what "smooth" actually means. If you try to build a robot chef based on that vague recipe, it might fail.

This paper, AI4SLT, is about building a perfect, unbreakable digital version of that rulebook using a tool called Lean 4. Think of Lean 4 as a super-strict proofreader that refuses to accept a single vague word. If a step in the logic isn't explicitly defined, Lean 4 stops and says, "I can't do that."

Here is what the authors did, explained through simple analogies:

1. The Human-AI Team: The Architect and the Mason

The authors didn't just ask an AI to "write the code." They used a collaborative workflow:

The Humans (Architects): They looked at the complex math textbooks and designed the strategy. They said, "We need to prove this specific part first, and here is the plan."
The AI (The Mason): The AI (specifically Claude Code) took that plan and did the heavy lifting of writing the actual code, filling in the tiny, tedious logical steps.
The Result: They built a massive library of about 30,000 lines of code. This is like constructing a skyscraper from the ground up, brick by brick, where every single brick has been inspected by a robot to ensure it fits perfectly.

2. Building the Foundation: The "Gaussian Toolbox"

To prove that machine learning works, you need to understand how random noise behaves. The paper built a complete toolbox for this, which had never been done before in a computer-verifiable way.

The Analogy: Imagine you are trying to predict the weather. You need to understand how wind, rain, and temperature interact. The authors built the "wind," "rain," and "temperature" sensors from scratch inside the computer.
What they built: They formalized complex mathematical tools like Gaussian Lipschitz concentration and Dudley's entropy integral.
- Simple translation: These tools help us calculate the "worst-case scenario" for how much a learning algorithm might mess up due to random luck. The paper proved that even in the worst case, the algorithm stays within a predictable, safe boundary.

3. The "Chaining" Trick: Climbing a Mountain

One of the hardest parts of the math is called Dudley's Entropy Integral.

The Analogy: Imagine you need to climb a very tall, foggy mountain (the "empirical process"). You can't see the top.
The Old Way: Textbooks often say, "Just assume you can see the top."
The Paper's Way: They built a ladder of platforms (called "chaining"). You don't jump to the top; you jump from a small platform to a slightly higher one, then to a higher one, all the way up.
The Achievement: The authors formalized this entire ladder system in Lean 4. They proved that if you take these small, safe jumps, you can mathematically guarantee you won't fall off the mountain. This allows them to predict exactly how much data you need to learn a specific task.

4. Testing the Engine: The Least Squares Test

Once the toolbox was built, they tested it on a real-world problem: Least Squares Regression (a common way to draw a line through a set of dots).

The Result: They used their new, super-strict digital rulebook to prove that this method works, and they calculated the exact speed at which it learns.
Why it matters: They didn't just say "it works." They proved how fast it works, down to the smallest detail, and showed that their method achieves the best possible speed (minimax rate) for these types of problems.

5. The Hidden Benefit: Finding the "Ghost" Assumptions

The most surprising part of the paper is what happened during the process.

The Analogy: When you try to build a house with a robot that demands perfect instructions, you realize your original blueprints were missing things like "the door needs a hinge" or "the floor needs to be level."
The Discovery: The authors found that standard math textbooks often leave out tiny, crucial details (like whether a function is "measurable" or "continuous"). The AI couldn't proceed until these were fixed.
The Outcome: By forcing the computer to check every line, they cleaned up the theory, making it more rigorous and exposing hidden assumptions that humans had been glossing over for years.

Summary

This paper is the first time someone has taken the complex, abstract "rulebook" of machine learning theory and rebuilt it entirely inside a computer system that checks every single logical step. They used a team of humans to design the plan and AI to build the structure. The result is a verified, error-free foundation that proves machine learning algorithms work, explains exactly how fast they learn, and fixes the hidden holes in the original mathematical theories.

Technical Summary: AI4SLT: Empirical Processes in Lean 4 for Formal Statistical Learning Theory

Problem Statement

Statistical Learning Theory (SLT) has successfully guided machine learning progress for decades, providing foundational concepts like bias-variance trade-offs and regularization. However, as models evolve into complex architectures (e.g., deep neural networks, large language models), contemporary theoretical analyses have become increasingly intricate, relying on advanced mathematical tools from functional analysis and statistical physics. This complexity strains human verification, making it difficult to track logical dependencies and verify intermediate lemmas at scale.

Furthermore, core techniques in SLT, such as concentration inequalities and covering arguments, lack a structured, machine-readable library, limiting their reusability. While interactive theorem provers like Lean 4 offer a path to machine-checkable correctness, existing formalizations in machine learning are limited to specific areas (e.g., reinforcement learning, optimization) or simplified settings (e.g., generalization bounds via Rademacher complexity over entire function classes). A comprehensive formalization of the localized empirical process framework—which is essential for deriving sharp minimax rates in high-dimensional and nonparametric settings—remains absent. This framework requires rigorous handling of measurability, integrability, and topological assumptions that are often left implicit in standard textbooks.

Methodology

The authors present AI4SLT, the first comprehensive formalization of SLT grounded in empirical process theory within Lean 4. The project was executed using a human-AI collaborative workflow:

Human Role: Mathematicians designed proof strategies, analyzed the existing Mathlib infrastructure, decomposed complex theorems into manageable lemmas, and verified the consistency of statements.
AI Role: AI agents (specifically Claude Code with Opus-4.5) executed tactical proof construction, filling in details based on structured specifications.

The workflow involved a structured specification protocol (TASK.md) containing target statements, infrastructure pointers, formalization-oriented proof plans, and hard boundaries. The process emphasized iterative refinement, where AI failures were used to identify implicit assumptions left by humans, leading to convergent rather than open-ended collaboration. The entire project spanned approximately 500 hours of supervised development, resulting in ~30,000 lines of Lean 4 code compiled without sorry (unproven goals) or custom axioms.

Key Contributions

1. Gaussian Lipschitz Concentration Toolbox

The authors constructed a complete formal development of Gaussian Lipschitz concentration, a foundational tool in high-dimensional probability. This required building a substantial infrastructure from scratch, including:

Efron-Stein Inequality: Formalized with a universal transfer lemma to handle coordinate-wise updates with distinct distributions.
Gaussian Poincaré Inequality: Derived using Efron-Stein's infrastructure and Taylor expansion bounds.
Density Arguments: Formalized the extension of inequalities from smooth, compactly supported functions ( $C^\infty_c$ ) to general Lipschitz and $C^1$ classes via Gaussian Sobolev spaces ( $W^{1,2}$ ) and mollification techniques.
Gaussian Logarithmic Sobolev Inequality (LSI): Formalized the tensorization of the 1D LSI to the $n$ -dimensional case using entropy subadditivity.
Gaussian Lipschitz Concentration: Derived the final concentration bound using the Herbst argument and Chernoff's bound.

To the authors' knowledge, this constitutes the first formalization of the complete Gaussian analysis tools in any theorem prover.

2. Dudley's Entropy Integral for Sub-Gaussian Processes

The paper provides the first formalization of Dudley's entropy integral theorem for sub-Gaussian processes in Lean 4. This result bounds the expected supremum of a stochastic process by an integral involving metric entropy.

Formalization Challenges: The authors addressed the need for rigorous chaining arguments, decomposing the process into a telescoping sum over dyadic approximations. They formalized covering and packing numbers in metric spaces and handled the integration of extended non-negative reals ( $\mathbb{R}_{\ge 0}^\infty$ ) versus real-valued functions, ensuring the bound is applicable to general sub-Gaussian processes.

3. Application: Least-Squares Framework via Localized Empirical Processes

The authors demonstrated the practical utility of their infrastructure by developing a unified framework for least-squares regression based on the localized empirical process.

Master Error Bound: They formalized the critical inequality linking prediction error to the critical radius $\delta^*$ , derived from the localized Gaussian complexity.
Sharp Rates: The framework was applied to linear regression and $\ell_1$ -constrained regression (Lasso). By bounding covering numbers (using Euclidean reduction and Maurey's empirical method for $\ell_1$ -convex hulls), the authors obtained sharp rates up to the minimax level, recovering results such as $O(\sigma^2 r/n)$ for linear regression and $O(R\sqrt{\log d/n})$ for high-dimensional sparse regression.

4. Human-AI Collaborative Formalization Paradigm

The paper details a methodology for large-scale formalization:

Structured Specifications: Reducing first-attempt failure rates from ~70% to ~15% by providing explicit infrastructure pointers and tactic-level proof plans.
Iterative Evolution: Using AI failures to surface implicit human assumptions (e.g., measurability, integrability, domain constraints) and refining specifications iteratively.
Quantitative Breakdown: Approximately 40% of declarations were proved under full natural language proof plans, 30% were sketch-guided, 15% were autonomous, and 15% required critical human intervention (e.g., correcting flawed mathematical strategies or verifying statement consistency).

Results

Codebase: A library of ~30,000 lines of Lean 4 code containing over 1,000 theorems and lemmas.
Completeness: All formalizations compile without sorry or axioms, ensuring machine-verifiable correctness.
Gap Resolution: The formalization exposed and resolved implicit assumptions in standard SLT textbooks, such as measurability conditions for supremum random variables, integrability of entropy functionals, and the non-emptiness of empirical spheres.
Performance: The framework successfully derived sharp minimax rates for both parametric (linear) and nonparametric (sparse) regression settings, validating the utility of the localized empirical process approach.

Significance

The paper claims that this work establishes a reusable formal foundation for statistical learning theory. By moving beyond mechanical translation to a granular, line-by-line understanding of the theory, the project enforces a rigorous standard that clarifies logical dependencies and hidden assumptions.

The significance is twofold:

Theoretical Rigor: It provides a machine-checked library for SLT, enabling scalable, automated theoretical analysis of machine learning systems and serving as a principled training ground for students to master the full technical stack of SLT.
Methodological Advancement: It demonstrates that large-scale formalization projects can be substantially accelerated through well-designed human-AI collaboration, offering a blueprint for future developments in machine learning theory and other complex mathematical domains.

The authors emphasize that this work is not merely an exercise in rigor but a necessary step to handle the increasing complexity of modern machine learning theory, opening the door for future formal developments in the field.