Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.9: if C is weakly PAC learnable using H then C is strongly PAC learnable using ternary majority trees over H

Proved
ComputationalLearning.weak_strong_equivalence

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

boostingpac-learningweak-learning

Theorem 4.9. Let CCC be any concept class and HHH any hypothesis class. Then if CCC is efficiently weakly PAC learnable using HHH, CCC is efficiently strongly PAC learnable using a hypothesis class of ternary majority trees with leaves from HHH.

Formally (sample-complexity sense): if CCC is weakly learnable using measurable hypotheses in HHH (some constant advantage γ>0\gamma > 0γ>0, confidence δ0>0\delta_0 > 0δ0​>0, sample size mmm, by an algorithm jointly measurable in the sample and the instance, uniformly over measurable targets in CCC and all distributions), then CCC is PAC learnable using the class of ternary majority trees with leaves from HHH: for all 0<ϵ,δ<1/20 < \epsilon, \delta < 1/20<ϵ,δ<1/2 there are a sample size and a learning algorithm outputting majority trees over HHH with error greater than ϵ\epsilonϵ with probability at most δ\deltaδ, for every measurable target in CCC and every distribution. The algorithm is Strong-Learn of §4.3.3 (recursive modest boosting on filtered distributions sampled by rejection from the sample) with the confidence boosting of §4.2; its polynomial running time is not formalized.

Why the learner is measurable. Strong-Learn runs LLL on distributions filtered through LLL's own earlier hypotheses, so its analysis conditions on the earlier samples and integrates. For an arbitrary function LLL that integral need not exist. Outer-measure bounds on the separate runs do not combine: there are sets, under the continuum hypothesis, whose sections all have measure 000 while the whole has full outer measure. The book's weak learner is an algorithm, and every algorithm is measurable.

Preamble
import Definitions.Def_ComputationalLearning_Boosting

open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning

/-- **Theorem 4.9** (p. 100). Let `C` be any concept class and `H` any hypothesis class. Then if
`C` is efficiently weakly PAC learnable using `H`, `C` is efficiently strongly PAC learnable using
a hypothesis class of ternary majority trees with leaves from `H`. Stated in the
sample-complexity sense: if for some constant advantage `γ > 0`, confidence `δ₀ > 0` and sample
size a jointly measurable algorithm outputs hypotheses in `H` with error at most `1/2 − γ` with probability at
least `δ₀`, for every measurable target in `C` and every distribution, then `C` is PAC learnable
using the class of ternary majority trees over `H` (the recursive accuracy boosting of §4.3
with the confidence boosting of §4.2; running time is not modelled). -/
theorem weak_strong_equivalence {X : Type*} [MeasurableSpace X] (C H : Set (X → Bool))
    (hH : ∀ h ∈ H, Measurable h) (hweak : WeaklyLearnable C H) :
    PACLearnable C (majorityTrees H) := by sorry

end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §4.3 pp. 78-100, Theorem 4.9 (Schapire) with the recursive accuracy boosting algorithm Strong-Learn and Lemmas 4.2-4.8
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me