Sharper Generalization Bounds for Pairwise Learning: Supplementary Material

To prove Theorem 1, we need to introduce some lemmas. The following lemma is attributed to [7], which provides far-reaching moment bounds for a summation of weakly dependent and mean-zero random functions with bounded increments under a change of any single coordinate. The bounds on moments of random variables can be used to establish concentration inequalities, as shown in the following lemma [4, 16]. Lemma A.2. Let a, b R The following lemma controls the change on the output of stable algorithms if we perturb a training dataset by two examples. With these lemmas, we can give the proof of Theorem 1 on high-probability bounds of the generalization gap.