高效学习截断布尔乘积分布：影响力助力

# 高效学习截断布尔乘积分布：借助影响力的方法  
来源：https://arxiv.org/html/2607.22889  

Ioannis Panageas²²  
加州大学尔湾分校, ipanagea@uci\.edu (https://arxiv.org/html/2607.22889v1/[email protected]),  
受 NSF 基金 CCF\-2454115 资助  
加州大学尔湾分校  

###### 摘要  

学习离散分布 \( \mu_z \) 的自然参数 \( z \in \mathbb{R}^n \)，该分布受限于子集 \( S \subseteq \{0,1\}^n \)，并且基于独立样本，是高维统计学中的一个基础挑战。现有高效估计截断布尔乘积分布的方法（特别是 [Fotakis et al’ COLT’20, Algorithmica ’22] 的工作）要求对 \( S \) 有很强的局部连通性假设——这一性质被称为“fatness”——或者严格的反集中性假设，并且要求截断集的总质量相对于 \( n \) 为常数。此外，[Fotakis et al’ COLT’20, Algorithmica ’22] 的结果在 \( S \) 的质量相对 \( n \) 指数小时，样本复杂度会达到 \( \Omega(2^n) \)。在这项工作中，我们通过分析 \( S \) 在测度 \( \mu_z \) 下的几何结构来规避这些限制。我们在 fatness 假设下改进了现有的参数估计保证，将 \( \ell_\infty \) 恢复的先前样本复杂度提升至 \( \mathcal{O}(\log n / \epsilon^2) \)，与未截断的极小极大率相匹配。我们进一步利用布尔函数分析中使用的“影响力”概念推广了 fatness，并为高效推断提供了充分条件。值得注意的是，与先前工作不同，我们的方法不需要在模型的任意参数化下进行采样。最后，我们建立了一个理论下界，表明样本复杂度对模型的宽度和集合中元素之间的最小距离具有内在的指数依赖性。  

## 1 引言  

从截断样本中学习是统计学领域中一个历史悠久且具有挑战性的问题，其目标是在给定位于测度支撑子集 \( S \) 上的样本时，估计潜在真实分布的模型参数。截断样本出现在许多领域，如经济学、工程学、生物科学和网络等，经典例子包括在收集医学实验对象时的抽样偏差以及精算分析中的幸存者偏差。从截断样本中进行严格的统计估计至少可以追溯到 1760 年，当时 Daniel Bernoulli 分析了天花治疗方法的效果（bernoulli1760essai）。这项分析开启了由 Pearson、Galton 和 Fisher 研究的一系列工作（galton1898examination; pearson1902systematic; pearson1908generalised; fisher1931properties），旨在开发在截断环境下进行稳健估计和检验的技术。  

近年来，在开发计算和统计上高效的算法以学习截断下的连续和离散分布方面，出现了大量活动。从 daskalakis2018efficient 的工作开始，该工作分析了在已知截断集下多元高斯分布的恰当学习，可证明高效的学习保证已扩展到未知截断下的多元高斯分布（kontonis2019efficient）、带截断数据的线性回归（daskalakis2019computationally）、已知或未知截断下的指数族（lee2023learning; lee2024efficient）以及其他连续环境。  

受基因组学（eng2019transcriptome; ghosh2001lateral）和网络（durvy2006packing; zafer2006blocking）中等众多复杂离散截断分布的例子启发，fotakis2022efficientparameterestimationtruncated 启动了对从截断样本中估计离散模型参数的研究，为截断布尔乘积分布中的推断开发了高效算法。与前述关于连续环境中截断估计的工作所使用的技术类似，作者证明了一个非平凡的生存质量 \( \mu(S) \geq \alpha \) 和一个全局反集中性条件，例如 \( \operatorname{Cov}_{\boldsymbol{x} \sim \mu}(\boldsymbol{x}) \succeq \lambda I \)，其中 \( \alpha, \lambda \) 为 \( \Theta(1) \)，足以进行推断。然而，在这些假设下，得到的样本复杂度可能达到 \( \mathsf{poly}(1/\alpha)^{\mathsf{poly}(1/\lambda)} \)³³³参见 fotakis2022efficientparameterestimationtruncated 的 arXiv 版本 (arXiv:2007.02392v3) 中的定理 4 (p. 20)。当 \( \lambda = o(1) \) 随问题参数变化时，这会变得令人望而却步。这与 fotakis2022efficientparameterestimationtruncated 中相关的下界形成鲜明对比，该下界对 \( \alpha \) 没有依赖性，且量级为 \( \mathsf{poly}(1/\lambda) \)。找到在此机制下运行的高效算法是一个诱人的开放问题。  

此外，相关的随机梯度方法不仅需要估计真实参数处的梯度，还需要估计候选模型邻域内的梯度，这需要从一系列截断分布 \( \mu_S \) 中进行拒绝采样，对应于许多相邻参数。这样的要求对于乘积分布来说已经十分微妙，而对于一般的马尔可夫随机场则变得更加难以维持，因为在其中采样是公认的难题。  

fotakis2022efficientparameterestimationtruncated 中不依赖于生存质量的那些算法保证依赖于局部信息；给定位于 \( S \) 中的样本 \( \boldsymbol{x} \sim \mu \)，作者旨在通过条件密度 \( \mathbf{Pr}_{\boldsymbol{x} \sim \mu}(x_i \mid \boldsymbol{x}_{-i}) \) 来估计潜在参数。对任何给定样本具有良好的“平均”局部连通性的想法被 (fotakis2022efficientparameterestimationtruncated) 形式化为“fatness”的概念，该概念将分布称为 \( \gamma \)-fat，如果对于所有 \( i \in [n] \)，有 \( \mathbf{Pr}_{\boldsymbol{x} \sim \mu}((1-x_i, \boldsymbol{x}_{-i}) \in S) \geq 1/\mathsf{poly}(n) = \gamma \)。作者随后在此条件下证明了高效的参数估计和采样。  

然而，在许多感兴趣的集合中，例如所有具有偶数个 1 的布尔向量集合（奇偶性集合），没有一个元素具有单翻转邻居，这违反了该假设，并导致条件分布崩溃。为了弥补这一差异，在这项工作中，我们研究了从潜在模型的独立同分布 (i.i.d.) 样本中高效恢复超立方体 \(\{0,1\}^n\) 上截断乘积分布（最简单的离散分布类）参数的任务。我们希望开发一个框架来分析这些分布，超越对 \( S \) 质量的限制、严格的反集中性假设以及单翻转局部连通性，从而引出以下问题：是否存在计算上高效的算法，可以在不依赖于生存质量和严格局部连通性条件的情况下学习截断布尔乘积分布？  

我们在这项工作中的主要贡献是通过推广 “fatness” 的概念以涵盖更广泛的截断集，对上述问题给出了肯定答案。  

### 1.1 我们的结果  

与需要从未截断分布中采样或估计截断似然的全局梯度的方法不同，我们转而利用乘积测度下截断集的局部结构。令 \( \mu_{\boldsymbol{p}} \) 为 \( \{0,1\}^n \) 上的布尔乘积测度，即一个坐标独立且 \( \mathbf{Pr}_{\boldsymbol{x} \sim \mu_{\boldsymbol{p}}}(x_i=1) = p_i \in (0,1) \) 的分布。我们假设可以访问一个截断集 \( S \subseteq \{0,1\}^n \) 的预言机，并观察来自 \( \mu_{\boldsymbol{p} \mid S} \) 的样本，即 \( \mu_{\boldsymbol{p}} \) 在 \( S \) 上的条件分布。我们的主要目标是计算真实参数向量 \( \boldsymbol{p} \) 的估计量 \( \widehat{\boldsymbol{p}} \)，使得以至少 \( 1-\delta \) 的概率，有 \( \|\widehat{\boldsymbol{p}} - \boldsymbol{p}\|_\infty \leq \epsilon \)，并且运行时间是 \( n, 1/\epsilon, \log(1/\delta) \) 的多项式。我们还考虑估计相应的自然参数 \( \boldsymbol{z} \)，其按坐标定义为 \( z_i = \log(p_i/(1-p_i)) \)，其中 \( i \in [n] \)。在 \( \boldsymbol{p} \) 参数化下学习对应于伯努利概率的加性误差，而在 \( \boldsymbol{z} \) 参数化下学习对应于控制对数几率 (log-odds) 的误差，从而为潜在概率提供相对误差的概念。  

我们的第一个贡献是在假设截断测度 \( \mu_{\boldsymbol{p} \mid S} \) 是 \( \gamma \)-fat 的情况下，改进了估计的样本复杂度。粗略地说，\( \mu_{\boldsymbol{p} \mid S} \) 在坐标 \( i \) 上是 \( \gamma \)-fat 的，如果对于 \( \boldsymbol{x} \sim \mu_{\boldsymbol{p} \mid S} \) 以至少 \( \gamma \) 的概率，其邻居点 \( (1-x_i, \boldsymbol{x}_{-i}) \) 也位于 \( S \) 中。这意味着在 \( \gamma \) 比例的截断样本上，第 \( i \) 个坐标的两个取值都是可行的，而其余坐标固定，因此 \( x_i \) 的条件分布揭示了原始乘积分布的相应一维边际信息。在这个意义上，fatness 是 \( S \) 上的一个条件内部连通性条件。  

###### 非正式定理 1（在 \( \gamma \)-fatness 下学习）。令 \( \boldsymbol{x}^{(1)}, \dots, \boldsymbol{x}^{(N)} \) 为来自一个 \( \gamma \)-fat 截断布尔乘积分布 \( \mu \) 的 i.i.d. 样本，并假设 \( \|\boldsymbol{z}\|_\infty \leq R \)。存在多项式时间算法，能够从 \( N = \mathcal{O}\left(\frac{\log(n/\delta)}{\gamma \epsilon^2}\right) \) 个样本中估计概率向量，达到 \( \ell_\infty \) 误差 \( \epsilon \)，以及从 \( N = \mathcal{O}\left(\frac{e^{2R} \log(n/\delta)}{\gamma \epsilon^2}\right) \) 个样本中估计自然参数向量，达到 \( \ell_\infty \) 误差 \( \epsilon \)，每种情况概率至少为 \( 1-\delta \)。  

该样本复杂度相比先前工作提升了 \( \log(n) \) 倍，并且在 \( \gamma \in \Theta(1) \) 时达到了估计截断布尔乘积分布的极小极大率，因为每个坐标估计到精度 \( \epsilon \) 需要 \( 1/\epsilon^2 \) 量级的样本，再加上 \( \log(n/\delta) \) 因子用于统一的 \( \ell_\infty \) 控制。此外，该界限仅依赖于局部 fatness 参数 \( \gamma \)，而与全局生存质量 \( \mu_{\boldsymbol{p}}(S) \) 无关。假设 fatness 成立，这些算法即使在之前提到的反集中性参数 \( \lambda \in o(1) \) 时也能给出多项式样本复杂度⁴⁴⁴模型的宽度 \( R \) 与 fotakis2022efficientparameterestimationtruncated 中反集中性参数之间的关系在附录 A (https://arxiv.org/html/2607.22889#A1) 中详细说明。。  

然而，fatness 的概念对于许多自然的截断集来说限制性过强。例如，奇偶性集合 \( S = \{ x \in \{0,1\}^n : \sum_i x_i \equiv 0 \pmod{2} \} \) 没有单坐标连通性。对于每个 \( i \in [n], \boldsymbol{x} \in S \)，有 \( \mathbf{Pr}_{\boldsymbol{x} \sim \mu_{\boldsymbol{z} \mid S}}((1-x_i, \boldsymbol{x}_{-i}) \in S) = 0 \)，这意味着任何仅基于单比特翻转的分析都是无效的。尽管如此，奇偶性在双比特翻转下保持不变，并且将对所有不在 \( \{i,j\} \) 中的坐标取条件会得到一个非平凡的一维伯努利问题，其自然参数是 \( z_i + z_j \) 或 \( z_i - z_j \)。这表明应将直接协调估计 \( z_i \) 替换为对稀疏线性形式 \( \boldsymbol{w}_I^\top \boldsymbol{z} \) 的估计，其中 \( \boldsymbol{w}_I \in \{-1,0,1\}^n \) 支撑在小的坐标集 \( I \) 上。为了形式化这种高阶移动的存在性，我们使用以下条件影响力的概念。  

###### 定义 1.1（条件影响力）。给定一个截断布尔乘积分布 \( \mu_{\boldsymbol{z} \mid S} \) 和一个坐标集 \( I \subseteq [n] \)，定义 \( I \) 的条件影响力为  
\[
\textrm{Inf}_I^{\,\mu_{\boldsymbol{z} \mid S}} := \mathbf{Pr}_{\boldsymbol{x} \sim \mu_{\boldsymbol{z} \mid S}}\!\left[ \boldsymbol{x}^{\oplus I} \notin S \right],
\]  
其中 \( \boldsymbol{x}^{\oplus I} = (1 - \boldsymbol{x}_I, \boldsymbol{x}_{-I}) \) 表示通过对 \( \boldsymbol{x} \) 中所有 \( I \) 内的坐标进行翻转得到的向量。因此，\( \textrm{Inf}_I^{\,\mu_{\boldsymbol{z} \mid S}} \) 是从截断分布中抽取的样本在同时翻转 \( I \) 中的坐标后变得不可行的概率；等价地，此翻转的可行性概率为 \( 1 - \textrm{Inf}_I^{\,\mu_{\boldsymbol{z} \mid S}} \)。  

我们回忆一下，布尔影响力的传统概念记录的是在特定翻转下布尔函数值改变的概率。在当前设置中，定义 1.1 (https://arxiv.org/html/2607.22889#S1.Thmdefinition1) 是此概念对于 \( S \) 的指示函数在原始点位于 \( S \) 条件下的单侧版本。此外，\( \gamma \)-fatness 等价于对每个坐标 \( i \) 有 \( \textrm{Inf}_{\{i\}}^{\,\mu_{\boldsymbol{z} \mid S}} \leq 1-\gamma \)。我们的框架用高阶条件取代了这一单坐标要求：即使每个单坐标翻转都不可行，只要足够多的小集合 \( I \) 的可行性概率 \( 1 - \textrm{Inf}_I^{\,\mu_{\boldsymbol{z} \mid S}} \) 远离零，并且关联的向量 \( \boldsymbol{w}_I \) 以数量上稳定的方式张成 \( \mathbb{R}^n \)，学习仍然可能是可行的。为了使模型可识别（参见 fotakis2022efficientparameterestimationtruncated 的假设 1），我们需要 \( S \) 的仿射张成是 \( \mathbb{R}^n \)。这意味着存在可行的翻转方向张成 \( \mathbb{R}^n \)（参见引理 A.3 (https://arxiv.org/html/2607.22889#A1.Thmlemma3)）。然而，如果除了可识别性之外没有数量上的条件，相应的可行性概率可能是指数小的，并且带符号的设计可能是任意病态的。因此，我们施加两个结构假设。第一个确保一个坐标集族 \( \mathcal{F} \) 以至少 \( \gamma \) 的概率给出最小可行翻转。第二个，带符号的反集中性，确保诱导的量 \( \boldsymbol{w}_I^\top \boldsymbol{z} \) 共同以数量上稳定的方式识别参数向量的每个方向。在这些假设下，推