Lemma 5.3 — Population category assignment
OpenCalibratedMA.Randomized.Supplement.lemma_5_3calibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity
Fix any context probability law and the complete finite assignment construction of Section 5.2: a nonempty finite , signed tests , measurable score , finite measurable cell partition, private singleton set, and . Put and . There is one distribution on for which both bounds hold:
Here and average the residual change and squared score change under the actual independent assignment law. The mixture may depend on and the construction. This population existence result supports Theorem 5.1 and assumes no optimality or error bound.
Differences from the source:
- encoding: Section 5.2 partition, signed tests and tuples → AssignmentConfig, finite indices for the distinct signed functions, and an actual finite product measure; reason: this is the source construction, not arbitrary predictors with assumed residual bounds
- encoding: a maximum bound over H → the inequality for every h in the finite nonempty H; reason: equivalent to the finite maximum bound
- encoding: only nonprivate cells receive draws → independent unused draws at private cells are also present; reason: integrating out ignored coordinates leaves exactly the source assignment law
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Supplement_Assignment open MeasureTheory
Formal statement
namespace CalibratedMA.Randomized.Supplement
/-- Lemma 5.3, p.24: the same mixture satisfies both bounds. -/
theorem lemma_5_3 (X : Type) [MeasurableSpace X] (P : Measure X)
(hP : IsProbabilityMeasure P) (c : AssignmentConfig X) :
∃ π : Measure (Fin (signedTests c.G).card), IsProbabilityMeasure π ∧
(∀ h ∈ signedTests c.G, meanChange c P π h ≤ approximationError c ^ 2 / (4 * c.lam)) ∧
meanVariance c P π ≤ approximationError c ^ 2 / c.lam ^ 2 := 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. 24, Lemma 5.3 (PDF pp. 26)