# Learning Distributions from Multiple Data Providers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 27 Jul 2026.

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

- [DoReMi: Optimizing Data Mixtures Speeds Up Language Model Pretraining](https://mlsanity.com/paper/2305.10429/) (2023)
- [Data Mixing Laws: Optimizing Data Mixtures by Predicting Language Modeling Performance](https://mlsanity.com/paper/2403.16952/) (2024)
- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Active Ranking with Subset-wise Preferences](https://mlsanity.com/paper/1810.10321/) (2018)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [DAVED: Data Acquisition via Experimental Design for Data Markets](https://mlsanity.com/paper/2403.13893/) (2024)
- [Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing](https://mlsanity.com/paper/1807.06168/) (2018)
- [Optimal mass estimation in the conditional sampling model](https://mlsanity.com/paper/2503.12518/) (2025)
- [Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise](https://mlsanity.com/paper/2602.21039/) (2026)

## Abstract (arXiv)

Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution p on a finite domain [n]. The learner is given a fixed family of queryable sets mathscrS subseteq 2[n], and each query to S ∈ mathscrS returns an independent sample from the conditional distribution p(· mid S). Learnability is governed by the co-occurrence graph associated with mathscrS: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete. The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Every query family with complete co-occurrence graph admits sample complexity widetilde O(n2/ε2), and this bound is tight in the worst case. On the other hand, if [n] is queryable then ordinary sampling improves the bound to Theta(n/ε2), and this cannot be improved further even if every set is queryable. More generally, we identify hierarchical comparabilityas a sufficient structural condition on mathscr S under which the optimal complexity is nearly linear, widetilde Theta(n/ε2), with pairwise query families as a canonical example. Finally, the full range of polynomial rates between linear and quadratic is attainable: for every α ∈ (1,2), there exists a query family with optimal PAC rate widetilde Theta(nα/ε2).