Near-Optimal Algorithms for Omniprediction

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 (√T log |H|) regret for any class of Lipschitz loss functions L subseteq LLip. Quite surprisingly, this regret bound matches the optimal regret for minimization of a single loss function (up to a √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 LBV (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 (LBV,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 Th circ H.