arxiv: 2604.19592 · v1 · submitted 2026-04-21 · 💻 cs.LG · cs.GT

Recognition: unknown

An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Φ-Regret Minimization

Gabriele Farina, Juan Carlos Perdomo

Authors on Pith no claims yet

Pith reviewed 2026-05-10 02:14 UTC · model grok-4.3

classification 💻 cs.LG cs.GT

keywords online learningmulticalibrationregret minimizationvariational inequalitiesblack-box reductionPhi-regret

0 comments

The pith

Any no-regret learner over a function class combined with an expected variational inequality solver suffices for high-dimensional online multicalibration.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a black-box reduction showing that high-dimensional multicalibration with respect to any class of functions H follows from running a standard no-regret learner over H together with a solver for expected variational inequalities. This construction delivers sqrt(T)-type guarantees in an oracle-efficient way and works for arbitrary H. The same technique yields a converse reduction and a separate reduction from multicalibration to contextual Phi-regret minimization. These results connect basic online learning primitives to stronger calibration and regret notions without requiring specialized fixed-point machinery.

Core claim

To achieve high-dimensional multicalibration with respect to a class of functions H, it suffices to combine any no-regret learner over H with an expected variational inequality solver. The paper proves the forward reduction, a matching converse, and a fine-grained reduction from high-dimensional online multicalibration to contextual Phi-regret minimization.

What carries the argument

Gordon-Greenwald-Marks style black-box reduction that reduces online multicalibration to online learning over H plus solving expected variational inequalities.

Load-bearing premise

An efficient black-box solver for the relevant expected variational inequality exists and can be invoked repeatedly.

What would settle it

An explicit function class H together with a no-regret learner and EVI solver for which the combined procedure fails to produce multicalibrated predictions on some sequence of outcomes.

Figures

Figures reproduced from arXiv: 2604.19592 by Gabriele Farina, Juan Carlos Perdomo.

read the original abstract

We give a Gordon-Greenwald-Marks (GGM) style black-box reduction from online learning to online multicalibration. Concretely, we show that to achieve high-dimensional multicalibration with respect to a class of functions H, it suffices to combine any no-regret learner over H with an expected variational inequality (EVI) solver. We also prove a converse statement showing that efficient multicalibration implies efficient EVI solving, highlighting how EVIs in multicalibration mirror the role of fixed points in the GGM result for $\Phi$-regret. This first set of results resolves the main open question in Garg, Jung, Reingold, and Roth (SODA '24), showing that oracle-efficient online multicalibration with $\sqrt{T}$-type guarantees is possible in full generality. Furthermore, our GGM-style reduction unifies the analyses of existing online multicalibration algorithms, enables new algorithms for challenging environments with delayed observations or censored outcomes, and yields the first efficient black-box reduction between online learning and multiclass omniprediction. Our second main result is a fine-grained reduction from high-dimensional online multicalibration to (contextual) $\Phi$-regret minimization. Together with our first result, this establishes a new route from external regret to Phi-regret that bypasses sophisticated fixed-point or semi-separation machinery, dramatically simplifies a result of Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '25) while improving rates, and yields new algorithms that are robust to richer deviation classes, such as those belonging to any reproducing kernel Hilbert space.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the SODA 2024 open question on oracle-efficient multicalibration via a clean black-box reduction and gives a simpler route to Phi-regret that skips fixed-point machinery.

read the letter

The main takeaway is that any no-regret learner over a class H plus a black-box expected variational inequality solver yields oracle-efficient sqrt(T) multicalibration. This directly resolves the central open question from Garg et al. at SODA 2024, and the paper adds a converse showing multicalibration implies efficient EVI solving. It also reduces multicalibration to contextual Phi-regret minimization, which simplifies the STOC 2025 result by Daskalakis et al., improves rates, and handles richer deviation classes like RKHS functions. The reductions are GGM-style and black-box, so they unify existing algorithms and extend to delayed or censored settings plus multiclass omniprediction without introducing non-black-box steps or extra polynomial factors. The construction treats the learner and EVI solver as oracles, which keeps the argument modular and reusable. On the soft spots, the whole thing still depends on the existence of an efficient EVI solver for the specific H; the paper does not supply new solvers or bound the cost of that step beyond the black-box assumption. If that solver is expensive in practice, the practical gain is limited even if the theoretical reduction holds. The rates appear to match the stated theorems without hidden fitting or self-referential definitions. This is for researchers in online learning, calibration, and regret minimization who want modular connections between these areas. A reader working on theoretical algorithms will find the reductions useful and the applications to delayed settings worth checking. I would send it to peer review because the ideas are substantive, the reductions look consistent, and the open-question resolution gives it clear value.

Referee Report

0 major / 2 minor

Summary. The paper presents a Gordon-Greenwald-Marks style black-box reduction showing that high-dimensional online multicalibration w.r.t. any class H is achieved by combining an arbitrary no-regret learner over H with a black-box expected variational inequality (EVI) solver. It proves a matching converse, resolves the main open question of Garg et al. (SODA '24) with oracle-efficient sqrt(T)-type guarantees, unifies prior algorithms, extends to delayed/censored observations and multiclass omniprediction, and gives a fine-grained reduction from multicalibration to contextual Phi-regret minimization that bypasses fixed-point machinery, simplifies Daskalakis et al. (STOC '25), improves rates, and supports richer deviation classes such as RKHS.

Significance. If the results hold, the work resolves a central open question on oracle-efficient online multicalibration in full generality and supplies the first black-box reduction between online learning and multiclass omniprediction. The GGM-style construction unifies existing analyses without hidden polynomial factors and enables new algorithms for delayed and censored settings. The Phi-regret reduction provides a simpler, rate-improved route from external regret that avoids sophisticated fixed-point or semi-separation techniques while handling arbitrary RKHS deviation classes. Strengths include the explicit black-box treatment of both the no-regret learner and EVI solver, the matching converse, and the preservation of sqrt(T) rates across extensions.

minor comments (2)

[Abstract] Abstract: the phrase 'dramatically simplifies a result of Daskalakis et al. (STOC '25) while improving rates' would benefit from a parenthetical note on the specific rate improvement (e.g., the precise dependence on the dimension or the deviation class size) to aid readers.
[Theorem statements] The paper should explicitly state in the main theorem statements (likely §3 or §4) whether the EVI solver is assumed to run in time polynomial in the description of H or whether its runtime is treated purely as an oracle cost.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and thorough review, as well as for recommending acceptance of the paper.

Circularity Check

0 steps flagged

No significant circularity; black-box reductions are independent

full rationale

The paper presents explicit black-box reductions: any no-regret learner over H combined with an EVI solver yields multicalibration, with a converse also shown. These invoke standard oracles from prior literature (GGM, Garg et al.) without reducing the claimed sqrt(T) guarantees or Phi-regret route to fitted parameters, self-definitions, or unverified self-citations. The simplification of the authors' own STOC '25 result is a consequence of the new construction rather than a load-bearing premise. No equations or steps in the derivation chain collapse to the inputs by construction; the central claims retain independent content.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the existence of no-regret learners for arbitrary function classes H and of efficient EVI solvers, both treated as black-box oracles from prior literature rather than derived or fitted within the paper.

axioms (2)

domain assumption Standard definition and existence of no-regret learners over function classes H
Invoked as the starting point for the GGM-style reduction to multicalibration.
domain assumption Existence of efficient solvers for expected variational inequalities
Central black-box component whose efficiency is assumed to obtain sqrt(T) multicalibration guarantees.

pith-pipeline@v0.9.0 · 5612 in / 1428 out tokens · 54228 ms · 2026-05-10T02:14:34.096759+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Instance-Adaptive Online Multicalibration
cs.LG 2026-05 conditional novelty 8.0

A single online multicalibration algorithm adaptively refines a dyadic grid and achieves instance-dependent rates: O(T^{2/3}) worst-case, O(sqrt T) for marginal stochastic data, and O(sqrt(JT)) for J-piecewise station...

Reference graph

Works this paper leans on

14 extracted references · 6 canonical work pages · cited by 1 Pith paper · 2 internal anchors

[1]

Swap Regret Minimization Through Response-Based Approachability

[Ana+26] Ioannis Anagnostides, Gabriele Farina, Maxwell Fishelson, Haipeng Luo, and Jon Schneider. “Swap Regret Minimization Through Response-Based Approachability”. In:arXiv preprint arXiv:2602.06264(2026). [Aru+25] Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. “Swap regret and corr...

work page internal anchor Pith review Pith/arXiv arXiv 2026
[2]

From external to internal regret

[BM07] Avrim Blum and Yishay Mansour. “From external to internal regret.” In:Journal of Machine Learning Research(2007). [Cas+25] S´ ılvia Casacuberta, Parikshit Gopalan, Varun Kanade, and Omer Reingold. “How global calibration strengthens multiaccuracy”. In:IEEE Symposium on Foundations of Computer Science(2025). [CDV24] S´ ılvia Casacuberta, Cynthia Dwo...

2007
[3]

Minimizing regret with label efficient prediction

[CLS05] Nicol` o Cesa-Bianchi, G´ abor Lugosi, and Gilles Stoltz. “Minimizing regret with label efficient prediction”. In:IEEE Transactions on Information Theory(2005). [CLW21] Liyu Chen, Haipeng Luo, and Chen-Yu Wei. “Impossible tuning made possible: A new expert algorithm and its applications”. In:Conference on Learning Theory

2005
[4]

Optimal Lower Bounds for Online Multicalibration

[Col+26] Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth. “Optimal Lower Bounds for Online Multicalibration”. In:arXiv preprint arXiv:2601.05245(2026). [Das+24] Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, and Brian Hu Zhang. “A lower bound on swap regret in extensive-form games”. In:arXiv preprint arXiv:2406.13116(2...

work page internal anchor Pith review Pith/arXiv arXiv 2026
[5]

From Fairness to Infinity: Outcome-Indistinguishable (Omni) Prediction in Evolving Graphs

[Dwo+25] Cynthia Dwork, Chris Hays, Nicole Immorlica, Juan C Perdomo, and Pranay Tankala. “From Fairness to Infinity: Outcome-Indistinguishable (Omni) Prediction in Evolving Graphs”. In:Conference on Learning Theory(2025). [Far+22] Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. “Simple uncoupled no-regret learning dynamics for extensiv...

2025
[6]

Polynomial-time linear-swap regret minimiza- tion in imperfect-information sequential games

[FP23] Gabriele Farina and Charilaos Pipis. “Polynomial-time linear-swap regret minimiza- tion in imperfect-information sequential games”. In:Advances in Neural Information Processing Systems(2023). [FP24] Gabriele Farina and Charilaos Pipis. “Polynomial-Time Computation of Exact Φ- Equilibria in Polyhedral Games”. In:Advances in Neural Information Proces...

work page arXiv 2023
[7]

The ellipsoid method and its consequences in combinatorial optimization

[GLS81] Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver. “The ellipsoid method and its consequences in combinatorial optimization”. In:Combinatorica(1981). [GLS93] Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver.Geometric Algorithms and Combinatorial Optimization

1981
[8]

Loss minimization through the lens of outcome indistinguishability

[Gop+23] Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. “Loss minimization through the lens of outcome indistinguishability”. In:Innovations in Theoretical Computer Science(2023). [Gop+24] Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, and Mihir Singhal. “Omnipredictors for regression and the app...

2023
[9]

Online multivalid learning: Means, moments, and prediction intervals

30 [Gup+21] Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M Pai, and Aaron Roth. “Online multivalid learning: Means, moments, and prediction intervals”. In:arXiv preprint arXiv:2101.01739(2021). [Haz16] Elad Hazan. “Introduction to online convex optimization”. In:Foundations and Trends in Optimization(2016). [H´ eb+18] Ursula H´ ebert-Johnson, Mic...

work page arXiv 2021
[10]

A unifying perspective on multi- calibration: Game dynamics for multi-objective learning

[HJZ23] Nika Haghtalab, Michael Jordan, and Eric Zhao. “A unifying perspective on multi- calibration: Game dynamics for multi-objective learning”. In:Advances in Neural In- formation Processing Systems(2023). [HK07] Elad Hazan and Satyen Kale. “Computational equivalence of fixed points and no re- gret algorithms, and convergence to equilibria”. In:Advance...

2023
[11]

Deterministic calibration and Nash equilibrium

[KF08] Sham M Kakade and Dean P Foster. “Deterministic calibration and Nash equilibrium”. In:Journal of Computer and System Sciences(2008). [Kim+22] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Rein- gold. “Universal adaptability: Target-independent inference that competes with propen- sity scoring”. In:Proceedings of the Nati...

2008
[12]

arXiv preprint arXiv:2310.17651 , year=

[Noa+23] Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. “High-dimensional prediction for sequential decision making”. In:arXiv preprint arXiv:2310.17651(2023). [NOR10] Arkadi Nemirovski, Shmuel Onn, and Uriel G Rothblum. “Accuracy certificates for computational problems with convex structure”. In:Mathematics of Operations Re- search(2010). ...

work page arXiv 2023
[13]

arXiv preprint arXiv:2506.11848 , year=

[PR25] Juan Carlos Perdomo and Benjamin Recht. “In defense of defensive forecasting”. In: arXiv preprint arXiv:2506.11848(2025). [QK15] Kent Quanrud and Daniel Khashabi. “Online learning with adversarial delays”. In: Advances in neural information processing systems28 (2015). [SL05] Gilles Stoltz and G´ abor Lugosi. “Internal regret in on-line portfolio s...

work page arXiv 2025
[14]

Effi- cient Φ-regret minimization with low-degree swap deviations in extensive-form games

[Zha+24] Brian H Zhang, Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. “Effi- cient Φ-regret minimization with low-degree swap deviations in extensive-form games”. In:Advances in Neural Information Processing Systems(2024). [Zha+25a] Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, a...

2024