# Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 25 Jun 2021.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [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)
- [Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds](https://mlsanity.com/paper/1810.12263/) (2018)
- [On PAC-Bayesian Bounds for Random Forests](https://mlsanity.com/paper/1810.09746/) (2018)
- [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, 13 of 13)

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [On Margins and Generalisation for Voting Classifiers](https://mlsanity.com/paper/2206.04607/) (2022)
- [Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss](https://mlsanity.com/paper/2405.14681/) (2024)
- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes](https://mlsanity.com/paper/2510.25569/) (2025)
- [Stability of Weighted Majority Voting under Estimated Weights](https://mlsanity.com/paper/2207.06118/) (2022)
- [Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds](https://mlsanity.com/paper/2411.06276/) (2024)
- [On Uniform, Bayesian, and PAC-Bayesian Deep Ensembles](https://mlsanity.com/paper/2406.05469/) (2024)
- [Soft Specialists: α-R'enyi Ensembles for Uncertainty-Aware LLM Post-Training](https://mlsanity.com/paper/2605.27747/) (2026)
- [Learning Perturbation Robust Policies for LLM Agents with Stable Optimization](https://mlsanity.com/paper/2609.34064/) (2026)

## Abstract (arXiv)

We present a new second-order oracle bound for the expected risk of a weighted majority vote. The bound is based on a novel parametric form of the Chebyshev- Cantelli inequality (a.k.a. one-sided Chebyshev's), which is amenable to efficient minimization. The new form resolves the optimization challenge faced by prior oracle bounds based on the Chebyshev-Cantelli inequality, the C-bounds [Germain et al., 2015], and, at the same time, it improves on the oracle bound based on second order Markov's inequality introduced by Masegosa et al. [2020]. We also derive a new concentration of measure inequality, which we name PAC-Bayes-Bennett, since it combines PAC-Bayesian bounding with Bennett's inequality. We use it for empirical estimation of the oracle bound. The PAC-Bayes-Bennett inequality improves on the PAC-Bayes-Bernstein inequality of Seldin et al. [2012]. We provide an empirical evaluation demonstrating that the new bounds can improve on the work of Masegosa et al. [2020]. Both the parametric form of the Chebyshev-Cantelli inequality and the PAC-Bayes-Bennett inequality may be of independent interest for the study of concentration of measure in other domains.