Formal Learning Theory Kernel: Blueprint v1

Scope

Blueprint v1 covers the core story of the kernel:

  • [leftmargin=*,itemsep=3pt]

  • PAC characterization (Chapter 3): the five-way equivalence for PAC learning, with the NullMeasurableSet refinement of the standard Borel hypothesis used in the literature.

  • Online characterization (Chapter 4): the Littlestone characterization theorem with the Standard Optimal Algorithm as the constructive witness.

  • Gold-style learning (Chapter 5): Gold’s theorem with the diagonalization proof and the mind-change characterization with ordinal bounds.

  • Three-paradigm separation (Chapter 6): the 13-edge separation lattice between PAC, online, and Gold-style learning.

  • Measurability layer (Chapter 7): the Borel-parameterized setting, the analytic measurability bridge via Choquet capacitability, and the Borel-analytic separation theorem. This chapter is net-new: it does not exist in the companion textbook because the Borel-analytic separation was discovered during the formalization effort.

Deferred to v2: compression via approximate minimax, the measurable batch learner monad, PAC-Bayes bounds, extended criteria (robust PAC, RKHS), and the Baxter multi-task base case. Compression and the MBL monad rely on infrastructure whose mathematical exposition is not yet stable enough to import from the textbook, and their blueprint treatment will ship once that stabilizes.