Learning Distributions from Multiple Data Providers¶

会议: NeurIPS 2026
arXiv: 2607.24732
OpenReview: https://openreview.net/forum?id=GJbuWXhmG5
领域: 学习理论
关键词: 分布学习, 受限条件采样, 共现图, 样本复杂度, 马尔可夫链

一句话总结¶

本文针对来自异构且重叠数据提供商的受限条件采样问题，首次建立了离散分布学习的完备理论框架，证明了共现图连通性是点态一致性的充要条件、完全图是 PAC 可学性的充要条件，并揭示了样本复杂度在 $\widetilde{\Theta}(n/\varepsilon^2)$ 至 $\widetilde{\Theta}(n^2/\varepsilon^2)$ 之间的多项式连续谱。

研究背景与动机¶

现代生成模型和基础大模型的扩展严重依赖海量高质量训练数据，然而公开网页级爬虫数据的边际效益递减，人类生成的高质量数据正逐渐成为模型扩展的关键瓶颈。这促使开发者转向由众多专业化、异质且互有重叠的独立数据提供商组成的数据市场。然而，不同数据源的覆盖范围和重叠模式存在两面性：专精于特定垂直领域的提供商能够提供密集且高质量的局部数据，却无法揭示该子领域在全局总体分布中的真实比重；相反，同时采购多个宽泛的大型数据源又会因大面积重叠造成冗余开销与样本信号稀释。

在统计学习理论中，这一现实挑战可以抽象为受限条件采样模型下的分布学习问题：目标是估计有限全集 $[n]$ 上的未知离散概率分布 $p$，但学习者无法直接从全集采样，只能自适应地向固定的子集族 $\mathcal{S}\subseteq 2^{[n]}$ 提问，并获得对应集合的条件样本 $p(\cdot \mid S)$。经典条件采样理论（$\mathsf{COND}$）大多假设任意子集均可查询，并借此加速分布测试；而在现实采购场景中，查询族 $\mathcal{S}$ 是预先固定且受限的。这一设定的核心矛盾在于：定性上，何种集合重叠拓扑足以校准并恢复全局分布；定量上，定性可学后，查询族的几何结构如何决定最优样本复杂度，是否会出现不同查询结构导致样本复杂度剧烈劣化的现象。

本文的研究切入点是将子集重叠关系编码为超图的 2-截面图（共现图），并系统解析信息在重叠集合间传播与稀释的机理。核心 idea：以共现图拓扑精确刻画定性可学性（连通对应点态一致，完全对应 PAC 可学），并通过构造可逆马尔可夫链采样与树状分层比较机制，完整证明了 PAC 样本复杂度从近线性 $\widetilde{\Theta}(n/\varepsilon^2)$ 到二次方极差 $\widetilde{\Theta}(n^2/\varepsilon^2)$ 的连续多项式谱。

方法详解¶

整体框架¶

算法的目标是在给定查询族 $\mathcal{S}$ 与精度参数 $\varepsilon, \delta$ 的条件下，输出一个在全变差距离（Total Variation, TV）意义下满足 $d_{\mathrm{TV}}(\widehat{p}, p) \le \varepsilon$ 的经验分布 $\widehat{p}$。学习者无法直接获取全局样本，但可以通过查询 $S \in \mathcal{S}$ 获得条件采样，当集合概率质量 $p(S)=0$ 时遵循标准的 $\mathsf{UNIF0}$ 约定返回集合内均匀采样。

整个理论与算法框架分为定性判定与定量学习两大部分：首先根据目标支撑集 $U \subseteq [n]$ 在查询族 $\mathcal{S}$ 下诱导的共现图 $\mathrm{CO}(\mathcal{S}, U)$ 判定可学性模式；若仅图连通且支撑已知，则通过生成树比率累乘实现点态一致性；若图完全，则保证全局一致的 PAC 可学。在 PAC 学习中，根据查询族是否满足“分层可比性”，分别选用基于可逆马尔可夫链采样的通用二次学习器，或基于平衡二叉划分树的近线性递归分解学习器。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：查询族 S、目标支撑 U、误差 ε 与置信度 δ"] --> B["拓扑判定：构建共现图 CO(S, U)"]
    B -->|仅连通 & 支撑已知| C["生成树比率累乘估计"]
    B -->|完全图| D{"查询族局部几何结构"}
    D -->|通用完全图| E["对称见证集构造与模拟马尔可夫链"]
    D -->|分层可比族| F["平衡二叉划分树与局部链分裂估计"]
    E --> G["独立重启动截断采样"]
    F --> H["根到叶路径分裂比率连乘重构"]
    G --> I["输出全局分布估计 p_hat (TV ≤ ε)"]
    H --> I
    C --> J["输出点态收敛估计 (依赖分布常数)"]

关键设计¶

1. 共现图拓扑判定与定性可学性分离：在受限查询下，任意两个元素 $x, y$ 能够在某个查询集 $S \in \mathcal{S}$ 中同时出现是直接估计相对比率 $p_x/p_y$ 的唯一统计信道。将所有二元共现关系连接成边即可得到共现图 $\mathrm{CO}(\mathcal{S}, U)$。论文证明，当支撑集精确已知时，图连通即可选取生成树 $\mathcal{T}$，通过在每条边对应的见证集上采样并累乘边缘频率估计值 $\prod p_{v_i}/p_{v_{i-1}}$ 恢复全局分布（定理 3.1）。然而在标准的分布无关 PAC 设定或未知支撑集中，若图非完全，则存在未直接相连的非相邻点对；此时若分布在所有中间桥梁点上赋予趋近于 0 的质量，桥梁信号在有限样本下将被统计淹没，导致不同分布产生全变差距离为常数但在观测转录本上不可区分的退化情况。因此，完全共现图是保证有限样本 PAC 可学的充要拓扑条件（定理 3.2）。

2. 模拟可逆马尔可夫链采样与二次方通用上界：针对任意具备完全共现图的查询族，为了避免繁琐且误差级联放大的全图参数比率估计，论文设计了一种基于单步条件查询的可逆马尔可夫链模拟机制（算法 1）。对任意无序点对 $\{x, y\}$，固定一个对称见证集合 $W_{xy} = W_{yx} \in \mathcal{S}$ 使得 $x, y \in W_{xy}$。当游走处于状态 $x$ 时，均匀随机挑选候选转移点 $y \in U \setminus \{x\}$，查询 $W_{xy}$ 并观察样本 $z$：若 $z = y$ 则接受转移进入 $y$，否则保持在 $x$。该转移核显式满足细致平稳条件： $$p_x K(x, y) = \frac{1}{m - 1} \frac{p_x p_y}{p(W_{xy})} = p_y K(y, x)$$ 因此真实未知分布 $p$ 天然是该马尔可夫链的平稳分布。进一步，由于见证集合包含当前点 $x$，其总概率必然满足 $p(W_{xy}) \ge p_x$，由此推导出均匀 Doeblin 次微化条件 $K(x, \cdot) \ge \frac{1}{m - 1} p(\cdot)$。该条件直接给出了全变差几何收缩率 $(1 - \frac{1}{m-1})^t \le e^{-t/(m-1)}$，从而链在 $B = \lceil (m-1) \log(2/\varepsilon) \rceil$ 步内即可达到与平稳分布距离不超过 $\varepsilon/2$。学习者通过独立运行 $M = \Theta((m + \log(1/\delta))/\varepsilon^2)$ 次该链并记录末态，即可利用经验测度获得总体样本复杂度为 $\widetilde{O}(m^2/\varepsilon^2)$ 的通用 PAC 学习器（定理 4.2）。

3. 中心稀释下界与分层可比性的近线性突破：通用二次上界并非马氏链证明松弛，而是完全共现图在最差情况下的本质界限。论文构造了“中心轮毂稀释”（Hub Dilution）反例：一个中心轮毂点 $0$ 拥有常数质量 $1/2$，其余 $2m$ 个轻量元素分成 $m$ 对，查询集均为包含中心点与两对元素的 5 元集。此时每个查询集合中，绝大多数条件样本都被中心点 $0$ 吸收，要看到轻量元素的有效转移必须耗费 $\Theta(m)$ 次无意义查询，结合 Fano 不等式精确导出 $\Omega(n^2/\varepsilon^2)$ 下界（定理 4.3）。为了克服轮毂稀释，论文提出了“分层可比性”（Hierarchical Comparability，定义 5）：域 $U$ 允许构建深度为 $O(\log |U|)$ 的平衡二叉划分树 $\mathcal{T}$，且内部节点 $C$ 内的任意点对 $\{x, y\}$ 均可在完全局限于 $C$ 内部的见证集 $W_C(\{x,y\}) \subseteq C$ 中进行比较。通过树结构上的局部马氏链直接估计左右子树质量分裂比例 $\alpha_C = p(C_L \mid C)$，配合可逆马氏链的 Bernstein 集中不等式，利用树状 KL 链式法则将全变差误差分解到 $D$ 层树深上： $$D_{\mathrm{KL}}(p \parallel \widehat{p}) = \sum_{C \in \mathcal{I}(\mathcal{T}): p(C) > 0} p(C) D_{\mathrm{KL}}(\mathrm{Bern}(\alpha_C) \parallel \mathrm{Bern}(\widehat{\alpha}_C))$$ 最终以 $\widetilde{O}(n/\varepsilon^2)$ 近线性样本开销完成全局重构（定理 4.4）。

4. 粗粒度商域构造与多项式连续谱：为了探明在线性与二次方之间是否存在其他复杂性阶次，论文引入了非均匀块扩张（Block Lift）技术（定理 4.10）。将全域划分为 $H$ 个粗粒度原子（含一个中心轮毂），每个粗原子内部扩张为规模可调的紧致子块，块内允许完全查询，而块间则通过包含轮毂的硬查询族连接。学习该分布被严格正交分解为两部分：在粗粒度商域上校准 $H$ 个原子的质量（复杂度 $\widetilde{\Theta}(H^2/\varepsilon^2)$）与在各块内部学习条件分布（复杂度 $\widetilde{\Theta}(n/\varepsilon^2)$），总复杂度为 $\widetilde{\Theta}((n + H^2)/\varepsilon^2)$。通过选取 $H \asymp n^{(1+\gamma)/2}$，对任意 $\gamma \in (0, 1)$，成功构造出最优 PAC 样本复杂度精确为 $\widetilde{\Theta}(n^{1+\gamma}/\varepsilon^2)$ 的查询族，严密证明了复杂度连续谱的存在。

实验关键数据¶

主实验：不同查询拓扑下的 PAC 样本复杂度理论界限¶

论文为理论奠基工作，其核心结果通过信息论与统计极限定理建立了不同受限查询结构下的极小化极大（minimax）样本复杂度界限。

查询族结构 $\mathcal{S}$	共现图拓扑 $\mathrm{CO}(\mathcal{S}, U)$	PAC 最优样本复杂度 $q^*_{\mathcal{S}, \mathcal{P}_U}(\varepsilon, \delta)$	最优性说明与下界依据	复杂度阶次类型
全子集族 $2^{[n]} \setminus \{\emptyset\}$	完全图 (全连接)	$\Theta(n/\varepsilon^2)$	信息论下界：全集单步独立采样已达下界，条件采样无法打破（定理 4.1）	经典线性界
成对查询族 $\binom{[n]}{2}$	完全图 (边完备)	$\widetilde{\Theta}(n/\varepsilon^2)$	满足分层可比性，上界为 $O(\frac{n (\log n)^2 \log(n/\delta)}{\varepsilon^2})$（推论 4.5）	近线性界
分层可比族 (如区间/超立方体)	完全图 (局部完备)	$\widetilde{\Theta}(n/\varepsilon^2)$	递归二叉划分树局部 Markov 链模拟，深度 $O(\log n)$（定理 4.4）	近线性界
块扩张粗粒度族 ($H \asymp n^{\frac{1+\gamma}{2}}$)	完全图 (两级结构)	$\widetilde{\Theta}(n^{1+\gamma}/\varepsilon^2)$	粗粒度轮毂下界与局部块采样的匹配匹配上界，$\forall \gamma \in (0, 1)$（定理 4.10）	多项式中间谱
最差完全共现族 (轮毂稀释族)	完全图 (轮毂主导)	$\widetilde{\Theta}(n^2/\varepsilon^2)$	匹配 Fano 编码下界 $\Omega(n^2/\varepsilon^2)$ 与通用 Markov 链上界（定理 4.2, 4.3）	最差二次界
非完全共现图族	不完全图 (含非相邻点)	$+\infty$ (不可 PAC 学习)	零质量桥梁反例导致 TV 间隔 $\ge 1/6$ 下观测分布 TV 距离趋近 0（定理 3.2）	不可学

消融实验：定性与定量学习条件对结构假设的敏感性分析¶

下表对比了学习目标、支撑假设与图拓扑约束变化时的行为跃迁，清晰展示了各项结构假设的必要性与边界。

学习保证模式	支撑集先验假设	充要结构条件	样本复杂度收敛行为	破坏假设后的失效机制
PAC 学习 ($\mathcal{P}_U$)	允许零质量子集	$\mathrm{CO}(\mathcal{S}, U)$ 完全	$\widetilde{O}(n^2/\varepsilon^2)$ 至 $\widetilde{\Theta}(n/\varepsilon^2)$	若缺失一条边，非相邻两点分配极小桥梁质量即可完全混淆转录本分布
点态一致性 ($\mathcal{P}_U^+$)	精确已知全支撑	$\mathrm{CO}(\mathcal{S}, U)$ 连通	速率 $O(C_{p, \mathcal{S}, U} \frac{\log(1/\delta)}{\varepsilon^2})$，依赖 $p$	若图不连通，连通分支间无法建立相对缩放比率，参数不可辨识
点态一致性 ($\mathcal{P}_U$)	允许零质量子集	$\mathrm{CO}(\mathcal{S}, U)$ 完全	与 PAC 相同，退化为完全图要求	中间桥梁质量为 0 时路径断裂，退化为两两无法比较
近线性 PAC 学习	任意非空子集	分层可比性 (定义 5)	$O(\frac{n (\log n)^2 \log(n/\delta)}{\varepsilon^2})$	若缺乏树局部见证集，跨层查询将引入大尺度集合的质量稀释，退化至高阶项

关键发现¶

拓扑充分性与复杂度分离：共现图完全性是 PAC 可学性的精确拓扑分界线，但完全性本身无法约束样本速率；拓扑同为完全图的查询族，其最优样本复杂度可以跨越从 $O(n \log^2 n / \varepsilon^2)$ 到 $\Omega(n^2 / \varepsilon^2)$ 的整整一个 $n$ 因子。
信息稀释的本质：高维数据提供商的“广度重叠”并不等价于“高信息量”。如果重叠总是伴随着高概率主导项（如高频模式、通用停用词或轮毂类别），条件采样将被大概率主导项湮没，有效信噪比降低 $1/n$ 倍，直接导致二次方样本爆炸。
递归局部化的治愈作用：只要数据提供商能够提供细分领域的局部对比能力（即分层可比性），即便学习者每次只能在极小的局部（如成对比较）查询，依然能够通过多级分治达到与全域自由采样相同的近线性复杂度。

亮点与洞察¶

首次将现实数据市场中的多源数据采购与组合问题抽象为形式化的受限条件采样理论，打通了超图 2-截面理论、可逆马尔可夫链分析与极小化极大分布学习。
提出的模拟马尔可夫链构造极其精巧：利用对称见证集 $W_{xy}$ 与单步判定规则，完全无需显式估计各集合的配分函数或边缘概率，自然利用细致平稳条件逼近目标分布。
建立了非均匀块扩张理论，不仅证明了连续谱定理（定理 4.10），而且为理解复杂网络数据源的分层商空间学习提供了通用的代数降维与升维分析框架。

局限与展望¶

理论上虽然在多项式阶次上紧致，但近线性界与二次界中仍残留若干 $\log n$ 及 $\log(1/\varepsilon)$ 的多对数因子差距，尚未给出精确的常数级匹配。
当前理论严格限定在有限离散支撑集 $[n]$ 上，对于连续域、可数无穷状态空间或带有潜在几何嵌入的连续分布学习尚未涵盖。
论文仅探讨了在已知固定查询族 $\mathcal{S}$ 下的被动/主动选择策略，未引入经济学定价机制（如每个提供商具有不同的单次查询成本）下的预算受限最优设计。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立受限条件采样分布学习的完备理论框架并证明连续谱定理
实验充分度: ⭐⭐⭐⭐⭐ 理论证明完备自洽，涵盖严密的信息论 Fano 下界与构造性马氏链上界
写作质量: ⭐⭐⭐⭐⭐ 叙述极为清晰，动机直指大模型扩展瓶颈，数学推导干净优美
价值: ⭐⭐⭐⭐⭐ 为多源数据集成、数据要素市场采购设计与受限生成建模提供了坚实的理论基石

查询族结构 \(\mathcal{S}\)	共现图拓扑 \(\mathrm{CO}(\mathcal{S}, U)\)	PAC 最优样本复杂度 \(q^*_{\mathcal{S}, \mathcal{P}_U}(\varepsilon, \delta)\)	最优性说明与下界依据	复杂度阶次类型
全子集族 \(2^{[n]} \setminus \{\emptyset\}\)	完全图 (全连接)	\(\Theta(n/\varepsilon^2)\)	信息论下界：全集单步独立采样已达下界，条件采样无法打破（定理 4.1）	经典线性界
成对查询族 \(\binom{[n]}{2}\)	完全图 (边完备)	\(\widetilde{\Theta}(n/\varepsilon^2)\)	满足分层可比性，上界为 \(O(\frac{n (\log n)^2 \log(n/\delta)}{\varepsilon^2})\)（推论 4.5）	近线性界
分层可比族 (如区间/超立方体)	完全图 (局部完备)	\(\widetilde{\Theta}(n/\varepsilon^2)\)	递归二叉划分树局部 Markov 链模拟，深度 \(O(\log n)\)（定理 4.4）	近线性界
块扩张粗粒度族 (\(H \asymp n^{\frac{1+\gamma}{2}}\))	完全图 (两级结构)	\(\widetilde{\Theta}(n^{1+\gamma}/\varepsilon^2)\)	粗粒度轮毂下界与局部块采样的匹配匹配上界，\(\forall \gamma \in (0, 1)\)（定理 4.10）	多项式中间谱
最差完全共现族 (轮毂稀释族)	完全图 (轮毂主导)	\(\widetilde{\Theta}(n^2/\varepsilon^2)\)	匹配 Fano 编码下界 \(\Omega(n^2/\varepsilon^2)\) 与通用 Markov 链上界（定理 4.2, 4.3）	最差二次界
非完全共现图族	不完全图 (含非相邻点)	\(+\infty\) (不可 PAC 学习)	零质量桥梁反例导致 TV 间隔 \(\ge 1/6\) 下观测分布 TV 距离趋近 0（定理 3.2）	不可学

学习保证模式	支撑集先验假设	充要结构条件	样本复杂度收敛行为	破坏假设后的失效机制
PAC 学习 (\(\mathcal{P}_U\))	允许零质量子集	\(\mathrm{CO}(\mathcal{S}, U)\) 完全	\(\widetilde{O}(n^2/\varepsilon^2)\) 至 \(\widetilde{\Theta}(n/\varepsilon^2)\)	若缺失一条边，非相邻两点分配极小桥梁质量即可完全混淆转录本分布
点态一致性 (\(\mathcal{P}_U^+\))	精确已知全支撑	\(\mathrm{CO}(\mathcal{S}, U)\) 连通	速率 \(O(C_{p, \mathcal{S}, U} \frac{\log(1/\delta)}{\varepsilon^2})\)，依赖 \(p\)	若图不连通，连通分支间无法建立相对缩放比率，参数不可辨识
点态一致性 (\(\mathcal{P}_U\))	允许零质量子集	\(\mathrm{CO}(\mathcal{S}, U)\) 完全	与 PAC 相同，退化为完全图要求	中间桥梁质量为 0 时路径断裂，退化为两两无法比较
近线性 PAC 学习	任意非空子集	分层可比性 (定义 5)	\(O(\frac{n (\log n)^2 \log(n/\delta)}{\varepsilon^2})\)	若缺乏树局部见证集，跨层查询将引入大尺度集合的质量稀释，退化至高阶项