Re: A little puzzle
This problem makes me wonder if the VC dimension formula for the growth function isn't (sometimes?) far too restrictive. It's true that the growth function here is 2^N, and therefore our problem is maybe unlearnable. But is that really true? Because we could find one wacko example with numbers 2^50 digits long, does that mean that our hypotheses are really much too general? Actually, this set of hypotheses is awfully restricted, and you (probably) can't hardly do anything with them for almost all sets of x1,...xn. Maybe we should have a modified version of the VC formula, where the bound works for almost all sets of xn. Is it still true that the growth will be polynomial, almost always?
