An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Φ \Phi -Regret Minimization
Gabriele Farina, Juan Carlos Perdomo · 2026
Read An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Φ \Phi -Regret Minimization by Gabriele Farina, Juan Carlos Perdomo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19592.txt.
Introduction
Farina and Perdomo give a black-box reduction from online learning to online multicalibration, in the style of Gordon, Greenwald, and Marks. To achieve high-dimensional multicalibration for a class of functions, it suffices to combine any no-regret learner over that class with an expected variational inequality solver. They also prove the converse: efficient multicalibration implies efficient solver performance. That converse shows how expected variational inequalities mirror the role of fixed points in the Gordon-Greenwald-Marks result for phi-regret.
Catalog record
| CREATOR | Gabriele Farina, Juan Carlos Perdomo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91026 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.19592
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Φ \Phi -Regret Minimization Gabriele Farina, Juan Carlos Perdomo 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 ℋ \mathcal{H} , it suffices to combine any no-regret learner over ℋ \mathcal{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 T \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. 1 Introduction Originally developed as a definition of algorithmic fairness, multicalibration has turned out to have interesting and important implications beyond its initial scope. Within learning theory, multicalibrated predictors are outcome indistinguishable; they constitute generative models that are computationally unfalsifiable [ 12 ] . Multicalibration also implies robustness to distribution shift [ 41 ] and loss minimization, not just for one loss, but for many losses simultaneously [ 27 ] . Within complexity theory, recent work has started to explore how multicalibration enables stronger versions of classical regularity lemmas, such as the Dense Model Theorem and the Hardcore Lemma [ 4 , 38 ] . In game theory, notions of calibration are intimately tied to swap regret minimization and thus to correlated equilibria [ 21 , 22 , 40 ] . Despite this growing web of connections, the algorithmic understanding of how to achieve multicalibration remains rather fragmented. In the batch setting, the only known algorithms are boosting-style procedures that use polynomially more samples than necessary. In the online setting, where procedures enjoy worst-case guarantees and yield batch algorithms with optimal \mathcal{O}(1/\varepsilon^{2}) sample complexity via online-to-batch reductions, we have a complicated patchwork of designs. Each algorithm targets a specific outcome type (e.g., binary) or hypothesis class (e.g., linear functions) and requires its own idiosyncratic and often lengthy analysis. In short, we lack a clean algorithmic template that works in full generality. There is, however, a compelling precedent for a solution to this issue. Multicalibration is reminiscent of a different and older problem in online learning, namely \Phi -regret minimization [ 30 ] . Both are parameterized by a family of functions: tests in the case of multicalibration, and a set \Phi of strategy transformations \phi:\mathcal{Z}\to\mathcal{Z} in the case of \Phi -regret on a strategy set \mathcal{Z} . Since the seminal result of [ 29 ] (henceforth abbreviated as Gordon-Greenwald-Marks or GGM), it is known that \Phi -regret minimization can be efficiently reduced, black-box, to standard regret minimization over \Phi , converting the outputs over \Phi into strategies in \mathcal{Z} by computing a fixed point of the transformations. Since 2008, this black-box reduction has been the standard approach for \Phi -regret algorithms, and has led to a flurry of results for equilibrium computation (e.g., [ 14 , 23 , 9 , 2 ] and references therein). In light of the above, this paper is motivated by two questions. (Q1) Is there a Gordon-Greenwald-Marks-like reduction for online multicalibration? That is, can online multicalibration be black-box reduced to regret minimization, and if so, what nonlinear optimization primitive plays the role that fixed points play for \Phi -regret? (Q2) How formal is the resemblance between multicalibrated forecasting and \Phi -regret? Can one devise a more fine-grained connection between online \mathcal{H} -multicalibration and \Phi -regret with \mathcal{H} scaling naturally with the complexity of \Phi and recovering the well-known connection between strong calibration and swap regret in the limit? We establish positive answers to both questions. Our first contribution, addressing (Q1) , is a Gordon-Greenwald-Marks-style theorem for online multicalibration. This resolves one of the main open questions in [ 24 ] regarding the existence of efficient oracle-based constructions for online multicalibration. Specifically, we show that online, high-dimensional multicalibration can be obtained efficiently and in a black-box fashion with respect to any class \mathcal{H} by combining external regret minimization over test functions in \mathcal{H} with the nonlinear optimization primitive of expected variational inequalities (EVIs). This black-box reduction is especially appealing in light of recent algorithmic progress on EVIs, demonstrating that they can be solved very efficiently [ 56 ] . Furthermore, we show that EVIs are not only sufficient but also necessary: contingent on an efficient oracle for online learning over \mathcal{H} , an efficient online multicalibrated forecasting algorithm exists if and only if one can efficiently solve EVIs defined by the test functions in \mathcal{H} . Our reduction enables a technical transfer of ideas from the rich literature on online learning to the more recent area of multicalibration. Looking backward, we recover and dramatically simplify the proofs of prior online multicalibration algorithms. By leveraging recent advances in EVIs, these reinterpretations also yield stronger guarantees. Looking forward, we leverage our reduction to design new algorithms for previously unstudied versions of online multicalibration. In particular, we develop forecasting procedures with guarantees in challenging learning environments, such as settings with delayed feedback or censored observations, simply by swapping in the appropriate off-the-shelf regret minimizer. Given how online problems generate offline problems, these new algorithms also imply better batch algorithms via online-to-batch reductions. Our second contribution, addressing (Q2) , runs in the opposite direction: from forecasting to decision making. We show that an efficient no- \Phi -regret algorithm can be constructed by first building an online forecaster for the losses that is multicalibrated with respect to a set of tests defined in terms of \Phi , and then best responding. This result yields a substantially finer-grained reduction from decision making to forecasting than the folklore connection between swap regret and \ell_{1} -multicalibration (e.g., [ 21 ] ), and yields state-of-the-art \Phi -regret algorithms for new domains. Taken together, we show that our two main reductions provide an alternative path between external regret and \Phi -regret to that established by [ 29 ] : Rather than optimizing directly over endomorphisms and then computing fixed points, one can route through multicalibration and EVIs. Recent work on \Phi -regret minimization for expressive deviation classes has increasingly run into the limits of the GGM path: extending it to richer classes of deviations over general action sets \mathcal{Z} has required increasingly elaborate machinery, including semi-separation oracles and careful relaxations of sets of endomorphisms [ 9 ] . Certain natural classes,