Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.1 — online residual control for finite tests

Proved
CalibratedMA.Randomized.lemma_3_1

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

calibrationonline-learningp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let N≥1N\ge1N≥1 and let Φ\PhiΦ be a finite nonempty class of tests ϕ:X×[0,1]→[−1,1]\phi:\mathcal X\times[0,1]\to[-1,1]ϕ:X×[0,1]→[−1,1], each continuous in its second argument. Run the online rule of Appendix D, which before round ttt determines a rule st:X→[0,1]s_t:\mathcal X\to[0,1]st​:X→[0,1] from the preceding examples, observes XtX_tXt​, predicts St=st(Xt)S_t=s_t(X_t)St​=st​(Xt​) and then observes YtY_tYt​. There is a universal constant CCC such that for every sequence of examples (Xt,Yt)t=1N(X_t,Y_t)_{t=1}^N(Xt​,Yt​)t=1N​ in X×[0,1]\mathcal X\times[0,1]X×[0,1],

sup⁡ϕ∈Φ∣1N∑t=1Nϕ(Xt,St)(Yt−St)∣≤Clog⁡(2∣Φ∣)N.\sup_{\phi\in\Phi}\Big|\frac1N\sum_{t=1}^N\phi(X_t,S_t)(Y_t-S_t)\Big|\le C\sqrt{\frac{\log(2|\Phi|)}{N}}.ϕ∈Φsup​​N1​t=1∑N​ϕ(Xt​,St​)(Yt​−St​)​≤CNlog(2∣Φ∣)​​.

The statement also records that sts_tst​ takes values in [0,1][0,1][0,1] and depends only on the examples of rounds before ttt.

The bound is deterministic and holds against an adversarial sequence. In Theorem 4.1 it controls the empirical residuals of the sequential scores against the tests in G\mathcal GG and against the lifted class A\mathcal AA.

Formalization Note. The constant is quantified first, ∃ C > 0, before the input type, NNN, Φ\PhiΦ and the sequence. Rounds are 0,…,N−10,\dots,N-10,…,N−1, and the tests are only constrained on X×[0,1]\mathcal X\times[0,1]X×[0,1].

Differences from the source:

  • generalization: "There is an online algorithm" → the bound is stated for the specific rule of Appendix D (onlineRule), with its online property and range as conclusions; reason: Appendix D proves the lemma for this rule and Algorithm 1 runs this rule; the existence statement follows by taking this rule.
  • encoding: sup⁡ϕ∈Φ∣⋅∣≤B\sup_{\phi\in\Phi}|\cdot|\le Bsupϕ∈Φ​∣⋅∣≤B → ∀ϕ∈Φ, ∣⋅∣≤B\forall\phi\in\Phi,\ |\cdot|\le B∀ϕ∈Φ, ∣⋅∣≤B; reason: equivalent for a finite set.
  • encoding: rounds 1,…,N1,\dots,N1,…,N and tests on X×[0,1]\mathcal X\times[0,1]X×[0,1] → rounds Fin N and tests X → ℝ → ℝ with hypotheses only on X×[0,1]\mathcal X\times[0,1]X×[0,1]; reason: Lean convention, same instances.
  • generalization: tests on X × [0,1] → tests extended to X × ℝ, with distinct extensions counted separately even if their restrictions agree; reason: the signed-potential bound applies to this larger family; choosing the clamped extension of each source test recovers its exact cardinality and full bound.
Preamble
import Mathlib
import Definitions.Def_CalibratedMA_Randomized_OnlineRule

universe u
Formal statement
namespace CalibratedMA.Randomized

/-- Lemma 3.1 (p. 13), online residual control for finite tests, for the online rule of
Appendix D: the rule `s_t` depends only on the examples of rounds `< t`, takes values in
`[0,1]`, and for every sequence of examples in `X × [0,1]` every test `ϕ ∈ Φ` has
`|N⁻¹ Σ_t ϕ(X_t, S_t)(Y_t − S_t)| ≤ C √(log(2|Φ|)/N)`, `C` universal. -/
theorem lemma_3_1 :
    ∃ C : ℝ, 0 < C ∧
      ∀ (X : Type u) (N : ℕ) (Φ : Finset (X → ℝ → ℝ)), 1 ≤ N → Φ.Nonempty →
        (∀ ϕ ∈ Φ, ∀ x, ContinuousOn (ϕ x) (Set.Icc (0 : ℝ) 1)) →
        (∀ ϕ ∈ Φ, ∀ x, ∀ p ∈ Set.Icc (0 : ℝ) 1, ϕ x p ∈ Set.Icc (-1 : ℝ) 1) →
        (∀ (z z' : Fin N → X × ℝ) (t : ℕ), (∀ s : Fin N, (s : ℕ) < t → z s = z' s) →
            onlineRule N Φ z t = onlineRule N Φ z' t) ∧
        (∀ (z : Fin N → X × ℝ) (t : ℕ) (x : X), onlineRule N Φ z t x ∈ Set.Icc (0 : ℝ) 1) ∧
        ∀ z : Fin N → X × ℝ, (∀ t, (z t).2 ∈ Set.Icc (0 : ℝ) 1) →
          ∀ ϕ ∈ Φ,
            |(1 / (N : ℝ)) * ∑ t : Fin N,
                ϕ (z t).1 (onlineScore N Φ z t) * ((z t).2 - onlineScore N Φ z t)| ≤
              C * Real.sqrt (Real.log (2 * (Φ.card : ℝ)) / N) := 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. 13, Lemma 3.1 (algorithm and proof: Appendix D, pp. 51–52)
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