Thank you for your additional comments. We take on board and to some extent agree with your view on the importance of non-asymptotic results. We hope to produce such results that explicitly depend on the kernel parameters in the near future. Similarly, we understand your reservations and example regarding "infinitely small lengthscales" but argue that even without explicit convergence rate results, empirical results confirm that this approach (in less extreme circumstances) has very good performance and exhibits convergent behaviour, despite obviously existing in the finite data regime.
In addition, we would point out that although rates obviously depend on the choice of kernel, as an example if we consider an isotropic kernel we can infer that the corresponding convergence will depend on the convergence of the distance between neighbouring input points, something which has been studied extensively in the classical kNN literature and shown to display gradual convergence rates (e.g. [1],[2],[3]). As such, we expect similarly gradual convergence for a large number of commonly-used kernels.
Thank you for your insightful feedback and clarification regarding Algorithm 1. We now further understand your concerns, but remain confident in the validity of our conclusions pertaining to convergence behaviour. We believe that we can probe your concern by supplementing the current version with a computationally cheap deterministic function. Having applied this enhancement already to Figure 2 using the Oakley and O'Hagan function from Section 7.2, we can report that the plots maintain their core characteristics consistent with the original figure, while directly addressing the issues you raised. We can also run (smaller scale) versions to generate very similar plots to Figure 2 using data sampled directly from a GP and avoiding the use of Algorithm 1, further reinforcing our confidence in our conclusions.
We hope that our successful reproduction of the salient features of figure 2 via alternative means will have already satisfied you on the matter of Alg. 1. However, we realise that the above does not fully explain its validity in response to your final question on the topic. Details are given below. If we include algorithm 1, in addition to other evidence, we will include a proof of its validity in the appendix.
Define "Algorithm 1" as in the paper. As argued in our original rebuttal, the evaluations ${e_i^*}$ are iid RVs and so our estimator, $\frac{1}{n^*}\sum_{i=1}^{n^*} {e_i^*}$ is valid for the corresponding expectation.
Define "Algorithm 1b" to be the procedure whereby we generate an $n$-length $x$ training set that we subsequently hold constant. For each generated test point $x^*$ we then generate an $(n+1)$-length GP sample $y$. We take the $m$ nearest-neighbours of the test point $x^*$ and evaluate the function $e(\cdot)$ to obtain ${e_i^*}'$. We repeat this $n^*$ times and compute a Monte-Carlo estimate of the expectation, $\frac{1}{n^*}\sum_{i=1}^{n^*}{e_i^*}'$. This method is clearly valid, albeit computationally very expensive.
Finally, we show that the expectations in both cases are equivalent, where we begin with the case of Algorithm 1b and show that it is equivalent to that of Algorithm 1.
We use $y^*$ to refer to the test observation, $y'$ to refer to the nearest-neighbours and $y''$ to the remaining disjoint observations. $y=(y^*,y',y'')$ refers to the full (n+1) length vector and hence $p(y)$ to the full joint distribution:
$$
\frac{1}{n^*}\sum_{i=1}^{n^*} {e_i^*}' \approx E_{(y^*,y',y'')}[e(y^*,y',y'')]
= E_{(y^*,y',y'')}[e(y^*,y')]
= E_{(y^*,y')}[e(y^*,y')]
\approx \frac{1}{n^*}\sum_{i=1}^{n^*} {e_i^*}
$$
Since $e(\cdot)$ is only a function of $y^*,y'$.
[1] L ́aszl ́o Gy ̈orfi et al. A Distribution-Free Theory of Nonparametric Re- gression. 2010.,
[2] Kohler, Krzyzak, and Walk, ‘Rates of Convergence for Partitioning and Nearest Neighbor Regression Estimates with Unbounded Data’,
[3] Kulkarni and Posner, ‘Rates of Convergence of Nearest Neighbor Estimation Under Arbitrary Sampling’.