PAC learnability

The fundamental theorem of statistical learning, and what can be removed from a learner without losing it.

• MTH.C-2026-6012universal_imp_pac

  Universal learnable → PAC learnable. Proof sketch: UniversalLearnable gives learner L with rate → 0 and Pr[error ≤ rate(m)] ≥ 2/3. Two components: 1. Event containment: rate(m) < ε ⟹ {error ≤ rate(m)} ⊆ {error ≤ ε} (monotonicity). 2. Confidence boosting: 2/3 → 1-δ via median-of-means (Γ₆₇, sorry'd in boost_two_thirds_to_pac). Routes through boost_two_thirds_to_pac which encapsulates the Chernoff-based boosting.

• MTH.C-2026-6026fundamental_theorem

  Fundamental theorem of statistical learning (5-way equivalence, BP₅).

• MTH.C-2026-6027vcDim_fundamental_theorem

  The fundamental theorem of statistical learning. For a measurable concept class, finite VC dimension, eventually polynomial growth, and PAC learnability are mutually equivalent.

• MTH.C-2026-6029advice_elimination

  Advice elimination (Ben-David & Dichterman 1998): If C is PAC-learnable with concept-dependent advice from a FINITE set A (with measurability regularity), then C is PAC-learnable without advice.