April 24, 2022 Machine Learning

Improving kernel online learning with a snapshot memory

  • 04 minutes
  • Trung Le, Khanh Nguyen, Dinh Phung

  • Machine Learning Journal 2022
Share

Abstract

We propose in this paper the Stochastic Variance-reduced Gradient Descent for Kernel Online Learning (DualSVRG), which obtains the 𝜀ε-approximate linear convergence rate and is not vulnerable to the curse of kernelization. Our approach uses a variance reduction technique to reduce the variance when estimating full gradient, and further exploits recent work in dual space gradient descent for online learning to achieve model optimality. This is achieved by introducing the concept of an instant memory, which is a snapshot storing the most recent incoming data instances and proposing three transformer oracles, namely budget, coverage, and always-move oracles. We further develop rigorous theoretical analysis to demonstrate that our proposed approach can obtain the 𝜀ε-approximate linear convergence rate, while maintaining model sparsity, hence encourages fast training. We conduct extensive experiments on several benchmark datasets to compare our DualSVRG with state-of-the-art baselines in both batch and online settings. The experimental results show that our DualSVRG yields superior predictive performance, while spending comparable training time with baselines.

Bibtex

@article{le2022improving,
title={Improving kernel online learning with a snapshot memory},
author={Le, Trung and Nguyen, Khanh and Phung, Dinh},
journal={Machine Learning},
pages={1–22},
year={2022},
publisher={Springer US}
}

Back to Research
  • 04 minutes
  • Trung Le, Khanh Nguyen, Dinh Phung

  • Machine Learning Journal 2022
Share

Related publications