Gaussian DAG

新算法HOST提高了高斯有向无环图学习的效率

研究人员开发了HOST，一种用于学习高斯有向无环图（DAG）的新算法，解决了统计-计算差距问题。与需要计算成本高昂的子集搜索或样本复杂度较差的现有方法不同，HOST使用节点外评分和凸回归。该方法在多项式时间内实现了具有竞争力的图恢复，对于最大入度为d的p节点DAG，其样本复杂度为$d\log p$的量级。实验表明，HOST在运行时方面具有良好的可扩展性，同时保持了强大的图恢复性能。