Skip to main navigation Skip to search Skip to main content

Lean formalization of generalization error bound by Rademacher complexity and Dudley’s entropy integral

  • Sho Sonoda
  • , Kazumi Kasaura
  • , Yuma Mizuno
  • , Kei Tsukamoto
  • , Naoto Onda
  • RIKEN
  • CyberAgent, Inc.
  • OMRON Corporation
  • The University of Tokyo

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

Abstract

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.

Original languageEnglish
Title of host publication17th International Conference on Interactive Theorem Proving, ITP 2026
EditorsEkaterina Komendantskaya, Ekaterina Komendantskaya, Tobias Nipkow
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-17
Number of pages17
ISBN (Electronic)9783959774369
DOIs
Publication statusPublished - 16 Jul 2026
Event17th International Conference on Interactive Theorem Proving, ITP 2026 - Lisbon, Portugal
Duration: 26 Jul 2026 → 29 Jul 2026

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume382
ISSN (Print)1868-8969

Conference

Conference17th International Conference on Interactive Theorem Proving, ITP 2026
Country/TerritoryPortugal
CityLisbon
Period26/07/26 → 29/07/26

Keywords

  • Chaining
  • Dudley’s entropy integral
  • Generalization error bound
  • Hoeffding’s lemma
  • Lean
  • McDiarmid’s inequality
  • Rademacher complexity
  • Symmetrization arguments
  • [Maths]

Fingerprint

Dive into the research topics of 'Lean formalization of generalization error bound by Rademacher complexity and Dudley’s entropy integral'. Together they form a unique fingerprint.

Cite this