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

Scientific Impact Assessment

Core Contribution

This paper establishes two complementary black-box reductions that fundamentally reshape our understanding of the algorithmic landscape connecting online learning, multicalibration, and Φ-regret minimization.

First reduction (Theorem 4): Online multicalibration with respect to a function class H can be achieved by combining *any* no-regret learner over H with an expected variational inequality (EVI) solver. This is a GGM-style result where EVIs play the role that fixed points play in the classical Gordon-Greenwald-Marks framework for Φ-regret. The converse—that efficient multicalibration implies efficient EVI solving—establishes EVIs as the "right" nonlinear optimization primitive for multicalibration, paralleling Hazan and Kale's necessity result for fixed points.

Second reduction (Theorem 5): Φ-regret minimization reduces to multicalibration with respect to a carefully constructed test class H_Φ, via best-responding to multicalibrated forecasts. Crucially, this reduction is *fine-grained*: the complexity of the required multicalibration tests scales with the complexity of Φ, rather than requiring the full strength of ℓ₁-calibration.

Together, these establish a new route from external regret → (via EVIs) multicalibration → (via best response) Φ-regret, bypassing the fixed-point and semi-separation machinery of the GGM path.

Methodological Rigor

The paper's proofs are remarkably concise and elegant. The proof of Theorem 4 is essentially four lines: the EVI guarantee provides non-negativity of a correction term, which telescopes into the regret of the external learner plus accumulated EVI error. Theorem 5's proof similarly exploits the optimality of best response (σ(p) minimizes p⊤z) to establish the key inequality. This simplicity is a strength—it suggests the results capture something fundamental rather than being artifacts of elaborate machinery.

The paper thoroughly validates its framework by:

1. Recovering Defensive Forecasting (K29) as FTRL over the RKHS ball within their reduction, matching guarantees up to constants

2. Recovering the Unbiased Prediction algorithm of Noarov et al. as Multiscale Multiplicative Weights within their framework

3. Demonstrating that swapping the EVI solver from regret-based to ellipsoid-based yields cubic runtime improvements (Ω(T³) → Õ(T))

The reliance on Fact 1 (efficient EVI solving from Zhang et al. [2025a]) is well-justified and the assumptions (well-bounded convex sets, bounded operators) are standard.

Potential Impact

Resolving open problems: The paper directly resolves the main open question from Garg et al. (SODA '24) on oracle-efficient online multicalibration with √T rates in full generality, and provides the first efficient black-box reduction for multiclass omniprediction.

Unifying framework: By showing that disparate multicalibration algorithms are instantiations of one template (different regret minimizers + EVI solvers), the paper provides a organizing principle that should guide future algorithm design. This mirrors how GGM unified Φ-regret algorithms.

New algorithmic capabilities: The modular nature enables immediate transfer from the mature online learning literature:

Impact on Φ-regret: The alternative path to Φ-regret is potentially transformative. It improves the dimension dependence for linear swap regret from O(d⁴√T) to O(d^{5/2}√T), but more importantly, it eliminates the need for semi-separation oracles that have been the technical bottleneck in recent work. The extension to RKHS deviation classes (Theorem 6) is the first result of its kind and opens a genuinely new frontier—Gaussian RKHS deviations were previously out of reach.

Broader implications: Since multicalibration connects to fairness, omniprediction, outcome indistinguishability, complexity-theoretic regularity lemmas, and equilibrium computation, improvements to multicalibration algorithms propagate broadly. The batch setting benefits through online-to-batch reductions.

Timeliness & Relevance

The paper arrives at a critical moment. The Φ-regret minimization community has been pushing GGM-based approaches to their limits, with increasingly sophisticated semi-separation techniques (Daskalakis et al. STOC '25, Arunachaleswaran et al. EC '25, Zhang et al. EC '25). The paper offers a fundamentally different and simpler path that sidesteps these difficulties. Simultaneously, multicalibration has emerged as a central concept connecting fairness, learning theory, and complexity theory, yet lacked a clean algorithmic foundation—this paper provides exactly that.

Strengths

1. Conceptual clarity: The parallel between EVIs/multicalibration and fixed-points/Φ-regret is deeply illuminating and likely to become a standard framework

2. Proof elegance: Core results proved in a few lines, suggesting they capture essential structure

3. Practical modularity: Off-the-shelf components (any regret minimizer + any EVI solver) yield specialized algorithms

4. Breadth of consequences: One framework yields unified analyses, improved runtimes, new settings (delays, censoring, RKHS deviations), and connections across subfields

5. Full generality: Works for arbitrary compact convex Y, arbitrary H, no binning arguments needed

Limitations

1. EVI solver dependency: The efficiency gains partly rely on recent EVI algorithms (Zhang et al. 2025a); the paper's practical impact is coupled to the maturity of EVI solvers

2. Rates for censored observations: The Õ(T^{3/4}) rate for censored outcomes may not be tight

3. Empirical validation: No experiments are provided; the paper is purely theoretical

4. Lower bounds: While the paper shows EVIs are necessary, it does not establish whether the achieved rates are optimal across all settings

5. Contextual Φ-regret: While mentioned, the contextual extension could be developed more fully

Overall Assessment

This is a high-impact theoretical contribution that provides the "missing" GGM theorem for multicalibration. Its dual reductions create a new structural bridge between forecasting and decision-making that is both simpler and more powerful than existing approaches, resolves multiple open problems, and opens new algorithmic frontiers (RKHS deviations, delayed/censored settings). The elegance of the framework—and its ability to unify, simplify, and extend—suggests it will become a standard reference.