Theorem 4 — Multicalibration error is at most external regret plus cumulative EVI error
ProvedMulticalibrationGGM.Reduction.theorem_4Let be any feature space, a compact convex outcome set, and any class of individually bounded tests . Supply a learner over and an EVI oracle, and run their Algorithm 1 composition against arbitrary successive contexts and outcomes. Nature may choose each outcome after seeing the current forecast law. Suppose each call satisfies Equation (1) with its nonnegative tolerance , and the scalar expectations defining its EVI certificate and actual comparator feedback are well defined.
For every finite horizon and every comparator , the distributions generated by this composition satisfy
Here is the signed, unnormalized error of Definition 1, and uses the actual losses . Both coefficients are exactly 1. Regret may be negative. The result applies to infinite test classes and general probability laws on the full continuous . If the learner's comparator regret has a sublinear upper bound and the cumulative EVI error is , this inequality gives a sublinear upper bound for the corresponding multicalibration error.
Differences from the source:
- generalization: the supplied learner guarantees sublinear external regret → any supplied causal full-feedback learner; reason: the finite-horizon inequality does not require a rate and therefore specializes to every no-regret learner in the source.
- generalization: the online protocol uses positive round numbers → horizons include zero completed rounds; reason: all three empty sums are zero and the positive-horizon claim is retained unchanged.
- encoding: finite-dimensional real vectors and functions on X times Y → Fin d coordinates with equivalent coordinate-sup-norm boundedness, curried tests, and subtype membership in Y and H; reason: finite-dimensional norm equivalence preserves every bounded test and forecasts still range over every point of the full Y.
- encoding: probability laws and well-defined scalar expectations → Borel probability measures on Y with integrability of the EVI payoffs and realized comparator payoffs under the actual laws; reason: this makes the source expectation convention explicit without requiring globally measurable tests or finite support.
- encoding: Algorithm 1's interactive description → a recursion over learner and oracle states against adaptive Nature, with actual computed loss feedback; reason: every source interaction and every fixed realization of internal randomness has this causal representation, and loss feedback is its restriction to the action set H.
- generalization: the EVI primitive on p. 6 is defined for positive precision ε > 0 → nonnegative real tolerances, including zero when an exact EVI certificate holds; reason: restricting to positive tolerances recovers every source instance, and the same finite-horizon inequality also holds for certified exact solutions without asserting their universal existence.
import Mathlib import Definitions.Def_MulticalibrationGGM_Reduction_Algorithm open scoped NNReal
namespace MulticalibrationGGM.Reduction
/-- Farina and Perdomo, STOC 2027 submission #721 (October 2026), Theorem 4, p. 12,
with Definition 1 (p. 5), Algorithm 1 and Equations (1),(2) (p. 11).
https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/721.pdf
PDF SHA256: 299cdd3237dbe89568ae8f4a701914eb73339a79fee7d6e00d20cd603b38af44.
The source's exact comparator-wise, signed inequality, on the wrapper's computed
trace. The finite-horizon statement is generalized to any supplied learner; in
particular it applies to every no-regret learner in the source. Zero rounds are
included. `ValidPrefix` supplies only EVI correctness and defined expectations.
No global regularity of tests, finite-support law, or uniform class bound is assumed. -/
theorem theorem_4 {X S Q : Type*} {d : ℕ} (Y : Set (Vector d))
(hYcompact : IsCompact Y) (hYconvex : Convex ℝ Y)
(H : Set (Test X Y)) (hHbounded : BoundedTests H)
(A : OnlineLearner H S) (O : EVIOracle X Y H Q) (N : Nature X Y H)
(ε : ℕ → ℝ≥0) (T : ℕ)
(hvalid : ValidPrefix (algorithmRound A O N ε) T) (h : H) :
mcError (algorithmRound A O N ε) T h ≤
comparatorRegret (algorithmRound A O N ε) T h + eviError (algorithmRound A O N ε) T := by sorry
end MulticalibrationGGM.Reduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.