# Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 24 Feb 2026.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [DoReMi: Optimizing Data Mixtures Speeds Up Language Model Pretraining](https://mlsanity.com/paper/2305.10429/) (2023)
- [Distributionally Robust Language Modeling](https://mlsanity.com/paper/1909.02060/) (2019)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Active Sampling for Min-Max Fairness](https://mlsanity.com/paper/2006.06879/) (2020)
- [Improved Algorithms for Collaborative PAC Learning](https://mlsanity.com/paper/1805.08356/) (2018)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Tight Bounds for Collaborative PAC Learning via Multiplicative Weights](https://mlsanity.com/paper/1805.09217/) (2018)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Agnostic Multi-Group Active Learning](https://mlsanity.com/paper/2306.01922/) (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)
- [Distribution-Dependent Rates for Multi-Distribution Learning](https://mlsanity.com/paper/2312.13130/) (2023)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [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)

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

- [Learning Distributions from Multiple Data Providers](https://mlsanity.com/paper/2607.24732/) (2026)

## Abstract (arXiv)

Towards understanding the statistical complexity of learning from heterogeneous sources, we study the problem of multi-distribution learning. Given k data sources, the goal is to output a classifier for each source by exploiting shared structure to reduce sample complexity. We focus on the bounded label noise setting to determine whether the fast 1/ε rates achievable in single-task learning extend to this regime with minimal dependence on k. Surprisingly, we show that this is not the case. We demonstrate that learning across k distributions inherently incurs slow rates scaling with k/ε2, even under constant noise levels, unless each distribution is learned separately. A key technical contribution is a structured hypothesis-testing framework that captures the statistical cost of certifying near-optimality under bounded noise-a cost we show is unavoidable in the multi-distribution setting. Finally, we prove that when competing with the stronger benchmark of each distribution's optimal Bayes error, the sample complexity incurs a textitmultiplicative penalty in k. This establishes a textitstatistical separation between random classification noise and Massart noise, highlighting a fundamental barrier unique to learning from multiple sources.