# Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 2 Feb 2024.

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

- [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)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [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)
- [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)
- [Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory](https://mlsanity.com/paper/2310.06483/) (2023)

## Abstract (arXiv)

Pairwise learning, an important domain within machine learning, addresses loss functions defined on pairs of training examples, including those in metric learning and AUC maximization. Acknowledging the quadratic growth in computation complexity accompanying pairwise loss as the sample size grows, researchers have turned to online gradient descent (OGD) methods for enhanced scalability. Recently, an OGD algorithm emerged, employing gradient computation involving prior and most recent examples, a step that effectively reduces algorithmic complexity to O(T), with T being the number of received examples. This approach, however, confines itself to linear models while assuming the independence of example arrivals. We introduce a lightweight OGD algorithm that does not require the independence of examples and generalizes to kernel pairwise learning. Our algorithm builds the gradient based on a random example and a moving average representing the past data, which results in a sub-linear regret bound with a complexity of O(T). Furthermore, through the integration of O(√TlogT) random Fourier features, the complexity of kernel calculations is effectively minimized. Several experiments with real-world datasets show that the proposed technique outperforms kernel and linear algorithms in offline and online scenarios.