Non-Parametric Inference Adaptive to Intrinsic Dimension

abstractWe consider non-parametric estimation and inference of conditional moment models in high dimensions. We show that even when the dimension $D$ of the conditioning variable is larger than the sample size $n$, estimation and inference is feasible as long as the distribution of the conditioning variable has small intrinsic dimension $d$, as measured by locally low doubling measures. Our estimation is based on a sub-sampled ensemble of the $k$-nearest neighbors ($k$-NN) $Z$-estimator. We show that if the intrinsic dimension of the covariate distribution is equal to $d$, then the finite sample estimation error of our estimator is of order $n^{-1/(d+2)}$ and our estimate is $n^{1/(d+2)}$-asymptotically normal, irrespective of $D$. The sub-sampling size required for achieving these results depends on the unknown intrinsic dimension $d$. We propose an adaptive data-driven approach for choosing this parameter and prove that it achieves the desired rates. We discuss extensions and applications to heterogeneous treatment effect estimation.

cases\frac{1}{k} \binom{n}{s}^{-1} \, \binom{n-i}{s-1} & if i \leq k \\ \frac{1}{k} \binom{n}{s}^{-1} \, \sum_{j=0}^{k-1} \binom{i-1}{j} \binom{n-i}{s-1-j} & if i \geq k+1 \,.

minipage{0.48\textwidth} \begin{algorithm}[H] \caption{Sub-Sampled Kernel Estimation} \begin{algorithmic}[1] \State {\bf Input.} Data $\left\{Z_i=(X_i, Y_i)\right\}_{i=1}^n$, moment $\psi$, kernel $K$, sub-sampling size $s$, number of iterations $B$ \State {\bf Initialize.} $\alpha(X_i) = 0, 1 \leq i \leq n$ \For{$b \gets 1, B$} \State Sub-sampling. Draw set $S_b$ by sampling $s$ points from $Z_1,Z_2,\ldots,Z_n$ without replacement. \State Weight Updates. $\alpha(X_i) \gets \alpha(X_i) + K_{\omega_b}(x,X_i,S_b)$ \EndFor \State Weight Normalization. $\alpha(X_i) \gets \alpha(X_i)/B$ \State Estimation. Denote $\hat{\theta}$ as a solution of $\Psi(x;\theta)=\sum_{i=1}^n \alpha(X_i) \psi(Z_i;\theta)=0$ \end{algorithmic} \end{algorithm}

minipage{0.48\textwidth} \begin{algorithm}[H] \caption{Sub-Sampled $k$-NN Estimation} \begin{algorithmic}[1] \State {\bf Input.} Data $\left\{Z_i=(X_i, Y_i)\right\}_{i=1}^n$, moment $\psi$, sub-sampling size $s$, number of iterations $B$, number of neighbors $k$ \State {\bf Initialize.} $\alpha(X_i) \gets 0, 1 \leq i \leq n$ \For{$b \gets 1,B$} \State Sub-sampling. Draw set $S_b$ by sampling $s$ points from $Z_1,Z_2,\ldots,Z_n$ without replacement \State Weight Updates. $\alpha(X_i) \gets \alpha(X_i) + \,1 \left\{X_i \in H_k(x,S_b)\right\}/k $ \EndFor \State Weight Normalization. $\alpha(X_i) \gets \alpha(X_i)/B$ \State Estimation. Denote $\hat{\theta}$ as a solution of $\Psi(x;\theta)=\sum_{i=1}^n \alpha(X_i) \psi(Z_i;\theta)=0$ \end{algorithmic} \end{algorithm}

definitionThe marginal $\mu$ is called {\bf doubling measure} if there exists a constant $C_{db}>0$ such that for any $x \in \mathcal{X}$ and any $r>0$ we have $\mu(B(x,r)) \leq C_{db} \mu(B(x,r/2))$.

definitionFix $x \in \mathcal{X}$ and $r > 0$. The marginal $\mu$ is $(C,d)$-{\bf homogeneous on} $B(x,r)$ if for any $\theta \in (0,1)$ we have $\mu(B(x, r)) \leq C \theta^{-d} \mu(B(x, \theta r))$.

definition[Kernel Shrinkage in Expectation] The kernel weighting function output by learner $\mathcal{L}_k$ when it is given $s$ i.i.d. observations drawn from distribution $\mathcal{D}$ satisfies \begin{equation*} \mathbf{E} \left[\sup \left\{\|x - X_i\|_2 : K(x,X_i,S)>0\right\}\right] = \epsilon(s)\,. \end{equation*}

definition[Kernel Shrinkage with High Probability] The kernel weighting function output by learner $\mathcal{L}_k$ when it is given $s$ i.i.d. observations drawn from distribution $\mathcal{D}$ w.p. $1-\delta$ over the draws of the $s$ samples satisfies \begin{equation*} \sup \left\{\|x - X_i\|_2: K(x,X_i,S)>0\right\} \leq \epsilon(s,\delta)\,. \end{equation*}

assumption\begin{enumerate} • • The moment $m(x; \theta)$ corresponds to the gradient w.r.t. $\theta$ of a $\lambda$-strongly convex loss $L(x; \theta)$. This also means that the Jacobian $M_0= \nabla_\theta m(x; \theta(x))$ has minimum eigenvalue at least $\lambda$. • For any fixed parameters $\theta$, $m(x; \theta)$ is a $L_m$-Lipschitz function in $x$ for some constant $L_m$. • There exists a bound $\psi_{\max}$ such that for any observation $z$ and any $\theta$, $\|\psi(z; \theta)\|_{\infty}\leq \psi_{\max}$. • The bracketing number $N_{[]}({\cal F}, \epsilon, L_2)$ of the function class: ${ \cal F}=\{\psi(\cdot; \theta): \theta \in \Theta\}$, satisfies $\log(N_{[]}({\cal F}, \epsilon, L_2))= O(1 /\epsilon)$. \end{enumerate}

assumption\begin{enumerate} • • For any coordinate $j$ of the moment vector $m$, the Hessian $H_j(x; \theta)=\nabla^2_{\theta\theta} m_j(x;\theta)$ has eigenvalues bounded above by a constant $L_H$ for all $\theta$. • Maximum eigenvalue of $M_0$ is upper bounded by $L_J$. • Second moment of $\psi(x;\theta)$ defined as $\operatorname{Var}\left(\psi(Z;\theta) \mid X=x\right)$ is $L_{mm}$-Lipschitz in $x$, i.e., \begin{equation*} \|\operatorname{Var}\left(\psi(Z;\theta) \mid X=x\right) - \operatorname{Var}\left(\psi(Z;\theta) \mid X=x'\right)\|_F \leq L_{mm} \|x-x'\|_2\,. \end{equation*} • Variogram is Lipschitz: $\sup_{x\in \mathcal{X}} \|\operatorname{Var}(\psi(Z; \theta) - \psi(Z; \theta') \mid X=x)\|_F \leq L_{\psi} \|\theta - \theta'\|_2$. \end{enumerate}

assumptionThe kernel $K$, built using samples $\left\{Z_1,Z_2,\ldots,Z_s\right\}$, is {\bf honest} if the weight of sample $i$ given by $K(x,X_i,\left\{Z_j\right\}_{j=1}^s)$ is independent of $Y_j$ conditional on $X_j$ for any $j \in [s]$.

assumptionThe kernel $K$, built using samples $\left\{Z_1, Z_2, \ldots, Z_s\right\}$, is {\bf symmetric} if for any permutation $\pi:[s] \to [s]$, the distribution of $K(x,X_i,\left\{Z_j\right\}_{j=1}^s)$ and $K(x, X_{\pi(i)}, \left\{Z_{\pi(j)}\right\}_{j=1}^s)$ are equal. In other words, the kernel weighting distribution remains unchanged under permutations.

theorem[Finite Sample Estimation Rate] Let Assumptions (ref) and (ref) hold. Suppose that Algorithm (ref) is executed with $B \geq n/s$. If the base kernel $K$ satisfies kernel shrinkage in expectation, with rate $\epsilon(s)$, then w.p. $1-\delta$ \begin{equation} \|\hat{\theta} - \theta(x)\|_2 \leq \frac{2}{\lambda}\left(L_m \epsilon(s) + O\left(\psi_{\max}\sqrt{\frac{p\, s}{n} \left(\log\log(n /s) + \log(p/\delta)\right)}\right)\right)\,. \end{equation} Moreover, \begin{equation} \sqrt{\mathbf{E}\left[\|\hat{\theta} - \theta(x)\|_2^2\right]} \leq \frac{2}{\lambda}\left(L_m \epsilon(s) + O\left(\psi_{\max}\sqrt{\frac{p\, s}{n} \log\log(p\, n /s)}\right)\right)\,. \end{equation}

theorem[Asymptotic Normality] Let Assumptions (ref), (ref), (ref), and (ref) hold. Suppose that Algorithm (ref) is executed with $B \geq (n/s)^{5/4}$ and the base kernel $K$ satisfies kernel shrinkage, with rate $\epsilon(s, \delta)$ in probability and $\epsilon(s)$ in expectation. Let $\eta(s)$ be the incrementality of kernel $K$ defined in Equation (ref) and $s$ grow at a rate such that $s\rightarrow \infty$, $n \eta(s) \rightarrow \infty$, and $\epsilon(s,\eta(s)^2) \rightarrow 0$. Consider any fixed coefficient $\beta\in \mathbb{R}^p$ with $\|\beta\|\leq 1$ and define the variance as $$\sigma_{n,\beta}^2(x) = \frac{s^2}{n}\operatorname{Var}\left[\mathbf{E}\left[\sum_{i=1}^s K(x, X_i, \{Z_j\}_{j=1}^s) \left\langle \beta, M_0^{-1} \psi(Z_i; \theta(x))\right\rangle\mid Z_1\right]\right]\right]}.$$ Then it holds that $\sigma_{n,\beta}(x) = \Omega\left(s \sqrt{\eta(s)/n}\right)$. Moreover, suppose that \begin{equation} \max \left(\epsilon(s), \epsilon(s)^{1/4} \left(\frac{s}{n} \,\log\log(n/s) \right)^{1/2}, \left(\frac{s}{n} \, \log\log(n/s)\right)^{5/8} \right) = o(\sigma_{n,\beta}(x))\,. \end{equation} Then, \[ \frac{\left\langle \beta, \hat{\theta} - \theta(x)\right\rangle}{\sigma_{n,\beta}(x)} \rightarrow_d \mathsf{N}(0, 1)\,. \]

lemmaFor any symmetric kernel $K$ (Assumption (ref)) and for any $\delta\in [0,1]$: \begin{equation*} \eta_s = \mathbf{E} \left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]^2\right]ight]^2} \geq \frac{\left(1-\delta\right)^2\,(1/s)^2}{\inf_{\rho>0} \left(\mu(B(x, \epsilon(s, \rho)))+\rho\,s/\delta\right)}\,. \end{equation*} Thus if $\mu(B(x, \epsilon(s, 1/(2s^2))))=O(\log(s)/s)$, then picking $\rho=1/(2s^2)$ and $\delta = 1/2$ implies that $\mathbf{E}[\mathbf{E}[K(x, X_1, \{Z_j\}_{j=1}^s) |X_1]^2] = \Omega(1/s\log(s)).$

corollaryIf $\epsilon(s, \delta)=O((\log(1/\delta)/s)^{1/d})$ and $\mu$ satisfies a two-sided version of the doubling measure property on $B(x,r)$, defined in Definition (ref), i.e., $c \theta^d \mu(B(x, r)) \leq \mu(B(x,\theta r)) \leq C \theta^d \mu(B(x,r))$ for any $\theta \in (0,1)$. Then, $\mathbf{E}[\mathbf{E}[K(x, X_1, \{Z_j\}_{j=1}^s) |X_1]^2] = \Omega(1/(s\log(s)))$.

lemma[High probability shrinkage for the $k$-NN kernel] Suppose that the measure $\mu$ is $(C,d)$-homogeneous on $B(x,r)$. Then, for any $\delta$ satisfying $2 \exp \left(-\mu(B(x,r))s/(8C)\right) \leq \delta \leq \frac{1}{2} \exp(-k/2),$ w.p. at least $1-\delta$ we have \begin{equation*} \|x - X_{(k)}\|_2 \leq \epsilon_k(s,\delta) = O \left(\frac{\log(1/\delta)}{s}\right)^{1/d}\,. \end{equation*}

corollary[Expected shrinkage for the $k$-NN kernel] Suppose that the conditions of Lemma (ref) hold. Let $k$ be a constant and $\epsilon_k(s)$ be the expected shrinkage for the $k$-NN kernel. Then, for any $s$ larger than some constant we have $\epsilon_k(s)=\mathbf{E} \left[\|x - X_{(k)}\|_2\right] = O \left(\frac{1}{s}\right)^{1/d}$.

theorem[Estimation Guarantees for the $k$-NN Kernel] Suppose that $\mu$ is $(C,d)$-homogeneous on $B(x,r)$, Assumption (ref) holds and that Algorithm (ref) is executed with $B\geq n/s$. Then, w.p. $1-\delta$: \begin{equation} \|\hat{\theta} - \theta(x)\|_2 \leq \frac{2}{\lambda}\left(O \left(s^{-1/d} \right) + O\left(\psi_{\max}\sqrt{\frac{p\, s}{n} \left(\log\log(n /s) + \log(p/\delta)\right)}\right)\right)\,, \end{equation} and \begin{equation} \sqrt{\mathbf{E}\left[\|\hat{\theta} - \theta(x)\|_2^2\right]} \leq \frac{2}{\lambda}\left(O \left(s^{-1/d}\right) + O \left(\psi_{\max}\sqrt{\frac{s\, p\, \log \log(p\,n/s)}{n}}\right)\right)/s)}{n}}\right)} \,. \end{equation} By picking $s = \Theta \left(n^{d/(d+2)}\right)$ and $B = \Omega \left(n^{2/(d+2)}\right)$ we get $\sqrt{\mathbf{E}\left[\|\hat{\theta} - \theta(x)\|_2^2\right]} = \tilde{O}\left(n^{-1/(d+2)}\right)$.

lemma[$k$-NN Incrementality] Let $K$ be the $k$-NN kernel and let $\eta_k(s)$ denote the incrementality rate of this kernel. Then, the following holds: \begin{equation*} \eta_k(s)=\mathbf{E}\left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]^2\right]ight]^2} = \frac{1}{(2s-1)\,k^2} \left(\sum_{t=0}^{2k-2}\frac{a_t}{b_t}\right)\,, \end{equation*} where sequences $\left\{a_t\right\}_{t=0}^{2k-2}$ and $\left\{b_t\right\}_{t=0}^{2k-2}$ are defined as \begin{equation*} a_t = \sum_{i=\max \left\{0, t-(k-1)\right\}}^{\min \left\{t, k-1\right\}} \binom{s-1}{i}\,\binom{s-1}{t-i} \quad \quad and \quad \quad b_t = \sum_{i=0}^t \binom{s-1}{i}\,\binom{s-1}{t-i} \end{equation*}

theorem[Asymptotic Variance of $k$-NN] Let $j \in [p]$ be one of coordinates. Suppose that $k$ is constant while $s\rightarrow \infty$. Then, for the $k$-NN kernel \begin{equation} \sigma_{n,j}^2(x) = \frac{s^2}{n}\frac{\sigma_{j}^2(x)}{k^2\,(2s-1)}\,\zeta_k + o(s/n)\,, \end{equation} where $\sigma_j^2(x)=\operatorname{Var}\left[\left\langle e_j, M_0^{-1}\psi(Z; \theta(x))\right\rangle\mid X=x\right]$ and $\zeta_k = k + \sum_{t=k}^{2k-2} 2^{-t} \sum_{i=t-k+1}^{k-1} \binom{t}{i}.$

theorem[Asymptotic Normality of $k$-NN Estimator] Suppose that $\mu$ is $(C,d)$-homogeneous on $B(x,r)$. Let Assumptions (ref), (ref) hold and suppose that Algorithm (ref) is executed with $B\geq (n/s)^{5/4}$ iterations. Suppose that $s$ grows at a rate such that $s \rightarrow \infty$, $n/s \rightarrow \infty$, and also $s^{-1/d} (n/s)^{1/2} \rightarrow 0$. Let $j \in [p]$ be one of coordinates and $\sigma^2_{n,j}(x)$ be defined in Equation (ref). Then, \begin{equation*} \frac{\hat{\theta}_j(x)-\theta_{j}(x)}{\sigma_{n,j}(x)} \rightarrow \mathsf{N}(0,1)\,. \end{equation*} Finally, if $s = n^{\beta}$ and $B\geq n^{\frac{5}{4}(1-\beta)}$ with $\beta \in (d/(d+2),1)$. Then, \begin{equation*} \frac{\hat{\theta}_j(x)-\theta_{j}(x)}{\sigma_{n,j}(x)} \rightarrow \mathsf{N}(0,1)\,. \end{equation*}

proposition[Adaptive Estimation] Let Assumptions of Theorem (ref) hold. Suppose that $s_1$ is the output of the above process. Let $s_* = 9s_1+1$ and suppose that Algorithm (ref) is executed with $s=s_*$ and $B \geq n/s_*$. Then w.p. at least $1-2\delta$ we have $\|\hat{\theta} - \theta(x)\|_2 = O(G_{\delta}(s^*)) =O \left(\left(\frac{n}{p\log(2pn/\delta)}\right)^{-1/(d+2)}\right)/(d+2)}}$. Further, for $\delta = 1/n$ we have $\sqrt{\mathbf{E}\left[\|\hat{\theta} - \theta(x)\|_2^2\right]} = \tilde{O}\left(n^{-1/(d+2)}\right)$.

proposition[Adaptive Asymptotic Normality] Let Assumptions of Theorem (ref) hold. Suppose that $s_1$ is the output of the above process when $\delta = 1/n$ and $s_* = 9s_1+1$. For any $\zeta \in (0, (\log(n)-\log(s_1)-\log\log^2(n))/\log(n)))$ define $s_{\zeta} = s_* n^{\zeta}$. Suppose that Algorithm (ref) is executed with $s=s_{\zeta}$ and $B \geq (n/s_{\zeta})^{5/4}$, then for any coordinate $j \in [p]$, we have $\frac{\hat{\theta}_j(x)-\theta_{j}(x)}{\sigma_{n,j}(x)} \rightarrow \mathsf{N}(0,1)\,.$

appendix\section{Related work} There exists a vast literature on average treatment effect estimation in high-dimensional settings. The key challenge in such settings is the problem of overfitting which is usually handled by adding regularization terms. However, this leads to a shrinked estimate for the average treatment effect and therefore not desirable. The literature has taken various approaches to solve this issue. For instance, belloni2014high, belloni2014inference used a two-step method for estimating average treatment effect where in the first step feature-selection is accomplished via a lasso and then treatment effect is estimated using selected features. athey2018approximate studied approximate residual balancing where a combination of weight balancing and regression adjustment is used for removing undesired bias and for achieving a double robust estimator. chernozhukov2018double, chernozhukov2018double considered a more general semi-parametric framework and studied debiased/double machine learning methods via first order Neyman orthogonality condition. mackey2017orthogonal extended this result to higher order moments. Please refer to athey2017state,mullainathan2017machine,belloni2017program for a review on this literature. However, in many applications, researchers are interested in estimating heterogeneous treatment effect on various sub-populations. One effective solution is to use one of the methods described in previous paragraph to estimate problem parameters and then project such estimations onto the sub-population of interest. However, these approaches usually perform poorly when there is a model mis-specification, i.e., when the true underlying model does not belong to the parametric search space. Consequently, researchers have studied non-parametric estimators such as $k$-NN estimators, kernel estimators, and random forests. While these non-parametric estimators are very robust to model mis-specification and work well under mild assumptions on the function of interest, they suffer from the curse of dimensionality (see e.g., bellman1961adaptive, robins1997toward, friedman2001elements). Therefore, for applying these estimators in high-dimensional settings it is necessary to design and study non-parametric estimators that are able to overcome curse of dimensionality when possible. The seminal work of wager2017estimation utilized random forests originally introduced by breiman2001random and adapted them nicely for estimating heterogeneous treatment effect. In particular, the authors demonstrated how the recursive partitioning idea, explained in athey2016recursive for estimating heterogeneity in causal settings, can be further analyzed to establish asymptotic properties of such estimators. The main premise of random forests is that they are able to adaptively select nearest neighbors and that is very desirable in high-dimensional settings where discarding uninformative features is necessary for combating the curse of dimensionality. In a follow-up work, they extended these results and introduced Generalized Random Forests for more general setting of solving generalized method of moment (GMM) equations athey2019generalized. There has been some interesting developments of such ideas to other settings. fan2018dnn introduced Distributional Nearest Neighbor (DNN) where they used $1$-NN estimators together with sub-sampling and explained that by precisely combining two of these estimators for different sub-sampling sizes, the first order bias term can be efficiently removed. friedberg2018local paired this idea with a local linear regression adjustment and introduced Local Linear Forests in order to improve forest estimations for smooth functions. oprescu2018orthogonal incorporated the double machine learning methods of chernozhukov2018double into GMM framework of athey2019generalized and studied Orthogonal Random Forests in partially linear regression models with high-dimensional controls. Although forest kernels studied in wager2017estimation and athey2019generalized seem to work well in high-dimensional applications, to the best of our knowledge, there still does not exists a theoretical result supporting it. In fact, all existing theoretical results suffer from the curse of dimensionality as they depend on the dimension of problem $D$. The literature on machine learning and non-parametric statistics has recently studied how these worst-case performances can be avoided when the intrinsic dimension of problem is smaller than $D$. Please refer to cutler1993review for different notions of intrinsic dimension in metric spaces. dasgupta2008random studied random projection trees and showed that the structure of these trees do not depend on the actual dimension $D$, but rather on the intrinsic dimension $d$. They used the notion of Assouad Dimension, introduced by assouad1983plongements, and proved that using random directions for splitting, the number of levels required for halving the diameter of a leaf scales as $O(d \log d)$. The follow-up work verma2009spatial generalized these results for some other notions of dimension. kpotufe2012tree extended this idea to the regression setting and proved integrated risk bounds for random projection trees that were only dependent on intrinsic dimension. kpotufe2011k, kpotufe2013adaptivity studied this in the context of $k$-NN and kernel estimations and established uniform point-wise risk bounds only depending on the local intrinsic dimension. Our work is deeply rooted in the literature on intrinsic dimension explained above, literature on $k$-NN estimators (see e.g, mack1981local, samworth2012optimal, gyorfi2006distribution, biau2015lectures, berrett2019efficient, fan2018dnn), and generalized method of moments (see e.g., tibshirani1987local, staniswalis1989kernel, fan1998local, hansen1982large, stone1977consistent, lewbel2007local, mackey2017orthogonal). We adapt the framework of athey2019generalized and oprescu2018orthogonal and solve a generalized moment problem using a DNN estimator, originally introduced and studied by fan2018dnn. We establish consistency and inference properties of this estimator and prove that these properties only depend on the local intrinsic dimension of problem. In particular, we prove that the finite sample estimation error of order $n^{-1/(d+2)}$ together with $n^{1/(d+2)}$-asymptotically normality result of DNN estimator for solving the generalized moment problem regardless of how big the actual dimension $D$ is. Our result differs from existing literature on intrinsic dimension (e.g., kpotufe2011k, kpotufe2013adaptivity) since in addition to estimation guarantees for the regression setting, we also allow valid inference in solving conditional moment equations. Our asymptotic normality result is different from existing results for $k$-NN (see e.g., mack1981local), generalized method of moments (see e.g., lewbel2007local). This paper complements the work of fan2018dnn and extends it to the generalized method of moment setting. Furthermore, we relax the common assumption on the existence of density for covariates and prove that DNN estimators are adaptive to intrinsic dimension. We also provide the exact expression for the asymptotic variance of DNN estimator built using a $k$-NN kernel, which enables plug-in construction of confidence intervals, rather than the bootstrap method of efron1982jackknife which was used by wager2017estimation, athey2019generalized, fan2018dnn. While establishing consistency and asymptotic normality of our estimator, we also provide more general bounds on kernel shrinkage rate and also incrementality which can be useful for establishing asymptotic properties in other applications. One such application is given in high-dimensional settings where the exact nearest neighbor search is computationally expensive and Approximate Nearest Neighbor (ANN) search is often replaced in order to reduce this cost. Our flexible result allows us to use the state-of-the-art ANN algorithms (see e.g., andoni2017optimal,andoni2018approximate) while maintaining consistency and asymptotic normality. \section{Examples of spaces with small intrinsic dimension} In this section we provide examples of metric spaces that have small local intrinsic dimension. Our first example covers the setting where the distribution of data lies on a low-dimensional manifold (see e.g., roweis2000nonlinear,tenenbaum2000global,belkin2003laplacian). For instance, this happens for image inputs. Even though images are often high-dimensional (e.g., $4096$ in the case of $64$ by $64$ images), all these images belong intrinsically to a $3$-dimensional manifold. \begin{example}[Low dimensional manifold (adapted from kpotufe2011k)] Consider a $d$-dimensional submanifold $\mathcal{X} \subset \mathbb{R}^D$ and let $\mu$ have lower and upper bounded density on $\mathcal{X}$. The local intrinsic dimension of $\mu$ on $B(x,r)$ is $d$, provided that $r$ is chosen small enough and some conditions on curvature hold. In fact, Bishop-Gromov theorem (see e.g., carmo1992riemannian) implies that under such conditions, the volume of ball $B(x,r) \cap \mathcal{X}$ is $\Theta(r^{d})$. This together with the lower and upper bound on the density implies that $\mu(B(x,r) \cap \mathcal{X})/\mu(B(x, \theta r) \cap \mathcal{X}) = \Theta(\theta^d)$, i.e. $\mu$ is $(C,d)$-homogeneous on $B(x,r)$ for some $C>0$. \end{example} Another example which happens in many applications, is sparse data. For example, in the bag of words representation of text documents, we usually have a vocabulary consisting of $D$ words. Although $D$ is usually large, each text document contains only a small number of these words. In this application, we expect our data (and measure) to have smaller intrinsic dimension. Before stating this example, let us discuss a more general example about mixture distributions. \begin{example}[Mixture distributions (adapted from kpotufe2011k)] Consider any mixture distribution $\mu=\sum_i \pi_i \mu_i$, with each $\mu_i$ defined on $\mathcal{X}$ with potentially different supports. Consider a point $x$ and note that if $x \not\in \operatorname{supp}(\mu_i)$, then there exists a ball $B(x,r_i)$ such that $\mu_i(B(x,r_i))=0$. This is true since the support of any probability measure is always closed, meaning that its complement is an open set. Now suppose that $r$ is chosen small enough such that for any $i$ satisfying $x \in \operatorname{supp}(\mu_i)$, $\mu_i$ is $(C_i,d_i)$-homogeneous on $B(x,r)$, while for any $i$ satisfying $x \not\in \operatorname{supp}(\mu_i)$ we have $\mu_i(B(x,r))=0$. Then, \begin{align*} \mu(B(x,r)) = &\sum_i \pi_i \mu_i(B(x,r)) = \sum_{i: \mu_i(B(x,r))=0} \pi_i \mu_i(B(x,r)) + \sum_{i: \mu_i(B(x,r))>0} \pi_i \mu_i(B(x,r)) \\ \leq & C \theta^{-d} \sum_{i: \mu_i(B(x,r))>0} \pi_i \mu_i(B(x,\theta r)) = C \theta^{-d} \sum_{i} \pi_i \mu_i(B(x,\theta r) = C \theta^{-d} \mu(B(x,\theta r))\,, \end{align*} where $C = \max_{i: \mu_i(B(x,r))>0} C_i$ and $d = \max_{i: \mu_i(B(x,r))>0} d_i$ and we used the fact that if $\mu_i(B(x,r))=0$ then $\mu_i(B(x,\theta r)) = 0$. Therefore, $\mu$ is $(C,d)$-homogeneous on $B(x,r)$. \end{example} This result applies to the case of $d$-sparse data and is explained in the following example. \begin{example}[$d$-sparse data] Suppose that $\mathcal{X} \subset \mathbb{R}^D$ is defined as $$\mathcal{X} = \left\{(x_1,x_2,\ldots,x_D) \in \mathbb{R}^D: \sum_{i=1}^D \,1\left\{x_i \neq 0\right\} \leq d\right\}\} \leq d}.$$ Let $\mu$ be a probability measure on $\mathcal{X}$. In this case, we can write $\mathcal{X}$ as the union of $k=\binom{D}{d}, d$-dimensonal hyperplanes in $\mathbb{R}^D$. In fact, \begin{equation*} \mathcal{X} = \cup_{1 \leq i_1 < i_2 < \cdots i_d \leq D} \left\{(x_1,x_2,\cdots,x_D) \in \mathbb{R}^D: x_j = 0, j \not \in \left\{i_1,i_2,\ldots,i_d\right\}\right\}d\right\}}\,. \end{equation*} Letting $\mu_{i_1,i_2,\ldots,i_d}$ be the probability measure restricted to the hyperplane defined by $x_j = 0, j\not\in \left\{i_1,i_2,\ldots,i_d\right\}$, we can express $\mu = \sum_{1 \leq i_1 < i_2 < \cdots i_d \leq D} \pi_{i_1,i_2,\ldots,i_d} \mu_{i_1,i_2,\ldots,i_d}$. Therefore, the result of Example (ref) implies that for any $x \in \mathcal{X}$, for $r$ that is small enough $\mu$ is $(C,d)$-homogeneous on $B(x,r)$. \end{example} Our final example is about the product measure. This allows us to prove that any concatenation of spaces with small intrinsic dimension has a small intrinsic dimension as well. \begin{example}[Concatenation under the product measure] Suppose that $\mu_i$ is a probability measure on $\mathcal{X}_i \subset \mathbb{R}^{D_1}$. Define $\mathcal{X} = \left\{(z_1,z_2) \mid z_1 \in \mathcal{X}_1, z_2 \in \mathcal{X}_2\right\}$ and let $\mu = \mu_1 \times \mu_2$ be the product measure on $\mathcal{X}$, i.e., $\mu(E_1 \times E_2) = \mu_1(E_1) \times \mu_2(E_2)$ for $E_i$ that is $\mu_i$-measurable, $i=1,2$. Suppose that $\mu_i$ is $(C_i,d_i)$-homogeneous on $B(x_i,r_i)$ and let $x=(x_1,x_2)$. Then, $\mu$ is $(C,d)$-homogeneous on $B(x,r)$, where $d=d_1+d_2, r =\min \left\{r_1,r_2\right\}$ and $C=(C_1\,C_2\,r^{-(d_1+d_2)}\,2^{(d_1+d_2)/2})/(r_1^{-d_1}\,r_2^{-d_2})$. To establish this, let $r=\min \left\{r_1,r_2\right\}$ and note that for any $\theta \in (0,1)$ we have \begin{align*} \mu\left(B(x,r)\right) \leq & \mu \left(B(x_1,r) \times B(x_2,r)\right) = \mu_1 \left(B(x_1,r)\right) \times \mu_2 \left(B(x_2,r)\right) \\ &\leq \mu_1 \left(B(x_1,r_1)\right) \times \mu_2 \left(B(x_2,r_2)\right) \\ \leq & \left[C_1 \left(\frac{r\theta}{r_1\sqrt{2}}\right)^{-d_1} \mu_1 \left(B \left(x_1, \frac{r\theta}{\sqrt{2}}\right)\right)\right)}\right] \times \left[C_2 \left(\frac{r\theta}{r_2\sqrt{2}}\right)^{-d_2} \mu_2 \left(B\left(x_2, \frac{r\theta}{\sqrt{2}}\right)\right)\right)}\right] \\ = & \frac{C_1\,C_2\,r^{-(d_1+d_2)}}{r_1^{-d_1}\,r_2^{-d_2}\,\sqrt{2}^{-(d_1+d_2)}} \theta^{-d_1-d_2} \mu \left(B(x_1, r\theta/\sqrt{2}) \times B(x_2, r\theta/\sqrt{2})\right) \\ \leq & \frac{C_1\,C_2\,r^{-(d_1+d_2)\,2^{(d_1+d_2)/2}}}{r_1^{-d_1}\,r_2^{-d_2}} \theta^{-(d_1+d_2)} \mu \left(B(x,r \theta)\right)\,, \end{align*} where we used two simple inequalities that $\|(z_1,z_2)-(x_1,x_2)\|_2 \leq r$ implies $\|z_i-x_i\|_2 \leq r,~i=1,2,$ and further $\|z_i-x_i\|_2 \leq r/\sqrt{2},~i=1,2,$ implies $\|(z_1,z_2)-(x_1,x_2)\|_2 \leq r$. \end{example} \section{Simulation Setting} Here we explain the settings for simulations shown in Figures (ref) and (ref). \subsection{Single test point} The data for single test point simulation, shown in Figure (ref), has been generated as follows. Here $p=1$, $D=20$ and $d=2$. All the points are generated using $X_i = A X_i^{\text{low}}$, where $A \in \mathbb{R}^{D \times d}$ and entries of $A$ are independently sampled from $U[-1,1]$. Components of each $X_i^{\text{low}}$ are also generated independently from $U[-1,1]$. We generate a fix test point $x_{\text{test}} = A x_{\text{test}}^{\text{low}}$ and keep the matrix $A$ throughout all Monte-Carlo iterations fixed. In each Monte-Carlo iteration, we generate $n=20000$ training points as mentioned before. The values of $Y_i$ are generated according to $Y_i = f(X_i) + \varepsilon_{i}$, where $f(X) = \frac{1}{1+\exp(-3X[0])}$, and $\varepsilon_i \sim \mathsf{N}(0,\sigma_e^2)$ with $\sigma_e = 1$. We are interested in estimate and inference for $f(x_{\text{test}})$ which is equivalent to solving for $\mathbf{E}[\psi(Z;\theta(x)) \mid X=x] = 0$ with $\psi(Z;\theta(x)) = Y - \theta(x)$ at $x = x_{\text{test}}$. We run DNN (Algorithm (ref)) for $k=1,2$ and $5$ with parameter $s = s_{\zeta}$ chosen using Proposition (ref) with $\zeta=0.1$ over $1000$ Monte-Carlo iterations and report the histogram and quantile-quantile plot of estimates compared to theoretical asymptotic normal distribution of estimates stemming from our characterization. In our simulations, we considered the complete $U$-statistic case, i.e., $B = \binom{n}{s}$. \subsection{Multiple test point} The data for the multiple test point simulation, shown in Figure (ref), has been generated very similarly to the single test point setting. The only difference is that instead of generating a single test point we generate $100$ test points. These test points together with matrix $A$ are kept fixed throughout all $1000$ Monte-Carlo iterations. We compare the performance of DNN (Algorithm (ref)) with parameter $s = s_{\zeta}$ chosen using Proposition (ref) with $\zeta = 0.1$ with two benchmarks that set $s_d=n^{1.05 d/(d+2)}$ and $s_D=n^{1.05 D/(D+2)}$. This process has been repeated for $k=1,2$ and $5$ and the coverage over a single run for all test points, the empirical coverage over $1000$ runs, and chosen $s_{\zeta}$ versus $s_d$ are depicted. \section{Nuisance parameters and heterogeneous treatment effects} Using the techniques of oprescu2018orthogonal, our work also easily extends to the case where the moments depend on, potentially infinite dimensional, nuisance components $h_0$, that also need to be estimated, i.e., \begin{equation} \textstyle{\theta(x) solves: m(x; \theta, h_0) = \mathbf{E}[\psi(Z; \theta, h_0)\mid x] = 0.} \end{equation} If the moment $m$ is orthogonal with respect to $h$ and assuming that $h_0$ can be estimated on a separate sample with a conditional MSE rate of \begin{equation} \textstyle{\mathbf{E}[(\hat{h}(z) - h_0(z))^2 | X=x] = o_p(\epsilon(s) + \sqrt{s/n})\,,} \end{equation} then using the techniques of oprescu2018orthogonal, we can argue that both our finite sample estimation rate and our asymptotic normality rate, remain unchanged, as the estimation error only impacts lower order terms. This extension allows us to capture settings like heterogeneous treatment effects, where the treatment model also needs to be estimated when using the orthogonal moment as \begin{equation} \textstyle{\psi(z; \theta, h_0) = (y - q_0(x, w) - \theta (t - p_0(x, w)))\, (t-p_0(x,w))\,,} \end{equation} where $y$ is the outcome of interest, $t$ is a treatment, $x, w$ are confounding variables, $q_0(x, w) = \mathbf{E}[Y | X=x, W=w]$ and $p_0(x,w)=E[T | X=x, W=w]$. The latter two nuisance functions can be estimated via separate non-parametric regressions. In particular, if we assume that these functions are sparse linear in $w$, i.e.: \begin{align} q_0(x,w) =& \left\langle \beta(x), w\right\rangle\,,&p_0(x,w) = \left\langle \gamma(x), w\right\rangle\,. \end{align} Then we can achieve a conditional mean-squared-error rate of the required order by using the kernel lasso estimator of oprescu2018orthogonal, where the kernel is the sub-sampled $k$-NN kernel, assuming the sparsity does not grow fast with $n$. \section{Proof of Theorem (ref)} \begin{lemma} For any $\theta\in \Theta$: \begin{equation} \|\theta - \theta(x)\|_2 \leq \frac{2}{\lambda} \| m(x; \theta)\|_2\,. \end{equation} \end{lemma} \begin{proof} By strong convexity of the loss $L(x; \theta)$ and the fact that $m(x;\theta(x))=0$, we have: \begin{equation*} L(x; \theta) - L(x; \theta(x)) \geq \left\langle m(x;\theta(x)), \theta - \theta(x)\right\rangle + \frac{\lambda}{2} \cdot \|\theta- \theta(x)\|_2^2 = \frac{\lambda}{2} \cdot \|\theta- \theta(x)\|_2^2 \,. \end{equation*} By convexity of the loss $L(x; \theta)$ we have: \begin{equation*} L(x; \theta(x)) - L(x; \theta) \geq \left\langle m(x;\theta), \theta(x) - \theta\right\rangle\,. \end{equation*} Combining the latter two inequalities we get: \begin{equation*} \frac{\lambda}{2} \cdot \|\theta- \theta(x)\|_2^2 \leq \left\langle m(x;\theta), \theta - \theta(x)\right\rangle \leq \|m(x;\theta)\|_2 \cdot \|\theta - \theta(x)\|_2\,. \end{equation*} Note that if $\|\theta-\theta(x)\|_2 = 0$, then the result is obvious. Otherwise, dividing over by $\|\theta - \theta(x)\|_2$ completes the proof of the lemma. \end{proof} \begin{lemma} Let $\Lambda(x; \theta) = m(x;\theta) - \Psi(x;\theta)$. Then the estimate $\hat{\theta}$ satisfies: \begin{equation} \|m(x;\hat{\theta})\|_2 \leq \sup_{\theta\in\Theta} \|\Lambda(x; \theta)\|_2\,. \end{equation} \end{lemma} \begin{proof} Observe that $\hat{\theta}$, by definition, satisfies $\Psi(x;\hat{\theta})=0$. Thus: \begin{equation*} \|m(x;\hat{\theta})\|_2 = \|m(x;\hat{\theta}) - \Psi(x; \hat{\theta})\|_2 = \|\Lambda(x;\hat{\theta})\|_2 \leq \sup_{\theta\in \Theta} \|\Lambda(x; \theta)\|_2\,. \end{equation*} \end{proof} \begin{lemma} Suppose that the kernel is built with sub-sampling at rate $s$, in an honest manner (Assumption (ref)) and with at least $B\geq n/s$ sub-samples. If the base kernel satisfies kernel shrinkage in expectation, with rate $\epsilon(s)$, then w.p. $1-\delta$: \begin{equation} \sup_{\theta\in\Theta} \|\Lambda(x; \theta)\|_2 \leq L_m \epsilon(s) + O\left(\psi_{\max}\sqrt{\frac{p\, s}{n} \left(\log\log(n /s) + \log(p/\delta)\right)}\right)\,. \end{equation} \end{lemma} \begin{proof} Define \begin{equation*} \mu_0(x;\theta) = \mathbf{E} \left[\Psi_0(x;\theta)\right]\,, \end{equation*} where we remind that $\Psi_0$ denotes the complete $U$-statistic: \begin{equation*} \Psi_0(x; \theta) = \binom{n}{s}^{-1} \sum_{S_b \subset [n]: |S_b|=s} \mathbf{E}_{\omega_b}\left[\sum_{i\in S_b} \alpha_{S_b,\omega_b}(X_i) \psi(Z_i; \theta)\right] \,. \end{equation*} Here the expectation is taken with respect to the random draws of $n$ samples. Then, the following result which is due to oprescu2018orthogonal holds. \begin{lemma}[Adapted from oprescu2018orthogonal] For any $\theta$ and target $x$ \begin{equation*} \mu_0(x;\theta) = \binom{n}{s}^{-1} \sum_{S_b \subset [n]: |S_b|=s} \mathbf{E}\left[\sum_{i\in S_b} \alpha_{S_b,\omega_b}(X_i) m(X_i; \theta)\right]\,. \end{equation*} \end{lemma} In other words, Lemma (ref) states that, in the expression for $\mu_0$ we can simply replace $\psi(Z_i; \theta)$ with its expectation which is $m(X_i; \theta)$. We can then express $\Lambda(x;\theta)$ as sum of kernel error, sampling error, and sub-sampling error, by adding and subtracting appropriate terms, as follows: \begin{align*} \Lambda(x; \theta) = & m(x; \theta) - \Psi(x;\theta)\\ = & \underbrace{m(x; \theta) - \mu_0(x;\theta)}_{\Gamma(x,\theta)=Kernel error} + \underbrace{\mu_0(x; \theta) - \Psi_0(x; \theta)}_{\Delta(x,\theta)=Sampling error} + \underbrace{\Psi_0(x;\theta) - \Psi(x;\theta)}_{\Upsilon(x,\theta) = Sub-sampling error} \end{align*} The parameters should be chosen to trade-off these error terms nicely. We will now bound each of these three terms separately and then combine them to get the final bound. \paragraph{Bounding the Kernel error.} By Lipschitzness of $m$ with respect to $x$ and triangle inequality, we have: \begin{align*} \|\Gamma(x;\theta)\|_2 \leq & \binom{n}{s}^{-1} \sum_{S_b \subset [n]: |S_b|=s} \mathbf{E}\left[\sum_{i\in S_b} \alpha_{S_b,\omega_b}(X_i) \|m(x;\theta) - m(X_i; \theta)\|\right]\\ \leq & L_m\binom{n}{s}^{-1} \sum_{S_b \subset [n]: |S_b|=s} \mathbf{E}\left[\sum_{i\in S_b} \alpha_{S_b,\omega_b}(X_i) \|x-X_i\|\right]\\ \leq & L_m\binom{n}{s}^{-1} \sum_{S_b \subset [n]: |S_b|=s} \mathbf{E}\left[\sup\{\|x-X_i\|: \alpha_{S_b,\omega_b}(X_i)>0\}\right]\\ \leq & L_m\, \epsilon(s) \,, \end{align*} where the second to last inequality follows from the fact that $\sum_{i} |\alpha_{S_b}(X_i) |=1$. \paragraph{Bounding the Sampling error.} For bounding the sampling error we rely on Lemma (ref) and in particular Corollary (ref). Observe that for each $j\in \{1,\ldots, p\}$, $\Psi_{0j}(x;\theta)$ is a complete $U$-statistic for each $\theta$. Thus the sampling error defines a $U$-process over the class of symmetric functions $\text{conv}(\mathcal{F}_j)=\{f_j(\cdot;\theta): \theta \in \Theta\}$, with $f_j(Z_1,\ldots, Z_{s};\theta) = \mathbf{E}_{\omega}\left[\sum_{i=1}^{s} \alpha_{Z_{1:s},\omega}(X_i) \psi_j(Z_i; \theta)\right]$. Observe that since $f_j\in \text{conv}(\mathcal{F}_j)$ is a convex combination of functions in $\mathcal{F}_j=\{\psi_j(\cdot; \theta): \theta \in \Theta\}$, the bracketing number of functions in $\text{conv}(\mathcal{F}_j)$ is upper bounded by the bracketing number of $\mathcal{F}_j$, which by our assumption, satisfies $\log(N_{[]}({\cal F}_j, \epsilon, L_2))= O(1 /\epsilon)$. Moreover, by our assumptions on the upper bound $\psi_{\max}$ of $\psi_j(z;\theta)$, we have that $\sup_{f_j\in \text{conv}(\mathcal{F}_j)} \|f_j\|_{2}, \sup_{f_j\in \text{conv}(\mathcal{F}_j)} \|f_j\|_{\infty} \leq \psi_{\max}$. Thus all conditions of Corollary (ref) are satisfied, with $\eta=G=\psi_{\max}$ and we get that w.p. $1-\delta/2p$: \begin{equation} \sup_{\theta\in\Theta} |\Delta_j(x,\theta)| = O\left(\psi_{\max}\sqrt{\frac{s}{n} \left(\log\log(n/s) + \log(2p/\delta)\right)}\right)\,. \end{equation} By a union bound over $j$, we get that w.p. $1-\delta/2$: \begin{equation} \sup_{\theta\in\Theta} \|\Delta_j(x,\theta)\|_2 \leq \sqrt{p} \max_{j\in [p]} \sup_{\theta\in\Theta} |\Delta_j(x,\theta)| = O\left(\psi_{\max}\sqrt{\frac{p\, s}{n} \left(\log\log(n /s) + \log(p/\delta)\right)}\right). \end{equation} \paragraph{Bounding the Sub-sampling error.} Sub-sampling error decays as $B$ is increased. Note that for a fixed set of samples $\left\{Z_1,Z_2,\ldots,Z_n\right\}$, for a set $S_b$ randomly chosen among all $\binom{n}{s}$ subsets of size $s$ from the $n$ samples, we have: \begin{equation*} \mathbf{E}_{S_b,\omega_b}\left[\sum_{i\in S_b} \alpha_{S_b,\omega_b}(X_i) \psi(Z_i;\theta)\right] = \Psi_0(x;\theta)\,. \end{equation*} Therefore, $\Psi(x;\theta)$ can be thought as the sum of $B$ i.i.d. random variables each with expectation equal to $\Psi_0(x;\theta)$, where expectation is taken over $B$ draws of sub-samples, each with size $s$. Thus one can invoke standard results on empirical processes for function classes as a function of the bracketing entropy. For simplicity, we can simply invoke Corollary (ref) in the appendix for the case of a trivial $U$-process, with $s=1$ and $n=B$ to get that w.p. $1-\delta/2$: \begin{equation*} \sup_{\theta\in \Theta} |\Upsilon(x;\theta)| = O\left(\psi_{\max}\sqrt{\frac{\log\log(B) + \log(2/\delta)}{B}}\right) \end{equation*} Thus for $B\geq n/s$, the sub-sampling error is of lower order than the sampling error and can be asymptotically ignored. Putting together the upper bounds on sampling, sub-sampling and kernel error finishes the proof of the Lemma. \end{proof} The probabilistic statement of the proof follows by combining the inequalities in the above three lemmas. The in expectation statement follows by simply integrating the exponential tail bound of the probabilistic statement. \section{Proof of Theorem (ref)} We will show asymptotic normality of $\hat{\alpha}=\left\langle \beta, \hat{\theta}\right\rangle$ for some arbitrary direction $\beta \in \mathbb{R}^p$, with $\|\beta\|_2\leq R$. Consider the complete multi-dimensional $U$-statistic: \begin{equation} \Psi_0(x; \theta) = \binom{n}{s}^{-1} \sum_{S_b \subset [n]: |S_b|=s} \mathbf{E}_{\omega_b}\left[\sum_{i\in S_b}\alpha_{S_b,\omega_b}(X_i) \psi(Z_i; \theta)\right] \,. \end{equation} Let \begin{equation} \Delta(x;\theta) = \Psi_0(x;\theta)-\mu_0(x; \theta) \end{equation} where $\mu_0(x;\theta) = \mathbf{E}\left[\Psi_0(x;\theta)\right]$ (as in the proof of Theorem (ref)) and \begin{equation} \tilde{\theta} = \theta(x) - M_0^{-1} \Delta(x;\theta(x)) \end{equation} Finally, let \begin{equation} \tilde{\alpha} \triangleq \left\langle \beta, \tilde{\theta}\right\rangle = \left\langle \beta, \theta(x)\right\rangle - \left\langle \beta, M_0^{-1}\,\Delta(x;\theta(x))\right\rangle \end{equation} For shorthand notation let $\alpha_0=\left\langle \beta, \theta(x)\right\rangle$, $\psi_\beta(Z; \theta) = \left\langle \beta, M_0^{-1} (\psi(Z;\theta)-m(X;\theta))\right\rangle$ and \begin{align*} \Psi_{0,\beta}(x;\theta) = & \left\langle \beta, M_0^{-1}\, \Delta(x;\theta(x))\right\rangle\\ = & \binom{n}{s}^{-1} \sum_{S_b \subset [n]: |S_b|=s} \mathbf{E}_{\omega_b}\left[\sum_{i\in S_b}\alpha_{S_b,\omega_b}(X_i) \psi_{\beta}(Z_i; \theta)\right] \end{align*} be a single dimensional complete $U$-statistic. Thus we can re-write: \begin{align*} \tilde{\alpha} = \alpha_0 - \Psi_{0,\beta}(x;\theta(x)) \end{align*} We then have the following lemma which its proof is provided in Appendix (ref): \begin{lemma} Under the conditions of Theorem (ref): \begin{equation*} \frac{\Psi_{0,\beta}(x;\theta(x))}{\sigma_n(x)} \rightarrow \mathsf{N}(0,1)\,, \end{equation*} for $\sigma_n^2(x) = \frac{s^2}{n}\operatorname{Var}\left[\mathbf{E}\left[\sum_{i=1}^sK(x, X_i, \{X_j\}_{j=1}^s) \psi_{\beta}(Z_i; \theta)\mid X_1\right]\right]\right]} = \Omega(\frac{s^2}{n} \eta(s))$. \end{lemma} Invoking Lemma (ref) and using our assumptions on the kernel, we conclude that: \begin{equation} \frac{\tilde{\alpha} - \alpha_0(x)}{\sigma_n(x)} \rightarrow \mathsf{N}(0,1). \end{equation} For some sequence $\sigma_n^2$ which decays at least as slow as $s^2 \eta(s)/n$. Hence, since \[ \frac{\hat{\alpha}-\alpha_0}{\sigma_n(x)} = \frac{\tilde{\alpha}-\theta(x)}{\sigma_n(x)} + \frac{\hat{\alpha}-\tilde{\alpha}}{\sigma_n(x)}, \] if we show that $\frac{\hat{\alpha}-\tilde{\alpha}}{\sigma_n(x)}\rightarrow_p 0$, then by Slutsky's theorem we also have that: \begin{equation} \frac{\hat{\alpha}-\alpha_0}{\sigma_n(x)} \rightarrow \mathsf{N}(0,1), \end{equation} as desired. Thus, it suffices to show that: \begin{equation} \frac{\|\hat{\alpha} - \tilde{\alpha}\|_2}{\sigma_n(x)} \rightarrow_p 0. \end{equation} Observe that since $\|\beta\|_2 \leq R$, we have $\|\hat{\alpha} - \tilde{\alpha}\|_2\leq R \|\hat{\theta} - \tilde{\theta}\|_2$. Thus it suffices to show that: \begin{equation*} \frac{\|\hat{\theta} - \tilde{\theta}\|}{\sigma_n(x)} \rightarrow_p 0. \end{equation*} \begin{lemma} Under the conditions of Theorem (ref), for $\sigma_n^2(x)= \Omega\left(\frac{s^2}{n} \eta(s)\right)$: \begin{equation} \frac{\|\hat{\theta} - \tilde{\theta}\|}{\sigma_n(x)} \rightarrow_p 0. \end{equation} \end{lemma} \begin{proof} Performing a second-order Taylor expansion of $m_j(x; \theta)$ around $\theta(x)$ and observing that $m_j(x;\theta(x))=0$, we have that for some $\bar{\theta}_j\in\Theta$: \begin{align*} m_j(x;\hat{\theta}) = & \left\langle \nabla_{\theta} m_j(x;\theta(x)), \hat{\theta} - \theta(x)\right\rangle + \underbrace{(\hat{\theta}-\theta(x))^\top H_j(x;\bar{\theta}_j) (\hat{\theta}-\theta(x))^\top}_{\rho_j}\,. \end{align*} Letting $\rho=(\rho_1,\ldots, \rho_p)$, writing the latter set of equalities for each $j$ in matrix form, multiplying both sides by $M_0^{-1}$ and re-arranging, we get that: \begin{equation*} \hat{\theta} = \theta(x) + M_0^{-1} m (x;\hat{\theta}) - M_0^{-1}\rho \,. \end{equation*} Thus by the definition of $\tilde{\theta}$ we have: \begin{equation*} \hat{\theta}-\tilde{\theta} = M_0^{-1} \cdot (m(x;\hat{\theta}) + \Delta(x;\theta(x))) - M_0^{-1}\rho \,. \end{equation*} By the bounds on the eigenvalues of $H_j(x;\theta)$ and $M_0^{-1}$, we have that: \begin{equation} \|M_0^{-1}\rho\|_2 \leq \frac{L_H}{\lambda} \|\hat{\theta}-\theta(x)\|_2^2 \,. \end{equation} Thus we have: \begin{equation*} \|\hat{\theta}-\tilde{\theta}\|_2 = \frac{1}{\lambda} \|m(x;\hat{\theta}) + \Delta(x;\theta(x))\|_2 +\frac{L_H}{\lambda} \|\hat{\theta}-\theta(x)\|_2^2 \,. \end{equation*} By our estimation error Theorem (ref), we have that the expected value of the second term on the right hand side is of order $O\left(\epsilon(s)^2, \frac{s}{n} \log\log(n/s)\right)$. Thus by the assumptions of the theorem, both are $o(\sigma_n)$. Hence, the second term is $o_p(\sigma_n)$. We now argue about the convergence rate of the first term on the right hand side. Similar to the proof of Theorem (ref), since $\Psi(x;\hat{\theta})=0$ we have: \begin{align*} m(x;\hat{\theta}) = m(x; \hat{\theta}) - \Psi(x; \hat{\theta}) = m(x; \hat{\theta}) - \Psi_0(x; \hat{\theta}) + \underbrace{\Psi_0(x; \hat{\theta}) - \Psi(x;\hat{\theta})}_{Sub-sampling error} \,. \end{align*} We can further add and subtract $\mu_0$ from $m(x;\hat{\theta})$. \begin{align*} m(x;\hat{\theta}) = & m(x; \hat{\theta}) - \mu_0(x;\hat{\theta}) +\mu_0(x;\hat{\theta})- \Psi_0(x; \hat{\theta}) + \Psi_0(x; \hat{\theta}) - \Psi(x;\hat{\theta})\\ = & m(x; \hat{\theta}) - \mu_0(x;\hat{\theta}) -\Delta(x;\hat{\theta}) + \Psi_0(x; \hat{\theta}) - \Psi(x;\hat{\theta})\,. \end{align*} Combining we have: \begin{align*} m(x;\hat{\theta}) + \Delta(x;\theta(x)) = & \underbrace{m(x; \hat{\theta}) - \mu_0(x;\hat{\theta})}_{C=Kernel error} + \underbrace{\Delta(x;\theta(x)) - \Delta(x;\hat{\theta})}_{F=\text{Stochastic equicontinuity term}} + \underbrace{\Psi_0(x; \hat{\theta}) - \Psi(x;\hat{\theta})}_{E=\text{Sub-sampling error}}\,. \end{align*} Now similar to proof of Theorem (ref) we bound different terms separately and combine the results. \paragraph{Kernel Error.} Term $C$ is a kernel error and hence is upper bounded by $\epsilon(s)$ in expectation. Since, by assumption $s$ is chosen such that $\epsilon(s)=o(\sigma_n(x))$, we ge that $\|C\|_2/\sigma_n(x)\rightarrow_p 0$. \paragraph{Sub-sampling Error.} Term $E$ is a sub-sampling error, which can be made arbitrarily small if the number of drawn sub-samples is large enough and hence $\|E\|_2/\sigma_n(x)\rightarrow_p 0$. In fact, similar to the part about bounding sub-sampling error in Lemma (ref) we have that that: \begin{equation*} \mathbf{E}_{S_b}\left[\sum_{i\in S_b} \alpha_{S_b}(X_i) \psi(Z_i;\theta)\right] = \Psi_0(x;\theta)\,, \end{equation*} Therefore, $\Psi(x;\theta)$ can be thought as the sum of $B$ independent random variables each with expectation equal to $\Psi_0(x;\theta)$. Now we can invoke Corollary (ref) in the appendix for the trivial U-process, with $s=1, n=B$ to get that w.p. $1-\delta_1$: \begin{equation*} \sup_{\theta \in \Theta} \| \Psi_0(x;\theta)-\Psi(x;\theta)\| \leq O \left(\Psi_{\max} \sqrt{\frac{\log\log(B)+\log(1/\delta_1)}{B}}\right)\,. \end{equation*} Hence, for $B\geq (n/s)^{5/4}$, due to our assumption that $\left(s/n \log\log(n/s)\right)^{5/8} = o(\sigma_n(x))$ we get $\|E\|_2/\sigma_n(x)\rightarrow_p 0$. \paragraph{Sampling Error.} Thus it suffices that show that $\|F\|_2/\sigma_n(x)\rightarrow_p 0$, in order to conclude that $\frac{\|m(x;\hat{\theta}) + \Psi_0(x;\theta(x))\|_2}{\sigma_n(x)}\rightarrow_p 0$. Term $F$ can be re-written as: \begin{equation} F = \Psi_0(x;\theta(x)) - \Psi_0(x; \hat{\theta}) - \mathbf{E}\left[\Psi_0(x;\theta(x)) - \Psi_0(x; \hat{\theta})\right]\,. \end{equation} Observe that each coordinate $j$ of $F$, is a stochastic equicontinuity term for $U$-processes over the class of symmetric functions $\text{conv}(\mathcal{F}_j)=\{f_j(\cdot;\theta): \theta \in \Theta\}$, with $f_j(Z_1,\ldots, Z_{s};\theta) = \mathbf{E}_{\omega}\left[\sum_{i=1}^{s} \alpha_{Z_{1:s},\omega}(X_i) (\psi_j(Z_i; \theta(x))-\psi_j(Z_i;\theta))\right]$. Observe that since $f_j\in \text{conv}(\mathcal{F}_j)$ is a convex combination of functions in $\mathcal{F}_j=\{\psi_j(\cdot; \theta(x))-\psi_j(\cdot;\theta): \theta \in \Theta\}$, the bracketing number of functions in $\text{conv}(\mathcal{F}_j)$ is upper bounded by the bracketing number of $\mathcal{F}_j$, which in turn is upper bounded by the bracketing number of the function class $\{\psi_j(\cdot;\theta): \theta \in \Theta\}$, which by our assumption, satisfies $\log(N_{[]}({\cal F}_j, \epsilon, L_2))= O(1 /\epsilon)$. Moreover, under the variogram assumption and the lipschitz moment assumption we have that if $\|\theta-\theta(x)\|\leq r\leq 1$, then: \begin{align*} \|f_j(\cdot;\theta)\|_{P,2}^2 = & \mathbf{E}\left[\left(\sum_{i=1}^{s} \alpha_{Z_{1:s}}(X_i) (\psi_j(Z_i; \theta(x))-\psi_j(Z_i;\theta)\right)^2\right]\\ \leq & \mathbf{E}\left[\sum_{i=1}^{s} \alpha_{Z_{1:s}}(X_i) \left(\psi_j(Z_i; \theta(x))-\psi_j(Z_i;\theta)\right)^2\right] \tag{Jensen's inequality}\\ = & \mathbf{E}\left[\sum_{i=1}^{s} \alpha_{Z_{1:s}}(X_i) \mathbf{E}\left[\psi_j(Z_i; \theta(x))-\psi_j(Z_i;\theta)\right]^2|X_i]\right]^2|X_i]} \tag{honesty of kernel}\\ = &\mathbf{E}\left[\sum_{i=1}^{s} \alpha_{Z_{1:s}}(X_i) \left(\operatorname{Var}(\psi(Z;\theta(x)) - \psi(Z;\theta)|X_i) + \left(m(X_i;\theta(x)) - m(X_i;\theta)\right)^2\right)\right]\\ \leq & L_\psi \|\theta-\theta(x)\| + L_J^2 \|\theta - \theta(x)\|^2 \leq L_\psi r + L_J^2 r^2 = O(r)\,. \end{align*} Moreover, $\|f_j\|_{\infty}\leq 2\psi_{\max}$. Thus we can apply Corollary (ref), with $\eta= \sqrt{L_\psi r + L_J^2 r^2}=O(\sqrt{r})$ and $G=2\psi_{\max}$ to get that if $\|\hat{\theta}-\theta(x)\|\leq r$, then w.p. $1-\delta/p$: \begin{align*} |F_j| \leq & \sup_{\theta: \|\theta-\theta(x)\|\leq r} \left|\Psi_0(x;\theta(x)) - \Psi_0(x; \hat{\theta}) - \mathbf{E}\left[\Psi_0(x;\theta(x)) - \Psi_0(x; \hat{\theta})\right]\right|\\ = & O\left( \left(r^{1/4} + \sqrt{r} \sqrt{\log(p/\delta) + \log\log(n/(s\,r))}\right) \sqrt{\frac{s}{n}}\right)\\ = & O\left( \left(r^{1/4}\sqrt{\log(p/\delta) + \log\log(n/s)}\right) \sqrt{\frac{s}{n}}\right)\triangleq \kappa(r,s,n,\delta)\,. \end{align*} Using a union bound this implies that w.p. $1-\delta$ we have \begin{equation*} \max_j |F_j| \leq \kappa(r,s,n,\delta)\,. \end{equation*} By our MSE theorem and also Markov's inequality, w.p. $1-\delta'$: $\|\hat{\theta}-\theta(x)\|\leq \nu(s)/\delta'$, where: \[ \nu(s) = \frac{1}{\lambda}\left(L_m \epsilon(s) + O\left(\psi_{\max}\sqrt{\frac{p\, s}{n} \log\log(p\, s /n)}\right)\right) \] Thus using a union bound w.p. $1-\delta-\delta'$, we have: \begin{align*} \max_j |F_j| = O\left(\kappa(\nu(s)/\delta', s, n, \delta))\right)\, \end{align*} To improve readability from here we ignore all the constants in our analysis, while we keep all terms (even $\log$ or $\log\log$ terms) that depend on $s$ and $n$. Note that we can even ignore $\delta$ and $\delta'$, because they can go to zero at very slow rate such that terms $\log(1/\delta)$ or even $\delta'^{1/4}$ appearing in the analysis grow slower than $\log\log$ terms. Now, by the definition of $\nu(s)$ and $\kappa(r, s, n, \delta')$, as well as invoking the inequality $(a+b)^{1/4} \leq a^{1/4} + b^{1/4}$ for $a,b >0$ we have: \begin{equation} \max_j |F_j| \leq O(\kappa(\nu(s)/\delta', s, n, \delta)) \leq O\left(\epsilon(s)^{1/4} \left(\frac{s}{n}\log\log(n/s)\right)^{1/2} + \left(\frac{s}{n}\log\log(n/s)\right)^{5/8}\right)\,, \end{equation} Hence, using our Assumption on the rates in the statement of Theorem (ref) we get that both of the terms above are $o(\sigma_n(x))$. Therefore, $\|F\|_2/\sigma_n(x) \rightarrow_p 0$. Thus, combining all of the above, we get that: \begin{equation*} \frac{\|\tilde{\theta}-\hat{\theta}\|}{\sigma_n(x)} = o_p(1) \end{equation*} as desired. \end{proof} \begin{remark} Our notion of incrementality is slightly different from that of wager2017estimation, as there the incrementality is defined as $\operatorname{Var} \left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]\right]\right]}$. However, using the tower law of expectation \begin{align*} \mathbf{E} &\left[\mathbf{E}[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1]^2\right] - \operatorname{Var} \left[\mathbf{E}[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1]\right] \\ = & \mathbf{E}\left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]\right]\right]}^2 = \mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s)\right]^2\,. \end{align*} For a symmetric kernel the term $\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s)\right]^2$ is equal to $1/s^2$ and is asymptotically negligible compared to $\operatorname{Var} \left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]\right]\right]}$, which usually decays at a slower rate. \end{remark} \section{Lower Bound on Incrementality as Function of Kernel Shrinkage} We give a generic lower bound on the quantity $\mathbf{E}[\mathbf{E}[K(x, X_1, \{Z_j\}_{j=1}^s) |X_1]^2]$ that depends only on the Kernel shrinkage. The bound essentially implies that if we know that the probability that the distribution of $x$'s assigns to a ball of radius $\epsilon(s,1/2s)$ around the target $x$ is of order $1/s$, i.e. we should expect at most a constant number of samples to fall in the kernel shrinkage ball, then the main condition on incrementality of the kernel, required for asymptotic normality, holds. In some sense, this property states that the kernel shrinkage behavior is tight in the following sense. Suppose that the kernel was assigning positive weight to at most a constant number of $k$ samples. Then kernel shrinkage property states that with high probability we expect to see at least $k$ samples in a ball of radius $\epsilon(s,\delta)$ around $x$. The above assumption says that we should also not expect to see too many samples in that radius, i.e. we should also expect to see at most a constant number $K>k$ of samples in that radius. Typically, the latter should hold, if the characterization of $\epsilon(s,\delta)$ is tight, in the sense that if we expected to see too many samples in the radius, then most probably we could have improved our analysis on Kernel shrinkage and given a better bound that shrinks faster. \subsection{Proof of Lemma (ref)} By the Paley-Zygmund inequality, for any random variable $Z\geq 0$ and for any $\delta\in [0,1]$: \begin{align*} \mathbf{E}[Z^2] \geq (1-\delta)^2 \frac{\mathbf{E}[Z]^2}{\Pr[Z\geq \delta \mathbf{E}[Z]]} \end{align*} Let $W_1=K(x, X_1, \{Z_j\}_{j=1}^s)$. Then, applying the latter to the random variable $Z=\mathbf{E}[W_1|X_1]$ and observing that by symmetry $\mathbf{E}[Z]=\mathbf{E}[W_1]=1/s$, yields: \begin{align*} \mathbf{E}\left[\mathbf{E}[W_1|X_1]^2\right] \geq \frac{\left(1-\delta\right)^2 \mathbf{E}[W_1]^2}{\Pr[\mathbf{E}[W_1|X_1]> \delta \mathbf{E}[W_1]]} =\frac{\left(1-\delta\right)^2 (1/s)^2}{\Pr[\mathbf{E}[W_1|X_1]> \delta/s]} \end{align*} Moreover, observe that by the definition of $\epsilon(s,\rho)$ for some $\rho>0$: \begin{align*} \Pr[W_1>0 \wedge \|X_1-x\|\geq \epsilon(s,\rho)] \leq \rho \end{align*} This means that at most a mass $\rho\,s/\delta$ of the support of $X_1$ in the region $\|X_1 - x\|\geq \epsilon(s, \rho)$ can have $\Pr[W_1 > 0 | X_1]\geq \delta/s$. Otherwise the overall probability that $W_1 > 0$ in the region of $\|X_1 - x\| \geq \epsilon(s,\rho)$ would be more than $\rho$. Thus we have that except for a region of mass $\rho\,s/\delta$, for each $X_1$ in the region $\|X_1 - x\|\geq \epsilon(s,\rho)$: $\mathbf{E}[W_1 | X_1] \leq \delta/s$. Combining the above we get: \begin{equation*} \Pr[ \mathbf{E}[W_1 | X_1] \leq \delta/s ] \geq \Pr[\|X_1 - x\| \geq \epsilon(s,\rho)] - \rho\,s/\delta \end{equation*} Thus: \begin{equation*} \Pr[ \mathbf{E}[W_1 | X_1] > \delta/s ] \leq \Pr[\|X_1 - x\| \leq \epsilon(s,\rho)] + \rho\,s/\delta= \mu(B(x,\epsilon(s,\delta))) + \rho\,s/\delta \end{equation*} Since $\rho$ was arbitrarily chosen, the latter upper bound holds for any $\rho$, which yields the result. \subsection{Proof of Corollary (ref)} Thus applying Lemma (ref) with $\delta=1/2$ yields: \begin{equation*} \mathbf{E}[\mathbf{E}[K(x, X_1, \{Z_j\}_{j=1}^s) |X_1]^2] \geq \frac{\left(1/2s\right)^2}{\inf_{\rho>0} \left(\mu(B(x, \epsilon(s, \rho)))+2\rho\,s\right)} \end{equation*} Observe that: \begin{equation*} \mu(B(x,\epsilon(s, \rho))) \leq C \epsilon(s, \rho)^d \mu(B(x,r)) = O\left(\frac{\log(1/\rho)}{s}\right) \end{equation*} Hence: \begin{equation*} \inf_{\rho>0} \left(\mu(B(x, \epsilon(s, \rho)))+2\rho\,s\right) = O\left(\inf_{\rho>0} \left(\frac{\log(1/\rho)}{s}+2\rho\,s\right)\right) = O\left(\frac{\log(s)}{s}\right) \end{equation*} where the last follows by choosing $\rho=1/s^2$. Combining all the above yields: \begin{equation*} \mathbf{E}[\mathbf{E}[K(x, X_1, \{Z_j\}_{j=1}^s) |X_1]^2] =\Omega\left(\frac{1}{s\log(s)}\right) \end{equation*} \section{Proofs of Section (ref)} \subsection{Proof of Lemma (ref)} For proving this result, we rely on Bernstein's inequality which is stated below: \begin{proposition}[Bernstein's Inequality] Suppose that random variables $Z_1,Z_2,\ldots,Z_n$ are i.i.d., belong to $[-c,c]$ and $\mathbf{E}[Z_i] = \mu$. Let $\bar{Z}_n = \frac{1}{n} \sum_{i=1}^n Z_i$ and $\sigma^2 = \operatorname{Var}(Z_i)$. Then, for any $\theta>0$, \begin{equation*} \Pr \left(|\bar{Z}_n - \mu| > \theta\right) \leq 2 \exp \left(\frac{-n \theta^2}{2 \sigma^2 + 2 c \theta/3}\right). \end{equation*} This also implies that w.p. at least $1-\delta$ the following holds: \begin{equation} |\bar{Z}_n - \mu| \leq \sqrt{\frac{2 \sigma^2 \log(2/\delta)}{n}} + \frac{2c \log(2/\delta)}{3n}. \end{equation} \end{proposition} Let $A$ be any $\mu$-measurable set. An immediate application of Bernstein's inequality to random variables $Z_i = \,1 \left\{X_i \in A\right\}$, implies that w.p. $1-\delta$ over the choice of covariates $\left(X_i\right)_{i=1}^s$, we have: \begin{equation*} |\mu_s(A)-\mu(A)| \leq \sqrt{\frac{2 \mu(A) \log(2/\delta)}{s}} + \frac{2 \log(2/\delta)}{3s}. \end{equation*} In above, we used the fact that $\operatorname{Var}(Z_i) = \mu(A)(1-\mu(A)) \leq \mu(A)$. This result has the following corollary. \begin{corollary} Define $U = 2\log(2/\delta)/s$ and let $A$ be an arbitrary $\mu$-measurable set. Then, w.p. $1-\delta$ over the choice of training samples, $\mu(A) \geq 4U$ implies $\mu_s(A) \geq U$. \end{corollary} \begin{proof} Define $U = 2\log(2/\delta)/s$. Then, Bernstein's inequality in Proposition (ref) implies that w.p. $1-\delta$ we have \begin{equation*} |\mu_s(A)-\mu(A)| \leq \sqrt{U\mu(A)} + \frac{U}{3}\,. \end{equation*} Assume that $\mu(A) \geq 4U$, we want to prove that $\mu_s(A) \geq U$. Suppose, the contrary, i.e., $\mu_s(A) < U$. Then, by dividing the above equation by $\mu(A)$ we get \begin{equation*} \Big|\frac{\mu_s(A)}{\mu(A)} - 1 \Big| \leq \sqrt{\frac{U}{\mu(A)}} + \frac{1}{3} \frac{U}{\mu(A)}\\,. \end{equation*} Note that since $\mu_s(A)<U<\mu(A)$, by letting $z = U/\mu(A) \leq 1/4$ the above implies that \begin{equation*} 1-z \leq \sqrt{z} + \frac{z}{3} \Rightarrow \frac{4}{3} z + \sqrt{z} - 1 \geq 0\,, \end{equation*} which as $z>0$ only holds for \begin{equation*} \sqrt{z} \geq \frac{-3+\sqrt{57}}{8} \Rightarrow z \geq 0.3234\,. \end{equation*} This contradicts with $z \leq 1/4$, implying the result. \end{proof} Now we are ready to finish the proof of Lemma (ref). First, note that using the definition of $(C,d)$-homogeneous measure. Note that for any $\theta \in (0,1)$ we have $\mu(B(x,\theta r)) \geq (1/C) \theta^d \mu(B(x,r))$. Replace $\theta r = \epsilon$ in above. It implies that for any $\epsilon \in (0,r)$ \begin{equation} \mu(B(x,\epsilon)) \geq \frac{1}{C\,r^d} \epsilon^d \mu(B(x,r))\,. \end{equation} Pick $\epsilon_k(s,\delta)$ according to \begin{equation*} \epsilon_k(s,\delta) = r \left(\frac{8C\,\log(2/\delta)}{\mu(B(x,r)) s}\right)^{1/d}\,. \end{equation*} Note that for having $\epsilon_k(s,\delta) \in (0,r)$ we need \begin{equation*} \log(2/\delta) \leq \frac{1}{8\,C} \mu(B(x,r)) s \Rightarrow \delta \geq 2 \exp \left(-\frac{1}{8\,C}\mu(B(x,r)s\right) \,. \end{equation*} Therefore, replacing this choice of $\epsilon_k(s,\delta)$ in Equation (ref) implies that $\mu(B(x,\epsilon_k(s,\delta)))\geq \frac{8\log(2/\delta)}{s}$. Now we can use the result of Corollary (ref) for the choice $A=B(x,\epsilon_k(s,\delta))$. It implies that w.p. $1-\delta$ over the choice of $s$ training samples, we have \begin{equation*} \mu_s(B(x,\epsilon_k(s,\delta))) \geq \frac{2\log(2/\delta)}{s}\,. \end{equation*} Note that whenever $\delta \leq \exp(-k/2)/2$ we have \begin{equation*} \frac{2\log(2/\delta)}{s} \geq \frac{k}{s} \,. \end{equation*} Therefore, w.p. $1-\delta$ we have \begin{equation*} \|x-X_{(k)}\| \leq \epsilon_k(s,\delta) = O \left(\frac{\log(1/\delta)}{s}\right)^{1/d} \,. \end{equation*} \subsection{Proof of Corollary (ref)} Lemma (ref) shows that for any $t = \epsilon_k(s,\delta) = r \left(\frac{8C\log(2/\delta)}{\mu(B(x,r)) s}\right)^{1/d}$, such that $t\leq r$ and $t\geq r \left(\frac{4k\,C}{ \mu(B(x,r)) s}\right)^{1/d}$, we have that: \begin{equation*} \Pr[\|x - X_{(k)}\|_2\geq \epsilon_k(s,\delta)] \leq \delta\,. \end{equation*} Let $\rho = \frac{1}{r}\left(\frac{\mu(B(x,r))}{8C}\right)^{1/d}$, which is a constant. Solving for $\delta$ in terms of $t$ we get: \begin{equation*} \Pr[\|x - X_{(k)}\|_2\geq t] \leq 2 \exp \left(- \rho^d\, s\,t^d\right)\,, \end{equation*} for any $t\in \left[\frac{(s/k)^{-1/d}}{\rho} , r\right]$. Thus, noting that $X_i$'s and target $x$ both belong to $\mathcal{X}$ that has diameter $\Delta_{\mathcal{X}}$, we can upper bound the expected value of $[\|x - X_{(k)}\|_2$ as: \begin{align*} \mathbf{E} \left[\|x - X_{(k)}\|_2\right] = & \int_{0}^{\Delta_{\mathcal{X}}} \Pr\left[\|x - X_{(k)}\|_2 \geq t\right] dt\\ \leq & \frac{(s/k)^{-1/d}}{\rho} + \int_{\rho\, (s/k)^{-1/d}}^{r} \Pr\left[\|x - X_{(k)}\|_2 \geq t\right] dt + \Pr\left[\|x - X_{(k)}\|_2 \geq r\right] (\Delta_{\mathcal{X}} - r)\\ \leq & \frac{(s/k)^{-1/d}}{\rho} + \int_{\rho\, (s/k)^{-1/d}}^{r} 2 \exp\left\{- \rho^d\,s\, t^d\right\} dt + 2 \exp\left\{- \rho^d\, r^d\, s\right\} (\Delta_{\mathcal{X}} - r)\,. \end{align*} Note that for $s$ larger than some constant, we have $\exp\left\{- \rho^d\, r^d\, s\right\}\leq s^{-1/d}$. Thus the first and last terms in the latter summation are of order $\left(\frac{1}{s}\right)^{1/d}$. We now show that the same holds for the middle term, which would complete the proof. By setting $u=\rho^d\,s\, t^d$ and doing a change of variables in the integral we get: \begin{align*} \int_{\rho\, (s/k)^{1/d}}^{r} 2 \exp\left\{- \rho^d\,s\, t^d\right\} dt & \leq \int_{0}^{\infty} 2 \exp\left\{- \rho^d\,s\, t^d\right\} dt \\ = & \frac{1}{d\, \rho\, s^{1/d}} \int_{0}^{\infty} u^{1/d -1} \exp\left\{-u\right\} du = \frac{s^{-1/d}}{\rho} \frac{1}{d} \Gamma(1/d)\,. \end{align*} where $\Gamma$ is the Gamma function. Since by the properties of the Gamma function $z \Gamma(z)=\Gamma(z+1)$, the latter evaluates to: $ \frac{s^{-1/d}}{\rho} \Gamma((d+1)/d)$. Since $(d+1)/d\in [1,2]$, we have that $\Gamma((d+1)/d)\leq 2$. Thus the middle term is upper bounded by $\frac{2s^{-1/d}}{\rho}$, which is also of order $\left(\frac{1}{s}\right)^{1/d}$. \subsection{Proof of Lemma (ref)} Before proving this lemma we state and prove and auxiliary lemma which comes in handy in our proof. \begin{lemma} Let $P_1$ denote the mass that the density of the distribution of $X_i$ puts on the ball around $x$ with radius $\|x-X_1\|_2$, which is a random variable as it depends on $X_1$. Then, for any $s \geq k$ the following holds: \begin{align*} \mathbf{E}\left[\sum_{i=0}^{k-1}\binom{s-1}{i} (1 - P_1)^{s-1-i} P_1^{i}\right] = \mathbf{E} \left[\mathbf{E} \left[S_1 \mid X_1\right]\right]\right]} = \frac{k}{s}\,. \end{align*} \end{lemma} \begin{proof} The proof is an easy consequence of symmetry. Let $S_1 = \,1\{\text{sample 1 is among $k$ nearest neighbors}\}$, then we can write \begin{equation*} \mathbf{E} \left[ \mathbf{E} [S_1 \mid X_1]\right]= \mathbf{E}\left[\sum_{i=0}^{k-1}\binom{s-1}{i} (1 - P_1)^{s-1-i} P_1^{i}\right]\,, \end{equation*} which simply computes the probability that there are at most $k-1$ other points in the ball with radius $\|x-X_1\|$. Now, by using the tower law \begin{equation*} \mathbf{E} \left[ \mathbf{E} [S_1 \mid X_1]\right] = \mathbf{E}[S_1] = \frac{k}{s}\,, \end{equation*} which holds because of the symmetry. In other words, the probability that sample $1$ is among the $k$-NN is equal to $k/s$. Hence, the conclusion follows. \end{proof} We can finish the proof of Lemma (ref). Define $S_1 = \,1\{\text{sample 1 is among $k$ nearest neighbors}\}$, then we can write \begin{equation*} \mathbf{E}\left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]^2\right]ight]^2} = \frac{1}{k^2} \mathbf{E}\left[\mathbf{E}\left[S_1 \mid X_1\right]^2\right]ight]^2}\,. \end{equation*} Recall that if $P_1$ denotes the mass that the density of the distribution of $X_i$ puts on the ball around $x$ with radius $\|x-X_1\|_2$, which is a random variable depending on $X_1$. Therefore, \begin{align*} \mathbf{E}\left[S_1 \mid X_1\right] = \sum_{i=0}^{k-1}\binom{s-1}{i} (1 - P_1)^{s-1-i} P_1^{i}\,. \end{align*} Now we can write \begin{align*} \mathbf{E}\left[\mathbf{E} \left[S_1 \mid X_1\right]^2\right]ight]^2} = & \mathbf{E}\left[\left(\sum_{i=0}^{k-1}\binom{s-1}{i} (1 - P_1)^{s-1-i} P_1^{i}\right)^2\right]\\ = & \mathbf{E}\left[\sum_{i=0}^{k-1}\sum_{j=0}^{k-1} \binom{s-1}{i}\,\binom{s-1}{j} (1 - P_1)^{2s-2-i-j} P_1^{i+j}\right]\\ = & \mathbf{E}\left[\sum_{t=0}^{2k-2} (1 - P_1)^{2s-2-t} P_1^{t} \sum_{i=0}^{k-1}\sum_{j=0}^{k-1} \binom{s-1}{i}\,\binom{s-1}{j}\,1\left\{i+j=t\right\}\right] \\ = & \mathbf{E}\left[\sum_{t=0}^{2k-2} (1 - P_1)^{2s-2-t} P_1^{t} \sum_{i=\max \{0, t-(k-1)\}}^{\min\{t, k-1\}}\binom{s-1}{i}\,\binom{s-1}{t-i}\right] \\ = & \mathbf{E}\left[\sum_{t=0}^{2k-2} a_t\, (1 - P_1)^{2s-2-t} P_1^{t}\right] \end{align*} Now using Lemma (ref) (where $s$ is replaced by $2s-1$) we know that for any value of $0 \leq r \leq 2s-2$ we have \begin{equation} \mathbf{E} \left[\sum_{t=0}^{r} b_t\, (1 - P_1)^{2s-2-r} P_1^{r}\right] = \mathbf{E} \left[\sum_{t=0}^{r} \binom{2s-2}{t}\, (1 - P_1)^{2s-2-t} P_1^{t}\right] = \frac{r+1}{2s-1}\,. \end{equation} This implies that for any value of $r$ we have $\mathbf{E} \left[b_r (1 - P_1)^{2s-2-r} P_1^{r}\right] = 1/(2s-1)$. The reason is simple. Note that the above is obvious for $r=0$ using Equation (ref). For other values of $r \geq 1$, we can write Equation (ref) for values $r$ and $r-1$. Taking their difference implies the result. Note that this further implies that $\mathbf{E} \left[(1 - P_1)^{2s-2-r} P_1^{r}\right] = 1/(b_r\,(2s-1))$, as $b_r$ is a constant. Therefore, by plugging this back into the expression of $\mathbf{E}[\mathbf{E}[S_1 \mid X_1]^2]$ we have \begin{equation*} \mathbf{E}[\mathbf{E}[S_1|X_1]^2] = \mathbf{E} \left[ \sum_{t=0}^{2k-2} a_t\, (1 - P_1)^{2s-2-t} P_1^{t}\right] = \frac{1}{2s-1} \left( \sum_{t=0}^{2k-2} \frac{a_t}{b_t}\right)\,, \end{equation*} which implies the desired result. \begin{remark} Note that $b_t = \binom{2s-2}{t}$ since we can view $b_t$ as follows: how many different subsets of size $t$ can we create from a set of $2s-2$ elements if we pick a number $i=\{0,\ldots,t\}$ and then choose $i$ elements from the first half of these elements and $t-i$ elements from the second half. Observe that this process creates all possible sets of size $t$ from among the $2s-2$ elements, which is equal to $\binom{2s-2}{t}$. Furthermore, $a_t = b_t $ for $0 \leq t \leq k-1$ and for any $k \leq t \leq 2k-2$, after some little algebra, we have \begin{equation*} \frac{2k-1-t}{t+1} \leq \frac{a_t}{b_t} \leq 1\,. \end{equation*} This implies that the summation appeared in Lemma (ref) satisfies \begin{equation*} k + \sum_{t=k}^{2k-2} \frac{2k-1-t}{t+1} \leq \sum_{t=0}^{2k-2} \frac{a_t}{b_t} \leq 2k-1\,. \end{equation*} \end{remark} \subsection{Proof of Theorem (ref)} Note that according to Lemma (ref), the asymptotic variance $\sigma_{n,j}^2(x)=\frac{s^2}{n}\operatorname{Var}\left[\Phi_1(Z_1)\right]$, where $\Phi_1(Z_1) = \frac{1}{k} \mathbf{E}[\sum_{i \in H_k(x,s)} \left\langle e_j, M_0^{-1}\psi(Z_i;\theta(x))\right\rangle \mid Z_1]$. Therefore, once we establish an expression for $\operatorname{Var}\left[\Phi_1(Z_1)\right]$ we can finish the proof of this theorem. The following lemma provides such result. \begin{lemma} Suppose that the kernel $K$ is the $k$-NN kernel and let $\sigma_j^2(x) = \operatorname{Var}\left(\left\langle e_j, M_0^{-1}\psi(z;\theta(x))\right\rangle \mid X=x\right)$. Moreover, suppose that $\epsilon_{k}(s, 1/s^2)\rightarrow 0$ for any constant $k$. Then: \begin{equation*} \operatorname{Var}\left[\Phi_1(Z_1)\right] = \sigma_j(x)^2\,\mathbf{E}\left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]^2\right]ight]^2} + o(1/s) = \frac{\sigma_j^2(x)}{(2s-1) k^2}\, \left(\sum_{t=0}^{2k-2} \frac{a_t}{b_t}\right) + o(1/s)\, \end{equation*} where the second equality above holds due to Lemma (ref) and sequences $a_t$ and $b_t$, for $0 \leq t \leq 2k-2$, are defined in Lemma (ref). \end{lemma} \begin{proof} In this proof for simplicity we let $Y_i = \left\langle e_j, M_0^{-1} \psi(Z_i;\theta(x))\right\rangle$ and $\mu(X_i) = \mathbf{E}[Y_i] = \left\langle e_j, M_0^{-1}m(X_i;\theta(x))\right\rangle$. Let $Z_{(i)}$ denote the random variable of the $i$-th closest sample to $x$. For the case of $k$-NN we have that: \begin{align*} k\,\Phi_1(Z_1) = \mathbf{E}\left[\sum_{i=1}^k Y_{(i)} \mid Z_1\right]\,. \end{align*} Let $S_1 = \mathbf{1}\{\text{sample 1 is among $k$ nearest neighbors}\}$. Then we have: \begin{align*} k\,\Phi_1(Z_1) = \mathbf{E}\left[S_1 \sum_{i=1}^k Y_{(i)} \mid Z_1\right] + \mathbf{E}\left[(1-S_1)\sum_{i=1}^k Y_{(i)} \mid Z_1\right]\,. \end{align*} Let $\tilde{Y}_{(i)}$ denote the label of the $i$-th closest point to $x$, excluding sample $1$. Then: \begin{align*} k\, \Phi_1(Z_1) = & \mathbf{E}\left[S_1 \sum_{i=1}^k Y_{(i)} \mid Z_1\right] + \mathbf{E}\left[(1-S_1)\sum_{i=1}^k \tilde{Y}_{(i)} \mid Z_1\right]\\ = &\mathbf{E}\left[S_1 \sum_{i=1}^k \left(Y_{(i)} - \tilde{Y}_{(i)}\right) \mid Z_1\right] + \mathbf{E}\left[\sum_{i=1}^k \tilde{Y}_{(i)}\mid Z_1\right]\,. \end{align*} Observe that $\tilde{Y}_{(i)}$ are all independent of $Z_1$. Hence: \begin{align*} k\,\Phi_1(Z_1) = & \mathbf{E}\left[S_1 \sum_{i=1}^k \left(Y_{(i)} - \tilde{Y}_{(i)}\right) \mid Z_1\right] + \mathbf{E}\left[\sum_{i=1}^k \tilde{Y}_{(i)}\right]\,. \end{align*} Therefore the variance of $\Phi(Z_1)$ is equal to the variance of the first term on the right hand side. Hence: \begin{align*} k^2\,\operatorname{Var}\left[\Phi_1(Z_1)\right] = & \mathbf{E}\left[\mathbf{E}\left[S_1 \sum_{i=1}^k \left(Y_{(i)} - \tilde{Y}_{(i)}\right) \mid Z_1\right]^2\right]ight]^2} - \mathbf{E}\left[S_1 \sum_{i=1}^k \left(Y_{(i)} - \tilde{Y}_{(i)}\right)\right]^2\\ = & \mathbf{E}\left[\mathbf{E}\left[S_1 \sum_{i=1}^k \left(Y_{(i)} - \tilde{Y}_{(i)}\right) \mid Z_1\right]^2\right]ight]^2} + o(1/s)\,. \end{align*} Where we used the fact that: \begin{equation} \left|\mathbf{E}\left[S_1 \sum_{i=1}^k \left(Y_{(i)} - \tilde{Y}_{(i)}\right)\right]\right| \leq \mathbf{E}\left[S_1\right] 2k\psi_{\max} = \frac{2k^2\psi_{\max}}{s}\,. \end{equation} Moreover, observe that under the event that $S_1=1$, we know that the difference between the closest $k$ values and the closest $k$ values excluding $1$ is equal to the difference between the $Y_1$ and $Y_{(k+1)}$. Hence: \begin{align*} \mathbf{E}\left[S_1 \sum_{i=1}^k \left(Y_{(i)} - \tilde{Y}_{(i)}\right)\mid Z_1\right] = \mathbf{E}\left[S_1 \left(Y_{1} - Y_{(k+1)}\right) \mid Z_1\right] = \mathbf{E}\left[S_1 \left(Y_{1} - \mu(X_{(k+1)})\right) \mid Z_1\right]\,. \end{align*} where the last equation holds from the fact that for any $j\neq 1$, conditional on $X_{j}$, the random variable $Y_{j}$ is independent of $Z_1$ and is equal to $\mu(X_j)$ in expectation. Under the event $S_1=1$, we know that the $(k+1)$-th closest point is different from sample $1$. We now argue that up to lower order terms, we can replace $\mu(X_{(k+1)})$ with $\mu(X_{1})$ in the last equality: \begin{align*} \mathbf{E}\left[S_1 \left(Y_{1} - \mu(X_{(k+1)})\right) \mid Z_1\right] = & \underbrace{\mathbf{E}\left[S_1 \left(Y_{1} - \mu(X_{1})\right) \mid Z_1\right]}_{A} + \underbrace{\mathbf{E}\left[S_1 \left(\mu(X_{1}) - \mu(X_{(k+1)})\right) \mid Z_1\right]}_{\rho}\,. \end{align*} Observe that: \begin{align*} \mathbf{E}\left[\mathbf{E}\left[S_1 \left(Y_{1} - \mu(X_{(k+1)})\right) \mid Z_1\right]^2\right]ight]^2} = \mathbf{E}[A^2] + \mathbf{E}[\rho^2] + 2\mathbf{E}[A\rho]\,. \end{align*} Moreover, by Jensen's inequality, Lipschitzness of the first moments and kernel shrinkage: \begin{align*} \left|\mathbf{E}[\rho^2]\right| = & \mathbf{E}\left[\mathbf{E}\left[S_1 \left(\mu(X_{1}) - \mu(X_{(k+1)})\right) \mid Z_1\right]^2\right]ight]^2} \leq \mathbf{E}\left[S_1 \left(\mu(X_{1}) - \mu(X_{(k+1)})\right)^2\right]\\ \leq & 4L_m^2\epsilon_{k+1}(s,\delta)^2 \mathbf{E}[\mathbf{E}[S_1|X_1]] + 4 \delta \psi_{\max}^2 \leq 4L_m^2 \epsilon_{k+1}(s,\delta)^2 \frac{k}{s} + 4 \delta \psi_{\max}^2\,. \end{align*} Hence, for $\delta=1/s^2$, the latter is $o(1/s)$. Similarly: \begin{align*} |\mathbf{E}[A\rho]|\leq \mathbf{E}[|A|\, |\rho|] \leq & \psi_{\max} \mathbf{E}\left[\mathbf{E}\left[S_1 \left|\mu(X_{1}) - \mu(X_{(k+1)}\right|\mid Z_1\right]\right]\right]} = \psi_{\max} \mathbf{E}\left[S_1 \left|\mu(X_{1}) - \mu(X_{(k+1)}\right|\right]\\ \leq & \psi_{\max} \mathbf{E}[S_1]\epsilon_{k+1}(s,\delta) + 2\delta \psi_{\max} = \psi_{\max} \epsilon_{k+1}(s,\delta) \frac{k}{s} + 2\delta \psi_{\max} \,. \end{align*} which for $\delta=1/s^2$ is also of order $o(1/s)$. Combining all the above we thus have: \begin{align*} k^2\,\operatorname{Var}\left[\Phi_1(Z_1)\right] = & \mathbf{E}\left[\mathbf{E}\left[S_1 \left(Y_{1} - \mu(X_{1})\right) \mid Z_1\right]^2\right]ight]^2} + o(1/s)\\ = & \mathbf{E}\left[\mathbf{E}\left[S_1\mid X_1\right]^2 \left(Y_{1} - \mu(X_{1})\right)^2\right]{1})}^2} + o(1/s)\,. \end{align*} We now work with the first term on the right hand side. By the tower law of expectations: \begin{align*} \mathbf{E}\left[\mathbf{E}[S_1 \mid X_1]^2 \left(Y_1 - \mu(X_1)\right)^2\right] = & \mathbf{E}\left[\mathbf{E}[S_1 \mid X_1]^2 \mathbf{E}\left[Y_1 - \mu(X_1)^2\mid X_1\right]\right]\right]} = \mathbf{E}\left[\mathbf{E}[S_1 \mid X_1]^2 \sigma_j^2(X_1)\right]\\ = & \mathbf{E}\left[\mathbf{E}[S_1 \mid X_1]^2 \sigma_j^2(x)\right] + \mathbf{E}\left[\mathbf{E}[S_1 \mid X_1]^2 \left(\sigma_j^2(X_1) - \sigma_j^2(x)\right)\right]\,. \end{align*} By Lipschitzness of the second moments, we know that the second part is upper bounded as: \begin{align*} \left|\mathbf{E}\left[\mathbf{E}[S_1 \mid X_1]^2 \left(\sigma_j^2(X_1) - \sigma_j^2(x)\right)\right]\right| \leq & \left|\mathbf{E}\left[\mathbf{E}[S_1 \mid X_1] \left(\sigma_j^2(X_1) - \sigma_j^2(x)\right)\right]\right|\\ \leq & \left|\mathbf{E}\left[S_1 \left(\sigma_j^2(X_1) - \sigma_j^2(x)\right)\right]\right|\\ = & \left|\mathbf{E}\left[S_1 \left(\sigma_j^2(X_{(k)}) - \sigma_j^2(x)\right)\right]\right|\\ \leq & L_{mm}\mathbf{E}\left[S_1\right] \epsilon_k(s,\delta) + \delta \psi_{\max}^2\\ = & \frac{L_{mm}\, \epsilon_k(s, \delta)\, k}{s} + \delta \psi_{\max}^2\,. \end{align*} For $\delta=1/s^2$ it is of $o(1/s)$. Thus: \begin{align*} k^2\, \operatorname{Var}\left[\Phi_1(Z_1)\right] = \mathbf{E}\left[\mathbf{E}[S_1 \mid X_1]^2\right] \sigma_j^2(x) + o(1/s)\,. \end{align*} Note that Lemma (ref) provides an expression for $\mathbf{E} \left[\mathbf{E}[S_1 \mid X_1]^2\right]$ which finishes the proof. \end{proof} For finishing proof of Theorem (ref) we need to prove that $\sum_{t=0}^{2k-2} \frac{a_t}{b_t}$ is equal to $\zeta_k$ plus lower order terms. This is proved in the following lemma. \begin{lemma} Suppose that $s \rightarrow \infty$ and $k$ is fixed. Then \begin{equation*} \sum_{t=0}^{2k-2} \frac{a_t}{b_t} = \zeta_k + O(1/s)\,. \end{equation*} \begin{proof} Note that for any $0 \leq t \leq k-1$ we have $a_t = b_t$ according to Remark (ref). For any $k \leq t \leq 2k-2$ we have \begin{align*} \frac{a_t}{b_t} &= \sum_{i=t-k+1}^{k-1} \frac{\binom{s-1}{i} \binom{s-1}{t-i}}{\binom{2s-2}{t}} = \sum_{i=t-k+1}^{k-1} \frac{\frac{(s-1)(s-2)\ldots(s-i)}{i\,!} \frac{(s-1)(s-2)\ldots(s-t+i)}{(t-i)\,!}}{\frac{(2s-2)(2s-3)\ldots(2s-1-t)}{t\,!}} \\ &= \sum_{i=t-k+1}^{k-1} \binom{t}{i} \frac{(s-1)(s-2)\ldots(s-i)\, \, (s-1)(s-2)\ldots(s-t+i)}{(2s-2)(2s-3)\ldots(2s-1-t)} \\ &= \sum_{i=t-k+1}^{k-1} \binom{t}{i} \frac{s-1}{2s-2} \frac{s-2}{2s-3} \cdots \frac{s-i}{2s-1-i}\,\frac{s-1}{2s-i}\frac{s-2}{2s-i-1} \cdots \frac{s-t+i}{2s-1-t} \\ &= \sum_{i=t-k+1}^{k-1} 2^{-t} \binom{t}{i} \left(1-\frac{1}{2s-3}\right) \cdots \left(1-\frac{i-1}{2s-1-i}\right) \, \left(1+\frac{i-2}{2s-i}\right) \cdots \left(1+\frac{i-(i-t+1)}{2s-1-t}\right) \\ &= 2^{-t} \sum_{i=t-k+1}^{k-1} \binom{t}{i} (1+O(1/s)) \\ &= 2^{-t} \sum_{i=t-k+1}^{k-1} \binom{t}{i} + O(1/s)\,, \end{align*} where we used the fact that $t$ and $i$ are both bounded above by $2k-2$ which is a constant. Hence, \begin{equation*} \sum_{t=0}^{2k-2} \frac{a_t}{b_t} = k + \sum_{t=k}^{2k-2} 2^{-t} \sum_{i=t-k+1}^{k-1} \binom{t}{i} + O(1/s) = \zeta_k + O(1/s)\,, \end{equation*} as desired. \end{proof} \end{lemma} \subsection{Proof of Theorem (ref)} The goal is to apply Theorem (ref). Note that $k$-NN kernel is both honest and symmetric. According to Lemma (ref), we have that $\epsilon_k(s,\delta) = O\left( (\log(1/\delta)/s)^{1/d}\right)$ for $\exp(-Cs) \leq \delta \leq D$, where $C$ and $D$ are constants. Corollary (ref) also implies that $\epsilon_k(s) = O((1/s)^{1/d})$. Furthermore, according to Lemma (ref), the incrementality $\eta_k(s)$ is $\Theta(1/s)$. Therefore, as $s$ goes to $\infty$ we have $\epsilon_k(s,\eta_k(s)) = O\left((\log(s)/s)^{1/d}\right) \rightarrow 0$. Moreover, as $\eta_k(s) = \Theta(1/s)$, we also get that $n \eta_k(s) = O(n/s) \rightarrow \infty$. We only need to ensure that Equation (ref) is satisfied. Note that $\sigma_{n,j}(x) = \Theta(\sqrt{s/n})$. Therefore, by dividing terms in Equation (ref) it suffices that \begin{equation*} \max \left(s^{-1/d} \left(\frac{n}{s}\right)^{1/2}, s^{-1/4d} \left(\log\log(n/s) \right)^{1/2}, \left(\frac{n}{s}\right)^{-1/8} \, \left(\log\log(n/s)\right)^{5/8}\right)left(\log\log(n/s)\right)^{5/8}} = o(1)\,. \end{equation*} Note that due to our Assumption $n/s \rightarrow \infty$, the last term obviously goes to zero. Also, because of the assumption made in the statement of theorem, the first term also goes to zero. We claim that if the first term goes to zero, the same also holds for the second term. Note that we can write \begin{equation*} s^{-1/4d} \left(\log\log(n/s) \right)^{1/2} = \left(s^{-1/d} \left(\frac{n}{s}\right)^{1/2}\right))^{1/2}}^{1/4} \cdot \left[\left(\frac{n}{s}\right)^{-1/8} \, \left(\log\log(n/s)\right)^{1/2}\right]\,, \end{equation*} and since $n/s \rightarrow \infty$, our claim follows. Therefore, all the conditions of Theorem (ref) are satisfied and the result follows. The second part of result is implied by the first part since if $s = n^{\beta}$ and $\beta \in (d/(d+2),1)$ then $s^{-1/d} \sqrt{\frac{n}{s}} \rightarrow 0$. \subsection{Proof of Proposition (ref)} For proving this lemma, we need two following auxiliary results. Before that we state the Hoeffding's inequality for $U$-statistics hoeffding1994probability. \begin{proposition} Suppose that $\mathbf{X} = \left(X_1,X_2,\ldots,X_n\right)$ are i.i.d. and $q$ is a function that has range $[0,1]$. Define $U_s = \binom{n}{s}^{-1} \sum_{i_1 < i_2 < \ldots < i_s} q(X_{i_1},X_{i_2},\ldots, X_{i_s})$. Then, for any $\epsilon > 0$ \begin{equation*} \Pr \left[|U_s - \mathbf{E}[U_s]| \geq \epsilon\right] \leq 2 \exp \left(-\lfloor{n/s \rfloor} \epsilon^2\right)\,. \end{equation*} Furthermore, for any $\delta>0$, w.p. $1-\delta$ we have \begin{equation*} |U_s - \mathbf{E}[U_s]| \leq \sqrt{\frac{1}{\lfloor{n/s \rfloor}} \log(2/\delta)}\,. \end{equation*} \end{proposition} \begin{lemma} Consider the function $H(s)$ defined in Section (ref) and $G_\delta(s) = \Delta \sqrt{2ps/n \log(2np/\delta)}$. Then, w.p. $1-\delta$, for all values of $k \leq s \leq n$ we have \begin{equation*} |H(s) - \epsilon_k(s)| \leq G_\delta(s)\,. \end{equation*} \begin{proof} Note that $H(s)$ is the complete $U$-statistic estimator for $\epsilon_k(s)$. For each subset $S$ of size $s$ from $[n]$ we have \begin{equation*} \mathbf{E}[\max_{X_i \in H_k(x,S)} \|x-X_i\|_2] = \epsilon_k(s)\,. \end{equation*} Further, $\|x-x'\|_2 \leq \Delta_{\mathcal{X}} \leq \Delta$ holds for any $x' \in \mathcal{X}$. Therefore, using Hoeffding's inequality for $U$-statistics stated in Proposition (ref), for any fixed $s$, w.p. $1-\delta$ we have \begin{equation*} |H(s) - \epsilon_k(s)| \leq \Delta \sqrt{\frac{1}{\lfloor{n/s \rfloor}} \log(2/\delta)}\,. \end{equation*} Note that $\lfloor{z \rfloor} \geq z/2$ for $z \geq 1$ and therefore the above translates to \begin{equation*} |H(s) - \epsilon_k(s)| \leq \Delta \sqrt{\frac{2s}{n} \log(2/\delta)}\,. \end{equation*} Taking a union bound over $s=k,k+1,\ldots,n$, replacing $\delta = \delta/n$, and using $p \geq 1$, implies the result. \end{proof} \end{lemma} \begin{lemma} Consider the selection process mentioned in Section (ref) and let $s_1$ be the output of this process. Then, w.p. $1-\delta$ we have \begin{equation*} \frac{s^*-1}{9} \leq s_1 \leq s^*\,. \end{equation*} \end{lemma} \begin{proof} Note that using Lemma (ref), w.p. $1-\delta$, for all values of $s$ we have $|H(s)-\epsilon_k(s)| \leq G_\delta(s)$. Now consider three different cases: \begin{itemize} • $s_1 \geq s_2 \geq s^*:$ Note that based on the choice of $s_1,s_2$, we have $H(s_2) > 2G_\delta(s_2)$. However, $H(s_2) \leq \epsilon_k(s_2) + G_\delta(s_2)$. Hence, $\epsilon_k(s_2) > G_\delta(s_2)$ which contradicts with the assumption that $s_2 \geq s^*$. Note that this is true since $\epsilon_k(s) - G_\delta(s)$ is non-positive for $s \geq s^*$. • $s_1 = s^*, s_2 = s^*-1:$ Obviously $s_1 \leq s^*$. • $s_2 \leq s_1\leq s^*-1:$ Note that we have \begin{equation*} \epsilon_k(s_1) - G_\delta(s_1) \leq H(s_1) \leq 2G_\delta(s_1)\,. \end{equation*} Hence, $G_\delta(s^*-1) < \epsilon_k(s^*-1) \leq \epsilon_k(s_1) \leq 3G_\delta(s_1)$. This means that $G_\delta(s^*-1)/G_\delta(s_1) \leq 3$ which implies $\sqrt{(s^*-1)/s_1} \leq 3$. Therefore, $s_1 \geq (s^*-1)/9$. \end{itemize} This completes the proof. \end{proof} Now we are ready to finalize the proof of Theorem (ref). Note that using the result of Lemma (ref), w.p. $1-\delta$, we have \begin{equation*} \frac{s^*-1}{9} \leq s_1 \leq s^* \,. \end{equation*} This basically means that if $s_* = 9s_1+1$, then $s_*$ belongs to $[s^*, 10s^*]$. Hence, we have $\epsilon_k(s_*) \leq \epsilon_k(s^*) \leq G_\delta(s^*)$ and $G_\delta(s_*) \leq G_\delta(10s^*) = \sqrt{10} G_\delta(s^*)$. Now using Theorem (ref), for $B \geq n/s_*$ w.p. $1-\delta$ we have \begin{equation*} \|\hat{\theta} - \theta(x)\|_2 \leq \frac{2}{\lambda}\left(L_m \epsilon(s_*) + O\left(\psi_{\max}\sqrt{\frac{p\, s_*}{n} \left(\log\log(n /s_*) + \log(p/\delta)\right)}\right)\right)\right)}\,. \end{equation*} Note that $G_\delta(s_*) = \Delta \sqrt{\frac{2ps_*}{n}\log(2pn/\delta)}$. Therefore, \begin{equation*} \sqrt{\frac{p\, s_*}{n} \left(\log\log(n /s_*) + \log(p/\delta)\right)} \leq G_\delta(s_*) \leq \sqrt{10} G_\delta(s^*)\,. \end{equation*} Replacing this in above equation together with a union bound implies that w.p. at least $1-2 \delta$ we have \begin{equation*} \|\hat{\theta} - \theta(x)\|_2 = O(G_\delta(s^*))\,, \end{equation*} which finishes the first part of the proof. For the second part, note that according to Corollary (ref), for the $k$-NN kernel $\epsilon(s) \leq C s^{-1/d}$, for a constant $C$. Note that at $s=s^*-1$ we have \begin{equation*} \Delta \sqrt{\frac{2ps}{n} \log(2np/\delta)} = \epsilon_k(s) \leq Cs^{-1/d}\,, \end{equation*} for a constant $C$. The above implies that \begin{equation*} s^* \leq 1 + \left(\frac{C}{\Delta}\right)^{2d/(d+2)} \left(\frac{n}{2p\log(2np/\delta)}\right)^{d/(d+2)} \leq 2 \left(\frac{C}{\Delta}\right)^{2d/(d+2)} \left(\frac{n}{2p\log(2np/\delta)}\right)^{d/(d+2)}\,. \end{equation*} Hence, \begin{equation*} G_\delta(s^*) \leq \sqrt{2} \Delta^{2/(d+2)} C^{d/(d+2)} \left(\frac{n}{2p\log(2np/\delta)}\right)^{-1/(d+2)}\,. \end{equation*} \begin{remark} Note that although computation of $H(s)$ may look complex as it involves calculation of distance to $k$-nearest neighbor of $x$ on all $\binom{n}{s}$ subsets, there is a closed form representation for $H(s)$ according to its representation based on $L$-statistic. In fact, by sorting samples $(X_1,X_2,\ldots,X_n)$ based on their distance to $x$, i.e, $\|x-X_{(1)}\|_2 \leq \|x-X_{(2)}\|_2 \leq \ldots \leq \|x-X_{(n)}\|_2$, we have \begin{equation*} H(s) = \binom{n}{s}^{-1} \sum_{i=k}^{n-s+k} \binom{i-1}{k-1}\binom{n-i}{s-k} \|x-X_{(i)}\|_2\,. \end{equation*} Therefore, after sorting training samples, we can compute values of $H(s)$ very efficient and fast. \end{remark} \subsection{Proof of Proposition (ref)} Note that according to Lemma (ref), w.p. $1-1/n$, the output of process, $s_1$ satisfies \begin{equation*} \frac{s^*-1}{9} \leq s_1 \leq s^*\,, \end{equation*} where $s^*$ is the point for which we have $\epsilon_k(s^*) = G_{1/n}(s^*)$. This basically means that $s_* = 9s_1+1 \geq s^*$. Note that for the $k$-NN kernel we have $\eta_k(s) = \Theta(1/s)$. As $s_\zeta \geq n^{\zeta}$, this also implies that $\epsilon_k(s_\zeta,\eta_k(s_\zeta)) = O((\log(s_\zeta)/s_\zeta)^{1/d}) \rightarrow 0$. Also, according to the inequality $\zeta < \frac{\log(n) - \log(s_*)-\log\log^2(n)}{\log(n)}$ we have $1-\zeta > (\log(s_*)+\log\log^2(n))/\log(n)$ and therefore \begin{equation*} n^{1-\zeta} \geq s_\zeta \log^2(n) \rightarrow \frac{s_\zeta}{n} \leq \frac{1}{\log^2(n)}\,, \end{equation*} and hence $n \eta_k(s_\zeta) \rightarrow 0$. Finally, note that $\sigma_{n,j}(x) = \Theta(\sqrt{s/n})$ and according to Theorem (ref) it suffices that \begin{equation*} \max \left(\epsilon_k(s_\zeta) \left(\frac{s_\zeta}{n}\right)^{-1/2}, \epsilon_k(s_\zeta)^{1/4} \left(\log\log(n/s_\zeta)\right)^{1/2}, \left(\frac{s_\zeta}{n}\right)^{1/8} \left(\log\log(n/s_\zeta)\right)^{5/8}\right)log\log(n/s_\zeta)\right)^{5/8}} = o(1)\,. \end{equation*} Note that for any $\zeta>0, s_\zeta \geq s^*$ and therefore $\epsilon_k(s_\zeta) \leq \epsilon_k(s^*) = G_{1/n}(s^*)$. For the first term, \begin{align*} \epsilon_k(s_\zeta) \left(\frac{s_\zeta}{n}\right)^{-1/2} &\leq G_{1/n}(s^*) \left(\frac{s_\zeta}{n}\right)^{-1/2} \\ &= \Delta \sqrt{\frac{2p \,s^*}{n} \log(2n^2/p)} \, \,\left(\frac{s_\zeta}{n}\right)^{-1/2} \\ &=O \left(\sqrt{\frac{s^*}{s_\zeta}} \log(n)\right). \end{align*} Now note that $s_\zeta = s_* n^\zeta \geq s^* n^{\zeta}$ and hence $\sqrt{s^*/s_\zeta} \log(n) = O(n^{-\zeta/2} \log(n)) \rightarrow 0$. For the second term, note that again $s_\zeta \geq s^*$ and therefore $\epsilon_k(s_\zeta) \leq \epsilon_k(s^*) = G_{1/n}(s^*) \leq G_{1/n}(s_\zeta)$. Now note that since $s_\zeta/n \leq 1/\log^2(n)$ hence \begin{equation*} \epsilon_k(s_\zeta)^{1/4} \log \log(n/s_\zeta)^{1/2} \leq G_{1/n}(s_\zeta) \log\log(n) = O \left( \left(\frac{\log(n)}{\log^2(n)}\right)^{1/8} \log\log(n)\right)\log(n)} \rightarrow 0\,. \end{equation*} Finally, for the last term we have $s_\zeta/n \leq 1/\log^2(n)$ and hence \begin{equation*} \left(\frac{s_\zeta}{n}\right)^{1/8} \left(\log\log(n/s_\zeta)\right)^{5/8} \leq \left(\frac{1}{\log(n)}\right)^{1/4} \log\log(n) \rightarrow 0. \end{equation*} This basically means w.p. $1-1/n$, $s_\zeta$ belongs to the interval for which the asymptotic normality result in Theorem (ref) holds. As $n \rightarrow \infty$, the conclusion follows. \section{Stochastic Equicontinuity of $U$-statistics via Bracketing} We define here some standard terminology on bracketing numbers in empirical process theory. Consider an arbitrary function space $\mathcal{F}$ of functions from a data space $\mathcal{Z}$ to $\mathbb{R}$, equipped with some norm $\|\cdot\|$. A \emph{bracket} $[a, b]\subseteq \mathcal{F}$, where $a,b:\mathcal{Z}\rightarrow \mathbb{R}$ consists of all functions $f\in \mathcal{F}$, such that $a\leq f \leq b$. An \emph{$\epsilon$-bracket} is a bracket $[a, b]$ such that $\|a - b\|\leq \epsilon$. The \emph{bracketing number} $N_{[]}(\epsilon, \mathcal{F}, \|\cdot\|)$ is the minimum number of $\epsilon$-brackets needed to cover $\mathcal{F}$. The functions $[a,b]$ used in the definition of the brackets need not belong to $\mathcal{F}$ but satisfy the same norm constraints as functions in $\mathcal{F}$. Finally, for an arbitrary measure $P$ on $\mathcal{Z}$, let \begin{align} \|f\|_{P,2} = & \sqrt{\mathbf{E}_{Z\sim P}[f(Z)^2]} & \|f\|_{P,\infty} = \sup_{z \in \text{ support}(P)} |f(z)| \end{align} \begin{lemma}[Stochastic Equicontinuity for $U$-statistics via Bracketing] Consider a function space ${\cal F}$ of symmetric functions from some data space $\mathcal{Z}^s$ to $\mathbb{R}$ and consider the $U$-statistic of order $s$, with kernel $f$ over $n$ samples: \begin{equation} \Psi_s(f, z_{1:n}) = \binom{n}{s}^{-1} \sum_{1\leq i_1\leq \ldots \leq i_s \leq n} f(z_{i_1},\ldots, z_{i_s}) \end{equation} Suppose $\sup_{f\in \mathcal{F}} \|f\|_{P,2} \leq \eta$, $\sup_{f \in \mathcal{F}} \|f\|_{P,\infty}\leq G$ and let $\kappa=n/s$. Then for $\kappa \geq \frac{G^2}{\log N_{[]}(1/2,\mathcal{F}, \|\cdot\|_{P,2})}$, w.p. $1-\delta$: \begin{multline*} \sup_{f \in \mathcal{F}} |\Psi_s(f, Z_{1:n}) - \mathbf{E}[f(Z_{1:s})]| \\ = O\left( \inf_{\rho>0} \frac{1}{\sqrt{\kappa}}\int_{\rho}^{2\eta}\sqrt{\log(N_{[]}(\epsilon, \mathcal{F}, \|\cdot\|_{P,2})} + \eta \sqrt{\frac{\log(1/\delta) + \log\log(\eta/\rho)}{\kappa}} + \rho\right) \end{multline*} \end{lemma} \begin{proof} Let $\kappa=n/s$. Moreover, wlog we will assume that $\mathcal{F}$ contains the zero function, as we can always augment $\mathcal{F}$ with the zero function without changing the order of its bracketing number. For $q=1,\ldots,M$, let $\mathcal{F}_q=\cup_{i=1}^{N_q}\mathcal{F}_{qi}$ be a partition of $\mathcal{F}$ into brackets of diameter at most $\epsilon_q = 2\eta/2^{q}$, with $\mathcal{F}_0$ containing a single partition of all the functions. Moreover, we assume that $\mathcal{F}_q$ are nested partitions. We can achieve the latter as follows: i) consider a minimal bracketing cover of $\mathcal{F}$ of diameter $\epsilon_q$, ii) assign each $f\in \mathcal{F}$ to one of the brackets that it is contained arbitrarily and define the partition $\bar{\mathcal{F}}_q$ of size $\bar{N}_q= N_{[]}(\epsilon_q, \mathcal{F}, \|\cdot\|_{P,2})$, by taking $\mathcal{F}_{qi}$ to be the functions assigned to bracket $i$, iii) let $\mathcal{F}_q$ be the common refinement of all partitions $\bar{\mathcal{F}}_0, \ldots, \bar{\mathcal{F}}_q$. The latter will have size at most $N_q \leq \prod_{q=0}^M \bar{N}_q$. Moreover, assign a representative function $f_{qi}$ to each partition $\mathcal{F}_{qi}$, with the representative for the single partition at level $q=0$ is the zero function. \paragraph{Chaining definitions.} Consider the following random variables, where the dependence on the random input $Z$ is hidden: \begin{align*} \pi_q f = & f_{qi}, \quad \text{if $f\in \mathcal{F}_{qi}$}\\ \Delta_q f = & \sup_{g, h\in \mathcal{F}_{qi}} |g - h|, \quad \text{if $f\in \mathcal{F}_{qi}$}\\ B_q f = & \{\Delta_0 f\leq \alpha_0, \ldots, \Delta_{q-1} f\leq \alpha_{q-1}, \Delta_q f>\alpha_q\}\\ A_q f = & \{\Delta_0 f\leq \alpha_0, \ldots, \Delta_q f \leq \alpha_q\}\,, \end{align*} for some sequence of numbers $\alpha_0, \ldots, \alpha_M$, to be chosen later. By noting that $A_{q-1} f = A_{q} f + B_{q} f$ and continuously expanding terms by adding and subtracting finer approximations to $f$, we can write the telescoping sum: \begin{align*} f - \pi_0 f = & (f - \pi_0 f)\, B_0 f + (f-\pi_0 f) A_0 f\\ = & (f - \pi_0 f)\, B_0 f + (f - \pi_1 f)A_0 f + (\pi_1 f - \pi_0 f) A_0 f\\ = & (f - \pi_0 f)\, B_0 f + (f - \pi_1 f)B_1 f + (f - \pi_1 f) A_1f + (\pi_1 f - \pi_0 f) A_0 f\\ \ldots\\ = & \sum_{q=0}^M (f-\pi_q f) B_q f + \sum_{q=1}^{M} (\pi_{q} f - \pi_{q-1} f) A_{q-1} f + (f - \pi_M f) A_M f\,. \end{align*} For simplicity let $\mathbb{P}_{s,n} f = \Psi(f,Z_{1:n})$, $\mathbb{P} f = E[f(Z_{1:s})]$ and $\mathbb{G}_{s,n}$ denote the $U$-process: \begin{equation} \mathbb{G}_{s,n} f = \mathbb{P}_{s,n} f - \mathbb{P} f\,. \end{equation} Our goal is to bound $\|\mathbb{P}_{s,n} f\|_{\mathcal{F}}=\sup_{f\in \mathcal{F}} |\mathbb{P}_{s,n} f|$, with high probability. Observe that since $\mathcal{F}_0$ contains only the zero function, then $\mathbb{G}_{s,n} f_0 = 0$. Moreover, the operator $\mathbb{G}_{s,n}$ is linear. Thus: \begin{align*} \mathbb{G}_{s,n} f = \mathbb{G}_{s,n} (f - \pi_0 f) = \sum_{q=0}^M \mathbb{G}_{s,n}(f-\pi_q f) B_q f + \sum_{q=1}^{M} \mathbb{G}_{s,n}(\pi_{q} f - \pi_{q-1} f) A_{q-1} f + \mathbb{G}_{s,n} (f - \pi_M f) A_M f\,. \end{align*} Moreover, by triangle inequality: \begin{align*} \|\mathbb{G}_{s,n} f\|_{\mathcal{F}} \leq \sum_{q=0}^M \|\mathbb{G}_{s,n}(f-\pi_q f) B_q f\|_{\mathcal{F}} + \sum_{q=1}^{M} \|\mathbb{G}_{s,n} (\pi_{q} f - \pi_{q-1} f) A_{q-1} f\|_{\mathcal{F}} + \|\mathbb{G}_{s,n} (f - \pi_M f) A_M f\|_{\mathcal{F}}\,. \end{align*} We will bound each term in each summand separately. \paragraph{Edge cases.} The final term we will simply bound it by $2\alpha_M$, since $|(f - \pi_M f) A_M f|\leq \alpha_M$, almost surely. Moreover, the summand in the first term for $q=0$, we bound as follows. Observe that $B_0 f = 1\{\sup_{f} |f| > \alpha_0\}$. But we know that $\sup_{f} |f| \leq G$, hence: $B_0 f \leq 1\{ G > \alpha_0 \}$. \begin{align*} \mathbb{G}_{s,n}(f-\pi_0 f) B_0 f = \mathbb{G}_{s,n} f B_0 f \leq |\mathbb{P}_{s,n} f B_0 f| + |\mathbb{P} f B_0 f| \leq 2 G\, 1\{G > \alpha_0\}\,. \end{align*} Hence, if we assume that $\alpha_0$ is large enough such that $\alpha_0 > G$, then the latter term is zero. By the setting of $\alpha_0$ that we will describe at the end, the latter would be satisfied if $\kappa \geq \frac{G^2}{\log N_{[]}(1/2,\mathcal{F}, \|\cdot\|_{P,2})}$. \paragraph{$B_q$ terms.} For the terms in the first summand we have by triangle inequality: \begin{align*} |\mathbb{G}_{s,n}(f-\pi_q f) B_q f| \leq & \mathbb{P}_{s,n} |f-\pi_q f| B_q f + \mathbb{P} |f-\pi_q f| B_q f\\ \leq & \mathbb{P}_{s,n} \Delta_q f B_q f + \mathbb{P} \Delta_q f B_q f\\ \leq & \mathbb{G}_{s,n} \Delta_q f B_q f + 2\mathbb{P} \Delta_q f B_q f \,. \end{align*} Moreover, observe that: \begin{align*} \mathbb{P} \Delta_q f B_q f \leq \mathbb{P} \Delta_q f 1\{\Delta_q f > \alpha_q\} \leq \frac{1}{\alpha_q} \mathbb{P} (\Delta_q f)^2 1\{\Delta_q f > \alpha_q\} \leq \frac{1}{\alpha_q} \mathbb{P} (\Delta_q f)^2 = \frac{1}{\alpha_q} \|\Delta_q f\|_{P, 2}^2 \leq \frac{\epsilon_q^2}{\alpha_q}\,, \end{align*} where we used the fact that the partitions in $\mathcal{F}_q$, have diameter at most $\epsilon_q$, with respect to the $\|\cdot\|_{P,2}$ norm. Now observe that because the partitions $\mathcal{F}_q$ are nested, $\Delta_q f \leq \Delta_{q-1} f$. Therefore, $\Delta_q f B_q f\leq \Delta_{q-1}f B_q f \leq \alpha_{q-1}$, almost surely. Moreover, $\|\Delta_q f B_q f\|_{P,2}\leq \|\Delta_q f\|_{P,2}\leq \epsilon_q$. By Bernstein's inequality for $U$ statistics (see e.g. peel2010empirical) for any fixed $f$, w.p. $1-\delta$: \begin{align*} |\mathbb{G}_{s,n} \Delta_q f B_q f| \leq & \epsilon_q \sqrt{\frac{2\log(2/\delta)}{\kappa}} + \alpha_{q-1}\frac{2\log(2/\delta)}{3\kappa}\,. \end{align*} Taking a union bound over the $N_q$ members of the partition, and combining with the bound on $\mathbb{P} \Delta_q f B_q f$, we have w.p. $1-\delta$: \begin{equation} \|\mathbb{G}_{s,n}(f-\pi_q f) B_q f\|_{\mathcal{F}} \leq \epsilon_q \sqrt{\frac{2\log(2N_q /\delta)}{\kappa}} + \alpha_{q-1}\frac{2\log(2N_q/\delta)}{3\kappa} + \frac{2 \epsilon_q^2}{\alpha_q}\,. \end{equation} \paragraph{$A_q$ terms.} For the terms in the second summand, we have that since the partitions are nested, $|(\pi_{q} f - \pi_{q-1} f) A_{q-1} f|\leq \Delta_{q-1} f A_{q-1} f\leq \alpha_{q-1}$. Moreover, $\|(\pi_{q} f - \pi_{q-1} f) A_{q-1} f\|_{P,2} \leq \|\Delta_{q-1} f\|_{P,2} \leq \epsilon_{q-1}\leq 2\epsilon_q$. Thus, by similar application of Bernstein's inequality for $U$-statistics, we have for a fixed $f$, w.p. $1-\delta$: \begin{align*} |\mathbb{G}_{s,n}(\pi_{q} f - \pi_{q-1} f) A_{q-1} f| \leq \epsilon_{q} \sqrt{\frac{8\log(2/\delta)}{\kappa}} + \alpha_{q-1}\frac{2\log(2/\delta)}{3\kappa}\,. \end{align*} As $f$ ranges there are at most $N_{q-1}\, N_{q}\leq N_{q}^2$ different functions $(\pi_{q} f - \pi_{q-1} f) A_{q-1} f$. Thus taking a union bound, we have that w.p. $1-\delta$: \begin{align*} \|\mathbb{G}_{s,n}(\pi_{q} f - \pi_{q-1} f) A_{q-1} f\|_{\mathcal{F}}\leq \epsilon_q \sqrt{\frac{16\log(2N_{q}/\delta)}{\kappa}} + \alpha_{q-1}\frac{4\log(2N_{q}/\delta)}{3\kappa}\,. \end{align*} Taking also a union bound over the $2M$ summands and combining all the above inequalities, we have that w.p. $1-\delta$: \begin{align*} \|\mathbb{G}_{s,n} f\|_{\mathcal{F}} \leq \sum_{q=1}^M \epsilon_q \sqrt{\frac{32\log(2N_{q} M /\delta)}{\kappa}} + \alpha_{q-1}\frac{6\log(2N_{q} M /\delta)}{3\kappa} + \frac{2 \epsilon_q^2}{\alpha_q}\,. \end{align*} Choosing $\alpha_q = \epsilon_q \sqrt{\kappa} / \sqrt{\log(2N_{q+1} M /\delta)}$ for $q<M$ and $\alpha_M=\epsilon_M$, we have for some constant $C$: \begin{align*} \|\mathbb{G}_{s,n} f\|_{\mathcal{F}} \leq & C \sum_{q=1}^M \epsilon_q \sqrt{\frac{\log(2N_{q} M /\delta)}{\kappa}} + 3\epsilon_M\\ \leq & C \sum_{q=1}^M \epsilon_q \sqrt{\frac{\log(N_{q})}{\kappa}} + C\sum_{q=1}^M \epsilon_q \sqrt{\frac{\log(2M/\delta)}{\kappa}} + 3\epsilon_M\\ \leq & C \sum_{q=1}^M \epsilon_q \sqrt{\frac{\log(N_{q})}{\kappa}} + 2C\eta \sqrt{\frac{\log(2M/\delta)}{\kappa}} + 3\epsilon_M\,. \end{align*} Moreover, since $\log(N_q) \leq \sum_{t=0}^q \log(N_{[]}(\epsilon_q, \mathcal{F}, \|\cdot\|_{P,2})$, we have: \begin{align*} \sum_{q=1}^M \epsilon_q \sqrt{\log(N_{q})} \leq & \sum_{q=1}^M \epsilon_q \sum_{t=0}^q \sqrt{\log(N_{[]}(\epsilon_t, \mathcal{F}, \|\cdot\|_{P,2})} = \sum_{t=0}^M \sqrt{\log(N_{[]}(\epsilon_t, \mathcal{F}, \|\cdot\|_{P,2})} \sum_{q=t}^M \epsilon_q\\ \leq & 2\sum_{t=0}^M \epsilon_t \sqrt{\log(N_{[]}(\epsilon_t, \mathcal{F}, \|\cdot\|_{P,2})}\\ \leq & 4\sum_{t=0}^M (\epsilon_t-\epsilon_{t+1}) \sqrt{\log(N_{[]}(\epsilon_t, \mathcal{F}, \|\cdot\|_{P,2})}\\ \leq & 4 \int_{\epsilon_M}^{\epsilon_0}\sqrt{\log(N_{[]}(\epsilon, \mathcal{F}, \|\cdot\|_{P,2})}\,. \end{align*} Combining all the above yields the result. \end{proof} \begin{corollary} Consider a function space ${\cal F}$ of symmetric functions. Suppose that $\sup_{f\in \mathcal{F}} \|f\|_{P,2} \leq \eta$ and $\log(N_{[]}(\epsilon, \mathcal{F}, \|\cdot\|_{P,2})=O(1/\epsilon)$. Then for $\kappa \geq O(G^2)$, w.p. $1-\delta$: \begin{equation} \sup_{f \in \mathcal{F}} |\Psi_s(f, Z_{1:n}) - \mathbf{E}[f(Z)]| = O\left( \sqrt{\frac{\eta}{\kappa}} + \eta \sqrt{\frac{\log(1/\delta) + \log\log(\kappa/\eta)}{\kappa}}\right)\,. \end{equation} \end{corollary} \begin{proof} Applying Lemma (ref), we get for every $\rho>0$, the desired quantity is upper bounded by: \begin{align*} O\left(\frac{1}{\sqrt{\kappa}}\int_{\rho}^{\eta}\frac{1}{\sqrt{\epsilon}} + \eta \sqrt{\frac{\log(1/\delta) + \log\log(\eta/\rho)}{\kappa}} + \rho\right)\\ = O\left(\frac{\sqrt{\eta} - \sqrt{\rho}}{\sqrt{\kappa}} + \eta \sqrt{\frac{\log(1/\delta) + \log\log(\eta/\rho)}{\kappa}} + \rho\right)\,. \end{align*} Choosing $\rho=\sqrt{\eta}/\sqrt{\kappa}$, yields the desired bound. \end{proof} \section{Proof of Lemma (ref)} We will argue asymptotic normality of the $U$-statistic defined as: \begin{equation*} \Psi_{0,\beta}(x; \theta(x)) = \binom{n}{s}^{-1} \sum_{b\subset [n]: |b|=s} \mathbf{E}_{\omega_b}\left[\sum_{i\in S_b}\alpha_{S_b,\omega_b}(X_i) \psi_\beta(Z_i; \theta(x))\right] \end{equation*} under the assumption that for any subset of indices $S_b$ of size $s$: $\mathbf{E}\left[\mathbf{E}[\alpha_{S_b,\omega_b}(X_1) | X_1]^2\right]=\eta(s)$ and that the kernel satisfies shrinkage in probability with rate $\epsilon(s, \delta)$ such that $\epsilon(s, \eta(s)^2)\rightarrow 0$ and $n \eta(s)\rightarrow \infty$. For simplicity of notation we let: \begin{equation} Y_i = \psi_\beta(Z_i; \theta(x)) \end{equation} and we then denote: \begin{equation} \Phi(Z_1, \ldots, Z_s) = \mathbf{E}_{\omega}\left[\sum_{i=1}^s K_{\omega}(x, X_i, \{Z_j\}_{j=1}^s)\, Y_i\right]\,. \end{equation} Observe that we can then re-write our $U$-statistic as: \begin{equation*} \Psi_{0,\beta}(x; \theta(x)) = \binom{n}{s}^{-1}\sum_{1\leq i_1\leq \ldots \leq i_s\leq n} \Phi(Z_{i_1}, \ldots, Z_{i_s})\,. \end{equation*} Moreover, observe that by the definition of $Y_i$, $\mathbf{E}[Y_i \mid X_i]=0$ and also \begin{align*} |Y_i| \leq \|\beta\|_2 \|M_0^{-1} (\psi(Z_i; \theta(x))-m(X_i;\theta(x))\|_2 2\leq \frac{R}{\lambda} \|\psi(Z_i; \theta(x))\|_2 \leq 2\frac{R\sqrt{p}}{\lambda} \psi_{\max} \triangleq y_{\max}\,. \end{align*} Invoking Lemma (ref), it suffices to show that: $\operatorname{Var}\left[\Phi_1(Z_1)\right]=\Omega(\eta(s))$, where $\Phi_1(z_1) = \mathbf{E}[\Phi(z_1, Z_2, \ldots, Z_s)]$. The following lemma shows that under our conditions on the kernel, the latter property holds. \begin{lemma} Suppose that the kernel $K$ is symmetric (Assumption (ref)), has been built in an honest manner (Assumption (ref)) and satisfies: \begin{align*} \mathbf{E}\left[\mathbf{E}\left[K(x, X_1, \{Z_j\}_{j=1}^s) \mid X_1\right]^2\right]ight]^2} &= \eta(s) \leq 1 & \text{and} & & \epsilon(s,\eta(s)^2) &\rightarrow 0 \,. \end{align*} Then, the following holds \begin{equation*} \operatorname{Var} \left[\Phi_1(Z_1)\right] \geq \operatorname{Var}(Y \mid X=x)\, \eta(s) + o(\eta(s)) = \Omega \left(\eta(s)\right)\,. \end{equation*} \end{lemma} \begin{proof} Note we can write \begin{equation*} \Phi_1(Z_1) = \underbrace{\mathbf{E}\left[\Phi(Z_1, \ldots, Z_s) \mid X_1\right]}_{A} + \underbrace{\mathbf{E}\left[\Phi(Z_1, \ldots, Z_s) \mid X_1,Y_1\right] - \mathbf{E}\left[\Phi(Z_1, \ldots, Z_s)\mid X_1\right]}_B. \end{equation*} Here, $B$ is zero mean conditional on $X_1$ and also $A$ and $B$ are uncorrelated, i.e., $\mathbf{E}[AB]=\mathbf{E}[A]\mathbf{E}[B]=0$. Therefore: \begin{equation*} \operatorname{Var} \left[\Phi_1(Z_1)\right] \geq \operatorname{Var}\left[B\right] = \operatorname{Var} \left[\sum_{i=1}^s \left(\mathbf{E}\left[K(x, X_i, \{Z_j\}_{j=1}^s) Y_i \mid X_1,Y_1\right] - \mathbf{E}[K(x, X_i, \{Z_j\}_{j=1}^s) Y_i \mid X_1]\right)\right]d X_1]}}\,. \end{equation*} For simplicity of notation let $W_i = K(x, X_1, \{Z_j\}_{j=1}^s)$ denote the random variable which corresponds to the weight of sample $i$. Note that thanks to the honesty of kernel defined in Assumption (ref), $W_i$ is independent of $Y_1$ conditional on $X_1$, for $i \geq 2$. Hence all the corresponding terms in the summation are zero. Therefore, the expression inside the variance above simplifies to \begin{equation*} \mathbf{E}[W_1 Y_1 \mid X_1,Y_1]-\mathbf{E}[W_1 Y_1 \mid X_1]\,. \end{equation*} Moreover, by honesty $W_1$ is independent of $Y_1$ conditional on $X_1$. Thus, the above further simplifies to: \begin{equation*} \mathbf{E}[W_1\mid X_1] \, \left(Y_1 - \mathbf{E}[Y_1 \mid X_1]\right)\,. \end{equation*} Using $\operatorname{Var}(G)=\mathbf{E}[G^2]-\mathbf{E}[G]^2$, this can be further rewritten as \begin{equation*} \operatorname{Var}\left[\Phi_1(Z_1)\right] \geq \mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]^2 \left(Y_1 - \mathbf{E}[Y_1\mid X_1]\right)^2\right] - \mathbf{E} \left[\mathbf{E}[W_1 \mid X_1] (Y_1-\mathbf{E}[Y_1 \mid X_1])\right]^2\,. \end{equation*} Note that $Y_1 - \mathbf{E}[Y_1 \mid X_1]$ is uniformly upper bounded by some $\psi_{\max}$. Furthermore, by the symmetry of the kernel we have $\mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]\right] = \mathbf{E}[W_1] = 1/s$.\footnote{Since $\mathbf{E}[W_i]$ are all equal to the same value $\kappa$ and $\sum_i\mathbf{E}[W_i] = 1$, we get $\kappa=1/s$.} Thus the second term in the latter is of order $1/s^2$. Hence: \begin{equation*} \operatorname{Var} \left[\Phi(Z_1)\right] \geq \mathbf{E} \left[\mathbf{E}[\alpha_b(X_1) \mid X_1]^2 \left(Y_1 - \mathbf{E}[Y_1\mid X_1]\right)^2\right] + o(1/s)\,. \end{equation*} Focusing at the first term and letting $\sigma^2(x) = \operatorname{Var}(Y | X=x)$, we have: \begin{align*} \mathbf{E}\left[\mathbf{E}[W_1 \mid X_1]^2 \left(Y_1 - \mathbf{E}[Y_1\mid X_1]\right)^2\right] = & \mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]^2 \sigma^2(X_1)\right] \\ = & \mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]^2\right] \sigma^2(x) + \mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]^2 \left(\sigma^2(X_1)-\sigma^2(x)\right)\right]\,. \end{align*} The goal is to prove that the second term is $o(1/s)$. For ease of notation let $V_1=\mathbf{E}\left[W_1 \mid X_1\right]$. Then we can bound the second term as: \begin{align*} \left|\mathbf{E} \left[V_1^2 \left(\sigma^2(X_1)-\sigma^2(x)\right)\right]\right| \leq & L_{mm} \epsilon(s,\delta)\, \mathbf{E} \left[V_1^2\, \,1\left\{\|x-X_1\|_2 \leq \epsilon(s,\delta)\right\}\right] \\ & + 2 y_{\max}^2 \mathbf{E} \left[V_1^2\,1 \left\{\|x-X_1\|_2 > \epsilon(s,\delta)\right\}\right]\\ \leq & L_{mm} \epsilon(s,\delta)\, \mathbf{E} \left[V_1^2\right] + 2 y_{\max}^2 \mathbf{E} \left[V_1^2\,1 \left\{\|x-X_1\|_2 > \epsilon(s,\delta)\right\}\right]\\ \leq & L_{mm} \epsilon(s,\delta) \eta(s) + 2 y_{\max}^2 \mathbf{E} \left[V_1\,1 \left\{\|x-X_1\|_2 > \epsilon(s,\delta)\right\}\right]\\ \leq & L_{mm} \epsilon(s,\delta) \eta(s) + 2 y_{\max}^2 \mathbf{E} \left[W_1\,1 \left\{\|x-X_1\|_2 > \epsilon(s,\delta)\right\}\right]\,, \end{align*} where we used the fact that $V_1 \leq 1$, the assumption that $\sigma^2(\cdot)$ is $L_{mm}$-Lipschitz, the tower rule and the definition of $\eta(s)$. Furthermore, \begin{align*} \mathbf{E} \left[W_1 \,1 \left\{\|x-X_1\|_2 > \epsilon(s,\delta)\right\}\right] &\leq \Pr \left[\|x-X_1\|_2 \geq \epsilon(s,\delta){ \text{and} } W_1 > 0\right] \\ &\leq \Pr \left[\sup_i \left\{\|x-X_i\|_2 : W_i > 0\right\} \geq \epsilon(s,\delta)\right]\,, \end{align*} which by definition is at most $\delta$. By putting $\delta = \eta(s)^2$ we obtain \begin{align*} \left|\mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]^2 \left(\sigma^2(X_1)-\sigma^2(x)\right)\right]\right| \leq L_{mm} \epsilon(s,\eta(s)^2) \eta(s) + 2 y_{\max}^2 \eta(s)^2 = o(\eta(s))\,, \end{align*} where we invoked our assumption that $\epsilon(s,\eta(s)^2) \rightarrow 0$. Thus we have obtained that: \begin{equation*} \operatorname{Var}\left[\Phi_1(Z_1)\right] \geq \mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]^2\right] \sigma^2(x) + o(\eta(s)) \,, \end{equation*} which is exactly the form of the lower bound claimed in the statement of the lemma. This concludes the proof. \end{proof} \subsection{H\'{a}jek Projection Lemma for Infinite Order $U$-statistics} The following is a small adaptation of Theorem 2 of fan2018dnn, which we present here for completeness. \begin{lemma}[fan2018dnn] Consider a $U$-statistic defined via a symmetric kernel $\Phi$: \begin{equation} U(Z_1,\ldots, Z_n) = \binom{n}{s}^{-1}\sum_{1\leq i_1\leq \ldots \leq i_s\leq n} \Phi(Z_{i_1}, \ldots, Z_{i_s})\,, \end{equation} where $Z_i$ are i.i.d. random vectors and $s$ can be a function of $n$. Let $\Phi_1(z_1) = \mathbf{E}[\Phi(z_1, Z_2, \ldots, Z_s)]$ and $\eta_1(s)=\operatorname{Var}_{z_1}\left[\Phi_1(z_1)\right]$. Suppose that $\operatorname{Var}{\Phi}$ is bounded, $n\, \eta_1(s) \rightarrow \infty$. Then: \begin{equation} \frac{U(Z_1,\ldots, Z_n) - \mathbf{E}\left[U\right]}{\sigma_n} \rightarrow_d \mathsf{N}(0,1)\,, \end{equation} where $\sigma_n^2 = \frac{s^2}{n}\eta_1(s)$. \end{lemma} \begin{proof} The proof follows identical steps as the one in fan2018dnn. We argue about the asymptotic normality of a $U$-statistic: \begin{equation} U(Z_1,\ldots, Z_n) = \binom{n}{s}^{-1}\sum_{1\leq i_1\leq \ldots \leq i_s\leq n} \Phi(Z_{i_1}, \ldots, Z_{i_s})\,. \end{equation} Consider the following projection functions: \begin{align*} \Phi_1(z_1) = & \mathbf{E}[\Phi(z_1, Z_2, \ldots, Z_s)]\,, & \tilde{\Phi}_1(z_1) = & \Phi_1(z_1) - \mathbf{E}\left[\Phi\right]\,, \\ \Phi_2(z_1, z_2) = & \mathbf{E}[\Phi(z_1, z_2, Z_3, \ldots, Z_s) \,, & \tilde{\Phi}_2(z_1, z_2) = & \Phi_2(z_1, z_2) - \mathbf{E}\left[\Phi\right] \,, \\ \vdots\\ \Phi_s(z_1, z_2, \ldots, z_s) = & \mathbf{E}[\Phi(z_1, z_2, Z_3, \ldots, Z_s) \,, & \tilde{\Phi}_s(z_1, z_2, \ldots, z_s) = & \Phi_s(z_1, z_2, \ldots, z_s) - \mathbf{E}\left[\Phi\right]\,, \end{align*} where $\mathbf{E}\left[\Phi\right]=\mathbf{E}\left[\Phi(Z_1,\ldots, Z_s)\right]$. Then we define the canonical terms of Hoeffding's $U$-statistic decomposition as: \begin{align*} g_1(z_1) = & \tilde{\Phi}_1(z_1) \,, \\ g_2(z_1, z_2) = & \tilde{\Phi}_2(z_1, z_2) - g_1(z_1) - g_2(z_2)\,, \\ g_3(z_1, z_2, z_3) = & \tilde{\Phi}_2(z_1, z_2, Z_3) - \sum_{i=1}^3 g_1(z_i) - \sum_{1\leq i<j\leq 3} g_2(z_i, z_j) \,, \\ \vdots\\ g_s(z_1, z_2, \ldots, z_s) = & \tilde{\Phi}_s(z_1, z_2, \ldots, z_s) - \sum_{i=1}^s g_1(z_i) - \sum_{1\leq i < j \leq s} g_2(z_i, z_j) - \ldots\\ & ...- \sum_{1\leq i_1 < i_2 < \ldots < i_{s-1} \leq s} g_{s-1}(z_{i_1}, z_{i_2}, \ldots, z_{i_{s-1}}) \,. \end{align*} Subsequently the kernel of the $U$-statistic can be re-written as a function of the canonical terms: \begin{equation} \tilde{\Phi}(z_1, \ldots, z_s) = \Phi(z_1, \ldots, z_s) - \mathbf{E}\left[\Phi\right] = \sum_{i=1}^s g_1(z_i) + \sum_{1\leq i < j \leq s} g_2(z_i, z_j) + \ldots + g_s(z_1, \ldots, z_s)\,. \end{equation} Moreover, observe that all the canonical terms in the latter expression are un-correlated. Hence, we have: \begin{equation} \operatorname{Var} \left[\Phi(Z_1, \ldots, Z_n)\right] = \binom{s}{1} \mathbf{E}\left[g_1^2\right] + \binom{s}{2} \mathbf{E}\left[g_2^2\right] + \ldots + \binom{s}{s} \mathbf{E}\left[g_s^2\right]\,. \end{equation} We can now re-write the $U$ statistic also as a function of canonical terms: \begin{align*} U(Z_1,\ldots, Z_n) - \mathbf{E}\left[U\right] = & \binom{n}{s}^{-1} \sum_{1\leq i_1 < i_2 < \ldots < i_s \leq n} \tilde{\Phi}(Z_{i_1}, \ldots, Z_{i_s})\\ = & \binom{n}{s}^{-1} \bigg(\binom{n-1}{s-1}\sum_{i=1}^n g_1(Z_i) + \binom{n-2}{s-2} \sum_{1\leq i < j \leq n} g_2(Z_i, Z_j) + \ldots\\ & + \binom{n-s}{s-s} \sum_{1\leq i_1 < i_2 < \ldots < i_s \leq n} g_s(Z_{i_1}, \ldots, Z_{i_s})\bigg)\,. \end{align*} Now we define the H\'{a}jek projection to be the leading term in the latter decomposition: \begin{equation} \hat{U}(Z_1, \ldots, Z_n) = \binom{n}{s}^{-1} \binom{n-1}{s-1}\sum_{i=1}^n g_1(Z_i)\,. \end{equation} The variance of the Hajek projection is: \begin{equation} \sigma_n^2 = \operatorname{Var}\left[\hat{U}(Z_1, \ldots, Z_n)\right] = \frac{s^2}{n} \operatorname{Var}\left[\Phi_1(z_1)\right] = \frac{s^2}{n}\eta_1(s)\,. \end{equation} The H\'{a}jek projection is the sum of independent and identically distributed terms and hence by the Lindeberg-Levy Central Limit Theorem (see e.g., billingsley2008probability,borovkov2013probability): \begin{equation} \frac{\hat{U}(Z_1,\ldots, Z_n)}{\sigma_n} \rightarrow_d \mathsf{N}(0,1)\,. \end{equation} We now argue that the remainder term: $\frac{U - \mathbf{E}\left[U\right] - \hat{U}}{\sigma_n}$ vanishes to zero in probability. The latter then implies that $\frac{U - \mathbf{E}\left[U\right]}{\sigma_n} \rightarrow_d \mathsf{N}(0,1)$ as desired. We will show the sufficient condition of convergence in mean square: $\frac{\mathbf{E}\left[\left(U - \mathbf{E}\left[U\right] - \hat{U}\right)^2\right]t{U}}^2}}{\sigma_n^2}\rightarrow 0$. From an inequality due to wager2017estimation: \begin{align*} \mathbf{E}\left[\left(U - \mathbf{E}\left[U\right] - \hat{U}\right)^2\right]t{U}}^2} = & \binom{n}{s}^{-2} \left\{\binom{n-2}{s-2}^2 \binom{n}{2} \mathbf{E}[g_2^2] + \ldots + \binom{n-s}{s-s}^2 \binom{n}{s} \mathbf{E}[g_s^2]\right\}\\ = & \sum_{r=2}^s \left\{\binom{n}{s}^{-2} \binom{n-r}{s-r}^2 \binom{n}{r} \mathbf{E}[g_r^2]\right\}\\ = & \sum_{r=2}^s \left\{\frac{s! (n-r)!}{n! (s-r)!} \binom{s}{r}\mathbf{E}[g_r^2]\right\}\\ \leq & \frac{s(s-1)}{n(n-1)} \sum_{r=2}^s \binom{s}{r} \mathbf{E}[g_r^2]\\ \leq & \frac{s^2}{n^2} \operatorname{Var}\left[\Phi(Z_1, \ldots, Z_s)\right]\,. \end{align*} Since $\operatorname{Var}\left[\Phi(Z_1, \ldots, Z_n)\right]$ is bounded by a constant $V^*$ and $n\,\eta_1(s) \rightarrow \infty$, by our assumption, we have: \begin{equation} \frac{\mathbf{E}\left[\left(U - \mathbf{E}\left[U\right] - \hat{U}\right)^2\right]t{U}}^2}}{\sigma_n^2}\leq \frac{\frac{s^2}{n^2} V^*}{\frac{s^2}{n}\eta_1} = \frac{V^*}{n\, \eta_1(s)} \rightarrow 0 \,. \end{equation} \end{proof} \begin{comment} \kkdelete{ \section{Random Projection Trees} Let us explain the idea behind random projection trees (RPTree). The results of this section are built on kpotufe2012tree and we include it here for completeness. We start by defining RPTree and then explain technical lemmas required for establishing their shrinkage. We require the following definition (\kkcomment{we should think about how this relates to Definition (ref)}): \begin{definition} The Assouad dimension (or doubling dimension) of $\mathcal{X} \in \mathbb{R}^D$ is the smallest $d$ such that for any ball $B \in \mathbb{R}^D$, the set $B \cap \mathcal{X}$ can be covered by $2^d$ balls of half the radius of $B$. \end{definition} Before stating the algorithm and proving its theoretical guarantees, let us define some notions. Define the \textit{Physical Diameter} of a cell $A \subset \mathbb{R}^p$ as \begin{equation*} \Delta(A) = \max_{x,x' \in A} \|x-x'\|_2\,. \end{equation*} Furthermore, given a data set $\mathbf{X}=\left\{X_1,X_2,\ldots,X_s\right\}$ define the \textit{Data Diameter} of this cell as \begin{equation*} \Delta_s(A) = \max_{x,x' \in A \cap \mathbf{X}} \|x-x'\|_2\,. \end{equation*} Finally, given a partition $\mathcal{A}$ containing different cells, we can define the average physical diameter and also the average data diameter as \begin{align*} \Delta(\mathcal{A}) &= \sqrt{\frac{\sum_{A \in \mathcal{A}} \mu(A) \Delta(A)}{\sum_{A \in \mathcal{A}} \mu(A)}}\,, \\ \Delta_s(\mathcal{A}) &=\sqrt{\frac{\sum_{A \in \mathcal{A}} \mu_s(A) \Delta_s(A)}{\sum_{A \in \mathcal{A}} \mu_s(A)}}\,. \end{align*} The following contains the pseudo-code for RPtree. Similar to kpotufe2012tree we define two subroutines \textsf{basicRPTree} and \textsf{coreRPTree} that will be called in the main \textsf{adaptiveRPTree} algorithm. The key idea behind these two subroutines is that \textsf{coreRPTree} works as follows: \begin{itemize} • It takes a region $A \subset \mathbb{R}^p$ • It recursively splits the region till the point that the data diameter of leaves become at most half of data diameter of $A$ • As in the even rounds, the split happens at the median, the process returns a tree such that each leaf has at most $\lceil{A \cap \mathbf{X}/2 \rceil}$ sample points. \end{itemize} For formalizing our result we need the following definition. \begin{definition} Given a sample $\mathbf{X}$, we say that \textsf{coreRPTree} attains a diameter decrease at rate of $k$ on $\mathbf{X}$ for $k \geq d$, if every call to it in the second loop of the main procedure \textsf{adaptiveRPTree} returns a tree of depth at most $k$. \end{definition} The following lemma holds. \begin{lemma} There exists an absolute constant $C_1$ such that w.p. $1-\delta/3$, the subroutine \textsf{coreRPTree} achieves diameter decrease at rate $k \leq C_1 d \log d$. \end{lemma} \begin{proof} The main idea of proof follows from the argument of dasgupta2008random \kkcomment{we can add this as a lemma if we want} and has been generalized to this setting in kpotufe2012tree. \end{proof} The estimator at a target point $x$ assigns the weights according to \begin{equation*} K(X_i,x,\left\{X_1,X_2,\ldots,X_s\right\}) = \frac{\,1 \left\{X_i \in A(x)\right\}}{|A(x)|}\,, \end{equation*} where $A(x)$ is the leaf that $x$ falls into. Note that this implies \begin{equation*} \sup \left\{\|X_i-x\|: K(X_i,x,\left\{X_1,X_2,\ldots,X_s\right\}) >0\right\}ght\}) >0} \leq \text{diam}\left(A(x)\right)\,. \end{equation*} The challenge here is that because of the fact that the leaves of tree generated by \textsf{adaptiveRPTree} are convex polytopes, their physical diameter might not decrease gracefully as one goes down in the tree. In order to analyze this quantity better we partition each cell $A \in \mathcal{A}^t$ into two parts $A_1', A_2'$ satisfying the following: \begin{itemize} • $\mu_s(A_1')=\mu_s(A_1)$ and $\mu_s(A_2')=0$, i.e., all the training points belong to $A_1'$. • The physical diameter of $A_1'$ is nicely related to the data diameter of $A$. \end{itemize} The existence of this partition would help us to bound the bias gracefully for target points $x$ that fall into $A_1'$ (for one of leaves of the final tree). Having this established, we then prove that the probability that $x \sim \mathcal{X}$ belongs to $A_2'$ for one of the leaf nodes is very small. The reason behind this is the concentration of measures $\mu_s(A_1'), \mu_s(A_2')$ around their means $\mu(A_1')$ and $\mu(A_2')$ which we later explain. } \kkdelete{ The construction of $A_1'$ and $A_2'$ is explained in the following. Let $\mathcal{B}_i$ to be a $U/2^i-$cover of $\mathcal{X}$. Note that as Assouad Dimension is equal to $d$ (see Definition (ref)), there exists a $U/2^i-$cover of size at most $2^{id}$. Now consider $\mathcal{B}_i$ for $i=0, 1, 2, \ldots, I = \lfloor{\frac{1}{k} \log \left(s\right)\rfloor}$ and define $\mathcal{B} = \cup_{i=0}^I \left\{4B: B \in \mathcal{B}_i\right\}$. Then, for any cell $A$, partitions $A_1'$ and $A_2'$ are defined follows: \begin{itemize} • If $A \cap \mathbf{X} = \varnothing$, then define $A_1' = A$ and $A_2' = \varnothing$. • Otherwise, set $i=\min \left\{I, \lceil{\log \left(U/\Delta_s(A\right) \rceil}\right\}$; we will find a ball $B \in \mathcal{B}_i$ such that $A \cap \mathbf{X} \subset B$. Pick any $x \in A \cap \mathbf{X}$ and suppose that $x$ belongs to the ball $B = B(z,U/2^i)$. For any $x' \in A \cap \mathbf{X}$, using triangle inequality we have \begin{equation*} \|x'-z\|_2 \leq \|x'-x\|_2 + \|x-z\|_2 \leq \Delta_s(A) + 2^{-i} U \leq 2^{-{i-1}} U + 2^{-i} U \leq 4 \cdot 2^{-i} U\,, \end{equation*} implying that $x' \in 4B$. Now, let $A_1' = A \cap 4B$ and $A_2'= A - A_1'$. \end{itemize} \begin{lemma} Let $\mathcal{A}$ be a partitioning of $\mathcal{X}$ and define $\mathcal{A}'$ as above. Then, for any $A_1' \in \mathcal{A}$ we have \begin{equation*} \Delta(A_1') \leq \max \left\{8 \Delta_s(A), 16 U s^{-1/k}\right\}\,. \end{equation*} \end{lemma} \begin{proof} Note that $A_1' = A \cap 4B$ where $B$ is a ball with radius $2^{-i} U$, where $i=\min \left\{I, \lceil{\log \left(U/\Delta_s(A\right) \rceil}\right\}$. Therefore, the diameter of $A_1'$ is at most equal to $8 \cdot 2^{-i} U \leq \max \left\{8 \Delta_s(A), 8 \cdot 2^{-I} U\right\}$. Replacing the definition of $I$ and noting that $\lfloor{z \rfloor} \geq z-1$ implies the result. \end{proof} Now that we have this Lemma, we want to prove that the marginal mass of cell $A_2'$ is small. For proving this we need a Bernstein's type inequality which relates the empirical mass of $A_2'$ (which is actually zero) to its marginal mass. The following result is due to vapnik1971uniform. \begin{lemma}[VC bound] Let $\mathcal{C}$ be a class of subsets of $\mathbb{R}^p$. Pick an $\delta>0$. Suppose a sample of size $s$ is drawn independently at random from a distribution $\mu$ over $\mathbb{R}^p$, with resulting empirical distribution $\mu_s$. Then w.p. at least $1-\delta$ over the choice of sample, all $C \in \mathcal{C}$ satisfy \begin{equation*} \mu(C) \leq \mu_s(C) + 2 \sqrt{\mu_s(C) \frac{\ln \mathcal{S}(\mathcal{C},2s)+\ln(4/\delta)}{s}} + 4 \frac{\ln \mathcal{S}(\mathcal{C},2s)+\ln(4/\delta)}{s} \,, \end{equation*} where $\mathcal{S}(\mathcal{C}, 2s)$ is the $2s$-shatter coefficient of $\mathcal{C}$. \end{lemma} Having this Lemma in hand, we only need to prove that $\mathcal{S}(\mathcal{C},2s)$ is nicely behaved in our problem. The key observation here is that the random directions that are used in the construction of tree do not depend on data. Rather, only the displacement points (which is either at median or noisy version of median) depend on the data. Hence, in the analysis of shattering coefficient we can fix the random direction in the analysis. The following lemma can be then adapted from Lemma 15 of kpotufe2012tree after modifying the definition of $I$. \begin{lemma}[Masses of cells in $\mathcal{A}'$] There exists a constant $C_0$ such that for any $\delta>0$, w.p. at least $1-2\delta/3$ over the choice of $\mathcal{X}$ and the randomness in the algorithm, we have for any partition $\mathcal{A} = \mathcal{A}^t$ generated during the construction of tree, every cell $A'\in \mathcal{A}'$ (i.e., both $A_1'$s and $A_2'$s) satisfies \begin{equation*} \mu(A') \leq \mu_s(A') + 2 \sqrt{\mu_s(A') \frac{C(s,\delta)}{s}} + 4 \frac{C(s,\delta)}{s} \,, \end{equation*} where $C(s,\delta) \leq C_0 \log s \left(\log s + \log \log (s/\delta)\right) + \log (4/\delta)$. \end{lemma} Note that $\mu_s(A_2')=0$. Therefore, we have the following corollary. \begin{corollary} Under assumptions of the above lemma, for any $A_2' \in \mathcal{A}'$ we have \begin{equation*} \mu(A_2') \leq 4 \frac{C(s, \delta)}{s} \,. \end{equation*} \end{corollary} Having this Corollary in mind, now it is easy to prove the following lemma \begin{lemma}[Shrinkage rate of random projection tree] Suppose that $\mathcal{X}$ has Assouad dimension $d$ (see Definition (ref)). Let $\mathcal{A}^{t-1}$ be the tree returned by \textsf{adaptiveRPTree} and let $K$ be the associated kernel. Then, w.p. $1-\delta$ over samples $\mathbf{X}$ and also the randomness in the algorithm the following holds: There exists a set $\mathcal{F}_{\zeta}$ such that $\mu(\mathcal{F}_{\zeta}) \geq 1-\zeta$ and for any $x \in \mathcal{F}_{\zeta}$ we have \begin{equation*} \sup \left\{\|X_i-x\|_2: K(X_i, x, \left\{X_1,X_2,\ldots,X_s\right\}\right\}s\right\}} \leq 16U \left(\frac{s \zeta}{C(s,\delta)}\right)^{-1/k} \end{equation*} \end{lemma} \begin{proof} Suppose that for index $i$ the stopping criterion is satisfied. This basically means that \begin{equation*} \frac{|\mathcal{A}^{t-1}| C(s,\delta)}{s} \leq \zeta \leq \frac{|\mathcal{A}^{t}| C(s,\delta)}{s} \,, \end{equation*} For any partition $\mathcal{A}$ define \begin{equation*} \text{level}(\mathcal{A}) = \max_{A \in \mathcal{A}}\,\text{level}(A)\,. \end{equation*} Note that $\mathcal{A}^{t}$ has at most $2^{\text{level}(\mathcal{A}^{t})}$ cells and based on Lemma (ref), w.p. at least $1-\delta/3$ the subroutine \textsf{coreRPTree} achieves diameter decrease at rate $k \leq C_1 d \log d$. Hence, $\text{level}(\mathcal{A}^{t}) \leq kt$ holds which implies that \begin{equation*} \frac{2^{kt} C(s,\delta)}{s} \geq \zeta \Rightarrow 2^t \geq \left(\frac{s \zeta}{C(s,\delta)}\right)^{1/k}\,. \end{equation*} Furthermore, for any $A \in \mathcal{A}^{t-1}$ we know that $\Delta_s(A) \leq 2^{-(t-1)} U$. This is true according to the second fact about the subroutine \textsf{coreRPTree}. Finally, using Lemma (ref) we also have that for any $A \in \mathcal{A}^{t-1}$, for $A_1'$ we have \begin{equation*} \Delta(A_1') \leq \max \left\{8 \Delta_s(A), 16 U s^{-1/k}\right\} \leq \max 16 U\left\{\left(\frac{s \zeta}{C(s,\delta)}\right)^{-1/k}, s^{-1/k}\right\} \leq 16U \left(\frac{s \zeta}{C(s,\delta)}\right)^{-1/k} \,, \end{equation*} where we used the inequalities $\zeta \in (0,1)$ and $C(s,\delta) \geq 1$. Now note that w.p. $1-2\delta/3$ the total mass of cells $A_2'$ where $A \in \mathcal{A}^{t-1}$ is bounded above by \begin{equation*} \sum_{A \in \mathcal{A}^{t-1}} \mu(A_2') \leq |\mathcal{A}^{t-1}| \frac{C(s,\delta)}{s} \leq \zeta \,, \end{equation*} according to the stopping rule and also Corollary (ref). Hence, using a union bound w.p. $1-\delta$ the following holds: define $\mathcal{F}_\zeta = \cup_{A \in \mathcal{A}^{t-1}} A_1'$, then $\mu(\mathcal{F}_\zeta) \geq 1-\zeta$ and also for any $x \in \mathcal{F}_\zeta$ \begin{equation*} \sup \left\{\|X_i-x\|: K(X_i,x,\left\{X_1,X_2,\ldots,X_s\right\}) >0\right\}ght\}) >0} \leq \Delta\left(A_1'(x)\right) \leq 16U \left(\frac{s \zeta}{C(s,\delta)}\right)^{-1/k} \,, \end{equation*} as desired. \end{proof} Note that the above result implies that for all target points $x \in \mathbb{G}_\zeta$ \begin{equation*} \epsilon(s,\delta) \leq 16U \left(\frac{s \zeta}{C(s,\delta)}\right)^{-1/k} \end{equation*} \kkdelete{ We can extend this result to forests by taking a union bound. \begin{corollary}[Shrinkage rate of random projection forests] Suppose that $\mathcal{X}$ has Assouad dimension $d$ (see Definition (ref)) and the kernel is the random projection tree defined in \textsf{adaptiveRPTree} routine (see Algorithm (ref)). Furthermore, assume that the sub-sampling size is chosen equal to $s$ with $B$ different sub-samples. Then, w.p. $1-\delta/2$ over the choice of training samples and also randomness in the algorithm the following holds: for any $\zeta \in (0,1)$, there exists a set $\mathbb{G}_\zeta$ such that $\mu(\mathbb{G}_\zeta) \geq 1-\zeta$ and for any $x \in \mathbb{G}_\zeta$ \begin{equation*} \sup \left\{\|X_{ib} - x\|: K(X_{ib},x,\left\{X_{1b},X_{2b},\ldots,X_{sb} > 0\right\})\right\}\right\})} \leq 16U \left(\frac{s \zeta}{BC(s,\delta/2B)}\right)^{-1/k}\,, \end{equation*} where $\mathcal{S}_b = \left\{X_{1b},X_{2b},\ldots,X_{sb}\right\},~1 \leq b \leq B$ denotes the $b$th sub-sample. In other words, for all target points in $\mathbb{G}_\zeta$, the shrinkage is upper bounded by the quantity given on the right hand side above equation uniformly over all $B$ sub-samples. \end{corollary} } We can now invoke Theorem (ref) to establish estimation rate for our random projection forest. \begin{theorem} Suppose that $\mathcal{X}$ has Assouad dimension $d$ (see Definition (ref)) and the kernel is the random projection tree defined in \textsf{adaptiveRPTree} routine (see Algorithm (ref)). Furthermore, assume that the sub-sampling size is chosen equal to $s$ with $B = \lceil{n/s \rceil}$ different sub-samples. Then, there exists a set $\mathbb{G}_{\zeta}$ such that $\mu(\mathbb{G}_{\zeta}) \geq 1-\zeta$ that for any $x \in \mathbb{G}_{\zeta}$ also w.p. at least $1-\delta$ (over the choice of training samples and randomness of algorithm) we have \begin{equation} \|\theta - \theta(x)\|_2 \leq \frac{1}{\lambda}\left(O \left(U\left(\frac{s^2 \zeta}{nC(s,s\delta/(2n))}\right)^{-1/k}\right)^{-1/k}} + O\left(\psi_{\max}\sqrt{\frac{s\, p\, \ln(p\, L\, n/s\,\delta)}{n}} \right)\right)a)}{n}} \right)} \,, \end{equation} Furthermore, for the optimal choice of $s \approx n^{(k+2)/(k+4)}$ (which implies $B \approx n^{2/(k+4)}$), the above estimation error is $\tilde{O} \left(n^{-1/(k+4)}\right)$. \end{theorem} \begin{proof} Replace $\zeta = \zeta/B$. Apply a union bound, Lemma (ref) and Theorem (ref) \end{proof} \begin{remark} The above guarantee holds for all target points $x$ that belong to a set which has measure equal to $1-\zeta$. If we are interested in having this measure to be asymptotically equal to $1$, we can allow $\zeta \in (0,1)$ to be a function of $s$. Indeed, if one takes $\zeta = 1/\log(s)$, then asymptotically $\mathbb{G}_{\zeta}$ has its measure equal to $1$. As $\zeta$ is logarithmic in $s$, it does not change the achieved rate of estimation. \end{remark} \kkdelete{ \subsection*{Why normality fails with current conditions?} Suppose that we use Lemma (ref). \begin{equation*} \mathbf{E}[\mathbf{E}[K(x, X_1, \{X_j\}_{j=1}^s) |X_1]^2] \geq \frac{\left(1/s - \delta\right)^2}{\mu(B(x, \epsilon(s, \delta)))} \,. \end{equation*} Now note that if we assume the two-sided version of Assouad dimension meaning that $\mu(B(X, \epsilon r)) \leq c \epsilon^d \mu(B(x,r))$ and also the shrinkage result in Lemma (ref) we get that \begin{equation*} \mu(B(x, \epsilon(s,\delta))) \leq L \left(\epsilon(s,\delta)\right)^d = \tilde{O} s^{-d/k}\,. \end{equation*} As $(1/s - \delta)^2$ is at most $1/s^2$, we obtain that \begin{equation*} \mathbf{E}[\mathbf{E}[K(x, X_1, \{X_j\}_{j=1}^s) |X_1]^2] = \tilde{O} \left(s^{-2+d/k}\right) = \eta(s) \end{equation*} The main step in proving normality would be establishing a result similar to Lemma 6. Now looking at the proof of Lemma 15, we want to get something like: \begin{equation*} \operatorname{Var}(\Phi(Z_1)) \geq \operatorname{Var} \left(Y \mid X=x\right) \eta(s)\,. \end{equation*} Following the steps of the proof, the terms that are $O(s^{-2})$ still can be neglected in the analysis. However, in the line that we are bounding $\left|\mathbf{E} \left[\mathbf{E}[W_1 \mid X_1]^2 \left(\sigma^2(X_1)-\sigma^2(x)\right)\right]\right|$ the first term is \begin{equation*} L \epsilon(s,\delta) \mathbf{E}[W_1] = \tilde{O} \left(s^{-1-1/k}\right)\,. \end{equation*} The challenge now is that $s^{-1-1/k}$ is larger than $\eta(s) = s^{-2+d/k}$ (unless $k \leq d+1$ which of course does not hold for $k=Cd\log d$) and therefore we get stuck here. Of course, there should be a way to get around this. The main reason is that in the very first inequality we use $\mathbf{E}[U]^2 \leq \mathbf{E}[U]$ for $U \in [0,1]$. I suppose that if we do something nicer we should be able to make this closer to $s^{-2}$ which is smaller than $\eta(s)$. } \kkdelete{ \subsection*{Normality with the new theorem} If we assume that $\mathbf{E}[\mathbf{E}[W_1 | X_1]^2]= \Omega(\eta(s))$, then the normality theorem now has the following requirements: \begin{align} s \rightarrow \infty \\ \epsilon(s, \eta(s)^2) \rightarrow 0 \\ \frac{n \eta(s)}{\log^2(n/s)} \rightarrow \infty \\ \epsilon(s) = o\left(s\sqrt{\frac{\eta(s)}{n}}\right) \end{align} where the last condition is a sufficient condition for the condition that $\epsilon(s)=o(\sigma_n(x))$, where we take the conservative lower bound that $\sigma_n(x) = \Omega\left(s\sqrt{\frac{\eta(s)}{n}}\right)$. } \kkdelete{ If we use Lemma (ref), then we have roughly: $\eta(s) = \frac{1}{s^{2} \epsilon(s)^d}$ and $\epsilon(s, \delta)=\tilde{O}\left(\left(\frac{\log(1/\delta)}{s}\right)^{1/d\log(d)}\right)$. Similarly, $\epsilon(s) = \tilde{O}\left(\frac{1}{s^{1/d\log(d)}}\right)$. \begin{itemize} • Condition (ref) is satisfied as long as $s$ is a growing function of $n$. • Condition (ref) is satisfied whenever $s\rightarrow \infty$ since: \begin{align*} \epsilon(s, \eta(s)^2) = \tilde{O}\left( \frac{\log(1/s)}{s} \right) = o(1) \end{align*} • Condition (ref) is satisfied when: $s^2 \epsilon(s)^d = o(n^{1-\alpha})$ for any $\alpha>0$. • Condition (ref) is problematic, as it holds when: \begin{align*} \epsilon(s)^{1 + d/2} = o(n^{-1/2}) \Leftrightarrow \epsilon(s)^{2 + d} = o(n^{-1}) \end{align*} If $\epsilon(s)=s^{-1/d\log(d)}$, then the latter implies $s^{\frac{2+d}{d\log(d)}}=\omega(n)$. But when $2+d\leq d\log(d)$, the latter happens only if $s=\omega(n)$, which is impossible. \end{itemize} It seems that if one uses the generic result of Lemma (ref), then it must be that $\epsilon(s)=s^{\beta}$, for $\beta> 1/(d+1)$. Otherwise, we cannot both satisfy: $\epsilon(s)^{2+d}=o(n^{-1})$ and $s^2 \epsilon(s)^d = o(n)$. So the behavior has to be roughly $\epsilon(s) = s^{-1/d}$ and one can afford at most a shrinkage as slow as $s^{-1/(d+1)}$ but not slower. Hence, the $s^{-1/d\log(d)}$ that we have is too slow for the Lemma (ref) to have some bite and for such a slower rate, one needs to do an ad hoc proof of a lower bound on the incrementality. } \kkdelete{It seems to me that the bound $s^{-d/k}$ on the density of ball around $x$ is very bad. Roughly speaking, we should get something closer to $s^{-1}$. This mainly comes from the Bernstein inequality. In some sense, $\mu(A'_2)$ is of the order $1/s$, but we expect in the cells that we have data points ($A_1'$s), we get better rates. I will try see whether we can do this.} \kkdelete{ \begin{algorithm} \caption{\textsf{basicRPTree}($A_0 \subset \mathcal{X}, \Delta$)} \begin{algorithmic}[1] \State $\mathcal{A}_0 \gets \left\{A_0\right\}$ \For{$i=1,2,\cdots$} \If{$\Delta_s(\mathcal{A}_{i-1}) \leq \Delta$ and $i$ is odd} \State \Return \EndIf \State Choose a random direction $v \sim \mathsf{N}(0,\frac{1}{p} I_p)$ \State Choose a random $\tau \in \mathcal{U}[-1,1] \cdot \frac{6}{\sqrt{p}} \Delta_s(A_0)$ \ForEach{cell in $A \in \mathcal{A}_{i-1}$} \If{$i$ is odd} \State $t \gets \text{median} \left\{z^\top v: z \in A_0 \cap \mathbf{X}\right\} + \tau \quad \quad \textsf{Noisy Splits}$ \Else \State $t \gets \text{median} \left\{z^\top v: z \in A \cap \mathbf{X}\right\} \quad \quad \textsf{Median Splits}$ \EndIf \State $A_{\text{left}} \gets \left\{x \in A: x^\top v \leq t\right\}$ \State $A_{\text{right}} A - A_{\text{left}}$ \If {$A_{\text{left}}$ and $A_{\text{right}}$ are both non-empty} \State $\left(\text{children of A}\right) \gets A_{\text{left}}, A_{\text{right}}$ \EndIf \EndFor \State $\mathcal{A}_i \gets \text{partition of~}A_0\text{~defined by leaves of current tree~}$ \EndFor \end{algorithmic} \end{algorithm} } \kkdelete{ \begin{algorithm} \caption{\textsf{coreRPTree}($A \subset \mathcal{X}, \Delta, \delta$)} \begin{algorithmic}[1] \State Call $\textsf{basicRPtree}(A, \Delta)~~\log \left(3s/\delta\right)$ times and return the shortest tree \end{algorithmic} \end{algorithm} } \kkdelete{ \begin{algorithm} \caption{\textsf{adaptiveRPTree}(Sample $\mathbf{X} = \left\{X_1,X_2,\ldots,X_s\right\}$, Confidence parameter $\delta$, Accuracy parameter $\zeta$)} \begin{algorithmic}[1] \State $\mathcal{A}^0 \gets \mathbb{R}^p$ \State $C(s,\delta) \gets \log^2(s) \log\log(s/\delta) + \log(1/\delta)$ \For{$t=1,2,\ldots,$} \ForEach{cell $A \in \mathcal{A}^{t-1}$} \State (subtree rooted at A) $\gets \textsf{coreRPtree}(A, \Delta_s(A)/2, \delta)$ \EndFor \State $\mathcal{A}^{t}$ partition of $\mathbb{R}^p$ defined by the leaves of the current tree \If{$\frac{|\mathcal{A}^{t}| C(s,\delta)}{s} \geq \zeta$} \State{\Return} \EndIf \EndFor \State Return $\mathcal{A}^{t-1}$ as the final tree \end{algorithmic} \end{algorithm} } \kkdelete{ \begin{lemma} Suppose that we construct a random projection tree (a single one) using samples $\left\{X_i\right\}_{i=1}^s$, where $X_i \sim \mathcal{X}$. Furthermore, suppose that $\mathcal{X}$ has intrinsic dimension $d<<p$. Let $\theta \in (0,1)$ be a constant and suppose the target $x \sim \mathcal{X}$. Then, w.p. $1-\delta$ the following holds: there exists a set $\mathcal{F}_{\theta} \subset \mathcal{X}$ satisfying $\mu(\mathcal{F}_{\theta}) \geq 1-s^{-\theta}$ which under some appropriate stopping rule (that depends on $\theta$) for any $x \in \mathcal{F_\theta}$ \begin{equation*} \sup \left\{\|x-X_i\|_2: K(X_i,x, \left\{X_1,X_2,\ldots,X_s\right\})\right\}\right\})} \leq C(\delta,s) s^{-(1-\theta)/k}, \end{equation*} where $k = C_1 d \log d$, with $C(\delta,s) = O \left(\log(1/\delta) \log(s)^2\right)$ and $C_1$ being constants. \end{lemma} } \kkdelete{ \begin{remark} This is what I could establish during the summer. As you recall, if we build a forest using these random projection trees, there is no easy way for avoiding the union bound coming from sets $\mathcal{F}_\alpha$ for different sub-samples. Yet, I believe that if we assume $B$ is chosen according to $B \approx n/s$ we should be able to get some rate for MSE. \end{remark} \begin{remark} If we include the target point $x$ in the tree building process, we should be able to get the same result but with losing at most a factor of two. Basically, we construct a random projection tree on $\left\{X_1,X_2,\ldots,X_s\right\} \cup \left\{x\right\}$ and if $x$ ends up being in a leaf alone, we consider one level higher (where $x$ is not alone anymore) and we are good to go. We would only lose a factor of two. This is another possible way to deal with it I guess. \end{remark} } \end{comment}