Title: Learning linear structural equation models in polynomial time and sample complexity,
Abstract: 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})$.