Appendix for " Generalization Guarantee of SGD for Pairwise Learning " Y unwen Lei

We collect in Table A.1 the notations of performance measures used in this paper.X input space Y output space Z sample space S training dataset n sample size z To this aim, we require the following lemma on the self-bounding property of smooth loss functions. We only consider Part (b). We can plug the above inequality back into (B.1), and get E[F ( A (S)) F In this section, we prove Theorem 2. To this aim, we first introduce some lemmas. Lemma C.3 is motivated by a recent Let p 2 be any number. C.1 to show that 1 null The stated bound then follows by combining the above two inequalities together.