Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
12-2020
Abstract
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 √nn-times faster than the existing results, where nn 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.
Keywords
Pairwise learning, Stochastic Gradient Descent, Stability analysis, Learning theory
Discipline
Databases and Information Systems | Graphics and Human Computer Interfaces
Research Areas
Intelligent Systems and Optimization
Publication
Proceedings of the 35th Conference on Neural Information Processing System (NeurIPS 2020), Virtual Conference, December 6-12
Volume
33
First Page
21236
Last Page
21246
ISBN
9781713829546
City or Country
Virtual Conference
Citation
LEI, Yunwen; LEDENT, Antoine; and KLOFT, Marius.
Sharper generalisation bounds for pairwise learning. (2020). Proceedings of the 35th Conference on Neural Information Processing System (NeurIPS 2020), Virtual Conference, December 6-12. 33, 21236-21246.
Available at: https://ink.library.smu.edu.sg/sis_research/7208
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Included in
Databases and Information Systems Commons, Graphics and Human Computer Interfaces Commons