Generalization Error Bounds on Deep Learning with Markov Datasets
This work addresses the theoretical understanding of deep learning performance with non-i.i.d. data, which is incremental as it extends existing i.i.d. bounds to Markov settings.
The paper tackles the problem of bounding generalization errors for deep neural networks trained on Markov datasets, deriving upper bounds that incorporate the spectral gap of the Markov chain's generator and extending these bounds to Bayesian counterparts and higher-order Markov models.
In this paper, we derive upper bounds on generalization errors for deep neural networks with Markov datasets. These bounds are developed based on Koltchinskii and Panchenko's approach for bounding the generalization error of combined classifiers with i.i.d. datasets. The development of new symmetrization inequalities in high-dimensional probability for Markov chains is a key element in our extension, where the spectral gap of the infinitesimal generator of the Markov chain plays a key parameter in these inequalities. We also propose a simple method to convert these bounds and other similar ones in traditional deep learning and machine learning to Bayesian counterparts for both i.i.d. and Markov datasets. Extensions to $m$-order homogeneous Markov chains such as AR and ARMA models and mixtures of several Markov data services are given.