The Price of Linear Time: Error Analysis of Structured Kernel Interpolation

Thank you for your support and positive assessment of our work as a valuable contribution! We are glad that you found the proofs straightforward and the work well-positioned. Regarding your points:

• Clarifying the SKI Implementation (Sec 3.2 / 3.3 Connection): We will make the connection between the general SKI formulation and cubic interpolation clearer. We will explicitly state that the weight vectors $w(x)$ in $\tilde{k}(x,x^{\prime})=w(x)^{\top}K_{U}w(x^{\prime})$ are constructed using the tensor-product cubic interpolation function $g(x)$ from Definition 3.2. In this context, $g(x)$ uses the cubic kernel $u(s)$ from Definition 3.1, and the function values being interpolated, $f(c_x+hk)$, corresponding to kernel evaluations between inducing points, $k(u_i, u_j)$, which form the matrix $K_U$. We will add cross-references to make this link explicit.
• Writing Suggestions:
  • We will define the SPD (symmetric positive definite) acronym on first use (line 125) but instead replace it with the suggested PSD (positive semi-definite) nomenclature for consistency.
  • We will rephrase "compute the action of the inverse" to simply "compute the inverse times a vector" or similar.
  • We will format the definition of the inducing points matrix U on its own line for clarity.
  • We will ensure consistent capitalization of SKI.
  • Regarding the comment on Line 234 ("linearly for $d=2$" should be "linearly for $d=3$"): Thank you for prompting us to double-check. You are correct and we will fix this. We appreciate the careful reading.
  • We will fix the typo "healthcar".

Thank you again for your encouraging review and constructive suggestions.

Thank you for your thorough and critical reading of our manuscript. We appreciate the detailed feedback, particularly regarding the assumption about kernel derivatives.

Regarding the critique of Assumption 5.3: You are absolutely correct. Our claim that the partial derivative of the kernel $k_\theta$ with respect to lengthscale $\ell$ for RBF is a valid SPD kernel (Assumption 5.3 and a short description about RBF kernel’s before the formal statement) is false. For stationary kernels $k(x,y) = \phi(||x-y||^2/\ell^2)$, the derivative with respect to $\ell$ is symmetric but indefinite. Thanks for noticing this. Crucially, we do not actually need positive definiteness. We only rely on the spectral norm error we derived: this starts with tensor-product convolutional cubic interpolation error (not for kernels specifically). It then moves to elementwise kernel error, which relies on neither positive definiteness nor symmetry. After that the spectral norm bound relies on symmetry (so that the $l_1$ and $l_\infty$ norms are equal), but not positive definiteness. We will thus adjust the assumption to not claim positive definiteness.

Regarding Bound Tightness/Experiments: We appreciate the request for empirical validation. We performed experiments measuring $||K - \tilde{K}||_2$ on synthetic data using an RBF kernel. Specifically, we set the number of inducing points according to our theoretical scaling, $m = \lceil n^{d/3} \rceil$, for dimensions $d=2, 3, 4$. We then plotted the log of the approximation error against the log of the sample size $n$.

Our theoretical bounds predict that the error should asymptotically approach a constant $O(1)$ for this scaling ($m \propto n^{d/3}$). However, the experiments revealed a more favorable trend: for all tested dimensions ($d=2, 3, 4$), the approximation error actually decreased as $n$ increased. This suggests our theoretical upper bounds are likely pessimistic as you suggested and that the method's practical scaling performance is better than the worst-case guarantee.

Furthermore, a careful re-reading of our theory (Theorem 4.5 proof) confirmed the correct threshold condition is $d<3$ vs $d \ge 3$; we had made a typo and written $d \le 3$ vs $d > 3$ and will correct this throughout the paper. We will include plots and details of these experiments in the next revision of the paper.

Regarding Novelty (Curse of Dimensionality): While the curse of dimensionality impacting SKI is known, our contribution lies in its theoretical characterization that we can control error by growing inducing points at an $n^{d/3}$ rate and that for $d<3$ this guarantees linear time controlled error, further supported by our empirical findings showing performance exceeding the pessimistic bounds.

Regarding Proof Style/LLMs: Lemma A.1 was included for completeness. Regarding LLMs, they assisted in outlining and literature search, but all final proofs were a combination of human and AI derived and human verified.

Regarding Generalization Error: We agree kernel matrix error isn't the full story. Our bounds on the posterior mean and covariance approximation errors (Lemmas 5.9, 5.10) provide a more direct theoretical link between the SKI approximation and the resulting predictive distribution's accuracy.

Thank you again for your detailed critique. Clarifying the assumption issue and incorporating the empirical results will significantly strengthen the paper.

Thanks for your helpful review and for recognizing the paper's comprehensive scope. We acknowledge the concern regarding the density of the paper due to proofs being in the appendix. In the next version, we will incorporate additional proof intuitions or summaries of the key steps for our main theorems and lemmas into the main body of the paper to improve readability, as requested. Specifically, while the main text already outlines the core strategy for some results (like Theorem 4.5 relating error bounds to grid spacing and $m$, and Lemma 5.6 using quadratic form bounding techniques for the score function), we will add or enhance the intuitions for several key steps:

• For Lemma 4.1 (Interpolation Error), we will note the proof uses induction on dimension $d$, showing how the error bound accumulates multiplicatively based on the 1D case from Keys (1981).
• For Prop 4.3 (Gram Matrix Error) and Lemma 4.4 (Cross-Kernel Error), we will clarify that the proofs rely on standard matrix norm inequalities ($\Vert A\Vert_2 \leq \Vert A\Vert_\infty$ for Prop 4.3 using symmetry, and $\Vert A\Vert_2 \le \sqrt{\Vert A\Vert_1 \Vert A\Vert_\infty}$ for Lemma 4.4) combined with the elementwise error bounds derived in Lemma 4.2.
• For Lemma 5.9 (Posterior Mean Error), which currently mentions the standard strategy, we will elaborate on the specific steps: using algebraic manipulation (add and subtract terms) and the triangle inequality to decompose the error $\Vert \mu - \tilde{\mu}\Vert_2$ into terms involving the error in the cross-kernel matrix ($K_{\cdot,X} - \tilde{K}_{\cdot,X}$) and the error in the inverse Gram matrix ($(K+\sigma^2I)^{-1} - (\tilde{K}+\sigma^2I)^{-1}$), then applying our previously derived bounds for these components (Lemma 4.4 and Lemma B.4).
• For Lemma 5.10 (Posterior Covariance Error), which currently highlights the quadratic form bounding, we will add detail on bounding the prior covariance term ($K_{\cdot,\cdot} - \tilde{K}_{\cdot,\cdot}$) using Prop 4.3, and explicitly mention how the update term's error decomposition utilizes the bounds derived in previous lemmas.

We will address the formatting and writing suggestions:

• We will carefully revise referencing for consistency (including theorems in Sec 4) and ensure consistent capitalization (e.g., Gram matrix, SKI).
• We will use textual citations (\citet/\textcite) where appropriate for better flow.
• We will define the SPD (symmetric positive definite) acronym upon first use (line 125), but change it as you suggested to PSD for consistency with common GP literature.
• We will review the older citations (Lagrange, 1795; Kolmogorov, 1940). These were included to credit the original foundational works. We will check for standard modern references.

Thank you for your constructive feedback, which will help us enhance the clarity and presentation of our work.

Thank you for your positive feedback and insightful suggestions! We are encouraged that you found the theoretical claims rigorous and the proofs correct.

We will address the clarity issues raised:

• We will explicitly define $k=1,\ldots,K$ as the iterations when we first use it in Section 5.1.
• We will clarify the definition of interpolation error in Lemma 4.1 (as the uniform error bound over the domain using functions) and $\delta_{m,L}$ in Lemma 4.2 (as the tensor-product convolutional cubic interpolation error). We will also ensure the specific norm (spectral, elementwise, L2) is clear whenever "error" is discussed.
• We will correct the noted typos (e.g., "healthcar").
• We confirm Lemma 4.2 should use an inequality ($\le$), and will correct this.
• Regarding Lemma A.1, you’re right that it essentially shows the distributive property; we included the inductive proof for formal completeness but will add a few sentences that summarize it before the full proof.
• Regarding LLM usage: LLMs assisted with brainstorming, literature search, and initial proof drafting. However, all final mathematical arguments, proofs, and derivations presented were significantly refined, validated, and verified by the authors.

Regarding the request for empirical validation: We appreciate the suggestion and performed experiments simulating the spectral norm error $||K - \tilde{K}||_2$ for varying $n$ and $d$ using an RBF kernel on synthetic data. Specifically, we set the number of inducing points according to our theoretical scaling, $m = \lceil n^{d/3} \rceil$, for dimensions $d=2, 3, 4$. We then plotted the log of the approximation error against the log of the sample size $n$.

Our theoretical bound (Prop 4.3 combined with $m \propto n^{d/3}$) predicts that the error should asymptotically approach a constant $O(1)$ independent of $n$. However, our experiments showed a more favorable outcome for all tested dimensions ($d=2, 3, 4$), the approximation error actually decreased as the sample size $n$ increased with $m$ scaled precisely as $n^{d/3}$. This suggests our theoretical upper bound, particularly the $O(n)$ factor in the numerator derived from the infinity norm bound, is likely pessimistic, and the practical performance of SKI with this scaling is better than the worst-case guarantee. We will add these figures along with experimental details to the next revision.

Furthermore, upon reviewing our theoretical derivation (specifically Corollary 4.7 and its proof), there is a typo: the correct regimes are $d<3$ and $d \ge 3$, but this was incorrectly stated as $d \le 3$ vs $d > 3$. We will correct this inconsistency throughout the text. Thank you again for your valuable feedback which has helped improve our paper.