Near-Optimal Algorithms for Omniprediction

Understand

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).