AFTD Auto-Formalizing Theoretical Domains

Cslib.MachineLearning.PACLearning.IsPACLearnerFor

defimported Lean

IsPACLearnerFor m ε δ C 𝒟 asserts that there exists a learner using m samples that is (ε, δ)-correct for the concept class C over the distribution family 𝒟: for every probability measure D ∈ 𝒟 on α × β, the probability (over i.i.d. samples from D) that the learner's hypothesis has error exceeding opt_C(D) + ε is at most δ. The parameters ε and δ are elements of Set.Ioo (0 : ℝ≥0) 1, bundling the value with the proof that it lies in (0, 1). This ensures the condition is non-vacuous: ε < 1 prevents the error threshold from exceeding the maximum possible error under a probability measure, and δ < 1 prevents the confidence bound from being trivially satisfied.

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.IsPACLearnerFor (m : ℕ) (ε δ : Set.Ioo (0 : ℝ≥0) 1)
    (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop
Defined in
CSLib, `Cslib.MachineLearning.PACLearning.IsPACLearnerFor`
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 5
Used by 17

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
/-- `IsPACLearnerFor m ε δ C 𝒟` asserts that there exists a learner using `m` samples that is `(ε, δ)`-correct for the concept class `C` over the distribution family `𝒟`: for every probability measure `D ∈ 𝒟` on `α × β`, the probability (over i.i.d. samples from `D`) that the learner's hypothesis has error exceeding `opt_C(D) + ε` is at most `δ`. The parameters `ε` and `δ` are elements of `Set.Ioo (0 : ℝ≥0) 1`, bundling the value with the proof that it lies in `(0, 1)`. This ensures the condition is non-vacuous: `ε < 1` prevents the error threshold from exceeding the maximum possible error under a probability measure, and `δ < 1` prevents the confidence bound from being trivially satisfied. -/
noncomputable def Cslib.MachineLearning.PACLearning.IsPACLearnerFor (m : ℕ) (ε δ : Set.Ioo (0 : ℝ≥0) 1)
    (C : ConceptClass α β) (𝒟 : Set (Measure (α × β))) : Prop :=
  ∃ A : Learner α β m,
    ∀ (D : Measure (α × β)) [IsProbabilityMeasure D], D ∈ 𝒟 →
      (Measure.pi (fun _ : Fin m => D))
        {S : LabeledSample α β m |
          error D (A S) > optimalError D C + ↑ε.val} ≤ ↑δ.val
See it in the graphDiscuss this resultChallenge it