# Learning Gaussian DAG Models without Condition Number Bounds

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 51 references that are in the map.
- First posted on arXiv 8 Nov 2025.

## Builds on (most cited first, 19 of 19)

- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal-learn: Causal Discovery in Python](https://mlsanity.com/paper/2307.16405/) (2023)
- [Learning Equivalence Classes of Bayesian Networks Structures](https://mlsanity.com/paper/1302.3566/) (2013)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [A polynomial-time algorithm for learning nonparametric causal graphs](https://mlsanity.com/paper/2006.11970/) (2020)
- [Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity](https://mlsanity.com/paper/1703.01196/) (2017)
- [Optimal structure and parameter learning of Ising models](https://mlsanity.com/paper/1612.05024/) (2016)
- [Efficient Learning of Discrete Graphical Models](https://mlsanity.com/paper/1902.00600/) (2019)
- [Learning Some Popular Gaussian Graphical Models without Condition Number Bounds](https://mlsanity.com/paper/1905.01282/) (2019)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models](https://mlsanity.com/paper/1810.11905/) (2018)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [Information-theoretic limits of Bayesian network structure learning](https://mlsanity.com/paper/1601.07460/) (2016)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)

## Built on by (most cited first, 3 of 3)

- [BUILD with Precision: Bottom-Up Inference of Linear DAGs](https://mlsanity.com/paper/2512.16111/) (2025)
- [Hold-Out Scoring for Efficient Gaussian DAG Learning](https://mlsanity.com/paper/2610.02785/) (2026)
- [Learning Non-Gaussian SEMs with Conditional Risk, and Why the Direction of Recursion Matters](https://mlsanity.com/paper/2610.14246/) (2026)

## Abstract (arXiv)

We study the problem of learning the topology of a directed Gaussian Graphical Model under the equal-variance assumption, where the graph has n nodes and maximum in-degree d. Prior work has established that O(d log n) samples are sufficient for this task. However, an important factor that is often overlooked in these analyses is the dependence on the condition number of the covariance matrix of the model. Indeed, all algorithms from prior work require a number of samples that grows polynomially with this condition number. In many cases this is unsatisfactory, since the condition number could grow polynomially with n, rendering these prior approaches impractical in high-dimensional settings. In this work, we provide an algorithm that recovers the underlying graph and prove that the number of samples required is independent of the condition number. Furthermore, we establish lower bounds that nearly match the upper bound up to a d-factor, thus providing an almost tight characterization of the true sample complexity of the problem. Moreover, under a further assumption that all the variances of the variables are bounded, we design a polynomial-time algorithm that recovers the underlying graph, at the cost of an additional polynomial dependence of the sample complexity on d. We complement our theoretical findings with simulations on synthetic datasets that confirm our predictions.