Review for NeurIPS paper: Sharper Generalization Bounds for Pairwise Learning

Summary and Contributions: The paper adresses the generalization of pairwise learning (minimization of an expected loss depending on independent data pairs) under the perspective of algorithmic stability. Pairwise learning is relevant to ranking and metric learning. Theorem 1, the first bound on the generalization gap on which most other results in the paper are based, relies on uniform stability of the training algorithm, as introduced by Boulsquet/Elisseeff in 2002. The bound is of O(\gamma log n n {-1/2}, where \gamma is the stability parameter and n the sample size, and it also replaces the frequenttly assumed boundedness of the loss function by a uniform bound on the sample-expectation of the loss of the algorithms output. Theorem 3 then considers regularized algorithms minimizing a strongly convex objective under Lipschitz assumptions, and second-moment assumptions on the minimizer of the regularized risk.