mlsanityData to 7 Oct 2026

The sample complexity of multi-distribution learning

arXiv 2312.04027 ↗First posted 7 Dec 2023cs.LG cs.AI cs.DScited by 12

Not on the map. Why?

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].

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

Builds on

25 of 56 references.

References · 25

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  3. 2018Multi-Task Learning as Multi-Objective Optimizationcited by 809
  4. 2019Agnostic Federated Learningcited by 451
  5. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
  6. 2020An Investigation of Why Overparameterization Exacerbates Spurious Correlationscited by 310
  7. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  8. 2021Multi-group Agnostic PAC Learnabilitycited by 42
  9. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  10. 2021One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learningcited by 39
  11. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  12. 2019Limits of Private Learning with Access to Public Datacited by 38
13 more
  1. 2022Bagging is an Optimal PAC Learnercited by 34
  2. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  3. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 26
  4. 2021Adaptive Sampling for Minimax Fair Classificationcited by 24
  5. 2018Improved Algorithms for Collaborative PAC Learningcited by 20
  6. 2022Memory Bounds for Continual Learningcited by 18
  7. 2020Boosting Simple Learnerscited by 16
  8. 2022Online Prediction in Sub-linear Spacecited by 16
  9. 2018Tight Bounds for Collaborative PAC Learning via Multiplicative Weightscited by 15
  10. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  11. 2015Optimal and Adaptive Algorithms for Online Boostingcited by 12
  12. 2020Online Agnostic Boosting via Regret Minimizationcited by 12
  13. 2018Do Outliers Ruin Collaboration?cited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 4; 2026: 4.

12 papers.

  1. 2025Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyondcited by 15
  2. 2023Optimal Multi-Distribution Learningcited by 13
  3. 2024Derandomizing Multi-Distribution Learningcited by 5
  4. 2024Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsitycited by 5
  5. 2025How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimensioncited by 3
  6. 2024Collaborative Learning with Different Labeling Functionscited by 2
  7. 2025Towards Fundamental Limits for Active Multi-distribution Learningcited by 1
  8. 2025Sample-Adaptivity Tradeoff in On-Demand Samplingcited by 1
  9. 2026Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noisecited by 1
  10. 2026Optimal Deterministic Multicalibration and Omnipredictioncited by 1
  11. 2026A One-Inclusion Graph Approach to Multi-Group Learningcited by 0
  12. 2026Learning Distributions from Multiple Data Providerscited by 0