Oracle Efficient Online Multicalibration and Omniprediction
Sumegha Garg Christopher Jung Omer Reingold Aaron Roth
A recent line of work has shown a surprising 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. Prior work studies omniprediction in the batch
setting. We initiate the study of omniprediction in the online adversarial
setting. Although there exist algorithms for obtaining notions of
multicalibration in the online adversarial setting, unlike batch algorithms,
they work only for small finite classes of benchmark functions $F$, because
they require enumerating every function $f \in F$ at every round. In contrast,
omniprediction is most interesting for learning theoretic hypothesis classes
$F$, which are generally continuously large.
  We develop a new online multicalibration algorithm that is well defined for
infinite benchmark classes $F$, and is oracle efficient (i.e. for any class
$F$, the algorithm has the form of an efficient reduction to a no-regret
learning algorithm for $F$). The result is the first efficient online
omnipredictor -- an oracle efficient prediction algorithm that can be used to
simultaneously obtain no regret guarantees to all Lipschitz convex loss
functions. For the class $F$ of linear functions, we show how to make our
algorithm efficient in the worst case. Also, we show upper and lower bounds on
the extent to which our rates can be improved: our oracle efficient algorithm
actually promises a stronger guarantee called swap-omniprediction, and we prove
a lower bound showing that obtaining $O(\sqrt{T})$ bounds for
swap-omniprediction is impossible in the online setting. On the other hand, we
give a (non-oracle efficient) algorithm which can obtain the optimal
$O(\sqrt{T})$ omniprediction bounds without going through multicalibration,
giving an information theoretic separation between these two solution concepts.