Nonlinear Online Learning with Adaptive Nyström Approximation
This work addresses a problem for online learning practitioners by enabling efficient nonlinear kernel approximation in streaming data scenarios, though it is incremental as it builds on existing Nyström methods.
The paper tackles the challenge of applying improved Nyström approximation methods to online learning by proposing an adaptive approach that modifies landmark points via online k-means and adjusts the model with least squares and gradient descent, resulting in an algorithm that outperforms state-of-the-art methods under the same budget.
Use of nonlinear feature maps via kernel approximation has led to success in many online learning tasks. As a popular kernel approximation method, Nyström approximation, has been well investigated, and various landmark points selection methods have been proposed to improve the approximation quality. However, these improved Nyström methods cannot be directly applied to the online learning setting as they need to access the entire dataset to learn the landmark points, while we need to update model on-the-fly in the online setting. To address this challenge, we propose Adaptive Nyström approximation for solving nonlinear online learning problems. The key idea is to adaptively modify the landmark points via online kmeans and adjust the model accordingly via solving least square problem followed by a gradient descent step. We show that the resulting algorithm outperforms state-of-the-art online learning methods under the same budget.