Theorem 6.1 — Matching lower bound for randomized predictors
OpenCalibratedMA.Randomized.Supplement.theorem_6_1calibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity
Let 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 are positive universal . For every integer and every , suppose one learner family with common sample count has the following guarantee for every finite discrete domain , every finite bounded test family with , and every labeled law on :
Then the full sum lower bound holds:
The learner may depend on the public domain and tests but cannot depend on . This companion theorem matches the two randomized rates; it is not used in the proof of Theorem 4.1.
Differences from the source:
- encoding: a finite discrete domain [R] → Fin R, with source coordinate i represented by i.val+1; reason: finite relabeling preserves every statistical experiment, test and error
- 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: 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: sufficiently small positive accuracy → one positive universal ε₀ quantified before all instance parameters; reason: the source proof supplies a threshold uniform in the class budget
- encoding: one algorithm uniform over finite domains and public test families → one dependent family L R G with common n, chosen before all distributions; reason: finite discrete relabeling preserves all guarantees and permits different public-parameter seed laws
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Supplement_Hidden open MeasureTheory
Formal statement
namespace CalibratedMA.Randomized.Supplement
/-- Theorem 6.1, p.32: finite domains are represented by their cardinality and relabeling. -/
theorem theorem_6_1 :
∃ c c₀ ε₀ : ℝ, 0 < c ∧ 0 < c₀ ∧ 0 < ε₀ ∧
∀ NG : ℕ, 2 ≤ NG → ∀ ε : ℝ, 0 < ε → ε < ε₀ →
∀ (n : ℕ) (L : ∀ R : ℕ, Finset (Fin R → ℝ) → RandomizedLearner (Fin R) n),
(∀ (R : ℕ) (G : Finset (Fin R → ℝ)), G.card ≤ NG →
(∀ g ∈ G, ∀ i, g i ∈ Set.Icc (-1 : ℝ) 1) →
∀ D : Measure (Fin R × ℝ), IsLabeledDist D →
RandomizedSuccess (L R G) D G (c * ε) (2 / 3)) →
(n : ℝ) ≥ c₀ * (Real.log NG / ε ^ 2 + 1 / ε ^ (5 / 2 : ℝ)) := by sorry
end CalibratedMA.Randomized.Supplement
Source
Jiuyao Lu, Georgy Noarov, Aaron Roth, Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity, STOC 2027 submission #900 (October 2026; title page November 2, 2026), p. 32, Theorem 6.1 (PDF pp. 34)