On-Demand Sampling: Learning Optimally from Multiple Distributions ∗ Nika Haghtalab, Michael I. Jordan, and Eric Zhao University of California, Berkeley

Societal and real-world considerations such as robustness, fairness, social welfare and multi-agent tradeoffs have given rise to multi-distribution learning paradigms, such as collaborative [5], group distributionally robust [36], and fair federated learning [27]. In each of these settings, a learner seeks to minimize its worstcase loss over a set of n predefined distributions, while using as few samples as possible. In this paper, we establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity.