# Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 13 Feb 2023.

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

- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Multicalibration as Boosting for Regression](https://mlsanity.com/paper/2301.13767/) (2023)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Multicalibrated Partitions for Importance Weights](https://mlsanity.com/paper/2103.05853/) (2021)

## Built on by (most cited first, 30 of 31)

- [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)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Human Expertise in Algorithmic Prediction](https://mlsanity.com/paper/2402.00793/) (2024)
- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [Smooth Calibration and Decision Making](https://mlsanity.com/paper/2504.15582/) (2025)
- [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025)
- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [When does a predictor know its own loss?](https://mlsanity.com/paper/2502.20375/) (2025)
- [Orthogonal Causal Calibration](https://mlsanity.com/paper/2406.01933/) (2024)
- [Three Types of Calibration with Properties and their Semantic and Formal Relationships](https://mlsanity.com/paper/2504.18395/) (2025)
- [MCGrad: Multicalibration at Web Scale](https://mlsanity.com/paper/2509.19884/) (2025)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [The Costs of Pretending That There Are Data-Generating Probability Distributions in the Social World](https://mlsanity.com/paper/2407.17395/) (2024)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Measuring multi-calibration](https://mlsanity.com/paper/2506.11251/) (2025)
- [Integrating Expert Judgment and Algorithmic Decision Making: An Indistinguishability Framework](https://mlsanity.com/paper/2410.08783/) (2024)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [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)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Scalable Utility-Aware Multiclass Calibration](https://mlsanity.com/paper/2510.25458/) (2025)
- [On the Convergence of Multicalibration Gradient Boosting](https://mlsanity.com/paper/2602.06773/) (2026)
- [Optimal Recalibration of an Online Predictor](https://mlsanity.com/paper/2607.19689/) (2026)
- [Improved and Oracle-Efficient Online ℓ1-Multicalibration](https://mlsanity.com/paper/2505.17365/) (2025)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)

## Abstract (arXiv)

We introduce and study Swap Agnostic Learning. The problem can be phrased as a game between a predictor and an adversary: first, the predictor selects a hypothesis h; then, the adversary plays in response, and for each level set of the predictor x ∈ X : h(x) = v selects a (different) loss-minimizing hypothesis cv ∈ C; the predictor wins if h competes with the adaptive adversary's loss. Despite the strength of the adversary, we demonstrate the feasibility Swap Agnostic Learning for any convex loss. Somewhat surprisingly, the result follows through an investigation into the connections between Omniprediction and Multicalibration. Omniprediction is a new notion of optimality for predictors that strengthtens classical notions such as agnostic learning. It asks for loss minimization guarantees (relative to a hypothesis class) that apply not just for a specific loss function, but for any loss belonging to a rich family of losses. A recent line of work shows that omniprediction is implied by multicalibration and related multi-group fairness notions. This unexpected connection raises the question: is multi-group fairness necessary for omniprediction? Our work gives the first affirmative answer to this question. We establish an equivalence between swap variants of omniprediction and multicalibration and swap agnostic learning. Further, swap multicalibration is essentially equivalent to the standard notion of multicalibration, so existing learning algorithms can be used to achieve any of the three notions. Building on this characterization, we paint a complete picture of the relationship between different variants of multi-group fairness, omniprediction, and Outcome Indistinguishability. This inquiry reveals a unified notion of OI that captures all existing notions of omniprediction and multicalibration.