Non-asymptotic Analysis of Mat\'ern Regression: The Roles of Target and Kernel Lengthscales

Abstract

Theoretical guarantees for kernel regression are typically formulated in terms of smoothness, but practical accuracy depends critically on how the design resolution compares with the target and kernel lengthscales. We develop a finite-sample theory for Mat\'ern regression on periodic domains with quasi-uniform designs, covering noiseless interpolation and noisy kernel ridge regression. Our minimax result shows that accurate recovery requires a design dense enough to resolve the target lengthscale and sufficient information at that scale to overcome noise. We prove that Mat\'ern interpolation additionally requires the design to resolve the kernel lengthscale: if the kernel is too short relative to the point spacing, an additional error remains even when the target is well resolved. For noisy Mat\'ern regression, we derive a three-term fixed-ridge risk characterization consisting of target-scale bias, kernel-scale bias, and variance, and show that optimizing over the ridge parameter yields four distinct contributions. When the target is no more than twice as smooth as the kernel, choosing a kernel lengthscale longer than the target does not worsen the oracle risk, whereas choosing one too short can. Thus these resolution conditions determine when accurate recovery becomes possible, while smoothness determines how rapidly the error decreases thereafter.