  We present a new concentration of measure inequality for sums of independent
bounded random variables, which we name a split-kl inequality. The inequality
is particularly well-suited for ternary random variables, which naturally show
up in a variety of problems, including analysis of excess losses in
classification, analysis of weighted majority votes, and learning with
abstention. We demonstrate that for ternary random variables the inequality is
simultaneously competitive with the kl inequality, the Empirical Bernstein
inequality, and the Unexpected Bernstein inequality, and in certain regimes
outperforms all of them. It resolves an open question by Tolstikhin and Seldin
[2013] and Mhammedi et al. [2019] on how to match simultaneously the
combinatorial power of the kl inequality when the distribution happens to be
close to binary and the power of Bernstein inequalities to exploit low variance
when the probability mass is concentrated on the middle value. We also derive a
PAC-Bayes-split-kl inequality and compare it with the PAC-Bayes-kl,
PAC-Bayes-Empirical-Bennett, and PAC-Bayes-Unexpected-Bernstein inequalities in
an analysis of excess losses and in an analysis of a weighted majority vote for
several UCI datasets. Last but not least, our study provides the first direct
comparison of the Empirical Bernstein and Unexpected Bernstein inequalities and
their PAC-Bayes extensions.
