Learning Distributions from Multiple Data Providers

This paper investigates the fundamental limits of learning an unknown discrete distribution $p$ over a finite domain $[n]$ when a learner is restricted to querying a fixed family of subsets $\mathscr{S}$. Each query to a set $S \in \mathscr{S}$ provides an independent sample from the conditional distribution $p(\cdot \mid S)$. The authors aim to characterize the conditions under which such a distribution can be learned (qualitative learnability) and determine the optimal number of samples required (quantitative sample complexity) based on the overlap structure of the query sets.

The authors define the co-occurrence graph $CO(\mathscr{S}, U)$, where vertices are elements of the target support $U$, and an edge exists between two elements if they appear together in at least one queryable set $S \in \mathscr{S}$. They analyze the relationship between the topology of this graph and the ability to perform PAC learning versus pointwise consistent learning. By examining various query families, they map the sample complexity landscape, identifying structural conditions—such as hierarchical comparability—that allow for efficient learning.

• Qualitative Learnability: PAC learning is possible if and only if the co-occurrence graph is complete. Pointwise consistency is achievable under the weaker condition that the co-occurrence graph is connected.
• Sample Complexity Landscape: The optimal sample complexity for PAC learning varies significantly. While full conditional access allows for $\Theta(n/\epsilon^2)$ complexity, restricted query families can require anywhere from $\widetilde{\Theta}(n/\epsilon^2)$ to $\widetilde{\Theta}(n^2/\epsilon^2)$ samples.
• Redundant overlap (where queries repeatedly expose a common high-mass element) leads to quadratic complexity. Conversely, hierarchical structures that support recursive localization enable nearly linear sample complexity, similar to the efficiency seen in pairwise comparison models.