Overcoming Model Growth in Online Kernel Learning

144 concepts116 papers1 proposal

Kernel methods are celebrated for their ability to capture complex, non-linear relationships by implicitly mapping data into an infinite-dimensional Reproducing Kernel Hilbert Space (RKHS). However, this expressive power comes with a severe hidden cost when applied to streaming data.

In a standard linear online learning model, the parameter vector has a fixed dimensionality. In contrast, non-parametric kernel methods rely on the Representer Theorem, which dictates that the learned function $f(x)$ is represented as a linear combination of kernel evaluations centered at previously observed data points:

$$f(x) = \sum_{i=1}^{t} \alpha_i k(x_i, x)$$

As noted by Alec Koppel et al. in Decentralized Online Learning with Kernels and Zhuang Wang et al. in Multi-Class Pegasos on a Budget, every time an online algorithm encounters a new data point or makes a prediction error, it adds a new "support vector" $x_t$ to its internal dictionary.

For an infinite or long-running data stream, this causes the model's memory footprint to grow linearly ($O(t)$) over time. Consequently, computing a single new prediction requires evaluating the kernel against all accumulated historical points, causing the per-step computational cost to scale linearly and the total processing cost over a horizon $T$ to scale quadratically ($O(T^2)$). As Jas Kandola et al. discuss in Online Classification on a Budget and Alejandro D. de la Concha Duarte et al. explain in Online non-parametric likelihood-ratio estimation by Pearson-divergence functional minimization, this "curse of kernelization" inevitably leads to memory exhaustion and computational failure on resource-constrained hardware.

Budget-Driven Pruning and Deletion

The most direct way to counter unbounded model growth is to enforce a strict memory "budget" $B$. When the number of stored support vectors exceeds $B$, the algorithm must decide how to evict or compress old information without destabilizing its predictive performance.

An early foundational approach was introduced by Ofer Dekel in The Forgetron: A Kernel-Based Perceptron on a Fixed Budget. Instead of abruptly deleting old data points, the Forgetron systematically down-scales (or "shrinks") the weights of older support vectors before eventually evicting them. This ensures that the model maintains a strict memory limit while providing formal theoretical guarantees on accuracy.

Alternatively, Giovanni Cavallanti et al. demonstrated a surprisingly simple yet effective strategy in Tracking the best hyperplane with a simple budget Perceptron: when the budget is full, the algorithm randomly discards an old support vector. The authors proved that this randomized strategy is highly effective for tracking targets that change over time. To minimize information loss more deterministically, Zhuang Wang et al. framed support vector removal as a joint optimization problem in Online Passive-Aggressive Algorithms on a Budget, adjusting the remaining weights to compensate for the deleted vector.

Functional Approximation via Random Features

Rather than maintaining a dictionary of raw data points and pruning them post-hoc, a second paradigm shifts the problem entirely by approximating the kernel function itself. By mapping data into a fixed, finite-dimensional feature space, non-parametric kernel learning is effectively transformed into a parametric linear problem.

This approach heavily leverages Random Fourier Features (RFF). As Pantelis Bouboulis et al. demonstrate in Efficient KLMS and KRLS Algorithms: A Random Fourier Feature Perspective, applying RFF to classic algorithms like Kernel Least Mean Square (KLMS) and Kernel Recursive Least Squares (KRLS) bypasses the need for complex dictionary management entirely, keeping the computational cost per iteration strictly constant.

Building on this, Trung Le et al. introduced Reparameterized Random Features (RRF) in Large-scale Online Kernel Learning with Random Feature Reparameterization. By utilizing the reparameterization trick, the authors enabled the model to learn and optimize kernel parameters (such as Gaussian width) on the fly via stochastic gradient descent, achieving high accuracy with a fraction of the memory footprint. As Steven HOI et al. argue in Large Scale Online Kernel Classification, transitioning from explicit support vector tracking to functional approximations like RFF or the Nyström method allows online kernel classification to scale seamlessly to massive datasets.

Incremental Sketching and Sparsification

A third strategy involves maintaining a low-rank "sketch" or compact projection of the data history or hypothesis space as new samples arrive.

Instead of storing every historical point, Francesco Orabona et al. proposed an alternative in On-line Independent Support Vector Machines for Cognitive Systems that evaluates whether a new data point is linearly independent of the existing dictionary in the feature space. If it can be closely approximated by a linear combination of current support vectors, it is discarded, preventing unnecessary model bloat.

For adversarial or highly dynamic environments, Xiao Zhang et al. introduced SkeGD in Incremental Randomized Sketching for Online Kernel Learning. By using an incremental randomized sketching mechanism, the algorithm compresses the streaming data matrix on the fly, ensuring constant update and prediction times. The authors later extended this concept to continuous kernel spaces in Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space, maintaining a fixed-size sketch of the hypothesis space to dynamically select the optimal kernel width in real time.

The Regret-Memory Trade-off

The ultimate goal of these budget and approximation strategies is to break the linear dependency of memory on time ($O(T)$) while preserving sublinear regret—meaning the online model's cumulative performance loss compared to the best fixed offline model approaches zero over time.

Theoretical insights have shown that a massive memory footprint is not always a prerequisite for accurate learning. For instance, Junfan Li et al. proved in Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis that if the chosen kernel aligns well with the underlying data distribution, sublinear regret is achievable even with a highly constrained memory budget scaling as low as $O(\ln T)$. By balancing geometric data alignment with smart budget-clearing strategies, modern online kernel learning algorithms can achieve optimal regret bounds while operating within strictly bounded physical resources.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 122 papers
  2. Version 1 · 2026-10-04 · 145 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_kernelization_1c4b3729,
  title = {curse of kernelization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-kernelization/rdr_1c4b3729bbd44ee8b4d54a1b7d4704c3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_curse_of_kernelization_1c4b3729_v2,
  title = {curse of kernelization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-kernelization/rdr_1c4b3729bbd44ee8b4d54a1b7d4704c3/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake