Supplementary Material for " Refined Learning Bounds for Kernel and Approximate k-Means "

Lemma 2. There exists a set C H However our bound in Lemma 2 does match. To prove Theorem 1, we first give the following two lemmas: Lemma 5. To prove Theorem 4, we first propose the following lemma: Lemma 7. Thus, we can obtain that min(k, Ξ) k Ξ k 1 + c α 1 . Substituting the above inequality into Theorem 4, we can prove this result. Thus, by the above upper bounds the lower bound (Eq.