# Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 43 references that are in the map.
- First posted on arXiv 31 Aug 2023.

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

- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [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)
- [Regularized estimation in sparse high-dimensional time series models](https://mlsanity.com/paper/1311.4175/) (2013)
- [Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity](https://mlsanity.com/paper/1703.01196/) (2017)
- [Learning Quadratic Variance Function (QVF) DAG models via OverDispersion Scoring (ODS)](https://mlsanity.com/paper/1704.08783/) (2017)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [On the Sample Complexity of Learning Bayesian Networks](https://mlsanity.com/paper/1302.3579/) (2013)
- [Spectral Analysis of High-dimensional Time Series](https://mlsanity.com/paper/1810.11223/) (2018)
- [Information-theoretic limits of Bayesian network structure learning](https://mlsanity.com/paper/1601.07460/) (2016)
- [Physics Informed Topology Learning in Networks of Linear Dynamical Systems](https://mlsanity.com/paper/1809.10535/) (2018)
- [Bayesian Structure Learning for Stationary Time Series](https://mlsanity.com/paper/1505.03131/) (2015)
- [Topology Learning of Linear Dynamical Systems with Latent Nodes using Matrix Decomposition](https://mlsanity.com/paper/1912.07152/) (2019)
- [Efficient and passive learning of networked dynamical systems driven by non-white exogenous inputs](https://mlsanity.com/paper/2110.00852/) (2021)
- [Non-Asymptotic Pointwise and Worst-Case Bounds for Classical Spectrum Estimators](https://mlsanity.com/paper/2303.11908/) (2023)
- [Topology Learning of Radial Dynamical Systems with Latent Nodes](https://mlsanity.com/paper/1803.02793/) (2018)

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

- [Optimal structure learning and conditional independence testing](https://mlsanity.com/paper/2507.05689/) (2025)
- [Intervention-Based Time Series Causal Discovery via Simulator-Generated Interventional Distributions](https://mlsanity.com/paper/2605.09870/) (2026)

## Abstract (arXiv)

In this article, the optimal sample complexity of learning the underlying interactions or dependencies of a Linear Dynamical System (LDS) over a Directed Acyclic Graph (DAG) is studied. We call such a DAG underlying an LDS as dynamical DAG (DDAG). In particular, we consider a DDAG where the nodal dynamics are driven by unobserved exogenous noise sources that are wide-sense stationary (WSS) in time but are mutually uncorrelated, and have the same power spectral density (PSD). Inspired by the static DAG setting, a metric and an algorithm based on the PSD matrix of the observed time series are proposed to reconstruct the DDAG. It is shown that the optimal sample complexity (or length of state trajectory) needed to learn the DDAG is n=Theta(qlog(p/q)), where p is the number of nodes and q is the maximum number of parents per node. To prove the sample complexity upper bound, a concentration bound for the PSD estimation is derived, under two different sampling strategies. A matching min-max lower bound using generalized Fano's inequality also is provided, thus showing the order optimality of the proposed algorithm.