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

Hilal AlQuabeh, William de Vazelhes, Bin Gu

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

Introduction

In standard machine learning, models typically process individual data points in isolation. However, pairwise learning is critical for tasks where the loss function depends on the relationship between pairs of examples, such as AUC maximization (comparing positive and negative samples) and metric learning (calculating distances for image retrieval).

The primary challenge in this domain is scalability. In an online setting, a naive update for the $T$-th data point requires comparisons against all $T-1$ previous points, leading to a quadratic computational complexity of $O(T^2)$. While buffer-based methods have attempted to mitigate this, they often rely on the assumption that data is independent and identically distributed (i.i.d.), which rarely holds in dynamic or adversarial real-world environments. This paper introduces Average Online Gradient Descent (AOGD), a lightweight algorithm designed to achieve $O(T)$ complexity without requiring i.i.d. data streams.

Methodology

AOGD maintains high accuracy and low memory usage through two primary innovations:

  1. Dynamic Averaging & Random Correction: To avoid storing a massive history, the algorithm maintains a moving average of all past data. To correct for the "Jensen's gap" (the bias introduced by using an average in a non-linear loss function), AOGD incorporates a single random sample from the history using a Bernoulli sampling strategy. The resulting gradient update combines the information from the average and this random "correction" point, maintaining a buffer size of essentially $O(1)$.
  2. Kernelization via Random Fourier Features (RFF): To capture non-linear relationships efficiently, AOGD utilizes RFF to map data into a lower-dimensional space. By using $O(\sqrt{T} \log T)$ random features, the algorithm maintains sub-linear regret while keeping per-step computation linear ($O(T)$), avoiding the prohibitive costs of traditional kernel methods.

Experimental Evaluation

The researchers evaluated AOGD against several state-of-the-art linear and kernelized algorithms (including OGD, SPAM-NET, and KAR) across diverse benchmarks such as mnist, rcv1, and covtype.

AUC vs. CPU time on the mnist dataset, showing AOGD's superior performance and rapid convergence.

As shown in the mnist results, AOGD significantly outperforms competing online methods. On this dataset, AOGD achieved an AUC of 96.98, surpassing the next best online method, SPAM-NET, which reached 96.57. Beyond final accuracy, AOGD demonstrates exceptional convergence speed.

Comparison of convergence speed on the rcv1 dataset; AOGD reaches near-optimal AUC almost instantly compared to SPAM and KAR.

In the rcv1 dataset experiments, AOGD reaches high AUC scores much faster in terms of CPU time than competing methods like KAR and SPAM. This efficiency is a direct result of the $O(T)$ complexity and the streamlined gradient updates enabled by dynamic averaging.

Key Insights and Conclusion

AOGD successfully breaks the i.i.d. barrier, making it robust for streaming applications where data distributions may shift. By resolving the Jensen's Gap with a simple random correction and integrating RFF for non-linear expressiveness, the algorithm provides a theoretically sound and practically efficient solution for large-scale pairwise learning. Future work may explore the use of multiple moving averages over different time windows to further enhance adaptability to rapidly changing data streams.

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(√T logT) 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