Online Learning with Pairwise Loss Functions
This work addresses a theoretical gap for researchers and practitioners in machine learning who use online learning for tasks like ranking and metric learning, but it is incremental as it builds on existing online learning frameworks.
The paper tackles the problem of deriving generalization bounds for online learning algorithms with pairwise loss functions, which are crucial for maximizing ROC AUC in large-scale systems, and provides the first data-dependent risk bounds for arbitrary online learners, demonstrating applicability to bipartite ranking and supervised metric learning.
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.