Formal Learning Theory Kernel

Source: url:https://github.com/Zetetic-Dhruv/formal-learning-theory-kernel Authors: Dhruv Gupta Status: verified Main declarations: fundamental_theorem, littlestone_characterization, pac_not_implies_online Tags: learning-theory, probability, combinatorics, online-learning MSC: 68Q32, 68T05

Mathematical overview

This development covers several central results in computational learning theory. The completed public results include:

• PAC/VC equivalence via vc_characterization.
• The bundled PAC, VC, compression-with-side-information, Rademacher, and sample-complexity statement fundamental_theorem.
• The Moran-Yehudayoff style compression-with-side-information equivalence fundamental_vc_compression.
• Gold-style identification results, including gold_theorem and mind_change_characterization.
• Online-learning characterizations and separations, including littlestone_characterization, pac_not_implies_online, and ex_not_implies_pac.

Sources include standard texts and papers in statistical and online learning theory: Shalev-Shwartz and Ben-David for PAC/VC theory, Gold's 1967 identification-in-the-limit theorem, Littlestone's online-learning dimension, and Moran-Yehudayoff compression with side information.