Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks

• URL: http://arxiv.org/abs/2405.06884v2
• Date: Sun, 28 Jul 2024 18:22:17 GMT
• Title: Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks
• Authors: Zirou Qiu, Abhijin Adiga, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns, Anil Vullikanti,
• Abstract summary: We study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. 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.
• Score: 30.424671907681688
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Learning System Dynamics without Forgetting [60.08612207170659]
  Predicting trajectories of systems with unknown dynamics is crucial in various research fields, including physics and biology. We present a novel framework of Mode-switching Graph ODE (MS-GODE), which can continually learn varying dynamics. We construct a novel benchmark of biological dynamic systems, featuring diverse systems with disparate dynamics.
  arXiv  Detail & Related papers  (2024-06-30T14:55:18Z)
• Towards Scalable and Versatile Weight Space Learning [51.78426981947659]
  This paper introduces the SANE approach to weight-space learning. Our method extends the idea of hyper-representations towards sequential processing of subsets of neural network weights.
  arXiv  Detail & Related papers  (2024-06-14T13:12:07Z)
• Mechanistic Neural Networks for Scientific Machine Learning [58.99592521721158]
  We present Mechanistic Neural Networks, a neural network design for machine learning applications in the sciences. It incorporates a new Mechanistic Block in standard architectures to explicitly learn governing differential equations as representations. Central to our approach is a novel Relaxed Linear Programming solver (NeuRLP) inspired by a technique that reduces solving linear ODEs to solving linear programs.
  arXiv  Detail & Related papers  (2024-02-20T15:23:24Z)
• Learning the Topology and Behavior of Discrete Dynamical Systems [30.424671907681688]
  We focus on the problem of learning the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. Our results provide a theoretical foundation for learning both the behavior and topology of discrete dynamical systems.
  arXiv  Detail & Related papers  (2024-02-18T19:31:26Z)
• On the effectiveness of neural priors in modeling dynamical systems [28.69155113611877]
  We discuss the architectural regularization that neural networks offer when learning such systems. We show that simple coordinate networks with few layers can be used to solve multiple problems in modelling dynamical systems.
  arXiv  Detail & Related papers  (2023-03-10T06:21:24Z)
• Knowledge-based Deep Learning for Modeling Chaotic Systems [7.075125892721573]
  This paper considers extreme events and their dynamics and proposes models based on deep neural networks, called knowledge-based deep learning (KDL) Our proposed KDL can learn the complex patterns governing chaotic systems by jointly training on real and simulated data. We validate our model by assessing it on three real-world benchmark datasets: El Nino sea surface temperature, San Juan Dengue viral infection, and Bjornoya daily precipitation.
  arXiv  Detail & Related papers  (2022-09-09T11:46:25Z)
• Constructing Neural Network-Based Models for Simulating Dynamical Systems [59.0861954179401]
  Data-driven modeling is an alternative paradigm that seeks to learn an approximation of the dynamics of a system using observations of the true system. This paper provides a survey of the different ways to construct models of dynamical systems using neural networks. In addition to the basic overview, we review the related literature and outline the most significant challenges from numerical simulations that this modeling paradigm must overcome.
  arXiv  Detail & Related papers  (2021-11-02T10:51:42Z)
• Learning Contact Dynamics using Physically Structured Neural Networks [81.73947303886753]
  We use connections between deep neural networks and differential equations to design a family of deep network architectures for representing contact dynamics between objects. We show that these networks can learn discontinuous contact events in a data-efficient manner from noisy observations. Our results indicate that an idealised form of touch feedback is a key component of making this learning problem tractable.
  arXiv  Detail & Related papers  (2021-02-22T17:33:51Z)
• Physical deep learning based on optimal control of dynamical systems [0.0]
  In this study, we perform pattern recognition based on the optimal control of continuous-time dynamical systems. As a key example, we apply the dynamics-based recognition approach to an optoelectronic delay system. This is in contrast to conventional multilayer neural networks, which require a large number of weight parameters to be trained.
  arXiv  Detail & Related papers  (2020-12-16T06:38:01Z)
• Deep learning of contagion dynamics on complex networks [0.0]
  We propose a complementary approach based on deep learning to build effective models of contagion dynamics on networks. By allowing simulations on arbitrary network structures, our approach makes it possible to explore the properties of the learned dynamics beyond the training data. Our results demonstrate how deep learning offers a new and complementary perspective to build effective models of contagion dynamics on networks.
  arXiv  Detail & Related papers  (2020-06-09T17:18:34Z)
• Learning Stable Deep Dynamics Models [91.90131512825504]
  We propose an approach for learning dynamical systems that are guaranteed to be stable over the entire state space. We show that such learning systems are able to model simple dynamical systems and can be combined with additional deep generative models to learn complex dynamics.
  arXiv  Detail & Related papers  (2020-01-17T00:04:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.