TY - GEN
T1 - Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss
AU - Yang, Zhenhuan
AU - Lei, Yunwen
AU - Lyu, Siwei
AU - Ying, Yiming
PY - 2021/4/15
Y1 - 2021/4/15
N2 - 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.
AB - 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.
UR - http://proceedings.mlr.press/pmlr-license-agreement.pdf
M3 - Conference contribution
T3 - Proceedings of Machine Learning Research
SP - 2026
EP - 2034
BT - Proceedings of The 24th International Conference on Artificial Intelligence and Statistics
A2 - Banerjee, Arindam
A2 - Fukumizu, Kenji
T2 - The 24th International Conference on Artificial Intelligence and Statistics
Y2 - 13 April 2021 through 15 April 2021
ER -