Optimal estimation of Gaussian DAG models
Optimal estimation of Gaussian DAG models
复制标题
DOI：
--
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Ming Gao;W. Tai;Bryon Aragam
中科院分区：
文献类型：
--
作者：
Ming Gao;W. Tai;Bryon Aragam
研究了从观测数据中学习高斯有向无环图（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.