A Tight Excess Risk Bound via a Unified PAC-Bayesian–Rademacher–Shtarkov–MDL Complexity
Abstract
We present a novel notion of complexity that interpolates between and generalizes some classic complexity notions in learning theory: for empirical risk minimization (ERM) with arbitrary bounded loss, it is upper bounded in terms of data-independent Rademacher complexity; for generalized Bayesian estimators, it is upper bounded by the data-dependent information (KL) complexity. For ERM, the new complexity reduces to normalized maximum likelihood 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 to $L_2(P)$ entropy via Rademacher complexity, generalizing earlier results of Opper, Haussler, Lugosi, and Cesa-Bianchi who covered the log-loss case with $L_\infty$ entropy. Together, these results recover optimal bounds for VC-type and large (polynomial entropy) classes, replacing local Rademacher complexities by a simpler analysis which almost completely separates the two aspects that determine the achievable rates: ‘easiness’ (Bernstein) conditions and model complexity.
Cite
Text
Grünwald and Mehta. "A Tight Excess Risk Bound via a Unified PAC-Bayesian–Rademacher–Shtarkov–MDL Complexity." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.Markdown
[Grünwald and Mehta. "A Tight Excess Risk Bound via a Unified PAC-Bayesian–Rademacher–Shtarkov–MDL Complexity." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.](https://mlanthology.org/alt/2019/grunwald2019alt-tight/)BibTeX
@inproceedings{grunwald2019alt-tight,
title = {{A Tight Excess Risk Bound via a Unified PAC-Bayesian–Rademacher–Shtarkov–MDL Complexity}},
author = {Grünwald, Peter D. and Mehta, Nishant A.},
booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory},
year = {2019},
pages = {433-465},
volume = {98},
url = {https://mlanthology.org/alt/2019/grunwald2019alt-tight/}
}