# On-Demand Sampling: Learning Optimally from Multiple Distributions

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 74 references that are in the map.
- First posted on arXiv 22 Oct 2022.

## Builds on (most cited first, 30 of 31)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [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)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Meta-Sim: Learning to Generate Synthetic Datasets](https://mlsanity.com/paper/1904.11621/) (2019)
- [Fair Attribute Classification through Latent Space De-biasing](https://mlsanity.com/paper/2012.01469/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [DeceptionNet: Network-Driven Domain Randomization](https://mlsanity.com/paper/1904.02750/) (2019)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning](https://mlsanity.com/paper/2103.03228/) (2021)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (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)
- [Do Outliers Ruin Collaboration?](https://mlsanity.com/paper/1805.04720/) (2018)
- [Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability](https://mlsanity.com/paper/2203.04536/) (2022)

## Built on by (most cited first, 30 of 39)

- [Robust Learning with Progressive Data Expansion Against Spurious Correlation](https://mlsanity.com/paper/2306.04949/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (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)
- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Differentially Private Worst-group Risk Minimization](https://mlsanity.com/paper/2402.19437/) (2024)
- [Multi-group Learning for Hierarchical Groups](https://mlsanity.com/paper/2402.00258/) (2024)
- [Agnostic Multi-Group Active Learning](https://mlsanity.com/paper/2306.01922/) (2023)
- [Learning In Reverse Causal Strategic Environments With Ramifications on Two Sided Markets](https://mlsanity.com/paper/2404.13240/) (2024)
- [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)
- [Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2302.09267/) (2023)
- [Safety vs. Performance: How Multi-Objective Learning Reduces Barriers to Market Entry](https://mlsanity.com/paper/2409.03734/) (2024)
- [Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization](https://mlsanity.com/paper/2410.23461/) (2024)
- [Learning With Multi-Group Guarantees For Clusterable Subpopulations](https://mlsanity.com/paper/2410.14588/) (2024)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [Property Elicitation on Imprecise Probabilities](https://mlsanity.com/paper/2507.05857/) (2025)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Assessing the Role of Data Quality in Training Bilingual Language Models](https://mlsanity.com/paper/2506.12966/) (2025)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [Taking a Moment for Distributional Robustness](https://mlsanity.com/paper/2405.05461/) (2024)
- [An Axiomatic Approach to Loss Aggregation and an Adapted Aggregating Algorithm](https://mlsanity.com/paper/2406.02292/) (2024)
- [On Calibration in Multi-Distribution Learning](https://mlsanity.com/paper/2412.14142/) (2024)
- [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)
- [Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget](https://mlsanity.com/paper/2602.17894/) (2026)

## Abstract (arXiv)

Social 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 learning, group distributionally robust optimization, and fair federated learning. In each of these settings, a learner seeks to uniformly minimize its expected loss over n predefined data 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. Importantly, our sample complexity bounds for multi-distribution learning exceed that of learning a single distribution by only an additive factor of n log(n) / ε2. This improves upon the best known sample complexity bounds for fair federated learning by Mohri et al. and collaborative learning by Nguyen and Zakynthinou by multiplicative factors of n and log(n)/ε3, respectively. We also provide the first sample complexity bounds for the group DRO objective of Sagawa et al. To guarantee these optimal sample complexity bounds, our algorithms learn to sample from data distributions on demand. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving stochastic zero-sum games. In particular, we contribute stochastic variants of no-regret dynamics that can trade off between players' differing sampling costs.