mlsanityData to 7 Oct 2026

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

arXiv 1503.08329 ↗First posted 28 Mar 2015stat.ML cs.LGcited by 50

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 6; 2023: 7; 2024: 9; 2025: 7; 2026: 7.

50 papers.

Sort:

By area:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  2. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
  3. 2023Domain Watermark: Effective and Harmless Dataset Copyright Protection is Closed at Handcited by 52
  4. 2021Diversity and Generalization in Neural Network Ensemblescited by 32
  5. 2023A unified recipe for deriving (time-uniform) PAC-Bayes boundscited by 25
  6. 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
  7. 2023When are ensembles really effective?cited by 21
  8. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  9. 2021Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Boundcited by 16
  10. 2021A PAC-Bayes Analysis of Adversarial Robustnesscited by 13
  11. 2021Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Votecited by 13
  12. 2022PAC-Bayesian Domain Adaptation Bounds for Multiclass Learnerscited by 13
38 more
  1. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
  2. 2025Enhancing Robust Fairness via Confusional Spectral Regularizationcited by 11
  3. 2022Minimax risk classifiers with 0-1 losscited by 9
  4. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  5. 2021Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Boundcited by 8
  6. 2022On Margins and Generalisation for Voting Classifierscited by 7
  7. 2023Are Ensembles Getting Better all the Time?cited by 6
  8. 2024A sparse PAC-Bayesian approach for high-dimensional quantile predictioncited by 6
  9. 2021Adaptive transfer learningcited by 4
  10. 2021There is no Double-Descent in Random Forestscited by 4
  11. 2024Sample Compression Unleashed: New Generalization Bounds for Real Valued Lossescited by 4
  12. 2021PAC Bayesian Performance Guarantees for Deep (Stochastic) Networks in Medical Imagingcited by 3
  13. 2021Multi-class Probabilistic Bounds for Self-learningcited by 3
  14. 2022Controlling Multiple Errors Simultaneously with a PAC-Bayes Boundcited by 3
  15. 2024Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworkscited by 3
  16. 2025A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votescited by 3
  17. 2026Two Calls, Two Moments, and the Vote-Accuracy Curve of Repeated LLM Inferencecited by 3
  18. 2025Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifiercited by 2
  19. 2021Kernel Interpolation as a Bayes Point Machinecited by 1
  20. 2022Stability of Weighted Majority Voting under Estimated Weightscited by 1
  21. 2022Identify ambiguous tasks combining crowdsourced labels by weighting Areas Under the Margincited by 1
  22. 2023Responsible AI (RAI) Games and Ensemblescited by 1
  23. 2024PAC-Bayesian Domain Adaptation Bounds for Multi-view learningcited by 1
  24. 2024Learning via Surrogate PAC-Bayescited by 1
  25. 2024Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Boundscited by 1
  26. 2025Higher-order Structure Boosts Link Prediction on Temporal Graphscited by 1
  27. 2025Structured Basis Function Networks: Loss-Centric Multi-Hypothesis Ensembles with Controllable Diversitycited by 1
  28. 2025PAC-Bayesian Reinforcement Learning Trains Generalizable Policiescited by 1
  29. 2026Smoothness-Based Derandomization of PAC-Bayes Boundscited by 1
  30. 2023EnSolver: Uncertainty-Aware Ensemble CAPTCHA Solvers with Theoretical Guaranteescited by 0
  31. 2024A note on generalization bounds for losses with finite momentscited by 0
  32. 2024On Uniform, Bayesian, and PAC-Bayesian Deep Ensemblescited by 0
  33. 2025Principal Eigenvalue Regularization for Improved Worst-Class Certified Robustness of Smoothed Classifierscited by 0
  34. 2026PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifierscited by 0
  35. 2026Block-Sample MAC-Bayes Generalization Boundscited by 0
  36. 2026Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classificationcited by 0
  37. 2026Soft Specialists: α-R'enyi Ensembles for Uncertainty-Aware LLM Post-Trainingcited by 0
  38. 2026On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithmcited by 0