Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 — Φ-regret of best responses is at most the HΦH_\PhiHΦ​-multicalibration error

Open
MulticalibrationGGM.Reduction.Supplement.theorem_5

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

machine-learningmulticalibrationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1phi-regret

Let Z⊆RdZ\subseteq\mathbb R^dZ⊆Rd be a compact convex set of actions, L⊆RdL\subseteq\mathbb R^dL⊆Rd a convex set of losses, and Φ⊆{Z→Z}\Phi\subseteq\{Z\to Z\}Φ⊆{Z→Z} any family of deviations. Let σ:L→Z\sigma:L\to Zσ:L→Z be a best-response map, σ(p)∈arg⁡min⁡z∈Zp⊤z\sigma(p)\in\arg\min_{z\in Z}p^\top zσ(p)∈argminz∈Z​p⊤z, with arbitrary deterministic tie-breaking. For ϕ∈Φ\phi\in\Phiϕ∈Φ put hϕ(p)=σ(p)−ϕ(σ(p))h_\phi(p)=\sigma(p)-\phi(\sigma(p))hϕ​(p)=σ(p)−ϕ(σ(p)).

Let TTT be a horizon, D1,…,DTD_1,\dots,D_TD1​,…,DT​ probability laws on LLL, and ℓ1,…,ℓT∈L\ell_1,\dots,\ell_T\in Lℓ1​,…,ℓT​∈L losses. Let μt\mu_tμt​ be the pushforward of DtD_tDt​ under σ\sigmaσ, the law of zt=σ(pt)z_t=\sigma(p_t)zt​=σ(pt​) with pt∼Dtp_t\sim D_tpt​∼Dt​. Assume the expectations below are defined. Then:

  1. For every ϕ∈Φ\phi\in\Phiϕ∈Φ,
Φ-RegretT(ϕ)=∑t=1TEzt∼μt[ℓt⊤(zt−ϕ(zt))]≤∑t=1TEpt∼Dt[hϕ(pt)⊤(ℓt−pt)]=MC-ErrT(hϕ).\Phi\text{-}\mathrm{Regret}_T(\phi)=\sum_{t=1}^T\mathbb E_{z_t\sim\mu_t}\big[\ell_t^\top(z_t-\phi(z_t))\big]\le\sum_{t=1}^T\mathbb E_{p_t\sim D_t}\big[h_\phi(p_t)^\top(\ell_t-p_t)\big]=\mathrm{MC\text{-}Err}_T(h_\phi).Φ-RegretT​(ϕ)=t=1∑T​Ezt​∼μt​​[ℓt⊤​(zt​−ϕ(zt​))]≤t=1∑T​Ept​∼Dt​​[hϕ​(pt​)⊤(ℓt​−pt​)]=MC-ErrT​(hϕ​).
  1. In particular,
RegretTΦ=sup⁡ϕ∈ΦΦ-RegretT(ϕ)≤sup⁡h∈HΦMC-ErrT(h)=MC-ErrT,\mathrm{Regret}^\Phi_T=\sup_{\phi\in\Phi}\Phi\text{-}\mathrm{Regret}_T(\phi)\le\sup_{h\in H_\Phi}\mathrm{MC\text{-}Err}_T(h)=\mathrm{MC\text{-}Err}_T,RegretTΦ​=ϕ∈Φsup​Φ-RegretT​(ϕ)≤h∈HΦ​sup​MC-ErrT​(h)=MC-ErrT​,

with both suprema taken in the extended reals.

The inequality holds for every sequence of laws and losses, so it covers every run of Algorithm 2, where DtD_tDt​ is the forecaster's output and ℓt\ell_tℓt​ is revealed by Nature. Sublinear multicalibration error with respect to HΦH_\PhiHΦ​ therefore gives sublinear Φ-regret for the decision maker who best-responds to the forecasts. This is a companion theorem and is not used in the proof of Theorem 4.

Differences from the source:

  • generalization: D_t is the sequence produced in Algorithm 2 by a forecaster multicalibrated with respect to H_Φ, and ℓ_t are Nature's losses → arbitrary probability laws D_t on L and arbitrary losses ℓ_t ∈ L; reason: the inequality is pathwise, and every run of Algorithm 2 gives such sequences
  • generalization: horizons T ≥ 1 → every T ∈ ℕ, including T = 0; reason: at T = 0 both sums are empty, and the statement for T ≥ 1 is unchanged
  • reading: the display's "h(p_t)" → h_ϕ(p_t); reason: the display defines MC-Err_T(h_ϕ) on the same line
  • encoding: σ(p) := argmin_{z∈Z} pᵀz with ties broken deterministically by an arbitrary scheme → any function σ : L → Z with σ(p) minimizing pᵀz over Z; reason: these are exactly the possible tie-breaking schemes
  • encoding: expectations are well defined → σ almost-everywhere measurable for each D_t, with the regret integrand integrable under μ_t and the multicalibration payoff integrable under D_t, for every ϕ ∈ Φ and every round; reason: these make the displayed expectations and the pushforward meaningful; without measurability Mathlib's pushforward is the zero measure
  • encoding: tests (x, p) ↦ σ(p) − ϕ(σ(p)) on X × Y → context-free tests on the one-point context type Unit; reason: the tests do not depend on the context
  • encoding: the shorthands Regret^Φ_T := sup_ϕ and MC-Err_T := sup_{h ∈ H_Φ} → suprema in EReal; reason: Φ may be infinite and the families unbounded; the empty supremum is ⊥ on both sides
  • encoding: vectors in ℝ^d, Z and L subsets → Fin d coordinates, subtypes of Fin d → ℝ, Borel probability measures on the subtype L; reason: Lean representation
Preamble
import Mathlib
import Definitions.Def_MulticalibrationGGM_Reduction_Model
import Definitions.Def_MulticalibrationGGM_Reduction_Supplement_Forecaster
import Definitions.Def_MulticalibrationGGM_Reduction_Supplement_PhiRegret

open MeasureTheory
Formal statement
namespace MulticalibrationGGM.Reduction.Supplement

/-- Farina and Perdomo, STOC 2027 submission #721 (October 2026), Theorem 5, p. 15
(proof pp. 15–16), with Definition 2 (p. 5), Equation (4) (p. 14) and Algorithm 2 (p. 15).
https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/721.pdf
PDF SHA256: 299cdd3237dbe89568ae8f4a701914eb73339a79fee7d6e00d20cd603b38af44.

Pathwise over every sequence of forecast laws `D_t` on `L` and losses `ℓ_t ∈ L`
(round `t` of `R`, with outcome `ℓ_t`), hence over every run of Algorithm 2: with
`µ_t = σ#D_t` and `h_ϕ = σ − ϕ ∘ σ`, (a) `Φ-Regret_T(ϕ) ≤ MC-Err_T(h_ϕ)` for every
`ϕ ∈ Φ`, and (b) `sup_{ϕ ∈ Φ} Φ-Regret_T(ϕ) ≤ sup_{h ∈ H_Φ} MC-Err_T(h)` in `EReal`.
The hypotheses `hσ`, `hreg`, `hmc` state that the source's expectations are defined. -/
theorem theorem_5 {d : ℕ} (Z L : Set (Vector d))
    (hZcompact : IsCompact Z) (hZconvex : Convex ℝ Z) (hLconvex : Convex ℝ L)
    (Φ : Set (Z → Z)) (σ : L → Z) (hσbr : IsBestResponseMap σ)
    (R : ℕ → FRound Unit L) (T : ℕ)
    (hσ : ∀ t ∈ Finset.Icc 1 T, AEMeasurable σ ((R t).forecast : Measure L))
    (hreg : ∀ ϕ ∈ Φ, ∀ t ∈ Finset.Icc 1 T,
      Integrable (deviationLoss (R t).outcome ϕ) (actionLaw σ (R t).forecast))
    (hmc : ∀ ϕ ∈ Φ, ∀ t ∈ Finset.Icc 1 T,
      Integrable (payoff (hPhi σ ϕ) () (R t).outcome) ((R t).forecast : Measure L)) :
    (∀ ϕ ∈ Φ, phiRegret σ R T ϕ ≤ roundsMCError R T (hPhi σ ϕ)) ∧
    phiRegretSup σ Φ R T ≤ mcErrorSup (HPhi σ Φ) R T := 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 5, p. 15 (proof pp. 15–16); Definition 2, p. 5; Equation (4), p. 14; Algorithm 2, p. 15. 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