A One-Inclusion Graph Approach to Multi-Group Learning

In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}((d_G+d_H)/\varepsilon^2)$ samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where $d_G$ and $d_H$ are the VC dimensions of the group and hypothesis classes and $\varepsilon$ bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of $Ω((d_G+d_H)/\varepsilon^2)$ samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most $k$ groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with $\tilde{O}((d_H+\log k)/\varepsilon^2)$ samples in the agnostic setting and $\tilde{O}((d_H+\log k)/\varepsilon)$ samples when every group has a hypothesis that is correct on it.

Multi-group learning is a learning task that focuses on controlling predictors' conditional losses over specified subgroups. We propose ShakyPrepend, a method that leverages tools inspired by differential privacy to obtain improved theoretical guarantees over existing approaches. Through numerical experiments, we demonstrate that ShakyPrepend adapts to both group structure and spatial heterogeneity. We provide practical guidance for deploying multi-group learning algorithms in real-world settings.

We show every multi-group learner in the transductive setting may incur a multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting, and the penalty can increasing linearly with the number of groups, up to roughly the square-root of the sample size. This stands in stark contrast to optimal multi-group learners in an analogous (group-realizable) statistical setting, where the penalty is always at most logarithmic in the sample size and independent of the number of groups.