# Simultaneous Swap Regret Minimization via KL-Calibration

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 23 Feb 2025.

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

- [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)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Forecast Hedging and Calibration](https://mlsanity.com/paper/2210.07169/) (2022)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- ["Calibeating": Beating Forecasters at Their Own Game](https://mlsanity.com/paper/2209.04892/) (2022)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [Online Isotonic Regression](https://mlsanity.com/paper/1603.04190/) (2016)

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

- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (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)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [Proper Calibeating](https://mlsanity.com/paper/2605.26703/) (2026)
- [Toward Simultaneously Optimal Regret in U-Calibration](https://mlsanity.com/paper/2606.18527/) (2026)
- [The Hidden Game Problem](https://mlsanity.com/paper/2510.03845/) (2025)
- [Fast Rates for Swap-Agnostic Learning of Proper Losses](https://mlsanity.com/paper/2607.28856/) (2026)

## Abstract (arXiv)

Calibration is a fundamental concept that aims at ensuring the reliability of probabilistic predictions by aligning them with real-world outcomes. There is a surge of studies on new calibration measures that are easier to optimize compared to the classical ℓ1-Calibration while still having strong implications for downstream applications. One recent such example is the work by Fishelson et al. (2025) who show that it is possible to achieve O(T1/3) pseudo ℓ2-Calibration error via minimizing pseudo swap regret of the squared loss, which in fact implies the same bound for all bounded proper losses with a smooth univariate form. In this work, we significantly generalize their result in the following ways: (a) in addition to smooth univariate forms, our algorithm also simultaneously achieves O(T1/3) swap regret for any proper loss with a twice continuously differentiable univariate form (such as Tsallis entropy); (b) our bounds hold not only for pseudo swap regret that measures losses using the forecaster's distributions on predictions, but also hold for the actual swap regret that measures losses using the forecaster's actual realized predictions. We achieve so by introducing a new stronger notion of calibration called (pseudo) KL-Calibration, which we show is equivalent to the (pseudo) swap regret for log loss. We prove that there exists an algorithm that achieves O(T1/3) KL-Calibration error and provide an explicit algorithm that achieves O(T1/3) pseudo KL-Calibration error. Moreover, we show that the same algorithm achieves O(T1/3(log T)-1/3log(T/δ)) swap regret w.p. ≥ 1-δ for any proper loss with a smooth univariate form, which implies O(T1/3) ℓ2-Calibration error. A technical contribution of our work is a new randomized rounding procedure and a non-uniform discretization scheme to minimize the swap regret for log loss.