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

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

Authors

Colleges, School and Institutes

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.

Details

Original languageEnglish
Title of host publicationProceedings of The 24th International Conference on Artificial Intelligence and Statistics
EditorsArindam Banerjee, Kenji Fukumizu
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