# Learning linear structural equation models in polynomial time and sample complexity

arXiv: https://arxiv.org/abs/1707.04673 · HTML: https://mlsanity.com/paper/1707.04673/

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2017.

## Built on by (most cited first, 30 of 51)

- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery](https://mlsanity.com/paper/2112.02761/) (2021)
- [Diffusion Models for Causal Discovery via Topological Ordering](https://mlsanity.com/paper/2210.06201/) (2022)
- [A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models](https://mlsanity.com/paper/2303.18211/) (2023)
- [MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models](https://mlsanity.com/paper/2205.13869/) (2022)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Optimizing NOTEARS Objectives via Topological Swaps](https://mlsanity.com/paper/2305.17277/) (2023)
- [Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling](https://mlsanity.com/paper/2310.18123/) (2023)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [Ordering-Based Causal Discovery for Linear and Nonlinear Relations](https://mlsanity.com/paper/2410.05890/) (2024)
- [Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families](https://mlsanity.com/paper/2110.04719/) (2021)
- [Scalable Intervention Target Estimation in Linear Models](https://mlsanity.com/paper/2111.07512/) (2021)
- [Score matching through the roof: linear, nonlinear, and latent variables causal discovery](https://mlsanity.com/paper/2407.18755/) (2024)
- [Heteroscedastic Causal Structure Learning](https://mlsanity.com/paper/2307.07973/) (2023)
- [Markov Equivalence and Consistency in Differentiable Structure Learning](https://mlsanity.com/paper/2410.06163/) (2024)
- [Learning linear non-Gaussian directed acyclic graph with diverging number of nodes](https://mlsanity.com/paper/2111.00740/) (2021)
- [Learning Latent Structural Causal Models](https://mlsanity.com/paper/2210.13583/) (2022)
- [iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive Noise Models](https://mlsanity.com/paper/2306.17361/) (2023)
- [Order-based Structure Learning with Normalizing Flows](https://mlsanity.com/paper/2308.07480/) (2023)
- [Linear Causal Bandits: Unknown Graph and Soft Interventions](https://mlsanity.com/paper/2411.02383/) (2024)
- [Causal Representation Learning from General Environments under Nonparametric Mixing](https://mlsanity.com/paper/2604.23800/) (2026)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs](https://mlsanity.com/paper/2308.16859/) (2023)
- [Learning Directed Acyclic Graphs from Partial Orderings](https://mlsanity.com/paper/2403.16031/) (2024)
- [Causal Ordering for Structure Learning from Time Series](https://mlsanity.com/paper/2510.24639/) (2025)
- [Definite Non-Ancestral Relations and Structure Learning](https://mlsanity.com/paper/2105.10350/) (2021)

## Abstract (arXiv)

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 O(p(d2 + log p)) operations. In the finite sample setting, if the estimated precision matrix is sparse, our algorithm has a smoothed complexity of widetildeO(p3 + pd7), while if the estimated precision matrix is dense, our algorithm has a smoothed complexity of widetildeO(p5). For sub-Gaussian noise, we show that our algorithm has a sample complexity of O(fracd8varepsilon2 log (fracp√δ)) to achieve varepsilon element-wise additive error with respect to the true autoregression matrix with probability at most 1 - δ, while for noise with bounded (4m)-th moment, with m being a positive integer, our algorithm has a sample complexity of O(fracd8varepsilon2 (fracp2δ)1/m).