Learning linear structural equation models in polynomial time and sample complexity

Asish Ghoshal, Jean Honorio
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1466-1475, 2018.

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 Markov blanket size 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 $O(p(d + \log p))$ operations. In the finite sample setting, if the estimated precision matrix is sparse, our algorithm has a smoothed complexity of $\tilde{O}(p^3 + pd^{4})$, while if the estimated precision matrix is dense, our algorithm has a smoothed complexity of $\tilde{O}(p^5)$. For sub-Gaussian and bounded ($4m$-th, $m$ being positive integer) moment noise, our algorithm has a sample complexity of $\mathcal{O}(\frac{d^4}{\varepsilon^2} \log (\frac{p}{\sqrt{δ}}))$ and $\mathcal{O}(\frac{d^4}{\varepsilon^2} (\frac{p^2}{δ})^{\nicefrac{1}{m}})$ resp., to achieve $\varepsilon$ element-wise additive error with respect to the true autoregression matrix with probability at least $1 - δ$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-ghoshal18a, title = {Learning linear structural equation models in polynomial time and sample complexity}, author = {Ghoshal, Asish and Honorio, Jean}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1466--1475}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/ghoshal18a/ghoshal18a.pdf}, url = {https://proceedings.mlr.press/v84/ghoshal18a.html}, 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 Markov blanket size 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 $O(p(d + \log p))$ operations. In the finite sample setting, if the estimated precision matrix is sparse, our algorithm has a smoothed complexity of $\tilde{O}(p^3 + pd^{4})$, while if the estimated precision matrix is dense, our algorithm has a smoothed complexity of $\tilde{O}(p^5)$. For sub-Gaussian and bounded ($4m$-th, $m$ being positive integer) moment noise, our algorithm has a sample complexity of $\mathcal{O}(\frac{d^4}{\varepsilon^2} \log (\frac{p}{\sqrt{δ}}))$ and $\mathcal{O}(\frac{d^4}{\varepsilon^2} (\frac{p^2}{δ})^{\nicefrac{1}{m}})$ resp., to achieve $\varepsilon$ element-wise additive error with respect to the true autoregression matrix with probability at least $1 - δ$.} }
Endnote
%0 Conference Paper %T Learning linear structural equation models in polynomial time and sample complexity %A Asish Ghoshal %A Jean Honorio %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-ghoshal18a %I PMLR %P 1466--1475 %U https://proceedings.mlr.press/v84/ghoshal18a.html %V 84 %X 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 Markov blanket size 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 $O(p(d + \log p))$ operations. In the finite sample setting, if the estimated precision matrix is sparse, our algorithm has a smoothed complexity of $\tilde{O}(p^3 + pd^{4})$, while if the estimated precision matrix is dense, our algorithm has a smoothed complexity of $\tilde{O}(p^5)$. For sub-Gaussian and bounded ($4m$-th, $m$ being positive integer) moment noise, our algorithm has a sample complexity of $\mathcal{O}(\frac{d^4}{\varepsilon^2} \log (\frac{p}{\sqrt{δ}}))$ and $\mathcal{O}(\frac{d^4}{\varepsilon^2} (\frac{p^2}{δ})^{\nicefrac{1}{m}})$ resp., to achieve $\varepsilon$ element-wise additive error with respect to the true autoregression matrix with probability at least $1 - δ$.
APA
Ghoshal, A. & Honorio, J.. (2018). Learning linear structural equation models in polynomial time and sample complexity. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1466-1475 Available from https://proceedings.mlr.press/v84/ghoshal18a.html.

Related Material