# Optimal Multiclass U-Calibration Error and Beyond

arXiv: https://arxiv.org/abs/2405.19374 · HTML: https://mlsanity.com/paper/2405.19374/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 28 May 2024.

## Builds on (most cited first, 12 of 12)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)
- [Calibrated Forecasts: The Minimax Proof](https://mlsanity.com/paper/2209.05863/) (2022)

## Built on by (most cited first, 13 of 13)

- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [Calibeating Made Simple](https://mlsanity.com/paper/2603.22167/) (2026)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [The Benefit of Being Bayesian in Online Conformal Prediction](https://mlsanity.com/paper/2410.02561/) (2024)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [Toward Simultaneously Optimal Regret in U-Calibration](https://mlsanity.com/paper/2606.18527/) (2026)
- [Calibeating for general proper losses: A Bregman divergence approach](https://mlsanity.com/paper/2605.17269/) (2026)
- [Improved Multi-Dimensional Forecasting for Swap Regret](https://mlsanity.com/paper/2606.29533/) (2026)
- [Fast Rates for Swap-Agnostic Learning of Proper Losses](https://mlsanity.com/paper/2607.28856/) (2026)
- [Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration](https://mlsanity.com/paper/2608.06656/) (2026)

## Abstract (arXiv)

We consider the problem of online multiclass U-calibration, where a forecaster aims to make sequential distributional predictions over K classes with low U-calibration error, that is, low regret with respect to all bounded proper losses simultaneously. Kleinberg et al. (2023) developed an algorithm with U-calibration error O(K√T) after T rounds and raised the open question of what the optimal bound is. We resolve this question by showing that the optimal U-calibration error is Theta(√KT) -- we start with a simple observation that the Follow-the-Perturbed-Leader algorithm of Daskalakis and Syrgkanis (2016) achieves this upper bound, followed by a matching lower bound constructed with a specific proper loss (which, as a side result, also proves the optimality of the algorithm of Daskalakis and Syrgkanis (2016) in the context of online learning against an adversary with finite choices). We also strengthen our results under natural assumptions on the loss functions, including Theta(log T) U-calibration error for Lipschitz proper losses, O(log T) U-calibration error for a certain class of decomposable proper losses, U-calibration error bounds for proper losses with a low covering number, and others.