Sample-Optimal Multi-Group Learning with an ERM Oracle
Abstract
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper resolves a major open problem in multi-group learning by demonstrating that optimal sample complexity can be achieved with polynomially many calls to a weighted ERM oracle, matching the theoretical lower bound and eliminating the previous statistical penalty for computational efficiency.
Methodology
The paper addresses a fundamental gap in multi-group learning: achieving optimal sample complexity ($\tilde{O}((d_G+d_H)/\varepsilon^2)$) while remaining computationally efficient via an ERM oracle. Previous optimal algorithms required tracking weights for every group-hypothesis pair, which is infeasible for large classes, while oracle-based algorithms suffered from worse sample rates (typically $\varepsilon^{-3}$). The authors propose a novel reduction of the batch multi-group problem to a hybrid online learning setting. They introduce a "pair class" of functions that encode the joint output of a group and a hypothesis, allowing the use of Gaussian Follow-the-Perturbed-Leader (GFTPL) with a weighted ERM oracle. A key technical contribution is the "voting rule" that allows the learner to predict using the pair player's distribution without explicitly solving the joint optimization problem at each step. The paper also provides a rigorous lower bound showing that this sample complexity is optimal for any learner, even with unlimited computation, proving that oracle efficiency comes at no statistical cost. Additionally, they identify a "bounded membership" condition under which a simpler ERM oracle over the hypothesis class alone suffices, yielding improved rates in the realizable case.
Results & evaluation
This is a pure theory paper. There are no empirical experiments, datasets, or benchmarks. The "evaluation" consists of rigorous mathematical proofs of upper and lower bounds on sample complexity and oracle calls. The results are validated through reduction to classical agnostic learning lower bounds and analysis of the online-to-batch conversion.
Reproducibility
The paper provides full proofs in the appendix (implied by the structure, though the provided text is truncated). The algorithms are described in pseudocode (Algorithm 1, 2, 3). Since the contribution is theoretical, "reproducibility" refers to the verifiability of the proofs. The logical flow is clear, and the reliance on standard tools (VC dimension, Assouad's lemma, online learning regret bounds) makes the results accessible to experts in learning theory.
Limitations
The main limitation is the reliance on an ERM oracle over the *pair* class $(g,h)$. The paper proves that this joint oracle cannot generally be implemented from separate oracles for $G$ and $H$ without solving an NP-hard problem (Max-Cut reduction). While they provide a workaround for the "bounded membership" case, the general case still requires an oracle that can jointly optimize over groups and hypotheses, which may be computationally expensive or unavailable in practice for complex group structures. The deterministic predictor result requires a computable total order on the input space, which is a strong assumption not always met.
Broader impact
This work significantly advances the theory of fair and robust learning. Multi-group learning is a core component of subgroup fairness and robustness guarantees. By closing the gap between statistical optimality and computational efficiency, this paper provides a blueprint for designing practical algorithms that offer strong fairness guarantees without prohibitive computational costs. It bridges the gap between online learning theory and batch learning guarantees, offering new techniques (hybrid online-to-batch conversion with oracles) that could be applied to other structured prediction problems. The paper resolves a major open problem in multi-group learning by demonstrating that optimal sample complexity can be achieved with polynomially many calls to a weighted ERM oracle, matching the theoretical lower bound and eliminating the previous statistical penalty for computational efficiency.
Author of this paper? Send a correction.