Mathesis

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

Arguments

DOIAuthorDate
MTH.R-2026-6012Dhruv GuptaDhruv Gupta2026-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