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:
- 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.
- 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.
- 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.
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.
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