General Lower Bounds on Sample Complexity
Martin Anthony, Peter L. Bartlett · Cambridge University Press eBooks · 1999
Introduction In the previous chapters we showed that a class of functions of finite VC-dimension is learnable by the fairly natural class of SEM algorithms, and we provided bounds on the estimation error and sample complexity of these learning algorithms in terms of the VC-dimension of the class. In this chapter we provide lower bounds on the estimation error and sample complexity of any learning algorithm. These lower bounds are also in terms of the VC-dimension, and are not vastly different from the upper bounds of the previous chapter. We shall see, as a consequence, that the VC-dimension not only characterizes learnability, in the sense that a function class is learnable if and only if it has finite VC-dimension, but it provides precise information about the number of examples required. A Lower Bound for Learning A technical lemma The first step towards a general lower bound on the sample complexity is the following technical lemma, which will also prove useful in later chapters. It concerns the problem of estimating the parameter describing a Bernoulli random variable. Lemma 5.1 Suppose that α is a random variable uniformly distributed on {α − , α + }, where α − = 1/2 − ∈/2 and α + = 1/2 + ∈/2, with 0 < ∈ < 1. Suppose that ξ 1 , …, ξ m are i.i.d. (independent and identically distributed) {0, 1}- valued random variables with Pr(ξ i = 1) = α for all i. Let f be a function from {0, 1} m to {α − , α + }.