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.
Decluniversal_imp_pac
∀ (X : Type u) [inst : MeasurableSpace X] (C : ConceptClass X Bool) [MeasurableHypotheses X C], (∀ (L : BatchLearner X Bool), LearnEvalMeasurable L) → UniversalLearnable X C → PACLearnable X C
TopicPAC learnability
Arguments
| DOI | Author | Date |
|---|---|---|
| MTH.R-2026-6012 | 2026-09-24T00:00:00Z |
DOIMTH.C-2026-6012
Cite
Verification
- Library
- FLT_Proofs.Theorem.Separation
- Statement digest
- 018fb4ce4ed4
- First verified
- 2026-09-24T00:00:00Z