# On Margins and Generalisation for Voting Classifiers

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 9 Jun 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Tabular Data: Deep Learning is Not All You Need](https://mlsanity.com/paper/2106.03253/) (2021)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [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)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016)
- [Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm](https://mlsanity.com/paper/1503.08329/) (2015)
- [Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks](https://mlsanity.com/paper/1905.10259/) (2019)
- [Second Order PAC-Bayesian Bounds for the Weighted Majority Vote](https://mlsanity.com/paper/2007.13532/) (2020)
- [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [On Margins and Derandomisation in PAC-Bayes](https://mlsanity.com/paper/2107.03955/) (2021)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)
- [Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote](https://mlsanity.com/paper/2106.13624/) (2021)
- [Spacecraft Collision Avoidance Challenge: design and results of a machine learning competition](https://mlsanity.com/paper/2008.03069/) (2020)
- [On PAC-Bayesian Bounds for Random Forests](https://mlsanity.com/paper/1810.09746/) (2018)
- [Margins are Insufficient for Explaining Gradient Boosting](https://mlsanity.com/paper/2011.04998/) (2020)
- [Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Bound](https://mlsanity.com/paper/2104.13626/) (2021)

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

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty](https://mlsanity.com/paper/2210.11289/) (2022)
- [Are Ensembles Getting Better all the Time?](https://mlsanity.com/paper/2311.17885/) (2023)
- [Federated Learning with Nonvacuous Generalisation Bounds](https://mlsanity.com/paper/2310.11203/) (2023)
- [On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithm](https://mlsanity.com/paper/2609.16803/) (2026)

## Abstract (arXiv)

We study the generalisation properties of majority voting on finite ensembles of classifiers, proving margin-based generalisation bounds via the PAC-Bayes theory. These provide state-of-the-art guarantees on a number of classification tasks. Our central results leverage the Dirichlet posteriors studied recently by Zantedeschi et al. [2021] for training voting classifiers; in contrast to that work our bounds apply to non-randomised votes via the use of margins. Our contributions add perspective to the debate on the "margins theory" proposed by Schapire et al. [1998] for the generalisation of ensemble classifiers.