}_r)]&=\sum_{j=2}^{\lceil \frac{d}{2}-1\rceil}c_j\sum_{i\in\mathcal{I}}^{}w_i M_i^{-\frac{j}{d}}+\mathcal{O}(N^{-\frac{1}{2}})\\
	&\leq \sum_{j=2}^{\lceil \frac{d}{2}-1\rceil} c_j \epsilon N^{-\frac{1}{2}}+\mathcal{O}(N^{-\frac{1}{2}})
	\end{aligned}
	\end{equation}
	\endgroup
	Using Lemma 1, this can be upper bounded by 
	\begin{equation}
	\mathbb{B}[\Phi_k(N,\mathbf{w}_r)]\leq \sum_{j=2}^{\lceil \frac{d}{2}-1\rceil} c_j \epsilon^* N^{-\frac{1}{2}}+\mathcal{O}(N^{-\frac{1}{2}})
	\end{equation}
	thus ensuring that $\mathbb{B}[\Phi_k(N,\mathbf{w}_r)]=\mathcal{O}(N^{-\frac{1}{2}})$. Similarly, we can express the variance as
	\begin{equation}
	\begin{aligned}
	\mathbb{V}[\Phi_k(N,\mathbf{w}_r)]\leq \frac{\epsilon}{4N}\leq \frac{\epsilon^*}{4N}=\mathcal{O}(N^{-1}).
	\end{aligned}
	\end{equation}
	Since both $\mathbb{B}[\Phi_k(N,\mathbf{w}_r)]^2$ and $\mathbb{V}[\Phi_k(N,\mathbf{w}_r)]$ are bounded by rate $\mathcal{O}(N^{-1})$, the MSE must be bound by this rate as well.
	
	It is worth noting that while Theorem \ref{thm:Main} guarantees $\mathcal{O}(N^{-1})$ convergence asymptotically, it may converge more slowly for specific ranges of $N$.
	
	Returning to the original problem of estimating an unknown density functional $G(f_0,f_1)$, we can update the estimator $\hat{G}(\mathbf{X},\boldsymbol{\alpha})$ described in \eqref{eq:G_estimator1} to be a linear combination of these ensemble estimators
	\begin{equation}
	\hat{G}(\mathbf{X},\boldsymbol{\alpha})=\sum_{k\in\mathcal{K}}^{}\alpha_k \Phi_k(N,\mathbf{w}_r).
	\label{eq:Combined_Estimator}
	\end{equation}

	If $\hat{G}(\mathbf{X},\boldsymbol{\alpha})$ is an asymptotically consistent estimate of $G(f_0,f_1)$, then the bias is




	\begin{equation}
	\mathbb{B}[\hat{G}]=\sum_{k\in\mathcal{K}}^{}\alpha_k 	\mathbb{B}[\Phi_k(N,\mathbf{w}_r)],
	\label{eq:bias_combined}
	\end{equation}
	and we can bound the variance by
	\begingroup\makeatletter\def\f@size{8.5}\check@mathfonts
	\def\maketag@@@#1{\hbox{\m@th\normalsize\normalfont#1}}%
	\begin{equation}
	\mathbb{V}[\hat{G}]\leq\sum_{k\in\mathcal{K}}^{}\sum_{j\in\mathcal{K}}^{}\alpha_j \alpha_k 	\sqrt{\mathbb{V}[\Phi_j(N,\mathbf{w}_r)]\mathbb{V}[\Phi_k(N,\mathbf{w}_r)]}.
	\label{eq:var_combined}
	\end{equation}
	\endgroup
	Since all of the basis functions comprising $\hat{G}(\mathbf{X},\boldsymbol{\alpha})$ achieve an MSE convergence rate of $\mathcal{O}(N^{-1})$, the combined estimator also converges at rate $\mathcal{O}(N^{-1})$.
	

	
	\section{Numerical Results}

	
	
	\label{sec:simulation_overview}
	To evaluate the efficacy of the method proposed in this paper we consider the problem of estimating the Hellinger distance between two multivariate normal distributions. In this experiment each class PDF is distributed according to  $f(\mathbf{x})\sim N(\mu \mathbf{1}_d,\mathbf{\Sigma}_d)$, where the $i,j$ term in $\mathbf{\Sigma}_d$ is defined by $\sigma_{i,j}=\beta^{|i-j|}$ for all $i,j\in [1,\dots,d]$. We set $\mu=0$ and $\beta=0.8$ for distribution $f_0(\mathbf{x})$ and $\mu=1$ and $\beta=0.9$ for distributions $f_1(\mathbf{x})$. This set of parameters offers each distribution a unique elliptical covariance structure and was identified as particularly challenging for direct estimation in \cite{wisler2017data}. 






















	
		\begin{figure*}[!htb]
			\begin{center}
				\subfloat[Estimates of $R_1$]{
					\includegraphics[width=0.49\textwidth]{Plot_1.eps}
					\label{fig:k1_dplot}
				}	
				\subfloat[MSE of $R_1$ estimates]{
					\includegraphics[width=0.49\textwidth]{Plot_2.eps}
					\label{fig:k1_MSE}
				}\\
				\subfloat[Estimates of $H^2(f_0,f_1)$]{		
					\includegraphics[width=0.49\textwidth]{Plot_3.eps}
					\label{fig:Hellinger_dplot}
				}
				\subfloat[MSE of  $H^2(f_0,f_1)$ estimates]{
					\includegraphics[width=0.49\textwidth]{Plot_4.eps}
					\label{fig:Hellinger_MSE}
				}	 				
				\caption{(a) \& (c) display the mean and standard error across sample size for each estimator of the $1$-NN classifier error rate and Hellinger-squared distance respectively, while (b) \& (d) display the corresponding MSE results for these estimators. These results reflect the average of $1000$ Monte Carlo trials where the $12$ $l_i$ values are logarithmically spaced between $0.05$ and $0.5$ and $\mathbf{k}=[1,3,5,7,9]$.}
				\label{fig:Exp3Plots}
			\end{center}
		\end{figure*}	
	
	At each sample size $N$, we compare 3 methods of estimating $R_k$ for all $k\in \mathbf{k}$. The first method is to simply evaluate the error rate of a $k$-NN classifier on the held-out portion of the data. We then generate ensemble estimates using the relaxed method described in Section \ref{sec:ensemble_method} using $\lambda=0.1$ and $\lambda=1$. For the $k=1$ basis, the resulting estimates are displayed relative to the ground truth in Figure \ref{fig:k1_dplot}, and the corresponding MSE is displayed in Figure \ref{fig:k1_MSE}. We see that while all three estimates contain some finite-sample bias, the bias is significantly reduced using the proposed method, particularly when $\lambda$ is set to prioritize minimization of the bias more heavily. As a result of the reduced bias, we see a significant improvement in the rate at which the MSE decays with $N$ in Figure \ref{fig:k1_MSE}.	It is worth noting that, despite the improvement, the slope of the MSE for the ensemble methods here is not indicative of the $\mathcal{O}(N^{-1})$ rate guaranteed by the proposed ensemble method since the theorem does not guarantee that it converges consistently at this rate across all $N$. As we increase the sample size, we expect that the rate would eventually reach the expected $\mathcal{O}(N^{-1})$.
	
	Next we evaluate the ensemble method when using $R_k(N)$ as a basis set for estimating density functionals like the squared Hellinger distance:
	\begin{align}
	H^2(f_0, f_1) & = \frac{1}{2} \int \left ( \sqrt{f_0(\mathbf{x})} - \sqrt{f_1(\mathbf{x})} \right)^2 d\mathbf{x} \\
	& = \frac{1}{2} \int g(\eta) f_{\mathbf{x}} (\mathbf{x}) d\mathbf{x},
	\end{align}	
	where $g(\eta) = (\sqrt{\eta} - \sqrt{1-\eta})^2$. Estimates of the Hellinger distance are generated using