Estimation based on nearest neighbor matching: from density ratio to average treatment effect

Estimation based on nearest neighbor matching: from density ratio to average treatment effect

{5pt} {5pt} {5pt} {5pt} \hypersetup{colorlinks,breaklinks,urlcolor=blue,linkcolor=blue}

{\bf Keywords:} graph-based statistics, stochastic geometry, double robustness, double machine learning, propensity score.

Introduction

With observations from different groups, matching methods greenwood1945experimental, chapin1947experimental aim to balance them through minimizing group differences in observed covariates. Such methods have proven their usefulness for causal inference in various disciplines, including economics imbens2004nonparametric, epidemiology brookhart2006variable, political science ho2007matching,sekhon2008multivariate, sociology morgan2006matching, and statistics cochran1973controlling,rubin2006matched,rosenbaum2010design.

Among all the matching methods, nearest neighbor (NN) matching rubin1973matching is likely the most well-used and easiest to implement approach. In addition, it is computationally attractive as the time complexity of locating NNs is low. In the simplest treatment-control study, NN matching assigns each treatment (control) individual to $M$ control (treatment) individuals with the smallest distance to it. In this regard, two natural questions arise. First, how do we select the number of matches, $M$? This is referred to in the literature as ratio matching, and is both important and delicate, well-known to be related to the bias-variance tradeoff in nonparametic statistics smith19976,rubin2000combining. Second, how do we perform large-sample statistical inference for NN matching methods? Such an analysis is usually nonstandard and thus believed to be mathematically challenging. Indeed, it was long-lacking in the literature until abadie2006large.

To answer the above two questions, in a series of ingenious papers, abadie2006large,abadie2008failure,abadie2011bias,abadie2012martingale established large-sample properties of $M$-NN matching for estimating the average treatment effect (ATE). These results are, however, only valid under a crucial assumption that, in ratio matching, $M$ is fixed. The according message is then mixed. As a matter of fact, abadie2006large argued --- which we quote here --- that the ATE estimator based on $M$-NN matching with a fixed $M$ is both asymptotically biased and statistically inefficient, namely, it “does not achieve the semiparametric efficiency bound as calculated by hahn1998role”. While bias correction is now feasible to alleviate the first issue abadie2011bias, the lack of efficiency seems fundamental.

This manuscript revisits the study of abadie2006large from a new perspective, bridging $M$-NN matching to density ratio estimation nguyen2010estimating,sugiyama2012density as well as double robustness scharfstein1999adjusting,bang2005doubly. To this end, our analysis stresses, in ratio matching, the importance of forcing $M$ to diverge with the sample size $n$ in order to achieve statistical efficiency. Our claim is thus aligned with similar ones in various other random graph-based inference problems MR2083,MR532236,MR947577,MR1212489,MR1701112,MR3909934,MR3961499, which also include a series of results made by some of the authors in this paper shi2021ac,shi2020power,lin2021boosting.

The contributions of this manuscript are mainly two-fold. First, we show that an intrinsic statistic that plays a central role in the analysis of abadie2006large, $K_M(x)$ (abadie2006large; to be defined in (ref) of Section (ref)), actually gives rise to a consistent density ratio estimator in the two-sample setting. Even more interestingly, from the angle of density ratio estimation, this NN matching-based estimator is to our knowledge the first one that simultaneously satisfies the following three properties.

This estimator itself is accordingly an appealing alternative to existing density ratio estimators. Moreover, it is potentially useful in many data analysis problems (e.g., $f$-divergence estimation, classification, importance sampling, and etc.) where density ratio estimation plays a pivotal role.

Getting back to the original ATE estimation problem, our second contribution is to bridge the above insights to the bias-corrected matching-based estimator proposed in abadie2011bias as well as the double robustness and double machine learning framework introduced in scharfstein1999adjusting, bang2005doubly, and chernozhukov2018double. In fact, their bias-corrected estimator can be formulated as \[ \hat{\tau}_M^{\rm bc} = \hat{\tau}^{\rm reg} + \frac{1}{n} \Big[ \sum_{i=1,D_i = 1}^n \Big(1 + \frac{K^1_M(i)}{M}\Big) \hat{R}_i - \sum_{i=1,D_i = 0}^n \Big(1 + \frac{K^0_M(i)}{M}\Big) \hat{R}_i \Big] \] (notation to be introduced in Section (ref)), where $1 + K^1_M(\cdot)/M$ and $1 + K^0_M(\cdot)/M$ approach the inverse of the propensity score $e(x)$ and $1-e(x)$, respectively. One could then leverage the general double robustness and double machine learning theory to validate the following two claims of (a double machine learning version of) $\hat{\tau}_M^{\rm bc}$.

Our results thus complement those made in abadie2006large,abadie2011bias, rendering necessary confidence for practitioners to implement NN matching for inferring the ATE. In addition, although abadie2006large hints at the necessity of allowing $M$ to diverge for gaining efficiency, we provide rigorous theory for their conjecture.

Technically speaking, our analysis hinges on those $M$'s that grow with $n$. Existing results in NN matching literature, including abadie2006large, abadie2008failure, abadie2011bias, and abadie2012martingale, are then limited as they are all focused on a fixed $M$. Instead, we take a different route to establish nonasymptotic moment bounds of $K_M(x)$, where there is more room for $M$ to move around; of note, similar ideas were also pursued in lin2021boosting by the authors to analyze rank-based statistics. Detailed explanation of our theoretical analysis, however, has to be left to latter sections.

\paragraph*{Paper organization.} The rest of this manuscript is organized as follows. In Sections (ref)-(ref) we introduce the method, computation, and theory of density ratio estimation via NN matching. In detail, Section (ref) introduces the statistical setup and the matching-based estimator of density ratio. Section (ref) introduces the algorithms to implement the matching-based estimator constructed on the $k$-d tree structure. Section (ref) delivers the main theory, quantifying both pointwise and global approximation accuracy. Built on the previous three sections, Section (ref) formally elaborates on the double robustness and semiparametric efficiency of the bias-corrected NN matching-based estimator of the ATE. More applications of the proposed matching-based estimator will be covered in Section (ref), with proofs of the main results relegated to Section (ref) and the rest put in the appendix. Additional results about NN matching that cannot be incorporated in the double robustness and double machine learning framework are exhibited in the supplement.

\paragraph*{Notation.} For any integers $n,d\ge 1$, let $\llbracket n\rrbracket:= \{1,2,\ldots,n\}$, $n!$ be the factorial of $n$, and $\bR^d$ be the $d$-dimensional real space. A set consisting of distinct elements $x_1,\dots,x_n$ is written as either $\{x_1,\dots,x_n\}$ or $\{x_i\}_{i=1}^{n}$, and its cardinality is written by $\lvert \{x_i\}_{i=1}^n \rvert$. The corresponding sequence is denoted $[x_1,\dots,x_n]$ or $[x_i]_{i=1}^{n}$. The notation $\ind(\cdot)$ is saved for the indicator function. For any $a,b \in \bR$, write $a \vee b = \max\{a,b\}$ and $a \wedge b = \min\{a,b\}$. For any two real sequences $\{a_n\}$ and $\{b_n\}$, write $a_n \lesssim b_n$ (or equivalently, $b_n \gtrsim a_n$ or $a_n=O(b_n)$) if there exists a universal constant $C>0$ such that $a_n/b_n \le C$ for all sufficiently large $n$, and write $a_n \prec b_n$ (or equivalently, $b_n \succ a_n$ and $a_n=o(b_n)$) if $a_n/b_n \to 0$ as $n$ goes to infinity. We write $a_n\asymp b_n$ if both $a_n\lesssim b_n$ and $b_n\lesssim a_n$ holds. We use $\stackrel{\sf d}{\longrightarrow}$ and $\stackrel{\sf p}{\longrightarrow}$ to denote convergence in distribution and in probability, respectively. For any sequence of random variables $\{X_n\}$, write $X_n = o_{\mathrm P}(1)$ if $X_n \stackrel{\sf p}{\longrightarrow} 0$. For any random variable $Z$, ${\mathrm P}_Z$ represents its law. Denote the closed ball in $\bR^d$ centered at $x$ with radius $\delta$ by $B_{x,\delta}$. In the sequel, let $c,C,C',C'',C''',...$ be generic positive constants whose actual values may change at different locations.

Density ratio estimation I: method

From this section to Section (ref), we consider $X,Z$ to be two general random vectors in $\bR^d$ that are defined on the same probability space, with $d$ to be a fixed positive integer.

Let $\nu_0$ and $\nu_1$ represent the probability measures of $X$ and $Z$, respectively. Assume $\nu_0$ and $\nu_1$ are absolutely continuous with respect to the Lebesgue measure $\lambda$ on $\bR^d$ equipped with the Euclidean norm $\lVert \cdot \rVert$; denote the corresponding densities (Radon-Nikodym derivatives) by $f_0$ and $f_1$. Assume further that $\nu_1$ is absolutely continuous with respect to $\nu_0$ and write the corresponding density ratio, $f_1/f_0$, as $r$; we set $0/0=0$ by default.

Assume $X_1,\ldots,X_{N_0}$ are $N_0$ independent copies of $X$, $Z_1,\ldots,Z_{N_1}$ are $N_1$ independent copies of $Z$, and $[X_i]_{i=1}^{N_0}$ and $[Z_j]_{j=1}^{N_1}$ are mutually independent. The problem of estimating the density ratio $r$ based on $\{X_1,\ldots,X_{N_0},Z_1,\ldots,Z_{N_1}\}$ is fundamental in economics cunningham2021causal, information theory cover1999elements, machine learning sugiyama2012density, statistics imbens2015causal, and other fields.

In density ratio estimation, NN-based estimators are advocated before due to its computational efficiency; cf. lima2008estimating, poczos2011estimation, kremer2015nearest, noshad2017direct, MR3909934, zhao2020minimax, among many others. In this manuscript, based on abadie2006large,abadie2008failure,abadie2011bias,abadie2012martingale's NN matching framework, we unveil a new density ratio estimator based on NN matching. To this end, some necessary notation is introduced first.

The following proposition formally links $K_M(\cdot)$ to $A_M(\cdot)$, was shown and used in the proof of abadie2006large, and is stated here for aiding understanding.

With these notation and concepts, we are now ready to introduce the following density ratio estimator based on NN matching.

The estimator $\hat r_M(\cdot)$ is by construction a one-step estimator, and thus automatically satisfies Property (ref) in \hyperref[sec:intro]{Introduction}. In the following two sections, we will show that $\hat r_M(\cdot)$ also satisfies Properties (ref) and (ref).

Density ratio estimation II: computation

This section discusses implementation of and establishes Property (ref) for the proposed estimator $\hat r_M(\cdot)$. To this end, we separately discuss two cases:

{\bf Case I.} In many applications, we are only interested in a functional of density ratios at observed sample points, i.e., the values of $\Phi\big(\{r(X_i)\}_{i=1}^{N_0}\big)$ for some given functions $\Phi$ defined on $\bR^{N_0}$. Check, e.g., (ref) and -- in a slightly different but symmetric form -- (ref) ahead for such examples on Kullback-Leibler (KL) divergence and ATE estimation. To this end, it is natural to consider the plug-in estimator $\Phi\big(\{\hat{r}_M(X_i)\}_{i=1}^{N_0}\big)$, for which it suffices to compute the values of $\{\hat{r}_M(X_i)\}_{i=1}^{N_0}$.

Built on the $k$-d tree structure bentley1975multidimensional for tracking NNs, Algorithm (ref) below outlines an easy to implement algorithm to simultaneously compute all the values of $\{\hat{r}_M(X_i)\}_{i=1}^{N_0}$. This algorithm could be regarded as a direct extension of the celebrated Friedman-Bentley-Finkel algorithm 10.1145/355744.355745 to the NN matching setting.

{\bf Case II.} Suppose we are interested in estimating density ratios at both the observed and $n$ new points in $\bR^d$. A naive algorithm is then to insert each new point into observed points and perform Algorithm (ref) in order. However, this algorithm is not ideal as the corresponding time complexity would be $n$ times the complexity of Algorithm (ref), which could be computationally heavy with a large number of new points.

Instead, we develop a more sophisticated implementation. Let the new points be $\{x_i\}_{i=1}^n$. Algorithm (ref) computes all the values of $\{\hat{r}_M(x_i)\}_{i=1}^n$ as well as $\{\hat{r}_M(X_i)\}_{i=1}^{N_0}$. The key message delivered here is that, compared to the aforementioned naive implementation, in Algorithm (ref) we only need to construct one single $k$-d tree; the matching elements are then categorized to two different sets, corresponding to those with regard to $X_i$'s and $x_i$'s, separately. Such an implementation is thus intuitively much more efficient.

The following is the main theorem of this section, elaborating on the computational advantage of the proposed estimator.

Density ratio estimation III: theory

This section introduces the theory for density ratio estimation based on NN matching. To this end, before establishing detailed theoretical properties (e.g., consistency and the rate of convergence) for $\hat r_M(\cdot)$, we first exhibit a lemma elaborating on the (asymptotic) $L^p$ moments of $\nu_1(A_M(x))$, the $\nu_1$-measure of the catchment area. This novel result did not appear in Abadie and Imbens's analysis. It is also of independent interest in stochastic and computational geometry in light of Remark (ref).

Consistency

We first establish the pointwise consistency of the estimator $\hat r_M(x)$ for estimating $r(x)$. This requires nearly no assumption on $\nu_0,\nu_1$ except for those made at the beginning of Section (ref), in line with similar observations made in NN-based density estimation MR3445317.

For evaluating the global consistency of the estimator, on the other hand, it is necessary to introduce the following (global) $L_p$ risk:

where $X$ is a copy drawn from $\nu_0$ that is independent of the data. For the $L_p$ risk consistency of the estimator, we impose conditions on $\nu_0$ and $\nu_1$ further as follows.

Denote the supports of $\nu_0$ and $\nu_1$ by $S_0$ and $S_1$, respectively. For any set $S\subset \bR^d$, denote the diameter of $S$ by \[ {\rm diam}(S):= \sup_{x,z \in S} \Big\lVert x-z \Big\rVert. \]

We then establish the $L_p$ risk consistency of the estimator via the Hardy–Littlewood maximal inequality stein2016singular; cf. Lemma (ref) ahead. Of note, this inequality was used in han2020optimal in a relative manner in order to study the information-theoretical limit of entropy estimation.

As a direct corollary of Theorem (ref), one can obtain the limit of any finite moment of $\nu_1(A_M(\cdot))$ with a random center. This could be regarded as a global extension of Lemma (ref).

Rates of Convergence

In this section we establish the rates of convergence for $\hat r(x)$ under both pointwise and global measures. We first consider the pointwise mean square error (MSE) convergence rate and show that $\hat r_M(\cdot)$ is minimax optimal in that regard. In the sequel, we fix an $x \in \bR^d$ and consider the following local assumption on $(\nu_0,\nu_1)$.

Define the following probability class \[ \cP_{x,\rm p}(f_L,f_U,L,d,\delta):=\Big\{(\nu_0,\nu_1): \text{Assumption \ref{asp:ptw} holds} \Big\}. \] The following theorem establishes the uniform pointwise convergence rate of $\hat r_M(\cdot)$.

The final rate of convergence in Theorem (ref), Equ. (ref) matches the established minimax lower bound in Lipschitz density function estimation MR2724359. By some simple manipulation, the argument in MR2724359 directly extends to density ratio as the latter is a harder statistical problem kpotufe2017lipschitz. This is formally stated in the following proposition.

We then move on to the case of a global risk and study the rates of convergence in this regard. To this end, a global assumption on $(\nu_0,\nu_1)$ is given below.

Define the following probability class

The next theorem establishes the uniform rate of convergence of $\hat r(\cdot)$ within the above probability class and under the $L_1$ risk. This rate is further matched by a minimax lower bound derived in Theorem 1 of zhao2020analysis using similar arguments as in the pointwise case.

Revisiting the matching-based estimator of the ATE

This section studies the bias-corrected NN matching-based estimator of the ATE, proposed in abadie2011bias to correct the asymptotic bias of the original matching-based estimator derived by abadie2006large. To this end, we leverage the new insights obtained in the last three sections, and bridge the study to both the classic double robustness framework scharfstein1999adjusting,bang2005doubly and the modern double machine learning framework chernozhukov2018double.

We first introduce the setup for the NN matching-based estimator and its bias-corrected version. Following abadie2006large, let $[(X_i,D_i,Y_i)]_{i=1}^n$ be $n$ independent independent copies of $(X,D,Y)$, where $D\in\{0,1\}$ is a binary variable, $X \in \bR^d$ represents the individual covariates, assumed to be absolute continuous admitting a density $f_X$, and $Y \in \bR$ stands for the outcome variable.

For each unit $i \in \llbracket n\rrbracket$, we observe $D_i=1$ if in the treated group and $D_i=0$ if in the control group. Let $n_0:=\sum_{i=1}^n (1-D_i)$ and $n_1:=\sum_{i=1}^n D_i$ be the numbers of control and treated units, respectively. Under the potential outcome framework rubin1974estimating, the unit $i$ has two potential outcomes, $Y_i(1)$ and $Y_i(0)$, but we observe only one of them: \[ Y_i =

\]

The goal is to estimate the following population ATE,

based on the observations $\{(X_i, D_i, Y_i)\}_{i=1}^n$. To estimate ATE, we consider its empirical counterpart

where $\hat{Y}_i(0)$ and $\hat{Y}_i(1)$ are the imputed outcomes of $Y_i(0)$ and $Y_i(1)$. With a fixed $M$, the matching-based estimator in abadie2006large imputes the missing potential outcomes by

Here for $\omega\in\{0,1\}$, $\mathcal{J}^\omega_M(i)$ represents the index set of $M$-NNs of $X_i$ in $\{X_j:D_j=\omega\}_{j=1}^n$, i.e., the set of all indices $j \in \llbracket n\rrbracket$ such that $D_j=\omega$ and \[ \sum_{\ell=1, D_\ell=\omega}^n \ind\Big(\lVert X_\ell -X_i \rVert \le \lVert X_j - X_i \rVert\Big) \le M. \] Let $K^\omega_M(i)$ be the number of matched times for unit $i$ such that $D_i=\omega$, i.e., \[ K^\omega_M(i) := \sum_{j=1, D_j = 1-\omega}^n \ind\Big(i \in \cJ^\omega_M(j)\Big). \] With the above notation and concepts, the matching-based estimator in abadie2006large can be written as

However, when $d>1$, the bias term of $\hat{\tau}_M$ is asymptotically non-negligible abadie2006large. To fix this, abadie2011bias proposed the following bias-corrected version for $\hat\tau_M$. In detail, let $\hat{\mu}_0(x)$ and $\hat{\mu}_1(x)$ be mappings from $\bR^d$ to $\bR$ that estimate the conditional means of the outcomes \[ \mu_0(x) := {\mathrm E} [Y \,|\, X=x,D=0]~~ {\rm and}~~ \mu_1(x) := {\mathrm E} [Y \,|\, X=x,D=1], \] respectively, with the corresponding residuals \[ \hat{R}_i := Y_i - \hat{\mu}_{D_i}(X_i), ~~i\in\llbracket n\rrbracket. \] The estimator based on the outcomes regression is \[ \hat{\tau}^{\rm reg}:= n^{-1} \sum_{i=1}^n \Big[\hat{\mu}_1(X_i) - \hat{\mu}_0(X_i)\Big]. \] One is then ready to check that the bias-corrected matching-based estimator in abadie2011bias has the following equivalent form, summarized as a lemma.

Equ. (ref) is related to doubly robust estimators. To compare them, we review the general double robustness framework. In detail, we first have some outcome models and residuals defined in the same way as above, and then let \[ \hat{e}(x):\bR^d \to \bR \] be a genetic estimator of the propensity score \[ e(x) := {\mathrm P}(D=1 \,|\, X =x). \] The doubly robust estimator in scharfstein1999adjusting and bang2005doubly could then be formulated as

Notice that conditional on $\mD := (D_1, \ldots, D_n)$, $[X_i:D_i=\omega]_{i=1}^n$ are $n_{\omega}$ i.i.d. random variables sampled from the distribution of $X \,|\, D=\omega$, and the two groups of sample points, \[ [X_i:D_i=0]_{i=1}^n ~~~{\rm and}~~~ [X_i:D_i=1]_{i=1}^n, \] are mutually independent. Denote the density of $X \,|\, D=\omega$ by $f_{X \,|\, D=\omega}$. From the construction of $K_M^0(i), K_M^1(i)$ and results in Section (ref), under the density assumptions and an appropriate choice of $M$, conditional on $\mD$, \[ \frac{n_0}{n_1} \frac{K^0_M(i)}{M}~~~{\rm and}~~~ \frac{n_1}{n_0} \frac{K^1_M(i)}{M} \] are consistent estimators of \[ \frac{f_{X \,|\, D=1}(X_i)}{f_{X \,|\, D=0}(X_i)} ~~~{\rm and}~~~\frac{f_{X \,|\, D=0}(X_i)}{f_{X \,|\, D=1}(X_i)}, \] respectively. Noting further that $n_1/n_0$ converges almost surely to ${\mathrm P}(D=1)/{\mathrm P}(D=0)$ by the law of large numbers, the following two statistics \[ \frac{K^0_M(i)}{M}~~~{\rm and }~~~\frac{K^1_M(i)}{M} \] are then consistent estimators of \[ \frac{e(X_i)}{1-e(X_i)}~~~{\rm and }~~~\frac{1-e(X_i)}{e(X_i)}, \] respectively. Thus, in view of (ref), the bias-corrected matching-based estimator $\hat{\tau}_M^{\rm bc}$ in (ref) is actually a doubly robust estimator of $\tau$, and accordingly, should also enjoy all the desirable properties of doubly robust estimators. This novel insight into abadie2011bias's bias-corrected matching estimator allows us to establish its asymptotic properties with a diverging $M$, which is the main topic in the rest of this section. It is worth mentioning here that Abadie and Imbens never pointed out the relation between matching-based ATE estimators and the double robustness framework, and there is no study in the double robustness literature that has analyzed NN matching-based estimators.

To formally state the properties, we first leverage the results of chernozhukov2018double. In the sequel, let $U_\omega := Y(\omega) - \mu_{\omega}(X)$ for $\omega \in \{0,1\}$ and $\bX$ be the support of $X$.

Lastly, we review the semiparametric efficiency lower bound for estimating ATE hahn1998role: \[ \sigma^2:= {\mathrm E} \Big[\mu_1(X) - \mu_0(X) + \frac{D(Y-\mu_1(X))}{e(X)} - \frac{(1-D)(Y-\mu_0(X))}{1-e(X)} - \tau \Big]^2. \] Theorem (ref) above and standard results on the double machine learning estimators (cf. chernozhukov2018double) then imply the following theorem, showing that, once allowing $M$ to diverge at an appropriate rate, $\hat{\tau}_M^{\rm bc}$ in (ref) constitutes a doubly robust estimator of $\tau$. In addition, the counterpart of $\hat{\tau}_M^{\rm bc}$ via sample splitting and cross fitting chernozhukov2018double, denoted by $\tilde{\tau}_{M,K}^{\rm bc}$ with $K \ge 2$ representing a fixed number of partitions, is semiparametrically efficient. Check the beginning of Theorem (ref)'s proof for a formal definition of $\tilde{\tau}_{M,K}^{\rm bc}$.

The analysis of $\hat\tau_M^{\rm bc}$ itself, on the other hand, cannot be directly incorporated in the double machine learning and its analysis has to be done independently. This is given in the next theorem based on the following two sets of assumptions.

As $d = 1$, by picking $\hat{\mu}_\omega = 0$ for $\omega \in \{0,1\}$, Assumption (ref) is automatically satisfied and the bias-corrected estimator $\hat\tau_M^{\rm bc}$ reduces to the original estimator $\hat\tau_M$ studied in abadie2006large. Theorem (ref) then directly implies the following corollary, which corresponds to abadie2006large but with one key difference that $M\to\infty$ here.

Discussion

The success of NN matching in estimating ATE raises natural question about possible extension to other functional estimation problems. In what follows we present some partial results along this direction for the KL divergence estimation, which is a topic of interest in many applications; cf. the references at the beginning of zhao2020minimax.

In detail, let's consider the same two-sample setting as Sections (ref)-(ref). Denote $\phi(x) := x\log x$ with the convention that $\phi(0) = 0$. We consider estimating the KL divergence between $\nu_1$ and $\nu_0$, written as

based on the data points $\{X_i\}_{i=1}^{N_0},\{Z_j\}_{j=1}^{N_1}$. To estimate $D_\phi(\nu_1 \Vert \nu_0)$, it is natural to consider the following plug-in estimator,

where $\hat r_M(\cdot)$ is the NN matching-based density ratio estimator introduced in Section (ref).

Define the following probability class

The following results establish the MSE convergence rate of $\hat{D}_\phi$ and show that the estimator is minimax optimal over $\cP_{\rm KL}(f_L,f_U,L,d,a,H,R,f_U')$. Under the condition that $N_0\gtrsim N_1$, this rate is further (up to some $\log n$-terms) minimax optimal in view of han2020optimal and similar arguments as used in Section (ref).

Proofs of the main results

\paragraph*{Additional notation.} We use $\mX$ and $\mZ$ to represent $(X_1,X_2,\ldots,X_{N_0})$ and $(Z_1,Z_2,\ldots,Z_{N_1})$, respectively. Let $U(0,1)$ denote the uniform distribution on $[0,1]$. In the sequel, let $U \sim U(0,1)$ and $U_{(M)}$ be the $M$-th order statistic of $N_0$ independent random variables from $U(0,1)$, assumed to be mutually independent and both independent of $(\mX,\mZ)$. It is well known that $U_{(M)}$ follows the beta distribution ${\rm Beta}(M, N_0+1-M)$. Let ${\rm Bin}(\cdot,\cdot)$ denote the binomial distribution. Let $L_1(\bR^d)$ denote the space of all functions $f:\bR^d\to\bR$ such that $\int|f(x)|{\mathrm d} x<\infty$. For any $x \in \bR^d$ and function $f:\bR^d \to \bR$, we say $x$ is a Lebesgue point of $f$ if \[ \lim_{\delta \to 0^+} \frac{1}{\lambda(B_{x,\delta})} \int_{B_{x,\delta}} \lvert f(x) - f(y) \rvert {\mathrm d} y = 0. \]

Proof of Lemma (ref)

Proof of Theorem (ref)

Proof of Theorem (ref)

Proof of Theorem (ref)

We only have to prove the first two claims as the rest are trivial.

Proof of Theorem (ref)