# Optimal Multi-Distribution Learning

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 44 references that are in the map.
- First posted on arXiv 8 Dec 2023.

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

- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [An Investigation of Why Overparameterization Exacerbates Spurious Correlations](https://mlsanity.com/paper/2005.04345/) (2020)
- [Meta-Sim: Learning to Generate Synthetic Datasets](https://mlsanity.com/paper/1904.11621/) (2019)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Fairness-aware Agnostic Federated Learning](https://mlsanity.com/paper/2010.05057/) (2020)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Coping with Label Shift via Distributionally Robust Optimisation](https://mlsanity.com/paper/2010.12230/) (2020)
- [Multi-source Domain Adaptation in the Deep Learning Era: A Systematic Survey](https://mlsanity.com/paper/2002.12169/) (2020)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [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)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Active Sampling for Min-Max Fairness](https://mlsanity.com/paper/2006.06879/) (2020)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Improved Algorithms for Collaborative PAC Learning](https://mlsanity.com/paper/1805.08356/) (2018)
- [Tight Bounds for Collaborative PAC Learning via Multiplicative Weights](https://mlsanity.com/paper/1805.09217/) (2018)
- [Statistical Inference for Maximin Effects: Identifying Stable Associations across Multiple Studies](https://mlsanity.com/paper/2011.07568/) (2020)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Magging: maximin aggregation for inhomogeneous large-scale data](https://mlsanity.com/paper/1409.2638/) (2014)
- [Communication-Aware Collaborative Learning](https://mlsanity.com/paper/2012.10569/) (2020)
- [Guided Adversarial Robust Transfer Learning with Source Mixing](https://mlsanity.com/paper/2309.06534/) (2023)

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

- [Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyond](https://mlsanity.com/paper/2501.10945/) (2025)
- [Distributionally Robust Policy Learning under Concept Drifts](https://mlsanity.com/paper/2412.14297/) (2024)
- [Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity](https://mlsanity.com/paper/2410.00690/) (2024)
- [Minimax Regret Estimation for Generalizing Heterogeneous Treatment Effects with Multisite Data](https://mlsanity.com/paper/2412.11136/) (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)
- [Learning Pareto manifolds in high dimensions: How can regularization help?](https://mlsanity.com/paper/2503.08849/) (2025)
- [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)
- [Multi-Objective Learning for Diffusion Models: A Statistical Theory under Semi-Supervised Learning](https://mlsanity.com/paper/2605.25210/) (2026)

## Abstract (arXiv)

Multi-distribution learning (MDL), which seeks to learn a shared model that minimizes the worst-case risk across k distinct data distributions, has emerged as a unified framework in response to the evolving demand for robustness, fairness, multi-group collaboration, etc. Achieving data-efficient MDL necessitates adaptive sampling, also called on-demand sampling, throughout the learning process. However, there exist substantial gaps between the state-of-the-art upper and lower bounds on the optimal sample complexity. Focusing on a hypothesis class of Vapnik-Chervonenkis (VC) dimension d, we propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2 (modulo some logarithmic factor), matching the best-known lower bound. Our algorithmic ideas and theory are further extended to accommodate Rademacher classes. The proposed algorithms are oracle-efficient, which access the hypothesis class solely through an empirical risk minimization oracle. Additionally, we establish the necessity of randomization, revealing a large sample size barrier when only deterministic hypotheses are permitted. These findings resolve three open problems presented in COLT 2023 (i.e., citet[Problems 1, 3 and 4]awasthi2023sample).