# Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 68 references that are in the map.
- First posted on arXiv 29 Oct 2024.

## Builds on (most cited first, 30 of 31)

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning](https://mlsanity.com/paper/1902.03932/) (2019)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Practical Deep Learning with Bayesian Principles](https://mlsanity.com/paper/1906.02506/) (2019)
- [Priors in Bayesian Deep Learning: A Review](https://mlsanity.com/paper/2105.06868/) (2021)
- [Deep ReLU network approximation of functions on a manifold](https://mlsanity.com/paper/1908.00695/) (2019)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [Posterior Concentration for Sparse Deep Learning](https://mlsanity.com/paper/1803.09138/) (2018)
- [Data augmentation in Bayesian neural networks and the cold posterior effect](https://mlsanity.com/paper/2106.05586/) (2021)
- [Smooth function approximation by deep neural networks with general activation functions](https://mlsanity.com/paper/1906.06903/) (2019)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Convergence Rates of Variational Inference in Sparse Deep Learning](https://mlsanity.com/paper/1908.04847/) (2019)
- [Consistent Sparse Deep Learning: Theory and Computation](https://mlsanity.com/paper/2102.13229/) (2021)
- [Disentangling the Roles of Curation, Data-Augmentation and the Prior in the Cold Posterior Effect](https://mlsanity.com/paper/2106.06596/) (2021)
- [Nonconvex sparse regularization for deep neural networks and its optimality](https://mlsanity.com/paper/2003.11769/) (2020)
- [Theoretical analysis of deep neural networks for temporally dependent observations](https://mlsanity.com/paper/2210.11530/) (2022)
- [Classification with Deep Neural Networks and Logistic Loss](https://mlsanity.com/paper/2307.16792/) (2023)
- [On the rate of convergence of a deep recurrent neural network estimate in a regression problem with dependent data](https://mlsanity.com/paper/2011.00328/) (2020)
- [Adaptive deep learning for nonlinear time series models](https://mlsanity.com/paper/2207.02546/) (2022)
- [FSP-Laplace: Function-Space Priors for the Laplace Approximation in Bayesian Deep Learning](https://mlsanity.com/paper/2407.13711/) (2024)
- [Wide stochastic networks: Gaussian limit and PAC-Bayesian training](https://mlsanity.com/paper/2106.09798/) (2021)
- [A reduced-rank approach to predicting multiple binary responses through machine learning](https://mlsanity.com/paper/2306.05829/) (2023)
- [Posterior and variational inference for deep neural networks with heavy-tailed weights](https://mlsanity.com/paper/2406.03369/) (2024)
- [Excess risk bound for deep learning under weak dependence](https://mlsanity.com/paper/2302.07503/) (2023)
- [Sparse-penalized deep neural networks estimator under weak dependence](https://mlsanity.com/paper/2303.01406/) (2023)
- [Posterior concentrations of fully-connected Bayesian neural networks with general priors on the weights](https://mlsanity.com/paper/2403.14225/) (2024)
- [Misclassification bounds for PAC-Bayesian sparse deep learning](https://mlsanity.com/paper/2405.01304/) (2024)
- [Deep Horseshoe Gaussian Processes](https://mlsanity.com/paper/2403.01737/) (2024)

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

- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [A general framework for deep learning](https://mlsanity.com/paper/2512.23425/) (2025)
- [Deep regression learning from dependent observations with minimum error entropy principle](https://mlsanity.com/paper/2603.11138/) (2026)
- [Adaptive deep nonparametric regression from dependent data under covariate shift](https://mlsanity.com/paper/2607.20309/) (2026)

## Abstract (arXiv)

In a groundbreaking work, Schmidt-Hieber (2020) proved the minimax optimality of deep neural networks with ReLu activation for least-square regression estimation over a large class of functions defined by composition. In this paper, we extend these results in many directions. First, we remove the i.i.d. assumption on the observations, to allow some time dependence. The observations are assumed to be a Markov chain with a non-null pseudo-spectral gap. Then, we study a more general class of machine learning problems, which includes least-square and logistic regression as special cases. Leveraging on PAC-Bayes oracle inequalities and a version of Bernstein inequality due to Paulin (2015), we derive upper bounds on the estimation risk for a generalized Bayesian estimator. In the case of least-square regression, this bound matches (up to a logarithmic factor) the lower bound of Schmidt-Hieber (2020). We establish a similar lower bound for classification with the logistic loss, and prove that the proposed DNN estimator is optimal in the minimax sense.