# High-Dimensional Calibration from Swap Regret

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 39 references that are in the map.
- First posted on arXiv 27 May 2025.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [Individual Calibration with Randomized Forecasting](https://mlsanity.com/paper/2006.10288/) (2020)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (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)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics](https://mlsanity.com/paper/2210.07152/) (2022)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)
- [Breaking the T2/3 Barrier for Sequential Calibration](https://mlsanity.com/paper/2406.13668/) (2024)
- [Calibrated Forecasts: The Minimax Proof](https://mlsanity.com/paper/2209.05863/) (2022)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [A Lower Bound on Swap Regret in Extensive-Form Games](https://mlsanity.com/paper/2406.13116/) (2024)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)

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

- [Calibration through the Lens of Indistinguishability](https://mlsanity.com/paper/2509.02279/) (2025)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Swap Regret Minimization Through Response-Based Approachability](https://mlsanity.com/paper/2602.06264/) (2026)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [Testable and Actionable Calibration for Full Swap Regret](https://mlsanity.com/paper/2605.17749/) (2026)
- [Defensive Generation](https://mlsanity.com/paper/2602.21390/) (2026)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [Efficient Opportunistic Approachability](https://mlsanity.com/paper/2602.21328/) (2026)
- [Smoothed Elicitation Complexity for Approximate Gamma-calibration of Discrete Classification Tasks](https://mlsanity.com/paper/2605.23017/) (2026)
- [Improved Multi-Dimensional Forecasting for Swap Regret](https://mlsanity.com/paper/2606.29533/) (2026)
- [High-dimensional online calibration from harmonic weights](https://mlsanity.com/paper/2610.07740/) (2026)

## Abstract (arXiv)

We study online calibration of multi-dimensional forecasts over an arbitrary convex set P subset ℝd relative to an arbitrary norm |·|. We connect this to external regret minimization for online linear optimization (OLO): if one can guarantee O(√ρ T) worst-case regret after T rounds when actions are drawn from P and losses from the dual |·|_* unit norm ball, then one can obtain ε-calibrated forecasts after T = exp(tilde O(ρ/ε2)) rounds. When P is the d-dimensional simplex and |·| is the ℓ1-norm, the O(√Tlog d) experts regret bound yields ε-calibrated forecasts after T = exp(tilde O(log d/ε2)) = dtilde O(1/ε2) rounds, recovering a recent result of Peng (2025). Interestingly, our algorithm obtains this guarantee without requiring access to any online linear optimization subroutine or knowledge of the optimal rate ρ -- in fact, our algorithm is identical for every setting of P and |·|. Instead, we show that the optimal regularizer for the above OLO problem can be used to upper bound the above calibration error by a swap regret, which we then minimize by running the recent TreeSwap algorithm (Dagan et al., 2024; Peng and Rubinstein, 2024) with Follow-The-Leader as a subroutine. The resulting algorithm is highly efficient and plays a distribution over simple averages of past observations in each round. Finally, we prove that any online calibration algorithm that guarantees ε T ℓ1-calibration error over the d-dimensional simplex requires T ≥ exp(poly(1/ε)) (assuming d ≥ poly(1/ε)). This strengthens the corresponding dOmega(log(1/ε)) lower bound of Peng (2025), and shows that an exponential dependence on 1/ε is necessary.