Improved lower bounds for learning from noisy examples: An information-theoretic approach

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 direct ly with the fundamental information quantities, avoiding a Bayesian analysi s. The technique is applied to several different models, illustrating its g enerality and power. The resulting bounds add logarithmic factors to (or im prove the constants in) previously known lower bounds. (C) 2001 Academic Pr ess.