Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted
  Majority Vote
  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 the PAC-Bayes-Bennett
inequality, which we use for empirical estimation of the oracle bound. The
PAC-Bayes-Bennett inequality improves on the PAC-Bayes-Bernstein inequality by
Seldin et al. [2012]. We provide an empirical evaluation demonstrating that the
new bounds can improve on the work by 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.
