proofs of Section 3

Assume |S|= m, for some m>0. Then, corresponding set of incorrectly-labelled examples is of size | S|= m(k 1). Let D S, be any distribution over m (k 1). We show that we can construct a distribution D S S over m k, for which the guarantee in the Lemma holds. First, observe that there must exist a m and b1,...,bm (k 1), such that for all i,j, we have D(i,j) = a(i)bi(j).