# Oracle Efficient Online Multicalibration and Omniprediction

**Authors:** Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth  
**arXiv:** [2307.08999](https://arxiv.org/abs/2307.08999)  
**Date:** 2023-07-18  
**Summary page:** https://www.summarizepaper.com/en/paper/2307.08999v1/

## Key points

- Paper explores the connection between multicalibration and omniprediction
- Focuses on studying omniprediction in the online adversarial setting
- Existing algorithms for multicalibration in online adversarial setting only work for small finite classes of benchmark functions
- Authors develop a new online multicalibration algorithm that is well-defined for infinite benchmark classes and oracle efficient
- Main contribution is the development of an efficient online omnipredictor that can obtain no regret guarantees for all Lipschitz convex loss functions
- Algorithm made efficient in worst case scenario when applied to linear functions, with upper and lower bounds on improvement rates provided
- Oracle efficient algorithm promises swap-omniprediction guarantee, but lower bound shows O(sqrt(T)) bounds impossible in online setting
- Non-oracle efficient algorithm achieves optimal O(sqrt(T)) omniprediction bounds without multicalibration
- Contributes to understanding of omniprediction in online adversarial setting and trade-offs between different solution concepts.

## Summary

This paper explores the connection between multicalibration, a multi-group fairness notion, and omniprediction, a learning paradigm that provides simultaneous loss minimization guarantees for a large family of loss functions. While previous work has focused on studying omniprediction in the batch setting, this paper initiates the study of omniprediction in the online adversarial setting. The authors note that existing algorithms for obtaining notions of multicalibration in the online adversarial setting only work for small finite classes of benchmark functions because they require enumerating every function at every round. However, omniprediction is most interesting for learning theoretic hypothesis classes, which are generally continuously large. To address this limitation, the authors develop a new online multicalibration algorithm that is well-defined for infinite benchmark classes. Importantly, this algorithm is also oracle efficient, meaning it can be reduced to a no-regret learning algorithm for any class F.

The main contribution of this work is the development of an efficient online omnipredictor – an oracle efficient prediction algorithm that can simultaneously obtain no regret guarantees for all Lipschitz convex loss functions. The authors demonstrate how their algorithm can be made efficient in the worst case scenario when applied to linear functions. Additionally, upper and lower bounds on the improvement rates are provided. The oracle efficient algorithm promises a stronger guarantee called swap-omniprediction. However, a lower bound is proven to show that obtaining O(sqrt(T)) bounds for swap-omniprediction is impossible in the online setting. On the other hand, the authors present a non-oracle efficient algorithm that can achieve optimal O(sqrt(T)) omniprediction bounds without going through multicalibration. This highlights an information theoretic separation between these two solution concepts. In conclusion, this paper introduces an oracle efficient online multicalibration algorithm and presents an efficient online omnipredictor that can simultaneously provide no regret guarantees for various loss functions. The results contribute to understanding of omniprediction in the online adversarial setting and provide insights into trade-offs between different solution concepts. Overall, this paper contributes to our understanding of both multicalibration and omniprediction by introducing an oracle efficient online multicalibration algorithm and presenting an efficient online omnipredictor with no regret guarantees for various loss functions while providing insights into trade-offs between different solution concepts.