Sample-Optimal Multi-Group Learning with an ERM Oracle

arXiv:2610.15916v1 Announce Type: new 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 ilde{O}((d_G+d_H)/arepsilon^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 arepsilon bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of Omega((d_G+d_H)/arepsilon^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 ilde{O}((d_H+log k)/arepsilon^2) samples in the agnostic setting and ilde{O}((d_H+log k)/arepsilon) samples when every group has a hypothesis that is correct on it.

Related

• Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
• The price of multi-group transductive learning
• An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension

Source: arXiv cs.LG | 2026-10-14