Source-linked AI summary
An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $\Phi$-Regret Minimization
Gabriele Farina, Juan Carlos Perdomo
TL;DR
The paper addresses the lack of a clean, general algorithmic template for online multicalibration and the limited connection between multicalibration and Φ-regret. It introduces black-box reductions through EVIs and best responses, obtaining broad multicalibration procedures and a forecasting-based route to Φ-regret. The results unify prior analyses, support delayed or censored outcomes and multiclass omniprediction, improve linear swap-regret methods, and extend guarantees to contextual and RKHS deviation classes.
Problem
Online multicalibration has lacked a clean algorithmic template working in full generality, while the connection between H-multicalibration and Φ-regret remained insufficiently fine-grained.
Method
The paper combines external regret minimization with EVI solving for multicalibration, and converts multicalibrated loss forecasting into Φ-regret minimization through best responses.
Results
The reductions yield efficient high-dimensional multicalibration, algorithms for delayed or censored outcomes and multiclass omniprediction, and new contextual and RKHS Φ-regret algorithms.
Takeaways & Limitations
Forecasting and EVIs provide an alternative computational route from external regret to Φ-regret that avoids fixed-point and semiseparation machinery.
Takeaways & Limitations
The linear swap-regret setting assumes well-bounded convex compact action and loss sets with efficient oracle access and bounded geometric parameters.
Abstract
from arXiv · showhide
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 addresses the high-dimensional analogue of the 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 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.
1 Introduction
The paper develops black-box reductions that make online multicalibration broadly algorithmic and connect it finely to Φ-regret minimization. These reductions use EVIs and best responses to unify existing analyses, handle challenging environments, and avoid fixed-point or semiseparation machinery.
- First contribution: Online multicalibration can be obtained efficiently and black-box from external regret minimization over H paired with an EVI solver, for arbitrary high-dimensional outcomes.The reduction applies to general function classes and convex compact outcome spaces without binning or discretization.
- Applications: The reduction provides a general template that recovers and strengthens prior algorithms while yielding procedures for delayed or censored outcomes and efficient multiclass omniprediction.It also transfers online guarantees to improved batch algorithms through online-to-batch reductions.
- Second contribution: A fine-grained reduction constructs no-Φ-regret algorithms by multicalibrating loss forecasts to tests induced by Φ and then best responding.This connection is more precise than the folklore link between swap regret and ℓ1-multicalibration and recovers strong-calibration-to-swap-regret only when Φ contains all deviations.
- Overall route: Together, the reductions route external regret to Φ-regret through forecasting and EVIs rather than fixed points, simplifying prior methods and extending efficient guarantees to contextual settings and RKHS deviation classes.The approach improves rates for linear swap regret and avoids the semiseparation machinery used for endomorphisms.
- First contribution: The converse also holds: efficient online multicalibration over H can be black-box converted into an efficient solver for EVIs defined by H.Thus EVIs are both sufficient and necessary under an efficient online-learning oracle.
2 A GGM-Like Theorem for Multicalibration, and Finer-Grained Connections between Decision-Making and Forecasting
The paper reduces online multicalibration to no-regret learning plus EVI solving, proves EVIs are necessary, and then converts suitably fine-grained multicalibration into Φ-regret, including contextual settings.
- Reducing Multicalibration to Online Learning via EVIs: MC-Err_T(h) ≤ Regret_T(h) + EVI_T, so any no-regret learner paired with an EVI solver yields sublinear multicalibration error.The reduction selects tests through online learning, solves an EVI to generate forecasts, and updates the learner after observing outcomes.
- Applications of the Reduction: For finite test sets, Hedge combined with EVI solving gives per-round O(poly(nd) log t) time and a multicalibration bound inherited from Hedge’s regret.The construction represents each selected test as a convex combination and updates its coefficients online.
- Applications of the Reduction: The same reduction applies to infinite structured families, including vector-valued RKHS balls, low-degree polynomials, decision trees, and Lipschitz functions.For low-degree polynomials, the induced losses remain linear in the learner’s representation, enabling the construction to extend beyond finite test families.
- The Necessity of EVIs: Reducing EVIs to Online Multicalibration: The converse reduction uses online multicalibration to solve EVIs: the uniform mixture of forecast distributions converges to an EVI solution as average multicalibration error vanishes.Thus, EVI solving is not merely an implementation aid; it is necessary for the reduction framework.
- Φ-Regret Minimization from Online Multicalibration: The fine-grained reduction makes the required test class grow with the deviation class, enabling efficient no-Φ-regret guarantees for rich structured deviations, including RKHS families.Together with the EVI-based reduction, it provides a route from external regret to Φ-regret and generalizes earlier finite-action connections.
- Φ-Regret Minimization from Online Multicalibration: H_Φ-multicalibration upper-bounds Φ-regret through tests h_ϕ(p) = σ(p) − ϕ(σ(p)); sublinear multicalibration therefore yields sublinear Φ-regret.The reduction also extends to contextual Φ-regret, where contexts arrive before action selection.
3 Algorithmic Implications for Online Multicalibration and Omniprediction
The reduction unifies online multicalibration algorithms, improves established runtimes, and transfers online-learning guarantees to delayed, censored, and multiclass omniprediction settings. It also yields oracle-efficient omniprediction and optimal-rate calibration results.
- Unified analyses and runtimes: The reduction unifies existing high-dimensional multicalibration algorithms and sometimes improves their runtimes.These algorithms become special cases of the general reduction, allowing their correctness to be reproved through a common framework.
- ECE multicalibration: The framework also supports optimal-rate calibration for stricter ℓ1 and ECE multicalibration notions.These guarantees extend the reduction beyond the base multicalibration formulation.
- Unified analyses and runtimes: eO(T) runtime replaces the previous Ω(T^3) runtime for the Unbiased Prediction Algorithm while preserving its multicalibration guarantee.The improved procedure uses an ellipsoid-based EVI solver and achieves runtime eO(T · poly(|H|)) instead of Ω(T^3 · poly(|H|)).
- Challenging observation settings: The reduction extends online multicalibration to delayed observations, with MC-Err_T(h) bounded by Regret_T(h) + EVI_T.Any learner supporting regret guarantees under delays can serve as the external regret minimizer.
- Challenging observation settings: Importance sampling yields the first known online multicalibration algorithms for censored observations, including an eO(T^3/4) rate using Multiplicative Weights.The definition sums multicalibration error over all rounds, including rounds whose outcomes are unobserved.
- Multiclass omniprediction: The reduction provides an oracle-efficient route to multiclass omniprediction by applying online learning to the test class H_L,C.Multicalibration error translates into omniprediction error bounded by 2MC-Err_T, and the resulting algorithm has error bounded by 2Regret_T plus EVI errors.
4 Algorithmic Implications for Φ-Regret Minimization
The paper develops an EVI-based, forecasting-centric route from external regret to Φ-regret that avoids fixed-point and semiseparation machinery. It yields simpler algorithms, improved linear-swap rates, and extensions to richer deviation classes including RKHS balls.
- Overview: The EVI-based reduction combined with multicalibration gives a forecasting-centric alternative to GGM’s fixed-point construction for Φ-regret minimization.This approach is designed to overcome the technical shortcomings of fixed-point and semiseparation methods.
- Overview: Testing membership in linear endomorphisms is provably hard, whereas multicalibration over a larger class of linear tests can be implemented with standard projected gradient descent.The construction replaces geometric reasoning about fixed points with optimization over a Frobenius-norm ball.
- 4.1 Improving Rates for Linear Swap Minimization: O(BLS√(dT)) linear swap regret is achieved with polynomial-time iterations for well-bounded convex strategy and loss sets with efficient oracle access.The guarantee holds for any loss sequence in the specified loss set.
- 4.1 Improving Rates for Linear Swap Minimization: Under John’s-position and standard normalization assumptions, the method yields O(d5/2√T), improving the dependence on dimension over Daskalakis et al. [Das+25].The simpler template also avoids checking whether enlarged test transformations admit fixed points in Z.
- 4.2 No-Φ-Regret with Respect to RKHS Deviations: The same approach yields Φ-regret algorithms for all transformations in an RKHS ball, including infinite-feature spaces such as the Gaussian RKHS.Low-degree polynomial deviations are recovered as a special case.
- 4.2 No-Φ-Regret with Respect to RKHS Deviations: The contextual result allows deviations to depend on observed features and supports general matrix-valued kernels with sequence-dependent bounds.For commonly used kernels, the diagonal operator norm is bounded by a constant, simplifying the resulting bound.