Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs

Mishfad Shaikh Veedu, Deepjyoti Deka, Murti Salapaka
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:4636-4644, 2024.

Abstract

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(q\log(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. The codes used in the paper are available at \url{https://github.com/Mishfad/Learning-Dynamical-DAGs}

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-shaikh-veedu24a, title = {Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs}, author = {Shaikh Veedu, Mishfad and Deka, Deepjyoti and Salapaka, Murti}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {4636--4644}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/shaikh-veedu24a/shaikh-veedu24a.pdf}, url = {https://proceedings.mlr.press/v238/shaikh-veedu24a.html}, abstract = {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(q\log(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. The codes used in the paper are available at \url{https://github.com/Mishfad/Learning-Dynamical-DAGs}} }
Endnote
%0 Conference Paper %T Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs %A Mishfad Shaikh Veedu %A Deepjyoti Deka %A Murti Salapaka %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-shaikh-veedu24a %I PMLR %P 4636--4644 %U https://proceedings.mlr.press/v238/shaikh-veedu24a.html %V 238 %X 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(q\log(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. The codes used in the paper are available at \url{https://github.com/Mishfad/Learning-Dynamical-DAGs}
APA
Shaikh Veedu, M., Deka, D. & Salapaka, M.. (2024). Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:4636-4644 Available from https://proceedings.mlr.press/v238/shaikh-veedu24a.html.

Related Material