Pairwise learning is essential in machine learning, especially for problems involving loss functions defined on pairs of training examples. Online gradient descent (OGD) algorithms have been proposed to handle online pairwise learning, where data arrives sequentially. However, the pairwise nature of the problem makes scalability challenging, as the gradient computation for a new sample involves all past samples. Recent advancements in OGD algorithms have aimed to reduce the complexity of calculating online gradients, achieving complexities less than $O(T)$ and even as low as $O(1)$. However, these approaches are primarily limited to linear models and have induced variance. In this study, we propose a limited memory OGD algorithm that extends to kernel online pairwise learning while improving the sublinear regret. Specifically, we establish a clear connection between the variance of online gradients and the regret, and construct online gradients using the most recent stratified samples with a limited buffer of size of $s$ representing all past data, which have a complexity of $O(sT)$ and employs $O(\sqrt{T}\log{T})$ random Fourier features for kernel approximation. Importantly, our theoretical results demonstrate that the variance-reduced online gradients lead to an improved sublinear regret bound. The experiments on real-world datasets demonstrate the superiority of our algorithm over both kernelized and linear online pairwise learning algorithms.

在线渐减梯度法是解决涉及训练示例对的损失函数机器学习问题中至关重要的方法之一。本研究提出了一种扩展到核在线成对学习的有限内存在线渐减梯度算法，同时改善亚线性遗憾。通过构建在线渐减梯度与格雷特之间的清晰关系，并使用存储有限数量的最新分层样本构建在线渐减梯度，我们的算法在真实数据集上的实验证明其优于核化和线性的在线成对学习算法。

有限内存下降低方差的在线梯度下降法在核化对学习中的应用