Carnegie Mellon University
Browse

PAC-MDL Bounds

Download (229.64 kB)
journal contribution
posted on 1975-01-01, 00:00 authored by Avrim Blum, John Langford
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.

History

Publisher Statement

All Rights Reserved

Date

1975-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC