AFTD Auto-Formalizing Theoretical Domains

Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall

theoremverifiedformalizationimported Lean

General pointwise monotonicity of sampleComplexity: if every witness sample size for (L₁, ε₁, δ₁, C₁, 𝒟₁) is also a witness for (L₂, ε₂, δ₂, C₂, 𝒟₂), then the latter's sample complexity is at most the former's (provided the former is attained).

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
theorem Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall {L₁ L₂ : LearnerModel α β}
    {ε₁ δ₁ ε₂ δ₂ : Set.Ioo (0 : ℝ≥0) 1} {C₁ C₂ : ConceptClass α β}
    {𝒟₁ 𝒟₂ : Set (Measure (α × β))}
    (hL : ∀ {m : ℕ}, L₁ m ε₁ δ₁ C₁ 𝒟₁ → L₂ m ε₂ δ₂ C₂ 𝒟₂)
    (h : ∃ m, L₁ m ε₁ δ₁ C₁ 𝒟₁) :
    sampleComplexity L₂ C₂ ε₂ δ₂ 𝒟₂ ≤ sampleComplexity L₁ C₁ ε₁ δ₁ 𝒟₁
Formalizes
CSLib, `Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall`
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
Classical.choiceQuot.soundpropext
Built on 3
Used by 12

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
/-- General pointwise monotonicity of `sampleComplexity`: if every witness sample size for `(L₁, ε₁, δ₁, C₁, 𝒟₁)` is also a witness for `(L₂, ε₂, δ₂, C₂, 𝒟₂)`, then the latter's sample complexity is at most the former's (provided the former is attained). -/
theorem Cslib.MachineLearning.PACLearning.sampleComplexity_le_of_forall {L₁ L₂ : LearnerModel α β}
    {ε₁ δ₁ ε₂ δ₂ : Set.Ioo (0 : ℝ≥0) 1} {C₁ C₂ : ConceptClass α β}
    {𝒟₁ 𝒟₂ : Set (Measure (α × β))}
    (hL : ∀ {m : ℕ}, L₁ m ε₁ δ₁ C₁ 𝒟₁ → L₂ m ε₂ δ₂ C₂ 𝒟₂)
    (h : ∃ m, L₁ m ε₁ δ₁ C₁ 𝒟₁) :
    sampleComplexity L₂ C₂ ε₂ δ₂ 𝒟₂ ≤ sampleComplexity L₁ C₁ ε₁ δ₁ 𝒟₁ :=
  Nat.sInf_le (hL (Nat.sInf_mem h))
See it in the graphDiscuss this resultChallenge it