Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — Multicalibration error is at most external regret plus cumulative EVI error

Proved
MulticalibrationGGM.Reduction.theorem_4

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

machine-learningmulticalibrationonline-learningp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let XXX be any feature space, Y⊆RdY\subseteq\mathbb R^dY⊆Rd a compact convex outcome set, and HHH any class of individually bounded tests h:X×Y→Rdh:X\times Y\to\mathbb R^dh:X×Y→Rd. Supply a learner over HHH 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 εt\varepsilon_tεt​, and the scalar expectations defining its EVI certificate and actual comparator feedback are well defined.

For every finite horizon TTT and every comparator h∈Hh\in Hh∈H, the distributions generated by this composition satisfy

MC ⁣-ErrT(h)≤RegretT(h)+∑t=1Tεt.\mathrm{MC\!\text{-}Err}_T(h)\le\mathrm{Regret}_T(h)+\sum_{t=1}^T\varepsilon_t.MC-ErrT​(h)≤RegretT​(h)+t=1∑T​εt​.

Here MC ⁣-ErrT(h)\mathrm{MC\!\text{-}Err}_T(h)MC-ErrT​(h) is the signed, unnormalized error of Definition 1, and RegretT(h)=∑t=1T(ft(ht)−ft(h))\mathrm{Regret}_T(h)=\sum_{t=1}^T(f_t(h_t)-f_t(h))RegretT​(h)=∑t=1T​(ft​(ht​)−ft​(h)) uses the actual losses ft(h)=−Ep∼Dt[h(xt,p)⊤(yt−p)]f_t(h)=-\mathbb E_{p\sim D_t}[h(x_t,p)^\top(y_t-p)]ft​(h)=−Ep∼Dt​​[h(xt​,p)⊤(yt​−p)]. Both coefficients are exactly 1. Regret may be negative. The result applies to infinite test classes and general probability laws on the full continuous YYY. If the learner's comparator regret has a sublinear upper bound and the cumulative EVI error is o(T)o(T)o(T), 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.
Preamble
import Mathlib
import Definitions.Def_MulticalibrationGGM_Reduction_Algorithm

open scoped NNReal
Formal statement
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
Source
Gabriele Farina, Juan Perdomo, An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Φ-Regret Minimization, STOC 2027 submission #721 (October 2026), Theorem 4, p. 12; 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.
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me