How Many Samples Are Needed to Determine Causal Direction? Sharp Minimax Bounds for Bivariate LiNGAM¶

作者: Jikai Jin
主题: 因果推断
相关性: 9/10
链接: https://arxiv.org/abs/2608.15840

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向要解决的根本问题是：在双变量线性非高斯无环模型（LiNGAM）中，给定两个线性相关的变量，需要多少样本才能以高概率确定因果方向？ 经典 LiNGAM 理论（Shimizu et al., 2006）证明了在总体水平上，只要扰动是非高斯的，因果方向就是可识别的。但它没有量化当因果效应很弱（结构系数接近零）或扰动接近高斯分布时，识别难度如何急剧增加。本文的目标是建立有限样本下的极小极大最优样本复杂度律，将其表达为因果效应强度、非高斯性程度和误差方差不确定性的显式函数。

发展脉络（history）¶

奠基工作：总体可识别性与算法
- Shimizu et al. (2006)：引入 LiNGAM 模型，证明独立非高斯扰动可识别因果方向，并使用 ICA 进行估计。其有限样本讨论是算法和经验的，没有统一的误差界。
- Shimizu et al. (2011, DirectLiNGAM)：用顺序外生变量程序替代 ICA 搜索，但正确性证明明确针对无限样本情况。
- Hyvärinen & Smith (2013)：直接通过似然比和偏度/峰度近似研究双变量方向。这是最接近本文的经典公式，但其累积量准则不覆盖偏度和超额峰度都为零的源分布。
主要进展：识别性的稳定性与不可能性
- Sokol, Maathuis & Falkeborg (2014)：沿着一条特定的近高斯污染路径量化了 ICA 的可识别性，发现了局部 \(n^{-1/2}\) 污染边界，并指出其对线性因果模型的影响。他们的结果是渐近的，且明确将有限样本界列为开放方向。
- Genin & Mayo-Wilson (2024)：证明了在未分离的 LiNGAM 模型类上，均匀一致性是不可能的。他们的双变量构造将结构系数推向零，形式化了障碍。这解释了为什么一个正的分离参数（如非高斯性下界 \(\nu\) 和边缘系数下界 \(\beta\)）在逻辑上是不可或缺的。
当前 Frontier：有限样本分析与匹配下界
- Auddy & Yuan (2025)：获得了高维 ICA 的极小极大和计算复杂性结果。其模型类对每个源的超额峰度施加了固定的双侧界，目标是混合方向估计，而非因果方向。
- Oh, Han & Park (2025)：推导了高维 LiNGAM 结构恢复率，但依赖于一个神谕残差距离协方差间隙 \(\tau_1 > 0\)，其下界没有追踪源级非高斯性趋于零时的退化。
- Laplante, Ambroise & Humbert (2026)：证明了基于 Wasserstein 距离的总体识别和经验收敛，但其因果序误差界通过一个神谕目标间隙 \(\Gamma\) 表达，没有将 \(\Gamma\) 与弱边缘和近高斯参数联系起来。
- 本文 (Jin, 2026)：填补了上述空白，建立了以原始模型参数（边缘强度 \(\beta\)、源非高斯性 \(\nu\)、误差尺度不确定性 \(\rho\)）表达的匹配的上下界。

子线索聚类¶

基于非高斯性的方法：核心是利用独立非高斯扰动在错误方向下产生的依赖信号。代表工作：Shimizu et al. (2006, 2011), Hyvärinen & Smith (2013), Laplante et al. (2026)。本文属于此线索，但提供了第一个匹配的有限样本极小极大律。
基于误差方差限制的方法：在扰动为高斯时，通过假设误差方差相等（Peters & Bühlmann, 2014）或已知协方差结构（Loh & Bühlmann, 2014）来实现识别。本文的 \(d_\beta\) 项捕捉了这种协方差信息，并刻画了它与非高斯信号的过渡。
稳定性与不可能性分析：研究当模型接近不可识别边界时的行为。代表工作：Sokol et al. (2014), Genin & Mayo-Wilson (2024)。本文的定量旋转定理（Theorem 7.1）是这类稳定性分析的一个有限样本、非渐近版本。

这个方向在追问的核心问题¶

样本复杂度如何随因果效应强度（\(\beta\)）和接近高斯程度（\(\nu\)）变化？ 经典理论只回答“是否可识别”，不回答“需要多少数据”。
协方差信息何时能替代非高斯信息？ 当误差方差不等时，协方差矩阵本身可能不提供方向信息（\(d_\beta = 0\)）；当方差相等时，协方差始终提供信号（\(d_\beta = \beta^2\)）。两者如何平滑过渡？
能否得到匹配的上下界？ 即，是否存在一个决策规则达到最优的样本复杂度，且没有规则能做得更好？
当前主流方法与已知瓶颈：主流方法（如 DirectLiNGAM, 似然比）在有限样本下缺乏统一的误差界。瓶颈在于，当 \(\beta\) 或 \(\nu\) 很小时，任何方法的样本需求都会急剧增长，且均匀一致性是不可能的（Genin & Mayo-Wilson, 2024），因此必须引入正分离参数。

⚠️ 作者的 framing¶

作者的缺口 frame：作者将缺口定位为“缺乏一个以原始模型参数（\(\beta, \nu, \rho\)）表达的、匹配的有限样本极小极大律”。他们声称，所有现有工作要么是总体的、要么是渐近的、要么依赖于一个未量化的神谕间隙（如 \(\tau_1, \Gamma\)），而本文首次将其统一为原始参数的显式函数。
被淡化或回避的竞争路线：
- 基于似然比的方法（Hyvärinen & Smith, 2013）：作者指出其累积量准则不覆盖所有非高斯分布（如对称分布、四阶矩匹配高斯分布）。本文的 \(NG_w\) 度量覆盖了这些情况。
- 基于 Wasserstein 距离的方法（Laplante et al., 2026）：作者承认其提供了有限样本上界，但指出其下界不匹配，且上界依赖于一个未量化的神谕间隙 \(\Gamma\)。本文通过构造一个匹配的硬对（hard pair）来证明下界。
什么明显该被引 / 该存在、却没出现在 intro 里？ 未见明显缺失。intro 覆盖了从奠基到前沿的主要工作，并清晰地定位了本文的贡献。一个值得研究者去查的问题是：是否存在其他基于不同非高斯性度量（如最大均值差异 MMD）的有限样本分析，其表现如何？ 本文的 \(NG_w\) 度量是基于特征函数的，其他度量（如基于核的）可能产生不同的样本复杂度律。

张力¶

未见明显对立引用。各工作在不同设定（总体 vs. 有限样本，固定分离 vs. 退化边界）下得出的结论是互补的，而非矛盾的。Genin & Mayo-Wilson (2024) 的“不可能性”结果与本文的“正分离参数”设定是逻辑一致的。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：
- \(X, Y\)：可观测的两个随机变量。
- \(Z_1, Z_2\)：潜在（不可观测）的独立非高斯扰动，均值为0，方差为1。
- \(a\)：从 \(X\) 到 \(Y\) 的结构系数（因果效应）。
- \(\sigma_1, \sigma_2\)：正向模型中 \(Z_1, Z_2\) 的尺度参数（标准差）。
- \(\beta\)：结构系数绝对值的下界，即 \(|a| \ge \beta\)。
- \(\nu\)：标准化扰动 \(Z_j\) 与标准高斯分布距离的下界，即 \(NG_w(Z_j) \ge \nu\)。
- \(\sigma, \overline{\sigma}\)：扰动尺度的下界和上界，即 \(\sigma \le \sigma_1, \sigma_2 \le \overline{\sigma}\)。
- \(\rho = \sigma^2 / \overline{\sigma}^2\)：最小与最大扰动方差之比。
- \(d_\beta = [\beta^2 - (1-\rho)]_+\)：协方差信号，当 \(\beta^2 > 1-\rho\) 时为正，否则为0。
- \(N^\star_2(\beta, \nu, \delta)\)：以不超过 \(\delta\) 的错误概率确定方向所需的最小样本量。
模型：双变量线性非高斯无环模型（LiNGAM）。数据生成机制为：
\[X = \sigma_1 Z_1, \quad Y = a X + \sigma_2 Z_2\]
其中 \(Z_1 \perp\!\!\!\perp Z_2\)，且 \(Z_1, Z_2\) 服从均值为0、方差为1的非高斯分布。
可观测数据：研究者能观测到的是 \((X, Y)\) 的 \(n\) 个独立同分布样本。想要但观测不到的是潜在扰动 \(Z_1, Z_2\) 以及它们是否独立。方向识别的核心就是通过观测数据判断数据是由上述正向模型生成，还是由反向模型 \(Y = \tau_2 U_2, X = bY + \tau_1 U_1\) 生成。

第二步：讲最小内核¶

本文的核心数学问题可以归结为：当协方差类重叠（即 \(d_\beta = 0\)）时，方向识别完全依赖于非高斯信号 \(\beta\nu\)。那么，这个信号的下界是多少？

最简特例：考虑一个极端情况，其中扰动尺度已知且相等（\(\sigma = \overline{\sigma}\)），且结构系数 \(a\) 很小（\(\beta\) 很小）。此时，\(d_\beta = \beta^2\)，但为了聚焦非高斯信号，我们考虑 \(d_\beta\) 相对于 \(\beta\nu\) 可忽略的情况（例如 \(\nu \gg \beta\)）。更简洁地，我们直接看 \(d_\beta = 0\) 的情况，即 \(\beta^2 \le 1-\rho\)。

在这个特例下，核心命题退化为：在错误方向下，OLS 残差与回归变量之间的依赖信号（用 Sobolev 范数度量）至少是 \(\kappa \beta \nu\) 的量级。

为什么是这个特例？ 因为当协方差类重叠时，协方差矩阵本身不包含任何方向信息（Proposition 6.1）。此时，唯一的信息来源就是非高斯性。而错误方向下的 OLS 残差，本质上是对两个独立非高斯源 \(Z_1, Z_2\) 做了一个正交旋转（Proposition 8.1）。旋转的角度 \(\theta\) 与结构系数 \(a\) 成正比，即 \(|\sin\theta| \approx |a| \ge \beta\)。

核心思路：如果 \(Z_1, Z_2\) 是高斯分布，那么任何正交旋转后的两个分量仍然是独立的（旋转不变性），因此依赖信号为0。但如果 \(Z_1, Z_2\) 是非高斯的，旋转就会产生依赖。本文的 Theorem 7.1 证明，这个依赖信号（用 Sobolev 范数 \(\|D\|_{S^3}\) 度量）的下界是 \(a_* |\sin\theta \cos\theta| \nu\)，其中 \(\nu\) 是源的非高斯性度量。由于 \(|\sin\theta \cos\theta| \ge c_1 \beta\)，所以信号下界就是 \(\kappa \beta \nu\)。

一句话总结：本文在数学上干的事就是：证明了一个定量化的 Darmois-Skitovich 定理——当两个独立非高斯变量被一个很小的角度旋转后，它们之间的依赖信号不会消失，而是与旋转角度和源的非高斯性程度成正比。这个下界是均匀的，不依赖于源的具体分布形式（只要它满足子高斯性和非高斯性下界）。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在双变量 LiNGAM 模型中，以结构系数下界 \(\beta\)、源非高斯性下界 \(\nu\) 和扰动尺度不确定性 \(\rho\) 为参数，刻画了确定因果方向所需的极小极大最优样本复杂度 \(N^\star_2(\beta, \nu, \delta)\)。
核心工具 / 方法：使用局部渐近极小极大框架，结合 Le Cam 方法构造下界，并设计了一个结合协方差比较和基于 Sobolev 范数的独立性得分估计的两分支决策规则来达到上界。
主要结论：证明了 \(N^\star_2(\beta, \nu, \delta) \asymp \log(1/\delta) / (d_\beta^2 + \beta^2 \nu^2)\)，其中 \(d_\beta = [\beta^2 - (1-\rho)]_+\)。该律表明，识别难度由非高斯依赖信号（\(\beta^2 \nu^2\)）和协方差信号（\(d_\beta^2\)）共同决定，且当 \(\beta\) 或 \(\nu\) 很小时样本需求急剧增长。

关键设定与假设¶

在第二节最小记号的基础上，补全完整设定：

源类 \(Q(K, \nu)\)：所有均值为0、方差为1、Orlicz 范数 \(\|\cdot\|_{\psi_2} \le K\)（子高斯）且非高斯性度量 \(NG_w(Z) \ge \nu\) 的分布。\(NG_w(Z)\) 定义为特征函数与高斯特征函数之差的 \(L^2(w)\) 范数，其中 \(w(t) = \pi^{-1/2} e^{-t^2}\)。相比已有文献：这是一个非参数类，不假设密度、对称性或特定累积量非零。\(K > K_G = \sqrt{8/3}\) 确保类非空。
方向类 \(P^\to(\beta, \nu)\) 和 \(P^\leftarrow(\beta, \nu)\)：分别由正向和反向模型生成的所有联合分布。关键假设包括：结构系数绝对值有下界 \(\beta\)，扰动尺度在 \([\sigma, \overline{\sigma}]\) 内，且标准化扰动属于 \(Q(K, \nu)\)。
SUTVA / 可忽略性：不适用，因为这是双变量无混杂模型。
Restricted eigenvalue：不适用，因为这不是高维稀疏模型。
相比已有文献放宽或强化：
- 放宽：不要求源分布有密度、对称性或非零偏度/峰度。
- 强化：引入了非高斯性下界 \(\nu\) 和结构系数下界 \(\beta\)。这是必要的，因为 Genin & Mayo-Wilson (2024) 证明了没有这种正分离，均匀一致性是不可能的。

主要结果¶

定理 3.1（Sharp bivariate LiNGAM sample complexity）：存在常数 \(\beta_0, \nu_0, \delta_0 > 0\) 和 \(0 < c < C < \infty\)，使得对所有 \(0 < \beta \le \beta_0, 0 < \nu \le \nu_0, 0 < \delta \le \delta_0\)，有
\[c \frac{\log(1/\delta)}{d_\beta^2 + \beta^2 \nu^2} \le N^\star_2(\beta, \nu, \delta) \le C \frac{\log(1/\delta)}{d_\beta^2 + \beta^2 \nu^2}.\]
- 直觉：分母是总信号强度。当 \(d_\beta\) 和 \(\beta\nu\) 都很小时，信号很弱，需要大量样本。\(\log(1/\delta)\) 是置信度带来的对数代价。
- 必要条件：\(\beta, \nu\) 足够小（局部结果），\(\delta\) 足够小。
- 解决的技术难点：将定性识别（Darmois-Skitovich）转化为定量下界（Theorem 7.1），并证明该下界是紧的（通过构造硬对）。

证明路线与技术技巧¶

整体路线（5步）：

非空性与定性识别：证明源类非空，且两个方向类不相交（Proposition 5.2）。
协方差信号：精确计算协方差矩阵提供的方向信号 \(d_\beta\)，并给出一个基于样本二阶矩的简单检验，其错误概率以 \(\exp(-c n d_\beta^2)\) 衰减（Proposition 6.1）。
非高斯信号（核心）：证明错误方向下的 OLS 残差等价于对独立非高斯源的一个正交旋转。然后证明一个定量化的旋转不等式（Theorem 7.1）：该旋转产生的依赖信号（用 Sobolev 范数 \(\|D\|_{S^3}\) 度量）至少是 \(a_* |\sin\theta \cos\theta| \nu\)。由于 \(|\sin\theta \cos\theta| \ge c_1 \beta\)，得到总体得分间隙 \(\ge \kappa \beta \nu\)（Proposition 8.1）。
得分估计：设计一个基于样本分割和Hilbert空间中位数均值的估计器，以 \(n^{-1/2}\) 的速率一致地估计该 Sobolev 得分（Proposition 9.3）。结合步骤3的间隙，得到非高斯分支的上界 \(\exp(-c n \beta^2 \nu^2)\)。
匹配下界：构造一个正向和一个反向的“硬对”（hard pair），其平方 Hellinger 距离 \(\le C(d_\beta^2 + \beta^2 \nu^2)\)（Proposition 10.1）。通过 Le Cam 方法，证明任何决策规则的风险至少为 \(\frac{1}{4} \exp(-C n (d_\beta^2 + \beta^2 \nu^2))\)（Proposition 10.2）。

关键跳跃点：

Theorem 7.1 的证明：这是整个论文的技术核心。难点在于将定性 Darmois-Skitovich 定理定量化，且下界必须与旋转角度 \(|\sin\theta|\) 和源的非高斯性 \(\nu\) 的乘积成正比。
- 卡在哪：直接分析全缺陷 \(D_\theta\) 很困难，因为它是非线性的。
- 怎么绕过去：作者将缺陷分解为线性部分 \(D_{\text{lin},\theta}\) 和非线性余项 \(R_\theta\)。
  - 线性部分：通过 Hermite 多项式展开，证明其 \(S^3\) 范数下界为 \(a_0 |sc| \eta\)（Lemma 7.3）。关键在于标准化条件（\(h_j(0)=h_j'(0)=h_j''(0)=0\)）迫使低阶 Hermite 系数被高阶系数控制，而高阶系数在旋转下是均匀正定的。
  - 非线性余项：通过复杂的乘积估计和 Sobolev 插值，证明其 \(S^3\) 范数上界为 \(C |sc| \eta^{4/3}\)（Proposition 7.8）。
  - 结合：当 \(\eta\) 很小时，线性项占主导，得到下界。当 \(\eta\) 有正下界时，通过紧性论证和 Darmois-Skitovich 定理排除零解，得到另一个正下界。

技术技巧点名：

Gaussian conjugation (Lemma 7.2)：将带高斯权重的 Sobolev 范数 \(S^r\) 转化为不带权重的 Shubin 范数 \(Q^r\)，简化了后续的乘积和微分估计。
Hermite 多项式展开 (Lemma 7.3)：将特征函数在 Hermite 基下展开，将旋转操作对角化，从而精确计算线性部分的 Gram 矩阵。
Sobolev 插值 (Eq. 7.41)：用 \(L^2(w)\) 范数和 \(S^{12}\) 范数来界 \(S^4\) 范数，从而将非线性余项的高阶范数控制转化为低阶范数的幂次。
Hilbert 空间中位数均值 (Proposition 9.1)：一种鲁棒的均值估计方法，用于在 Hilbert 空间中估计特征函数的期望，其偏差以指数型尾概率被控制。
Le Cam 方法 (Proposition 10.2)：通过构造一个难以区分的“硬对”，将检验问题转化为计算两个分布之间的 Hellinger 距离，从而得到 minimax 下界。

真实例子与应用¶

本文为纯理论，无实证例子。所有结果都是数学定理和证明。

🔎 结论是否比证明窄¶

定理 3.1 是“局部”结果：它只在 \(\beta \le \beta_0, \nu \le \nu_0\) 时成立。作者明确说明常数依赖于固定的有界常数（如 \(K, \sigma, \overline{\sigma}\)），但没有给出 \(\beta_0, \nu_0\) 的显式表达式。因此，该定理没有声称对任意大的 \(\beta, \nu\) 都成立，尽管在远离边界时，问题会退化为更简单的形式（Remark 3.3）。
Theorem 7.1 的常数 \(a_*\) 不显式：证明中的紧性论证部分（\(\eta \ge \eta_{\text{loc}}\)）只保证了正下界的存在，没有给出其数值。因此，最终样本复杂度律中的常数 \(c, C\) 也是非显式的。
结论的泛化声明：作者在引言和结论中声称这是“迈向一般 LiNGAM 样本复杂度理论的第一步”。这个声明是合理的，但本文只严格证明了双变量情况。扩展到多变量需要处理更复杂的图结构和搜索空间，这被明确列为未来工作。

四、开放问题¶

扩展到多变量 LiNGAM：本文的双变量律是“局部”的。如何将其推广到一般的有向无环图（DAG）？样本复杂度是否由图中每条边的“局部”难度（由 \(\beta, \nu\) 决定）的某种组合决定？扎根点：论文引言最后一句：“This bivariate law is a first step toward expressing the sample complexity of general LiNGAM directly in terms of edge strengths, source non-Gaussianity, and error-scale uncertainty.”
处理隐变量：本文假设所有变量都被观测到。当存在未观测的混杂因子时，LiNGAM 的识别和样本复杂度会如何变化？扎根点：参考文献 [5] (Genin & Mayo-Wilson, 2024) 讨论了含隐变量的 LiNGAM，但本文未处理此设定。
计算约束下的样本复杂度：本文的决策规则（估计 Sobolev 得分）在计算上是可行的，但未讨论其计算复杂度。是否存在更高效的算法能达到相同的极小极大率？或者，是否存在计算-统计的权衡，即更快的算法需要更多的样本？扎根点：论文未讨论计算复杂度。这与研究者的“statistical-computational tradeoff”兴趣直接相关。
更紧的常数依赖：本文的常数 \(c, C\) 依赖于固定的有界常数（如 \(K, \sigma, \overline{\sigma}\)），但未给出显式形式。能否推导出这些常数的显式表达式，特别是它们如何依赖于子高斯范数上界 \(K\)？扎根点：Remark 3.3 明确承认了这一点：“the compactness part of Theorem 7.1 does not provide closed-form dependence on \(K\)”。

Maintained by 陈星宇 · Homepage · Source on GitHub