Sharper Generalization Bounds for Pairwise Learning

Yunwen Lei, Antoine Ledent, Marius Kloft

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

19 Citations (Scopus)


Pairwise learning refers to learning tasks with loss functions depending on a pair of training examples, which includes ranking and metric learning as specific examples. Recently, there has been an increasing amount of attention on the generalization analysis of pairwise learning to understand its practical behavior. However, the existing stability analysis provides suboptimal high-probability generalization bounds. In this paper, we provide a refined stability analysis by developing generalization bounds which can be √n-times faster than the existing results, where n is the sample size. This implies excess risk bounds of the order O(n-1/2) (up to a logarithmic factor) for both regularized risk minimization and stochastic gradient descent. We also introduce a new on-average stability measure to develop optimistic bounds in a low noise setting. We apply our results to ranking and metric learning, and clearly show the advantage of our generalization bounds over the existing analysis.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 33
EditorsH. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, H. Lin
Number of pages11
ISBN (Electronic)9781713829546
Publication statusPublished - Dec 2020
Externally publishedYes
Event34th Conference on Neural Information Processing Systems, NeurIPS 2020 - Virtual, Online
Duration: 6 Dec 202012 Dec 2020


Conference34th Conference on Neural Information Processing Systems, NeurIPS 2020
Internet address

Scopus Subject Areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this