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

CREATORPrincewill Okoroafor, Robert Kleinberg, Michael P. Kim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE248 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-17205

Browse the full library · About the Tower of Babel