Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 — randomized upper bound for calibrated multiaccuracy

Proved
CalibratedMA.Randomized.theorem_4_1

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

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

There is a universal constant C<∞C<\inftyC<∞ such that the following holds. Let X\mathcal XX be a measurable space and G\mathcal GG a finite class of measurable functions g:X→[−1,1]g:\mathcal X\to[-1,1]g:X→[−1,1]. Let (X1,Y1),…,(Xn,Yn)(X_1,Y_1),\dots,(X_n,Y_n)(X1​,Y1​),…,(Xn​,Yn​) be n≥2n\ge2n≥2 i.i.d. samples from a distribution D\mathcal DD on X×[0,1]\mathcal X\times[0,1]X×[0,1], and let δ∈(0,1/2)\delta\in(0,1/2)δ∈(0,1/2). Then, with probability at least 1−δ1-\delta1−δ over the training sample, Algorithm 1 returns a randomized predictor Q=(Qx)x∈XQ=(Q_x)_{x\in\mathcal X}Q=(Qx​)x∈X​ such that

CMA(Q;G)≤C{log⁡(2∣G∣/δ)n+(log⁡(2n/δ)n)2/5}.\mathrm{CMA}(Q;\mathcal G)\le C\left\{\sqrt{\frac{\log(2|\mathcal G|/\delta)}{n}}+\Big(\frac{\log(2n/\delta)}{n}\Big)^{2/5}\right\}.CMA(Q;G)≤C{nlog(2∣G∣/δ)​​+(nlog(2n/δ)​)2/5}.

This is the randomized upper bound of the paper: O(log⁡∣G∣/ε2+ε−5/2)O(\log|\mathcal G|/\varepsilon^2+\varepsilon^{-5/2})O(log∣G∣/ε2+ε−5/2) samples (up to logarithmic factors) suffice for calibrated multiaccuracy error ε\varepsilonε with a randomized predictor. The bound concerns the specific output of Algorithm 1: its online learner, its parameters m,ρ,M∗m,\rho,M_*m,ρ,M∗​, 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, G\mathcal GG, nnn and δ\deltaδ. The sample is ω : Fin n → X × ℝ under the product measure D⊗n\mathcal D^{\otimes n}D⊗n. The conclusion bounds the outer measure of the failure set by δ\deltaδ, 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 CMA\mathrm{CMA}CMA is the true one. ∣G∣|\mathcal G|∣G∣ is the cardinality of the Finset; for G=∅\mathcal G=\emptysetG=∅, Lean's log⁡0=0\log 0=0log0=0 leaves only the second term, and MA=0\mathrm{MA}=0MA=0.

Differences from the source:

  • encoding: distribution on X×[0,1]\mathcal X\times[0,1]X×[0,1] → probability measure on X×R\mathcal X\times\mathbb RX×R with Y∈[0,1]Y\in[0,1]Y∈[0,1] almost surely; reason: same instances.
  • encoding: g:X→[−1,1]g:\mathcal X\to[-1,1]g:X→[−1,1] → measurable ggg; reason: E[g(X)(Y−P)]\mathbb E[g(X)(Y-P)]E[g(X)(Y−P)] is undefined otherwise; measurability only excludes undefined cases.
  • encoding: "with probability at least 1−δ1-\delta1−δ over the training sample and the construction randomness" → the D⊗n\mathcal D^{\otimes n}D⊗n-outer measure of the set of samples on which the conclusion fails is at most δ\deltaδ; reason: Algorithm 1's training is deterministic given the sample, and the output's internal randomness (the index JJJ and the rounding) is part of QQQ; bounding the bad set is the strong reading.
  • encoding: "Algorithm 1 returns a randomized predictor" → IsRandomizedPredictor (measurable, probability measures carried by [0,1][0,1][0,1]) 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\mathcal GG → G : Finset (X → ℝ) with ∣G∣|\mathcal G|∣G∣ 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.
Preamble
import Mathlib
import Definitions.Def_CalibratedMA_Randomized_Setting
import Definitions.Def_CalibratedMA_Randomized_Algorithm1

open MeasureTheory

universe u
Formal statement
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
Source
Jiuyao Lu, Georgy Noarov, Aaron Roth, Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity, STOC 2027 submission #900 (October 2026), p. 18, Theorem 4.1 (Algorithm 1, p. 18; proof pp. 19–20)
Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

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