Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space

Xiao Zhang, Shizhong LiaoIJCAI 2020 · OpenReview

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:

  1. The Discrete Limitation: Pre-defined discrete sets may miss the optimal kernel parameter residing in a continuous space.
  2. 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$.

Figure 1: Average mistake rate vs. number of examples for different budget sizes B. Accuracy stabilizes quickly as B increases, justifying the sketching approach.
Figure 2: Average runtime vs. number of examples for different budget sizes B. The linear slopes indicate that the per-round complexity remains constant.

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

Abstract

Online kernel selection in continuous kernel space is more complex than that in discrete kernel set. But existing online kernel selection approaches for continuous kernel spaces have linear computational complexities at each round with respect to the current number of rounds and lack sublinear regret guarantees due to the continuously many candidate kernels. To address these issues, we propose a novel hypothesis sketching approach to online kernel selection in continuous kernel space, which has constant computational complexities at each round and enjoys a sublinear regret bound. The main idea of the proposed hypothesis sketching approach is to maintain the orthogonality of the basis functions and the prediction accuracy of the hypothesis sketches in a time-varying reproducing kernel Hilbert space. We first present an efficient dependency condition to maintain the basis functions of the hypothesis sketches under a computational budget. Then we update the weights and the optimal kernels by minimizing the instantaneous loss of the hypothesis sketches using the online gradient descent with a compensation strategy. We prove that the proposed hypothesis sketching approach enjoys a regret bound of order O(√T) for online kernel selection in continuous kernel space, which is optimal for convex loss functions, where T is the number of rounds, and reduces the computational complexities at each round from linear to constant with respect to the number of rounds. Experimental results demonstrate that the proposed hypothesis sketching approach significantly improves the efficiency of online kernel selection in continuous kernel space while retaining comparable predictive accuracies.
BibTeX
@inproceedings{zhang2020hypothesis,
  author = {Xiao Zhang and Shizhong Liao},
  title = {{Hypothesis Sketching for Online Kernel Selection in Continuous Kernel Space}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=r0zaco8YaV},
}
Figure