# Misclassification excess risk bounds for PAC-Bayesian classification via convexified loss

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 16 Aug 2024.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [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)
- [Concentration of tempered posteriors and of their variational approximations](https://mlsanity.com/paper/1706.09293/) (2017)
- [Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds](https://mlsanity.com/paper/1810.12263/) (2018)
- [High-dimensional classification by sparse logistic regression](https://mlsanity.com/paper/1706.08344/) (2017)
- [1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation](https://mlsanity.com/paper/1604.04191/) (2016)
- [A reduced-rank approach to predicting multiple binary responses through machine learning](https://mlsanity.com/paper/2306.05829/) (2023)
- [High-dimensional sparse classification using exponential weighting with empirical hinge loss](https://mlsanity.com/paper/2312.12952/) (2023)
- [Collective Matrix Completion](https://mlsanity.com/paper/1807.09010/) (2018)
- [Misclassification bounds for PAC-Bayesian sparse deep learning](https://mlsanity.com/paper/2405.01304/) (2024)

## Abstract (arXiv)

PAC-Bayesian bounds have proven to be a valuable tool for deriving generalization bounds and for designing new learning algorithms in machine learning. However, it typically focus on providing generalization bounds with respect to a chosen loss function. In classification tasks, due to the non-convex nature of the 0-1 loss, a convex surrogate loss is often used, and thus current PAC-Bayesian bounds are primarily specified for this convex surrogate. This work shifts its focus to providing misclassification excess risk bounds for PAC-Bayesian classification when using a convex surrogate loss. Our key ingredient here is to leverage PAC-Bayesian relative bounds in expectation rather than relying on PAC-Bayesian bounds in probability. We demonstrate our approach in several important applications.