We study the problem of online multi-group learning, a learning model in which an online learner must simultaneously achieve small prediction regret on a large collection of (possibly overlapping) subsequences corresponding to a family of groups. Groups are subsets of the context space, and in fairness applications, they may correspond to subpopulations defined by expressive functions of demographic attributes. In contrast to previous work on this learning model, we consider scenarios in which the family of groups is too large to explicitly enumerate, and hence we seek algorithms that only access groups via an optimization oracle. In this paper, we design such oracle-efficient algorithms with sublinear regret under a variety of settings, including: (i) the i.i.d. setting, (ii) the adversarial setting with smoothed context distributions, and (iii) the adversarial transductive setting.

我们研究在线多组学习的问题，这是一个学习模型，其中在线学习器必须同时在一个大规模的（可能有重叠的）子序列集合上实现小的预测遗憾，这些子序列对应于一个组的家族。在本文中，我们设计了这样的支持优化预测的算法，在多种情况下拥有亚线性的遗憾，包括：（i）独立同分布的情况，（ii）具有平滑上下文分布的对抗情况，以及（iii）对抗转导的情况。

在线多组学习的分组式高效算法