The sample-complexity functional is monotone in the VC dimension.
ProvedsampleComplexity_linear_in_daether-catalogbridges
The sample-complexity functional is monotone in the VC dimension.
theorem sampleComplexity_linear_in_d{d₁ d₂ : ℕ} {ε δ : ℝ}
(hε : 0 < ε) (hδ : 0 < δ) (hδ1 : δ < 1) (hd : d₁ ≤ d₂) :
sampleComplexityBound d₁ ε δ ≤ sampleComplexityBound d₂ ε δ := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Bridges/Foundations.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Bridges/ToposTheoreticML/Foundations.lean
import Mathlib
import Definitions.Def_Bridges_ToposTheoreticML_Foundations
/-! # Topos-Theoretic Machine Learning: Foundations
This file develops the shared vocabulary connecting statistical learning theory to
topos-theoretic geometry. It introduces concept families and their shattering /
Vapnik–Chervonenkis dimension, the Sauer–Shelah growth function, an abstract
sample-complexity functional, sieves on a preorder together with their lattice
structure, and the auxiliary data (cryptographic hardness witnesses, transfer
morphisms) used to phrase transfer and lower-bound results.
The downstream file `Bridges/VCCompactness.lean` builds the actual bridge theorems
on top of these definitions.
-/
-- open removed: section is not a namespace
/-! ## Concept families, shattering and VC dimension -/
open ConceptFamily
variable {α : Type*}
/-! ## The Sauer–Shelah growth function -/
/-! ## Sample complexity -/Formal statement
theorem sampleComplexity_linear_in_d{d₁ d₂ : ℕ} {ε δ : ℝ}
(hε : 0 < ε) (hδ : 0 < δ) (hδ1 : δ < 1) (hd : d₁ ≤ d₂) :
sampleComplexityBound d₁ ε δ ≤ sampleComplexityBound d₂ ε δ := by sorrySource