Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks

Zirou Qiu, Abhijin Adiga, Madhav Marathe, S. S. Ravi, Daniel Rosenkrantz, Richard Stearns, Anil Kumar Vullikanti
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:41557-41581, 2024.

Abstract

Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-qiu24a, title = {Efficient {PAC} Learnability of Dynamical Systems Over Multilayer Networks}, author = {Qiu, Zirou and Adiga, Abhijin and Marathe, Madhav and Ravi, S. S. and Rosenkrantz, Daniel and Stearns, Richard and Vullikanti, Anil Kumar}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {41557--41581}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/qiu24a/qiu24a.pdf}, url = {https://proceedings.mlr.press/v235/qiu24a.html}, abstract = {Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.} }
Endnote
%0 Conference Paper %T Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks %A Zirou Qiu %A Abhijin Adiga %A Madhav Marathe %A S. S. Ravi %A Daniel Rosenkrantz %A Richard Stearns %A Anil Kumar Vullikanti %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-qiu24a %I PMLR %P 41557--41581 %U https://proceedings.mlr.press/v235/qiu24a.html %V 235 %X Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.
APA
Qiu, Z., Adiga, A., Marathe, M., Ravi, S.S., Rosenkrantz, D., Stearns, R. & Vullikanti, A.K.. (2024). Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:41557-41581 Available from https://proceedings.mlr.press/v235/qiu24a.html.

Related Material