Online Learning with Pairwise Loss Functions
  Efficient online learning with pairwise loss functions is a crucial component
in building large-scale learning system that maximizes the area under the
Receiver Operator Characteristic (ROC) curve. In this paper we investigate the
generalization performance of online learning algorithms with pairwise loss
functions. We show that the existing proof techniques for generalization bounds
of online algorithms with a univariate loss can not be directly applied to
pairwise losses. In this paper, we derive the first result providing
data-dependent bounds for the average risk of the sequence of hypotheses
generated by an arbitrary online learner in terms of an easily computable
statistic, and show how to extract a low risk hypothesis from the sequence. We
demonstrate the generality of our results by applying it to two important
problems in machine learning. First, we analyze two online algorithms for
bipartite ranking; one being a natural extension of the perceptron algorithm
and the other using online convex optimization. Secondly, we provide an
analysis for the risk bound for an online algorithm for supervised metric
learning.
