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

CREATORJiuyao Lu, Aaron Roth, Mirah Shi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE160 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12564

Browse the full library · About the Tower of Babel