Abstract
Online kernel selection in continuous kernel space is significantly more complex than selection from discrete kernel sets. Existing approaches often suffer from linear computational complexities per round and lack sublinear regret guarantees. We propose a novel hypothesis sketching approach for online kernel selection in continuous spaces that maintains constant computational complexity per round while achieving a sublinear regret bound of $O(\sqrt{T})$. By maintaining the orthogonality of basis functions and utilizing a weight compensation strategy, our method, OKS-SIL (Online Kernel Selection via Sketched Instantaneous Loss), significantly improves efficiency without sacrificing predictive accuracy.
Introduction
Online Kernel Learning (OKL) is a robust framework for learning non-linear patterns from data streams. However, its effectiveness is heavily dependent on the choice of the kernel function. Traditional methods typically rely on a pre-selected kernel or select from a small, discrete set of candidates. This leads to two primary limitations:
- The Discrete Limitation: Pre-defined discrete sets may miss the optimal kernel parameter residing in a continuous space.
- The Curse of Kernelization: Many continuous selection methods have computational costs that grow linearly with the number of rounds $T$, making them unsuitable for high-velocity or long-term online applications.
Our work addresses these gaps by navigating an infinite continuous kernel space with constant time and memory requirements per round.
Methodology: OKS-SIL
The core of our approach is the OKS-SIL framework, which utilizes hypothesis sketching to maintain a fixed-size model under a computational budget $B$.
Basis Function Sketching
To prevent the model size from growing indefinitely, we employ a Randomized Linear Dependency (RLD) condition. This condition ensures that the basis functions in the sketch remain approximately orthogonal. When the budget is reached, the algorithm evaluates if a new data point is sufficiently "independent" from a random subset of existing points. If so, it replaces the least significant basis function, ensuring the sketch captures the most informative data.
Weight Compensation Strategy
Simply discarding data points leads to information loss. OKS-SIL uses a compensation strategy based on the RLD condition to update the weights of remaining basis functions. This preserves the predictive power of the hypothesis even as the underlying basis changes, effectively "compressing" the discarded information into the remaining sketch.
Continuous Parameter Optimization
Unlike discrete selection, OKS-SIL treats kernel parameters (e.g., the width of a Gaussian kernel) as continuous variables. We perform online gradient descent on the Sketched Instantaneous Loss (SIL) to iteratively refine the kernel parameter toward its optimal value at every step.
Theoretical Guarantees and Results
We prove that OKS-SIL achieves a regret bound of $O(\sqrt{T})$, which is theoretically optimal for convex loss functions in online learning. Crucially, it reduces the per-round computational complexity from $O(T)$ to $O(B)$, where $B$ is the fixed budget.
Experimental evaluation on standard benchmark datasets (such as cod-rna and ijcnn1) confirms these gains. OKS-SIL was significantly faster than discrete OKS methods—for instance, completing the cod-rna task in ~89 seconds compared to over 1,786 seconds for the baseline.
Impact of Budget $B$
The performance of OKS-SIL is robust to the choice of budget $B$. As shown in the figures below, increasing the budget beyond a certain threshold (typically 100-200) yields diminishing returns in accuracy, while the runtime remains predictable and controlled by $B$.
Conclusion
Hypothesis sketching provides a scalable and theoretically sound framework for online kernel selection in continuous spaces. By combining RLD-based sketching with weight compensation, OKS-SIL overcomes the "curse of kernelization" while maintaining high predictive accuracy. This mechanism could potentially be extended to broader online model selection problems across different architectures.
Summary updated