# Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2025.

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

- [Revisiting the Predictability of Performative, Social Events](https://mlsanity.com/paper/2503.11713/) (2025)
- [Three Types of Calibration with Properties and their Semantic and Formal Relationships](https://mlsanity.com/paper/2504.18395/) (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)
- [Robust Decision Making with Partially Calibrated Forecasts](https://mlsanity.com/paper/2510.23471/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Testable and Actionable Calibration for Full Swap Regret](https://mlsanity.com/paper/2605.17749/) (2026)
- [Defensive Generation](https://mlsanity.com/paper/2602.21390/) (2026)
- [Toward Simultaneously Optimal Regret in U-Calibration](https://mlsanity.com/paper/2606.18527/) (2026)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)
- [Prior-Agnostic Incentive-Compatible Exploration](https://mlsanity.com/paper/2602.20465/) (2026)

## Abstract (arXiv)

We define "decision swap regret" which generalizes both prediction for downstream swap regret and omniprediction, and give algorithms for obtaining it for arbitrary multi-dimensional Lipschitz loss functions in online adversarial settings. We also give sample complexity bounds in the batch setting via an online-to-batch reduction. When applied to omniprediction, our algorithm gives the first polynomial sample-complexity bounds for Lipschitz loss functions -- prior bounds either applied only to linear loss (or binary outcomes) or scaled exponentially with the error parameter even under the assumption that the loss functions were convex. When applied to prediction for downstream regret, we give the first algorithm capable of guaranteeing swap regret bounds for all downstream agents with non-linear loss functions over a multi-dimensional outcome space: prior work applied only to linear loss functions, modeling risk neutral agents. Our general bounds scale exponentially with the dimension of the outcome space, but we give improved regret and sample complexity bounds for specific families of multidimensional functions of economic interest: constant elasticity of substitution (CES), Cobb-Douglas, and Leontief utility functions.