The sample complexity of multi-distribution learning
This work addresses a foundational problem in machine learning theory for researchers, settling the sample complexity of multi-distribution learning, which is incremental as it builds on prior work to close a known gap.
The paper tackles the problem of multi-distribution learning, which extends PAC learning to handle data from multiple distributions, and provides an algorithm with sample complexity that matches the lower bound up to a sub-polynomial factor, resolving an open problem from COLT 2023.
Multi-distribution learning generalizes the classic PAC learning to handle data coming from multiple distributions. Given a set of $k$ data distributions and a hypothesis class of VC dimension $d$, the goal is to learn a hypothesis that minimizes the maximum population loss over $k$ distributions, up to $ε$ additive error. In this paper, we settle the sample complexity of multi-distribution learning by giving an algorithm of sample complexity $\widetilde{O}((d+k)ε^{-2}) \cdot (k/ε)^{o(1)}$. This matches the lower bound up to sub-polynomial factor and resolves the COLT 2023 open problem of Awasthi, Haghtalab and Zhao [AHZ23].