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, {Di}_i∈[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 distributionfree settings. Specifically, in the near-realizable setting we prove an upper bound of (Formula Presented) in the realizable and agnostic settings respectively, where θ_maxis the maximum disagreement coefficient among the k distributions, d is the VC dimension of the hypothesis class, ν is the multi-distribution error of the best hypothesis, and ε is the target excess error. Moreover, we show that the bound in the realizable setting is information theoretically optimal and that the kν/ε²term in the agnostic setting is fundamental for proper learners. We also establish instance-dependent sample complexity bound for passive multi-distribution learning that smoothly interpolates between realizable and agnostic regimes (Blum et al., 2017; Zhang et al., 2024), which may be of independent interest.