Architecture-Aware Generalization Bounds for Temporal Networks: Theory and Fair Comparison Methodology

2025/08/08 by Gahtan, Barak, Bronstein, Alex M.
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2508.06066

Abstract

Deep temporal architectures such as TCNs achieve strong predictive performance on sequential data, yet theoretical understanding of their generalization remains limited. We address this gap through three contributions: introducing an evaluation methodology for temporal models, revealing surprising empirical phenomena about temporal dependence, and the first architecture-aware theoretical framework for dependent sequences. Fair-Comparison Methodology. We introduce evaluation protocols that fix effective sample size N_eff to isolate temporal structure effects from information content. Empirical Findings. Applying this method reveals that under N_eff = 2000, strongly dependent sequences (ρ= 0.8) exhibit approx' 76% smaller generalization gaps than weakly dependent ones (ρ= 0.2), challenging the conventional view that dependence universally impedes learning. However, observed convergence rates (N_eff^-1.21 to N_eff^-0.89) significantly exceed theoretical worst-case predictions (N^-0.5), revealing that temporal architectures exploit problem structure in ways current theory does not capture. Lastly, we develop the first architecture-aware generalization bounds for deep temporal models on exponentially β-mixing sequences. By embedding Golowich et al.'s i.i.d. class bound within a novel blocking scheme that partitions N samples into approx' B ≈ N/log N quasi-independent blocks, we establish polynomial sample complexity under convex Lipschitz losses. The framework achieves √(D) depth scaling alongside the product of layer-wise norms R = ∏_ℓ=1^D M^(ℓ), avoiding exponential dependence. While these bounds are conservative, they prove learnability and identify architectural scaling laws, providing worst-case baselines that highlight where future theory must improve.

Citations

• Generalization bounds for mixing processes via delayed online-to-PAC conversions
• Sequence Length Independent Norm-Based Generalization Bounds for Transformers
• Trained Transformers Learn Linear Models In-Context
• On Measuring Excess Capacity in Neural Networks
• Temporal Fusion Transformers for Interpretable Multi-horizon Time Series Forecasting
• Temporal Fusion Transformers for interpretable multi-horizon time series forecasting
• Generalization bounds for deep convolutional neural networks
• N-BEATS: Neural basis expansion analysis for interpretable time series forecasting
• An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling
• Size-Independent Sample Complexity of Neural Networks
• Spectrally-normalized margin bounds for neural networks
• Attention Is All You Need
• Temporal Convolutional Networks for Action Segmentation and Detection
• Train faster, generalize better: Stability of stochastic gradient descent
• Norm-Based Capacity Control in Neural Networks
• Stability Bound for Stationary Phi-mixing and Beta-mixing Processes
• Practical Markov Chain Monte Carlo

Related

• On the Generalization Capability of Temporal Graph Learning Algorithms: Theoretical Insights and a Simpler Method
• Forward and Inverse Approximation Theory for Linear Temporal Convolutional Networks
• Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximation
• Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers
• Temporal-Difference Networks