Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 (Informal), second bullet (§2.1.1) — a multicalibrated forecaster solves EVIs by uniform mixing

Open
MulticalibrationGGM.Reduction.Supplement.theorem_2_converse

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

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

Let Y⊆RdY\subseteq\mathbb R^dY⊆Rd be compact and convex, and let HHH be a class of tests h:X×Y→Rdh:X\times Y\to\mathbb R^dh:X×Y→Rd, each bounded. Let FFF be a forecaster and B:N→RB:\mathbb N\to\mathbb RB:N→R a function with B(T)/T→0B(T)/T\to0B(T)/T→0. Assume FFF is HHH-multicalibrated with error bound BBB against adaptive Nature: for every h∈Hh\in Hh∈H, every Nature that may choose yty_tyt​ after seeing DtD_tDt​, and every T≥1T\ge1T≥1,

∑t=1TEpt∼Dt[h(xt,pt)⊤(yt−pt)]≤B(T).\sum_{t=1}^T\mathbb E_{p_t\sim D_t}\big[h(x_t,p_t)^\top(y_t-p_t)\big]\le B(T).t=1∑T​Ept​∼Dt​​[h(xt​,pt​)⊤(yt​−pt​)]≤B(T).

Fix a context x∈Xx\in Xx∈X and a test h∈Hh\in Hh∈H. Then:

  1. There is a best-response Nature at (x,h)(x,h)(x,h): one that plays xt=xx_t=xxt​=x and yt∈arg⁡max⁡y^∈Yy^⊤Ept∼Dt[h(x,pt)]y_t\in\arg\max_{\hat y\in Y}\hat y^\top\mathbb E_{p_t\sim D_t}[h(x,p_t)]yt​∈argmaxy^​∈Y​y^​⊤Ept​∼Dt​​[h(x,pt​)].
  2. Take any best-response Nature at (x,h)(x,h)(x,h) and any T≥1T\ge1T≥1, and suppose the coordinates of h(x,⋅)h(x,\cdot)h(x,⋅) are integrable under the laws D1,…,DTD_1,\dots,D_TD1​,…,DT​ of its run with FFF. Let DˉT=1T∑t=1TDt\bar D_T=\frac1T\sum_{t=1}^TD_tDˉT​=T1​∑t=1T​Dt​ be their uniform mixture. Then for every y∈Yy\in Yy∈Y the payoff p↦h(x,p)⊤(y−p)p\mapsto h(x,p)^\top(y-p)p↦h(x,p)⊤(y−p) is integrable under DˉT\bar D_TDˉT​, and
Ep∼DˉT[h(x,p)⊤(y−p)]≤B(T)T.\mathbb E_{p\sim\bar D_T}\big[h(x,p)^\top(y-p)\big]\le\frac{B(T)}{T}.Ep∼DˉT​​[h(x,p)⊤(y−p)]≤TB(T)​.
  1. If those coordinates are integrable under every DtD_tDt​ of the run, then for every ε>0\varepsilon>0ε>0 there is T0≥1T_0\ge1T0​≥1 such that, for all T≥T0T\ge T_0T≥T0​, DˉT\bar D_TDˉT​ solves the EVI for h(x,⋅)h(x,\cdot)h(x,⋅) to tolerance ε\varepsilonε:
Ep∼DˉT[h(x,p)⊤(y−p)]≤εfor every y∈Y.\mathbb E_{p\sim\bar D_T}\big[h(x,p)^\top(y-p)\big]\le\varepsilon\qquad\text{for every }y\in Y.Ep∼DˉT​​[h(x,p)⊤(y−p)]≤εfor every y∈Y.

This is the converse to the mission's goal. EVI solving is necessary as well as sufficient for online multicalibration, and the reduction is black-box: the solver is the uniform mixture of the forecaster's own outputs on a best-response run. It is a companion theorem and is not used in the proof of Theorem 4.

Differences from the source:

  • reading: an H-multicalibrated forecaster's guarantee holds "for any h ∈ H and arbitrary sequence {(x_t, y_t)}" → the guarantee holds against adaptive Nature, which chooses x_t from the history and y_t after seeing D_t; reason: Definition 1's protocol reveals y_t after D_t ("regardless of Nature's choices"), and the source's own best-response outcomes depend on D_t
  • generalization: the forecaster's bound holds on every sequence and every T → the bound is assumed only for T ≥ 1 and only on runs where the payoffs of h are integrable under the actual laws; reason: this is a weaker hypothesis, and every forecaster satisfying the source's hypothesis satisfies it
  • reading: "A can be black-box converted into an efficient algorithm for solving EVIs over H" → the explicit construction of §2.1.1: on a best-response run at (x, h), the uniform mixture of D_1, …, D_T solves the EVI for h(x,·) to tolerance B(T)/T for every T ≥ 1, hence to every ε > 0 for all large T; no running time is stated; reason: the paper gives no computational model or time bound, and §2.1.1 is the theorem's only formal content
  • encoding: MC-Err_T is o(T) → a real function B of the horizon with B(T)/T → 0; reason: the same condition
  • encoding: y_t := argmax_{ŷ∈Y} ŷᵀ E[h(x, p_t)] → every best-response selection (any tie-breaking, any dependence on the history), plus a clause asserting that one exists; reason: the argmax may not be unique, and the existence clause shows the conclusion is not vacuous
  • encoding: expectations are well defined → integrability of the coordinates of h(x,·) under the run's actual laws D_t, as a hypothesis of clauses 2 and 3; integrability under the mixture is concluded, not assumed; reason: the source's best response uses E_{p_t∼D_t}[h(x, p_t)], which needs these integrals; no global measurability of the tests is imposed
  • encoding: forecaster and Nature as algorithms → a state machine (initial state, prediction, update) run by recursion against Nature's history-dependent choices, rounds numbered from 1; reason: every deterministic, or fixed-random-tape, forecaster in the protocol of Definition 1 has this form
  • encoding: vectors in ℝ^d, tests on X × Y, laws on Y → Fin d coordinates, curried tests, Borel probability measures on the subtype Y; reason: Lean representation; forecasts range over the full Y
Preamble
import Mathlib
import Definitions.Def_MulticalibrationGGM_Reduction_Model
import Definitions.Def_MulticalibrationGGM_Reduction_Supplement_Forecaster

open MeasureTheory Filter Topology
open scoped NNReal
Formal statement
namespace MulticalibrationGGM.Reduction.Supplement

/-- Farina and Perdomo, STOC 2027 submission #721 (October 2026), Theorem 2 (Informal),
second bullet, p. 7, with its formal statement and argument in §2.1.1, pp. 13–14
(Multicalibration → EVI).
https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/721.pdf
PDF SHA256: 299cdd3237dbe89568ae8f4a701914eb73339a79fee7d6e00d20cd603b38af44.

Let `F` be `H`-multicalibrated against adaptive Nature with signed error bound `B`,
`B T / T → 0`. Fix a context `x` and a test `h ∈ H`. Then (i) a best-response Nature at
`(x, h)` exists; and for every best-response Nature `N` at `(x, h)`, on its run with `F`:
(ii) for every `T ≥ 1` (when the coordinates of `h(x,·)` are integrable under `D_1, …, D_T`)
the uniform mixture `D̄_T` of `D_1, …, D_T` satisfies, for every `y ∈ Y`,
`E_{p∼D̄_T}[h(x,p)ᵀ(y − p)] ≤ B T / T` with the integrand integrable; and (iii) (when those
coordinates are integrable under every `D_t`) for every `ε > 0` the mixture `D̄_T` solves the
EVI for `h(x,·)` to tolerance `ε` for all large `T`. -/
theorem theorem_2_converse {X S : Type*} {d : ℕ} (Y : Set (Vector d))
    (hYcompact : IsCompact Y) (hYconvex : Convex ℝ Y)
    (H : Set (Test X Y)) (hHbounded : BoundedTests H)
    (F : Forecaster X Y S) (B : ℕ → ℝ)
    (hB : Tendsto (fun T : ℕ => B T / (T : ℝ)) atTop (𝓝 0))
    (hF : IsMulticalibratedWithBound F H B)
    (x : X) (h : Test X Y) (hh : h ∈ H) :
    (∃ N : ForecastNature X Y, IsBestResponseNature h x N) ∧
    ∀ N : ForecastNature X Y, IsBestResponseNature h x N →
      (∀ (T : ℕ) (hT : 1 ≤ T),
        (∀ t ∈ Finset.Icc 1 T, ∀ i : Fin d,
          Integrable (fun p : Y => h x p i) ((forecastRound F N t).forecast : Measure Y)) →
        ∀ y : Y,
          Integrable (payoff h x y)
            ((uniformMixture (fun t => (forecastRound F N t).forecast) T hT : ProbabilityMeasure Y) :
              Measure Y) ∧
          expectedPayoff h x (uniformMixture (fun t => (forecastRound F N t).forecast) T hT) y ≤
            B T / (T : ℝ)) ∧
      ((∀ t : ℕ, 1 ≤ t → ∀ i : Fin d,
          Integrable (fun p : Y => h x p i) ((forecastRound F N t).forecast : Measure Y)) →
        ∀ ε : ℝ≥0, 0 < ε → ∃ T₀ : ℕ, ∃ hT₀ : 1 ≤ T₀, ∀ (T : ℕ) (hT : T₀ ≤ T),
          SolvesEVI (h x) (uniformMixture (fun t => (forecastRound F N t).forecast) T
            (hT₀.trans hT)) ε) := by sorry

end MulticalibrationGGM.Reduction.Supplement
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 2 (Informal), second bullet, p. 7; formal statement and argument §2.1.1, pp. 13–14; Definition 1, p. 5. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/721.pdf. PDF SHA256: 299cdd3237dbe89568ae8f4a701914eb73339a79fee7d6e00d20cd603b38af44.

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