# A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2017.

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

- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [Tighter PAC-Bayes Bounds Through Coin-Betting](https://mlsanity.com/paper/2302.05829/) (2023)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [On the Importance of Gradient Norm in PAC-Bayesian Bounds](https://mlsanity.com/paper/2210.06143/) (2022)
- [Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2607.14506/) (2026)
- [Position: There Is No Free Bayesian Uncertainty Quantification](https://mlsanity.com/paper/2506.03670/) (2025)
- [Hardness, Structural Knowledge, and Opportunity: An Analytical Framework for Modular Performance Modeling](https://mlsanity.com/paper/2509.11000/) (2025)

## Abstract (arXiv)

We present a novel notion of complexity that interpolates between and generalizes some classic existing complexity notions in learning theory: for estimators like empirical risk minimization (ERM) with arbitrary bounded losses, it is upper bounded in terms of data-independent Rademacher complexity; for generalized Bayesian estimators, it is upper bounded by the data-dependent information complexity (also known as stochastic or PAC-Bayesian, KL(posterior operatorname| prior) complexity. For (penalized) ERM, the new complexity reduces to (generalized) normalized maximum likelihood (NML) complexity, i.e. a minimax log-loss individual-sequence regret. Our first main result bounds excess risk in terms of the new complexity. Our second main result links the new complexity via Rademacher complexity to L2(P) entropy, thereby generalizing earlier results of Opper, Haussler, Lugosi, and Cesa-Bianchi who did the log-loss case with L_∞. Together, these results recover optimal bounds for VC- and large (polynomial entropy) classes, replacing localized Rademacher complexity by a simpler analysis which almost completely separates the two aspects that determine the achievable rates: 'easiness' (Bernstein) conditions and model complexity.