mlsanityData to 7 Oct 2026

Optimal estimation of Gaussian DAG models

arXiv 2201.10548 ↗First posted 25 Jan 2022math.ST cs.AI cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We study the optimal sample complexity of learning a Gaussian directed acyclic graph (DAG) from observational data. Our main results establish the minimax optimal sample complexity for learning the structure of a linear Gaussian DAG model in two settings of interest: 1) Under equal variances without knowledge of the true ordering, and 2) For general linear models given knowledge of the ordering. In both cases the sample complexity is nasymp qlog(d/q), where q is the maximum number of parents and d is the number of nodes. We further make comparisons with the classical problem of learning (undirected) Gaussian graphical models, showing that under the equal variance assumption, these two problems share the same optimal sample complexity. In other words, at least for Gaussian models with equal error variances, learning a directed graphical model is statistically no more difficult than learning an undirected graphical model. Our results also extend to more general identification assumptions as well as subgaussian errors.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 20 of its 50 references that are in the map. First posted on arXiv 25 Jan 2022.

Builds on

20 of 50 references.

References · 20

  1. 2013Causal Discovery with Continuous Additive Noise Modelscited by 252
  2. 2013CAM: Causal additive models, high-dimensional order search and penalized regressioncited by 175
  3. 2013High-dimensional learning of linear causal networks via inverse covariance estimationcited by 86
  4. 2018On Causal Discovery with Equal Variance Assumptioncited by 55
  5. 2017Learning linear structural equation models in polynomial time and sample complexitycited by 49
  6. 2015High-dimensional consistency in score-based and hybrid structure learningcited by 44
  7. 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
  8. 2020A polynomial-time algorithm for learning nonparametric causal graphscited by 29
  9. 2017Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexitycited by 27
  10. 2014Support recovery without incoherence: A case for nonconvex regularizationcited by 25
  11. 2018High-Dimensional Causal Discovery Under non-Gaussianitycited by 24
  12. 2017Learning Quadratic Variance Function (QVF) DAG models via OverDispersion Scoring (ODS)cited by 18
8 more
  1. 2021Efficient Bayesian network structure learning via local Markov boundary searchcited by 14
  2. 2015Learning Directed Acyclic Graphs with Penalized Neighbourhood Regressioncited by 12
  3. 2018High-Dimensional Poisson DAG Model Learning Using ℓ1-Regularized Regressioncited by 10
  4. 2021Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential familiescited by 10
  5. 2013On the Sample Complexity of Learning Bayesian Networkscited by 9
  6. 2013Score-based Causal Learning in Additive Noise Modelscited by 8
  7. 2013Maximum Likelihood Bounded Tree-Width Markov Networkscited by 7
  8. 2016Information-theoretic limits of Bayesian network structure learningcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 2; 2025: 4; 2026: 3.

14 papers.

Sort:

  1. 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
  2. 2023Learning bounded-degree polytrees with known skeletoncited by 5
  3. 2025BUILD with Precision: Bottom-Up Inference of Linear DAGscited by 4
  4. 2024Optimal estimation of Gaussian (poly)treescited by 3
  5. 2026Exploiting Non-Negativity in DAG Structure Learningcited by 3
  6. 2024Probably approximately correct high-dimensional causal effect estimation given a valid adjustment setcited by 2
  7. 2022Learning Large Causal Structures from Inverse Covariance Matrix via Sparse Matrix Decompositioncited by 1
  8. 2023Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphscited by 1
  9. 2025Learning Gaussian DAG Models without Condition Number Boundscited by 1
  10. 2023Bayesian Approach to Linear Bayesian Networkscited by 0
  11. 2025Optimal structure learning and conditional independence testingcited by 0
  12. 2025Differentiable Structure Learning and Causal Discovery for General Binary Datacited by 0
2 more
  1. 2026On the Identifiability of Mixed Ordinal and Exponential Family Causal DAGs under Linear Parametric Modelscited by 0
  2. 2026The Statistical Cost of Causal Discovery with Feedbackcited by 0