Large-scale Online Kernel Learning with Random Feature Reparameterization

By Tu Dinh Nguyen, Trung Le, Hung Hai Bui, Dinh Q. Phung. 2017

51 citations recorded by the source corpus.

A typical online kernel learning method faces two fundamental issues: the complexity in dealing with a huge number of observed data points (a.k.a the curse of kernelization) and the difficulty in learning kernel parameters, which often assumed to be fixed. Random Fourier feature is a recent and effective approach to address the former by approximating the shift-invariant kernel function via Bocher's theorem, and allows the model to be maintained directly in the random feature space with a fixed dimension, hence the model size remains constant w.r.t. data size. We further introduce in this paper the reparameterized random feature (RRF), a random feature framework for large-scale online kernel learning to address both aforementioned challenges. Our initial intuition comes from the so-called "reparameterization trick" [Kingma et al., 2014] to lift the source of randomness of Fourier components to another space which can be independently sampled, so that stochastic gradient of the kernel parameters can be analytically derived. We develop a well-founded underlying theory for our method, including a general way to reparameterize the kernel, and a new tighter error bound on the approximation quality. This view further inspires a direct application of stochastic gradient descent for updating our model under an online learning setting. We then conducted extensive experiments on several large-scale datasets where we demonstrate that our work achieves state-of-the-art performance in both learning efficacy and efficiency.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Online Learning: A Comprehensive Survey (2018, methodology): “A recent work, Dual Space Gradient Descent (Le et al., 2016; Nguyen et al., 2017) updates the model as the RBP algorithm, but also builds an FOGD model using the discarded SV’s.”
Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees (2022, unknown): “AMRCs are compared with the state-of-the-art using 12 datasets that have been often used as benchmarks for supervised classification under concept drift (Pavlidis et al., 2011; Kumagai & Iwata, 2016; Lu et al., 2016; Nguyen et al., 2017; Webb et al., 2018): “Weather”, “Elec2”, “Airlines”, “German”, ”