HOST算法：高效学习高斯DAG的新范式

高斯DAG学习中的统计-计算鸿沟

有向无环图（DAG）是描述变量间因果与依赖结构的核心工具，在因果推断、基因调控网络、经济建模等领域应用广泛。然而在高维场景下，高斯DAG的结构学习始终面临一个棘手的两难问题——学界称之为"统计-计算鸿沟"（statistical-computational gap）。

一方面，那些具有尖锐（sharp）样本复杂度的方法，往往依赖于计算代价高昂的子集搜索（subset search），并且需要事先给定一个入度上界（indegree bound）作为先验信息。另一方面，能够在多项式时间内运行的算法，其样本复杂度表现又相对逊色。换句话说，想要"又快又准"，在过去是难以兼得的。

这篇发表于 arXiv 的研究（arXiv:2610.02785v1）提出了名为 HOST 的新算法，试图从根本上弥合这一鸿沟。

Hold-Out Scoring for Efficient Gaussian DAG Learning

HOST 的核心思路：留出评分与凸回归

HOST（Hold-Out Scoring）的名字直接点明了它的技术路线。它用逐节点的留出评分（nodewise hold-out scoring）配合凸回归（convex regression），取代了传统方法中昂贵的子集搜索，并且无需外部提供入度上界。这意味着算法摆脱了对先验结构信息的强依赖，适用范围更广。

关键洞察：排序只需单边误差控制

论文最具启发性的地方在于一个反直觉的观察：要恢复出正确的变量排序（ordering），并不需要排序分数的估计误差处处都很小，而只需要对这些误差进行"单边控制"（one-sided control）。

这是一个精巧的统计学思想。传统上我们倾向于追求估计量的一致小误差，但在排序这一特定任务里，真正重要的是误差的"方向"是否有利，而非其绝对大小。HOST 正是利用了这一点，把问题简化到了可以在多项式时间内求解的程度。

留出样本带来的"有利偏差"

具体而言，在排序阶段，HOST 利用了一个事实：使用留出样本进行分数估计时，排序分数在期望意义上会被"抬高"（inflated in expectation）。而这种抬高恰好发生在"尚不应被选入"的候选节点上——也就是说，偏差的方向是有利的。

这种设计让算法能够以较高的可靠性区分哪些节点应该先被排序、哪些应当暂缓，从而在没有子集搜索的情况下也能逼近正确排序。

从排序到父节点恢复

确定排序之后，HOST 进入第二阶段：恢复每个节点的父节点集合。这里采用的策略是递归地从两节点间的总效应（total effects）中剥离间接效应（indirect effects），最终留下的即为直接的父子依赖关系。

这一步骤与因果推断中区分直接效应与间接效应的经典思想一脉相承。通过递归剥离，HOST 能够在已知排序的前提下精确还原图结构，而不必枚举所有可能的父节点组合。

理论保证与实验表现

论文给出了明确的理论结果：在适当条件下，HOST 能够以 $d\log p$ 量级的样本复杂度，在多项式时间内精确恢复一个含 $p$ 个节点、最大入度为 $d$ 的 DAG。

这里的 $d\log p$ 样本复杂度正是过去那些依赖子集搜索的"尖锐"方法所具备的优势量级——而 HOST 在不牺牲多项式运行时间的前提下达到了这一水平，这正是其弥合统计-计算鸿沟的关键证据。

实验方面，论文报告 HOST 在图恢复质量上与现有方法具有竞争力，同时在运行时间的扩展性（runtime scaling）上表现更优。这意味着随着问题规模增大，HOST 的计算优势会愈发明显。

意义与展望

HOST 的价值不仅在于一个更快的算法，更在于它提供了一种新的问题视角：在结构学习任务中，精心设计的、方向可控的估计偏差，有时比追求无偏或一致小误差更有用。

对于需要在大规模高维数据上进行因果结构发现的研究者和工程师而言，HOST 提供了一个无需先验入度假设、兼具理论保证与计算效率的可行选择。当然，论文中的保证建立在"适当条件"之上，这些条件在真实数据中的满足程度，以及算法对高斯假设偏离时的鲁棒性，仍是值得进一步探索的方向。