# Fast Rates for Swap-Agnostic Learning of Proper Losses

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 30 Jul 2026.

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

- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [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)
- [Optimization of Scoring Rules](https://mlsanity.com/paper/2007.02905/) (2020)
- [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)
- [Faster Recalibration of an Online Predictor via Approachability](https://mlsanity.com/paper/2310.17002/) (2023)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [BayesCNS: A Unified Bayesian Approach to Address Cold Start and Non-Stationarity in Search Systems at Scale](https://mlsanity.com/paper/2410.02126/) (2024)
- [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)

## Abstract (arXiv)

Swap-agnostic learning strengthens classical agnostic learning by allowing the comparator to select a different hypothesis on each level set of the learner's predictions. This benchmark captures prediction-dependent postprocessing, but appears to require solving a separate agnostic-learning problem for every possible prediction value. We show that, for proper losses, these prediction-level comparisons can instead be controlled jointly. Our main result is an offline swap-agnostic learner for any fixed proper loss. For a finite hypothesis class H and any fixed smooth proper loss, the excess risk from m i.i.d. samples is widetildeO((log |H|/m)2/3), with a corresponding online swap-regret bound of widetildeO(T1/3(log |H|)2/3). We also give algorithms whose predictions are simultaneously swap-agnostic for entire families of losses. For all proper losses bounded in [-1,1], we obtain online and offline rates of widetildeO(√Tlog |H|) and widetildeO(√log |H|/m), respectively. For convex, 1-Lipschitz proper losses, these rates improve to widetildeO(T1/3(log |H|)2/3) online and widetildeO((log |H|/m)2/3) offline. These bounds are tight up to logarithmic factors and improve upon the widetildeO(T2/3(log |H|)1/3) rate implied by the swap-omniprediction guarantee of Luo et al. (2025). Our main technical contribution is a reduction from swap-agnostic learning to a second-order form of multicalibration, obtained via Blackwell approachability with a Bernstein-style variance correction.