你想知道从多个供应商凑数据学分布有多难吗？这篇论文给出了从线性到二次的完整样本复杂度图谱，还找到了层次可比性这个好用的结构条件。
本文研究在有限域[n]上从多个数据提供者学习未知分布p的问题，每个查询返回条件分布p(·|S)的独立样本。可学习性由查询集的共现图决定：当图在目标支撑上连通时可达点态一致性，完全图时可达PAC学习。PAC学习的最优样本复杂度范围从近线性到二次：完全共现图族复杂度为Õ(n²/ε²)，紧界；当[n]本身可查询时复杂度为Θ(n/ε²)，即使所有子集可查询也无法改进。作者识别了层次可比性作为近线性复杂度（Õ(n/ε²)）的充分条件，并展示对于每个α∈(1,2)存在查询族达到最优PAC率Θ(n^α/ε²)。
Learning Distributions from Multiple Data Providers
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)$.