Research map / Learning theory and algorithms / Sample complexity
Learning Gaussian DAG Models without Condition Number Bounds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a condition-number-free algorithm for recovering equal-variance linear Gaussian DAG topology with O(max(b_min^-4, tau b_min^-2) d log(n/d)) samples, a near-matching lower bound, and a polynomial-time Lasso-based variant under bounded variances.
Problem
Learning the topology of a directed linear Gaussian DAG (equal-variance SEM) with bounded in-degree d; prior sample complexity bounds scale polynomially with the covariance condition number, which can grow with n.
Approach
Estimate conditional variances via regression MSE (avoiding covariance inversion), so sample complexity depends on a graph quantity tau(G) ≤ condition number rather than κ; find parents via coefficient-based distinguishing test as in undirected GGM work; add a Lasso-based polynomial-time variant under bounded variance.
Key results
- Upper bound O(max(b_min^-4, tau b_min^-2) d log(n/d)) samples, independent of condition number, with lower bound Omega(max(b_min^-4, tau b_min^-2) log n), matching up to a factor d.
- Polynomial-time Lasso-based algorithm with sample complexity O(R^2 d^4 tau^3 b_min^-4 log(n/delta)) under bounded variance assumption.
- Simulations show the proposed methods converge to the truth while the prior condition-number-dependent algorithm fails to converge for larger n and more samples; the proposed methods are less accurate with few samples (~400 or fewer).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the information-theoretic recovery algorithm instead of the prior algorithm | Synthetic DAGs · Synthetic DAGs, n=10,15,20,25; d=4 | accuracy | Mixed |
| Use the efficient recovery algorithm instead of the prior algorithm | Synthetic DAGs · Synthetic DAGs, n=10,15,20,25; d=4 | accuracy | Mixed |
| Use either proposed algorithm instead of the prior algorithm | Synthetic DAGs · Synthetic DAGs with more than 600 samples | false positive edges | Helped |
| Use the proposed algorithms instead of the PC algorithm | Synthetic DAGs · Synthetic DAGs, including small n,d | performance | Helped |
Surprising findings
- The prior condition-number-dependent algorithm is more accurate for small sample sizes (up to about 400) but fails to converge as condition number grows.
Limitations
- Information-theoretic algorithm has runtime O(n^{2d+2}), impractical for moderate d.
- Lower bound matches upper bound only up to a factor of d.
- Polynomial-time algorithm requires an additional bounded-variance assumption and has worse dependence on d (d^4 tau^3).
Experimental setup
Datasets: synthetic random DAGs with linear Gaussian SEM
Benchmarks: synthetic Gaussian DAGs
Metrics: recovery accuracy false positive edges condition number, tau and max variance growth
Baselines: Ghoshal and Honorio (condition-number-dependent DAG algorithm) PC algorithm
Builds on: equal variances identifiability (Peters and Bühlmann) Gaussian graphical model neighborhood selection (undirected GGM sparse recovery) Fano's inequality
Closest papers by meaning
- Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity (NeurIPS 2017 · similarity 0.89)
- Deep Gaussian Processes on Directed Acyclic Graphs (NeurIPS 2026 · similarity 0.87)
- Analytic DAG Constraints for Differentiable DAG Learning (ICLR 2025 · similarity 0.85)
- Markov Equivalence and Consistency in Differentiable Structure Learning (NeurIPS 2024 · similarity 0.85)
- Parameter Estimation in DAGs from Incomplete Data via Optimal Transport (ICML 2024 · similarity 0.85)
- ProDAG: Projected Variational Inference for Directed Acyclic Graphs (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.