Abstract
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.
Introduction
Online kernel learning (OKL) is essential for processing massive, continuous streams of data where retraining a model from scratch is computationally infeasible. However, traditional OKL faces two major hurdles: the "Curse of Kernelization," where model size grows linearly with the number of data points, and the reliance on static kernel parameters. While Random Fourier Features (RFF) address the first issue by approximating kernels in a fixed finite-dimensional space, they typically rely on fixed kernel parameters (e.g., Gaussian width $\sigma$) determined via expensive offline grid searches.
Methodology: Reparameterized Random Features (RRF)
The core innovation of this work is the Reparameterized Random Feature (RRF) framework. By applying the "reparameterization trick"—a technique popularized in Variational Autoencoders—the authors enable the joint optimization of model weights and kernel parameters.
Instead of sampling random Fourier components $\omega$ directly from a distribution $p(\omega|\sigma)$, they express $\omega$ as a deterministic function of an auxiliary noise variable $e$ and the parameter $\sigma$ (e.g., $\omega = \sigma \odot e$). This shift makes the kernel approximation differentiable with respect to $\sigma$. Consequently, the model can utilize Stochastic Gradient Descent (SGD) to update both the model weights $w$ and the kernel parameters $\sigma$ simultaneously as new data arrives. To ensure numerical stability and keep $\sigma$ positive, the authors parameterize the log-variance $\gamma$ instead.
Experimental Evaluation
The researchers evaluated RRF on seven diverse, large-scale datasets for both classification (e.g., airlines, poker, cod-rna) and regression (casp, slice).
Efficiency and Dimensionality
A key finding is that learning kernel parameters allows for significantly more efficient models. RRF achieves superior performance with far fewer random features than competing methods. For instance, RRF can achieve lower mistake rates at a dimension of $D=20$ than other methods at $D=1,600$.
Performance Benchmarks
RRF consistently outperformed 12 state-of-the-art baselines in both accuracy and speed. On the ijcnn1 dataset, RRF-Hinge achieved a mistake rate of 3.68%, compared to the next best baseline at 8.35%. In terms of computational efficiency, RRF demonstrated dramatic speedups; on the cod-rna dataset, it was approximately 133x faster than standard Online Gradient Descent (OGD).
Conclusion
RRF successfully bridges the gap between classical kernel methods and modern deep learning optimization. By making random features differentiable, it enables end-to-end online learning that is both accurate and highly efficient. While the joint optimization introduces non-convexity, empirical results demonstrate that SGD effectively finds high-quality solutions. Future work may explore extending this framework to deeper kernel architectures.
Summary updated