Near-Optimal Algorithms for Omniprediction
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912766051221504 |
|---|---|
| author | Okoroafor, Princewill Kleinberg, Robert Kim, Michael P. |
| author_facet | Okoroafor, Princewill Kleinberg, Robert Kim, Michael P. |
| contents | Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class $H$, simultaneously for every loss function within a class of losses $L$. In this work, we give near-optimal learning algorithms for omniprediction, in both the online and offline settings. To begin, we give an oracle-efficient online learning algorithm that acheives $(L,H)$-omniprediction with $\tilde O (\sqrt{T \log |H|})$ regret for any class of Lipschitz loss functions $L \subseteq L_\mathrm{Lip}$. Quite surprisingly, this regret bound matches the optimal regret for \emph{minimization of a single loss function} (up to a $\sqrt{\log(T)}$ factor). Given this online algorithm, we develop an online-to-offline conversion that achieves near-optimal complexity across a number of measures. In particular, for all bounded loss functions within the class of Bounded Variation losses $L_\mathrm{BV}$ (which include all convex, all Lipschitz, and all proper losses) and any (possibly-infinite) $H$, we obtain an offline learning algorithm that, leveraging an (offline) ERM oracle and $m$ samples from $D$, returns an efficient $(L_{\mathrm{BV}},H,ε(m))$-omnipredictor for $\varepsilon(m)$ scaling near-linearly in the Rademacher complexity of a class derived from $H$ by taking convex combinations of a fixed number of elements of $\mathrm{Th} \circ H$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17205 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Algorithms for Omniprediction Okoroafor, Princewill Kleinberg, Robert Kim, Michael P. Machine Learning Data Structures and Algorithms Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class $H$, simultaneously for every loss function within a class of losses $L$. In this work, we give near-optimal learning algorithms for omniprediction, in both the online and offline settings. To begin, we give an oracle-efficient online learning algorithm that acheives $(L,H)$-omniprediction with $\tilde O (\sqrt{T \log |H|})$ regret for any class of Lipschitz loss functions $L \subseteq L_\mathrm{Lip}$. Quite surprisingly, this regret bound matches the optimal regret for \emph{minimization of a single loss function} (up to a $\sqrt{\log(T)}$ factor). Given this online algorithm, we develop an online-to-offline conversion that achieves near-optimal complexity across a number of measures. In particular, for all bounded loss functions within the class of Bounded Variation losses $L_\mathrm{BV}$ (which include all convex, all Lipschitz, and all proper losses) and any (possibly-infinite) $H$, we obtain an offline learning algorithm that, leveraging an (offline) ERM oracle and $m$ samples from $D$, returns an efficient $(L_{\mathrm{BV}},H,ε(m))$-omnipredictor for $\varepsilon(m)$ scaling near-linearly in the Rademacher complexity of a class derived from $H$ by taking convex combinations of a fixed number of elements of $\mathrm{Th} \circ H$. |
| title | Near-Optimal Algorithms for Omniprediction |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.17205 |