Theorem 5.1 — Deterministic upper bound
OpenCalibratedMA.Randomized.Supplement.theorem_5_1Let be the labeled law and the published error of a full predictor. Probabilities include the iid training sample and an independent training seed; a randomized output may have arbitrary, including continuous, prediction laws.
There is a universal such that the following holds in every finite dimension . Let be any Borel subset of and a nonempty finite family of measurable -valued tests. For every and every sample count satisfying
there is a learner chosen before , valid for every probability law on , whose trained output is a deterministic measurable function and satisfies
There is no assumption of finite support, atomlessness, or computational efficiency. This is a companion theorem, not a step in the proof of Theorem 4.1. The displayed logarithm makes the source's sample bound explicit.
Differences from the source:
- encoding: labels in [0,1] or in {0,1} → real labels with the corresponding almost-sure support predicate; reason: the measures are the same labeled laws
- encoding: a deterministic predictor p → the published CMA or ECE applied to x ↦ dirac(p(x)); reason: the point mass is exactly a deterministic prediction, with no new error measure
- encoding: an algorithm using iid examples and independent training randomness → a data-and-seed evaluation map, its product training law, and a measurable success event; reason: this gives the stated ordinary probability and keeps the same algorithm for every unknown distribution; invalid-label inputs can be measurably clipped without affecting any instance
- encoding: any Borel subset of the d-dimensional unit cube → a measurable subset of Fin d → ℝ contained in the coordinatewise unit cube; reason: the inherited product Borel space and subtype have the same instances
- encoding: Õ(A/ε²+A^(1/3)/ε^(8/3)) samples → the displayed ceiling envelope with B=A+(A/ε²)^(1/3), a universal C≥e, and all larger n; reason: Algorithm 2 and Appendix A Eq. (27), including the large-budget branch, give this logarithm; extra examples may be ignored
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Supplement_Learning open MeasureTheory
namespace CalibratedMA.Randomized.Supplement
/-- Theorem 5.1, p.21, with the logarithmic envelope supplied by Algorithm 2 and Eq. (27).
The learner is chosen before the unknown data distribution. -/
theorem theorem_5_1 :
∃ C : ℝ, Real.exp 1 ≤ C ∧ ∀ (d : ℕ) (X : Set (Fin d → ℝ)),
MeasurableSet X → (∀ x ∈ X, ∀ i, x i ∈ Set.Icc (0 : ℝ) 1) →
∀ G : Finset (X → ℝ), G.Nonempty →
(∀ g ∈ G, Measurable g ∧ ∀ x, g x ∈ Set.Icc (-1 : ℝ) 1) →
∀ ε δ : ℝ, 0 < ε → ε < 1 / 10 → 0 < δ → δ < 1 / 10 →
∀ n : ℕ, deterministicSampleBound C ε δ G.card ≤ n →
∃ L : DeterministicLearner X n, ∀ D : Measure (X × ℝ),
IsLabeledDist D → DeterministicSuccess L D G ε (1 - δ) := by sorry
end CalibratedMA.Randomized.Supplement