# Efficient Swap Multicalibration of Elicitable Properties

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 45 references that are in the map.
- First posted on arXiv 7 Nov 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [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)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [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)
- [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)
- [Breaking the T2/3 Barrier for Sequential Calibration](https://mlsanity.com/paper/2406.13668/) (2024)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [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 and Adaptive Algorithms for Online Boosting](https://mlsanity.com/paper/1502.02651/) (2015)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025)
- [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Supersimulators](https://mlsanity.com/paper/2509.17994/) (2025)

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

- [The Sample Complexity of Multicalibration](https://mlsanity.com/paper/2604.21923/) (2026)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [Instance-Adaptive Online Multicalibration](https://mlsanity.com/paper/2605.09273/) (2026)
- [Smoothed Elicitation Complexity for Approximate Gamma-calibration of Discrete Classification Tasks](https://mlsanity.com/paper/2605.23017/) (2026)
- [Defensive Boosting for Online Probabilistic Forecasting](https://mlsanity.com/paper/2608.13554/) (2026)

## Abstract (arXiv)

Multicalibration [HJKRR18] is an algorithmic fairness perspective that demands that the predictions of a predictor are correct conditional on themselves and membership in a collection of potentially overlapping subgroups of a population. The work of [NR23] established a surprising connection between multicalibration for an arbitrary property Gamma (e.g., mean or median) and property elicitation: a property Gamma can be multicalibrated if and only if it is elicitable, where elicitability is the notion that the true property value of a distribution can be obtained by solving a regression problem over the distribution. In the online setting, [NR23] proposed an inefficient algorithm that achieves √ T ℓ2-multicalibration error for a hypothesis class of group membership functions and an elicitable property Gamma, after T rounds of interaction between a forecaster and adversary. In this paper, we generalize multicalibration for an elicitable property Gamma from group membership functions to arbitrary bounded hypothesis classes and introduce a stronger notion -- swap multicalibration, following [GKR23]. Subsequently, we propose an oracle-efficient algorithm which, when given access to an online agnostic learner, achieves T1/(r+1) ℓr-swap multicalibration error with high probability (for r≥2) for a hypothesis class with bounded sequential Rademacher complexity and an elicitable property Gamma. For the special case of r=2, this implies an oracle-efficient algorithm that achieves T1/3 ℓ2-swap multicalibration error, which significantly improves on the previously established bounds for the problem [NR23, GMS25, LSS25a], and completely resolves an open question raised in [GJRR24] on the possibility of an oracle-efficient algorithm that achieves √T ℓ2-mean multicalibration error by answering it in a strongly affirmative sense.