Theorem 7.1 — Deterministic lower bound with a group budget
OpenCalibratedMA.Randomized.Supplement.theorem_7_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 and every real budget with , there exist a finite nonempty domain , a finite nonempty family of Bernoulli-label laws and a finite sign-test family such that
For every sample count and every randomized training procedure with deterministic trained output ,
All hard objects are chosen before and the learner. This is a companion theorem on deterministic prediction, not a step 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: 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: 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: finite hard witnesses and both log-cardinality bounds → explicitly nonempty finite witnesses chosen before n and the learner; reason: the source proof constructs these, and the complete budget interval and both inequalities are unchanged
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Supplement_Hidden open MeasureTheory
Formal statement
namespace CalibratedMA.Randomized.Supplement
/-- Theorem 7.1, p.36: the entire real budget interval and both log-cardinality bounds. -/
theorem theorem_7_1 :
∃ c csize csamp C₀ a₀ ε₀ : ℝ,
0 < c ∧ 0 < csize ∧ 0 < csamp ∧ 0 < C₀ ∧ 0 < a₀ ∧ 0 < ε₀ ∧
∀ ε : ℝ, 0 < ε → ε < ε₀ → ∀ A : ℝ,
C₀ * Real.log (1 / ε) ≤ A → A ≤ a₀ / ε →
∃ (R : ℕ) (Ds : Finset (Measure (Fin R × ℝ))) (G : Finset (Fin R → ℝ)),
0 < R ∧ Ds.Nonempty ∧
(∀ D ∈ Ds, IsLabeledDist D ∧ ∀ᵐ z ∂D, IsBit z.2) ∧
(∀ g ∈ G, ∀ i, IsSign (g i)) ∧
csize * A ≤ Real.log G.card ∧ Real.log G.card ≤ A ∧ G.Nonempty ∧
∀ (n : ℕ) (L : DeterministicLearner (Fin R) n),
(∀ D ∈ Ds, DeterministicSuccess L D G (c * ε) (2 / 3)) →
(n : ℝ) ≥ csamp * A ^ (1 / 3 : ℝ) / ε ^ (8 / 3 : ℝ) := 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. 36, Theorem 7.1 (PDF pp. 38)