Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding

Conditionally positive definite (CPD) kernels are defined with respect to a function class $\mathcal{F}$. It is well known that such a kernel $K$ is associated with its native space (defined analogously to an RKHS), which in turn gives rise to a learning method --- called conditional kernel ridge regression (conditional KRR) due to its analogy with KRR --- where the estimated regression function is penalized by the square of its native space norm. This method is of interest because it can be viewed as classical linear regression, with features specified by $\mathcal{F}$, followed by the application of standard KRR to the residual (unexplained) component of the target variable. Methods of this type have recently attracted increasing attention. We study the statistical properties of this method by reducing its behavior to that of KRR with another fixed kernel, called the residual kernel. Our main theoretical result shows that such a reduction is indeed possible, at the cost of an additional term in the expected test risk, bounded by $\mathcal{O}(1/\sqrt{N})$, where $N$ is the sample size and the hidden constant depends on the class $\mathcal{F}$ and the input distribution. This reduction enables us to analyze conditional KRR in the case where $K$ is positive definite and $\mathcal{F}$ is given by the first $k$ principal eigenfunctions in the Mercer decomposition of $K$. We also consider the setting where $\mathcal{F}$ consists of $k$ random features from a random feature representation of $K$. It turns out that these two settings are closely related. Both our theoretical analysis and experiments confirm that conditional KRR outperforms standard KRR in these cases whenever the $\mathcal{F}$-component of the regression function is more pronounced than the residual part.

Modern machine learning methods often rely on kernels, which are mathematical tools used to measure similarity between data points. Kernel Ridge Regression (KRR) is one such method and is widely used in areas ranging from neural network theory to scientific computing. In this paper, we study a more flexible version of KRR that allows some important patterns in the data to remain ``unpenalized'' during learning. Intuitively, the method first captures simple or structured components of the signal, and then applies standard kernel learning only to the remaining unexplained part. We develop a theoretical framework explaining why this approach can improve prediction accuracy. In particular, we show that when the main structure of the target signal aligns with the chosen unpenalized features, the method can outperform standard KRR. We analyze several settings, including principal component thresholding and random feature models, and provide experiments on synthetic data and MNIST digit classification that support our theory. Our results help clarify how combining explicit features with kernel methods can lead to more effective and interpretable learning algorithms.