Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
This work addresses a theoretical bottleneck in machine learning for researchers studying concentration inequalities and risk bounds, though it appears incremental as it builds on existing methods.
The paper tackles the problem of bounding the expected risk of weighted majority votes by introducing a new second-order oracle bound based on a parametric form of the Chebyshev-Cantelli inequality, which improves on prior bounds like the C-bounds and second-order Markov's inequality, and demonstrates empirical improvements over recent work.
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.