Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
Jiuyao Lu, Aaron Roth, Mirah Shi · 2025
Read Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses by Jiuyao Lu, Aaron Roth, Mirah Shi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12564.txt.
Description
Jiuyao Lu, Aaron Roth, and Mirah Shi study a learning problem that joins prediction with downstream choice. Their 2025 paper defines decision swap regret, a measure that covers both omniprediction and swap regret for agents who act on a forecast. The setting is online and adversarial, with losses that can be non-linear and multi-dimensional.
The authors give algorithms that reach this regret target for a broad class of smooth loss functions. A conversion trick then yields sample size bounds for the batch setting. For omniprediction, their bounds are the first to grow only polynomially for such losses. They also give sharper bounds for three utility families used in economics, where outcomes have many dimensions.
Catalog record
| CREATOR | Jiuyao Lu, Aaron Roth, Mirah Shi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 160 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12564