Improved Lower Bounds for Learning from Noisy Examples: An Information-Theoretic Approach

Claudio Gentile, David P. Helmbold

Abstract

This paper presents a general information-theoretic approach for obtaining lower bounds on the number of examples required for Probably Approximately Correct (PAC) learning in the presence of noise. This approach deals directly with the fundamental information quantities, avoiding a Bayesian analysis. The technique is applied to several different models, illustrating its generality and power. The resulting bounds add logarithmic factors to (or improve the constants in) previously known lower bounds.
BibTeX
@inproceedings{gentile1998improved,
  author = {Claudio Gentile and David P. Helmbold},
  title = {{Improved Lower Bounds for Learning from Noisy Examples: An Information-Theoretic Approach}},
  booktitle = {Conference on Learning Theory},
  year = {1998},
  doi = {10.1145/279943.279965},
}

Loading related content...

Figure