Near-Optimal Algorithms for Omniprediction
Princewill Okoroafor, Robert Kleinberg, Michael P. Kim · 2025
Read Near-Optimal Algorithms for Omniprediction by Princewill Okoroafor, Robert Kleinberg, Michael P. Kim (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-2501-17205.txt.
Description
Princewill Okoroafor, Robert Kleinberg and Michael P. Kim give near-optimal algorithms for omniprediction in their 2025 arXiv paper. An omnipredictor is a single prediction rule that does well for many loss functions at once, measured against a class of candidate rules. That one-for-many trait makes it a flexible base for later decisions.
Their online algorithm reaches regret that matches, up to small factors, the best known bound for minimizing just one loss. They then convert it to an offline method that works for a broad class of losses, including convex and Lipschitz ones. Sample needs scale with a complexity measure of the candidate class, which keeps the method close to optimal.
Catalog record
| CREATOR | Princewill Okoroafor, Robert Kleinberg, Michael P. Kim |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 248 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-17205