Learning Distributions from Multiple Data Providers
2026-07-27 • Data Structures and Algorithms
Data Structures and AlgorithmsComputer Science and Game TheoryMachine Learning
AI summaryⓘ
The authors study how to learn an unknown probability distribution when you can only get samples from certain subsets of the data (called queryable sets). They show that the ability to learn well depends on the structure of a graph that connects elements appearing together in these subsets. If this graph is fully connected, learning is easier and the required number of samples is roughly between linear and quadratic in the domain size. They identify conditions under which learning is nearly as easy as ordinary sampling, and demonstrate that all polynomial rates between linear and quadratic sample complexity are possible depending on the query sets.
distribution learningconditional samplesqueryable setsco-occurrence graphpointwise consistencyPAC learningsample complexityhierarchical comparabilitypolynomial rates
Authors
Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas
Abstract
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 $\mathscr{S} \subseteq 2^{[n]}$, and each query to $S \in \mathscr{S}$ returns an independent sample from the conditional distribution $p(\cdot \mid S)$. Learnability is governed by the co-occurrence graph associated with $\mathscr{S}$: 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(n^2/ε^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 $Θ(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 Θ(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 $α\in (1,2)$, there exists a query family with optimal PAC rate $\widetilde Θ(n^α/ε^2)$.