Near-Optimal Algorithms for Omniprediction

Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class ℋ, simultaneously for every loss function within a class of losses ℒ. 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 achieves (ℒ, ℋ)-omniprediction with $\tilde O\left( {\sqrt {T\log |\mathcal{H}|} } \right)$ regret for any class of Lipschitz loss functions ℒ ⊆ ℒLip. Quite surprisingly, this regret bound matches the optimal regret for 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 ℒBV(which include all convex, all Lipschitz, and all proper losses) and any (possibly-infinite) ℋ, we obtain an offline learning algorithm that, leveraging an (offline) ERM oracle and m samples from $\mathcal{D}$, returns an efficient (ℒBV, ℋ, ε(m))-omnipredictor for ε(m) scaling near-linearly in the Rademacher complexity of Th◦ℋ, the class of all binary threshold functions on ℋ.