Towards Fundamental Limits for Active Multi-distribution Learning

Multi-distribution learning extends agnostic Probably Approximately Correct (PAC) learning to the setting in which a family of k distributions, Dii∈[k], is considered and a classifier's performance is measured by its error under the worst distribution. This problem has attracted a lot of recent interests due to its applications in collaborative learning, fairness, and robustness. Despite a rather complete picture of sample complexity of passive multi-distribution learning, research on active multi-distribution learning remains scarce, with algorithms whose optimality remaining unknown. In this paper, we develop new algorithms for active multi-distribution learning and establish improved label complexity upper and lower bounds, in distribution-dependent and distribution-free settings. Specifically, in the near-realizable setting we prove an upper bound of widetildeOBigl(θmax(d+k)lnfrac1varepsilonBigr) and widetildeOBigl(θmax(d+k)Bigl(lnfrac1varepsilon+fracnu2varepsilon2Bigr)+fracknuvarepsilon2Bigr) in the realizable and agnostic settings respectively, where θmax is the maximum disagreement coefficient among the k distributions, d is the VC dimension of the hypothesis class, nu is the multi-distribution error of the best hypothesis, and varepsilon is the target excess error. Moreover, we show that the bound in the realizable setting is information-theoretically optimal and that the knu/varepsilon2 term in the agnostic setting is fundamental for proper learners. We also establish instance-dependent sample complexity bound for passive multidistribution learning that smoothly interpolates between realizable and agnostic regimes~citepblum2017collaborative,zhang2024optimal, which may be of independent interest.