# Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory

arXiv: https://arxiv.org/abs/2310.06483 · HTML: https://mlsanity.com/paper/2310.06483/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 10 Oct 2023.

## Builds on (most cited first, 13 of 13)

- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Occlusion Robust Face Recognition Based on Mask Learning with PairwiseDifferential Siamese Network](https://mlsanity.com/paper/1908.06290/) (2019)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [The Fairness of Risk Scores Beyond Classification: Bipartite Ranking and the xAUC Metric](https://mlsanity.com/paper/1902.05826/) (2019)
- [On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions](https://mlsanity.com/paper/1305.2505/) (2013)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Pairwise Relational Networks for Face Recognition](https://mlsanity.com/paper/1808.04976/) (2018)
- [Sharp Analysis of Random Fourier Features in Classification](https://mlsanity.com/paper/2109.10623/) (2021)
- [Online Pairwise Learning Algorithms with Kernels](https://mlsanity.com/paper/1502.07229/) (2015)
- [A Sparse Nonlinear Classifier Design Using AUC Optimization](https://mlsanity.com/paper/1612.08633/) (2016)
- [Pairwise Learning via Stagewise Training in Proximal Setting](https://mlsanity.com/paper/2208.04075/) (2022)
- [Computational Complexity of Sub-Linear Convergent Algorithms](https://mlsanity.com/paper/2209.14558/) (2022)

## Built on by (most cited first, 1 of 1)

- [Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging](https://mlsanity.com/paper/2402.01146/) (2024)

## Abstract (arXiv)

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(√TlogT) 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.