Lemma 3.3 — rounding error as total variation
ProvedCalibratedMA.Randomized.lemma_3_3calibrationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-rounding
Let be a grid partition, a distribution on , and . Write for and set . Then
So the largest calibration residual that rounding can create is the total variation of the sequence of interval contributions . Lemma 3.4 chooses the partition to make this small.
Formalization Note. The expectation is the iterated integral . The supremum is stated with IsLUB over all whose values at the partition points lie in ; only those values enter. The boundary conventions are built into the auxiliary sequences q and qprev.
Differences from the source:
- encoding: over →
IsLUBof the set of values over with ; reason: only the values at partition points enter, andIsLUBis the supremum without junk values. - encoding: with an integer → , ; reason: same instances.
- encoding: the joint expectation for S ∼ ν and P = Round_Γ(S) → an iterated integral under a probability measure ν on ℝ carried by [0,1] and roundMeasure; reason: the rounding law has finite support and is measurable, so the iterated integral is the source expectation.
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Rounding open MeasureTheory
Formal statement
namespace CalibratedMA.Randomized
/-- Lemma 3.3 (p. 14), rounding error as total variation. `S ∼ ν` with `ν` a distribution on
`[0,1]`, `P = Round_Γ(S)`, `q_j = q_j(ν, Γ)` and `q_{−1} = q_M = 0`. -/
theorem lemma_3_3 (K M : ℕ) (γ : ℕ → ℝ) (hΓ : IsGridPartition K M γ) (ν : Measure ℝ)
[IsProbabilityMeasure ν] (hν : ν (Set.Icc (0 : ℝ) 1)ᶜ = 0) :
let q : ℕ → ℝ := fun j => if j < M then qj ν γ j else 0
let qprev : ℕ → ℝ := fun j => if j = 0 then 0 else q (j - 1)
IsLUB {v : ℝ | ∃ h : ℝ → ℝ, (∀ j ≤ M, h (γ j) ∈ Set.Icc (-1 : ℝ) 1) ∧
v = |∫ s, (∫ p, h p * (s - p) ∂(roundMeasure M γ s)) ∂ν|} (RoundErr ν M γ) ∧
RoundErr ν M γ = qj ν γ 0 + qj ν γ (M - 1) +
∑ j ∈ Finset.Ico 1 M, |qj ν γ j - qj ν γ (j - 1)| ∧
RoundErr ν M γ = ∑ j ∈ Finset.range (M + 1), |q j - qprev j| := 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.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.