# The sample complexity of multi-distribution learning

arXiv: https://arxiv.org/abs/2312.04027 · HTML: https://mlsanity.com/paper/2312.04027/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 7 Dec 2023.

## Builds on (most cited first, 25 of 25)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [An Investigation of Why Overparameterization Exacerbates Spurious Correlations](https://mlsanity.com/paper/2005.04345/) (2020)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Limits of Private Learning with Access to Public Data](https://mlsanity.com/paper/1910.11519/) (2019)
- [One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning](https://mlsanity.com/paper/2103.03228/) (2021)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [Adaptive Sampling for Minimax Fair Classification](https://mlsanity.com/paper/2103.00755/) (2021)
- [Improved Algorithms for Collaborative PAC Learning](https://mlsanity.com/paper/1805.08356/) (2018)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Tight Bounds for Collaborative PAC Learning via Multiplicative Weights](https://mlsanity.com/paper/1805.09217/) (2018)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Optimal and Adaptive Algorithms for Online Boosting](https://mlsanity.com/paper/1502.02651/) (2015)
- [Online Agnostic Boosting via Regret Minimization](https://mlsanity.com/paper/2003.01150/) (2020)
- [Do Outliers Ruin Collaboration?](https://mlsanity.com/paper/1805.04720/) (2018)

## Built on by (most cited first, 12 of 12)

- [Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyond](https://mlsanity.com/paper/2501.10945/) (2025)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [Derandomizing Multi-Distribution Learning](https://mlsanity.com/paper/2409.17567/) (2024)
- [Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity](https://mlsanity.com/paper/2410.00690/) (2024)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise](https://mlsanity.com/paper/2602.21039/) (2026)
- [A One-Inclusion Graph Approach to Multi-Group Learning](https://mlsanity.com/paper/2603.23208/) (2026)
- [Learning Distributions from Multiple Data Providers](https://mlsanity.com/paper/2607.24732/) (2026)

## Abstract (arXiv)

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 widetildeO((d+k)ε-2) · (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].