Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.5: PAC learning a class of VC dimension d needs Ω(d/ε) examples; explicit forms m ≤ d/2 and m ≤ (d−1)/(64ε)

Proved
ComputationalLearning.vc_lower_bound

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

lower-boundssample-complexityvc-dimension

Theorem 3.5. Any algorithm for PAC learning a concept class of Vapnik–Chervonenkis dimension ddd must use Ω(d/ϵ)\Omega(d/\epsilon)Ω(d/ϵ) examples in the worst case.

Formally, for a class CCC shattering a set of d≥1d \ge 1d≥1 points on an instance space with measurable singletons, and every learning function LLL on samples of size mmm: (i) if m≤d/2m \le d/2m≤d/2, there are a target c∈Cc \in Cc∈C and a distribution DDD (uniform on the shattered set) such that the error of LLL's hypothesis is at least 1/81/81/8 with probability at least 1/21/21/2 over the sample (the book's first argument: the labels of unseen points are fair coins); (ii) if 0<ϵ≤1/160 < \epsilon \le 1/160<ϵ≤1/16 and m≤(d−1)/(64ϵ)m \le (d-1)/(64\epsilon)m≤(d−1)/(64ϵ), there are c∈Cc \in Cc∈C and DDD (one point of weight 1−16ϵ1 - 16\epsilon1−16ϵ, the others of weight 16ϵ/(d−1)16\epsilon/(d-1)16ϵ/(d−1)) such that the error exceeds ϵ\epsilonϵ with probability at least 1/41/41/4. The constants in (ii) instantiate the book's Ω(d/ϵ)\Omega(d/\epsilon)Ω(d/ϵ): with fewer than (d−1)/(64ϵ)(d-1)/(64\epsilon)(d−1)/(64ϵ) examples the algorithm fails with probability at least 1/41/41/4 for some target and distribution.

Preamble
import Definitions.Def_ComputationalLearning_VC

open MeasureTheory
Formal statement
namespace ComputationalLearning

/-- **Theorem 3.5** (p. 62). Any algorithm for PAC learning a concept class of VC dimension `d`
must use `Ω(d/ε)` examples in the worst case. Stated with the two explicit forms of the proof
(pp. 62–64), for a class shattering some set of `d ≥ 1` points, on an instance space with
measurable singletons, and for every learning function `L` on samples of size `m`:
(i) if `m ≤ d/2`, some target concept in the class and some distribution make the error of
`L`'s hypothesis at least `1/8` with probability at least `1/2`;
(ii) if `ε ≤ 1/16` and `m ≤ (d − 1)/(64ε)`, some target concept and some distribution make the
error greater than `ε` with probability at least `1/4` (so a PAC algorithm with `δ < 1/4` needs
more than `(d − 1)/(64ε)` examples). -/
theorem vc_lower_bound {X : Type*} [MeasurableSpace X] [MeasurableSingletonClass X]
    (C : Set (X → Bool)) (d : ℕ) (hd1 : 1 ≤ d) (hd : (d : ℕ∞) ≤ vcDim C) (m : ℕ)
    (L : (Fin m → X × Bool) → X → Bool) :
    ((m : ℝ) ≤ d / 2 → ∃ c ∈ C, ∃ D : Measure X, IsProbabilityMeasure D ∧
      ENNReal.ofReal (1 / 2) ≤ sampleLaw D c m {S | 1 / 8 ≤ errorOf D c (L S)}) ∧
    (∀ ε : ℝ, 0 < ε → ε ≤ 1 / 16 → (m : ℝ) ≤ (d - 1) / (64 * ε) →
      ∃ c ∈ C, ∃ D : Measure X, IsProbabilityMeasure D ∧
        ENNReal.ofReal (1 / 4) ≤ sampleLaw D c m {S | ε < errorOf D c (L S)}) := by sorry

end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §3.6 pp. 62-64, Theorem 3.5 with its proof (the coin-flipping construction and its scaling to weight 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