# Generalization Error Bounds on Deep Learning with Markov Datasets

arXiv: https://arxiv.org/abs/2201.11059 · HTML: https://mlsanity.com/paper/2201.11059/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 23 Dec 2021.

## Builds on (most cited first, 11 of 11)

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Bayesian Deep Learning and a Probabilistic Perspective of Generalization](https://mlsanity.com/paper/2002.08791/) (2020)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Generalization Error in Deep Learning](https://mlsanity.com/paper/1808.01174/) (2018)
- [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation](https://mlsanity.com/paper/1909.04299/) (2019)
- [Wide stochastic networks: Gaussian limit and PAC-Bayesian training](https://mlsanity.com/paper/2106.09798/) (2021)
- [Computationally Efficient Estimation of the Spectral Gap of a Markov Chain](https://mlsanity.com/paper/1806.06047/) (2018)

## Built on by (most cited first, 9 of 9)

- [On Rademacher Complexity-based Generalization Bounds for Deep Learning](https://mlsanity.com/paper/2208.04284/) (2022)
- [Theoretical analysis of deep neural networks for temporally dependent observations](https://mlsanity.com/paper/2210.11530/) (2022)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Global Convergence Rate of Deep Equilibrium Models with General Activations](https://mlsanity.com/paper/2302.05797/) (2023)
- [Trade-off Between Dependence and Complexity for Nonparametric Learning -- an Empirical Process Approach](https://mlsanity.com/paper/2401.08978/) (2024)
- [Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability constraints](https://mlsanity.com/paper/2405.20278/) (2024)
- [Generalization Bounds on Multi-Kernel Learning with Mixed Datasets](https://mlsanity.com/paper/2205.07313/) (2022)
- [Generalization Bounds for Equivariant Networks on Markov Data](https://mlsanity.com/paper/2503.00292/) (2025)
- [Causal Representation Learning on High-Dimensional Data: Benchmarks, Reproducibility, and Evaluation Metrics](https://mlsanity.com/paper/2603.17405/) (2026)

## Abstract (arXiv)

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.