Abstract
In contrast to offline kernel selection, online kernel selection must rise to the new challenges of passing the training set once, selecting optimal kernels and updating hypotheses at each round, enjoying a sublinear regret bound for online kernel learning, and requiring a constant maintenance time complexity at each round and an efficient overall time complexity integrated with online kernel learning. However, most of existing online kernel selection approaches can not meet the new challenges. To address this issue, we propose a novel online kernel selection approach via the incremental sketched kernel alignment criterion, which meets all the new challenges. We first define the incremental sketched kernel alignment (ISKA) criterion, which estimates the kernel alignment and can be computed incrementally and efficiently. When applying the proposed ISKA criterion to online kernel selection, we adopt the subclass coherence to maintain the hypothesis space, select the optimal kernel at each round using the median of the ISKA criterion estimates, and update the hypothesis following the online gradient decent method. We prove that the ISKA criterion is an unbiased estimate of the maximum mean discrepancy, enjoys the optimal logarithmic regret bound for online kernel learning, and has a constant maintenance time complexity at each round and a logarithmic overall time complexity integrated with online kernel learning. Empirical studies demonstrate that the proposed online kernel selection approach is computationally efficient while maintaining comparable accuracy for online kernel learning.
Introduction
Choosing an appropriate kernel function—the measure of similarity between data points—is a critical step in kernel-based machine learning. While offline selection via cross-validation is standard, the online setting presents unique challenges: data arrives in a continuous stream, each point is seen only once, and the model must update both its kernel choice and its predictions in real-time. Traditional methods often suffer from the "curse of kernelization," where model complexity grows linearly with data size, leading to prohibitive computational costs. This paper introduces Incremental Sketched Kernel Alignment (ISKA), a novel approach that addresses these efficiency and theoretical gaps.
Methodology
The proposed OKS-ISKA algorithm integrates three key components to achieve efficient and accurate online learning:
1. Incremental Sketched Kernel Alignment (ISKA)
The core of the method is the ISKA criterion, which estimates kernel alignment using a "sketch"—a small, representative buffer of positive and negative examples. Unlike standard alignment metrics that require the full kernel matrix, ISKA can be updated incrementally as new data points arrive or old ones are removed. Mathematically, the authors prove that ISKA is an unbiased estimate of the Maximum Mean Discrepancy (MMD), providing a rigorous statistical foundation for the selection process.
2. Subclass Coherence (SC)
To manage model complexity, OKS-ISKA employs a budget-constrained buffer. The algorithm uses "Subclass Coherence" to identify redundant data points. If a new example is highly similar to existing points in the buffer (exceeding a coherence threshold $\mu$), it is discarded to keep the hypothesis space compact. If the buffer is full, the point with the least contribution is removed.
3. Median Estimation for Robustness
To ensure the kernel selection is robust to noise and transient fluctuations in the data stream, the algorithm selects the kernel that maximizes the median ISKA score over a sliding window of the most recent $q$ rounds. This prevents erratic switching between kernels based on single outliers.
Experimental Evaluation
The authors evaluated OKS-ISKA against several state-of-the-art methods, including OKS, OKL-GD, and Proj-KA, across various benchmark datasets.
Accuracy and Mistake Rates
On the splice dataset, OKS-ISKA significantly outperformed its competitors in terms of prediction accuracy. As shown in the figure below, the average mistake rate for OKS-ISKA stabilizes at a much lower level (~23%) compared to other adaptive methods.
Computational Efficiency
A major advantage of OKS-ISKA is its scalability. By maintaining a fixed-size buffer $B$, the maintenance time per round remains constant. The following figure illustrates the average runtime on the splice dataset. While OKS-ISKA has a slightly higher initial overhead, its runtime grows much more slowly than OKS and OKL-GD, making it far more suitable for large-scale streaming applications.
Theoretical Contributions
Beyond empirical success, the paper provides strong theoretical guarantees:
- Logarithmic Regret: OKS-ISKA achieves an $O(\ln T)$ regret bound, which is the gold standard for strongly convex online learning problems.
- Complexity: The algorithm ensures a constant maintenance time complexity per round ($O(B)$) and an efficient overall time complexity when integrated with online kernel learning.
Conclusion
OKS-ISKA provides a robust and efficient framework for online kernel selection. By combining incremental sketching with subclass coherence, it overcomes the computational bottlenecks of traditional kernel methods while maintaining superior accuracy and providing strong theoretical guarantees. Future work may explore extending this framework beyond Gaussian kernels and automating the selection of the candidate kernel set.
Summary updated