{"id":1537,"date":"2025-01-30T07:03:18","date_gmt":"2025-01-30T07:03:18","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/01\/30\/2501-17205\/"},"modified":"2025-01-30T07:03:18","modified_gmt":"2025-01-30T07:03:18","slug":"2501-17205","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/01\/30\/2501-17205\/","title":{"rendered":"Near-Optimal Algorithms for Omniprediction"},"content":{"rendered":"

Near-Optimal Algorithms for Omniprediction
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2501.17205v1 Announce Type: new
\nAbstract: 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,eps(m))$-omnipredictor for $eps(m)$ scaling near-linearly in the Rademacher complexity of $mathrm{Th} circ H$.<\/div>\n

\t

\n
<\/BR>
\n Princewill Okoroafor, Robert Kleinberg, Michael P. Kim
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Near-Optimal Algorithms for Omniprediction arXiv:2501.17205v1 Announce Type: new Abstract: 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, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,413,113,112],"tags":[636,1551,1486],"class_list":["post-1537","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-ds","category-cs-lg","category-stat-ml","tag-loss","tag-near","tag-optimal"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/1537"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=1537"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/1537\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=1537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=1537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=1537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}