arXiv preprint ·
Sample-Optimal Multi-Group Learning with an ERM Oracle
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Do Rollups Self-Organize? Multi-Agent Reinforcement Learning in the EIP-4844 Blob Fee Market
Improved Combinatorial Auctions with and without Samples
Representation Theorems for Actual Powers over Two-Agent General Concurrent Game Frames
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Improving the Bounds on Approximating Weighted Maximin Share for Chores
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.