Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Boosting the confidence (§4.2): k independent runs all fail with probability ≤ (1 − δ₀)^k, and selecting the fewest-mistakes hypothesis loses at most γ

Proved
ComputationalLearning.confidence_boosting

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

boostingchernoff-boundspac-learningunion-bound

§4.2 (pp. 76–77). Simulate LLL a total of kkk times on independent samples; the probability that all of h1,…,hkh_1, \dots, h_kh1​,…,hk​ have error larger than ϵ\epsilonϵ is at most (1−δ0)k(1 - \delta_0)^k(1−δ0​)k (solving (1−δ0)k≤δ/2(1-\delta_0)^k \le \delta/2(1−δ0​)k≤δ/2 yields k≥(1/δ0)ln⁡(2/δ)k \ge (1/\delta_0)\ln(2/\delta)k≥(1/δ0​)ln(2/δ)). Then draw a sample SSS of (c0/γ2)log⁡(2k/δ)(c_0/\gamma^2)\log(2k/\delta)(c0​/γ2)log(2k/δ) examples and output the hih_ihi​ that makes the fewest mistakes on SSS: by the Chernoff bounds each empirical error is within γ/2\gamma/2γ/2 of the true error with confidence 1−δ/2k1 - \delta/2k1−δ/2k, and by the union bound the output has error at most ϵ+γ\epsilon + \gammaϵ+γ with confidence 1−δ/21 - \delta/21−δ/2.

Formally: (i) for any learner LLL on samples of size mmm whose hypothesis has error greater than ϵ\epsilonϵ with probability at most 1−δ01 - \delta_01−δ0​, on kkk independent samples all kkk hypotheses have error greater than ϵ\epsilonϵ with probability at most (1−δ0)k(1-\delta_0)^k(1−δ0​)k; (ii) for measurable h1,…,hkh_1, \dots, h_kh1​,…,hk​ one of which has error at most ϵ\epsilonϵ, γ>0\gamma > 0γ>0, and any rule selecting on a sample of mmm examples a hypothesis with the fewest mistakes, the selected hypothesis has error greater than ϵ+γ\epsilon + \gammaϵ+γ with probability at most 2k e−mγ2/22k\,e^{-m\gamma^2/2}2ke−mγ2/2 (the additive Chernoff bound at accuracy γ/2\gamma/2γ/2 and the union bound; the book's c0c_0c0​ is 222 with natural logarithms).

Preamble
import Definitions.Def_ComputationalLearning_Boosting

open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning

/-- **Boosting the confidence** (§4.2, pp. 76–77). (i) If a learner `L` on samples of size `m` finds
a hypothesis of error at most `ε` with probability at least `δ₀` (for the target `c` and
distribution `D`), then on `k` independent samples all `k` hypotheses have error greater than
`ε` with probability at most `(1 − δ₀)^k` (at most `δ/2` for `k ≥ (1/δ₀) ln(2/δ)`). (ii) Given
hypotheses `h₁, …, h_k` at least one of which has error at most `ε`, choosing on a fresh sample
of `m` examples a hypothesis with the fewest mistakes yields, with probability at least
`1 − 2k e^{−mγ²/2}` (the Chernoff bound with accuracy `γ/2` for each of the `k` hypotheses and
the union bound), a hypothesis of error at most `ε + γ`; the book's `(c₀/γ²) log(2k/δ)` examples
are `m ≥ (2/γ²) ln(4k/δ)` with this constant. -/
theorem confidence_boosting {X : Type*} [MeasurableSpace X] (c : X → Bool) (hc : Measurable c)
    (D : Measure X) [IsProbabilityMeasure D] {ε : ℝ} :
    (∀ (m : ℕ) (L : (Fin m → X × Bool) → X → Bool) {δ₀ : ℝ}, 0 ≤ δ₀ → δ₀ ≤ 1 →
      sampleLaw D c m {S | ε < errorOf D c (L S)} ≤ ENNReal.ofReal (1 - δ₀) →
      ∀ k : ℕ, blockSampleLaw D c k m {B | ∀ i, ε < errorOf D c (L (B i))} ≤
        ENNReal.ofReal ((1 - δ₀) ^ k)) ∧
    (∀ (k : ℕ) (h : Fin k → X → Bool), (∀ i, Measurable (h i)) → (∃ i, errorOf D c (h i) ≤ ε) →
      ∀ {γ : ℝ}, 0 < γ → ∀ (m : ℕ) (sel : (Fin m → X × Bool) → Fin k),
        (∀ S j, mistakes (h (sel S)) S ≤ mistakes (h j) S) →
        sampleLaw D c m {S | ε + γ < errorOf D c (h (sel S))} ≤
          ENNReal.ofReal (2 * k * Real.exp (-(m * γ ^ 2 / 2)))) := 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.2 pp. 76-77, the confidence boosting procedure and its analysis
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