Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss

Zhenhuan Yang, Yunwen Lei, Siwei Lyu, Yiming Ying

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

42 Downloads (Pure)

Abstract

Pairwise learning has recently received increasing attention since it subsumes many important machine learning tasks (e.g. AUC maximization and metric learning) into a unifying framework. In this paper, we give the first-ever-known stability and generalization analysis of stochastic gradient descent (SGD) for pairwise learning with non-smooth loss functions, which are widely used (e.g. Ranking SVM with the hinge loss). We introduce a novel decomposition in its stability analysis to decouple the pairwisely dependent random variables, and derive generalization bounds consistent with pointwise learning. Furthermore, we apply our stability analysis to develop differentially private SGD for pairwise learning, for which our utility bounds match with the state-of-the-art output perturbation method (Huai et al., 2020) with smooth losses. Finally, we illustrate the results using specific examples of AUC maximization and similarity metric learning. As a byproduct, we provide an affirmative solution to an open question on the advantage of the nuclear-norm constraint over Frobenius norm constraint in similarity metric learning.
Original languageEnglish
Title of host publicationProceedings of The 24th International Conference on Artificial Intelligence and Statistics
EditorsArindam Banerjee, Kenji Fukumizu
Pages2026-2034
Number of pages9
Publication statusPublished - 15 Apr 2021
EventThe 24th International Conference on Artificial Intelligence and Statistics - Virtual Conference
Duration: 13 Apr 202115 Apr 2021

Publication series

NameProceedings of Machine Learning Research
Volume130
ISSN (Electronic)2640-3498

Conference

ConferenceThe 24th International Conference on Artificial Intelligence and Statistics
Abbreviated titleAISTATS 2021
Period13/04/2115/04/21

Fingerprint

Dive into the research topics of 'Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss'. Together they form a unique fingerprint.

Cite this