Theorem 4.1 — randomized upper bound for calibrated multiaccuracy
ProvedCalibratedMA.Randomized.theorem_4_1There is a universal constant such that the following holds. Let be a measurable space and a finite class of measurable functions . Let be i.i.d. samples from a distribution on , and let . Then, with probability at least over the training sample, Algorithm 1 returns a randomized predictor such that
This is the randomized upper bound of the paper: samples (up to logarithmic factors) suffice for calibrated multiaccuracy error with a randomized predictor. The bound concerns the specific output of Algorithm 1: its online learner, its parameters , its greedy partition and its uniform mixture of rounded rules.
Formalization Note. The constant is quantified first (∃ C > 0), before the input space, the distribution, , and . The sample is ω : Fin n → X × ℝ under the product measure . The conclusion bounds the outer measure of the failure set by , which needs no measurability of that set. The good event also requires the output to be a measurable randomized predictor, so the joint law used in is the true one. is the cardinality of the Finset; for , Lean's leaves only the second term, and .
Differences from the source:
- encoding: distribution on → probability measure on with almost surely; reason: same instances.
- encoding: → measurable ; reason: is undefined otherwise; measurability only excludes undefined cases.
- encoding: "with probability at least over the training sample and the construction randomness" → the -outer measure of the set of samples on which the conclusion fails is at most ; reason: Algorithm 1's training is deterministic given the sample, and the output's internal randomness (the index and the rounding) is part of ; bounding the bad set is the strong reading.
- encoding: "Algorithm 1 returns a randomized predictor" →
IsRandomizedPredictor(measurable, probability measures carried by ) is part of the good event; reason: it makes the source's implicit claim explicit and ensures the joint law is the true one. - encoding: finite class →
G : Finset (X → ℝ)with its cardinality; reason: a finite set of functions, so no test is counted twice. - reading: a finite class G with no explicit nonemptiness assumption, leaving log(0) unspecified → G = ∅ is permitted, MA = 0 and Real.log 0 = 0; reason: this extends the formula at the undefined empty-class boundary; the calibration guarantee still follows using the lifted tests alone.
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Setting import Definitions.Def_CalibratedMA_Randomized_Algorithm1 open MeasureTheory universe u
namespace CalibratedMA.Randomized
/-- Theorem 4.1 (p. 18), randomized upper bound for calibrated multiaccuracy. There is a
universal `C` such that for every measurable space `X`, every distribution `D` on `X × [0,1]`,
every finite class `G` of measurable `g : X → [−1,1]`, every `n ≥ 2` and `δ ∈ (0, 1/2)`, the
`n`-sample probability that Algorithm 1 fails to return a randomized predictor `Q` with
`CMA(Q; G) ≤ C (√(log(2|G|/δ)/n) + (log(2n/δ)/n)^{2/5})` is at most `δ`. -/
theorem theorem_4_1 :
∃ C : ℝ, 0 < C ∧
∀ (X : Type u) [MeasurableSpace X] (D : Measure (X × ℝ)) [IsProbabilityMeasure D],
(∀ᵐ z ∂D, z.2 ∈ Set.Icc (0 : ℝ) 1) →
∀ G : Finset (X → ℝ), (∀ g ∈ G, Measurable g ∧ ∀ x, g x ∈ Set.Icc (-1 : ℝ) 1) →
∀ n : ℕ, 2 ≤ n → ∀ δ : ℝ, 0 < δ → δ < 1 / 2 →
(Measure.pi fun _ : Fin n => D)
{ω | ¬ (IsRandomizedPredictor (algorithm1 n δ G ω) ∧
CMA D (algorithm1 n δ G ω) G ≤
C * (Real.sqrt (Real.log (2 * (G.card : ℝ) / δ) / n) +
(Real.log (2 * (n : ℝ) / δ) / n) ^ (2 / 5 : ℝ)))} ≤
ENNReal.ofReal δ := by sorry
end CalibratedMA.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.