Lemma 3.2 — lifted rounded tests are linear interpolants
ProvedCalibratedMA.Randomized.lemma_3_2calibrationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-rounding
Fix a grid partition and a test . Let and . Then, for and ,
Thus is the continuous piecewise-linear interpolation of the values on the partition points.
The lemma identifies the lifted tests in as piecewise-linear functions of the score, which are continuous, as Lemma 3.1 requires.
Formalization Note. is liftTest M γ h s, the integral of against the law of . The test is a function , of which only the values at the partition points enter. "Continuous piecewise-linear interpolation" is stated as the interval formula together with continuity on .
Differences from the source:
- encoding: → the integral of against the law of ; reason: given , has exactly this law.
- encoding: on the partition points → ; 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.