Near-Optimal Algorithms for Omniprediction

Title: Near-Optimal Algorithms for Omniprediction

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, we give an oracle-efficient online learning algorithm that acheives (L, H)-omniprediction with O(\sqrt{T log |H|}) regret for any class of Lipschitz loss functions L ⊆ LLip. 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 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 ε(m) scaling near-linearly in the Rademacher complexity of Th ◦ H. 

Bio: Princewill Okoroafor is currently completing his final year as a PhD student in the Computer Science Department at Cornell University, advised by Robert Kleinberg. Princewill is interested in theoretical aspects of machine learning. His current research centers around designing online and statistical learning algorithms that satisfy desirable fairness guarantees, such as calibration, and are robust to deviations in practice. Princewill obtained his Bachelor's degree from Harvey Mudd College, majoring in Computer Science and Mathematics. This research was funded by the Cornell CIS-Linkedin Fellowship.