Research map / Learning theory and algorithms / Sample complexity
Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies PAC learnability of threshold multilayer synchronous dynamical systems from configuration snapshots, giving an efficient consistent learner, a sample complexity bound O(σk log(σk)), and tight Natarajan dimension results (exactly σ for one layer, σk asymptotically for almost all graphs).
Problem
Learning unknown threshold interaction functions of networked dynamical systems over multilayer networks from snapshots of system dynamics, with PAC guarantees and complexity (Natarajan dimension) analysis.
Approach
A consistent learner sets each vertex's per-layer threshold from the maximum score among training configurations whose successor state is 0, yielding a sample bound independent of graph size or density; combined with a combinatorial characterization of shatterable sets (canonical sets) for single-layer systems and a probabilistic argument for multilayer graphs.
Key results
- For a single layer, the Natarajan dimension is exactly sigma (number of unknown-threshold vertices), improving the prior n/4 VC lower bound.
- The PAC learner with q = ceil((1/eps) sigma k log(sigma k/delta)) samples achieves error below eps w.p. at least 1-delta, independent of graph size and density.
- For almost all k-layer graphs (k>=2), as n grows, Ndim equals exactly sigma k, with failure probability at most 4(sigma k)^2 (3/4)^n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase training set size | PAC learner · Multi-Gnp | empirical loss | Helped |
| Increase the sample distribution's bias toward state 0 | PAC learner · Multi-Gnp | empirical loss | Hurt |
| Increase the number of unknown vertices σ while holding |T| = 500 fixed | PAC learner · Multi-Gnp | empirical loss | Hurt |
| Increase the number of vertices, with all thresholds unknown | PAC learner · Real-world multilayer networks | empirical loss | Hurt |
| Use a network with more layers | PAC learner · PPI vs Twitter | empirical loss | Hurt |
| Increase the number of layers from 2 to 6 while holding |T| at 500 | PAC learner · Gnp networks of size 500 and average degree 10 per layer | empirical loss | Hurt |
Limitations
- Lower bound on sample complexity is not tight (gap between Omega((sigma+log(1/delta))/eps) and the upper bound).
- Noise-free setting; labels are assumed correct.
- Asymptotic almost-all-graph result is only for large n; proportion close to 1 only empirically around n=1000.
Experimental setup
Datasets: Aarhus CKM-Phy Multi-Gnp PPI Twitter
Metrics: empirical loss (fraction of configurations with wrong succes
Baselines: Adiga et al. 2019 general sample complexity bound
Builds on: Adiga et al. 2019 threshold PAC learning PMAC learning
Closest papers by meaning
- Learning the Topology and Behavior of Discrete Dynamical Systems (AAAI 2024 · similarity 0.92)
- Learning the Causal Structure of Networked Dynamical Systems under Latent Nodes and Structured Noise (AAAI 2024 · similarity 0.86)
- PAC-Bayes Generalisation Bounds for Dynamical Systems including Stable RNNs (AAAI 2024 · similarity 0.84)
- On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.84)
- Learning system dynamics without forgetting (ICLR 2025 · similarity 0.84)
- Dynamical Decoupling of Generalization and Overfitting in Large Two-Layer Networks (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.