Stability and Optimization Error of Stochastic Gradient Descent for
  Pairwise Learning
  In this paper we study the stability and its trade-off with optimization
error for stochastic gradient descent (SGD) algorithms in the pairwise learning
setting. Pairwise learning refers to a learning task which involves a loss
function depending on pairs of instances among which notable examples are
bipartite ranking, metric learning, area under ROC (AUC) maximization and
minimum error entropy (MEE) principle. Our contribution is twofold. Firstly, we
establish the stability results of SGD for pairwise learning in the convex,
strongly convex and non-convex settings, from which generalization bounds can
be naturally derived. Secondly, we establish the trade-off between stability
and optimization error of SGD algorithms for pairwise learning. This is
achieved by lower-bounding the sum of stability and optimization error by the
minimax statistical error over a prescribed class of pairwise loss functions.
From this fundamental trade-off, we obtain lower bounds for the optimization
error of SGD algorithms and the excess expected risk over a class of pairwise
losses. In addition, we illustrate our stability results by giving some
specific examples of AUC maximization, metric learning and MEE.
