betaFeedback

WorksMathematics

Training-point consistency of kernel ridge regression with varying correlation scales

Abstract

The scale parameter in kernel ridge regression plays a pivotal role in modeling the correlation structure of data. In modern applications, sampling density and the underlying correlation range often change simultaneously, making a fixed-scale assumption highly restrictive. However, establishing asymptotic theories under varying scale parameters is fundamentally challenging. To address this gap, this paper develops a unified theoretical framework for kernel ridge regression under varying scale parameters. We establish that, on uniform tensor grids with product exponential kernels, the consistency of the training-point risk holds if and only if the effective local sample size diverges to infinity. This sharp criterion universally covers all regimes along arbitrary deterministic scale sequences, seamlessly unifying the long-range, fixed-scale, and short-range. Furthermore, we provide an explicit, signal-independent construction of a deterministic regularization penalty that guarantees this consistency. Numerical experiments illustrate the criterion and the corresponding penalty across all the three regimes.

Introduction

Consider the nonparametric regression model

yi=f(xi)+εi,i=1,…,n,(1)y_i = f(\mathbf{x}_i) + \varepsilon_i, \qquad i = 1,\ldots,n, \tag*{(1)}

where the design points x1,…,xn∈D⊂Rd\mathbf{x}_1,\ldots,\mathbf{x}_n \in D \subset\mathbb{R}^d, DD is a bounded domain, f:D→Rf : D \to\mathbb{R} is the unknown regression function, and ε1,…,εn\varepsilon_1,\ldots,\varepsilon_n are random noises. Kernel ridge regression and Gaussian process regression are fundamental methods for estimating the signal ff in nonparametric statistics [18], machine learning [11], spatial statistics [13], and computer experiments [1]. The two methods combine observations at different sites through a correlation kernel that relies on a range/scale parameter. The scale parameter controls correlation decay: a smaller one makes distant sites more similar, whereas a larger one retains substantial correlation only between near neighbors. Therefore, the estimation performance is highly sensitive to selection of the scale parameter in the kernel [9, 22].

The asymptotic properties of kernel ridge regression and Gaussian process regression have been extensively studied in the literature. Caponnetto and De Vito [4] established optimal rates for regularized least squares under source conditions [4]. Steinwart, Hush, and Scovel [14] derived optimal rates for regularized least squares regression [14]. Dicker, Foster, and Hsu [6] clarified the relation between kernel ridge regression and principal component regression through minimax bounds and regularization qualification [6]. Wang and Jing [19] derived upper and lower error bounds for Gaussian process regression with possibly misspecified correlation functions and established corresponding convergence results for kernel ridge regression with a deterministic target [19]. The posterior asymptotics from the Bayesian perspective were investigated in [15, 16, 17]. However, these studies are all restricted to a fixed scale parameter. As is known, in many scenarios, particularly when the scale parameter is selected using data-driven methods such as cross-validation, the scale parameter (or its reciprocal) is not necessarily bounded [10].

Some studies have investigated the case of varying scale parameters for fixed sample sizes [2, 3, 7]. With a diverging sample size, sampling refinement and kernel scale adjustment can occur simultaneously. Therefore, fixed-domain asymptotics should address changing design density and changing correlation range together. To the best of our knowledge, the asymptotic properties of kernel ridge regression and Gaussian process regression with a varying scale parameter have not yet been systematically studied in the literature.

It is fundamentally challenging to extend the asymptotic properties with fixed scale parameters to varying scales. First, as the scale changes, the kernel matrix undergoes a continuous phase transition from a nearly flat (rank-deficient) structure to an almost diagonal one, rendering classical fixed-kernel spectral tools ineffective. Second, the reproducing kernel Hilbert space (RKHS) norm of a fixed signal depends heavily on the scale, shifting the bias-variance balance dynamically. Third, the simultaneous growth of the sample size and the scale creates a double asymptotic regime governed by the local sample size, where standard empirical process theory struggles to quantify whether local information suffices to offset the noise. Finally, in non-periodic bounded domains, boundary effects are amplified by scale variations and resist Fourier diagonalization. These intertwined challenges necessitate a unified framework that can bridge the long-range, fixed-scale, and short-range regimes.

To overcome these fundamental obstacles, we develop a unified asymptotic framework that fully characterizes the recoverability of signals under varying scale parameters. Our main theorem reveals a sharp phase transition governed entirely by the local sample size: the training-point risk of kernel ridge regression converges to zero if and only if the local sample size goes to infinity. This necessary and sufficient condition is valid for any nonzero signal and any deterministic scale sequence, seamlessly unifying the long-range, fixed-scale, and short-range. Furthermore, we provide a single, signal-independent penalty sequence that realizes this consistency, demonstrating that the bias-variance trade-off can be explicitly balanced across all regimes. The proof circumvents the aforementioned difficulties by combining shape-dependent RKHS norm bounds, an effective dimension estimate via product spectral grouping, and a finite-grid treatment of boundary terms.

The rest of this paper is organized as follows. Section 2 presents the exact risk decomposition and fixed-sample risk with extreme correlation scales. Section 3 establishes the unified framework. Section 4 reports reproducible numerical experiments. Section 5 concludes with discussion. The proofs are given in the Appendix.

Fixed-sample risk with extreme correlation scales

Under the model (1), write fn=(f(x1),…,f(xn)′)\mathbf{f}_n = (f(x_1), \ldots, f(x_n)^{\prime}), abbreviated as f\mathbf{f} when the sample size is clear, y=(y1,…,yn)′\mathbf{y} = (y_1, \ldots, y_n)^{\prime}, and ε=(ε1,…,εn)′\boldsymbol{\varepsilon} = (\varepsilon_1, \ldots, \varepsilon_n)^{\prime}. Let Kθ:D×D→RK_\theta: D \times D \to\mathbb{R} be a positive-semidefinite correlation kernel with a scale parameter θ>0\theta> 0. Here θ\theta controls correlation decay: a smaller θ\theta makes distant sites more similar, whereas a larger θ\theta retains substantial correlation only between near neighbors. The correlation matrix Rθ\mathbf{R}_\theta is defined by (Rθ)ij=Kθ(xi,xj)(\mathbf{R}_\theta)_{ij} = K_\theta(x_i, x_j) for i,j=1,…,ni,j = 1,\ldots,n.

Kernel ridge regression estimates the regression function ff in (1) by solving the optimization problem

min⁡g∈Hθ{∑i=1n(yi−g(xi))2+ρ∥g∥Hθ2}(2)\min_{g\in\mathcal{H}_\theta} \left\{ \sum_{i=1}^{n}(y_i-g(x_i))^2+\rho\lVert g\rVert_{\mathcal{H}_\theta}^2 \right\} \tag*{(2)}

where ρ>0\rho> 0 is a tuning penalty parameter, Hθ\mathcal{H}_\theta is the reproducing kernel Hilbert space (RKHS) induced by the kernel function KθK_\theta, and ∥⋅∥Hθ\lVert\cdot\rVert_{\mathcal{H}_\theta} is the corresponding norm. By (2), the fitted training-point vector is

f^θ,ρ=Rθ(Rθ+ρIn)−1y=:Sθ,ρy.(3)\widehat{\mathbf{f}}_{\theta,\rho}=\mathbf{R}_\theta(\mathbf{R}_\theta+\rho\mathbf{I}_n)^{-1}\mathbf{y}=: \mathbf{S}_{\theta,\rho}\mathbf{y}. \tag*{(3)}

This formula can also be derived from a Bayesian perspective. Under a zero-mean Gaussian prior with covariance τ2Rθ\tau^2\mathbf{R}_\theta and independent Gaussian noise of variance σ2\sigma^2, computing the posterior mean at the training points yields (3) with ρ=σ2/τ2\rho=\sigma^2/\tau^2.

We study the fixed-design training-point risk

Rn(θ,ρ;f)=1nE∥f^θ,ρ−f∥2.(4)\mathcal{R}_n(\theta,\rho;\mathbf{f})=\frac{1}{n}\mathbb{E}\lVert\widehat{\mathbf{f}}_{\theta,\rho}-\mathbf{f}\rVert^2. \tag*{(4)}

Assumption 1. The noise satisfies

Eε=0,E(εε′)=σ2In,0<σ2<∞,\mathbb{E}\boldsymbol{\varepsilon}=0,\qquad\mathbb{E}(\boldsymbol{\varepsilon}\boldsymbol{\varepsilon}^{\prime})=\sigma^{2}\mathbf{I}_{n},\qquad0<\sigma^{2}<\infty,

where In\mathbf{I}_{n} denotes the identity matrix of order nn.

The following theorem presents a bias-variance decomposition of the risk. Let Bn=Bn(θ,ρ;f)B_n=B_n(\theta,\rho;\mathbf{f}) and Vn=Vn(θ,ρ)V_n=V_n(\theta,\rho) denote the bias and variance of the kernel ridge estimator under the fixed-design training-point risk (4), respectively.

Theorem 1. Under Assumption 1,

Rn(θ,ρ;f)=ρ2nf′(Rθ+ρIn)−2f⏟=:Bn(θ,ρ;f)+σ2ntr⁡(Sθ,ρ2)⏟=:Vn(θ,ρ).(5)\mathcal{R}_{n}(\theta,\rho;\mathbf{f})=\underbrace{\frac{\rho^{2}}{n}\mathbf{f}^{\prime}(\mathbf{R}_{\theta}+\rho\mathbf{I}_{n})^{-2}\mathbf{f}}_{=:B_{n}(\theta,\rho;\mathbf{f})}+\underbrace{\frac{\sigma^{2}}{n}\operatorname{tr}(\mathbf{S}_{\theta,\rho}^{2})}_{=:V_{n}(\theta,\rho)}. \tag*{(5)}

We now study the following two extreme cases

Rθ⟶Jn:=1n1n′(θ↓0)andRθ⟶In(θ→∞)\mathbf{R}_{\theta}\longrightarrow\mathbf{J}_{n}:=\mathbf{1}_{n}\mathbf{1}_{n}^{\prime}\quad(\theta\downarrow0)\qquad\text{and}\qquad\mathbf{R}_{\theta}\longrightarrow\mathbf{I}_{n}\quad(\theta\to\infty)

for fixed nn and f\mathbf{f}, where 1n\mathbf{1}_{n} denotes the nn-vector with all elements being one. Write fˉ=n−11n′f\bar{f}=n^{-1}\mathbf{1}_{n}^{\prime}\mathbf{f}, yˉ=n−11n′y\bar{y}=n^{-1}\mathbf{1}_{n}^{\prime}\mathbf{y}, and ∥f∥n2=n−1f′f\lVert\mathbf{f}\rVert_{n}^{2}=n^{-1}\mathbf{f}^{\prime}\mathbf{f}.

Theorem 2. (i) For the long-range correlation case R0=Jn\mathbf{R}_{0}=\mathbf{J}_{n},

inf⁡ρ>0Rn(0,ρ;f)=∥f−fˉ1n∥n2+fˉ2σ2nfˉ2+σ2.\inf_{\rho>0}\mathcal{R}_{n}(0,\rho;\mathbf{f})=\lVert\mathbf{f}-\bar{f}\mathbf{1}_{n}\rVert_{n}^{2}+\frac{\bar{f}^{2}\sigma^{2}}{n\bar{f}^{2}+\sigma^{2}}.

(ii) For the short-range correlation case R∞=In\mathbf{R}_{\infty}=\mathbf{I}_{n}, if f≠0\mathbf{f}\ne0, then

inf⁡ρ>0Rn(∞,ρ;f)=∥f∥n2σ2∥f∥n2+σ2.\inf_{\rho>0}\mathcal{R}_{n}(\infty,\rho;\mathbf{f})=\frac{\lVert\mathbf{f}\rVert_{n}^{2}\sigma^{2}}{\lVert\mathbf{f}\rVert_{n}^{2}+\sigma^{2}}.

Training-point risk consistency with varying correlation scales

Theorem 2 shows that, regardless of the choice of ρ\rho, the risk does not converge to zero for extreme values of θ\theta and fixed nn. This section considers joint asymptotics as nn and θn\theta_n vary simultaneously, and answers whether there exists ρ=ρn\rho=\rho_n such that the risk tends to zero. For convenience, we denote the sample size by NN instead of nn in the following. We introduce the following definition.

Definition 1. Given a scale sequence {θN}N≥1\{\theta_N\}_{N\ge1} and a fixed ff, suppose that there exists a sequence {ρN}N≥1\{\rho_N\}_{N\ge1} such that

RN(θN,ρN;fN)⟶0as N⟶∞.R_N(\theta_N,\rho_N;f_N)\longrightarrow0 \quad\text{as } N\longrightarrow\infty.

We then say that the corresponding kernel ridge estimator has training-point risk consistency with respect to {θN}N≥1\{\theta_N\}_{N\ge1} for ff.

Because the risk is the second moment of the squared training-point error, its convergence to zero is equivalent to convergence of the training-point error in the corresponding L2L_2 space. Markov’s inequality further yields convergence in probability.

In our analysis, the dimension dd is fixed. We need the following assumptions on the design and the correlation function.

Assumption 2. Let D=[0,1]dD=[0,1]^d and N=ndN=n^d with some integer nn. The design points are

xi=in,i=(i1,…,id)∈{1,…,n}d.x_i=\frac{i}{n},\qquad i=(i_1,\ldots,i_d)\in\{1,\ldots,n\}^d.

Assumption 3. For θ>0\theta>0, the correlation function is

Kθ(x,y)=exp⁡{−θ∥x−y∥1}=∏r=1de−θ∣xr−yr∣,x,y∈[0,1]d.K_\theta(x,y)=\exp\{-\theta\|x-y\|_1\}=\prod_{r=1}^{d}e^{-\theta|x_r-y_r|},\qquad x,y\in[0,1]^d.

Under Assumptions 2 and 3, we denote the correlation matrix by R(d)=R(d)(θ)\mathbf{R}^{(d)} = \mathbf{R}^{(d)}(\theta) with

Ri,j(d)(θ)=Kθ(xi,xj)=q∥i−j∥1=∏r=1dq∣ir−jr∣(6)\mathbf{R}^{(d)}_{i,j}(\theta) = K_\theta(\mathbf{x}_i,\mathbf{x}_j) = q^{\lVert i-j\rVert_1} = \prod_{r=1}^{d}q^{|i_r-j_r|} \tag*{(6)}

for i=(i1,…,id),j=(j1,…,jd)∈{1,…,n}di=(i_1,\ldots,i_d),j=(j_1,\ldots,j_d)\in\{1,\ldots,n\}^d, where q=e−θ/nq=e^{-\theta/n}. Thus

R(d)=R1d(θ)⊗dwith(R1d(θ))ij=q∣i−j∣,i,j=1,…,n.(7)\mathbf{R}^{(d)}=\mathbf{R}_{1d}(\theta)^{\otimes d}\quad\text{with}\quad(\mathbf{R}_{1d}(\theta))_{ij}=q^{|i-j|},\quad i,j=1,\ldots,n. \tag*{(7)}

Write

mN=nθN,MN=mNd=NθNd,m_N=\frac{n}{\theta_N},\qquad M_N=m_N^d=\frac{N}{\theta_N^d},

which can be viewed as local sample sizes in one dimension and dd dimension, respectively.

For a multi-index α=(α1,…,αd)′∈{0,1}d\boldsymbol{\alpha}=(\alpha_1,\ldots,\alpha_d)^\prime\in\{0,1\}^d, write ∂α=∂1α1⋯∂dαd\partial^{\boldsymbol{\alpha}}=\partial_1^{\alpha_1}\cdots\partial_d^{\alpha_d}. Let

H1,…,1([0,1]d)={f:∂αf∈L2([0,1]d), α∈{0,1}d},H^{1,\ldots,1}([0,1]^d)=\left\{f:\partial^{\boldsymbol{\alpha}}f\in L_2([0,1]^d),\ \boldsymbol{\alpha}\in\{0,1\}^d\right\},

denote the mixed first-order Sobolev space equipped with the norm

∥f∥1,mix2=∑α∈{0,1}d∥∂αf∥L22.(8)\lVert f\rVert_{1,\mathrm{mix}}^2=\sum_{\boldsymbol{\alpha}\in\{0,1\}^d}\lVert\partial^{\boldsymbol{\alpha}}f\rVert_{L_2}^2. \tag*{(8)}

This space is the reproducing-kernel Hilbert space of the product exponential kernel at a fixed scale, and its elements have continuous representatives. We always take the continuous representative, and grid evaluations and pointwise Riemann sums are well defined.

The following theorem presents the necessary and sufficient condition for training-point risk consistency.

Theorem 3. Under Assumptions 1, 2, and 3, let f∈H1,…,1([0,1]d)f\in H^{1,\ldots,1}([0,1]^d) be fixed and nonzero, and let {θN}N≥1\{\theta_N\}_{N\geq1} be an arbitrary deterministic sequence of positive numbers. The corresponding kernel ridge estimator has training-point risk consistency with respect to {θN}N≥1\{\theta_N\}_{N\geq1} for ff if

and only if

MN=NθNd⟶∞.(9)M_N = \frac{N}{\theta_N^d} \longrightarrow\infty. \tag*{(9)}

More specifically, the following two statements hold.

(i) If MN→∞M_N \to\infty, selecting

ρN={NθNd/log⁡N,θN≤1,MN2/3,θN>1,(10)\rho_N = \begin{cases} N\theta_N^d/\log N, & \theta_N \le1, \\ M_N^{2/3}, & \theta_N > 1, \end{cases} \tag*{(10)}

gives RN(θN,ρN;fN)→0R_N(\theta_N,\rho_N;\boldsymbol{f}_N) \to0.

(ii) If lim inf⁡NMN<∞\liminf_{N} M_N < \infty, then for every deterministic sequence ρN>0\rho_N > 0,

lim sup⁡N→∞RN(θN,ρN;fN)>0.(11)\limsup_{N\to\infty} R_N(\theta_N,\rho_N;\boldsymbol{f}_N) > 0. \tag*{(11)}

This theorem covers all the cases of θN→0\theta_N \to0, fixed or bounded θN\theta_N, and θN→∞\theta_N \to\infty. The two branches of (10) have different orders at θN=1\theta_N = 1. This discontinuity arises from using the long-range spectral estimate and the coarse short-range variance bound on different sides; it serves only the consistency proof and does not represent a discontinuity in an optimal penalty or an optimal risk rate.

In the classical theory on consistency of kernel ridge regression for fixed θ\theta, it is required that ρN→∞\rho_N \to\infty and ρN/N→0\rho_N/N \to0; see, e.g. [4]. Set θN\theta_N to be fixed in Theorem 3, and our ρN\rho_N in (10) satisfies this condition.

Sanz-Alonso [12] gave a scale-consistent risk analysis of Matérn kernel ridge regression on periodic domains with quasi-uniform designs and Sobolev target classes [12]. Its kernel-scale information quantity has the same order as our local effective sample size at fixed dimension and fixed signal-to-noise ratio. Wenzel and Santin [21] studied asymptotically optimal shape parameters for finitely smooth Sobolev kernels and their relation to superconvergence [21]. Their results concern asymptotic approximation rates for noiseless kernel interpolation, whereas we study noisy kernel ridge regression.

Numerical experiments

We now illustrate the theoretical results with numerical examples. Consider the following one-dimensional and two-dimensional test functions,

f1(x)=1+0.4cos⁡(2πx)+0.2x,f_1(x) = 1 + 0.4\cos(2\pi x) + 0.2x,
f2(x1,x2)=1+0.3cos⁡(2πx1)+0.2sin⁡(2πx2)+0.1x1x2,f_2(x_1, x_2) = 1 + 0.3\cos(2\pi x_1) + 0.2\sin(2\pi x_2) + 0.1x_1x_2,

in the regression model (1). For the one-dimensional case, the sample size is set as n∈{64,125,216,343,512,729,1000}n \in\{64, 125, 216, 343, 512, 729, 1000\}. For the two-dimensional case, set n∈{16,20,24,28,32,36,40}n \in\{16, 20, 24, 28, 32, 36, 40\} and N=n2N = n^2, Let σ2=1\sigma^2 = 1 in Assumption 1. Under the grid design in Assumption 2, generate data with normal noises, and compute the kernel ridge estimator with the correlation function in Assumption 3.

For the one-dimensional case, consider the following four cases of the correlation parameter θ\theta in kernel ridge regression: (i) fixed θ=1/2\theta= 1/2, corresponding to the local sample size Mn=2nM_n = 2n; (ii) short range θn=n2/3\theta_n = n^{2/3}, corresponding to Mn=n1/3M_n = n^{1/3}; (iii) long range θn=n−3/2\theta_n = n^{-3/2}, corresponding to Mn=n5/2M_n = n^{5/2}; (iv) too short range θn=n/4\theta_n = n/4, corresponding to bounded local sample size Mn=4M_n = 4. Cases (i)-(iii) satisfy the diverging-local-sample-size condition (9) in Theorem 3, and we use ρn\rho_n in (10). For case (iv) where condition (9) does not hold, we select ρ\rho that yields the minimum value of training-point risk.

For the two-dimensional case, consider the following four cases similarly: (i) fixed θ=1/2\theta= 1/2, corresponding to the local sample size MN=4NM_N = 4N; (ii) short range θN=N1/4\theta_N = N^{1/4}, corresponding to MN=N1/2M_N = N^{1/2}; (iii) long range θN=N−1\theta_N = N^{-1}, corresponding to MN=N3M_N = N^3; (iv) too short range θN=N1/2/4\theta_N = N^{1/2}/4, corresponding to bounded local sample size MN=16M_N = 16. Cases (i)-(iii) satisfy condition (9), while case (iv) does not. We select ρ\rho in the same manner as in the one-dimensional case.

We compute the fixed-design training-point risk (4) by the analytic formula (5), not a Monte Carlo average over random realizations. The results are displayed in Figure 1. It can be seen that the risk converges to zero, albeit slowly, if the diverging-local-sample-size condition size condition holds, and remains bounded away from zero otherwise. The performance is consistent with the sufficiency and the necessity of the diverging-local-sample-size condition. The slow convergence may be due to the fact that we provide only a condition for convergence, rather than a condition for achieving the optimal convergence rate.

Figure 1. Training-point risk under four correlation regimes in one and two dimensions.

Discussion

This paper establishes a unified signal-recovery framework on fixed-dimensional bounded uniform grids with product exponential kernels, placing long-range correlation, fixed scale, and short-range correlation under one necessary and sufficient criterion and one penalty construction. For every fixed nonzero signal in the mixed first-order Sobolev space, training-point risk consistency is equivalent to the diverging-local-sample-size condition MN=N/θNd→∞M_N = N/\theta_N^d \to\infty. The statement holds along the entire sequence and therefore also covers mixed scale paths containing subsequences from different regimes.

The present study is restricted to specific conditions, leaving several open problems for future research. First, it is unclear whether the diverging-local-sample-size condition is valid for general Matérn kernels, nonuniform designs, out-of-sample prediction, and continuous L2L_2 recovery. Second, we establish the validity of prespecified deterministic penalty sequences, while the conditions under which cross-validation and other data-driven rules succeed are left open. Third, the numerical results show that the penalty sequence we proposed is far from optimal, and regime-specific optimal penalties and optimal risk rates remain to be studied.

Proofs

Proofs in Section 2

Proof of Theorem 1. Right-multiplying (Rθ+ρIn)−Rθ=ρIn(R_\theta+ \rho I_n) - R_\theta= \rho I_n by (Rθ+ρIn)−1(R_\theta+ \rho I_n)^{-1} gives

In−Sθ,ρ=ρ(Rθ+ρIn)−1.I_n - S_{\theta,\rho} = \rho(R_\theta+ \rho I_n)^{-1}.

Consequently,

f^θ,ρ−f=−ρ(Rθ+ρIn)−1f+Sθ,ρε.\hat{f}_{\theta,\rho} - f = -\rho(R_\theta+ \rho I_n)^{-1}f + S_{\theta,\rho}\varepsilon.

Expanding the squared norm, we find that the expected cross term is

E[ε′Sθ,ρ′(Sθ,ρ−In)f]=0,\mathbb{E}\left[\varepsilon'S_{\theta,\rho}'(S_{\theta,\rho}-I_n)f\right] = 0,

because Eε=0\mathbb{E}\varepsilon= 0. The deterministic part divided by nn is BnB_n. For the noise part,

E∥Sθ,ρε∥2=Etr⁡(Sθ,ρεε′Sθ,ρ′)=tr⁡(Sθ,ρE(εε′)Sθ,ρ′)=σ2tr⁡(Sθ,ρ2),\begin{aligned} \mathbb{E}\lVert S_{\theta,\rho}\varepsilon\rVert^2 = \mathbb{E}\operatorname{tr}\left(S_{\theta,\rho}\varepsilon\varepsilon'S_{\theta,\rho}'\right) \\ &= \operatorname{tr}\left(S_{\theta,\rho}\mathbb{E}(\varepsilon\varepsilon')S_{\theta,\rho}'\right) \\ &= \sigma^2\operatorname{tr}(S_{\theta,\rho}^2), \end{aligned}

where the last step uses the symmetry of Sθ,ρS_{\theta,\rho}. Division by nn gives (5).

Proof of Theorem 2. The identity Jn2=nJnJ_n^2 = nJ_n directly gives

(Jn+ρIn)−1=1ρIn−1ρ(n+ρ)Jn,Jn(Jn+ρIn)−1=Jnn+ρ.(J_n+\rho I_n)^{-1} = \frac{1}{\rho}I_n-\frac{1}{\rho(n+\rho)}J_n,\qquad J_n(J_n+\rho I_n)^{-1} = \frac{J_n}{n+\rho}.

This yields the fitted vector f^0,ρ=nyˉ1n/(n+ρ)\hat{f}_{0,\rho}=n\bar{y}\mathbf{1}_n/(n+\rho). Orthogonally decomposing ff into fˉ1n\bar{f}\mathbf{1}_n and f−fˉ1nf-\bar{f}1_n, and using tr⁡(Jn2)=n2\operatorname{tr}(J_n^2)=n^2, gives

Rn(0,ρ;f)=∥f−fˉ1n∥n2+ρ2fˉ2(n+ρ)2+nσ2(n+ρ)2.\mathcal{R}_n(0,\rho;\mathbf{f})=\lVert\mathbf{f}-\bar{f}1_n\rVert_n^2+\frac{\rho^2\bar{f}^2}{(n+\rho)^2}+\frac{n\sigma^2}{(n+\rho)^2}.

which reaches its minimum at ρ=σ2/fˉ2\rho=\sigma^2/\bar{f}^2, and this completes the proof of (i).

By R∞=In\mathbf{R}_{\infty}=\mathbf{I}_n, we can immediately get

f^∞,ρ=y1+ρ,Rn(∞,ρ;f)=ρ2∥f∥n2+σ2(1+ρ)2.\hat{\mathbf{f}}_{\infty,\rho}=\frac{\mathbf{y}}{1+\rho},\qquad\mathcal{R}_n(\infty,\rho;\mathbf{f})=\frac{\rho^2\lVert\mathbf{f}\rVert_n^2+\sigma^2}{(1+\rho)^2}.

Some algebra gives its minimizer ρ=σ2/∥f∥n2\rho=\sigma^2/\lVert\mathbf{f}\rVert_n^2. Substitution gives (ii).

Proofs in Section 3

For an N×NN\times N correlation matrix R\mathbf{R} and NN-vector a\mathbf{a}, define ∥a∥R−12=a′R−1a\lVert\mathbf{a}\rVert_{\mathbf{R}^{-1}}^2=\mathbf{a}^{\prime}\mathbf{R}^{-1}\mathbf{a}, and let ∥R∥op\lVert\mathbf{R}\rVert_{\mathrm{op}} denote the operator 2-norm/maximum singular value of R\mathbf{R}. Let Hθ\mathcal{H}_{\theta} denote the reproducing-kernel Hilbert space of the continuous product exponential kernel in Assumption 3 equipped with the norm ∥⋅∥Hθ\lVert\cdot\rVert_{\mathcal{H}_{\theta}}. The following lemma presents the general risk bounds of kernel ridge regression. As in Theorem 1, BNB_N and VNV_N denote the bias and variance of the kernel ridge estimator under the fixed-design training-point risk (4), respectively.

Lemma 1. Under Assumption 1, we have

the upper bounds BN≤ρ4N∥f∥R−12B_N\leq\frac{\rho}{4N}\lVert\mathbf{f}\rVert_{\mathbf{R}^{-1}}^2, VN≤σ24ρV_N\leq\frac{\sigma^2}{4\rho}; (12)

and the lower bounds BN≥∥f∥N2(1+∥R∥op/ρ)2B_N\geq\frac{\lVert\mathbf{f}\rVert_N^2}{(1+\lVert\mathbf{R}\rVert_{\mathrm{op}}/\rho)^2}, VN≥σ2(∥R∥op+ρ)2V_N\geq\frac{\sigma^2}{(\lVert\mathbf{R}\rVert_{\mathrm{op}}+\rho)^2}. (13)

Moreover, under Assumptions 1, 2, and 3, if R=R(d)\mathbf{R}=\mathbf{R}^{(d)} and f∈H1,…,1\mathbf{f}\in H^{1,\ldots,1}, then

∥f∥R−12≤∥f∥Hθ2.(12)\lVert\mathbf{f}\rVert_{\mathbf{R}^{-1}}^2\leq\lVert\mathbf{f}\rVert_{\mathcal{H}_{\theta}}^2. \tag*{(12)}

Proof. Write the eigenvalue decomposition R=Udiag⁡(λ1,…,λN)U′\mathbf{R}=\mathbf{U}\operatorname{diag}(\lambda_1,\ldots,\lambda_N)\mathbf{U}^{\prime}. By the reproducingkernel representation, there exists g\mathbf{g} such that f=R1/2g\mathbf{f} = \mathbf{R}^{1/2}\mathbf{g} and ∥g∥2=∥f∥R−1\lVert\mathbf{g}\rVert_2 = \lVert\mathbf{f}\rVert_{\mathbf{R}^{-1}}. Therefore,

BN=ρ2Ng′R1/2(R+ρI)−2R1/2g≤∥g∥22Nsup⁡λj≥0ρ2λj(λj+ρ)2=ρ4N∥f∥R−12.B_N = \frac{\rho^2}{N}\mathbf{g}^{\prime}\mathbf{R}^{1/2}(\mathbf{R}+\rho\mathbf{I})^{-2}\mathbf{R}^{1/2}\mathbf{g} \leq\frac{\lVert\mathbf{g}\rVert_2^2}{N}\sup_{\lambda_j\geq0}\frac{\rho^2\lambda_j}{(\lambda_j+\rho)^2} = \frac{\rho}{4N}\lVert\mathbf{f}\rVert_{\mathbf{R}^{-1}}^2.

Since 4ρλ≤(λ+ρ)24\rho\lambda\leq(\lambda+\rho)^2 and ∑jλj=tr⁡(R)=N\sum_j\lambda_j=\operatorname{tr}(\mathbf{R})=N,

VN=σ2N∑j=1Nλj2(λj+ρ)2≤σ24Nρ∑j=1Nλj=σ24ρ.V_N = \frac{\sigma^2}{N}\sum_{j=1}^{N}\frac{\lambda_j^2}{(\lambda_j+\rho)^2} \leq\frac{\sigma^2}{4N\rho}\sum_{j=1}^{N}\lambda_j = \frac{\sigma^2}{4\rho}.

For the lower bounds, 0≤λj≤∥R∥op0\leq\lambda_j\leq\lVert\mathbf{R}\rVert_{\mathrm{op}} gives

BN≥ρ2N(∥R∥op+ρ)2f′f=∥f∥N2(1+∥R∥op/ρ)2.B_N \geq\frac{\rho^2}{N(\lVert\mathbf{R}\rVert_{\mathrm{op}}+\rho)^2}\mathbf{f}^{\prime}\mathbf{f} = \frac{\lVert\mathbf{f}\rVert_N^2}{(1+\lVert\mathbf{R}\rVert_{\mathrm{op}}/\rho)^2}.

Similarly, using ∥R∥F2≥∑i=1NRii2=N\lVert\mathbf{R}\rVert_F^2\geq\sum_{i=1}^{N}\mathbf{R}_{ii}^2=N with the Frobenius norm ∥⋅∥F\lVert\cdot\rVert_F, we obtain

VN≥σ2N(∥R∥op+ρ)2∑j=1Nλj2=σ2∥R∥F2N(∥R∥op+ρ)2≥σ2(∥R∥op+ρ)2.V_N \geq\frac{\sigma^2}{N(\lVert\mathbf{R}\rVert_{\mathrm{op}}+\rho)^2}\sum_{j=1}^{N}\lambda_j^2 = \frac{\sigma^2\lVert\mathbf{R}\rVert_F^2}{N(\lVert\mathbf{R}\rVert_{\mathrm{op}}+\rho)^2} \geq\frac{\sigma^2}{(\lVert\mathbf{R}\rVert_{\mathrm{op}}+\rho)^2}.

Finally, minimum-norm interpolation [20] gives

∥f∥R−12=min⁡{∥g∥Hθ2:g(xi)=f(xi), i∈{1,…,nd}},\lVert\mathbf{f}\rVert_{\mathbf{R}^{-1}}^2=\min\{\lVert\mathbf{g}\rVert_{\mathcal{H}_\theta}^2:g(x_i)=f(x_i),\ i\in\{1,\ldots,n^d\}\},

and taking g=fg=f yields (12).

The following lemma shows the effect of the correlation scale on the RKHS norm.

Lemma 2. Under Assumptions 2 and 3, for f∈H1,…,1([0,1]d)f\in H^{1,\ldots,1}([0,1]^d), there exists a constant CfC_f, depending only on dd and ff, such that

∥f∥Hθ2≤{Cfθ−d,0<θ≤1,Cfθd,θ≥1.(13)\lVert f\rVert_{\mathcal{H}_\theta}^2 \leq \begin{cases} C_f\theta^{-d}, & 0<\theta\leq1,\\ C_f\theta^d, & \theta\geq1. \end{cases} \tag*{(13)}

Proof. We first construct a bounded extension of ff to Rd\mathbb{R}^{d}. Taking the even reflection of ff successively about 0 and 1 in each coordinate gives an extension fEf_{\mathrm{E}} on [−1,2]d[-1,2]^{d}. Each even reflection preserves the first weak derivative in that coordinate and its L2L_{2} integrability. Coordinatewise application therefore preserves all mixed weak derivatives and gives a Sobolev-norm bound depending only on dd.

Next, take an infinitely differentiable function η\eta, defined on R\mathbb{R}, which equals 1 on [0,1][0,1] and is supported in (−1/2,3/2)(-1/2,3/2). Let Φ(x)=∏r=1dη(xr)\Phi(\boldsymbol{x})=\prod_{r=1}^{d}\eta(x_{r}) and f~=ΦfE\widetilde{f}=\Phi f_{\mathrm{E}}. Then f~\widetilde{f} agrees with ff on [0,1]d[0,1]^{d} and has compact support. Applying the multivariate Leibniz rule to compute the partial derivatives term by term for α∈{0,1}d\boldsymbol{\alpha}\in\{0,1\}^{d} gives

∑α∈{0,1}d∥∂αf~∥L2(Rd)2≤Cd∥f∥1,mix2,(14)\sum_{\boldsymbol{\alpha}\in\{0,1\}^{d}}\|\partial^{\boldsymbol{\alpha}}\widetilde{f}\|_{L_{2}(\mathbb{R}^{d})}^{2}\leq C_{d}\|f\|_{1,\mathrm{mix}}^{2}, \tag*{(14)}

where CdC_{d} is a constant depending only on dd and the norm ∥⋅∥1,mix\|\cdot\|_{1,\mathrm{mix}} is defined by (8). The right-hand side of (14) is therefore a constant that depends only on dd and ff. Regard the kernel function KθK_{\theta} on [0,1]d[0,1]^{d} as the restriction of a kernel on Rd\mathbb{R}^{d}. Let Hθ(Rd)\mathcal{H}_{\theta}(\mathbb{R}^{d}) denote the RKHS induced by this kernel on Rd\mathbb{R}^{d}. The original RKHS Hθ\mathcal{H}_{\theta} induced by the restricted kernel consists of restrictions of functions in Hθ(Rd)\mathcal{H}_{\theta}(\mathbb{R}^{d}). We have

∥f∥Hθ≤∥f~∥Hθ(Rd).(15)\|f\|_{\mathcal{H}_{\theta}}\leq\|\widetilde{f}\|_{\mathcal{H}_{\theta}(\mathbb{R}^{d})}. \tag*{(15)}

Consider the Fourier transform g^(ω)=∫Rdg(x)e−iω′x dx\widehat{g}(\boldsymbol{\omega})=\int_{\mathbb{R}^{d}}g(\boldsymbol{x})e^{-i\boldsymbol{\omega}^{\prime}\boldsymbol{x}}\,d\boldsymbol{x}. The spectral density of the one-dimensional exponential kernel is

sθ(ω)=∫−∞∞e−θ∣t∣e−iωt dt=2θθ2+ω2,s_{\theta}(\omega)=\int_{-\infty}^{\infty}e^{-\theta|t|}e^{-i\omega t}\,dt=\frac{2\theta}{\theta^{2}+\omega^{2}},

and thus the product kernel has spectral density ∏r=1dsθ(ωr)\prod_{r=1}^{d}s_{\theta}(\omega_{r}). The Fourier representation of the RKHS norm and Parseval’s identity [13, 20] give

∥f~∥Hθ,d(Rd)2=1(2π)d∫Rd∣f~(ω)∣2∏r=1dθ2+ωr22θ dω=2−d∑α∈{0,1}dθd−2∣α∣∥∂αf~∥L2(Rd)2.\left\|\widetilde{f}\right\|_{\mathcal{H}_{\theta,d}(\mathbb{R}^{d})}^{2} = \frac{1}{(2\pi)^{d}} \int_{\mathbb{R}^{d}} \left|\widetilde{f}(\omega)\right|^{2} \prod_{r=1}^{d} \frac{\theta^{2}+\omega_{r}^{2}}{2\theta}\,d\omega = 2^{-d}\sum_{\alpha\in\{0,1\}^{d}}\theta^{d-2|\alpha|}\left\|\partial^{\alpha}\widetilde{f}\right\|_{L_{2}(\mathbb{R}^{d})}^{2}.

If θ≥1\theta\ge1, then θd−2∣α∣≤θd\theta^{d-2|\alpha|}\le\theta^{d}; if 0<θ≤10<\theta\le1, then θd−2∣α∣≤θ−d\theta^{d-2|\alpha|}\le\theta^{-d}. Combining (14) and (15) proves (13).

Lemma 2 unifies the two bias controls. For θ≥1\theta\ge1, (12) and (13) give

BN≤CfρθdN=CfρMN;(16)B_N\le C_f\frac{\rho\theta^{d}}{N}=C_f\frac{\rho}{M_N}; \tag*{(16)}

for 0<θ≤10<\theta\le1, they give

BN≤CfρNθd.(17)B_N\le C_f\frac{\rho}{N\theta^{d}}. \tag*{(17)}

The constant CfC_f may differ between the two cases.

The coarse variance bound VN≤σ2/(4ρ)V_N\le\sigma^2/(4\rho) in (12) remains valid under extremely long correlation, but a sharper spectral bound will be presented. We first estimate the nonprincipal eigenvalues of the one-dimensional factor in the following lemma.

Lemma 3. Under Assumptions 2 and 3, let Λn,0≥Λn,1≥⋯≥Λn,n−1\Lambda_{n,0}\ge\Lambda_{n,1}\ge\cdots\ge\Lambda_{n,n-1} be the eigenvalues of R1d(θ)\mathbf{R}_{1d}(\theta) in (7). There exists an absolute constant C0>0C_0>0 such that, for all n≥2n\ge2, 0<θ≤10<\theta\le1, and 1≤j≤n−11\le j\le n-1,

Λn,j≤C0nθj2.(18)\Lambda_{n,j}\le C_0\frac{n\theta}{j^{2}}. \tag*{(18)}

Proof. Note that q=e−θ/nq=e^{-\theta/n} in (6). We have

R1d(θ)−1=11−q2(1−q−q1+q2−q⋱⋱⋱−q1+q2−q−q1)\mathbf{R}_{1\mathrm{d}}(\theta)^{-1}=\frac{1}{1-q^2}\begin{pmatrix} 1 & -q & & & \\ -q & 1+q^2 & -q & & \\ & \ddots& \ddots& \ddots& \\ & & -q & 1+q^2 & -q \\ & & & -q & 1 \end{pmatrix}

Direct expansion for every v=(v1,…,vn)′∈Rn\mathbf{v}=(v_1,\ldots,v_n)^{\prime}\in\mathbb{R}^n gives

(1−q2)v′R1d(θ)−1v=q∑i=1n−1(vi−vi+1)2+(1−q)(v12+vn2)(1-q^2)\mathbf{v}^{\prime}\mathbf{R}_{1\mathrm{d}}(\theta)^{-1}\mathbf{v}=q\sum_{i=1}^{n-1}(v_i-v_{i+1})^2+(1-q)(v_1^2+v_n^2)
+(1−q)2∑i=2n−1vi2.\qquad+(1-q)^2\sum_{i=2}^{n-1}v_i^2.

Discarding the last two nonnegative terms, and letting Ln\mathbf{L}_n be the path-graph Laplacian [5] defined by v′Lnv=∑i=1n−1(vi−vi+1)2\mathbf{v}^{\prime}\mathbf{L}_n\mathbf{v}=\sum_{i=1}^{n-1}(v_i-v_{i+1})^2, yields

R1d(θ)−1⪰q1−q2Ln=12sinh⁡(θ/n)Ln.\mathbf{R}_{1\mathrm{d}}(\theta)^{-1}\succeq\frac{q}{1-q^2}\mathbf{L}_n=\frac{1}{2\sinh(\theta/n)}\mathbf{L}_n.

Since 0<θ/n≤10<\theta/n\leq1 and sinh⁡t≤(sinh⁡1)t\sinh t\leq(\sinh1)t for 0<t≤10<t\leq1, taking t=θ/nt=\theta/n gives

R1d(θ)−1⪰12sinh⁡1nθLn,c1:=12sinh⁡1.\mathbf{R}_{1\mathrm{d}}(\theta)^{-1}\succeq\frac{1}{2\sinh1}\frac{n}{\theta}\mathbf{L}_n,\qquad c_1:=\frac{1}{2\sinh1}.

The jjth eigenvalue of the path-graph Laplacian satisfies

νn,j=4sin⁡2πj2n≥4j2n2,1≤j≤n−1,\nu_{n,j}=4\sin^2\frac{\pi j}{2n}\geq\frac{4j^2}{n^2},\qquad1\leq j\leq n-1,

where we use sin⁡t≥2t/π\sin t\geq2t/\pi for 0≤t≤π/20\leq t\leq\pi/2. Applying the Courant–Fischer theorem [8] to the increasingly ordered eigenvalues of R1d(θ)−1\mathbf{R}_{1d}(\theta)^{-1} gives

Λn,j−1≥c1nθνn,j≥4c1j2nθ.\Lambda_{n,j}^{-1} \ge c_1 \frac{n}{\theta}\nu_{n,j} \ge4c_1\frac{j^2}{n\theta}.

Taking reciprocals proves (18).

The following lemma provides a sharper upper bound on the variance in Lemma 1 under long correlation.

Lemma 4. Under Assumptions 1, 2, and 3, let 0<θ≤10 < \theta\le1, R=R(d)\mathbf{R} = \mathbf{R}^{(d)}, and A=Nθd/ρA = N\theta^d/\rho. For A≥1A \ge1, there exists a constant CdC_d, depending only on dd, such that

VN≤Cdσ2{n−1+A1/2(1+log⁡A)d−1N}.(19)V_N \le C_d\sigma^2\left\{n^{-1}+\frac{A^{1/2}(1+\log A)^{d-1}}{N}\right\}. \tag*{(19)}

Proof. The eigenvalues of the product matrix R(d)=R1d(θ)⊗d\mathbf{R}^{(d)}=\mathbf{R}_{1d}(\theta)^{\otimes d} are indexed by multi-indices j=(j1,…,jd)∈{0,…,n−1}dj=(j_1,\ldots,j_d)\in\{0,\ldots,n-1\}^d:

Λj=∏r=1dΛn,jr.\Lambda_j=\prod_{r=1}^{d}\Lambda_{n,j_r}.

By Theorem 1,

VN=σ2Ntr⁡(Sθ,ρ2)=σ2N∑j(ΛjΛj+ρ)2.V_N=\frac{\sigma^2}{N}\operatorname{tr}(S_{\theta,\rho}^2)=\frac{\sigma^2}{N}\sum_j\left(\frac{\Lambda_j}{\Lambda_j+\rho}\right)^2.

For t≥0t\ge0, the inequalities t2/(1+t)2≤t/(1+t)≤min⁡{1,t}t^2/(1+t)^2\le t/(1+t)\le\min\{1,t\} give

VN≤σ2N∑jmin⁡{1,Λjρ}.(20)V_N\le\frac{\sigma^2}{N}\sum_j\min\left\{1,\frac{\Lambda_j}{\rho}\right\}. \tag*{(20)}

We group the terms by k=#{r=1,…,d:jr≥1}k=\#\{r=1,\ldots,d:j_r\ge1\}.

When k<dk<d, the group contains at most (dk)nk\binom{d}{k}n^k multi-indices. Bounding each summand by 11 and adding the groups k=0,…,d−1k=0,\ldots,d-1, we find that their contribution to VNV_N is at most

σ2N∑k=0d−1(dk)nk≤Cdσ2n−1.(21)\frac{\sigma^2}{N}\sum_{k=0}^{d-1}\binom{d}{k}n^k\le C_d\sigma^2n^{-1}. \tag*{(21)}

When k=dk=d, every jr≥1j_r \ge1. Lemma 3 gives

Ajρ≤C0dndθdρ∏r=1djr2=C0dA∏r=1djr2.\frac{A_j}{\rho} \le\frac{C_0^d n^d \theta^d}{\rho\prod_{r=1}^d j_r^2} = \frac{C_0^d A}{\prod_{r=1}^d j_r^2}.

Consequently, the sum over finite terms in the right-hand side of (20) is controlled by the unrestricted sum, i.e.,

∑j, k=dmin⁡{1,Ajρ}≤∑j∈Ndmin⁡{1,Ajρ}≤Sd(B):=∑j∈Ndmin⁡{1,B∏r=1djr2},\sum_{\substack{j,\ k=d}} \min\left\{1,\frac{A_j}{\rho}\right\} \le\sum_{j\in\mathbb{N}^d} \min\left\{1,\frac{A_j}{\rho}\right\} \le S_d(B):=\sum_{j\in\mathbb{N}^d} \min\left\{1,\frac{B}{\prod_{r=1}^d j_r^2}\right\},

where B=C0dA≥1B=C_0^dA\ge1 (we may take C0≥1C_0\ge1 in Lemma 3, and thus A≥1A\ge1 implies B≥1B\ge1).

We now estimate both the body region ∏rjr≤B1/2\prod_r j_r\le B^{1/2} and all remaining tail terms. Define the lattice count

Qd(T):=#{j∈Nd:∏r=1djr≤T}.Q_d(T):=\#\left\{j\in\mathbb{N}^d:\prod_{r=1}^d j_r\le T\right\}.

Clearly, Q1(T)≤TQ_1(T)\le T. If Qd−1(T)≤CT(1+log⁡T)d−2Q_{d-1}(T)\le CT(1+\log T)^{d-2}, then

Qd(T)=∑j∈Nj≤TQd−1(T/j)≤CT∑j≤Tj−1(1+log⁡Tj)d−2≤C′T(1+log⁡T)d−1.(22)\begin{aligned} Q_d(T)&=\sum_{\substack{j\in\mathbb{N}\\j\le T}}Q_{d-1}(T/j)\\ &\le CT\sum_{j\le T}j^{-1}\left(1+\log\frac{T}{j}\right)^{d-2}\le C'T(1+\log T)^{d-1}. \tag*{(22)} \end{aligned}

Hence the body-region contribution is at most

Qd(B1/2)≤CdB1/2(1+log⁡B)d−1.(23)Q_d(B^{1/2})\le C_dB^{1/2}(1+\log B)^{d-1}. \tag*{(23)}

For the tail, let ℓ0=⌊log⁡2(B1/2)⌋+1\ell_0=\lfloor\log_2(B^{1/2})\rfloor+1 and use the dyadic shells

Dℓ={j∈Nd:2ℓ−1<∏r=1djr≤2ℓ},ℓ≥ℓ0.\mathcal{D}_\ell=\left\{j\in\mathbb{N}^d:2^{\ell-1}<\prod_{r=1}^d j_r\le2^\ell\right\},\qquad\ell\ge\ell_0.

These shells cover every index with ∏rjr>B1/2\prod_r j_r>B^{1/2}. Any overlap with the body region is negligible since our estimate is used for an upper bound. Every term in Dℓ\mathcal{D}_{\ell} satisfies

min⁡{1,B∏rjr2}≤B22ℓ−2,∣Dℓ∣≤Qd(2ℓ).\min\left\{1,\frac{B}{\prod_r j_r^2}\right\}\leq\frac{B}{2^{2\ell-2}},\qquad|\mathcal{D}_{\ell}|\leq Q_d(2^\ell).

Combining this with (22), we bound the tail contribution by

∑ℓ=ℓ0∞B22ℓ−2Qd(2ℓ)≤CdB∑ℓ=ℓ0∞2−ℓ(1+ℓ)d−1≤CdB2−ℓ0(1+ℓ0)d−1≤CdB1/2(1+log⁡B)d−1.(24)\begin{aligned} \sum_{\ell=\ell_0}^{\infty}\frac{B}{2^{2\ell-2}}Q_d(2^\ell) \leq C_dB\sum_{\ell=\ell_0}^{\infty}2^{-\ell}(1+\ell)^{d-1} \\ &\leq C_dB2^{-\ell_0}(1+\ell_0)^{d-1} \\ &\leq C_dB^{1/2}(1+\log B)^{d-1}. \tag*{(24)} \end{aligned}

The second inequality uses the ratio of consecutive terms, 2−1((ℓ+2)/(ℓ+1))d−1→1/22^{-1}((\ell+2)/(\ell+1))^{d-1}\to1/2: beyond a sufficiently large ℓ\ell, comparison with a geometric series applies, and the finitely many earlier terms are absorbed into a constant depending only on dd.

Combining (23) and (24) gives

Sd(B)≤CdB1/2(1+log⁡B)d−1.S_d(B)\leq C_dB^{1/2}(1+\log B)^{d-1}.

Substituting B=C0dAB=C_0^dA and absorbing constants depending only on dd, we find that the full-coordinate group contributes at most

Cdσ2A1/2(1+log⁡A)d−1N.(25)C_d\sigma^2\frac{A^{1/2}(1+\log A)^{d-1}}{N}. \tag*{(25)}

to VNV_N. Combining (21) and (25) implies (19). □

Proof of Theorem 3. (i) We first prove sufficiency. Suppose MN→∞M_N\to\infty.

When 0<θN≤10<\theta_N\leq1, take

AN=log⁡N,ρN=NθNdAN.A_N=\log N,\qquad\rho_N=\frac{N\theta_N^d}{A_N}.

By (12), Lemma 2, and (17),

BN≤CfρNNθNd=CfAN→0.B_N \le C_f \frac{\rho_N}{N\theta_N^d} = \frac{C_f}{A_N} \to0.

For sufficiently large NN, AN≥1A_N \ge1. Lemma 4 therefore gives

VN≤Cdσ2{n−1+(log⁡N)1/2(1+log⁡log⁡N)d−1N}→0.V_N \le C_d\sigma^2\left\{n^{-1}+\frac{(\log N)^{1/2}(1+\log\log N)^{d-1}}{N}\right\}\to0.

Thus the risk tends to zero in this regime.

When θN>1\theta_N>1, take ρN=MN2/3\rho_N=M_N^{2/3}. By (16) and (12),

BN≤CfρNMN=CfMN−1/3,VN≤σ24MN−2/3.B_N\le C_f\frac{\rho_N}{M_N}=C_fM_N^{-1/3},\qquad V_N\le\frac{\sigma^2}{4}M_N^{-2/3}.

Both terms tend to zero as MN→∞M_N\to\infty. Combining the above two cases proves the sufficiency of (10).

(ii) We now prove necessity. Suppose lim inf⁡NMN<∞\liminf_N M_N<\infty. Choose a subsequence NℓN_\ell and a constant M0M_0 such that

MNℓ≤M0.(26)M_{N_\ell}\le M_0. \tag*{(26)}

To simplify notation, we continue to write NN for this subsequence. The spectrum of a Kronecker product consists of products of the factor spectra, and hence ∥R(d)∥op=∥R1d∥opd\lVert\mathbf{R}^{(d)}\rVert_{\mathrm{op}}=\lVert\mathbf{R}_{1d}\rVert_{\mathrm{op}}^d by (7). Since R1d\mathbf{R}_{1d} is symmetric, its operator 2-norm is at most its maximum absolute row sum. We have

∥R1d∥op≤max⁡i∑j=1n∣q∣i−j∣∣=max⁡i∑j=1nq∣i−j∣≤1+2∑h=1n−1qh≤1+21−q.\lVert\mathbf{R}_{1d}\rVert_{\mathrm{op}}\le\max_i\sum_{j=1}^{n}|q^{|i-j|}|=\max_i\sum_{j=1}^{n}q^{|i-j|}\le1+2\sum_{h=1}^{n-1}q^h\le1+\frac{2}{1-q}.

Along the subsequence satisfying (26), mN=MN1/d≤M01/dm_N=M_N^{1/d}\le M_0^{1/d}, and therefore q=e−1/mN≤q0:=(e−1/M0)1/d<1q=e^{-1/m_N}\le q_0:=(e^{-1/M_0})^{1/d}<1. It follows that

∥R(d)∥op=∥R1d∥opd≤L0:=(1+21−q0)d.(27)\lVert\mathbf{R}^{(d)}\rVert_{\mathrm{op}}=\lVert\mathbf{R}_{1d}\rVert_{\mathrm{op}}^d\le L_0:=\left(1+\frac{2}{1-q_0}\right)^d. \tag*{(27)}

For every ρ>0\rho> 0, if ρ≥∥R(d)∥op\rho\ge\lVert R^{(d)} \rVert_{\mathrm{op}}, then (13) gives

BN≥∥fN∥N2/4;B_N \ge\lVert f_N \rVert_N^2/4;

if ρ<∥R(d)∥op\rho< \lVert R^{(d)} \rVert_{\mathrm{op}}, then combining (13) and (27) gives

VN≥σ2(2∥R(d)∥op)2≥σ24L02.V_N \ge\frac{\sigma^2}{(2\lVert R^{(d)}\rVert_{\mathrm{op}})^2} \ge\frac{\sigma^2}{4L_0^2}.

Therefore, along this subsequence satisfying (26) and for every deterministic ρN\rho_N,

RN(θN,ρN;fN)≥min⁡{∥fN∥N24,σ24L02}.(28)R_N(\theta_N,\rho_N;f_N) \ge\min\left\{\frac{\lVert f_N\rVert_N^2}{4},\frac{\sigma^2}{4L_0^2}\right\}. \tag*{(28)}

Note that continuity of the fixed ff and Riemann summation on the bounded domain give

∥fN∥N2⟶∥f∥L2([0,1]d)2>0.\lVert f_N\rVert_N^2 \longrightarrow\lVert f\rVert_{L_2([0,1]^d)}^2 > 0.

The right-hand side of (28) has a positive limit inferior, which proves (11).

Acknowledgements

This work is partially supported by the National Natural Science Foundation of China (grant number 12571276).

References

  1. [1]Baker, E., Barbillon, P., Fadikar, A., Gramacy, R. B., Herbei, R., Higdon, D., Huang, J., Johnson, L. R., Ma, P., Mondal, A., Pires, B., Sacks, J., & Sokolov, V. (2022). Analyzing stochastic computer models: A review with opportunities. Statistical Science, 37, 64–89.arxiv.org/abs/2002.01321
  2. [2]Barthélé, S., Amblard, P. O., Tremblay, N., & Usevich, K. (2023). Gaussian process regression in the flat limit. The Annals of Statistics, 51(6), 2471–2505.arxiv.org/abs/2201.01074
  3. [3]Barthelmè, S., & Usevich, K. (2021). Spectral properties of kernel matrices in the flat limit. SIAM Journal on Matrix Analysis and Applications, 42(1), 17–57.DOI
  4. [4]Caponnetto, A., & De Vito, E. (2007). Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3), 331–368.DOI
  5. [5]Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.
  6. [6]Dicker, L. H., Foster, D. P., & Hsu, D. (2017). Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators. Electronic Journal of Statistics, 11(1), 1022–1047.
  7. [7]Driscoll, T. A., & Fornberg, B. (2002). Interpolation in the limit of increasingly flat radial basis functions. Computers & Mathematics with Applications, 43(3–5), 413–422.DOI
  8. [8]Horn, R. A., & Johnson, C. R. (2012). Matrix Analysis (2nd ed.). Cambridge University Press.
  9. [9]Kaufman, C. G., & Shaby, B. A. (2013). The role of the range parameter for estimation and prediction in geostatistics. Biometrika, 100(2), 473–484.arxiv.org/abs/1108.1851
  10. [10]Pramanick, S., & Karvonen, T. (2026). Lengthscale estimation for the Gaussian kernel and deterministic response functions. arXiv:2611.13930. https://doi.org/10.48550/arXiv.2611.13930
  11. [11]Rasmussen, C. E., & Williams, C. K. I. (2006). Gaussian processes for machine learning. MIT Press.DOI
  12. [12]Sanz-Alonso, D. (2026). Non-asymptotic analysis of Matérn regression: The roles of target and kernel lengthscales. arXiv:2608.22553. https://arxiv.org/abs/2608.22553
  13. [13]Stein, M. L. (1999). Interpolation of spatial data: Some theory for kriging. Springer.
  14. [14]Steinwart, I., Hush, D. R., & Scovel, C. (2009). Optimal rates for regularized least squares regression. In Proceedings of the 22nd Annual Conference on Learning Theory (pp. 79–93).
  15. [15]van der Vaart, A. W., & van Zanten, J. H. (2008). Rates of contraction of posterior distributions based on Gaussian process priors. The Annals of Statistics, 36(3), 1435–1463.DOI
  16. [16]van der Vaart, A. W., & van Zanten, J. H. (2009). Adaptive Bayesian estimation using a Gaussian random field with inverse Gamma bandwidth. The Annals of Statistics, 37(5B), 2655–2675.
  17. [17]van der Vaart, A. W., & van Zanten, J. H. (2011). Information rates of nonparametric Gaussian process methods. Journal of Machine Learning Research, 12, 2095–2119.DOI
  18. [18]Wahba, G. (1990). Spline models for observational data. SIAM.
  19. [19]Wang, W., & Jing, B.-Y. (2022). Gaussian process regression: Optimality, robustness, and relationship with kernel ridge regression. Journal of Machine Learning Research, 23(193), 1–67.
  20. [20]Wendland, H. (2005). Scattered Data Approximation. Cambridge University Press, Cambridge.DOI
  21. [21]Wenzel, T., & Santin, G. (2026). On the optimal shape parameter for kernel methods: Sharp direct and inverse statements. arXiv:2601.14070. https://arxiv.org/abs/2601.14070
  22. [22]Zhang, H. (2004). Inconsistent estimation and asymptotically equal interpolations in model-based geostatistics. Journal of the American Statistical Association, 99(465), 250–261.DOI

Paper details

vlnc:W_ejuchqv7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents