2010-10-29 More on VC-dimension

Today we proved the upper and lower bound theorems relating sample size for PAC-learning and VC-dimension.

We also presented the Chernoff and Hoeffding bounds, which we will use other times during the course (and are very often used in algorithmic design and complexity).
In fact, it was needed at one point of the proof above.

Exercise 9: Complete the proof that Pr(A) <= 2Pr(B) that we left pending in the proof of the upper bound theorem. This uses Hoeffding. Additional exercise, not stated in class:

Exercise 10: The upper and bound theorems presented in class gave conditions on the sample size for consistent algorithms, that is, learning algorithms that always achieve 0 errors on the sample. Not algorithms are like consistent. Extend the upper bound theorem to show that for sufficiently
large sample size, we have

|error_D(c) - error_S(c)| < epsilon with probability 1-delta

This is a more general form of generalization bound.

(Hint: go over the proof for the consistent case, see where the consistency hypothesis (error_S(c) = 0) is used, and see what you can claim for non-consistent algorithms. The Chernoff or Hoeffding bound will be used. You should get a dependence on epsilon of the form 1/epsilon^2 rather than 1/epsilon).