SharperGeneralizationBoundsforPairwise Learning: SupplementaryMaterial

Let S = {z1,...,zn} be a set of independent random variables each taking values inZ and M > 0. Letg1,...,gn be some functionsgi: Zn 7 R such that the following holdsforanyi [n] LetA:Zn 7 W beγ-uniformly stable. The following lemma establishes the uniform stability of pairwise learning with strongly convex objectives. The second term is the optimization error which comes since theoptimization algorithm maynotoutputtheexactminimizer. ThenTheorem 4actually presents estimation error bounds. We then introduce some basic properties of smooth functions.