Online Pairwise Learning Algorithms

Abstract

Pairwise learning refers to tasks where the considered loss function depends on pairs of sample data, such as bipartite ranking, metric learning and AUC maximisation. In this setting, we consider variants of Online Pairwise lEarRning Algorithm (OPERA), proposed in [57], where, as OPERA, iterates of these online algorithms are not constrained to a bounded domain of the reproducing kernel Hilbert space (RKHS) nor is the least square loss based risk functional assumed to be strongly convex.
First, we show that OPERA in the linear case exhibits faster convergence rates than previously thought. In fact, we prove that convergence to the minimiser of the true risk is arbitrarily close to O(1/T), a noticeable improvement over previous online pairwise learning results known to converge in O(1/√T ), [27,50], and over the at best O(T ¯ ^1/3 ) of OPERA for general kernels [57]. We also present an efficient implementation resulting in a linear time complexity as well a constant space complexity with respect to the number of samples, and not the quadratic dependence in the data size usually associated with pairwise learning. Preliminary numerical experiments are also presented for completeness.
Then, we proceed to introduce and analyse the convergence of two variants of OPERA in an attempt to obtain a fully online algorithm, respectively by the addition of a recursive update of a sum and by using a stochastic update at each iteration. As a matter of fact, the original OPERA is an online algorithm in the sense that it needs a sequential access to the data, but it is not fully online in the sense that it needs more than one pair of sample at each iteration. Although the two previous variants are fully online, their implementations cannot benefit from an efficient implementation for both linear time complexity and constant space complexity as it is the case for OPERA in the linear case.
We finally present a novel truly online algorithm exhibiting the expected behaviour, fully online with efficient implementation. This is achieved by showing that the pairwise formulation of the problem can be reduced to an univariate regression with offset. The algorithm only needs to perform a per-instance stochastic gradient update and therefore does not need to store the previous samples.

Date of Award	24 Aug 2016
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Dingxuan ZHOU (Supervisor)