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

Hilal AlQuabeh, William de Vazelhes, Bin Gu

Abstract

Pairwise learning addresses loss functions defined on pairs of training examples, such as AUC maximization. While online gradient descent (OGD) methods offer scalability, existing $O(T)$ complexity approaches are often limited to linear models and assume independent example arrivals. We introduce Average Online Gradient Descent (AOGD), a lightweight algorithm that generalizes to kernel pairwise learning without requiring example independence. By utilizing dynamic moving averages and Random Fourier Features, AOGD achieves sub-linear regret with $O(T)$ complexity. Experimental results on real-world datasets demonstrate that AOGD outperforms existing kernel and linear algorithms in both offline and online scenarios.

Introduction

In standard machine learning, loss functions are typically defined on individual data points. However, pairwise learning—where the loss depends on pairs of examples—is essential for tasks like maximizing the Area Under the ROC Curve (AUC) or metric learning. The primary challenge in pairwise learning is scalability; as the number of samples $T$ grows, the number of pairs grows quadratically ($O(T^2)$), making traditional methods computationally prohibitive for large-scale data streams.

While buffer-based methods attempt to mitigate this, they often rely on the assumption that data is independent and identically distributed (i.i.d.), which rarely holds in real-world, non-stationary environments. Furthermore, many efficient solutions are restricted to linear models, failing to capture complex non-linear patterns.

Methods: Average Online Gradient Descent (AOGD)

The proposed AOGD algorithm addresses these limitations through three key innovations:

  1. Dynamic Averaging with Gap Correction: Instead of comparing new points to all previous data, AOGD maintains a moving average. To account for the bias introduced by Jensen’s Inequality (where the gradient of the average is not the average of the gradients), the algorithm uses a dual-update step. It combines a gradient step based on the moving average with a corrective step using a randomly sampled past instance.
  2. Kernelization via Random Fourier Features (RFF): To handle non-linear data efficiently, AOGD maps inputs into a high-dimensional space using RFF. By employing $O(\sqrt{T} \log T)$ random features, the algorithm maintains a sub-linear regret bound while avoiding the high cost of standard kernel methods.
  3. Limited Memory Footprint: Unlike reservoir sampling techniques that require $O(\sqrt{T})$ buffer sizes, AOGD achieves optimal regret bounds with a constant $O(1)$ buffer size, making it highly memory-efficient.

Experimental Evaluation

The researchers evaluated AOGD against state-of-the-art algorithms, including SPAM-NET and OGD, across seven datasets: diabetes, ijcnn1, a9a, mnist, rcv1, usps, and german.

Key Results

AOGD consistently demonstrated superior AUC performance and faster convergence. For instance, on the ijcnn1 dataset, AOGD reached an AUC of 92.32, outperforming the linear OGD's 89.46.

AUC performance over time on the ijcnn1 dataset showing AOGD's rapid convergence and high accuracy.

On larger datasets like rcv1, the efficiency gains are even more pronounced. AOGD reaches peak performance significantly faster than competing methods like KAR or SPAM, which struggle with the overhead of maintaining support vector sets or large buffers.

AUC performance over time on the rcv1 dataset highlighting the efficiency of AOGD compared to other kernelized methods.

The algorithm maintains a time complexity of $O(T)$ for linear models and $O(\frac{D}{d}T)$ for non-linear models, effectively bringing the cost of kernelized pairwise learning down to the level of standard online learning.

Conclusion and Future Work

AOGD provides a robust, scalable framework for non-linear pairwise learning on data streams. It breaks the dependency on i.i.d. assumptions and offers a significant reduction in computational complexity. Future research may explore the application of AOGD to different kernel types beyond the Gaussian kernel and investigate the use of multiple moving averages to further improve adaptability to highly noisy or shifting distributions.

Summary updated

Abstract

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(\sqrt{T}{\log{T}})$ 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.
BibTeX
@inproceedings{alquabeh2024limited,
  author = {Hilal AlQuabeh and William de Vazelhes and Bin Gu},
  title = {{Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=GK9WGZlPst},
}
Figure