Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs
Not on the map. Why?
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.
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
17 of 43 references.
References · 17
- 2018Learning Without Mixing: Towards A Sharp Analysis of Linear System Identificationcited by 158
- 2017Finite Time Identification in Unstable Linear Systemscited by 66
- 2018On Causal Discovery with Equal Variance Assumptioncited by 59
- 2017Learning linear structural equation models in polynomial time and sample complexitycited by 51
- 2013Regularized estimation in sparse high-dimensional time series modelscited by 41
- 2017Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexitycited by 27
- 2017Learning Quadratic Variance Function (QVF) DAG models via OverDispersion Scoring (ODS)cited by 18
- 2022Optimal estimation of Gaussian DAG modelscited by 17
- 2013On the Sample Complexity of Learning Bayesian Networkscited by 9
- 2018Spectral Analysis of High-dimensional Time Seriescited by 8
- 2016Information-theoretic limits of Bayesian network structure learningcited by 7
- 2018Physics Informed Topology Learning in Networks of Linear Dynamical Systemscited by 7
5 more
- 2015Bayesian Structure Learning for Stationary Time Seriescited by 6
- 2019Topology Learning of Linear Dynamical Systems with Latent Nodes using Matrix Decompositioncited by 4
- 2021Efficient and passive learning of networked dynamical systems driven by non-white exogenous inputscited by 4
- 2023Non-Asymptotic Pointwise and Worst-Case Bounds for Classical Spectrum Estimatorscited by 4
- 2018Topology Learning of Radial Dynamical Systems with Latent Nodescited by 2
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.