论文标题
高斯DAG模型的最佳估计
Optimal estimation of Gaussian DAG models
论文作者
论文摘要
我们研究了从观测数据中学习高斯定向无环图（DAG）的最佳样品复杂性。我们的主要结果建立了最小值最佳样本复杂性，用于在两个感兴趣的设置中学习线性高斯DAG模型的结构：1）在相等的方差下，而没有真实排序的情况下，以及2）对于有订单知识的一般线性模型。在这两种情况下，样本复杂性都是$ n \ asymp q \ log（d/q）$，其中$ q $是父母的最大数量，$ d $是节点的数量。我们进一步与经典的学习问题（无向）高斯图形模型进行了比较，表明在相等的方差假设下，这两个问题具有相同的最佳样本复杂性。换句话说，至少对于具有相同误差差异的高斯模型，学习有向图形模型在统计学上比学习无方向的图形模型更困难。我们的结果还扩展到了更一般的识别假设以及亚高斯错误。
We study the optimal sample complexity of learning a Gaussian directed acyclic graph (DAG) from observational data. Our main results establish the minimax optimal sample complexity for learning the structure of a linear Gaussian DAG model in two settings of interest: 1) Under equal variances without knowledge of the true ordering, and 2) For general linear models given knowledge of the ordering. In both cases the sample complexity is $n\asymp q\log(d/q)$, where $q$ is the maximum number of parents and $d$ is the number of nodes. We further make comparisons with the classical problem of learning (undirected) Gaussian graphical models, showing that under the equal variance assumption, these two problems share the same optimal sample complexity. In other words, at least for Gaussian models with equal error variances, learning a directed graphical model is statistically no more difficult than learning an undirected graphical model. Our results also extend to more general identification assumptions as well as subgaussian errors.
