Kernel methods are the heavy hitters of non-linear learning, prized for their ability to map simple data into high-dimensional Reproducing Kernel Hilbert Spaces (RKHS) where complex patterns become linearly separable. However, they harbor a fundamental flaw for streaming data: the curse of kernelization.
In a standard online setting, the Representer Theorem implies that the optimal solution is a linear combination of all previously observed data points. As Lijun Zhang and Rong Jin noted in Online Kernel Learning with a Near Optimal Sparsity Bound, this causes the model's memory footprint to grow linearly with time. For a robot learning in the wild or a sensor network monitoring a continuous stream, this "memory explosion" eventually leads to hardware exhaustion and prohibitive latency.
The research direction of Parsimonious Online Kernel Learning seeks to break this linear dependency, allowing models to maintain high accuracy while strictly bounding their computational and memory costs.
The Geometry of Forgetting
The core intuition behind parsimonious learning is that not all data points are equally informative. In the high-dimensional feature space of a kernel, many points are redundant—they can be closely approximated by a linear combination of other points already in the model's "dictionary."
To exploit this, researchers like Alec Koppel and Amrit Bedi developed algorithms like POLK (Parsimonious Online Learning with Kernels) and DynaPOLK (Nonstationary Nonparametric Online Learning). These methods use greedy subspace projections. Instead of simply adding every new error to the model, the algorithm checks if the new information can be projected onto the span of the existing support vectors. If the projection error is small, the model is updated without increasing its size. If the model must grow, a subsequent pruning step removes the least significant "centers" to keep the total count within a fixed budget.
Budgeting and Randomized Pruning
A simpler but highly effective approach is to enforce a hard "budget" on the number of support vectors. Steven Hoi and Peilin Zhao pioneered this with BOGD (Fast Bounded Online Gradient Descent). When the budget is reached, the algorithm must decide which support vector to discard.
While one might intuitively try to remove the "oldest" or "weakest" point, Giovanni Cavallanti and Nicolò Cesa-Bianchi demonstrated in Tracking the best hyperplane with a simple budget Perceptron that even randomized deletion can be theoretically optimal. By randomly discarding a support vector when the memory is full, the model effectively "samples" the underlying distribution, maintaining a representative sketch of the decision boundary without the overhead of complex geometric calculations.
From Points to Features: Functional Approximation
Another way to bypass the memory explosion is to stop storing data points (the "dual" approach) and instead approximate the kernel function itself (the "primal" approach).
In Large Scale Online Kernel Classification, Steven Hoi and colleagues utilize Random Fourier Features (RFF). RFF maps the input data into a fixed-dimensional randomized feature space where the inner product approximates the desired kernel. This transforms the non-parametric kernel problem into a parametric linear problem. Because the feature space size is fixed upfront, the memory requirement remains constant regardless of how many millions of data points the model processes.
Similarly, Daniele Calandriello introduced Sketched-KONS (Second-Order Kernel Online Convex Optimization with Adaptive Sketching), which uses ridge leverage scores to adaptively sketch the kernel matrix. This ensures that the model only retains data points that are "statistically novel," allowing second-order methods (which are usually computationally ruinous) to run in nearly linear time.
Why It Works: The Information Bottleneck
The success of these methods rests on the realization that the "information density" of a data stream is often much lower than the raw number of samples.
- Redundancy: In many tasks, data points cluster together. Badong Chen and Lu Lu showed that quantization—merging new points into existing nearby centers—can keep the model compact without losing the "shape" of the data (Variable-mixing parameter quantized kernel robust mixed-norm algorithms).
- Kernel Alignment: If the chosen kernel is well-suited to the data, the underlying function can be represented by very few points. Junfan Li and Shizhong Liao proved in Learnability in Online Kernel Selection with Memory Constraint that if "kernel alignment" is high, we can achieve sub-linear regret with as little as $O(\ln T)$ memory.
By treating memory as a constrained resource rather than an infinite pool, parsimonious kernel learning enables the deployment of powerful non-linear models in real-time, resource-constrained environments like robotics (Federico Ceola et al., Fast Region Proposal Learning) and distributed sensor networks (Pantelis Bouboulis, Online Distributed Learning).