用留出评分替代子集搜索，HOST实现多项式时间d log p样本复杂度DAG学习！
Hold-Out Scoring for Efficient Gaussian DAG Learning
📖 AI 总结
该研究针对高维高斯有向无环图（DAG）学习中的统计—计算鸿沟提出新解法：具有尖锐样本复杂度的方法依赖计算昂贵的子集搜索且需预先给定入度上界，而多项式时间方法样本复杂度较差。作者提出HOST算法，用逐节点留出评分与凸回归替代子集搜索，且无需提供入度上界。其核心洞见是恢复正确排序并不需要排序分数估计误差一致地小，只需对这些误差进行单侧控制；留出样本评分在期望上会抬高排序分数，这一方向恰好有利于尚不应被选中的候选节点。确定排序后，HOST通过递归剔除两节点间总效应中的间接效应来恢复父节点。在适当条件下，该算法可在多项式时间内以d log p量级的样本复杂度精确恢复最大入度为d的p节点DAG。实验表明，HOST在图恢复效果上具有竞争力，且运行时间扩展性良好。
🔑 关键词速览
| 高斯 DAG 学习 (Gaussian DAG Learning) | 从服从高斯分布的数据中学习有向无环图结构，即推断变量之间的因果关系。 |
| 留出评分 (Hold-Out Scoring) | 将数据分为训练集和留出集，用留出集评估模型分数，以避免过拟合并控制估计误差。 |
| 样本复杂度 (Sample Complexity) | 学习算法达到给定精度所需的最小样本数量，通常表示为节点数 p 和入度 d 的函数。 |
| 入度上界 (Indegree Bound) | 每个节点允许的最大父节点数量，许多 DAG 学习算法需要预先知道该上界。 |
| 凸回归 (Convex Regression) | 一类通过凸优化求解的回归方法，如 Lasso，用于高效估计变量间的线性关系。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅