# Improved Bounds for Swap Multicalibration and Swap Omniprediction

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

## Key facts

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

## Builds on (most cited first, 30 of 35)

- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [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)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [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)
- [Multicalibration as Boosting for Regression](https://mlsanity.com/paper/2301.13767/) (2023)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Optimization of Scoring Rules](https://mlsanity.com/paper/2007.02905/) (2020)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [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)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Collaborative Prediction: Tractable Information Aggregation via Agreement](https://mlsanity.com/paper/2504.06075/) (2025)
- ["Calibeating": Beating Forecasters at Their Own Game](https://mlsanity.com/paper/2209.04892/) (2022)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses](https://mlsanity.com/paper/2502.12564/) (2025)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [Tractable Agreement Protocols](https://mlsanity.com/paper/2411.19791/) (2024)

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

- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [Optimal Recalibration of an Online Predictor](https://mlsanity.com/paper/2607.19689/) (2026)
- [Fast Rates for Swap-Agnostic Learning of Proper Losses](https://mlsanity.com/paper/2607.28856/) (2026)

## Abstract (arXiv)

In this paper, we consider the related problems of multicalibration -- a multigroup fairness notion and omniprediction -- a simultaneous loss minimization paradigm, both in the distributional and online settings. The recent work of Garg et al. (2024) raised the open problem of whether it is possible to efficiently achieve O(√T) ℓ2-multicalibration error against bounded linear functions. In this paper, we answer this question in a strongly affirmative sense. We propose an efficient algorithm that achieves O(T^frac13) ℓ2-swap multicalibration error (both in high probability and expectation). On propagating this bound onward, we obtain significantly improved rates for ℓ1-swap multicalibration and swap omniprediction for a loss class of convex Lipschitz functions. In particular, we show that our algorithm achieves O(T^frac23) ℓ1-swap multicalibration and swap omniprediction errors, thereby improving upon the previous best-known bound of O(T^frac78). As a consequence of our improved online results, we further obtain several improved sample complexity rates in the distributional setting. In particular, we establish a O(varepsilon ^ -3) sample complexity of efficiently learning an varepsilon-swap omnipredictor for the class of convex and Lipschitz functions, O(varepsilon -2.5) sample complexity of efficiently learning an varepsilon-swap agnostic learner for the squared loss, and O(varepsilon ^ -5), O(varepsilon ^ -2.5) sample complexities of learning ℓ1, ℓ2-swap multicalibrated predictors against linear functions, all of which significantly improve on the previous best-known bounds.