TY - GEN
T1 - Lean formalization of generalization error bound by Rademacher complexity and Dudley’s entropy integral
AU - Sonoda, Sho
AU - Kasaura, Kazumi
AU - Mizuno, Yuma
AU - Tsukamoto, Kei
AU - Onda, Naoto
N1 - © 2026, Sho Sonoda, Kazumi Kasaura, Yuma Mizuno, Kei Tsukamoto, and Naoto Onda. Licensed under Creative Commons License CC-BY 4.0
PY - 2026/7/16
Y1 - 2026/7/16
N2 - Understanding and certifying the generalization performance of machine learning algorithms - i.e. obtaining theoretical estimates of the test error from the training error - is a central theme of statistical learning theory. Among the many complexity measures used to derive such guarantees, Rademacher complexity yields sharp, data-dependent bounds that apply well beyond classical VC-dimension theory. In this study, we formalize the generalization error bound by Rademacher complexity in Lean 4, building on measure-theoretic probability theory available in the Mathlib library. Our development provides a mechanically-checked pipeline from the definitions of empirical and expected Rademacher complexity, through a formal symmetrization argument and a bounded-differences analysis, to high-probability uniform deviation bounds via a formally proved McDiarmid inequality. A key technical contribution is a reusable mechanism for lifting results from countable hypothesis classes (where measurability of suprema is straightforward in Mathlib) to separable topological index sets via a reduction to a countable dense subset. As worked applications of the abstract theorem, we mechanize standard empirical Rademacher bounds for linear predictors under ℓ2 and ℓ1 regularizations, and we also formalize a Dudley-type entropy integral bound based on covering numbers and a chaining construction.
AB - Understanding and certifying the generalization performance of machine learning algorithms - i.e. obtaining theoretical estimates of the test error from the training error - is a central theme of statistical learning theory. Among the many complexity measures used to derive such guarantees, Rademacher complexity yields sharp, data-dependent bounds that apply well beyond classical VC-dimension theory. In this study, we formalize the generalization error bound by Rademacher complexity in Lean 4, building on measure-theoretic probability theory available in the Mathlib library. Our development provides a mechanically-checked pipeline from the definitions of empirical and expected Rademacher complexity, through a formal symmetrization argument and a bounded-differences analysis, to high-probability uniform deviation bounds via a formally proved McDiarmid inequality. A key technical contribution is a reusable mechanism for lifting results from countable hypothesis classes (where measurability of suprema is straightforward in Mathlib) to separable topological index sets via a reduction to a countable dense subset. As worked applications of the abstract theorem, we mechanize standard empirical Rademacher bounds for linear predictors under ℓ2 and ℓ1 regularizations, and we also formalize a Dudley-type entropy integral bound based on covering numbers and a chaining construction.
KW - Chaining
KW - Dudley’s entropy integral
KW - Generalization error bound
KW - Hoeffding’s lemma
KW - Lean
KW - McDiarmid’s inequality
KW - Rademacher complexity
KW - Symmetrization arguments
KW - [Maths]
UR - https://www.scopus.com/pages/publications/105045843790
U2 - 10.4230/LIPIcs.ITP.2026.8
DO - 10.4230/LIPIcs.ITP.2026.8
M3 - Conference proceeding
AN - SCOPUS:105045843790
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 17
BT - 17th International Conference on Interactive Theorem Proving, ITP 2026
A2 - Komendantskaya, Ekaterina
A2 - Komendantskaya, Ekaterina
A2 - Nipkow, Tobias
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 17th International Conference on Interactive Theorem Proving, ITP 2026
Y2 - 26 July 2026 through 29 July 2026
ER -