Lemma 7.2 — Decoding signs from a predictor close to separated baselines
OpenCalibratedMA.Randomized.Supplement.lemma_7_2calibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity
Let , let real baselines obey for , and fix signs and such that . Let have uniform contexts on and Bernoulli labels with these means. For every deterministic predictor , write . For every and either fixed sign at ties, the decoder satisfies
The baselines need not belong to ; only the means for this fixed hidden vector must be valid. This decoding inequality supports Theorem 7.1.
Differences from the source:
- encoding: a finite discrete domain [R] → Fin R, with source coordinate i represented by i.val+1; reason: finite relabeling preserves every statistical experiment, test and error
- encoding: a deterministic predictor p → the published CMA or ECE applied to x ↦ dirac(p(x)); reason: the point mass is exactly a deterministic prediction, with no new error measure
- encoding: the uniform Bernoulli hard law and sign decoder with arbitrary ties → offsetData and signDecoder with either fixed tie sign; reason: both displayed terms and the exact factor 2 are retained; no baseline range hypothesis is added
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Supplement_Hidden open MeasureTheory
Formal statement
namespace CalibratedMA.Randomized.Supplement
/-- Lemma 7.2, p.37: no range restriction on the baselines beyond valid label means. -/
theorem lemma_7_2 (R : ℕ) (hR : 2 ≤ R) (t : Fin R → ℝ)
(Δt : ℝ) (hΔt : 0 < Δt) (hsep : ∀ i j, i ≠ j → Δt ≤ |t i - t j|)
(θ : Fin R → ℝ) (hθ : ∀ i, IsSign (θ i)) (η : ℝ) (hη : 0 < η)
(hμ : ∀ i, t i + η * θ i ∈ Set.Icc (0 : ℝ) 1)
(p : Fin R → ℝ) (hp : IsDetPredictor p) (tie : ℝ) (htie : IsSign tie)
(r : ℝ) (hr : 0 < r) (hrΔ : r < Δt / 2) :
(hamming (signDecoder tie p t) θ : ℝ) / R ≤
2 * baselineError p t / r + ECE (offsetData t η θ) (pointPredictor p) / η := by sorry
end CalibratedMA.Randomized.Supplement
Source
Jiuyao Lu, Georgy Noarov, Aaron Roth, Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity, STOC 2027 submission #900 (October 2026; title page November 2, 2026), p. 37, Lemma 7.2 (PDF pp. 39)