Generalization guarantee of SGD for pairwise learning

Yunwen Lei, Mingrui Liu, Yiming Ying

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Downloads (Pure)

Abstract

Recently, there is a growing interest in studying pairwise learning since it includes many important machine learning tasks as specific examples, e.g., metric learning, AUC maximization and ranking. While stochastic gradient descent (SGD) is an efficient method, there is a lacking study on its generalization behavior for pairwise learning. In this paper, we present a systematic study on the generalization analysis of SGD for pairwise learning to understand the balance between generalization and optimization. We develop a novel high-probability generalization bound for uniformly-stable algorithms to incorporate the variance information for better generalization, based on which we establish the first nonsmooth learning algorithm to achieve almost optimal high-probability and dimension-independent generalization bounds in linear time. We consider both convex and nonconvex pairwise learning problems. Our stability analysis for convex problems shows how the interpolation can help generalization. We establish a uniform convergence of gradients, and apply it to derive the first generalization bounds on population gradients for nonconvex problems. Finally, we develop better generalization bounds for gradient-dominated problems.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 34
EditorsM. Ranzato, A. Beygelzimer, P.S. Liang, J.W. Vaughan, Y. Dauphin
PublisherNeurIPS
Publication statusPublished - 1 Dec 2021
EventThirty-fifth Conference on Neural Information Processing Systems - Virtual
Duration: 6 Dec 202114 Dec 2021

Publication series

NameAdvances in neural information processing systems
ISSN (Print)1049-5258

Conference

ConferenceThirty-fifth Conference on Neural Information Processing Systems
Abbreviated titleNeurIPS 2021
Period6/12/2114/12/21

Fingerprint

Dive into the research topics of 'Generalization guarantee of SGD for pairwise learning'. Together they form a unique fingerprint.

Cite this