# Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 42 references that are in the map.
- First posted on arXiv 1 Jun 2022.

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

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Combating Label Noise in Deep Learning Using Abstention](https://mlsanity.com/paper/1905.10964/) (2019)
- [A Strongly Quasiconvex PAC-Bayesian Bound](https://mlsanity.com/paper/1608.05610/) (2016)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [Optimal learning with Bernstein Online Aggregation](https://mlsanity.com/paper/1404.1356/) (2014)
- [Second Order PAC-Bayesian Bounds for the Weighted Majority Vote](https://mlsanity.com/paper/2007.13532/) (2020)
- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote](https://mlsanity.com/paper/2106.13624/) (2021)
- [A Note on the Chernoff Bound for Random Variables in the Unit Interval](https://mlsanity.com/paper/2205.07880/) (2022)

## Built on by (most cited first, 11 of 11)

- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Tighter PAC-Bayes Bounds Through Coin-Betting](https://mlsanity.com/paper/2302.05829/) (2023)
- [Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty](https://mlsanity.com/paper/2210.11289/) (2022)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [Probabilistic Generating Circuits -- Demystified](https://mlsanity.com/paper/2404.02912/) (2024)
- [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)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Something for (almost) nothing: Improving deep ensemble calibration using unlabeled data](https://mlsanity.com/paper/2310.02885/) (2023)
- [Deep Actor-Critics with Tight Risk Certificates](https://mlsanity.com/paper/2505.19682/) (2025)

## Abstract (arXiv)

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.