Kernel methods are the non-parametric workhorses of machine learning, capable of capturing intricate, non-linear patterns by implicitly mapping data into infinite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). However, this expressive power comes with a severe computational penalty known as the curse of kernelization.
According to the classical Representer Theorem, the optimal non-parametric model is expressed as a linear combination of kernel evaluations centered at every single observed data point. In an online or streaming setting where data arrives continuously over $T$ time steps, this means the model's size grows linearly with $T$. Consequently, computing a single prediction scales as $O(T)$, and performing exact second-order updates explodes to $O(T^2)$ or $O(T^3)$. In real-time applications or resource-constrained environments, this unbounded growth is fatal.
To bypass this bottleneck, a powerful paradigm has emerged: adaptive dictionary maintenance. Instead of memorizing every observation, these algorithms dynamically construct a compact, representative subset of data points—a dictionary (or set of basis vectors)—that spans a sufficient subspace of the RKHS. By filtering out redundant data and updating the model using only the most informative points, they achieve sublinear computational complexity while preserving near-optimal accuracy.
The Geometry of Novelty: Approximate Linear Dependence
The earliest and most intuitive way to maintain a sparse dictionary is through geometric filtering. When a new data point $x_t$ arrives, we must decide if it offers enough unique information to justify the memory cost of adding it to our dictionary $\mathcal{D}$.
Geometrically, we can project the feature-mapped point $\phi(x_t)$ onto the linear subspace spanned by the current dictionary elements in the RKHS. If the squared projection error (the distance between the true feature vector and its projection) falls below a predefined threshold $\nu$, the point is considered Approximately Linearly Dependent (ALD).
RKHS Subspace spanned by Dictionary D
=====================================
^
| \ <- Projection Error (Distance)
| v
-------+-------* $\phi(x_t)$ [New Point]
|
If the error is small, the point is redundant. The algorithm updates the model's weights by projecting the new information onto the existing dictionary elements and then discards the raw sample. If the error exceeds $\nu$, the point is deemed "novel" and appended to the dictionary, expanding the basis.
This geometric approach has been successfully adapted across several domains:
- Gaussian Processes: Lehel Csató and Manfred Opper pioneered this in Sparse Representation for Gaussian Process Models, using a novelty threshold to maintain a fixed-size set of basis vectors, allowing GPs to scale to large datasets without losing their probabilistic confidence intervals.
- Vector Quantization: Matthieu Geist et al. leveraged ALD in Kernelizing Vector Quantization Algorithms to track prototypes in complex, non-linear feature spaces.
- Dimensionality Reduction: In Online kernel sliced inverse regression, Jianjun Xu et al. applied ALD to keep the dictionary size bounded while performing real-time dimension reduction on streaming data.
- Signal Processing: For complex-valued signals, Pantelis Bouboulis and Sergios Theodoridis in The Complex Gaussian Kernel LMS algorithm, alongside Rafael Boloix-Tortosa et al. in The Generalized Complex Kernel Least-Mean-Square Algorithm, combined spatial distance and prediction error as a unified novelty criterion, preventing infinite memory growth during adaptive signal regression.
Statistical Sparsification: Ridge Leverage Scores
While geometric novelty works well in stationary environments, it lacks strong theoretical guarantees when data streams are non-stationary or adversarial. To handle these harsher conditions, modern online kernel learning relies on a statistical measure of importance: Ridge Leverage Scores (RLS).
The ridge leverage score of a data point measures its statistical influence on a regularized linear model. In the context of kernel matrices, a point's leverage score quantifies how unique its variance is relative to the rest of the dataset. If a point lies in a direction where many other points have already been observed, its leverage score will be low. If it points in a novel direction, its score will be high.
By treating approximate leverage scores as probabilities, algorithms can perform online Nyström sampling. Instead of keeping every point, the algorithm flips a biased coin for each incoming sample: points with high leverage scores are highly likely to be added to the dictionary, while points with low leverage scores are safely ignored.
This mechanism fundamentally changes the scaling laws of online kernel learning:
- Breaking the Curse: In Efficient Second-Order Online Kernel Learning with Adaptive Embedding and Second-Order Kernel Online Convex Optimization with Adaptive Sketching, Daniele Calandriello et al. demonstrated that RLS-based adaptive sketching bounds the dictionary size by the effective dimension ($d_{\text{eff}}$) of the dataset rather than the time horizon $T$. This allows second-order methods to achieve optimal, fast logarithmic regret with nearly linear time complexity.
- Adversarial Robustness: Rémi Jézéquel et al. proved in Efficient online learning with kernels for adversarial large scale problems that this leverage-score-driven dictionary maintenance maintains theoretical optimality even when the data stream is chosen adversarially.
- Contextual Bandits: In decision-making under uncertainty, Houssam Zenati et al. introduced EK-UCB in Efficient Kernelized UCB for Contextual Bandits, utilizing leverage scores to slash the computational complexity of kernelized bandit exploration from a prohibitive $O(T^3)$ to a highly scalable $O(T d_{\text{eff}}^2)$.
Seamless Expansion: Incremental Matrix Updates
Deciding which points to add to the dictionary is only half the battle; the other half is updating the model's internal state without recomputing expensive matrix inversions from scratch. When a point passes the novelty or leverage score filter, the underlying feature space effectively expands by one dimension.
To handle this expansion seamlessly, researchers design incremental projection and factorization-free update schemes. For instance, Junfan Li and Shizhong Liao developed an incremental projection scheme in Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression. When a new basis element is identified, their method updates the existing covariance matrices and model parameters locally, preserving all prior information without requiring a full model restart.
Similarly, in the unsupervised domain, Yi Wang 0037 et al. proposed FKDA in Fast Factorization-free Kernel Learning for Unlabeled Chunk Data Streams. By treating newly detected data categories as orthogonal basis vectors, the authors expand the feature space's dimensionality locally. This avoids expensive global matrix factorizations (like SVD or QR decompositions) and ensures that the coordinates of previously learned classes remain perfectly stable during incremental updates.
Broadening the Paradigm
The strategy of adaptive dictionary maintenance has expanded far beyond simple regression, serving as a foundational mechanism for a wide variety of complex, streaming applications:
Distributed and Asynchronous Bandits
In collaborative environments, multiple agents learn a shared non-linear reward function. Sharing raw data streams is communication-heavy and compromises privacy. By leveraging RLS-guided Nyström sampling, Chuanhao Li et al. developed algorithms like Approx-DisKernelUCB (Communication Efficient Distributed Learning for Kernelized Contextual Bandits) and Async-KernelUCB (Learning Kernelized Contextual Bandits in a Distributed and Asynchronous Environment). Agents only synchronize their compact, sketched dictionaries, achieving sublinear communication costs and preventing slow clients ("stragglers") from bottlenecking the global system.
Graph Topology Identification
Tracking the evolving structure of complex networks in real-time requires identifying non-linear relationships on the fly. In Online Kernel-Based Graph Topology Identification with Partial-Derivative-Imposed Sparsity, Mircea Moscu et al. combined a kernel dictionary sparsification condition with partial-derivative penalties, keeping the active set of kernel functions manageable while accurately inferring network topologies from streaming data.
Subspace Clustering
For high-dimensional data streams that lie on low-dimensional subspaces, Wentao Qu et al. introduced an online clustering method in Fast online ℓ0 elastic net subspace clustering via a novel dictionary update strategy. Their approach maintains a dictionary of "support points"—a carefully curated subset of data points that best represent the underlying data distribution—allowing the model to adapt dynamically to shifting cluster characteristics without reprocessing historical data.
Summary
Adaptive dictionary maintenance reconciles the infinite-dimensional expressivity of kernel methods with the finite constraints of real-time computing. Whether through geometric novelty checks (ALD) or statistical importance sampling (Ridge Leverage Scores), the core intuition remains identical: identify and retain only the data points that expand the model's understanding of the feature space geometry. By filtering out redundant information at the door, these methods bound computational complexity to the intrinsic difficulty of the data stream, transforming kernel methods from expensive batch algorithms into agile, streaming-ready predictors.
Key Foundational Work
Kernelizing Vector Quantization Algorithms (2009) — contributed 1 concept elements to this direction.
Sparse Representation for Gaussian Process Models (2000) — contributed 1 concept elements to this direction.