Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.2 — lifted rounded tests are linear interpolants

Proved
CalibratedMA.Randomized.lemma_3_2

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

calibrationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-rounding

Fix a grid partition Γ=(γ0,…,γM)\Gamma=(\gamma_0,\dots,\gamma_M)Γ=(γ0​,…,γM​) and a test h:{γ0,…,γM}→Rh:\{\gamma_0,\dots,\gamma_M\}\to\mathbb Rh:{γ0​,…,γM​}→R. Let P=RoundΓ(S)P=\mathrm{Round}_\Gamma(S)P=RoundΓ​(S) and ah(s)=E[h(P)∣S=s]a_h(s)=\mathbb E[h(P)\mid S=s]ah​(s)=E[h(P)∣S=s]. Then, for 0≤j<M0\le j<M0≤j<M and s∈[γj,γj+1]s\in[\gamma_j,\gamma_{j+1}]s∈[γj​,γj+1​],

ah(s)=h(γj)γj+1−sγj+1−γj+h(γj+1)s−γjγj+1−γj.a_h(s)=h(\gamma_j)\frac{\gamma_{j+1}-s}{\gamma_{j+1}-\gamma_j}+h(\gamma_{j+1})\frac{s-\gamma_j}{\gamma_{j+1}-\gamma_j}.ah​(s)=h(γj​)γj+1​−γj​γj+1​−s​+h(γj+1​)γj+1​−γj​s−γj​​.

Thus aha_hah​ is the continuous piecewise-linear interpolation of the values h(γj)h(\gamma_j)h(γj​) on the partition points.

The lemma identifies the lifted tests in AM,ρ\mathcal A_{M,\rho}AM,ρ​ as piecewise-linear functions of the score, which are continuous, as Lemma 3.1 requires.

Formalization Note. ah(s)a_h(s)ah​(s) is liftTest M γ h s, the integral of hhh against the law of RoundΓ(s)\mathrm{Round}_\Gamma(s)RoundΓ​(s). The test is a function h:R→Rh:\mathbb R\to\mathbb Rh:R→R, of which only the values at the partition points enter. "Continuous piecewise-linear interpolation" is stated as the interval formula together with continuity on [0,1][0,1][0,1].

Differences from the source:

  • encoding: ah(s)=E[h(P)∣S=s]a_h(s)=\mathbb E[h(P)\mid S=s]ah​(s)=E[h(P)∣S=s] → the integral of hhh against the law of RoundΓ(s)\mathrm{Round}_\Gamma(s)RoundΓ​(s); reason: given S=sS=sS=s, PPP has exactly this law.
  • encoding: hhh on the partition points → h:R→Rh:\mathbb R\to\mathbb Rh:R→R; reason: only values at partition points enter.
  • encoding: a grid increment ρ > 0 with integer 1/ρ → a natural grid denominator K with ρ = 1/K, enforced by IsGridPartition; reason: a valid partition forces K ≥ 1 and represents every source grid.
Preamble
import Mathlib
import Definitions.Def_CalibratedMA_Randomized_Rounding

open MeasureTheory
Formal statement
namespace CalibratedMA.Randomized

/-- Lemma 3.2 (p. 14): the lift `a_h(s) = E[h(Round_Γ(s))]` of a test `h` on the partition
points is the linear interpolation of the values `h(γ_j)` on each interval `[γ_j, γ_{j+1}]`,
and it is continuous on `[0,1]`. -/
theorem lemma_3_2 (K M : ℕ) (γ : ℕ → ℝ) (hΓ : IsGridPartition K M γ) (h : ℝ → ℝ) :
    (∀ j < M, ∀ s ∈ Set.Icc (γ j) (γ (j + 1)),
      liftTest M γ h s =
        h (γ j) * ((γ (j + 1) - s) / (γ (j + 1) - γ j)) +
          h (γ (j + 1)) * ((s - γ j) / (γ (j + 1) - γ j))) ∧
    ContinuousOn (liftTest M γ h) (Set.Icc (0 : ℝ) 1) := 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. 14, Lemma 3.2
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