# Second Order PAC-Bayesian Bounds for the Weighted Majority Vote

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 30 of 34)

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [Diversity and Generalization in Neural Network Ensembles](https://mlsanity.com/paper/2110.13786/) (2021)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [Joint Training of Deep Ensembles Fails Due to Learner Collusion](https://mlsanity.com/paper/2301.11323/) (2023)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [When are ensembles really effective?](https://mlsanity.com/paper/2305.12313/) (2023)
- [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)
- [A PAC-Bayes Analysis of Adversarial Robustness](https://mlsanity.com/paper/2102.11069/) (2021)
- [Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote](https://mlsanity.com/paper/2106.13624/) (2021)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty](https://mlsanity.com/paper/2210.11289/) (2022)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Bound](https://mlsanity.com/paper/2104.13626/) (2021)
- [On Margins and Generalisation for Voting Classifiers](https://mlsanity.com/paper/2206.04607/) (2022)
- [Loss function based second-order Jensen inequality and its application to particle variational inference](https://mlsanity.com/paper/2106.05010/) (2021)
- [Multi-class Probabilistic Bounds for Self-learning](https://mlsanity.com/paper/2109.14422/) (2021)
- [Confident Sinkhorn Allocation for Pseudo-Labeling](https://mlsanity.com/paper/2206.05880/) (2022)
- [Improving Fairness with Ensemble Combination: Margin-Dependent Bounds](https://mlsanity.com/paper/2301.10813/) (2023)
- [PAC-Bayesian Soft Actor-Critic Learning](https://mlsanity.com/paper/2301.12776/) (2023)
- [A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes](https://mlsanity.com/paper/2510.25569/) (2025)
- [Kernel Interpolation as a Bayes Point Machine](https://mlsanity.com/paper/2110.04274/) (2021)
- [Responsible AI (RAI) Games and Ensembles](https://mlsanity.com/paper/2310.18832/) (2023)
- [Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds](https://mlsanity.com/paper/2411.06276/) (2024)
- [Smoothness-Based Derandomization of PAC-Bayes Bounds](https://mlsanity.com/paper/2606.19105/) (2026)
- [Excess risk analysis for epistemic uncertainty with application to variational inference](https://mlsanity.com/paper/2206.01606/) (2022)
- [EnSolver: Uncertainty-Aware Ensemble CAPTCHA Solvers with Theoretical Guarantees](https://mlsanity.com/paper/2307.15180/) (2023)
- [Something for (almost) nothing: Improving deep ensemble calibration using unlabeled data](https://mlsanity.com/paper/2310.02885/) (2023)
- [On Uniform, Bayesian, and PAC-Bayesian Deep Ensembles](https://mlsanity.com/paper/2406.05469/) (2024)
- [How many classifiers do we need?](https://mlsanity.com/paper/2411.00328/) (2024)

## Abstract (arXiv)

We present a novel analysis of the expected risk of weighted majority vote in multiclass classification. The analysis takes correlation of predictions by ensemble members into account and provides a bound that is amenable to efficient minimization, which yields improved weighting for the majority vote. We also provide a specialized version of our bound for binary classification, which allows to exploit additional unlabeled data for tighter risk estimation. In experiments, we apply the bound to improve weighting of trees in random forests and show that, in contrast to the commonly used first order bound, minimization of the new bound typically does not lead to degradation of the test error of the ensemble.