AFTD Auto-Formalizing Theoretical Domains

Cslib.MachineLearning.PACLearning.sampleComplexity

defimported Lean

The *sample complexity* of a concept class C under a learner model L, at accuracy ε ∈ (0, 1) and confidence δ ∈ (0, 1) over distribution family 𝒟, is the smallest sample size m with L m ε δ C 𝒟. Specialize with L := IsPACLearnerFor for the deterministic model and L := IsRPACLearnerFor for the randomized one. Caveat: because sInf on ℕ returns 0 for the empty set, this definition returns 0 when no learner exists (e.g., a concept class of infinite VC dimension). It is only meaningful when the defining set {m | L m ε δ C 𝒟} is nonempty. The IsPACLearnable.sampleComplexity_* variants below discharge this nonemptiness from a learnability hypothesis.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open MeasureTheory Set in
open scoped ENNReal NNReal in
variable {α : Type*} {β : Type*} [MeasurableSpace α] [MeasurableSpace β] in
noncomputable def Cslib.MachineLearning.PACLearning.sampleComplexity (L : LearnerModel α β) (C : ConceptClass α β)
    (ε δ : Set.Ioo (0 : ℝ≥0) 1) (𝒟 : Set (Measure (α × β))) : ℕ
Defined in
CSLib, `Cslib.MachineLearning.PACLearning.sampleComplexity`
Lean proof
By Samuel Schlesinger, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2026 Samuel Schlesinger. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 2
Used by 10

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open MeasureTheory Set in
open scoped ENNReal NNReal in
variable {α : Type*} {β : Type*} [MeasurableSpace α] [MeasurableSpace β] in
/-- The *sample complexity* of a concept class `C` under a learner model `L`, at accuracy `ε ∈ (0, 1)` and confidence `δ ∈ (0, 1)` over distribution family `𝒟`, is the smallest sample size `m` with `L m ε δ C 𝒟`. Specialize with `L := IsPACLearnerFor` for the deterministic model and `L := IsRPACLearnerFor` for the randomized one. **Caveat**: because `sInf` on `ℕ` returns `0` for the empty set, this definition returns `0` when no learner exists (e.g., a concept class of infinite VC dimension). It is only meaningful when the defining set `{m | L m ε δ C 𝒟}` is nonempty. The `IsPACLearnable.sampleComplexity_*` variants below discharge this nonemptiness from a learnability hypothesis. -/
noncomputable def Cslib.MachineLearning.PACLearning.sampleComplexity (L : LearnerModel α β) (C : ConceptClass α β)
    (ε δ : Set.Ioo (0 : ℝ≥0) 1) (𝒟 : Set (Measure (α × β))) : ℕ :=
  sInf {m : ℕ | L m ε δ C 𝒟}
See it in the graphDiscuss this resultChallenge it