The problem of learning structural equation models (SEMs) from data is a
fundamental problem in causal inference. We develop a new algorithm --- which
is computationally and statistically efficient and works in the
high-dimensional regime --- for learning linear SEMs from purely observational
data with arbitrary noise distribution. We consider three aspects of the
problem: identifiability, computational efficiency, and statistical efficiency.
We show that when data is generated from a linear SEM over $p$ nodes and
maximum degree $d$, our algorithm recovers the directed acyclic graph (DAG)
structure of the SEM under an identifiability condition that is more general
than those considered in the literature, and without faithfulness assumptions.
In the population setting, our algorithm recovers the DAG structure in
$\mathcal{O}(p(d^2 + \log p))$ operations. In the finite sample setting, if the
estimated precision matrix is sparse, our algorithm has a smoothed complexity
of $\widetilde{\mathcal{O}}(p^3 + pd^7)$, while if the estimated precision
matrix is dense, our algorithm has a smoothed complexity of
$\widetilde{\mathcal{O}}(p^5)$. For sub-Gaussian noise, we show that our
algorithm has a sample complexity of $\mathcal{O}(\frac{d^8}{\varepsilon^2}
\log (\frac{p}{\sqrt{\delta}}))$ to achieve $\varepsilon$ element-wise additive
error with respect to the true autoregression matrix with probability at most
$1 - \delta$, while for noise with bounded $(4m)$-th moment, with $m$ being a
positive integer, our algorithm has a sample complexity of
$\mathcal{O}(\frac{d^8}{\varepsilon^2} (\frac{p^2}{\delta})^{1/m})$.

本文研究了从观察数据中学习线性结构方程模型（SEMs）的算法问题，旨在实现计算和统计效率，解决较一般的识别问题并没有考虑 “信仰” 假设的情形，提供了一个高效的算法，能够在不同噪声分布的情况下恢复 SEM 的有向无环图结构。