New Scalable and Efficient Online Pairwise Learning Algorithm

Pairwise learning is an important machine-learning topic with many practical applications. An online algorithm is the first choice for processing streaming data and is preferred for handling large-scale pairwise learning problems. However, existing online pairwise learning algorithms are not scalable and efficient enough for large-scale high-dimensional data, because they were designed based on singly stochastic gradients. To address this challenging problem, in this article, we propose a dynamic doubly stochastic gradient algorithm (D2SG) for online pairwise learning. Especially, only the time and space complexities of $\mathcal {O} (d)$ are needed for incorporating a new sample, where $d$ is the dimensionality of data. This means that our D2SG is much faster and more scalable than the existing online pairwise learning algorithms while the statistical accuracy can be guaranteed through our rigorous theoretical analysis under standard assumptions. The experimental results on a variety of real-world datasets not only confirm the theoretical result of our new D2SG algorithm, but also show that D2SG has better efficiency and scalability than the existing online pairwise learning algorithms.

I. Introduction

A lot of machine-learning problems can be formulated as pairwise learning paradigm [1] where the loss function involves a pair of samples and , where is a hypothesis function. For example, area under the curve (AUC) maximization [2], [3], [4], [5], [6] considers the least-square pairwise loss function as the form of , where and are with different labels. In addition to AUC maximization, many other machine-learning problems, such as metric learning [7], [8], [9], ranking [10], [11], and multiple kernel learning [12] also consider pairwise loss functions. Currently, pairwise learning [13] has been an important research topic in machine learning.