# Misclassification bounds for PAC-Bayesian sparse deep learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 54 references that are in the map.
- First posted on arXiv 2 May 2024.

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

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [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)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Deep Neural Networks Learn Non-Smooth Functions Effectively](https://mlsanity.com/paper/1802.04474/) (2018)
- [Model Selection in Bayesian Neural Networks via Horseshoe Priors](https://mlsanity.com/paper/1705.10388/) (2017)
- [Posterior Concentration for Sparse Deep Learning](https://mlsanity.com/paper/1803.09138/) (2018)
- [Fast convergence rates of deep neural networks for classification](https://mlsanity.com/paper/1812.03599/) (2018)
- [Bayesian linear regression with sparse priors](https://mlsanity.com/paper/1403.0735/) (2014)
- [Efficient Variational Inference for Sparse Deep Learning with Theoretical Guarantee](https://mlsanity.com/paper/2011.07439/) (2020)
- [Convergence Rates of Variational Inference in Sparse Deep Learning](https://mlsanity.com/paper/1908.04847/) (2019)
- [On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces](https://mlsanity.com/paper/1905.09195/) (2019)
- [Convergence rates of deep ReLU networks for multiclass classification](https://mlsanity.com/paper/2108.00969/) (2021)
- [1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation](https://mlsanity.com/paper/1604.04191/) (2016)
- [Masked Bayesian Neural Networks : Theoretical Guarantee and its Posterior Inference](https://mlsanity.com/paper/2305.14765/) (2023)
- [On the rate of convergence of image classifiers based on convolutional neural networks](https://mlsanity.com/paper/2003.01526/) (2020)
- [Asymptotic Properties for Bayesian Neural Network in Besov Space](https://mlsanity.com/paper/2206.00241/) (2022)
- [On the Exponentially Weighted Aggregate with the Laplace Prior](https://mlsanity.com/paper/1611.08483/) (2016)

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

- [Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds](https://mlsanity.com/paper/2410.21702/) (2024)
- [Optimal sparse phase retrieval via a quasi-Bayesian approach](https://mlsanity.com/paper/2504.09509/) (2025)
- [Misclassification excess risk bounds for PAC-Bayesian classification via convexified loss](https://mlsanity.com/paper/2408.08675/) (2024)
- [High-dimensional prediction for count response via sparse exponential weights](https://mlsanity.com/paper/2410.15381/) (2024)
- [Kullback-Leibler excess risk bounds for exponential weighted aggregation in Generalized linear models](https://mlsanity.com/paper/2504.10171/) (2025)
- [Sparse classification with positive-confidence data in high dimensions](https://mlsanity.com/paper/2512.24443/) (2025)
- [Robust low-rank estimation with multiple binary responses using pairwise AUC loss](https://mlsanity.com/paper/2601.08618/) (2026)

## Abstract (arXiv)

Recently, there has been a significant focus on exploring the theoretical aspects of deep learning, especially regarding its performance in classification tasks. Bayesian deep learning has emerged as a unified probabilistic framework, seeking to integrate deep learning with Bayesian methodologies seamlessly. However, there exists a gap in the theoretical understanding of Bayesian approaches in deep learning for classification. This study presents an attempt to bridge that gap. By leveraging PAC-Bayes bounds techniques, we present theoretical results on the prediction or misclassification error of a probabilistic approach utilizing Spike-and-Slab priors for sparse deep learning in classification. We establish non-asymptotic results for the prediction error. Additionally, we demonstrate that, by considering different architectures, our results can achieve minimax optimal rates in both low and high-dimensional settings, up to a logarithmic factor. Moreover, our additional logarithmic term yields slight improvements over previous works. Additionally, we propose and analyze an automated model selection approach aimed at optimally choosing a network architecture with guaranteed optimality.