ML Anthology

PAC-MDL Bounds

Avrim Blum, John Langford
COLT 2003 pp. 344-357
doi:10.1007/978-3-540-45167-9_26 /colt/2003/blum2003colt-pac/

Abstract

We point out that a number of standard sample complexity bounds (VC-dimension, PAC-Bayes, and others) are all related to the number of bits required to communicate the labels given the unlabeled data for a natural communication game. Motivated by this observation, we give a general sample complexity bound based on this game that allows us to unify these different bounds in one common framework.

PDF COLT Semantic Scholar

Cite

Text

Blum and Langford. "PAC-MDL Bounds." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_26

Markdown

[Blum and Langford. "PAC-MDL Bounds." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/blum2003colt-pac/) doi:10.1007/978-3-540-45167-9_26

BibTeX

@inproceedings{blum2003colt-pac,
  title     = {{PAC-MDL Bounds}},
  author    = {Blum, Avrim and Langford, John},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2003},
  pages     = {344-357},
  doi       = {10.1007/978-3-540-45167-9_26},
  url       = {https://mlanthology.org/colt/2003/blum2003colt-pac/}
}