Abstract
Kernel-based methods are powerful tools for nonlinear learning, yet they face significant challenges in large-scale streaming environments due to high computational complexity and the need to adapt to non-stationary data. This paper introduces AdaRaker, a scalable online algorithm that combines Random Feature (RF) approximations with an ensemble of learners operating at different learning rates. AdaRaker achieves sub-linear dynamic regret, ensuring robust performance in changing environments while significantly reducing computational overhead compared to traditional online multi-kernel learning (OMKL) methods.
Introduction
In the era of big data, streaming applications like social media trend analysis and sensor networks require algorithms that can handle non-linear relationships on the fly. However, two major hurdles persist: the curse of dimensionality, where memory requirements grow quadratically with data points, and non-stationarity, where the underlying data-generating process shifts over time. While Multi-Kernel Learning (MKL) offers flexibility, making it adaptive and efficient for online streams remains a hurdle. AdaRaker addresses these by linearizing the kernel problem and employing a multi-rate expert aggregation strategy.
Methodology
Raker: Scalable Multi-Kernel Learning
The foundation of the proposed approach is Raker, which utilizes Random Features (RF) to approximate kernel functions. By mapping input data into a fixed-dimensional space, Raker transforms complex non-linear tasks into linear ones that can be solved efficiently using gradient descent. To enhance performance, the authors use an orthogonality-promoting RF variant that reduces approximation variance.
AdaRaker: Adapting to Change
To handle non-stationary environments, AdaRaker maintains an ensemble of Raker instances, each configured with a different learning rate. These instances act as "experts" operating over various time intervals. A master algorithm aggregates their predictions, dynamically shifting weight toward the most accurate experts. This allows AdaRaker to automatically transition between fast learning (to catch abrupt changes) and slow learning (for fine-tuning during stable periods).
Experimental Evaluation
The performance of AdaRaker was evaluated using four real-world benchmark datasets from the UCI repository: Twitter topic activity, Tom’s Hardware forum discussions, household energy efficiency, and air quality sensor data. These datasets represent diverse streaming scenarios with varying degrees of non-stationarity.
Key Results
Superior Accuracy and Tracking
AdaRaker consistently outperformed baseline methods, including standard OMKL and single-kernel Raker variants, by achieving the lowest Mean Square Error (MSE). Its ensemble approach proved particularly effective at tracking abrupt shifts in data patterns that caused other algorithms to lag or diverge.
Computational Efficiency
A critical advantage of AdaRaker is its scalability. By avoiding the construction of full kernel matrices, it achieves significant speedups. Experimental results indicate that AdaRaker's normalized runtime is approximately 20% of that required by traditional adaptive MKL (AdaMKL) approaches, making it a viable candidate for high-velocity streaming applications.
Conclusion
AdaRaker provides a robust and efficient framework for online non-linear learning in dynamic environments. By leveraging the speed of Random Features and the adaptability of multi-rate ensembles, it overcomes the traditional limitations of kernel methods. Future research directions include automating the selection of kernel dictionaries and further optimizing hyperparameter tuning for specific domains.
Summary updated