Abstract
We develop a general non-asymptotic analysis of learning rates in kernel ridge regression (KRR), applicable for arbitrary Mercer kernels with multi-dimensional support. Our analysis is based on an operator-theoretic framework, at the core of which lies two error bounds under reproducing kernel Hilbert space norms encompassing a general class of kernels and regression functions, with remarkable extensibility to various inferential goals through augmenting results. When applied to KRR estimators, our analysis leads to error bounds under the stronger supremum norm, in addition to the commonly studied weighted $L_2$ norm; in a concrete example specialized to the Matern kernel, the established bounds recover the nearly minimax optimal rates. The wide applicability of our analysis is further demonstrated through two new theoretical results: (1) non-asymptotic learning rates for mixed partial derivatives of KRR estimators, and (2) a non-asymptotic characterization of the posterior variances of Gaussian processes, which corresponds to uncertainty quantification in kernel methods and nonparametric Bayes.
Introduction
Kernel Ridge Regression (KRR) is a cornerstone of nonparametric statistics and machine learning, valued for its flexibility and closed-form solutions. However, much of the existing theoretical literature focuses on asymptotic behavior or average-case performance ($L_2$ norms). This paper provides a rigorous non-asymptotic foundation for KRR, offering error bounds that hold for finite sample sizes and extend to the estimation of derivatives—a task critical in fields ranging from robotics to cosmology.
A Unified Operator-Theoretic Framework
The core contribution of this work is a general framework for analyzing KRR using operator theory. By examining the properties of Mercer kernels on multi-dimensional support, the authors derive error bounds within Reproducing Kernel Hilbert Space (RKHS) norms.
Unlike traditional analyses that often rely on specific kernel geometries, this approach is remarkably extensible. It allows for the derivation of bounds not only in the standard weighted $L_2$ norm but also in the much stronger supremum ($L_\infty$) norm. This ensures that the KRR estimate is accurate across the entire domain, rather than just on average, which is vital for applications requiring high precision at every point.
The "Plug-in" Property for Derivative Estimation
A particularly elegant result of this analysis concerns the estimation of mixed partial derivatives. Traditionally, estimating derivatives (e.g., velocity or acceleration from position data) requires separate tuning for each derivative order. For instance, methods like smoothing splines or local polynomial regression often require different smoothing parameters ($\lambda$) for the function and its second derivative.
The authors demonstrate a "plug-in property" for KRR: a standard KRR estimator, once trained to fit the function, can be differentiated directly to estimate its derivatives. Crucially, the same regularization parameter $\lambda$ that is optimal for the regression function remains nearly minimax optimal for all its derivatives simultaneously. This significantly simplifies the implementation of derivative estimation in practice.
Key Theoretical Results
Minimax Optimality and the Matérn Kernel
To demonstrate the power of their framework, the authors apply it to the Matérn kernel, a popular choice in spatial statistics and Gaussian process modeling. They show that the established non-asymptotic bounds recover nearly minimax optimal rates. For a function with smoothness $\alpha$, the $L_2$ error for the $m$-th derivative scales approximately as $n^{-(\alpha-m)/(2\alpha+1)}$, where $n$ is the sample size.
Uncertainty Quantification
The framework also provides a non-asymptotic characterization of the posterior variances of Gaussian processes (GPs). This result bridges the gap between frequentist kernel methods and Bayesian nonparametric inference, providing a theoretical basis for uncertainty quantification in GP-based models.
Empirical Validation
The theoretical findings are supported by simulations comparing KRR against established baselines, including local polynomial regression (locpol), penalized smoothing splines (pspline), and locally weighted least squares (LowLSR).
- Performance in High Orders: In scenarios involving complex, "wiggly" synthetic functions, KRR (particularly with the Matérn kernel) demonstrated superior stability. While the performance of splines often degraded rapidly as the derivative order increased (e.g., 3rd-order derivatives), the KRR estimator remained robust.
- Boundary Robustness: KRR handles data edges more gracefully than difference-based methods, which often suffer from significant "boundary effects" unless specifically corrected.
- Practical Tuning: The authors show that Maximum Marginal Likelihood Estimation (MMLE) serves as an effective, data-driven method for selecting the tuning parameter $\lambda$ in practice, further enhancing the method's utility.
Conclusion
This research provides a powerful set of tools for understanding and applying Kernel Ridge Regression. By establishing non-asymptotic bounds in strong norms and proving the optimality of the plug-in derivative estimator, the paper simplifies the workflow for researchers needing to extract rates of change from noisy data. The framework's ability to characterize GP posterior variance further solidifies the theoretical link between kernel methods and Bayesian inference.
Summary updated