Oracle Efficient Algorithms for Groupwise Regret
Krishna Acharya Eshwar Ram Arunachaleswaran Sampath Kannan Aaron Roth Juba Ziani
We study the problem of online prediction, in which at each time step $t$, an
individual $x_t$ arrives, whose label we must predict. Each individual is
associated with various groups, defined based on their features such as age,
sex, race etc., which may intersect. Our goal is to make predictions that have
regret guarantees not just overall but also simultaneously on each sub-sequence
comprised of the members of any single group. Previous work such as [Blum &
Lykouris] and [Lee et al] provide attractive regret guarantees for these
problems; however, these are computationally intractable on large model
classes. We show that a simple modification of the sleeping experts technique
of [Blum & Lykouris] yields an efficient reduction to the well-understood
problem of obtaining diminishing external regret absent group considerations.
Our approach gives similar regret guarantees compared to [Blum & Lykouris];
however, we run in time linear in the number of groups, and are
oracle-efficient in the hypothesis class. This in particular implies that our
algorithm is efficient whenever the number of groups is polynomially bounded
and the external-regret problem can be solved efficiently, an improvement on
[Blum & Lykouris]'s stronger condition that the model class must be small. Our
approach can handle online linear regression and online combinatorial
optimization problems like online shortest paths. Beyond providing theoretical
regret bounds, we evaluate this algorithm with an extensive set of experiments
on synthetic data and on two real data sets -- Medical costs and the Adult
income dataset, both instantiated with intersecting groups defined in terms of
race, sex, and other demographic characteristics. We find that uniformly across
groups, our algorithm gives substantial error improvements compared to running
a standard online linear regression algorithm with no groupwise regret
guarantees.