# Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2015.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)
- [Domain Watermark: Effective and Harmless Dataset Copyright Protection is Closed at Hand](https://mlsanity.com/paper/2310.14942/) (2023)
- [Diversity and Generalization in Neural Network Ensembles](https://mlsanity.com/paper/2110.13786/) (2021)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [When are ensembles really effective?](https://mlsanity.com/paper/2305.12313/) (2023)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [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)
- [PAC-Bayesian Domain Adaptation Bounds for Multiclass Learners](https://mlsanity.com/paper/2207.05685/) (2022)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Enhancing Robust Fairness via Confusional Spectral Regularization](https://mlsanity.com/paper/2501.13273/) (2025)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (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)
- [Are Ensembles Getting Better all the Time?](https://mlsanity.com/paper/2311.17885/) (2023)
- [A sparse PAC-Bayesian approach for high-dimensional quantile prediction](https://mlsanity.com/paper/2409.01687/) (2024)
- [Adaptive transfer learning](https://mlsanity.com/paper/2106.04455/) (2021)
- [There is no Double-Descent in Random Forests](https://mlsanity.com/paper/2111.04409/) (2021)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [PAC Bayesian Performance Guarantees for Deep (Stochastic) Networks in Medical Imaging](https://mlsanity.com/paper/2104.05600/) (2021)
- [Multi-class Probabilistic Bounds for Self-learning](https://mlsanity.com/paper/2109.14422/) (2021)
- [Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound](https://mlsanity.com/paper/2202.05560/) (2022)
- [Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks](https://mlsanity.com/paper/2410.13577/) (2024)
- [A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes](https://mlsanity.com/paper/2510.25569/) (2025)
- [Two Calls, Two Moments, and the Vote-Accuracy Curve of Repeated LLM Inference](https://mlsanity.com/paper/2605.03379/) (2026)
- [PAC-Bayesian Domain Adaptation Bounds for Multi-view learning](https://mlsanity.com/paper/2401.01048/) (2024)

## Abstract (arXiv)

We propose an extensive analysis of the behavior of majority votes in binary classification. In particular, we introduce a risk bound for majority votes, called the C-bound, that takes into account the average quality of the voters and their average disagreement. We also propose an extensive PAC-Bayesian analysis that shows how the C-bound can be estimated from various observations contained in the training data. The analysis intends to be self-contained and can be used as introductory material to PAC-Bayesian statistical learning theory. It starts from a general PAC-Bayesian perspective and ends with uncommon PAC-Bayesian bounds. Some of these bounds contain no Kullback-Leibler divergence and others allow kernel functions to be used as voters (via the sample compression setting). Finally, out of the analysis, we propose the MinCq learning algorithm that basically minimizes the C-bound. MinCq reduces to a simple quadratic program. Aside from being theoretically grounded, MinCq achieves state-of-the-art performance, as shown in our extensive empirical comparison with both AdaBoost and the Support Vector Machine.