Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 — Deterministic upper bound

Open
CalibratedMA.Randomized.Supplement.theorem_5_1

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

calibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity

Let DDD be the labeled law and CMAD=max⁡{MAD,ECED}\mathrm{CMA}_D=\max\{\mathrm{MA}_D,\mathrm{ECE}_D\}CMAD​=max{MAD​,ECED​} 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 C≥eC\ge eC≥e such that the following holds in every finite dimension ddd. Let XXX be any Borel subset of [0,1]d[0,1]^d[0,1]d and GGG a nonempty finite family of measurable [−1,1][-1,1][−1,1]-valued tests. For every ε,δ∈(0,1/10)\varepsilon,\delta\in(0,1/10)ε,δ∈(0,1/10) and every sample count nnn satisfying

n≥⌈C(Aε2+A1/3ε8/3)log⁡CBεδ⌉,A=log⁡(8∣G∣/δ)+1,B=A+(A/ε2)1/3,n\ge\left\lceil C\left(\frac{A}{\varepsilon^2}+\frac{A^{1/3}}{\varepsilon^{8/3}}\right)\log\frac{CB}{\varepsilon\delta}\right\rceil, \quad A=\log(8|G|/\delta)+1,\quad B=A+(A/\varepsilon^2)^{1/3},n≥⌈C(ε2A​+ε8/3A1/3​)logεδCB​⌉,A=log(8∣G∣/δ)+1,B=A+(A/ε2)1/3,

there is a learner chosen before DDD, valid for every probability law DDD on X×[0,1]X\times[0,1]X×[0,1], whose trained output is a deterministic measurable function p:X→[0,1]p:X\to[0,1]p:X→[0,1] and satisfies

Pr⁡{CMAD(p;G)≤ε}≥1−δ.\Pr\{\mathrm{CMA}_D(p;G)\le\varepsilon\}\ge1-\delta.Pr{CMAD​(p;G)≤ε}≥1−δ.

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
Preamble
import Mathlib
import Definitions.Def_CalibratedMA_Randomized_Supplement_Learning

open MeasureTheory
Formal statement
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
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. 21, Theorem 5.1 (PDF pp. 23)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me