Section 5.1 — category projection, covariance and calibration
DefinitionCalibratedMA_Randomized_Supplement_Categoriescalibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity
Let be a context probability law, a measurable score, and a finite measurable category assignment. For a category of positive mass define
A zero-mass category receives mean zero. Conditional covariance is the conditional product moment minus the product of the conditional means, also zero at a zero-mass category. For a labeled law and score the cell calibration and category-sign maximum are
Signs are encoded as Booleans, and the maximum as a supremum over the finite nonempty type of sign assignments. These definitions distinguish categories from prediction level sets and assignment cells. Lemma 5.2 supplies the projection identities; no identity is assumed here.
Definition code
import Mathlib
import Definitions.Def_CalibratedMA_Randomized_Supplement_Learning
open MeasureTheory
namespace CalibratedMA.Randomized.Supplement
/-- Section 5.1: category means, zero on a category of probability zero. -/
noncomputable def categoryMean {X : Type} [MeasurableSpace X] {r : ℕ}
(P : Measure X) (S : X → ℝ) (J : X → Fin r) (j : Fin r) : ℝ :=
(∫ x in {x | J x = j}, S x ∂P) / (P {x | J x = j}).toReal
noncomputable def categoryPredictor {X : Type} [MeasurableSpace X] {r : ℕ}
(P : Measure X) (S : X → ℝ) (J : X → Fin r) : X → ℝ :=
fun x => categoryMean P S J (J x)
noncomputable def categoryResidual {X : Type} [MeasurableSpace X] {r : ℕ}
(P : Measure X) (S : X → ℝ) (J : X → Fin r) : X → ℝ :=
fun x => S x - categoryPredictor P S J x
/-- Conditional covariance, zero for a zero-mass category (real division by zero). -/
noncomputable def categoryCovariance {X : Type} [MeasurableSpace X] {r : ℕ}
(P : Measure X) (S g : X → ℝ) (J : X → Fin r) (j : Fin r) : ℝ :=
categoryMean P (fun x => g x * S x) J j -
categoryMean P g J j * categoryMean P S J j
noncomputable def cellCalibration {X : Type} [MeasurableSpace X] {r : ℕ}
(D : Measure (X × ℝ)) (q : X → ℝ) (J : X → Fin r) : ℝ :=
∑ j : Fin r, |∫ z, (if J z.1 = j then z.2 - q z.1 else 0) ∂D|
/-- Bool encodes the two category signs; this supremum is over a finite nonempty type. -/
noncomputable def categorySignMaximum {X : Type} [MeasurableSpace X] {r : ℕ}
(D : Measure (X × ℝ)) (S : X → ℝ) (J : X → Fin r) : ℝ :=
⨆ σ : Fin r → Bool, |∫ z, (if σ (J z.1) then (1 : ℝ) else -1) * (z.2 - S z.1) ∂D|
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), pp.21–22, Section 5.1 and Lemma 5.2