mlsanityData to 7 Oct 2026

Learning linear structural equation models in polynomial time and sample complexity

arXiv 1707.04673 ↗First posted 15 Jul 2017cs.LG stat.MLcited by 49

Not on the map. Why?

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).

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jul 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 8; 2023: 13; 2024: 9; 2025: 3; 2026: 7.

49 papers.

Sort:

By area:

  1. 2021Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Gamecited by 159
  2. 2022DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterizationcited by 135
  3. 2022Score matching enables causal discovery of nonlinear additive noise modelscited by 108
  4. 2021BCD Nets: Scalable Variational Approaches for Bayesian Causal Discoverycited by 68
  5. 2022Diffusion Models for Causal Discovery via Topological Orderingcited by 64
  6. 2023A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Modelscited by 28
  7. 2022MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Modelscited by 21
  8. 2023Optimizing NOTEARS Objectives via Topological Swapscited by 17
  9. 2023Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modelingcited by 15
  10. 2021Efficient Bayesian network structure learning via local Markov boundary searchcited by 14
  11. 2022Optimal estimation of Gaussian DAG modelscited by 14
  12. 2024Ordering-Based Causal Discovery for Linear and Nonlinear Relationscited by 11
37 more
  1. 2021Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential familiescited by 10
  2. 2021Scalable Intervention Target Estimation in Linear Modelscited by 10
  3. 2024Score matching through the roof: linear, nonlinear, and latent variables causal discoverycited by 8
  4. 2023Heteroscedastic Causal Structure Learningcited by 6
  5. 2024Markov Equivalence and Consistency in Differentiable Structure Learningcited by 6
  6. 2021Learning linear non-Gaussian directed acyclic graph with diverging number of nodescited by 5
  7. 2022Learning Latent Structural Causal Modelscited by 5
  8. 2023iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive Noise Modelscited by 5
  9. 2024Linear Causal Bandits: Unknown Graph and Soft Interventionscited by 5
  10. 2023Order-based Structure Learning with Normalizing Flowscited by 4
  11. 2024Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Modelscited by 4
  12. 2026Causal Representation Learning from General Environments under Nonparametric Mixingcited by 4
  13. 2024Optimal estimation of Gaussian (poly)treescited by 3
  14. 2024Learning Directed Acyclic Graphs from Partial Orderingscited by 2
  15. 2021Definite Non-Ancestral Relations and Structure Learningcited by 1
  16. 2021Learning Linear Polytree Structural Equation Modelscited by 1
  17. 2022Latent Variable Models for Bayesian Causal Discoverycited by 1
  18. 2022Learning Large Causal Structures from Inverse Covariance Matrix via Sparse Matrix Decompositioncited by 1
  19. 2023Hierarchical Topological Ordering with Conditional Independence Test for Limited Time Seriescited by 1
  20. 2023Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphscited by 1
  21. 2023Recovering Linear Causal Models with Latent Variables via Cholesky Factorization of Covariance Matrixcited by 1
  22. 2024LoSAM: Local Search in Additive Noise Models with Mixed Mechanisms and General Noise for Global Causal Discoverycited by 1
  23. 2025Identifiability of the minimum-trace directed acyclic graph and hill climbing algorithms without strict local optima under weakly increasing error variancescited by 1
  24. 2025Causal Ordering for Structure Learning from Time Seriescited by 1
  25. 2025Learning Gaussian DAG Models without Condition Number Boundscited by 1
  26. 2026Ordering-based Causal Discovery via Generalized Score Matchingcited by 1
  27. 2026Order-based Rehearsal Learningcited by 1
  28. 2021Identifiability of AMP chain graph modelscited by 0
  29. 2023Structural transfer learning of non-Gaussian DAGcited by 0
  30. 2023Distributionally Robust Skeleton Learning of Discrete Bayesian Networkscited by 0
  31. 2023Bayesian Approach to Linear Bayesian Networkscited by 0
  32. 2023Inconsistency of cross-validation for structure learning in Gaussian graphical modelscited by 0
  33. 2024Generalized Criterion for Identifiability of Additive Noise Models Using Majorizationcited by 0
  34. 2026Sparse Additive Model Pruning for Order-Based Causal Structure Learningcited by 0
  35. 2026Provable Guarantees and Efficient Learning of Structural Equation Models with Latent Confounderscited by 0
  36. 2026The Statistical Cost of Causal Discovery with Feedbackcited by 0
  37. 2026Discrete Score Matching Enables Causal Discovery from Count Datacited by 0