A One-Inclusion Graph Approach to Multi-Group Learning
This addresses sample efficiency in multi-group learning, a domain-specific problem in machine learning, with incremental improvements to existing methods.
The paper tackles the sample complexity problem in multi-group learning by proving the tightest-known upper bounds and providing an algorithm that achieves optimal convergence rates. The algorithm achieves a log n/n convergence rate in the group-realizable setting (proven optimal) and a 1/n rate under a relaxed objective.
We prove the tightest-known upper bounds on the sample complexity of multi-group learning. Our algorithm extends the one-inclusion graph prediction strategy using a generalization of bipartite $b$-matching. In the group-realizable setting, we provide a lower bound confirming that our algorithm's $\log n / n$ convergence rate is optimal in general. If one relaxes the learning objective such that the group on which we are evaluated is chosen obliviously of the sample, then our algorithm achieves the optimal $1/n$ convergence rate under group-realizability.