用于高效高斯DAG学习的留出评分

arXiv:2610.02785v1 公告类型：cross 摘要：高维高斯DAG学习面临统计与计算之间的鸿沟：具有精确样本复杂度的方法依赖计算开销高昂的子集搜索以及给定的入度上界，而多项式时间的替代方法则具有较差的样本复杂度。我们提出HOST，这是一种高效的DAG学习算法，以逐节点留出评分和凸回归取代子集搜索，且不要求给定入度上界。我们的关键洞见是，恢复正确的排序并不要求排序评分中的估计误差均匀地足够小，而只需要对这些误差进行单侧控制。在排序步骤中，HOST利用了这样一个事实：使用留出样本进行评分估计会在期望意义上抬高排序评分，而对于那些尚不应被选中的候选者而言，这正是有利的方向。在给定排序的情况下，HOST通过递归地消除两个节点之间总效应中的间接效应来恢复父节点。在适当条件下，HOST能够以多项式时间和数量级为$d\log p$的样本复杂度，准确恢复一个具有$p$个节点且最大入度为$d$的DAG。实验表明，HOST能够实现具有竞争力的图恢复效果，同时展现出良好的运行时间扩展性。