Simple Stochastic and Online Gradient Descent Algorithms for Pairwise
  Learning
  Pairwise learning refers to learning tasks where the loss function depends on
a pair of instances. It instantiates many important machine learning tasks such
as bipartite ranking and metric learning. A popular approach to handle
streaming data in pairwise learning is an online gradient descent (OGD)
algorithm, where one needs to pair the current instance with a buffering set of
previous instances with a sufficiently large size and therefore suffers from a
scalability issue. In this paper, we propose simple stochastic and online
gradient descent methods for pairwise learning. A notable difference from the
existing studies is that we only pair the current instance with the previous
one in building a gradient direction, which is efficient in both the storage
and computational complexity. We develop novel stability results, optimization,
and generalization error bounds for both convex and nonconvex as well as both
smooth and nonsmooth problems. We introduce novel techniques to decouple the
dependency of models and the previous instance in both the optimization and
generalization analysis. Our study resolves an open question on developing
meaningful generalization bounds for OGD using a buffering set with a very
small fixed size. We also extend our algorithms and stability analysis to
develop differentially private SGD algorithms for pairwise learning which
significantly improves the existing results.
