Lemma 2.1 — residual decomposition under postprocessing
ProvedCalibratedMA.Randomized.lemma_2_1calibrationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be jointly distributed with and . For each input-score pair let be a distribution on , and draw the postprocessed prediction using randomness independent of conditionally on . For a bounded test define its lift to the intermediate score by . Then
The first term is controlled while the score is learned and the second is the error introduced by coarsening; both upper bounds in the paper rest on this split.
Formalization Note. is the law of on , is a Markov kernel from to with , and the law of is (Measure.compProd with the kernel composed with ). This is the formal content of "independent of conditionally on ".
Differences from the source:
- reading: " jointly distributed" → in addition almost surely; reason: Section 2 fixes for the whole paper; this standing assumption also makes every expectation in (3) finite.
- encoding: the family of distributions on → a Markov kernel (measurable in ) carried by ; reason: measurability is needed for to have a joint law.
- encoding: bounded test → jointly measurable with values in on ; reason: measurability only excludes tests whose expectations are undefined.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace CalibratedMA.Randomized
/-- Lemma 2.1 (p. 12), residual decomposition under postprocessing. `μ` is the joint law of
`(X, Y, S)` (points `(x, y, s)`), `R` the postprocessing kernel `(x, s) ↦ R_{x,s}`, and the joint
law of `((X, Y, S), P)` is `μ ⊗ R_{X,S}`: given `(X, S)`, `P` is drawn independently of `Y`. -/
theorem lemma_2_1 {X : Type*} [MeasurableSpace X] (μ : Measure (X × ℝ × ℝ))
[IsProbabilityMeasure μ] (hY : ∀ᵐ w ∂μ, w.2.1 ∈ Set.Icc (0 : ℝ) 1)
(hS : ∀ᵐ w ∂μ, w.2.2 ∈ Set.Icc (0 : ℝ) 1)
(R : Kernel (X × ℝ) ℝ) [IsMarkovKernel R] (hR : ∀ xs, R xs (Set.Icc (0 : ℝ) 1)ᶜ = 0)
(φ : X → ℝ → ℝ) (hφm : Measurable (Function.uncurry φ))
(hφ : ∀ x, ∀ p ∈ Set.Icc (0 : ℝ) 1, φ x p ∈ Set.Icc (-1 : ℝ) 1) :
let ν : Measure ((X × ℝ × ℝ) × ℝ) :=
μ ⊗ₘ (R.comap (fun w : X × ℝ × ℝ => (w.1, w.2.2)) (by fun_prop))
let φup : X → ℝ → ℝ := fun x s => ∫ p, φ x p ∂(R (x, s))
∫ v, φ v.1.1 v.2 * (v.1.2.1 - v.2) ∂ν =
∫ w, φup w.1 w.2.2 * (w.2.1 - w.2.2) ∂μ + ∫ v, φ v.1.1 v.2 * (v.1.2.2 - v.2) ∂ν := 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. 12, Lemma 2.1, Eq. (3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.