In classical kernel learning theory, we often assume the "best of all worlds": that the target function we are trying to learn resides within the Reproducing Kernel Hilbert Space (RKHS) defined by our chosen kernel. This is the well-specified setting. However, in practice, the real world is rarely so cooperative. The true underlying relationship might be "rougher" or more complex than our kernel can perfectly represent.
Recent theoretical breakthroughs have shown that kernel methods are surprisingly robust to this discrepancy. Even when the model is misspecified—meaning the target function lies outside the RKHS—standard algorithms like Kernel Ridge Regression (KRR) and Gradient Flow still achieve minimax optimal convergence rates. They perform as well as the best possible estimator could, given the actual smoothness of the data.
The Myth of the Perfect Model
For years, a central debate in the community was whether the choice of regularization or the specific hypothesis space fundamentally limited learning when the model was "wrong." Ingo Steinwart, Don Hush, and colleagues addressed this in Optimal Rates for Regularized Least Squares Regression. They proved that the specific exponent used in regularization doesn't actually change the statistical learning rate. More importantly, they showed that regularized least squares can achieve optimal rates even when the target function is outside the hypothesis space, provided the regularization parameter is tuned to balance approximation error (how well we can fit the function) and estimation error (how much noise we pick up).
This robustness extends beyond simple regression. Yaoliang Yu and Csaba Szepesvari demonstrated in Analysis of Kernel Mean Matching under Covariate Shift that kernel-based estimators for covariate shift are robust to these same violations. The error doesn't explode when the target function leaves the RKHS; instead, it degrades gracefully based on the function's actual regularity.
Why It Works: Smoothness and Interpolation
The intuition behind this robustness lies in how spectral algorithms—a family including KRR, Gradient Flow, and Principal Component Regression—interact with the data's eigenvalues.
In On the Optimality of Misspecified Spectral Algorithms, Qian Lin, Haobo Zhang, and Yicheng Li utilized interpolation theory to show that these algorithms adapt to the "roughness" of the target function. Even if a function is potentially unbounded or lacks high-level smoothness, the algorithm's performance is governed by the target's actual smoothness rather than the constraints of the kernel's embedding.
Haobo Zhang and Yicheng Li further solidified this in On the Optimality of Misspecified Kernel Ridge Regression, proving that KRR achieves the information-theoretic lower bound for convergence across all smoothness levels in Sobolev spaces, even under misspecification. Essentially, the algorithm "squeezes" every bit of available information out of the data, regardless of whether the model is a perfect fit.
Scaling Without Losing Optimality
A common critique of kernel methods is their $O(N^3)$ computational complexity. To solve this, researchers use approximations like Nyström sampling, Random Features, or Sketching. A critical question was whether these approximations would break the robustness found in full-scale kernel methods.
The evidence suggests they do not:
- Sketching: Junhong Lin and Volkan Cevher showed in Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces that sketched KRR loses no predictive power in the misspecified setting, provided the sketch dimension is proportional to the data's "effective dimension."
- Nyström: Jian Li and Yong Liu proved in Optimal Convergence Rates for Agnostic Nyström Kernel Learning that low-rank approximations remain minimax optimal even when the target function is outside the RKHS.
- Random Features: Caixing Wang and Xingdong Feng demonstrated similar optimality for kernel quantile regression using random features in Optimal Kernel Quantile Learning with Random Features.
Beyond Scalar Outputs
This robustness isn't limited to simple regression. Zhu Li, Arthur Gretton, and Mattes Mollenhauer extended these results to Conditional Mean Embeddings (CME) and vector-valued outputs. In Optimal Rates for Regularized Conditional Mean Embedding Learning, they proved that CMEs achieve fast $O(1/n)$ learning rates even when the true relationship is infinite-dimensional and misspecified.
Furthermore, Dimitri Meunier and Arthur Gretton noted in Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms that while KRR is robust, it can "saturate"—failing to learn faster even if the data is extremely smooth. They showed that other spectral algorithms, like Principal Component Regression, can bypass this limit to achieve truly optimal rates for highly smooth, misspecified data.
Summary of Intuition
The "magic" of misspecified kernel learning is that regularization acts as a bridge. By tuning the regularization parameter $\lambda$, we effectively control the complexity of our hypothesis. If the target function is rougher than our RKHS, $\lambda$ allows the model to approximate that roughness without needing the function to "live" in the space. Because spectral algorithms naturally prioritize the most informative directions (eigenvectors) of the data, they remain statistically optimal regardless of whether the model's mathematical assumptions are perfectly met.