从格劳伯轨迹中学习不依赖混合的高斯图模型

# 从无需混合的 Glauber 轨迹学习高斯图模型

来源：https://arxiv.org/html/2606.31230

Tony Wu¹⁰⁻¹ [email protected]  
MIT  

Mahbod Majid [email protected]  
MIT  

Ankur Moitra [email protected]  
MIT  

部分受 DARPA expMath、微软可信赖人工智能资助、NSF-CCF 2430381、ONR 资助以及 David and Lucile Packard Fellowship 支持。

###### 摘要

我们研究从单条 Glauber 动力学轨迹学习 \(n\) 个变量上的 \(d\)-稀疏高斯图模型结构的任务。除了算法考虑之外，许多应用呈现的是时间上相关的观测，而非 i.i.d. 样本。在经典的 i.i.d. 设置下，在相当一般的稀疏性和最小边强度假设下，已知次线性于 \(n\) 的样本保证，但以多项式时间实现这些保证仍然是开放问题。部分受此差距驱动，我们给出一个多项式时间算法，该算法从单条 Glauber 轨迹恢复条件独立图，其轨迹长度保证不依赖于混合时间。技术上，我们的算法包含三个部分。首先，我们估计条件方差并重新缩放轨迹，从而归约为单位对角情形，而不改变底层图。其次，我们设计一个局部边检验，通过隔离成对影响，从短更新窗口中提取邻接信息。第三，我们使用基于中位数的鲁棒估计器聚合这些局部统计量，并在源于单条轨迹的时间依赖存在下证明其准确性。

###### 目录

1. 1 引言 (https://arxiv.org/html/2606.31230#S1)  
   1.1 结果 (https://arxiv.org/html/2606.31230#S1.SS1)  
   1.2 相关工作 (https://arxiv.org/html/2606.31230#S1.SS2)  
2. 2 技术概述 (https://arxiv.org/html/2606.31230#S2)  
3. 3 预备知识 (https://arxiv.org/html/2606.31230#S3)  
   3.1 连续时间 Glauber 动力学 (https://arxiv.org/html/2606.31230#S3.SS1)  
   3.2 观测模式 (https://arxiv.org/html/2606.31230#S3.SS2)  
   3.3 污染与鲁棒估计 (https://arxiv.org/html/2606.31230#S3.SS3)  
   3.4 集中不等式 (https://arxiv.org/html/2606.31230#S3.SS4)  
   3.5 混合与耦合 (https://arxiv.org/html/2606.31230#S3.SS5)  
4. 4 归约为归一化高斯图模型 (https://arxiv.org/html/2606.31230#S4)  
   4.1 统计量的性质 (https://arxiv.org/html/2606.31230#S4.SS1)  
   4.2 获取估计量 (https://arxiv.org/html/2606.31230#S4.SS2)  
   4.3 归一化高斯分布 (https://arxiv.org/html/2606.31230#S4.SS3)  
5. 5 主算法 (https://arxiv.org/html/2606.31230#S5)  
   5.1 统计量的性质 (https://arxiv.org/html/2606.31230#S5.SS1)  
   5.2 获取估计量 (https://arxiv.org/html/2606.31230#S5.SS2)  
6. 6 带混合的学习 (https://arxiv.org/html/2606.31230#S6)  
   6.1 统计量的性质 (https://arxiv.org/html/2606.31230#S6.SS1)  
   6.2 边检测 (https://arxiv.org/html/2606.31230#S6.SS2)  
7. 7 信息论下界 (https://arxiv.org/html/2606.31230#S7)  
   7.1 图类 (https://arxiv.org/html/2606.31230#S7.SS1)  
   7.2 KL 散度的界 (https://arxiv.org/html/2606.31230#S7.SS2)  
   7.3 Fano 方法 (https://arxiv.org/html/2606.31230#S7.SS3)  
8. 参考文献 (https://arxiv.org/html/2606.31230#bib)  
9. A 鲁棒估计量 (https://arxiv.org/html/2606.31230#A1)  
10. B 连续时间与更新次数 (https://arxiv.org/html/2606.31230#A2)  
11. C 先前工作分析中的一个技术缺口 (https://arxiv.org/html/2606.31230#A3)  
12. D 非退化性不控制特征值 (https://arxiv.org/html/2606.31230#A4)

## 1 引言

一个*高斯图模型*（GGM）在 \(n\) 个顶点上是一个均值为零的高斯随机变量 \(X \sim \mathcal{N}(0, \Sigma)\)。与图结构相关的对象是*精度矩阵* \(\Theta := \Sigma^{-1}\)。我们将一个无向图 \(G = (V, E)\) 与 \(\Theta\) 关联起来，当 \(\Theta_{ij} \neq 0\) 时就在 \((i, j)\) 之间放置一条边。关键事实是，对于高斯分布，\(\Theta\) 中的零恰好编码了条件独立性：对于不同的 \(i, j \in V\)，
\[
X_i \perp X_j \mid X_{V \setminus \{i, j\}} \quad \Longleftrightarrow \quad \Theta_{ij} = 0.
\]
这被称为马尔可夫性质。GGM 复杂性的一个重要度量是*稀疏性*：我们说 GGM 是 \(d\)-稀疏的，如果每个顶点在 \(G\) 中至多有 \(d\) 个邻居，等价地，\(\Theta\) 的每一行至多有 \(d\) 个非零非对角元素。

GGM 提供了一种自然的方式来表示许多相互作用变量之间的*条件依赖结构*。关于 GGM 应用的文献过于庞大，无法在此综述，但代表性例子包括神经科学和脑连接 [DMG+20 (https://arxiv.org/html/2606.31230#bib.bib12), HLS+10 (https://arxiv.org/html/2606.31230#bib.bib11)]、基因组学 [YZL+22 (https://arxiv.org/html/2606.31230#bib.bib14)]、代谢通路重建 [KSI+11 (https://arxiv.org/html/2606.31230#bib.bib13)]、气候科学 [ZFL+14 (https://arxiv.org/html/2606.31230#bib.bib10)]、金融系统性风险建模 [CG16 (https://arxiv.org/html/2606.31230#bib.bib4)] 以及环境心理学 [BMS+19 (https://arxiv.org/html/2606.31230#bib.bib3)]。此类应用中反复出现的场景是高维性，其中变量数量 \(n\) 可能等于或大于可用观测数，这促使我们将重点放在稀疏 GGM 上，其条件独立图的最大度数至多为 \(d\)。

算法上，主要挑战已经出现在*结构学习*中：恢复边集 \(E\)（等价地，\(\Theta\) 的支持集）。实际上，一旦知道了 \(G\)，估计系数就简化为运行 \(n\) 个低维（回归）问题，每个问题仅涉及一个节点的 \(d\) 个邻居。更精确地说，对于每个节点 \(i \in V\)，\(X_i\) 在给定其余坐标时的条件分布为
\[
X_i = -\sum_{j \in N(i)} \frac{\Theta_{ij}}{\Theta_{ii}} X_j + \xi_i, \quad \xi_i \sim \mathcal{N}\left(0, \frac{1}{\Theta_{ii}}\right).
\]
因此，给定 \(G\)，估计 \(\Theta\) 简化为 \(n\) 个回归问题，将 \(X_i\) 对 \(\{X_j : j \in N(i)\}\) 进行回归，从而恢复系数 \(\{-\Theta_{ij}/\Theta_{ii}\}_{j \in N(i)}\) 和噪声方差 \(1/\Theta_{ii}\)。

在经典的 i.i.d. 数据模型中，Misra、Vuffray 和 Lokhov [MVL20 (https://arxiv.org/html/2606.31230#bib.bib20)] 研究了学习稀疏 GGM 的信息论样本复杂度，*不*假设有界谱或不相关性。他们所做的唯一假设是以下关于最小归一化边强度的保证：
\[
\frac{|\Theta_{ij}|}{\sqrt{\Theta_{ii}\Theta_{jj}}} \geq \alpha \quad \forall (i,j) \in E,
\]
（非退化性）
这是一个自然的非退化条件，确保存在的边不是任意弱的。重要的是要注意，这个约束并*不*对归一化矩阵的最小特征值施加任何假设，谱可能是任意病态的。关于这一点的简单演示，见附录 D (https://arxiv.org/html/2606.31230#A4)。他们表明，信息论上 \(O(d \log n / \alpha^2)\) 个 i.i.d. 样本就足以学习图结构。Wang、Wainwright 和 Ramchandran 的早期工作 [WWR10 (https://arxiv.org/html/2606.31230#bib.bib22)] 表明，对于此任务至少需要 \(\Omega(\log n / \alpha^2)\) 个 i.i.d. 样本，目前尚不清楚上界和下界哪个是紧的。然而，代价是计算上的： [MVL20 (https://arxiv.org/html/2606.31230#bib.bib20)] 的算法使用基于 \(\ell_0\)-约束稀疏线性回归的穷举搜索，运行时间为 \(n^{\Omega(d)}\)。是否能为一般 GGM 以多项式时间算法匹配信息论样本复杂度仍然是一个开放问题。更广泛地，存在证据表明在相关稀疏线性回归问题中存在计算障碍。特别地，在固定设计、最坏情况的设置下，*恰当*稀疏线性回归——即算法必须在存在 \(k\)-稀疏解时输出一个 \(k\)-稀疏预测器——是 NP-难的 [NAT95 (https://arxiv.org/html/2606.31230#bib.bib8), ZWJ14 (https://arxiv.org/html/2606.31230#bib.bib9)]。

在许多科学环境中，观测不是 i.i.d. 的；相反，我们观测到一个随时间演化的系统。这种时间依赖的一个自然简化模型是一个马尔可夫链，其平稳分布是 GGM，例如单点 Gibbs 抽样（Glauber 动力学）。如果链混合迅速，那么通过将观测间隔至少为混合时间，我们可以获得近似独立的样本，并归约到经典的 i.i.d. 设置。然而，即使对于高斯目标，基于混合的归约也可能不令人满意。实际上，对于多元正态目标，单点 Gibbs 有一个显式的线性算子描述，其收敛率由相关更新矩阵的谱控制 [AMI91 (https://arxiv.org/html/2606.31230#bib.bib7), RS97 (https://arxiv.org/html/2606.31230#bib.bib6)]。此外，这种收敛行为在坐标的对角缩放下是不变的，因此它用归一化精度矩阵 \(\Theta' = D^{-1/2} \Theta D^{-1/2}\) 表示，其中 \(D = \operatorname{diag}(\Theta_{11}, \ldots, \Theta_{nn})\)。例如，单点 Gibbs 的一个标准谱间隙界意味着
\[
t_{\mathrm{mix}}(\varepsilon) \approx n \frac{1}{\lambda_{\min}(\Theta')} \log(1/\varepsilon),
\tag{1}
\]
其中等式成立到绝对常数 [RS97 (https://arxiv.org/html/2606.31230#bib.bib6), AMI91 (https://arxiv.org/html/2606.31230#bib.bib7)]。由于在非退化性 (https://arxiv.org/html/2606.31230#S1.Ex3) 约束下 \(\lambda_{\min}(\Theta')\) 可以任意小，¹ 混合时间可以任意大。这引出了我们的主要问题：
> *是否有可能从单条 Glauber 轨迹学习稀疏 GGM 的结构，而无需等待链混合，也无需对精度矩阵 \(\Theta\) 施加额外假设？*

我们通过给出一个高效算法来肯定地回答这个问题，该算法从单条轨迹恢复图，既不依赖混合时间，也不需要对精度矩阵施加除非退化性 (https://arxiv.org/html/2606.31230#S1.Ex3) 条件之外的额外假设。在下一节中，我们形式化模型并陈述我们的主要定理。

### 1.1 结果

我们首先回顾两个定义，它们形式化了我们的设置：\((\alpha, d)\)-稀疏高斯图模型和单点 Glauber 动力学。

###### 定义 1.1 (\((\alpha, d)\)-稀疏高斯图模型)。
令 \(\Sigma \in \mathbb{R}^{n \times n}\) 为正定矩阵，并令 \(\Theta := \Sigma^{-1}\)。对于 \(\alpha > 0\) 和整数 \(d \geq 1\)，我们说 \(X \sim \mathcal{N}(0, \Sigma)\) 是一个 \((\alpha, d)\)-稀疏 GGM，如果由 \((i, j) \in E \iff \Theta_{ij} \neq 0\) 定义在 \(V = [n]\) 上的图 \(G = (V, E)\) 的最大度数至多为 \(d\)，并且每条边具有至少 \(\alpha\) 的归一化强度，即
\[
\left| \frac{\Theta_{ij}}{\sqrt{\Theta_{ii} \Theta_{jj}}} \right| \geq \alpha \quad \forall (i, j) \in E.
\]
我们将 \(G\) 称为（条件独立）图或模型的稀疏模式。

接下来我们定义 GGM 的 Glauber 动力学。我们处理连续时间动力学，其中每个坐标具有独立的速率为 1 的泊松时钟，因此链每单位时间预期执行 \(n\) 次更新。

###### 定义 1.2 (GGM 的连续时间 Glauber 动力学)。
对于精度矩阵为 \(\Theta\) 的 GGM，其连续时间 Glauber 动力学是一个取值于 \(\mathbb{R}^n\) 的随机过程 \(\{Y^{(t)}\}_{t \geq 0}\)。它从任意（可能是随机的或最坏情况的）向量 \(Y^{(0)}\) 初始化，并在随机时间 \(\{S^{(\ell)}\}_{\ell \in \mathbb{N}}\) 更新，其中 \(S^{(0)} = 0\)，\(S^{(\ell)}\) 是第 \(\ell\) 次更新的时间。更新间隔 \(\{S^{(\ell+1)} - S^{(\ell)}\}_{\ell \geq 0}\) 是 i.i.d. 地服从参数为 \(n\) 的指数分布，即 \(\mathrm{Exp}(n)\)，因此链每单位时间预期执行 \(n\) 次更新。该过程在更新之间是分段常数；定义嵌入的离散时间链 \(X^{(\ell)} := Y^{(t)}\)，其中 \(t \in [S^{(\ell)}, S^{(\ell+1)})\)。在每个更新时刻 \(S^{(\ell)}\)，均匀随机地选择一个索引 \(I^{(\ell)} \in [n]\)。令 \(i = I^{(\ell)}\)。然后我们根据给定其他坐标的条件分布重新采样坐标 \(i\)：
\[
X_i^{(\ell)} \sim \mathcal{N}\left( -\sum_{j \in N(i)} \frac{\Theta_{ij}}{\Theta_{ii}} X_j^{(\ell-1)}, \frac{1}{\Theta_{ii}} \right),
\]
并对所有 \(j \neq i\) 令 \(X_j^{(\ell)} = X_j^{(\ell-1)}\)。这里 \(N(i) = \{ j \neq i : \Theta_{ij} \neq 0 \}\) 表示在 \(\Theta\) 的稀疏图中 \(i\) 的邻域。

现在准备呈现我们的主要结果。

###### 定理 1.3 (主定理（结构学习）)。
存在一个多项式时间算法，给定来自 \(n\) 个顶点上的 \((\alpha, d)\)-稀疏高斯图模型的 Glauber 轨迹，以至少 \(1 - \delta\) 的概率恢复稀疏模式（即 \(\mathrm{supp}(\Theta)\)），前提是轨迹长度满足
\[
T = \Omega\left( \frac{d^3 \log(n/\delta)}{\alpha^5} \right).
\]

需要说明几点。首先，该保证不假设混合时间，也不要求对 \(\Theta\) 施加除定义 1.1 中的稀疏性和边强度条件之外的任何额外正则性条件。其次，在定义 1.1 的连续时间动力学中，链每单位时间预期执行 \(n\) 次单点更新；因此，观测链到时间水平 \(T\) 对应平均约 \(n T\) 次单点更新。第三（关于最优性），先前已知 \(\Omega(\log(d)/\alpha^2)\) 的信息论下界（见 [TRD25 (https://arxiv.org/html/2606.31230#bib.bib31)] 的定理 2）。他们的陈述以 \(\beta_{\min} := \min_{(i,j) \in E} |\Theta_{ij}|/\Theta_{ii}\) 为参数，而我们使用对称归一化 \(\min_{(i,j) \in E} |\Theta_{ij}|/\sqrt{\Theta_{ii}\Theta_{jj}}\)。在 \(\Theta\) 的对角线为 1 的条件下，这些参数相等。在 第 7 节（定理 7.3）中，使用类似技术，我们展示了一个改进的信息论下界为 \(\Omega(n \log(n)/\alpha^2)\)。