Improved lower bounds for learning from noisy examples
Claudio Gentile, David P. Helmbold · 1998
This paper presents a general information-theoretic approach for obtaining lower bounds on the number of examples needed to PAC learn 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.Pemlission to snake digital or hard copies of all or part of this work for personal or classroom use is gmnted without fee provided that copies are not nlade or distributed for profit or commercial advantage and that copies hear this notice and the full citation on the first page.To copy otherwise, to republish, to post on servers or to redistribute to lists, requuxs prior specific pcmlission and/or a fee.