# An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization arXiv: https://arxiv.org/abs/2604.19592 · HTML: https://mlsanity.com/paper/2604.19592/ ## Key facts - Cited by 3 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 68 references that are in the map. - First posted on arXiv 21 Apr 2026. ## Builds on (most cited first, 30 of 34) - [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019) - [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020) - [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021) - [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022) - [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021) - [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021) - [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023) - [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023) - [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022) - [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025) - [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023) - [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021) - [Forecast Hedging and Calibration](https://mlsanity.com/paper/2210.07169/) (2022) - [Approachability, Regret and Calibration; implications and equivalences](https://mlsanity.com/paper/1301.2663/) (2013) - [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023) - [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021) - [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024) - [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023) - [Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses](https://mlsanity.com/paper/2502.12564/) (2025) - [From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs](https://mlsanity.com/paper/2411.17582/) (2024) - [Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games](https://mlsanity.com/paper/2412.20291/) (2024) - [Faster Recalibration of an Online Predictor via Approachability](https://mlsanity.com/paper/2310.17002/) (2023) - [Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games](https://mlsanity.com/paper/2307.05448/) (2023) - [A Lower Bound on Swap Regret in Extensive-Form Games](https://mlsanity.com/paper/2406.13116/) (2024) - [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025) - [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025) - [Optimal Lower Bounds for Online Multicalibration](https://mlsanity.com/paper/2601.05245/) (2026) - [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025) - [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025) - [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025) ## Built on by (most cited first, 3 of 3) - [Instance-Adaptive Online Multicalibration](https://mlsanity.com/paper/2605.09273/) (2026) - [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026) - [Defensive Boosting for Online Probabilistic Forecasting](https://mlsanity.com/paper/2608.13554/) (2026) ## Abstract (arXiv) 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 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 addresses the high-dimensional analogue of the open question in Garg, Jung, Reingold, and Roth (SODA '24), showing that oracle-efficient online multicalibration with √T-type guarantees is possible in full generality. Furthermore, our GGM-style reduction unifies the analyses of existing algorithms, transfers guarantees from online learning to multicalibration 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.