\section{Introduction}
\label{section: introduction}
Let
\begin{equation}
\label{model}
	\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} = \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} + \bfsym {\xi},~\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \RR^d,
\end{equation}
be the Gaussian shift model with $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$ being an observation, $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \RR^d$ being an unknown parameter, and $\bfsym {\xi} \in \RR^d$ being a mean zero non-degenerate Gaussian random noise with covariance matrix $\bSigma\in \RR^{d\times d}$.
The goal of this article is to study the problem of estimating $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ for a given smooth function $f: \RR^d \rightarrow \RR$ when the complexity of the problem, characterized by the effective rank
$\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)$ of $\bSigma$, becomes large.
To be more specific, we denote by $\|\bSigma\|_{op}:=\sigma^2$ as the noise level of the problem with some $\sigma>0$.
Without loss of generality, we assume that $\sigma<1$.
Suppose that $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma):=\sigma^{-2\alpha}$ and $d:=\sigma^{-2\beta}$ with some
$0<\alpha\leq \beta <1$.
An important application lies behind such setting is the classical Gaussian sequence model
where the dimension is allowed to grow with the sample size.
To establish the connection, we assume that $n$ i.i.d. copies $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_1$, $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_2$, ..., $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_n$ of a random vector $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\in\RR^d$ are observed:
$\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_j = \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}_j,~j=1,...,n$
where $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \RR^d$ is an unknown parameter and $\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}_j$'s are i.i.d. copies of a noise vector that yields the multivariate normal distribution $\mathcal{N}(\mathbf{0}, \bSigma_0)$. $\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}_j$'s can be treated as the measurement noise when one observes $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}$. This indicates that the problem we study appears almost everywhere in real world applications.
Then the sample mean $\bar{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}}= n^{-1}\sum_{j=1}^n \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_j$ which is a sufficient statistic used to estimate $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}$ can be equivalently rewritten as a form of model (\ref{model}):
\begin{equation}
\label{model: sequence}
	\bar{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}}=\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} + \bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}
\end{equation}
with $\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}\sim \mathcal{N}(\mathbf{0}; n^{-1}\bSigma_0)$. In this case, $\bSigma = n^{-1}\bSigma_0$ with $\|\bSigma_0\|_{op}= O(1)$,
$\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) = \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0) = n^{\alpha}$ with $\alpha\in (0,1)$, and the intrinsic dimension grows to infinity as the sample size $n\rightarrow \infty$.

Studies under the setting where the dimension of the underlying parameter is allowed to grow with the sample size can be traced back to \cite{portnoy1984asymptotic,portnoy1985asymptotic,portnoy1986asymptotic,mammen1989}.
Early results in the study of efficient estimation of smooth functionals were mostly focused on infinite-dimensional parameter space where people were trying to build the connection between the geometric complexity of the parameter space and the modulus of continuity of the functional.
Notable results include but not limited to~\cite{levit1976efficiency,levit1978asymptotically,ibragimov2013statistical,ibragimov1986some,bickel1988estimating,nemirovskii1991necessary,nemirovski2000topics,birge1995estimation,laurent1996efficient,lepski1999estimation}. Two types of special functionals are extensively studied. Results on estimation of linear functionals include~\cite{donoho1987minimax,donoho1991geometrizing,cai2005adaptive,klemela2001sharp} and the references therein.
Results in terms of estimation of quadratic functionals include~\cite{donoho1990minimax,cai2005nonquadratic,klemela2006sharp,laurent2000adaptive,bickel2003} and the references therein. Recent results show a surge of interest
in efficient and minimax optimal estimation of functionals of parameter in high dimensional models or models with growing dimension, see~\cite{collier2017minimax,collier2018estimation,van2014asymptotically,doi:10.1111/rssb.12026,koltchinskii2018efficient}.

We consider a given function $f$ which belongs to the inhomogeneous Besov space $B_{\infty,1}^s(\RR^d)$ with $s$ being a characterization of its smoothness. According to the well known Littlewood-Paley decomposition, for any
$f\in B_{\infty,1}^s(\RR^d)$ with $s\geq 0$, $f$ can be well approximated by a function series $f^N:= \sum_{j=0}^N f_j$ in the space of tempered distributions $\mathcal{S}'(\RR^d)$. Especially,
$\sum_{j=0}^Nf_j$ converges to $f$ uniformly in $\RR^d$.
Based on the fruitful idea of Littlewood-Paley theory and the seminal work by A. N. Kolmogorov \cite{kolmogorov1950unbiased} on unbiased estimation, we construct a new estimator in Section \ref{section: estimator} via a Fourier analytical approach and define it as
\begin{equation}
\label{estimator: intro}
g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) :=   \frac{1}{(2\pi)^{d/2}}   \int_{\Omega}  \mathcal{F} f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta},
\end{equation}
where $\mathcal{F}f^N$ denotes the Fourier transformation of $f^N$ and $\Omega$ denotes its support.
The new estimator is easy to implement and can be widely used in practice since it deals with Fourier transform data.
For instance, Fourier transform is used widely throughout medical imaging where its applications include:
determining the spatial resolution of imaging systems, spatial localisation in magnetic resonance imaging, analysis of Doppler ultrasound signals,
and image filtering in emission and transmission computed tomography.
An immediate implication following the construction of $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ is that $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ is an unbiased estimator
of $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ when $f$ is an entire function of exponential type. In Section \ref{section:bias}, we show that for a general $f\in B_{\infty,1}^s(\RR^d)$, the bias of $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ is
\begin{equation}
	|\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})| \lesssim \|f\|_{B^s_{\infty,1}} \sigma^{(1-\alpha)s}.
\end{equation}

In Section \ref{section: concentration_remainder} we show that when the operator norm of the Hessian function $\|\nabla^2 g\|_{op}$ is properly controlled,
\begin{equation}
\label{rate: upper1}
\EE_{\theta}(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \lesssim (\sigma^2 \vee \sigma^{2(1-\alpha)s})
\end{equation}
given $0<\sigma<1$. Despite the important role $\|\nabla^2 g\|_{op}$ plays in bounding the MSE,
it depends on the shape of the support $\Omega$ of $\mathcal{F}f^N$ that can vary for different functions $f$. In Section \ref{section: Hessian}, we derive a uniform bound on $\|\nabla^2 g\|_{op}$
and show that when the problem resides in a moderately high dimensional setting where non-trivial bias correction is needed, namely $\alpha \in (1/2,1)$, $\|\nabla^2 g\|_{op}$
is uniformly bounded, thus
\begin{equation}
\label{rate: upper2}
\sup_{\|f\|_{B^s_{\infty,1}}\leq 1} \EE_{\theta}(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \lesssim (\sigma^2 \vee \sigma^{2(1-\alpha)s}) \wedge 1.
\end{equation}
Note that such rate can not be achieved in this regime by the standard Delta Method with the plug-in estimator $f(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ which is usually asymptotically efficient for fixed dimension models. A recent
series of works by~\cite{koltchinskii2018asymptotically} and~\cite{koltchinskii2018efficient} considered similar problems via a different approach. Especifically, they developed an innovative method through
iterative bootstrap to achieve bias reduction and established similar rate as in (\ref{rate: upper2}) for Gaussian shift model~\cite{koltchinskii2018efficient} in Banach space over a H\"{o}lder type class.
Another work~\cite{jiao2017bias} used the similar approach as in~\cite{koltchinskii2018asymptotically} and~\cite{koltchinskii2018efficient} to study the estimation of smooth function of parameter of binomial model.

In Section \ref{section: lower}, we show that under standard Gaussian shift model where $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)=d$, the minimax lower bound is
\begin{equation}
\label{rate: lower}
\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \gtrsim   \big(\sigma^2 \vee ( \sigma^2d )^s \big) \wedge 1.
\end{equation}
 (\ref{rate: lower}) perfectly matches (\ref{rate: upper2}). This shows the minimax optimality of our estimator (\ref{estimator: intro}) and the rate (\ref{rate: upper2}) is indeed the minimax rate. It bridges the gap between the upper and lower bounds by removing a logarithmic factor introduced in the minimax lower bound in~\cite{koltchinskii2018efficient}.
The proof of the lower bound is based on some new construction and ideas which are different from the existing results. We believe the current methods are more general.

Combining the upper bound (\ref{rate: upper2}) and the lower bound (\ref{rate: lower}), we establish a sharp threshold on smoothness $s$ in terms of dimensionality such that when $s\geq 1/(1-\alpha)$, the MSE of estimation of $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ can be controlled by $\sigma^2$ given $\sigma^2$ is small. Such type of results were previously studied by~\cite{ibragimov1986some,nemirovskii1991necessary,nemirovski2000topics} in which the authors built the threshold on the smoothness in terms of Kolmogorov widths which characterized the complexity of the parameter space.

In Section \ref{section: normal}, we prove the normal approximation bound of our estimator. Especially, we show that with an appropriate control on the decay of $\big\|\|\nabla\widetilde{f}^N\|\big\|_{\infty}$, our estimator is asymptotic efficient in the spirit of H\'{a}jek and Le Cam.
In Section \ref{section: adaptive}, we propose a data-driven estimator under model (\ref{model: sequence}) when the covariance matrix $\bSigma$ is unknown and show that it achieves the same level of performance as (\ref{estimator: intro}).
Numerical simulation results are presented in Section \ref{section: simulation} to validate our theory. It shows that the new estimator's performance
is superior to its plug-in counterpart on both bias and variance reduction when the dimension is large.

\section{Preliminaries and Notations}

\subsection{Notations}

We use boldface uppercase letter $\bX$ to denote a matrix and boldface lowercase letter $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$ to denote a vector.
We use $\|\cdot\|$ to denote the $\ell_2$-norm of a vector, $\|\cdot\|_{op}$ to denote the spectral norm (largest singular value) of a matrix, and $\|\cdot\|_p$ to denote the $L^p$-norm of a function.
For a covariance matrix $\bSigma$, we use $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma): = {\rm tr}(\bSigma)/\|\bSigma\|_{op}$ to denote its effective rank. In the rest of this article, we will frequently use the notation
$\sigma^2:= \| \bSigma\|_{op}$ to denote the noise level. Without loss of generality, we always assume that $\sigma^2 \in (0,1)$. Particularly, in view of model (\ref{model: sequence}), one can always have
$\sigma^2 = n^{-1}$ in mind, where $n$ denotes the sample size. We use ${\cal  S}} \def\cS{{\cal  S} = {\cal  S}} \def\cS{{\cal  S}(\RR^d)$ to denote the Schwartz space and ${\cal  S}} \def\cS{{\cal  S}'={\cal  S}} \def\cS{{\cal  S}'(\RR^d)$ to denote the set of all complex-valued tempered distributions on $\RR^d$. Given a multi-index $\bfsym \alpha:=(\alpha_1,...,\alpha_d)$, we denote by $D^{\bfsym \alpha} = \frac{\partial^{|\bfsym \alpha|}}{\partial x_1^{\alpha_1}\dots \partial x_d^{\alpha_d}}$ and $|\bfsym \alpha| = \alpha_1+\dots+\alpha_d$.

We use $\mathcal{F}$ and $\mathcal{F}^{-1}$ to denote the Fourier transform (FT) and inverse Fourier transform (IFT) respectively. Throughout the paper, given nonnegative $a$ and $b$, $a\lesssim b$ means
that $a\leq Cb$ for a numerical constant $C$, and $a \asymp b$ means that $a \lesssim b$ and $b \lesssim a$. $a \wedge b = \min \{ a, b\}$ and $a \vee b = \max \{ a, b\}$.

\subsection{Besov Space and Basic Embedding Theorems}
\label{pre: besov}
In the following, we introduce the basic definitions of resolution of unity and Besov spaces.
\begin{dfn}
	Let $\Phi(\RR^d)$ be the collection of all systems  $\varphi = \{\varphi_{j}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})\}_{j=0}^{\infty} \subset \mathcal{S}(\RR^d)$ such that
	${\rm supp} (\varphi_0) \subset \{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} : \|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\| \leq 2\}$,
	and ${\rm supp} (\varphi_j) \subset \{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} : 2^{j-1} \leq \|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \|  \leq 2^{j+1}\},~j\in \NN^*$,
	for every multi-index $\bfsym \alpha$ there exists a positive number $c_{\alpha}$ such that
	\begin{equation}
		2^{j|\bfsym \alpha|} |D^{\bfsym \alpha}\varphi_j(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})| \leq c_{\alpha}
	\end{equation}
	for all $j\in \NN$ and all $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \in \RR^d$ and $\sum^{\infty}_{j=0} \varphi_j(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) = 1$ for every $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \in \RR^d$.
\end{dfn}
\begin{remark}
	For any $\varphi \in \Phi(\RR^d)$, it provides a smooth resolution of unity.
\end{remark}

\begin{dfn}
	\label{definition: besov}
	Let $-\infty < s < \infty$, $0<p\leq \infty$, and $0<q\leq \infty$. Let $\phi = \{\phi_{j}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})\}_{j=0}^{\infty} \in\Phi(\RR^d)$. Then the Besov spaces is defined as
	\begin{equation}
	B^s_{p,q}(\RR^d) = \{f : f\in \mathcal{S}'(\RR^d), \|f\|_{B^s_{p,q}} <\infty \},
	\end{equation}
	where
	\begin{equation}
	\label{LPD}
	\|f\|_{B^s_{p,q}} = \big\|(2^{js} \|f_j\|_{L^p})_{j=0}^{\infty}\big\|_{\ell_q},~~and~~f_j = \mathcal{F}^{-1}\phi_j\mathcal{F}f.
	\end{equation}
\end{dfn}
\begin{remark}
	Especially, when $1\leq p ,q\leq \infty$, $B^s_{p,q}(\RR^d)$ is a Banach space. Clearly, for each $j$, $\mathcal{F}f_j$ has a compact support. Then by the well known Paley-Wiener-Schwartz theorem (see~\cite{hormander2015analysis}), $f_j$ is an entire function in $\RR^d$. Therefore (\ref{LPD}) defines the Littlewood-Paley dyadic decomposition of $f$ in terms of a sequence of analytic functions $\{ f_j\}_{j=0}^{\infty}$.
\end{remark}

We introduce the H\"{o}lder spaces as follows, which are another commonly studied function spaces closely related to the function space that we will study in this article.
\begin{dfn}
	Let $s>0$ and $s \notin \NN^*$ be a real number such that $s = \lfloor s \rfloor+\{s\}$, where $\lfloor s \rfloor$ is an integer and $0 < \{s\} <1$, then the H\"{o}lder space $C^s(\RR^d)$ is defined as
	\begin{equation}
		C^s(\RR^d) = \big\{   f:  f \in C^{\lfloor s \rfloor}(\RR^d),~\| f\|_{C^s}< \infty \big\},
	\end{equation}
	where
	\begin{equation*}
		\|f \|_{C^s}  = \sum_{|\alpha|\leq \lfloor s\rfloor } \|D^{\alpha} f\|_{\infty} + \sum_{|\alpha| = \lfloor s \rfloor} \sup_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \neq \bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y}} \frac{|{\cal  D}} \def\cD{{\cal  D}^{\bfsym \alpha}f(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - D^{\alpha}f(\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y}) | }{|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}-\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y}|^{\{s\}}} .
	\end{equation*}

\end{dfn}

In the rest of this article, we consider the case where $s\geq 1$, $p=\infty$ and $q=1$, namely, $B^s_{\infty,1}(\RR^d)$. It is easy to see that if $f\in B^s_{\infty,1}(\RR^d)$ for some $s\geq 0$, then
$\sum_{j\geq 0} f_j$ converges uniformly to $f$ in $\RR^d$. Meanwhile, it is easy to see that $\|f\|_{\infty} \leq \sum_{j=0}^{\infty} \|f_j\|_{\infty} <\infty$ which implies that $f\in C_u(\RR^d)$, where $C_u(\RR^d)$ denotes the space of all bounded uniformly continuous functions in $\RR^d$. Thus, $B_{\infty,1}^s(\RR^d)$ is continuously embedded in $C_u(\RR^d)$. In this article, when we use $A \subset B$ and $A$, $B$ are
two function spaces, it always means $A$ can be continuously embedded in $B$. The following embedding theorems are quite elementary and well known.

\begin{proposition}\
	\begin{enumerate}
		\item Let $0<q_0 \leq q_1 \leq \infty$ and $-\infty < s < \infty$. Then
		\begin{equation}
			B^s_{p,q_0}(\RR^d) \subset 	B^s_{p,q_1}(\RR^d),~{\rm if}~0<p\leq \infty.
		\end{equation}
		\item Let $0< q_0\leq \infty$, $0<q_1\leq \infty$, $-\infty <s < \infty$ and $\varepsilon>0.$ Then
		\begin{equation}
			B^{s+\varepsilon}_{p,q_0}(\RR^d) \subset 	B^s_{p,q_1}(\RR^d),~{\rm if}~0<p\leq \infty.
		\end{equation}
		\item If $s>0$, then for H\"{o}lder space $C^s(\RR^d)$
		\begin{equation}
			C^s(\RR^d) = B^s_{\infty,\infty}(\RR^d).
		\end{equation}
	\end{enumerate}

\end{proposition}

\begin{remark}
	As a direct consequence of Proposition 2.1, we see that $C^{s'}(\RR^d) \subset B^s_{\infty,1}(\RR^d) \subset C^s(\RR^d)$ for $0<s<s'<\infty$. Thus, the
	Besov condition we consider is stronger than the H\"{o}lder condition with the same smoothness but weaker than that with strictly more smoothness.
\end{remark}

\subsection{Entire Function of Exponential Type}

The entire function of exponential type is also related to this article. We introduce the definition as follows.
\begin{dfn}
	Let $f: \CC^d \rightarrow \CC$ be an entire function and $\sigma:=(\sigma_1,...,\sigma_d)$, $\sigma_j>0$. Function $f$ is of exponential type $\sigma$ if for any
	$\varepsilon >0 $ there exists a constant $C(\varepsilon,\sigma,f)>0$ such that
	\begin{equation}
		\big| f(\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}) \big| \leq C(\varepsilon,\sigma,f) e^{\sum_{j=1}^d (\sigma_j+\varepsilon)|z_j|},~\forall \bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z} \in \CC^d.
	\end{equation}
\end{dfn}

The following theorem is part of the famous Paley-Wiener-Schwartz theorem:
\begin{theorem}
	The following two assertions are equivalent:
	\begin{enumerate}
		\item $\varphi \in \mathcal{S}'$ and ${\rm supp}(\mathcal{F}\varphi)\subset \{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}:\|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\|\leq \sigma \}$ is bounded;
		\item $\varphi(\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z})$ for all $\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z} \in \CC^d$ is an entire function of exponential type $\sigma$.
	\end{enumerate}
\end{theorem}
We refer to Theorem 1.7.7 in~\cite{hormander2015analysis} for a more detailed discussion in case the reader is interested.

\section{Estimator Construction and Bias Reduction}
\label{section: estimator}
In this section, we introduce a bias reducing estimator based on a Fourier analytical approach and the Gaussian kernel. The origin of this idea can be traced back to A.N. Kolmogorov~\cite{kolmogorov1950unbiased}
when the author tried to build the connection between unbiased estimation in Gaussian shift model with ``the inverse heat conductivity problem".
The intuition that lies behind the construction of the estimator is pretty straight forward. To find a good estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ of $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ with small bias depends on how well one can solve the following
integral equation
\begin{equation}
\label{equation: integral}
	\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) = f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}).
\end{equation}
Instead of solving it directly which is hard typically, we approximately solve it by replacing the right hand side with some good approximation of $f$. The proxy of $f$ is chosen by a rescaled truncation on $f$'s frequency domain based on the well known Littlewood-Paley decomposition. A different approach based on a bootstrap chain bias reduction technique was developed recently by~\cite{koltchinskii2018asymptotically,koltchinskii2018efficient} to approximately solve (\ref{equation: integral}) which achieves the same order bound on the bias as our estimator. The bootstrap chain
bias reduction technique is also used in~\cite{jiao2017bias} to estimate smooth functions of the parameter of binomial models.

To start with, we review some of the basic knowledge from PDE, and harmonic analysis. Based on our model (\ref{model}), we have $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\sim \mathcal{N}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}; \bSigma)$.
We denote the density function of $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$ by
$$
p(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta},\bSigma) := \frac{1}{\sqrt{(2\pi)^d  |\bSigma|}}\exp\Big\{  - \frac{1}{2} \langle \bSigma^{-1}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}-\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}-\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\rangle \Big\},
$$
where $|\bSigma|$ denotes the determinant of $\bSigma$.
For any given estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ of $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$, it is easy to check that
\begin{equation}
\label{expectation}
\mathbb{E}_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) = \mathbb{E}_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+\bfsym {\xi}) =  \mathbb{E}_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\xi}) =  \int_{\mathbb{R}^d} g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\zeta}) p(\bfsym {\zeta}|{\bf 0}; \bSigma) d\bfsym {\zeta}.
\end{equation}
Note that the right hand side of (\ref{expectation}) is the convolution of $g$ with a Gaussian density $p$ with zero mean and covariance matrix $\bSigma$. We denote by $h$ this convolution
\begin{equation}
\label{convolution}
h(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) := g \ast p^o (\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) =  \int_{\mathbb{R}^d} g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\zeta}) p(\bfsym {\zeta}|{\bf 0}; \bSigma) d\bfsym {\zeta},
\end{equation}
where $p^o(\bfsym {\zeta}):=p(\bfsym {\zeta}|{\bf 0}; \bSigma) $.
Recall that the Fourier Transform of a function $f:\mathbb{R}^d\rightarrow \mathbb{R}$ is defined as
$$
\mathcal{F}f(\bfsym {\zeta}) := \frac{1}{(2\pi)^{d/2}}\int_{\mathbb{R}^d} f(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) e^{-i \bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}}d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}.
$$
Given (\ref{convolution}), the basic properties of Fourier transform and convolution (see~\cite{reed1975ii}, page 6) lead to
\begin{equation}
\label{conv2}
\mathcal{F} h = \mathcal{F} (g \ast p^o) = (2\pi)^{d/2} \mathcal{F}g \cdot \mathcal{F}p^o.
\end{equation}
It is easy to see that
$$
\mathcal{F} p^o(\bfsym {\zeta})  = \frac{1}{(2\pi)^{d/2}} \int_{\mathbb{R}^d} \frac{1}{\sqrt{(2\pi)^d  |\bSigma|}}  e^{ - \frac{1}{2} \langle \bSigma^{-1}\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}, \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\rangle  }e^{- i\bfsym {\zeta}\cdot\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}}d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}
= \frac{1}{(2\pi)^{d/2}} e^{-\frac{1}{2}\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle}.
$$
Thus, from (\ref{conv2}) we have
$$
\mathcal{F} g (\bfsym {\zeta}) =\mathcal{F} h(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}.
$$
Now we take the Inverse Fourier Transform of $\mathcal{F}g(\bfsym {\zeta})$ and get our estimator
\begin{equation}
\label{estimator: general}
g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) =\mathcal{F}^{-1} (\mathcal{F} g) =  \frac{1}{(2\pi)^{d/2}} \int_{\mathbb{R}^d} \mathcal{F} g (\bfsym {\zeta}) e^{ i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}}d\bfsym {\zeta} =  \frac{1}{(2\pi)^{d/2}}   \int_{\mathbb{R}^d}  \mathcal{F} h(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta} .
\end{equation}
One should notice that the integral in (\ref{estimator: general}) can be meaningless when the integral on the right hand side diverges. Indeed, the term $e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}$ inside the integral grows exponentially fast when $\|\bfsym {\zeta}\|$ goes to infinity. If $|\mathcal{F} h(\bfsym {\zeta})|$ does not decay fast enough as $\|\bfsym {\zeta}\|$ goes to infinity, then $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ in (\ref{estimator: general}) may not be well defined.

We consider a given function $f\in B^s_{\infty,1}(\RR^d)$. According to our discussion in Section \ref{pre: besov}, the series $\sum_{j\geq 0} f_j$ converges uniformly to $f$ in $\RR^d$ with
$\supp({\cal  F}} \def\cF{{\cal  F} f_j) = \{ \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}: 2^{j-1} \leq \| \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\| \leq 2^{j+1} \}$ for all $j\geq 1$. Take
\begin{equation}
\label{N}
N := \lceil(\log_2 1/\|\bSigma\|_{op} -\log_2 \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) - 2)/2 \rceil
\end{equation}
where $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)$ denotes the effective rank of $\bSigma$.
Then we denote by $f^N := \sum_{j=0}^Nf_j$ and the remainder $\tilde{f}^N := f-f^N$.
It is easy to see that both $f^N$ and $\tilde{f}^N$ are still in $B^s_{\infty,1}(\RR^d)$ thus are continuous and uniformly bounded functions. Now we formally introduce the estimator
$g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ of $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ under model (\ref{model}) as the following:
\begin{equation}
\label{estimator: f}
g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) :=   \frac{1}{(2\pi)^{d/2}}   \int_{\Omega}  \mathcal{F} f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta} ,
\end{equation}
where $\Omega$ is the support of $\mathcal{F}f^N$. Obviously, the integral in (\ref{estimator: f}) is well defined since $\Omega={\rm supp}(\mathcal{F}f^N) \subset \{\bfsym {\zeta}: \|\bfsym {\zeta}\|\leq 2^{N+1} \}$.

\begin{remark}
	An immediate implication of the above analysis is that when $h$ is an entire function of exponential type, then
	due to an extension of Paley-Wiener Theorem to $\RR^d$ by E.M. Stein~\cite{stein1957functions}, $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ defined as in (\ref{estimator: general}) is an unbiased estimator of $f=h$ under model (\ref{model}).
\end{remark}

\section{Bound on the Bias}
\label{section:bias}

In this section, we derive an upper bound on the bias of the estimator (\ref{estimator: f}).
We show that the upper bound on the bias term $\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ involves the Besov norm of $f$, the smoothness parameter
$s$, the noise level $\|\bSigma\|_{op}$, and the effective rank $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)$ of $\bSigma$.

\begin{theorem}
	\label{theorem: bias}
	Under model (\ref{model}), assume that given $f\in B^s_{\infty,1}(\RR^d)$ with $s\geq 0$ and the estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ defined as in (\ref{estimator: f}), the following bound on the bias holds:
	\begin{equation}
	\label{bound: bias}
		\big| \EE_{\theta} g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big| \leq C_1 \|f\|_{B^s_{\infty,1}} \big(\|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)\big)^{s/2},
	\end{equation}
	where $C_1$ is some absolute constant.
\end{theorem}

\begin{remark}
	Set the noise level $\|\bSigma\|_{op}=\sigma^{2}$ with some $\sigma>0$ and $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)\leq \sigma^{-2\alpha}$ for some $\alpha \in (0,1)$, then the upper bound in (\ref{bound: bias}) can be written as
	$ \big| \EE_{\theta} g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big| \lesssim \sigma^{(1-\alpha)s}$. It suggests that for such a estimation problem with parameters in a higher dimension (larger $\alpha$), higher order smoothness (larger $s$) can contribute to achieving better bias reduction. Especially, to make the bias be of smaller order than $\|\bSigma\|_{op}^{1/2}$, one needs $s\geq 1/(\alpha-1)$. In view of model (\ref{model: sequence}), such a threshold on smoothness $s$ is necessary
	for one to achieve a $\sqrt{n}$-consistent estimator in order to show asymptotic normality and efficiency.
	\end{remark}

	\begin{remark}
	As we shall see in Section \ref{section: lower}, the term $\sigma^{2s(1-\alpha)}$ also appears in the minimax lower bound for standard Gaussian shift model where $\bSigma=\bI_d$. Namely,
	\begin{equation}
	\inf_{T}\sup_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \gtrsim  \sigma^{2s(1-\alpha)}.
	\end{equation}
	That means the smoothness threshold $s\geq1/(1-\alpha)$ is sharp for standard Gaussian shift model in order to achieve the mean square error rate $\sigma^2$ when $\sigma$ is small. A similar threshold
	on smoothness is established by a recent work~\cite{koltchinskii2018efficient} over a H\"older type function space for standard Gaussian shift model in Banach space.
\end{remark}

\section{Concentration of the Remainder}
\label{section: concentration_remainder}
In this section, we show a concentration inequality to control the remainder after applying the standard delta method to $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$.
We consider the first order Taylor expansion of $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ around $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}$, and get
\begin{equation}
\label{Taylor}
g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) =g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+\bfsym {\xi})= g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})+  \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfsym {\xi}\rangle + S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}),
\end{equation}
where
$$
S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} ;\bfsym {\xi}) := g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})-\langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfsym {\xi}\rangle.
$$
The remainder term $S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi})$ denotes the difference between $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ and its linearization around $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}$.
In Theorem \ref{theorem: SgConcentration} below, we derive a concentration bound on $S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}; \bfsym {\xi})$ around its mean $\EE S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}; \bfsym {\xi})$.
It turns out that in addition to $\|\bSigma\|_{op}$ and $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)$, another quantity plays an important role in the bound. We denote it by
\begin{equation}
\label{definition: hessian}
\big\| \nabla^2 g \big\|_{op} := \sup\limits_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \in \RR^d} \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \langle \nabla^2 g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) \bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}, \bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\rangle,
\end{equation}
which is the operator norm of the Hessian function of $g(\cdot)$. As one shall see, set $\|\bSigma\|_{op} = \sigma^2$ and $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) = \sigma^{-2\alpha}$ when
\begin{equation}
\label{condition: hessian}
	\|\nabla^2 g\|_{op}  = o(\sigma^{\alpha-1}),
\end{equation}
$|S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \mathbb{E}S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi})| = O_p(\|\bSigma\|^{1/2}_{op})$.  Together with bound (\ref{bound: bias}) on the bias, this result makes it possible for us to show the asymptotic normality and efficiency of the estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$. We will have a more detailed discussion on the uniform bound of $\|\nabla^2 g\|_{op}$ in Section \ref{section: Hessian}.

\begin{theorem}
	\label{theorem: SgConcentration}
	Under model (\ref{model}), assume that $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ is defined as in (\ref{estimator: f}).
	Then there exists a numerical constant $C_2$ such that for all $t\geq 1$, with probability at least $1-e^{-t}$
	\begin{equation}
	\label{bound: concentration_remainder}
	\Big|S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \mathbb{E}S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi})\Big| \leq C_2 \big(  (\|\bSigma\|_{op}\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma))^{1/2} \vee \|\bSigma\|^{1/2}_{op} \sqrt{t}\big)  \|\nabla^2 g\|_{op} \|\bSigma\|_{op}^{1/2}\sqrt{t}.
	\end{equation}
\end{theorem}

The following theorem is an immediate consequence of Theorem \ref{theorem: bias} and Theorem \ref{theorem: SgConcentration}.
\begin{theorem}
	\label{theorem: general_upper}
	Under model (\ref{model}), assume that $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ is defined as in (\ref{estimator: f}) given $f\in B^s_{\infty,1}(\RR^d)$ with $s>1$.
	Then there exists a numerical constant $C_3$ such that for all $t\geq 1$, with probability at least $1-e^{-t}$
	\begin{equation}
	\label{bound: upper_mse}
    \big| g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big| \leq C_3 \Big( \big( (\|\bSigma\|_{op}\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma))^{1/2})  \vee \|\bSigma\|^{1/2}_{op} \sqrt{t}\big)  \|\nabla^2 g\|_{op} \|\bSigma\|_{op}^{1/2}\sqrt{t} \vee \|f \|_{B^s_{\infty,1}}\big(\|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)\big)^{s/2} \Big).
	\end{equation}
	Especially, if $ \|\nabla^2 g\|_{op} =\|f\|_{B^s_{\infty,1}}= O(1)$, then with some numerical constant $C_4$
	\begin{equation}
	\label{bound: upper}
		 \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} \big(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \big)^2 \leq C_4 \Big( \|\bSigma\|_{op} \vee  \big(\|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)\big)^{s} \Big).
	\end{equation}
\end{theorem}

\begin{remark}
	The result in Theorem \ref{theorem: general_upper} indicates that when $ \|\nabla^2 g\|_{op} $ and $\|f\|_{B^s_{\infty,1}}$ are properly controlled,
	\begin{equation*}
		\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} \big(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \big)^2 \lesssim (\sigma^2 \vee \sigma^{2(1-\alpha)s}).
	\end{equation*}
	In section \ref{section: Hessian}, we show that for all the cases when non-trivial bias reduction is needed, namely, $\alpha \in (1/2,1)$, $\|\nabla^2 g\|_{op} = O(1)$ indeed holds.
	In section \ref{section: lower}, we show that the bound (\ref{bound: upper}) is indeed minimax optimal under standard Gaussian shift model where $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) = d = \sigma^{-2\alpha}$.
\end{remark}

\section{Uniform Upper Bounds on $\|\nabla ^2 g\|_{op}$}
\label{section: Hessian}
From last section, we learned that the quantity $\|\nabla^2 g\|_{op}$ plays a vital role in controlling the remainder.
Recall that from the definition of our estimator in (\ref{estimator: f}), the Hessian function is a matrix valued function
\begin{equation}
\label{Hessian}
\nabla^2 g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) = -   \frac{1}{(\sqrt{2\pi})^{d}} \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \bfsym {\zeta} \otimes \bfsym {\zeta} d\bfsym {\zeta}.
\end{equation}
where $\Omega \subset \{\bfsym {\zeta}: \|\bfsym {\zeta}\| \leq 2^{N+1} \}$ is the support of $\mathcal{F}f^N$.
By the definition of $\|\nabla^2 g\|_{op}$, we have
\begin{align*}
\|\nabla^2 g\|_{op} & := \sup\limits_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \in \Omega } \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \frac{1}{(\sqrt{2\pi})^{d}}  \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big| .
\end{align*}
Clearly, the quantity depends on the shape of $\Omega$ which can vary for different $f$ despite the fact that $\Omega$ is bounded.

In Theorem \ref{theorem: hessian}, we derive the uniform upper bounds on $\|\nabla^2 g\|_{op}$
regardless of the shape of $\Omega$.
Set $\|\bSigma\|_{op} = \sigma^2$, $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) = \sigma^{-2\alpha}$, and $d=\sigma^{-2\beta}$ with $0<\alpha\leq \beta <1$, we show that in the moderately high dimensional regime $\alpha \in (1/2,1)$ where
non-trivial bias reduction is needed, $\|\nabla^2 g\|_{op} = O(\sigma^{\epsilon d})$ for some constant $\epsilon>0$ when $\sigma$ is small. This decay rate is more than enough to serve our purpose as indicated in (\ref{condition: hessian}). Another interesting finding is that
when $\alpha \in (0,1/2)$, one needs either $\alpha+\beta>1$ or $s\geq (3d+1)/2$ to achieve similar decay rate on $\|\nabla^2 g\|_{op}$. Note that $s\geq (3d+1)/2$ is a much stronger threshold than $s\geq 1/(1-\alpha)$ on the smoothness as we discussed previously. Currently, we don't know whether this phenomenon is essential or just because of technical reasons. However, when $\alpha\in (0,1/2)$, it is not a worrisome regime since the plug-in estimator $f(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ typically gives the correct rate on MSE and serves as an efficient estimator.

\begin{theorem}
	\label{theorem: hessian}
	For any given $f\in B^s_{\infty,1}(\RR^d)$ with some $s > 0$, and $\|\nabla^2 g\|_{op}$ defined as in (\ref{definition: hessian}) by taking
	\begin{equation*}
	N = \lceil(\log_2 1/\|\bSigma\|_{op} -\log_2 \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) - 2)/2 \rceil.
	\end{equation*}
	Set
	$\|\bSigma\|_{op} = \sigma^2$, $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)=\sigma^{-2\alpha}$, and $d = \sigma^{-2\beta}$ with $0<\alpha\leq \beta <1$.
	If $\alpha + \beta > 1$, then for some numerical constant $\epsilon >0$ and for all $s>0$
	\begin{equation}
	\label{threshold: 1}
	\|\nabla^2 g\|_{op} =O(  \sigma^{\epsilon d}),~as~\sigma\rightarrow 0.
	\end{equation}
	If $\alpha + \beta \leq 1$, then for some numerical constants $\epsilon' >0$ and for all $s \geq (3d+1)/2$
	\begin{equation}
	\|\nabla^2 g\|_{op} =O(  \sigma^{\epsilon' d}), ~as~\sigma \rightarrow 0.
	\end{equation}
\end{theorem}

\begin{remark}
	Note that when $\alpha \in (1/2, 1)$, then $\alpha + \beta \geq 2\alpha > 1$. Under such a situation, as we have shown in Theorem \ref{theorem: general_upper}:
	\begin{equation}
	\sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \leq C_4 \big( \sigma^2 \vee \sigma^{2s(1-\alpha)} \big)\wedge 1.
	\end{equation}
	Especially, when $s\geq1/(1-\alpha)>2$,
	\begin{equation}
		\sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \leq C_5 \sigma^2 \wedge 1.
	\end{equation}
\end{remark}
One should notice that in the above arguments, we did some simplifications by assuming that $\sigma<1$. In general, one can modify the estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ by setting it to be $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})= 0$ when $\sigma>1$ and $\|f\|_{B^s_{\infty,1}}\leq 1$.

\section{Minimax Lower Bounds}
\label{section: lower}

In this section, we show two minimax lower bounds under standard Gaussian shift model where $\bSigma = \sigma^2\bI_d$.
Under this situation, $\|\bSigma\|_{op} = \sigma^2$ and $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)={\rm rank}(\bSigma) = d$.
A recent result in~\cite{koltchinskii2018efficient} attained a similar type of minimax lower bounds for a special H\"older type function class denoted by $\mathcal{C}^s$, where
$s$ characterizes the smoothness condition of the function class. We restate their result as follows.

\begin{theorem}
	\label{bound: lower_koltchinskii}
	[Theorem 2.2 in~\cite{koltchinskii2018efficient}] \
	Let $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\sim {\cal  N}} \def\cN{{\cal  N}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\sigma^2\bI_d)$ for some $0<\sigma<1$ and $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in \RR^d$. Then for some numerical constant $c_0$
	\begin{equation}
	\inf_T\sup_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1}\sup_{\|f\|_{{\cal  C}} \def\cC{{\cal  C}^s}\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \gtrsim  \Big(\sigma^2 \bigvee \big(\frac{\sigma^2d}{\log d}\Big)^s \Big) \bigwedge 1.
	\end{equation}
\end{theorem}

In Theorem \ref{theorem: minimax_lower_2} below, we show a new minimax lower bound which improves the above result by removing the logarithmic factor. The new lower bound
bridges the gap between the upper bound and minimax lower bound caused by this logarithmic factor. The proof of Theorem \ref{theorem: minimax_lower_2} is based on some new technique and a quite different approach from the previous methods introduced by~\cite{nemirovskii1991necessary,nemirovski2000topics}. We think that the new method is more general and can be adopted in various occasions.
\begin{theorem}
	\label{theorem: minimax_lower_2}
	Assume that $f \in B_{\infty,1}^s(\RR^d) $ with $s>1$, and $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \sim \mathcal{N}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}; \bSigma)$ with $\bSigma=\sigma^2 \bI_d$ for some $0<\sigma<1$.
	Then with some small enough constant $c_1$, the following lower bound holds
	\begin{equation}
	\label{bound: lower_2}
	\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \geq c_1
	\big(\sigma^2d )^s \wedge 1 \big) .
	\end{equation}
\end{theorem}

Now we switch to prove the other part of the minimax lower bound. We introduce a new approach through an application of the well known Assouad's Lemma (\cite{Tsybakov:2008:INE:1522486} Lemma 2.12).

\begin{theorem}
	\label{theorem: minimax_lower_1}
	Suppose that the conditions of Theorem \ref{theorem: minimax_lower_2} hold. Then for some small enough numerical constant $c'_1>0$
	\begin{equation}
	\label{bound: lower_1}
	\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \geq c'_1 ( \sigma^2 \wedge 1).
	\end{equation}
\end{theorem}

\begin{remark}
	Combining the bounds in (\ref{bound: lower_1}) and (\ref{bound: lower_2}), we get
	\begin{equation}
		\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2
		\gtrsim \big( \sigma^2 \vee (\sigma^2d)^s \big) \wedge 1,
	\end{equation}
	which matches the upper bound we get in (\ref{bound: upper}).
	It indicates that when $\sigma$ is small, say $\sigma<1$, $\sigma^2 \vee (\sigma^2d)^s$ is the minimax optimal rate for standard Gaussian shift model. And so is $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ for any $f \in B_{\infty,1}^s(\RR^d)$ with $\|f\|_{B^s_{\infty,1}}\leq 1$ when $\alpha \in (1/2,1)$.
\end{remark}

\section{Normal Approximation and Asymptotic Efficiency}
\label{section: normal}

In this section, we study the asymptotic normality of the estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ and prove a normal approximation bound. Let
\begin{equation}
	\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}):= \langle \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) , \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \rangle .
\end{equation}
According to the elementary embedding theorems (see~\cite{Triebelfunction} sec. 2.5.7), $B^s_{\infty, 1}(\RR^d)$ with $s>1$ is continuously embedded in $C^1(\RR^d)$. Thus, for any $f\in B^s_{\infty, 1}(\RR^d)$ with $s>1$, we have
\begin{equation}
	\| \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \| \leq \sum_{j=1}^d \Big\| \frac{\partial f}{\partial x_j} \Big\|_{\infty}  =  \| f\|_{C^1} \leq C^*  \| f\|_{B^s_{\infty, 1}}
\end{equation}
for some constant $C^*>0$. Therefore, we have
\begin{equation}
\label{bound: std_v}
	\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}):=\sqrt{\langle \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) , \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \rangle} \leq \|\bSigma \|^{1/2}_{op} 	\| \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \| \leq C^*\|\bSigma \|^{1/2}_{op}  \| f\|_{B^s_{\infty, 1}}.
\end{equation}
In the following, we denote by
\begin{equation}
\label{formula: K}
K(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}):=  \frac{\|\bSigma\|^{1/2}_{op} \|f\|_{B^s_{\infty, 1}}}{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}.
\end{equation}
Apparently, $K(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ is bounded away from $0$. Further, we make the following assumptions.

\begin{assumption}
	\label{assumption: K}
	Assume that there exists some constant $\tau>0$ such that $K(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \leq \tau$.
\end{assumption}

\begin{assumption}
	\label{assumption: decay}
	Given $f \in  B_{\infty,1}^s(\RR^d)$ and the decomposition $f = f^N+ \widetilde{f}^N$, assume that
	\begin{equation}
	 R_N(f,\sigma)  := \big\| \|\nabla \widetilde{f}^N \| \big\|_{\infty}  = o(N^{-1/2}),~{\rm as}~N\rightarrow \infty.
	\end{equation}
\end{assumption}

\begin{remark}
	Under Assumption \ref{assumption: K}, one should notice that $\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \gtrsim \|\bSigma\|^{1/2}_{op}$. Together with (\ref{bound: std_v}), it means that the standard deviation $\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ is comparable to the noise level $\|\bSigma\|_{op}^{1/2}$. Assumption \ref{assumption: decay} is on the decay rate of the first order derivative of the remainder.
	Consider $N$ defined as in (\ref{N}), we have $N \asymp O(\log \sigma ^{-1})$ by taking $\|\bSigma\|_{op} = \sigma^2$. Especially, $N \rightarrow \infty$ as $\sigma \rightarrow 0$.
\end{remark}

In the following theorem, we show that when assumption 1 and 2 hold, $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ is close normal in distribution.

\begin{theorem}
	\label{theorem: normal}
	Suppose that Assumption 1 holds. Then for any $f\in B_{\infty,1}^s(\RR^d)$ with $s>1$, the following normal approximation bound holds:
	\begin{equation}
	\label{bound: normal_apprx}
	\begin{aligned}
		&\sup\limits_{x\in \RR} \Big| \PP_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} \Big\{\frac{g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} \leq x \Big\} - \PP\{Z\leq x \}\Big| \leq  \\
		& C^*_1 \Big(\frac{(\|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)) ^{s/2}}{\|\bSigma\|^{1/2}_{op}} \bigvee \|\bSigma\|^{1/2}_{op}\log (\|\bSigma\|^{-1}_{op})
		\bigvee (\|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma))^{1/2} \|\nabla^2 g\|_{op}\bigvee R_N(f;\sigma) ) \sqrt{\log (\|\bSigma\|^{-1}_{op})} \Big).
		\end{aligned}
	\end{equation}
	where $Z$ is a standard normal random variable and $C^*_1$ is some constant. Moreover, with some constant $C^*_2$
	\begin{equation}
	\label{bound: efficiency}
	\begin{aligned}
		&\frac{ \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}^{1/2} (g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2}{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} \leq  \\
		& 1 + C^*_2\Big(\frac{(\|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)) ^{s/2}}{\|\bSigma\|^{1/2}_{op}} \bigvee \|\bSigma\|^{1/2}_{op}\log (\|\bSigma\|^{-1}_{op})
		\bigvee ( (\|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma))^{1/2}\|\nabla^2 g\|_{op}\vee R_N(f;\sigma)) \sqrt{\log (\|\bSigma\|^{-1}_{op})} \Big).
	\end{aligned}
	\end{equation}
\end{theorem}

\begin{remark}
	Set $\|\bSigma\|_{op} = \sigma^2$ and $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) = \sigma^{-2\alpha}$. When $s\geq 1/(1-\alpha)$, condition (\ref{condition: hessian}) and Assumption \ref{assumption: decay} hold, then (\ref{bound: normal_apprx}) indicates that $(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))/\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ weakly converges to the standard normal random variable $\mathcal{N}(0,1)$ as $\sigma \rightarrow 0$. Meanwhile,
	(\ref{bound: efficiency}) indicates that under the same condition $\frac{ \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}^{1/2} (g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2}{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} $ is close to $1$ uniformly in a parameter set where $K(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ is upper bounded by a constant.
\end{remark}

In the following theorem, we prove a lower bound which together with (\ref{bound: efficiency}) implies the asymptotic efficiency of the estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$.
\begin{theorem}
	\label{theorem: efficiency}
	Under model (\ref{model}), suppose that $f\in B^s_{\infty,1}(\RR^d)$ with some $s\in (1,2]$. Then there exists a constant $D>0$ such that for all $c>0$ satisfying
	$c\|\bSigma\|_{op}^{1/2} \leq 1$, the following bound holds
	\begin{equation}
	\label{bound: lecam_lower}
	\inf_T \sup\limits_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma)} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2}{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} \geq 1 - D K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) \Big(  c^{s-1} \|\bSigma\|_{op}^{(s-1)/2} +  \frac{1}{c^2} \Big)
	\end{equation}
	where $U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma):= \{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}: \|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} -\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0\|\leq c\|\bSigma\|_{op}^{1/2} \}$.
\end{theorem}

\begin{remark}
	The bound in (\ref{bound: lecam_lower}) shows that when the noise level $\|\bSigma\|_{op}$ is small and the quantity $K(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)$ is upper bounded by a constant, the following asymptotic minimax
	lower bound holds locally in a neighbourhood of $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0$ of the size comparable with the noise level:
	\begin{equation}
	\lim\limits_{c\rightarrow \infty} \liminf_{\|\bSigma\|^{1/2}_{op} \rightarrow 0} \inf_T \sup_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}-\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0\|\leq c\|\bSigma\|_{op}}  \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2}{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} \geq 1 .
	\end{equation}
	Given Theorem \ref{theorem: normal}, it shows the asymptotic efficiency of $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ in the spirit of H\'{a}jek and Le Cam of the estimator $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ and the optimality of the variance $\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ of normal approximation.
\end{remark}

\section{Estimation with Unknown Covariance Matrix}
\label{section: adaptive}

In this section, we discuss modifications of estimator (\ref{estimator: f}) when the covariance matrix $\bSigma$ of $\bfsym {\xi}$ is unknown. As we can see, there are two variables need to be decided without knowing $\bSigma$:
one is the true covariance matrix $\bSigma$ to be plugged into (\ref{estimator: f}) and the other is $N$ as in (\ref{N}) which determines the size of the truncation region in the frequency domain. According to the definition of
$\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma):= {\rm tr}(\bSigma)/\|\bSigma\|_{op}$ and $N$, it is sufficient to estimate $\sqrt{{\rm tr}(\bSigma)}$ in order to get a good estimate of $N$. Clearly, both can be achieved with a fairly good estimator of $\bSigma$ itself.
In the following, we provide a data driven method to estimate $\bSigma$ under model (\ref{model: sequence}), where multiple noisy observations are available.

Recall that $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_j = \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+ \bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}_j$, $j=1,...,n$ and $\bfm z}   \def\bZ{\bfm Z}  \def\ZZ{\mathbb{Z}_j\sim {\cal  N}} \def\cN{{\cal  N}(\mathbf{0},\bSigma_0)$. Here $\bSigma = n^{-1}\bSigma_{0}$ and ${\rm tr}(\bSigma) = n^{-1}{\rm tr}(\bSigma_0)$. It is sufficient to estimate $\bSigma_0$.
We consider
\begin{equation}
	\bfsym \beta_j = \sqrt{\frac{j-1}{j}}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_j - \bar{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}}_{j-1}),~\bar{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}}_{j-1} = \frac{1}{j-1} \sum_{i=1}^{j-1} \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}_i,~j=2,...,n.
\end{equation}
 In this case, it is easy to check that $\widetilde{\bfsym \beta}_{j} = \bfsym \beta_{j+1}$, $j=1,...,n-1$ are i.i.d. copies of a centered Gaussian random vector $\bfsym \beta\sim {\cal  N}} \def\cN{{\cal  N}(\mathbf{0},\bSigma_0)$. We denote by $\hat{\bSigma}_0:=(n-1)^{-1}\sum_{j=1}^{n-1}\widetilde{\bfsym \beta}_j\widetilde{\bfsym \beta}_j^T$ the sample
 covariance matrix of $\bfsym \beta$, and we use $\hat{\bSigma} = n^{-1}\hat{\bSigma}_0$ as an estimator of $\bSigma$ and $\hat{N}:=1/2* \log(n/{\rm tr}(\hat{\bSigma}_0))-1$ as an estimator of $N$. We denote by $\hat{\Omega} :={\rm supp}(\mathcal{F}f^{\hat{N}}) \subset \{\bfsym {\zeta}: \|\bfsym {\zeta}\|\leq 2^{\hat{N}+1} \}$, then we define
 \begin{equation}
 \label{estimator: adaptive}
 	\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}):=   \frac{1}{(2\pi)^{d/2}}   \int_{\hat{\Omega}}  \mathcal{F} f(\bfsym {\zeta})e^{\langle \hat{\bSigma} \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta} .
 \end{equation}
 In the following theorem, we show that $\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ is very close to $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ with high probability in the region $\alpha\in (1/2,1)$.
\begin{theorem}
\label{theorem: adaptive}
	Under model (\ref{model: sequence}), let $\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ and $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ be defined as in (\ref{estimator: adaptive}) and (\ref{estimator: f}) respectively. Suppose that
	$\|\bSigma_0\|_{op}=O(1)$ and $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0)=n^{\alpha}$ with $\alpha \in (1/2,1)$. Then for any $f\in B_{\infty,1}^s(\RR^d)$ with $\big\| f \big\|_{B_{\infty,1}^s}\leq 1$ and for some constant $\widetilde{C}$, with probability at least $1-e^{-n^{\alpha}}$
	\begin{equation}
	\big| \hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})\big| \leq \widetilde{C} n^{-1/2}.
	\end{equation}
\end{theorem}

\begin{remark}
Theorem \ref{theorem: adaptive} shows that in the regime where bias correction is needed, the estimator (\ref{estimator: adaptive}) is close to the estimator (\ref{estimator: f}) with high probability such that it can achieve similar performance. Indeed, our simulation results in Section \ref{experiment: adaptive} show that both estimators achieve better performance than the plug-in estimator, especially
on bias correction.

\end{remark}

\section{Numerical Simulation}
\label{section: simulation}

In this section, we conduct the simulation study to test the performance of our estimator under standard Gaussian shift model where $\bfsym {\xi} \sim \mathcal{N}(\mathbf{0}, \bI_d)$.
We denote the estimator defined in (\ref{estimator: f}) by TF-Estimator, and the estimator defined in (\ref{estimator: adaptive}) by adaptive-Estimator.
We test our estimators on the following type of multivariate functions:
$f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}):=\beta*\prod_{j=1}^d h(\theta_j) $, where the normalizing factor $\beta$ is used to make $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ be a constant for different values of $d$.

We choose $h$ with two different smoothness properties and compare the bias, variance, and MSE of TF-estimator, adaptive estimator with the plug-in estimator when
$\alpha$ ranges from $0.4$ to $0.85$ by an increase of $0.05$ each time.
The unknown parameters $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in \RR^d$ are randomly generated that yield a uniform distribution over $[0.4, 0.6]^d$ for different dimension parameter $d$.
We set $\sigma^2 = 10^{-4}$ defined in model (\ref{model}), or equivalently, $n=10000$ defined as in model (\ref{model: sequence}).

We use the MATLAB built-in function $\mathbf{fft}()$ and $\mathbf{ifft}()$ to compute the Fourier Transformation and the Inverse Fourier Transformation appeared in the analysis. When we implement TF-Estimator,
the truncation in the frequency domain was done uniformly for each coordinate for simplicity. Thus, the support of $\mathcal{F}f^N$ after truncation is contained in a hyper-cube instead of a d-ball. Note that the built-in
function $\mathbf{fft}()$ and $\mathbf{ifft}()$ are implementations of discrete Fourier transform (DFT). Those discrepancies between implementations and our theoretical results make the cutoff range drifted a little bit from our suggestion in (\ref{N}). The cutoff range for each coordinate we use is $[64, 100]$. We observed that typically larger $\alpha$ and higher dimension $d$ needs smaller cutoff to achieve better performance, which is consistent with our prediction.

\subsection{Bias reduction}

\begin{figure}[!htb]
	\centering
	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{adp_bias_s2}
		\caption{Bias Comparison for $h(x) = (2x)^{2.75}$}
		\label{fig: bias-s2}
	\end{subfigure}
	~

	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{adp_bias_s3}
		\caption{Bias Comparison for $h(x) = (2x)^{3.75}$}
		\label{fig: bias-s3}
	\end{subfigure}
	\caption{Bias Comparison}
\end{figure}

We choose two different base functions $h$ to test the performance. One is $h_1(x) = (2x)^{2.75}$ with $x\in[0,1]$ and the other is $h_2(x) = (2x)^{3.75}$ with $x\in[0,1]$. The scalar factor is used to avoid overflow of the function values when the dimension $d$ is large. Especially, the underlying function values for both cases are normalized to a constant for this case in order to force the function magnitude to be bounded.
One should notice that $h_1(x) = (2x)^{2.75}$ belongs to the H\"{o}lder class with smoothness at most $s=2.75$ while $h_2(x) = (2x)^{3.75}$ belongs to the one with $s=3.75$.
In other words, $h_2$ has a higher smoothness condition than $h_1$.
The data for bias comparison for both cases are listed in Table \ref{tb:adp_s2_bias} and Table \ref{tb:adp_s3_bias} respectively in the appendix, and they are plotted in Fig. \ref{fig: bias-s2} and Fig. \ref{fig: bias-s3}.
The metric we use is $|\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) -f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})|$, where $\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ is simulated by averaging the outcome of 20000 independent trials.

As we can see, for both cases, the bias reduction phenomena are very obvious. The dash lines which plot $(d/n)^{2.75/2}$ and $(d/n)^{3.75/2}$ are supposed to be of the same order as the upper bounds on the bias of our estimators as proved in Theorem \ref{theorem: bias}. The simulation results align with the bounds quite well. Sometimes, the actual bias can pass the line, we think these discrepancies may be due to the constant factors appeared in the bounds and the implementation issue we mentioned above.

\subsection{Threshold on smoothness}
Another phenomenon we are interested in is the threshold on smoothness. The magnitude of $f$ are intentionally adjusted for both cases such that the bias of the plug-in estimator will exceed $\sigma$ or the dash line $n^{-1/2}$ around $\alpha =0.5$. When we continue to increase $\alpha$ beyond $0.5$, the bias of TF-Estimators and adaptive estimators still stays below the dash line $n^{-1/2}$ for sometime while the bias of the plug-in estimators exceeds way above this level. However, the bias of both adaptive estimators start to pass the line as $\alpha$ passes $0.65$ for the case $h(x) = (2x)^{2.75}$ and between $0.70$ and $0.75$ for the case $h(x) = (2x)^{3.75}$. Our theory on the sharp threshold on smoothness comes from the growing bias when $\alpha$ is increasing. It suggests that the bias are expected to be greater than $\sigma$ when $\alpha > 1-1/s$. For both cases, the suggested passing point should be around $\alpha = 0.64$ for the case $h(x) = (2x)^{2.75}$ and the point should be around $\alpha = 0.73$ for the case $h(x) = (2x)^{3.75}$.

\subsection{MSE comparison and minimax lower bound}

\begin{figure}[!htb]
	\centering
	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{adp_var_s2.eps}
		\caption{Variance Comparison for $h(x) = (2x)^{2.75}$}
		\label{fig: var-s2}
	\end{subfigure}
	~

	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{adp_var_s3.eps}
		\caption{Variance Comparison for $h(x)=(2x)^{3.75}$}
		\label{fig: var-s3}
	\end{subfigure}
	\caption{Variance Comparison}
\end{figure}

\begin{figure}[!htb]
	\centering
	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{adp_mse_s2.eps}
		\caption{MSE Comparison for $h(x) = (2x)^{2.75}$}
		\label{fig: mse-s2}
	\end{subfigure}
	~

	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{adp_mse_s3.eps}
		\caption{MSE Comparison for $h(x)=(2x)^{3.75}$}
		\label{fig: mse-s3}
	\end{subfigure}
	\caption{MSE Comparison}
\end{figure}

We compare the variance and MSE for both cases in this section.
The variance data are listed in Table \ref{tb:adp_s2_var} and Table \ref{tb:adp_s3_var} in appendix which are plotted in Fig. \ref{fig: var-s2} and Fig. \ref{fig: var-s3}. As we can see, the variance are almost the same for TF-Estimator and adaptive estimator when $\alpha \leq 0.65$. The corresponding
smoothness threshold to $\alpha = 0.65$ is around $1/(1-\alpha) = 2.86$ which are close to the smoothness condition for both cases. Once $\alpha \geq 0.75$
which requires smoothness $s = 1/(1-\alpha) = 4$ that is higher than both cases, we can see a clear discrepancy between these two estimators. We can also observe that both estimators achieve variance reduction compared with Plug-in estimator when $\alpha$ exceeds $0.5$.
Given that TF-Estimator and adaptive estimator achieve better bias reduction, these show their superiority over Plug-in estimators.

The metric for MSE we use is $\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) -f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2$ which is simulated by averaging the square error of 20000 independent trials.
The MSE data are listed in Table \ref{tb:adp_s2_mse} and Table \ref{tb:adp_s3_mse} in appendix and are plotted in Fig. \ref{fig: mse-s2} and Fig. \ref{fig: mse-s3}.
As we can see, the improvements on reduction of MSE becomes more obvious as the dimension grow larger for both cases. We also plotted $\sigma^2 = n^{-1}$ and $(\sigma^2d)^s = (d/n)^s$ as dash lines, which are supposed to be of the same order as the components of the minimax lower bound on MSE as shown in (\ref{bound: lower_2}) and (\ref{bound: lower_1}). Ideally, the MSE curves should stay above
both lines. In Fig. \ref{fig: mse-s2} and Fig. \ref{fig: mse-s3}, we can see that both MSE curves' trend align well with the bound. Meanwhile, we can see that when $\alpha$ exceeds $0.5$, the reduction in MSE becomes more obvious for both cases. Especially, the reduction with $h_2$ with more smoothness is more obvious than with $h_1$.

\subsection{Adaptive Estimation}
\label{experiment: adaptive}

\begin{figure}[!htb]
	\centering
	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{mean_diff.eps}
		\caption{Mean of $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$}
		\label{fig: mean_diff}
	\end{subfigure}
	~

	\begin{subfigure}[b]{0.48\textwidth}
		\includegraphics[width=\textwidth]{var_diff.eps}
		\caption{Variance of $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$}
		\label{fig: var_diff}
	\end{subfigure}
	\caption{Difference between $g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ and $\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$}
\end{figure}

We have already shown in the previous sections that the adaptive estimator $\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ in (\ref{estimator: adaptive}) behaves similarly as
$g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ in (\ref{estimator: f}). In this section, we plot $\EE\big(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})\big)$ and $\Var\big( g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})\big)$ in Fig. \ref{fig: mean_diff} and Fig. \ref{fig: var_diff} which are simulated by 20000 independent trials. As we can see, for both cases, when $\alpha \leq 0.70$,
$\EE (g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}))\leq n^{-1/2}$ and $\Var(g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})-\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})) \leq n^{-1}$ which are what we expected. However, when $\alpha$ is approaching to $1$, the difference becomes quite big. The discrepancy between theory and experiments is due to the actually choice of $N$ for implementation is drifted from the theoretical ones because of the implementation issue we mentioned at the very beginning of this section.

\section{Conclusion}

In this article, we studied the estimation of $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ for an unknown parameter $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in \RR^d$ and a given $f$ under Gaussian shift model when the complexity of the parameter space is growing with the sample size.
We proposed a new estimator which can be shown both analytically and experimentally to achieve much better bias reduction than the traditional plug-in estimator when the intrinsic dimension of the problem is high.
By introducing an innovative approach to prove the minimax lower bounds under standard Gaussian shift model, we show that our estimator is actually minimax optimal in the regime where nontrivial bias correction is needed. This justifies the minimax rates for the current problem under standard Gaussian shift model and bridged a gap between the upper and lower bounds by removing a logarithmic factor in the previous work.
The minimax rate implies a sharp threshold on the smoothness $s$ such that for all $s$ above the threshold, $f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ can be estimated efficiently with a parametric rate.
Under mild conditions, we prove the normal approximation result of our estimator and establish its asymptotic efficiency.
Furthermore, we propose a data driven procedure to address the adaptive estimation issue when the covariance matrix of the noise is unknown, and show that
it achieves similar performance with the case when the covariance matrix is given.
Numerical simulations are presented to validate our analysis and show the new estimator's superiority over its plug-in counterpart. The simplicity of implementation and direct interaction with Fourier transform data indicate huge potential of the new estimator in real world applications.

\section*{Acknowledgement}

We sincerely thank the insightful discussion on Theorem 7.2 with Professor Cun-Hui Zhang from Rutgers University during his visit at Baidu Research and thank Professor Vladimir Koltchinskii for several insightful comments on this work.

\vfill\eject

\section{Proofs}

\subsection{Proof of Theorem \ref{theorem: bias}}
\begin{proof}
	\label{proof: theorem_bias}
	Recall that from (\ref{conv2}), we have
	\begin{equation}
	\begin{aligned}
	\EE_{\theta} g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) = g*p^o(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) &=  \frac{1}{(2\pi)^{d/2}}  \int_{\mathbb{R}^d} \Big(\int_{\mathbb{R}^d}  \mathcal{F} f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot (\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}-\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})} d\bfsym {\zeta} \Big) p^o(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \\
	& = \int_{\mathbb{R}^d}  \mathcal{F} f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} \mathcal{F} p^o(\bfsym {\zeta}) d\bfsym {\zeta} \\
	& = \frac{1}{(2\pi)^{d/2}} \int_{\mathbb{R}^d}  \mathcal{F} f^N(\bfsym {\zeta}) e^{i\bfsym {\zeta} \cdot \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}  d\bfsym {\zeta} \\
	& =  \mathcal{F}^{-1} \mathcal{F} f^N = f^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}).
	\end{aligned}
	\end{equation}
	where for the third line, we used the fact that $\mathcal{F} p^o(\bfsym {\zeta}) = (2\pi)^{-d/2} e^{-\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}.$
	Therefore, $\big| \EE_{\theta} g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big| = |f^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})| = |\tilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})| $. Due to the fact that $\tilde{f}^N \in B^s_{\infty,1}(\RR^d) \subset C_u(\RR^d)$,
	\begin{equation}
	\label{norm: remainder}
	|\tilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})| \leq  \|\tilde{f}^N\|_{L^{\infty}} \leq \sum\limits_{j=N+1}^\infty \|f_j\|_{L^{\infty}}
	\leq  2^{-(N+1)s}\sum\limits_{j=N+1}^\infty 2^{js}\|f_j\|_{L^{\infty}} \leq 2^{-(N+1)s} \|f\|_{B^s_{\infty,1}} <\infty.
	\end{equation}
	As a result, we have
	\begin{equation}
	|\tilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})|  \lesssim \|f\|_{B^s_{\infty,1}} \cdot 2^{-(N+1)s}.
	\end{equation}
	Plug in $N = \lceil (\log_2 1/\|\bSigma\|_{op} -\log_2 \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) - 2)/2 \rceil$, we immediately get
	\begin{equation}
	\big| \EE_{\theta} g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big| \leq C_1 \|f\|_{B^s_{\infty,1}} \cdot \big( \|\bSigma\|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) \big) ^{s/2}
	\end{equation}
	where $C_1$ is some absolute constant.
\end{proof}

\subsection{Proof of Theorem \ref{theorem: SgConcentration}}
\begin{proof}
	\label{proof: theorem_SgConcentration}
	For the convenience of presentation, we denote
	$$
	\tilde{g}(\bfsym {\xi}) := S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) = g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+\bfsym {\xi}) -g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})-  \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfsym {\xi}\rangle.
	$$
	Clearly, the remainder $\tilde{g}$ is a function of a zero mean normal random vector $\bfsym {\xi}$ in $\mathbb{R}^d$. The main tool
	we use is the following Gaussian concentration inequality (in a little bit non-standard fashion, see~\cite{koltchinskii2017}, sec. 3 for a similar argument) as in Lemma \ref{Lemma:isoperimetric}, which is a corollary of the classical Gaussian isoperimetric inequality, see~\cite{gine2016mathematical} chapter 2.

	\begin{lemma}
		\label{Lemma:isoperimetric}
		Let $X_1,...,X_d$ be i.i.d. centered Gaussian random variables in a Hilbert space $\mathbb{H}$ with covariance operator $\Sigma$. Let $f:\mathbb{R}^d \rightarrow \mathbb{R}$ be a function satisfying the following
		Lipschitz condition with Lipschitz constant $L>0$:
		$$
		\Big|f(x_1,...,x_d)-f(x'_1,...,x'_d) \Big| \leq L \Big(\sum\limits_{j=1}^d\|x_j-x'_j\|^2   \Big)^{1/2},~x_1,...,x_d,x'_1,...,x'_d\in \mathbb{H}.
		$$
		Suppose that, for a real number $M$,
		$$
		\mathbb{P}\{f(X_1,...,X_d) \geq M\} \geq 1/4~{\rm and}~\mathbb{P}\{f(X_1,...,X_d) \leq M\} \geq 1/4.
		$$
		Then, there exists a numerical constant $D$ such that for all $t\geq 1$,
		$$
		\mathbb{P}\Big\{ |f(X_1,...,X_d) - M| \geq DL\|\Sigma\|_{op}^{1/2}\sqrt{t} \Big\} \leq e^{-t}.
		$$
	\end{lemma}

	To apply Lemma \ref{Lemma:isoperimetric}, we need a Lipschitz function of $\bfsym {\xi}$. Unfortunately, $\tilde{g}$ may not be such a function. Instead,
	we consider a truncated version of $\tilde{g}$ which is guaranteed to be Lipschitz under mild restrictions. This kind of technique can also be found in Koltchinskii~\cite{koltchinskii2016asymptotics}, which was applied to tackle similar problems on spectral projectors of sample covariance. At first, we define a function $\varphi$:
	$$
	\varphi(s)=
	\begin{cases}
	1&, {\rm if}\ s\leq 1\\
	0&, {\rm if}\ s\geq 2 \\
	2-s&, {\rm if}\ s\in(1,2).
	\end{cases}
	$$
	One can easily check that $\varphi$ is a Lipschitz function with $L=1$. Then, with some $\delta>0$, we consider the "truncated" random variable
	$$
	h(\bfsym {\xi}) := \tilde{g}(\bfsym {\xi})\varphi\Big(\frac{\|\bfsym {\xi}\|}{\delta}\Big).
	$$

	In the following Lemma \ref{Lemma:Lip}, we show that $h$ is Lipschitz with respect to $\bfsym {\xi}$.
	\begin{lemma}
		\label{Lemma:Lip}
		Suppose that
		$g:\Omega\subset \mathbb{R}^d\rightarrow \mathbb{C}$ is twice continuously differentiable. Then there exists a numerical constant $C$ such that
		\begin{equation}
		\Big|h(\bfsym {\xi}) - h(\bfsym {\xi}') \Big| \leq C \delta \|\nabla^2 g\|_{op}  \|\bfsym {\xi}-\bfsym {\xi}'\|, \label{Lipschitz}
		\end{equation}
		where $\|\nabla^2 g\|_{op}:= \sup_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\in \Omega}\sup_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \langle \nabla^2 g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) \bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}, \bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\rangle$.
	\end{lemma}

	\begin{proof}
		\label{proof: lemma_lip}
		Firstly, we consider the case when
		$$
		\|\bfsym {\xi}\| \leq 2\delta,~\|\bfsym {\xi}'\| \leq 2 \delta.
		$$
		Under this situation, we have
		\begin{equation}
		\label{Lemma:iso1}
		\begin{aligned}
		\Big| h(\bfsym {\xi}) - h(\bfsym {\xi}') \Big| & = \Big|  \tilde{g}(\bfsym {\xi})\varphi\Big(\frac{\|\bfsym {\xi}\|}{\delta}\Big) - \tilde{g}(\bfsym {\xi}')\varphi\Big(\frac{\|\bfsym {\xi}'\|}{\delta}\Big)   \Big| \\
		& \leq \Big|  \tilde{g}(\bfsym {\xi}) \Big| \cdot \Big| \varphi\Big(\frac{\|\bfsym {\xi}\|}{\delta}\Big) - \varphi\Big(\frac{\|\bfsym {\xi}'\|}{\delta}\Big) \Big|  + \Big| \tilde{g}(\bfsym {\xi}') - \tilde{g}(\bfsym {\xi})\Big|\\
		& \leq \Big|  \tilde{g}(\bfsym {\xi}) \Big| \cdot \frac{1}{\delta} \cdot \|\bfsym {\xi}-\bfsym {\xi}'\| + \Big| \tilde{g}(\bfsym {\xi}') - \tilde{g}(\bfsym {\xi})\Big|.
		\end{aligned}
		\end{equation}
		The second inequality is due to the fact that $|\varphi |\leq 1$ and $\varphi(\cdot/\delta)$ is a Lipschitz function with Lipschitz constant $L = 1/\delta$.

		The next step is to bound $ \big|  \tilde{g}(\bfsym {\xi}) \big|$ and $\big| \tilde{g}(\bfsym {\xi}') - \tilde{g}(\bfsym {\xi})\big|$ respectively. Recall that
		$$
		\Big| \tilde{g}(\bfsym {\xi})\Big|=  \Big| g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+\bfsym {\xi}) -g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})-  \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfsym {\xi}\rangle  \Big|.
		$$
		Since $g(\cdot)$ is twice continuously differentiable, by applying the Mean Value Theorem, we have for some $c\in[0,1]$
		$$
		g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+\bfsym {\xi}) -g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) =  \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+ c\bfsym {\xi}), \bfsym {\xi} \rangle.
		$$
		Therefore,
		$$
		\Big| \tilde{g}(\bfsym {\xi})\Big|= \Big|  \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+ c\bfsym {\xi}) -\nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfsym {\xi} \rangle \Big|.
		$$
		By Cauchy-Schwarz inequality, we have
		$$
		\big| \tilde{g}(\bfsym {\xi})\big| \leq \|\nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+ c\bfsym {\xi}) -\nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \| \cdot\|\bfsym {\xi}\| \leq c\|\bfsym {\xi}\|^2 \|\nabla^2 g\|_{op},
		$$
		where $\|\nabla^2 g\|_{op}:= \sup_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\in \RR^d}\sup_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \langle \nabla^2 g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) \bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}, \bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\rangle$ and the last inequality is due to the fundamental theorem of calculus (\cite{lang2012real}, Chap. XIII, Theorem 4.2)
		\begin{equation}
		\nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+c\bfsym {\xi}) - \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) = \int_0^1 \nabla^2 g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+ \tau c\bfsym {\xi}) d\tau.
		\end{equation}
		Under the condition $\|\bfsym {\xi}\| \leq 2\delta$, we get
		\begin{equation}
		\label{bound: g_tilde}
		\big|  \tilde{g}(\bfsym {\xi})\big| \leq 4c \delta^2 \|\nabla^2 g\|_{op}.
		\end{equation}

		On the other hand, for $\tilde{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} = \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+\bfsym {\xi}+c(\bfsym {\xi}'-\bfsym {\xi})$ with some $c\in[0,1]$, similarly we have
		\begin{equation}
		\label{Lip_g}
		\begin{aligned}
		\Big| \tilde{g}(\bfsym {\xi}') - \tilde{g}(\bfsym {\xi})\Big| & = \Big| \langle \nabla g(\tilde{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}), \bfsym {\xi}-\bfsym {\xi}'\rangle  - \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfsym {\xi}-\bfsym {\xi}'\rangle\Big| \\
		& \leq (c\|\bfsym {\xi}-\bfsym {\xi}'\|+ \|\bfsym {\xi}\|)\|\nabla^2g\|_{op}\|\bfsym {\xi}-\bfsym {\xi}'\|\\
		& \leq 6c'\delta  \|\nabla^2 g\|_{op} \|\bfsym {\xi}-\bfsym {\xi}'\|,
		\end{aligned}
		\end{equation}
		Plug the results of (\ref{bound: g_tilde}) and (\ref{Lip_g}) to (\ref{Lemma:iso1}), we get
		\begin{equation}
		\big| h(\bfsym {\xi}) - h(\bfsym {\xi}') \big| \leq C \delta \|\nabla^2 g\|_{op} \|\bfsym {\xi}-\bfsym {\xi}'\|
		\end{equation}
		where $C$ is a numerical constant.

		Secondly, we consider the situation when
		$$
		\|\bfsym {\xi}\| \leq 2 \delta,~\|\bfsym {\xi}'\| > 2\delta.
		$$
		Note that the symmetric case is equivalent, thus we omit it here. Under this case, $h(\bfsym {\xi}')$ is simply zero, and one can get the following bound immediately similarly as the previous analysis
		$$
		\begin{aligned}
		\big|h(\bfsym {\xi}) - h(\bfsym {\xi}') \big| &=  \big|   \tilde{g}(\bfsym {\xi})\Big(\varphi\Big(\frac{\|\bfsym {\xi}\|}{\delta}\Big) -\varphi\Big(\frac{\|\bfsym {\xi}'\|}{\delta}\Big)\Big)\big| \leq  \big| \tilde{g}(\bfsym {\xi})\big| \frac{1}{\delta}\|\bfsym {\xi}-\bfsym {\xi}'\| \leq 4c \delta \|\nabla^2 g\|_{op} \|\bfsym {\xi}-\bfsym {\xi}'\|.
		\end{aligned}
		$$

		Finally, for the case when both
		$$
		\|\bfsym {\xi}\| > 2 \delta,~\|\bfsym {\xi}'\| > 2\delta,
		$$
		it is trivial to prove since $h(\bfsym {\xi}) = h(\bfsym {\xi}')=0$.
		Thus we complete the proof of this lemma.
	\end{proof}

	In what follows, we denote $\delta = \delta(t):= \EE \|\bfsym {\xi} \| + C\|\bSigma\|_{op}^{1/2}\sqrt{t}$. By Gaussian concentration inequality (see~\cite{vershynin2018high}, Chapter 6), we have for $t\geq 1$ with some constant
	$C>0$ such that
	\begin{equation}
	\PP\{ \|\bfsym {\xi}\| \geq \delta(t)\} \leq e^{-t},~t\geq 1.
	\end{equation}

	Denote by $Med(\eta)$ the median of a random variable $\eta$, and let $M:=Med(\tilde{g}(\bfsym {\xi}))$. Recall that, on the event $\{\|\bfsym {\xi}\| \leq \delta\}$, $\tilde{g}(\bfsym {\xi}) = h(\bfsym {\xi})$.  Therefore we have
	$$
	\begin{aligned}
	\mathbb{P} \Big\{  h(\bfsym {\xi}) \geq M \Big\} &\geq \mathbb{P} \Big\{  h(\bfsym {\xi}) \geq M,~\|\bfsym {\xi}\| <\delta \Big\} = \mathbb{P} \Big\{  \tilde{g}(\bfsym {\xi}) \geq M,~\|\bfsym {\xi}\| <\delta \Big\} \\
	&\geq  \mathbb{P} \Big\{  \tilde{g}(\bfsym {\xi}) \geq M \Big\} -\mathbb{P} \Big\{ \|\bfsym {\xi}\| \geq \delta \Big\}  \geq  \frac{1}{2}- e^{-t} \geq \frac{1}{4}.
	\end{aligned}
	$$
	Similarly, one can get
	$$
	\mathbb{P} \Big\{  h(\bfsym {\xi}) \leq M \Big\}  \geq \frac{1}{2}- e^{-t} \geq \frac{1}{4}.
	$$
	Now, it follows from Lemma \ref{Lemma:isoperimetric} and Lemma \ref{Lemma:Lip} that with some constant $C$, for all $t\geq 1$, with probability at least $1-e^{-t}$,
	\begin{equation}
	\Big| h(\bfsym {\xi}) - M\Big| \leq C  \delta(t)  \|\nabla^2 g\|_{op} \|\bSigma\|^{1/2}\sqrt{t}.
	\end{equation}
	Since $h(\bfsym {\xi})$ and $\tilde{g}(\bfsym {\xi})$ coincide on the event $\{\|\bfsym {\xi}\| \leq \delta\}$ of probability at least $1-e^{-t}$, we get with probability at least $1-2e^{-t}$
	\begin{equation}
	|\tilde{g}(\bfsym {\xi}) - M| \lesssim \delta(t) \|\nabla^2 g\|_{op} \|\bSigma\|\|_{op}^{1/2} \sqrt{t}.
	\end{equation}
	By adjusting the constant, we can replace $1-2e^{-t}$ with $1-e^{-t}$ for all $t\geq 0$. It remains to integrate out the tails of this exponential bound. We denote $s(t):= C\delta(t) \|\nabla^2 g\|_{op}\|\bSigma\|\|_{op}^{1/2} \sqrt{t}$.
	Obviously, $s(t)$ is strictly increasing with respect to $t$ such that $s(0)=0$ and $s(+\infty) = +\infty$.
	\begin{align*}
	|\EE \tilde{g}(\bfsym {\xi}) -M| &\leq \EE|\tilde{g}(\bfsym {\xi})-M| =  \int^{\infty}_0 \PP\{|\tilde{g}(\bfsym {\xi})-M| \geq s \} ds = \int^{\infty}_0 \PP\{|\tilde{g}(\bfsym {\xi})-M| \geq s(t) \} ds(t) \\
	& \leq \int^{\infty}_0 e^{-t} ds(t)  = \int^{\infty}_0 s(t)e^{-t}dt,
	\end{align*}
	where the last equity is due to $s(t)=o(e^{t})$ as $t\rightarrow \infty$. As a result,
	\begin{align*}
	|\EE \tilde{g}(\bfsym {\xi}) -M| &\lesssim \|\nabla^2 g\|_{op} \Big(\EE \|\bfsym {\xi}\| \|\bSigma\|\|_{op}^{1/2} \int^{\infty}_0 \sqrt{t}e^{-t} dt + \|\bSigma\|_{op} \int^{\infty}_0  te^{-t} dt  \Big ) \\
	& \lesssim (\EE \|\bfsym {\xi}\|  \vee \|\bSigma\|\|_{op}^{1/2} ) \|\nabla^2 g\|_{op} \|\bSigma\|_{op}^{1/2}.
	\end{align*}

	Thus we can replace $M$ by the expectation $\mathbb{E}\tilde{g}(\bfsym {\xi})$ in the concentration bound and get with some constant $C$ and for all $t\geq 1$ with probability at $1-e^{-t}$
	$$
	\Big|\tilde{g}(\bfsym {\xi}) - \mathbb{E}\tilde{g}(\bfsym {\xi}) \Big| \leq C \big( \EE \|\bfsym {\xi}\|  \vee \|\bSigma\|^{1/2}_{op} \sqrt{t}\big)  \|\nabla^2 g\|_{op} \|\bSigma\|^{1/2}\sqrt{t}.
	$$
	This completes the proof of the theorem.
\end{proof}

\subsection{Proof of Theorem \ref{theorem: hessian}}

\begin{proof}
	\label{proof: theorem_hessian}
	Using the definition $f^N := \sum_{j=0}^Nf_j$,
	then we can get
	\begin{align*}
	\|\nabla^2 g\|_{op} & := \sup\limits_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \in \Omega } \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \frac{1}{(\sqrt{2\pi})^{d}}  \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big| \\
	& \leq \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}   \frac{1}{(\sqrt{2\pi})^{d}} \int_{\Omega} \big| \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2 \big| d\bfsym {\zeta}
	\end{align*}
	where $\Omega_j \subset \{ \bfsym {\zeta} :  2^{j-1} \leq \|\bfsym {\zeta}\| \leq 2^{j+1} \}$ is the domain of $\mathcal{F}f_j$. In the following, we bound each term individually. Consider
	\begin{equation}
	\label{inequality: hessian1}
	\begin{aligned}
	&\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \frac{1}{(\sqrt{2\pi})^{d}}  \int_{\Omega_j}\Big| \mathcal{F}f_j(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2 \Big| d\bfsym {\zeta}\\
	& \leq   \frac{1}{(\sqrt{2\pi})^{d}} e^{ \|\bSigma\|_{op}R^2(\Omega_j)/2} \Big(\int_{\Omega_j} |\mathcal{F}f_j(\bfsym {\zeta})|^2d\bfsym {\zeta} \Big) ^{\frac{1}{2}} \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \Big( \int_{\Omega_j}   \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}} \\
	& \leq    \frac{1}{(\sqrt{2\pi})^{d}} e^{ \|\bSigma\|_{op}R^2(\Omega_j)/2}  \|f_j\|_{L^{2}}  \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \Big( \int_{\Omega_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}} \\
	& \leq    \frac{1}{(\sqrt{2\pi})^{d}} e^{ \|\bSigma\|_{op}R^2(\Omega_j)/2}  \|f_j\|_{L^{\infty}} {\rm Vol}(B_j) \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \Big( \int_{\Omega_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}} \\
	& \lesssim  \frac{1}{(\sqrt{2\pi})^{d}} \|f\|_{B^s_{\infty,1}} 2^{-js} {\rm Vol}(B_j) \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \Big( \int_{B_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}}
	\end{aligned}
	\end{equation}
	where $R(\Omega_j):= \sup_{\bfsym {\zeta}\in \Omega_j} \|\bfsym {\zeta}\|$ denotes the circumradius of $\Omega_j$ and ${\rm Vol}(B_j)$ denotes the volume of a d-ball $B_j$ with radius $r_j=2^{j+1}$.
	The second line of the above inequality is due to H\"{o}lder's inequality and the third line is due to Plancherel's formula given $f_j \in L^{\infty}(\Omega) \subset L^{2}(\Omega)$ for each $j$.
	By taking $N =(\log_2 1/\|\bSigma\|_{op} - \log_2 \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)-2)/2 $, we always have $e^{ \|\bSigma\|_{op}R^2(\Omega_j)/2} \leq e$. Meanwhile by definition, we have $\|f_j\|_{L^{\infty}} \leq \|f\|_{B^s_{\infty,1}}/2^{js} < \infty$.

	Next, we are going to bound the following quantity:
	\begin{equation}
	\label{I4}
	\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \Big( \int_{B_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}} .
	\end{equation}
	Clearly, a random vector $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$ in $\mathbb{R}^d$ uniformly distributed on a convex body $\Omega$ with ${\rm Vol}(\Omega)=1$  is a log concave random
	vector with density $\mathbf{1}_{\Omega}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$. Here, $\mathbf{1}_{\Omega}(\cdot)$ is the indicator function.
	There are abundant literatures in convex geometry on the bounds of more general formulas of (\ref{I4}).
	We introduce the following two important concepts: Let $\Omega \subset \RR^d$ be a convex body with ${\rm Vol}(\Omega)=1$. For every $p\geq 1$, the $p$-th moment of the Euclidean norm is defined as
	$$
	I_p(\Omega):=\Big( \int_{\Omega}  \|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\|^p d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \Big) ^{1/p},
	$$
	and for every $p\geq 1$ and $\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\in\mathbb{R}^d$, the weak $p$-th moment is defined as
	$$
	I_p(\Omega;\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}):= \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}\Big( \int_{\Omega} \big| \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big|^p d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \Big) ^{1/p}.
	$$
	As a consequence of Borell's lemma (see~\cite{milman2009asymptotic} Append. III), we have the following Khintchine-type inequalities, i.e.
	for every $p,q\geq 1$,
	$$
	I_{pq}(\Omega;\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}) \leq C_1pI_q(\Omega;\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U});~~I_{pq}(\Omega) \leq C_2pI_q(\Omega)
	$$
	where $C_1$ and $C_2$ are numerical constants. Therefore, with some numerical constant $C_3$ we can get
	\begin{equation}
	\label{formula: I4toI2}
	\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}  \Big( \int_{B_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}} \leq C_3  \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}   \int_{B_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^2d\bfsym {\zeta} .
	\end{equation}

	In general, it is hard to give explicit bounds on such a quantity with a general convex body $\Omega$ since the shape of the convex body may vary. What is more interesting to consider is that when $\Omega$ is in its isotropic position. Thus we will introduce some basic concepts in the literature of convex geometry to help the readers understand our later discussion.
	For every compact convex body, there is a linear isomorphism $\mathcal{T}\in GL(d,\RR)$ such that ${\rm Vol}(\mathcal{T}(\Omega))=1$, and
	\begin{equation}
	\label{hyperplane}
	\int_{\mathcal{T}(\Omega)}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^2d\bfsym {\zeta} = L^2_{\mathcal{T}(\Omega)} = L^2.
	\end{equation}
	with some constant $L_{\mathcal{T}(\Omega)}$ for every $\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\in S^{d-1}$. We call that $\mathcal{T}(\Omega)$ an isotropic position of $\Omega$. For every convex body in $\mathbb{R}^d$, the
	isotropic position is unique up to an orthogonal transformation. If a convex body $K$ is in its isotropic position, we say that $K$ is isotropic.
	The good news for us to consider the isotropic position of a convex body is that
	it is unique and the quantity $\int_{\mathcal{T}(\Omega)}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^2d\bfsym {\zeta}$ is always a constant, and so is
	$\sup_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1}   \int_{\mathcal{T}(\Omega)}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^2d\bfsym {\zeta} $.
	However, whether the constant $L_{\mathcal{T}(\Omega)}$ is bounded by a universal
	constant for all $d\geq 1$ remains an open problem. It is the so called well known Hyperplane Conjecture in convex geometry. We refer to section 5 in~\cite{milman1989isotropic} for several interesting equivalent
	formulations of this conjecture in case the reader is interested.
	The current best estimate of $L$ for general isotropic convex bodies is $L_{\Omega}\leq Cd^{1/4}$ due to Klartag~\cite{klartag2006convex}, which removed the logarithmic factor in the result given by
	Bourgain~\cite{bourgain1991distribution}.

	The convex body we are interested in here is a d-ball in its isotropic position. We denote by $B^d$ as the isotropic d-ball with radius $R_{B^d}$. It is well known that $L_{B^d} \leq C$ for all $d \geq 1$ with some numerical constant $C$ (Note that $L_{\Omega} \leq Cd^{1/4}$ is already enough for our purpose). Then for each $j$, by changing the variables we have
	\begin{equation}
	\begin{aligned}
	\Big( \int_{B_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}} &= \Big(\frac{r_j}{R_{B^d}}\Big)^{\frac{d+3}{2}}  	\Big( \int_{B^d}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym \beta\rangle \big| ^4d\bfsym \beta\Big)^{\frac{1}{2}}
	\end{aligned}
	\end{equation}
	According to Borell's Lemma and (\ref{hyperplane}) we get
	\begin{equation}
	\label{bound: borell}
	\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big( \int_{B_j}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle \big| ^4d\bfsym {\zeta}\Big)^{\frac{1}{2}}
	\leq \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big(\frac{r_j}{R_{B^d}}\Big)^{\frac{d+3}{2}}  	\Big( \int_{B^d}  \big|  \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym \beta\rangle \big| ^4d\bfsym \beta\Big)^{\frac{1}{2}}
	\leq  C_1 L^2_{B^d} \Big(\frac{r_j}{R_{B^d}}\Big)^{\frac{d+3}{2}}  .
	\end{equation}
	Now it remains to bound ${\rm Vol}(B_j)$ and $R_{B^d}$. It is well known that
	\begin{equation}
	\label{bound: volume}
	{\rm Vol}(B_j) = \frac{\pi^{d/2} r_j^d}{\Gamma(d/2+1)};~~R_{B^d} = \frac{\Gamma(d/2+1)^{1/d}}{\sqrt{\pi}} .
	\end{equation}
	where $\Gamma(\cdot)$ is the gamma function.
	Combine (\ref{inequality: hessian1}), (\ref{bound: borell}) and (\ref{bound: volume}), we get
	\begin{equation}
	\begin{aligned}
	& \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \frac{1}{(\sqrt{2\pi})^{d}}  \int_{\Omega_j}\Big| \mathcal{F}f_j(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2 \Big| d\bfsym {\zeta} \\
	& \lesssim \frac{1}{(\sqrt{2\pi})^{d}} \|f\|_{B^s_{\infty,1}} 2^{-js}  \frac{\pi^{3(d+1)/4} r_j^{3(d+1)/2}}{(\Gamma(d/2+1))^{3(d+1)/2d}}.
	\end{aligned}
	\end{equation}
	By applying Stirling's approximate formula,
	we have
	\begin{equation}
	\label{inequality: hessian2}
	\begin{aligned}
	& \sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \frac{1}{(\sqrt{2\pi})^{d}}  \int_{\Omega_j}\Big| \mathcal{F}f_j(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2 \Big| d\bfsym {\zeta} \\
	& \leq \|f\|_{B^s_{\infty,1}} (2\pi e^3)^{\frac{d}{4}} \frac{2^{(3(d+1)/2-s)j}}{d^{3(d+1)^2/4d}}
	\end{aligned}
	\end{equation}
	Combine (\ref{inequality: hessian1}) and (\ref{inequality: hessian2}), we get
	\begin{equation}
	\label{inequality: hessian3}
	\begin{aligned}
	&\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big| \\
	& \lesssim \|f\|_{B^s_{\infty,1}} \frac{(2\pi e^3)^{\frac{d}{4}}}{d^{3(d+1)^2/4d}}  \sum\limits_{j=0}^{N+1} 2^{j(\frac{3(d+1)}{2}-s)} \\
	& \lesssim \|f\|_{B^s_{\infty,1}} (2\pi e^3)^{\frac{d}{4}} d^{-\frac{3(d+1)}{4}}  \sum\limits_{j=0}^{N+1} 2^{j(\frac{3(d+1)}{2}-s)} .
	\end{aligned}
	\end{equation}
	We consider three cases here: 1). $3(d+1)/2-s \leq 0$; 2). $3(d+1)/2 > s > (3d+1) /2$; 3). $3(d+1)/2-s \geq 1$.

	Firstly, when $3(d+1)/2 -s \leq  0$, from (\ref{inequality: hessian3}), we get
	\begin{equation}
	\begin{aligned}
	&\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big|
	& \leq \|f\|_{B^s_{\infty,1}} (2\pi e^3)^{\frac{d}{4}} d^{-\frac{3(d+1)}{4}}  (N+2).
	\end{aligned}
	\end{equation}
	Taking $N =(\log_2 1/\|\bSigma\|_{op} -\log_2 \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) - 2)/2 $,
	we get
	\begin{equation}
	\label{bound: Hessian1}
	\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big|
	\leq \|f\|_{B^s_{\infty,1}} (2\pi e^3)^{\frac{d}{4}} d^{-\frac{3(d+1)}{4}} (-\log_2 \sqrt{\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) \|\bSigma\|_{op}})
	\end{equation}

	Secondly, when $3(d+1)/2 > s > (3d+1) /2$, we get
	\begin{equation}
	\begin{aligned}
	\label{bound: Hessian2}
	\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big|
	& \lesssim \|f\|_{B^s_{\infty,1}} (2\pi e^3)^{\frac{d}{4}} d^{-\frac{3(d+1)}{4}} 2^{N+2} \\
	& \lesssim  \|f\|_{B^s_{\infty,1}} (2\pi e^3)^{\frac{d}{4}} d^{-\frac{3(d+1)}{4}} (\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma) \|\bSigma\|_{op})^{-1/2}
	\end{aligned}
	\end{equation}

	Finally, when $(3d+1)/2-s > 0$, from (\ref{inequality: hessian3}), we get
	\begin{equation}
	\label{bound: Hessian3}
	\begin{aligned}
	\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big|
	&\lesssim \|f\|_{B^s_{\infty,1}} ( 2\pi e^3)^{\frac{d}{4}} d^{-\frac{3(d+1)}{4}}  \Big(\frac{p^{N+2}-1}{p-1} \Big)  \\
	&\lesssim \|f\|_{B^s_{\infty,1}} ( 2\pi e^3)^{\frac{d}{4}} d^{-\frac{3(d+1)}{4}}  p^{N+2}
	\end{aligned}
	\end{equation}
	where $p = 2^{3(d+1)/2-s}$. In this case, we have
	\begin{equation}
	p^{N+2} = \Big(\frac{2}{\sqrt{\|\bSigma \|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)}} \Big)^{3(d+1)/2-s}
	\end{equation}
	Plug it in (\ref{bound: Hessian2}), we have when $s < (3d+1)/2$
	\begin{equation}
	\sup\limits_{\|\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U}\|=1} \Big| \int_{\Omega} \mathcal{F}f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta}\cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \langle\bfm u}   \def\bU{\bfm U}  \def\UU{\mathbb{U},\bfsym {\zeta}\rangle ^2d\bfsym {\zeta} \Big|
	\lesssim \|f\|_{B^s_{\infty,1}} ( 2\pi e^3 )^{\frac{d}{4}} 2^{3d/2-s} d^{-\frac{3(d+1)}{4}}  (\|\bSigma \|_{op} \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma))^{s/2-3(d+1)/4}.
	\end{equation}

	Under our assumption $\|\bSigma\|_{op} = \sigma^2$, $\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)=\sigma^{-2\alpha}$, and $d = \sigma^{-2\beta}$ with $0<\alpha\leq \beta <1$. we plug this into (\ref{bound: Hessian1}) and (\ref{bound: Hessian2})
	respectively, and get:

	when $s\geq 3(d+1)/2$
	\begin{equation}
	\label{bound: Hessian4}
	\|\nabla^2 g\|_{op} \lesssim  \|f\|_{B^s_{\infty,1}} ( 2\pi e^3 )^{\frac{d}{4}}  \sigma^{3(d+1)\beta/2} (1-\alpha)\log_2\frac{1}{\sigma};
	\end{equation}

	when $(3d+1)/2 <s < 3(d+1)/2$
	\begin{equation}
	\label{bound: Hessian5}
	\|\nabla^2 g\|_{op} \lesssim   \|f\|_{B^s_{\infty,1}} ( 2\pi e^3 )^{\frac{d}{4}}  \sigma^{3(d+1)\beta/2 +\alpha -1}.
	\end{equation}

	when $s \leq (3d+1)/2$
	\begin{equation}
	\label{bound: Hessian6}
	\|\nabla^2 g\|_{op} \lesssim  \|f\|_{B^s_{\infty,1}}  ( 2\pi e^3 )^{\frac{d}{4}} 2^{3d/2-s}  \sigma^{3(d+1 )(\alpha + \beta-1)/2}\sigma^{(1-\alpha)s}.
	\end{equation}

	Now, we analyze the proper choices of $\alpha$ and $\beta$ that make $\|\nabla^2 g\|_{op} = O(1)$ as $\sigma \rightarrow 0$ and $d\rightarrow \infty$ simultaneously.
	For (\ref{bound: Hessian4}) and (\ref{bound: Hessian5}), a necessary and sufficient condition in asymptotic sense is that
	\begin{equation}
	\label{condtion: 1}
	\begin{cases}
	&(2\pi e^3)^{1/4} \sigma^{3\beta/2} \leq 1; \\
	& \frac{3}{2}\beta + \alpha -1 \geq 0;
	\end{cases}
	\end{equation}
	For (\ref{bound: Hessian6}), a necessary and sufficient condition in asymptotic sense is that
	\begin{equation}
	\label{condtion: 2}
	(128 \pi e^3)^{\frac{1}{4}}\sigma^{\frac{3}{2}(\alpha+\beta-1)} \leq 1,
	\end{equation}
	which is equivalent to $\alpha + \beta -1 >0$ for small enough $\sigma$.
	Given $\alpha$, $\beta\in (0,1)$, (\ref{condtion: 1}) and (\ref{condtion: 2}) together imply that when $\alpha + \beta > 1$, $\|\nabla ^2 g\|_{op}$ decays exponentially fast of the order $O(\sigma^{\epsilon d})$ for all $s\geq 0$ and some $\epsilon>0$.
	However, when $\alpha + \beta < 1$, $\|\nabla ^2 g\|_{op}$ can only decrease exponentially fast of the order $O(\sigma^{\epsilon' d})$ for $s \geq (3d+1)/2$ and some $\epsilon' >0$. In other words,
	for $f$ with insufficient smoothness, there may not be the guarantee to make $\| \nabla^2 g\|_{op}$ small.

\end{proof}

\subsection{Proof of Theorem \ref{theorem: minimax_lower_2}}

Note that in the proof of Theorem \ref{bound: lower_koltchinskii}, the authors assumed that $m$ i.i.d. copies of $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$ are available in order to use some large deviation bound. In the proof of Theorem \ref{theorem: minimax_lower_2}, we remove this requirement which we think makes the current method more general. Especially, the current method can be applied to the one sample situation under model (\ref{model}).

\begin{proof}
	We consider
	$$
	\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} = \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} + \bfsym {\xi},~\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in \RR^d,~\bfsym {\xi}\sim \mathcal{N}(\bf{0}; \bSigma)
	$$
	with unknown mean $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}$ and covariance matrix $\bSigma$.

	Let $\bTheta :=\{ \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0,...,\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_{M-1}\}$ be a set of $M = 2^d$ points such that $\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i\| = 8\varepsilon$, $\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j\| \geq 2 \varepsilon$, $0\leq i,j\leq M-1$, $i\neq j$, where $\varepsilon \leq 1/8$.
	Let $\varphi: \RR \rightarrow [0,1]$ be a function in $C^{\infty}_c(\RR)$ with compact support in $[0,1]$ and $\varphi(0) = a>0$. Based on $\varphi$, we define $\tilde{\varphi}: \RR^d \rightarrow \RR$
	such that $\tilde{\varphi}(\bfm t}   \def\bT{\bfm T}  \def\TT{\mathbb{T}) := \varphi(\|\bfm t}   \def\bT{\bfm T}  \def\TT{\mathbb{T}\|^2)$ and $\|\tilde{\varphi}\|_{B_{\infty,1}^s} \leq 1$. For $i\in \{0,1,...,M-1\}$ and $\ell = 1,...,d$, we denote by $e_{\ell i}\in \{-1,1\}$ as
	i.i.d. Rademacher random variables.
	Then for each $\ell=1,...,d$ we define the following random functions:
	\begin{equation}
	f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) := \sum\limits_{i=0}^{M-1} e_{\ell i} \varepsilon^s \tilde{\varphi}\Big(\frac{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i}{\varepsilon}\Big),~\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \RR^d.
	\end{equation}
	It is easy to see that $f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i) =  a \varepsilon^s$ with $e_{\ell i}=1$ and $f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i) =  -a \varepsilon^s$ with $e_{\ell i}=-1$, which implies that
	\begin{equation}
	e_{\ell i} = {\rm sign}(f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)),~\forall~i=0,...,M-1,~{\rm and}~\ell=1,...,d.
	\end{equation}
	Given $\varphi$ is compactly supported in $[0,1]$, the functions $\varepsilon^s\tilde{\varphi}((\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}-\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)/\varepsilon)$, $i=0,...,M-1$ have disjoint supports. This further implies that $\|f_{\ell}\|_{B^s_{\infty,1}} \leq 1$ given $a$ is small enough, $\|\tilde{\varphi}\|_{B_{\infty,1}^s} \leq 1$, and $0<\varepsilon \leq 1/8$.

	For now, we assume that for some $\delta >0$
	\begin{equation}
	\label{lowerbound2: assumption1}
	\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2  < \delta^2,
	\end{equation}
	which immediately implies that
	\begin{equation}
	\label{lowerbound2: assumption2}
	\inf_T  \max\limits_{1\leq \ell \leq d} \max_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \bTheta} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2  < \delta^2.
	\end{equation}
	This essentially means that for each $\ell=1,...,d$, there exists an estimator $T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ such that
	\begin{equation}
	\label{assumption: upper}
	\max_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \bTheta} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2  < \delta^2,~\ell=1,...,d,
	\end{equation}
	which leads to
	\begin{equation}
	\label{average_risk}
	\frac{1}{M} \sum_{i=0}^{M-1} \sum_{\ell=1}^d \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} (T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i))^2 < d\delta^2.
	\end{equation}
	We denote by $\hat{T}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) := (T_1(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}),...,T_{d}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}))^T \in \RR^d$, and $\hat{f}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}):=(f_1(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}),...,f_d(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))\in \RR^d$, then we can rewrite (\ref{assumption: upper}) as
	\begin{equation}
	\frac{1}{M} \sum_{i=0}^{M-1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} \big\| \hat{T}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - \hat{f}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)\big\|^2 < d\delta^2.
	\end{equation}

	Now we switch to consider the estimation problem of the random vector $\hat{f}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\in\RR^d$ over the parameter space $\bTheta$ based on the observation $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$ with the prior
	$\Pi:=(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta},\bfm e}   \def\bE{\bfm E}  \def\EE{\mathbb{E})$, where $\bfm e}   \def\bE{\bfm E}  \def\EE{\mathbb{E} \in \{-1,1\}^{d\times M}$ and is independent of $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}$. We further assume that $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}$ is uniformly distributed in $\bTheta$, and the entries of $\bfm e}   \def\bE{\bfm E}  \def\EE{\mathbb{E}$, $e_{\ell i}$ are i.i.d.
	Rademacher random variables for all $\ell=1,...,d$ and $i=1,...,M$.

	Given the prior $\Pi$, each entry of $\hat{f}$ only takes values in $\{a\varepsilon^s, -a\varepsilon^s \}$.
	Condition on $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$, we further assume that $\PP\{\hat{f}_{\ell} = a\varepsilon^s | \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \} = p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$. Due to the independence of the entries of $\bfm e}   \def\bE{\bfm E}  \def\EE{\mathbb{E}$,
	we can define the Bayes estimator of $\hat{f}$ as $\EE[\hat{f}|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}]$ with $\ell$-th entry as
	\begin{equation}
	\EE[\hat{f}_{\ell}| \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}] = a\varepsilon^s p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - a\varepsilon^s(1-p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})).
	\end{equation}
	We denote by $R_{\Pi}(T)$ the average risk of an estimator $T$ with respect to the prior $\Pi$. Then due to (\ref{average_risk}) and the definition of Bayes estimator, we have
	\begin{equation}
	\label{bound: upper_bayes}
	R_{\Pi}(\EE[\hat{f}|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}]) \leq 	R_{\Pi}(\hat{T}) < d\delta^2.
	\end{equation}
	On the other hand,
	\begin{equation}
	\label{formula: bayes_risk}
	R_{\Pi}(\EE[\hat{f}|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}]):=\EE_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \big[\EE_{\Pi} \big\| \EE[\hat{f}|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}]-\hat{f} \big\|^2 | \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\big] = 4\varepsilon^{2s} \sum_{\ell=1}^d \EE_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \big[ \EE_{\Pi} [p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})(1-p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}))|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}] \big].
	\end{equation}
	Now we consider the quantity $\EE_{\Pi} [p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})(1-p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}))|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}]$. We denote by $\phi_i:=p(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}| \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i,\sigma^2\bI_d )$ the multivariate Gaussian density with mean $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i$ and covariance matrix
	$\sigma^2\bI_d$. Then
	\begin{equation}
	\label{equation: bayes}
	\begin{aligned}
	\EE_{\Pi} [p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})(1-p_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}))|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}] &= \EE_{\Pi} \Big[ \frac{(\sum_{i=0}^M \mathbf{1}(e_{\ell i }=1)\phi_i)(\sum_{i'=0}^M \mathbf{1}(e_{\ell i' }=-1)\phi_{i'}) }{(\sum_{i=0}^M \phi_i)^2}\Big] \\
	&= \EE_{\Pi} \Big[ \frac{(\sum_{i,i'=0,i\neq i'}^M \mathbf{1}(e_{\ell i }=1) \mathbf{1}(e_{\ell i' }=-1)\phi_i\phi_{i'} }{(\sum_{i=0}^M \phi_i)^2}\Big] \\
	&= \frac{1}{4}\EE_{\Pi} \Big[ \frac{(\sum_{i,i'=0,i\neq i'}^M  \mathbf{1}(i\neq i') \phi_i\phi_{i'} }{(\sum_{i=0}^M \phi_i)^2}\Big] \\
	& = \frac{1}{4}\EE_{\Pi} \Big[ 1 - \frac{\sum_{i}^M   \phi_i^2  }{(\sum_{i=0}^M \phi_i)^2}\Big],
	\end{aligned}
	\end{equation}
	where the third equality is due to the fact that $\EE_{\Pi}[  \mathbf{1}(e_{\ell i }=1) \mathbf{1}(e_{\ell i' }=-1) | \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}] = \mathbf{1}\{ i\neq i'\}/4$ given $e_{\ell i}$'s are i.i.d. Rademacher random variables.
	Plug (\ref{equation: bayes}) into (\ref{formula: bayes_risk}), we get
	\begin{equation}
	R_{\Pi}(\EE[\hat{f}|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}]) = d\varepsilon^{2s} \EE_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \Big[\EE_{\Pi} \Big[ 1 - \frac{\sum_{i}^M   \phi_i^2  }{(\sum_{i=0}^M \phi_i)^2} \big| \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \Big] \Big] .
	\end{equation}
	Note that $\EE_{\Pi} \Big[ 1 - \frac{\sum_{i}^M   \phi_i^2  }{(\sum_{i=0}^M \phi_i)^2} \big| \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \Big]$ is a function of the random variable $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$. The density function of the marginal distribution of $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}$ is given by
	\begin{equation}
	p(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) = \frac{1}{M} \sum_{i=0}^M \phi_i.
	\end{equation}
	As a result,
	\begin{equation}
	\label{formula: bayes_risk_lower}
	\begin{aligned}
	\EE_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \Big[\EE_{\Pi} \Big[\frac{\sum_{i}^M   \phi_i^2  }{(\sum_{i=0}^M \phi_i)^2} \big| \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \Big] \Big] & \leq \EE_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \Big [\frac{\max_{i} \phi_i}{\sum_{i=0}^M \phi_i}  \Big]
	= M^{-1}\int_{\RR^d}  \max_{i} \phi_i d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \\
	& = M^{-1}\int_{\RR^d} \frac{1}{(\sqrt{2\pi\sigma})^d} e^{\frac{-\min_{i} \|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i\|^2}{2\sigma^2}} d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}  \\
	& \leq  M^{-1}\int_{\RR^d} \frac{1}{(\sqrt{2\pi\sigma})^d} e^{\frac{-[(\|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\| - 8\varepsilon)_+]^2}{2\sigma^2}} d\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \\
	& =   M^{-1}\int_{\RR^d} \exp \{ (\|\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y}\|^2-[(\|\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y}\| - 8\varepsilon/\sigma)_+]^2)/2 \} p(\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y} | \mathbf{0}, \bI_d )d\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y} \\
	& \leq M^{-1}\int_{\RR^d} \exp \{ 8\varepsilon \|\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y}\|/\sigma  \vee 32\varepsilon^2/\sigma^2 \} p(\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y} | \mathbf{0}, \bI_d )d\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y} \\
	& \leq M^{-1} (e^{16\varepsilon\sqrt{d}/\sigma} \vee e^{32\varepsilon^2/\sigma^2}).
	\end{aligned}
	\end{equation}
	where $(x)_+ :=\max\{x,0 \}$ and $p(\bfm y}   \def\bY{\bfm Y}  \def\YY{\mathbb{Y} | \mathbf{0}, \bI_d )$ denotes the density of an isotropic Gaussian random vector. The third line is due to
	$\min_{i} \|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i\| \geq \min_i | \|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\| - \|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i\||$ and $\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i\| = 8\varepsilon$. Set $\varepsilon = \sigma\sqrt{d}/\beta $ with $\beta = \max\{16/\log1.5, \sqrt{32/\log1.5}  \}$. Then from (\ref{formula: bayes_risk_lower}), we get
	\begin{equation}
	\label{bound: upper_bayes_risk}
	\EE_{\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} \Big[\EE_{\Pi} \Big[\frac{\sum_{i}^M   \phi_i^2  }{(\sum_{i=0}^M \phi_i)^2} \big| \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X} \Big] \Big] \leq \Big(\frac{3}{4}\Big)^d \leq \frac{3}{4},~\forall~d\geq 1.
	\end{equation}
	Combine (\ref{bound: upper_bayes_risk}) and (\ref{equation: bayes}), we get
	\begin{equation}
	\label{bound: lower_bayes}
	R_{\Pi}(\EE[\hat{f}|\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}]) \geq \frac{1}{4} d\varepsilon^{2s}.
	\end{equation}
	Taking $\delta:= \varepsilon^{s}/2$, (\ref{bound: lower_bayes}) contradicts (\ref{bound: upper_bayes}), which means that for $d\geq 1$, we have
	\begin{equation}
	\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2  \geq  \delta^2 = \frac{\varepsilon^{2s}}{4} \gtrsim (\sigma^2d)^s.
	\end{equation}
	On the other hand, to satisfy $\varepsilon<1/8$, we have $\varepsilon=\sigma\sqrt{d}/\beta\wedge 1/8$.
	This completes the proof of Theorem \ref{theorem: minimax_lower_2}.

\end{proof}

\subsection{Proof of Theorem \ref{theorem: minimax_lower_1}}

\begin{proof}
	In order to simplify the presentation, we will continue to use some of the notations already defined in the proof of Theorem \ref{theorem: minimax_lower_2}.
	For $i\in \{0,1,...,M-1\}$ and $\ell = 1,...,d$, we denote by $b_{\ell}(i)\in \{0,1\}$ as the $\ell$-th binary digit of $i$ so that $i=\sum^d_{\ell=1} b_{\ell}(i)2^{d-\ell}$.
	Similarly, we consider the following candidate functions:
	\begin{equation}
	f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) := \sum\limits_{i=0}^{M-1} (2b_{\ell}(i)-1) \varepsilon \tilde{\varphi}\Big(\frac{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i}{\varepsilon}\Big),~\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \RR^d.
	\end{equation}
	Note that $f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i) =  a \varepsilon$ with $b_{\ell}(i)=1$ and $f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i) =  -a \varepsilon$ with $b_{\ell}(i)=0$, which implies that
	\begin{equation}
	b_{\ell}(i) = \frac{1+{\rm sign}(f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i))}{2},~i=0,...,M-1,~and~\ell=1,...,d.
	\end{equation}
	Given $\varphi$ is compactly supported in $[0,1]$, the functions $\varepsilon\tilde{\varphi}((\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}-\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)/\varepsilon)$, $i=0,...,M-1$ have disjoint supports, which implies that $\|f_{\ell}\|_{B^s_{\infty,1}} \leq 1$ due to  $\|\tilde{\varphi}\|_{B_{\infty,1}^s} \leq 1$ and $\varepsilon \leq 1/8$.

	For now, we assume that for some $\delta >0$
	\begin{equation}
	\label{lowerbound2: assumption1}
	\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2  < \delta^2,
	\end{equation}
	which immediately implies that
	\begin{equation}
	\label{lowerbound2: assumption2}
	\inf_T  \max\limits_{1\leq \ell \leq d} \max_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \Theta} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2  < \delta^2.
	\end{equation}
	This essentially means that for each $\ell=1,...,d$, there exists an estimator $T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ such that
	\begin{equation}
	\max_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \bTheta} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2  < \delta^2,~\ell=1,...,d.
	\end{equation}
	By Markov's inequality, we get
	\begin{equation}
	\max_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \bTheta} \PP_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} \Big\{  |T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})| \geq \frac{a \varepsilon}{2}  \Big\} \leq \frac{4\delta^2}{ a^2 \varepsilon^{2}}.
	\end{equation}
	Take $\delta^2:= a^2\varepsilon^{2}/16$, we have
	\begin{equation}
	\label{inequality: prob1}
	\max_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \bTheta} \PP_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} \Big\{  |T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})| \geq \frac{a \varepsilon}{2}  \Big\} \leq \frac{1}{4}.
	\end{equation}
	Denote the event $\mathcal{E}$ as
	$$
	\mathcal{E} := \Big\{    |T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)| <  \frac{a \varepsilon}{2}  \Big\}.
	$$
	On this event, we have ${\rm sign}(T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})) = {\rm sign}(f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i))$, for $\ell=1,...,d$.
	Therefore for $i=0,...,M-1$
	\begin{equation}
	\label{inequality: sign}
	\PP_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} \{{\rm sign}(T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})) \neq {\rm sign}(f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)) \}\leq  \PP_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} \Big\{  |T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)| \geq \frac{a \varepsilon}{2}  \Big\} \leq \frac{1}{4}.
	\end{equation}

	We define
	\begin{equation*}
	\hat{\omega}:= ((1+{\rm sign}(T_1(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})))/2,...,(1+{\rm sign}(T_d(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})))/2)^T \in \{0,1\}^d;
	\end{equation*}
	and for $i=0,1,...,M-1$
	\begin{equation}
	\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i):= (b_1(i),...,b_d(i))^T.
	\end{equation}
	Let $\Lambda:=\{ 0,1 \}^d$ be the set of all binary sequences of length $d$, then it is easy to check that $\Lambda = \{\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}): \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \bTheta \}$.
	Let $\{ P_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}: \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \bTheta \}$ be a set of $2^d$ Gaussian measures with mean $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i$ and covariance matrix $\sigma^2\bI_d$.
	We state a user-friendly version of Assouad's Lemma as follows:
	\begin{lemma}[Assouad's Lemma]
		\label{lemma: Assouad}
		If the KL divergence $K(P_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} || P_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j})\leq \alpha <\infty$ for any $\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)$, $\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j)\in \Lambda$ with $\rho(\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i),\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j))=1$.
		Let $\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i}$ denote the corresponding expectation to the probability measure $P_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i}$. Then
		\begin{equation}
		\inf_{\hat{\omega}}\max_{\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i) \in \Lambda} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} \rho(\hat{\omega},\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)) \geq \frac{d}{2} \max \Big\{\frac{1}{2}e^{-\alpha}, 1-\sqrt{\alpha/2} \Big\}
		\end{equation}
		where $\rho$ denotes the Hamming distance of the binary sequences.
	\end{lemma}
	On one hand,
	\begin{equation}
	\label{contradiction: 21}
	\begin{aligned}
	\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} \rho(\hat{\omega},\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)) &= \sum_{\ell=1}^d \PP_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i}\{ \hat{\omega}_{\ell} \neq \omega_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i) \} = \sum_{\ell=1}^d \PP_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i}\{ {\rm sign}(T_{\ell}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}))\neq {\rm sign}(f_{\ell}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i))\} \leq d/4 .
	\end{aligned}
	\end{equation}
	where the inequality is due to (\ref{inequality: sign}).
	On the other hand, take $\varepsilon = \sigma/24$, for any $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i$, $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j\in \Lambda$,
	\begin{equation}
	K(P_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} || P_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j})= \frac{1}{2} \langle \bSigma^{-1} (\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j) , (\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_j) \rangle \leq  \frac{128  \varepsilon^2}{\sigma^2}  \leq \frac{2}{9}<\infty.
	\end{equation}
	By Lemma \ref{lemma: Assouad}, we have
	\begin{equation}
	\inf_{\hat{\omega}}\max_{\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i) \in \Lambda} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i} \rho(\hat{\omega},\omega(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_i)) \geq \frac{d}{3},
	\end{equation}
	which contradicts (\ref{contradiction: 21}). As a consequence, bound (\ref{lowerbound2: assumption1}) does not hold for $\delta^2 = a^2\varepsilon^{2}/16$ and $\varepsilon =  \sigma/24 \wedge 1/8$.
	This means that for some numerical constant $c_1$ we have
	\begin{equation*}
	\inf_T \sup\limits_{\|f\|_{B^s_{\infty,1}}\leq 1}\sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\|\leq 1} \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 \geq c_2 (\sigma^2 \wedge 1) .
	\end{equation*}
\end{proof}

\subsection{Proof of Theorem \ref{theorem: normal}}

\begin{proof}
	Firstly, we prove the normal approximation bound (\ref{bound: normal_apprx}).
	Recall that from (\ref{Taylor}), we have the following decomposition of the estimator
	$$
	g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) =g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}+ \bfsym {\xi}) = g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})+ \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \bfsym {\xi}\rangle + S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}).
	$$
	Then
	\begin{equation}
	\label{form: decomposition}
	\begin{aligned}
	g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) &= g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) + \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \\
	& = \langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) , \bfsym {\xi} \rangle + S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \widetilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})
	\end{aligned}
	\end{equation}
	where we used the fact that $\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) =  f^{N}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$. Set $Z \sim \mathcal{N}(0,1)$ to be a standard normal random variable. Then by the definition of $\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$ it is easy to see that
	$\langle \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) , \bfsym {\xi} \rangle = \sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) Z$.
	Then we have
	\begin{equation}
	g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) =  \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})Z + (\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))Z + S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \widetilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}).
	\end{equation}
	We denote by
	\begin{equation*}
	R:= (\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))Z + S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}}S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \widetilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}).
	\end{equation*}

	\begin{lemma}
		\begin{equation}
		\big|\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big| \leq \sigma_{g-f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})
		\end{equation}
	\end{lemma}
	\begin{proof}
		\begin{equation}
		\begin{aligned}
		\big|\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big| &= \big| \sqrt{\langle \bSigma \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\rangle} -  \sqrt{\langle \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\rangle} \big| \\
		& = \big| \|\bSigma^{1/2} \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\|  -  \|\bSigma^{1/2} \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\|\big| \\
		& \leq \| \bSigma^{1/2} (\nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})) \| = \sigma_{g-f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}).
		\end{aligned}
		\end{equation}
	\end{proof}

	Firstly, we consider the bound on $|\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})|$. As we have already shown,
	\begin{equation}
	\label{bound: variance}
	\begin{aligned}
	|\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})| &\leq \big\| \bSigma^{1/2} (\nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))\big\| \leq \|\bSigma \|_{op}^{1/2} \| \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})- \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\| \\
	& \leq \|\bSigma \|_{op}^{1/2}  \big(  \| \nabla f^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})- \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\|  + \| \nabla \widetilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\| \big).
	\end{aligned}
	\end{equation}
	For the term $ \| \nabla f^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})- \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\|$, we have
	\begin{equation}
	\label{bound: derivative_g_fN}
	\begin{aligned}
	\big\| \nabla f^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})- \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\big\| &=   \Big\|  \int  \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\xi}) p^o(\bfsym {\xi}) d\bfsym {\xi}- \int \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) p^o(\bfsym {\xi})d\bfsym {\xi} \Big\| \\
	& =  \Big\|  \int  \big( \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\xi}) - \nabla g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \big) p^o(\bfsym {\xi}) d \bfsym {\xi}\Big\|  \\
	& \leq \|\nabla^2 g\|_{op} \int \|\bfsym {\xi} \| p^o(\bfsym {\xi}) d\bfsym {\xi} \\
	& \leq \|\nabla^2 g\|_{op} \EE \|\bfsym {\xi}\| .
	\end{aligned}
	\end{equation}
	By assumption, we have $\|\nabla \widetilde{f}^N(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\| \leq R_N(f;\sigma)$.
	As a result, (\ref{bound: derivative_g_fN}) and (\ref{bound: variance}) lead to
	\begin{equation}
	\label{bound: sigma_variance}
	\big\| \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \big\| \leq C_*\|\bSigma\|^{1/2}_{op} (\|\nabla^2 g\|_{op} \EE \|\bfsym {\xi}\| + R_N(f;\sigma) ).
	\end{equation}
	for some constant $C_*$.
	From (\ref{bound: concentration_remainder}) and (\ref{bound: sigma_variance}), we get for all $t\geq 1$, with probability at least $1-e^{-t}$
	\begin{equation}
	\label{bound: remainder}
	|R| \lesssim \|\bSigma\|^{1/2}_{op} \sqrt{t} \big( (\|\nabla^2 g\|_{op} \EE \|\bfsym {\xi}\| + R_N(f;\sigma))  \vee  \|\nabla^2 g\|_{op} \|\bSigma\|_{op}^{1/2}\sqrt{t} \big) \vee (\EE\|\bfsym {\xi}\|^2)^{s/2}.
	\end{equation}
	Now, we proceed to prove the normal approximation bound. To accomplish this, we need the following elementary lemma which can be found in~\cite{koltchinskii2018asymptotically}, Lemma 10.
	\begin{lemma}
		\label{lemma: norm_approximation}
		For random variables $\eta_1,\eta_2$, denote
		\begin{equation}
		\Delta(\eta_1,\eta_2):= \sup\limits_{x \in \RR} \big| \PP\{\eta_1 \leq x \}  - \PP\{\eta_2 \leq x \}\big|
		\end{equation}
		and
		\begin{equation}
		\delta(\eta_1,\eta_2):= \inf\limits_{\delta>0} \Big\{  \PP\big\{ \big| \eta_1 -\eta_2 \big| \geq \delta \big\} +\delta   \Big\}
		\end{equation}
		Then for an arbitrary random variable $\eta$ and a standard normal random variable $Z$,
		\begin{equation}
		\Delta(\eta,Z) \leq \delta(\eta,Z).
		\end{equation}
	\end{lemma}

	We denote by $\eta:= (g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})- f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))/\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})$. By (\ref{form: decomposition}) and bound (\ref{bound: remainder}), we get for all $t \geq 1$ with probability at least $1-e^{-t}$
	\begin{equation}
	\Big| \eta - Z\Big| \lesssim K(f;\bSigma;\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \Big(\frac{(\EE^{1/2}\| \bfsym {\xi} \|^2 ) ^s}{\|\bSigma\|^{1/2}_{op}} \bigvee \|\bSigma\|^{1/2}_{op}t
	\bigvee \EE\|\bfsym {\xi}\|\|\nabla^2 g\|_{op}\sqrt{t} \bigvee R_N(f;\sigma)\sqrt{t} \Big).
	\end{equation}
	Take $t:=\log (\|\bSigma\|^{-1}_{op})$, then it is easy to check that with probability at least $1-\|\bSigma\|_{op}$,
	\begin{equation}
	\Big|\eta  - Z\Big| \lesssim   K(f;\bSigma;\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \Big(\frac{(\EE^{1/2}\| \bfsym {\xi} \|^2 ) ^s}{\|\bSigma\|^{1/2}_{op}} \bigvee \|\bSigma\|^{1/2}_{op}\log (\|\bSigma\|^{-1}_{op})
	\bigvee (\EE\|\bfsym {\xi}\|\|\nabla^2 g\|_{op}\vee R_N(f;\sigma))  \sqrt{\log (\|\bSigma\|^{-1}_{op})}  \Big).
	\end{equation}
	Following Lemma \ref{lemma: norm_approximation}, we get
	\begin{equation}
	\begin{aligned}
	& \Delta(\eta,Z) \leq \delta(\eta,Z) \lesssim  \\
	& K(f;\bSigma;\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\Big(\frac{(\EE^{1/2}\| \bfsym {\xi} \|^2 ) ^s}{\|\bSigma\|^{1/2}_{op}} \bigvee \|\bSigma\|^{1/2}_{op}\log (\|\bSigma\|^{-1}_{op})
	\bigvee (\EE\|\bfsym {\xi}\|\|\nabla^2 g\|_{op}\vee R_N(f;\sigma)) \sqrt{\log (\|\bSigma\|^{-1}_{op})} \Big) + \|\bSigma\|_{op}.
	\end{aligned}
	\end{equation}
	Clearly, $\|\bSigma\|_{op} \leq \|\bSigma\|^{1/2}_{op}\log (\|\bSigma\|^{-1}_{op})$ when $\|\bSigma\|_{op}$ is small enough. As a result,
	\begin{equation}
	\Delta(\eta,Z) \lesssim K(f;\bSigma;\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \Big(\frac{(\EE^{1/2}\| \bfsym {\xi} \|^2 ) ^s}{\|\bSigma\|^{1/2}_{op}} \bigvee \|\bSigma\|^{1/2}_{op}\log (\|\bSigma\|^{-1}_{op})
	\bigvee ( \EE\|\bfsym {\xi}\|\|\nabla^2 g\|_{op} \vee R_N(f;\sigma) ) \sqrt{\log (\|\bSigma\|^{-1}_{op})}  \Big).
	\end{equation}
	which gives (\ref{bound: normal_apprx}).

	Now we switch to prove the (\ref{bound: efficiency}). We introduce the following simple lemma.
	\begin{lemma}
		\label{lemma: orlicz}
		Let $Y$ be a non-negative random variable. Suppose that for some $A_1>0$,..., $A_m>0$, $\beta_1>0$, ..., $\beta_m>0$ and for all $t\geq 1$,
		\begin{equation}
		\PP \{  Y \geq A_1 t^{\beta_1} \vee \cdots \vee A_m t^{\beta_m}     \} \leq e^{-t}.
		\end{equation}
		Let $\beta:= \max_{1\leq j\leq m} \beta_j$. Then for any Orlicz function $\psi$ satisfying condition $\psi(t) \leq c_1e^{c_2t^{1/\beta}}$, for some constants $c_1$, $c_2>0$ and for $t\geq 0$ , we have
		\begin{equation}
		\| Y\|_{\psi} \leq A_1\vee\cdots \vee A_m.
		\end{equation}
	\end{lemma}

	By bound (\ref{bound: concentration_remainder}) and Lemma \ref{lemma: orlicz}, we have for any $\psi$ satisfying the condition $\psi(t)\leq c_1e^{c_2t}$ and for $t\geq 0$, we have
	\begin{equation}
	\big\| S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi}) - \mathbb{E}S_g(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta};\bfsym {\xi})  \big\|_{\psi}\lesssim  \big( \EE \|\bfsym {\xi}\|  \vee \|\bSigma\|^{1/2}_{op} \big)  \|\nabla^2 g\|_{op} \|\bSigma\|_{op}^{1/2}.
	\end{equation}
	for some constant $C$.
	Similarly, by Lemma \ref{lemma: orlicz} and (\ref{bound: sigma_variance}) we have
	\begin{equation}
	\big\| (\sigma_{g,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})) Z \big\|_{\psi} \lesssim \|\bSigma\|^{1/2}_{op} (\|\nabla^2 g\|_{op} \EE \|\bfsym {\xi}\| +  R_N(f;\sigma) ) \|Z\|_{\psi}.
	\end{equation}
	According to (\ref{bound: bias}), we have
	\begin{equation}
	\|\widetilde{f}^N \|_{\psi} \lesssim   (\EE\|\bfsym {\xi}\|^2)^{s/2}
	\end{equation}
	Therefore, we get
	\begin{equation}
	\|R \|_{\psi} \lesssim \|\bSigma\|_{op}^{1/2}(\|\nabla^2 g\|_{op} \EE \|\bfsym {\xi}\| +  R_N(f;\sigma) )  \bigvee (\EE^{1/2}\| \bfsym {\xi} \|^2 ) ^s.
	\end{equation}
	By taking $\psi(t) = t^2$, we get
	\begin{equation}
	\begin{aligned}
	& \Big\| \frac{g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} - Z \Big\|_{L^2(\PP)} \\
	&  \lesssim K(f;\bSigma;\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \Big(\frac{(\EE^{1/2}\| \bfsym {\xi} \|^2 ) ^s}{\|\bSigma\|^{1/2}_{op}} \bigvee \|\bSigma\|^{1/2}_{op}\log (\|\bSigma\|^{-1}_{op})
	\bigvee (\EE\|\bfsym {\xi}\|\|\nabla^2 g\|_{op} \vee R_N(f;\sigma)) \sqrt{\log (\|\bSigma\|^{-1}_{op})} \Big)
	\end{aligned}
	\end{equation}
	where $L^2(\PP)$ denotes the $L^2$-norm with respective to the standard Gaussian measure.

\end{proof}

\subsection{Proof of Theorem \ref{theorem: efficiency}}
\begin{proof}
	The main idea of the proof is based on an application of van Trees inequality, see~\cite{gill1995applications}.
	\begin{lemma}
		\label{Lemma: lowerbound_1}
		For all $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in \RR^d$ such that
		\begin{equation*}
		\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0\| \leq c \|\bSigma\|_{op}^{1/2} <1,
		\end{equation*}
		the following bound holds
		\begin{equation}
		\Big| \frac{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{ \sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} -1 \Big| \leq 2C^2_1 K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) c^{s-1} \|\bSigma\|_{op}^{(s-1)/2}
		\end{equation}
		with some constant $C_1>0$.
	\end{lemma}
	\begin{proof}
		\begin{equation}
		\begin{aligned}
		\Big| \frac{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{ \sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} -1 \Big| &= \frac{|\langle \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}), \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\rangle - \langle \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0), \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\rangle|}{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} \\
		& \leq \frac{\|\bSigma\|_{op} \|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\| (\|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\| + \|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\|)}{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}.
		\end{aligned}
		\end{equation}
		Recall that for $s>0$, we have $B_{\infty,1}^s(\RR^d) \subset C^s(\RR^d)$ where $C^s(\RR^d)$ is the H\"{o}lder space, see~\cite{Triebelfunction} sec. 2.5.7. Thus for $s\in (1,2]$
		\begin{equation}
		\label{bound: variance1}
		\begin{aligned}
		\|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) - \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\| & \leq \sum_{j=1}^d \Big| \frac{\partial f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{\partial x_j} - \frac{\partial f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}{\partial x_j} \Big| \\
		&  \leq \big\| f \big\|_{C^s} \|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} - \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0 \|^{(s-1)} \\
		& \leq C_1 \big\| f \big\|_{B^s_{\infty,1}} c^{s-1} \|\bSigma\|_{op}^{(s-1)/2} .
		\end{aligned}
		\end{equation}

		Now we switch to bound $\|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})\|$.
		\begin{equation}
		\label{bound: variance2}
		\begin{aligned}
		\| \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}) \| & =  \sqrt{ \Big(\frac{\partial f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{\partial x_1} \Big)^2 + \cdots + \Big(\frac{\partial f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{\partial x_d} \Big)^2}  \\
		& \leq \sum_{j=1}^d \Big| \frac{\partial f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{\partial x_j} \Big| \leq \sum_{j=1}^d \Big\| \frac{\partial f}{\partial x_j} \Big\|_{\infty} \leq \|f\|_{C^s} \leq C_1\big\| f \big\|_{B^s_{\infty,1}}  .
		\end{aligned}
		\end{equation}

		Combine the results in (\ref{bound: variance1}) and (\ref{bound: variance2}), we get
		\begin{equation*}
		\Big| \frac{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})}{ \sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} -1 \Big| \leq  \frac{2C_1^2c^{s-1}\|\bSigma\| _{op}^{(s+1)/2}  \|f\|^2_{B^s_{\infty,1}}}{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}
		\leq 2C_1^2K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)c^{s-1}\|\bSigma\| _{op}^{(s-1)/2}.
		\end{equation*}
	\end{proof}

	The bound of Lemma \ref{Lemma: lowerbound_1} implies that
	\begin{equation}
	\label{bound: lower_switch1}
	\begin{aligned}
	&\sup\limits_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma)} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 }{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} = \sup\limits_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma)} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 }{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} \frac{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} \\
	& \geq \sup\limits_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma)} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 }{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}  \frac{1}{1+ 2C_1^2K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)c^{s-1}\|\bSigma\| _{op}^{(s-1)/2}}.
	\end{aligned}
	\end{equation}

	Now we switch to bound
	\begin{equation*}
	\sup\limits_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}\in U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma)} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 }{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} .
	\end{equation*}
	Set $c_0:=c/C_1K(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)$, then for any $t\in [-c_0, c_0]$ and $\bfsym {\delta}}           \def\bDelta {\bfsym {\Delta} \in \RR^d$, we define
	\begin{equation}
	\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_t := \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0 + t\bfsym {\delta}}           \def\bDelta {\bfsym {\Delta}.
	\end{equation}
	Consider the estimation of the following functional
	\begin{equation*}
	\varphi(t) := f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_t),~t\in [-c_0,c_0]
	\end{equation*}
	based on an observation $\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}\sim \mathcal{N}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_t;\bSigma)$ . By choosing $\bfsym {\delta}}           \def\bDelta {\bfsym {\Delta}:= \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)/\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)$, we have
	\begin{equation}
	\begin{aligned}
	\|t\bfsym {\delta}}           \def\bDelta {\bfsym {\Delta}\| &\leq \frac{c_0 \|\bSigma\|_{op} \|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\| }{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} \leq \frac{c_0 \|\bSigma\|_{op} C_1 \|f\|_{B_{\infty,1}^s} }{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}\leq c_0 C_1\|\bSigma\|_{op}^{1/2} K(f;\bSigma;\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) \leq c \|\bSigma\|_{op}^{1/2} < 1,
	\end{aligned}
	\end{equation}
	which implies that $\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_t \in U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma)$. As a consequence,
	\begin{equation}
	\label{bound: lower_switch2}
	\sup\limits_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} \in U(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0;c;\bSigma)} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2 }{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)} \geq \sup\limits_{t \in [-c_0 ,c_0]} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - \varphi(t))^2 }{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}.
	\end{equation}
	Let $\pi$ be a prior density on $[-1,1]$ with $\pi(-1) = \pi(1) = 0$ and such that
	\begin{equation}
	J_{\pi} := \int^1_{-1} \frac{(\pi'(s))^2}{\pi(s)} ds < \infty.
	\end{equation}
	Denote $\pi_{c_0}(t) = c_0^{-1}\pi(t/c_0)$, with $t\in[-c_0, c_0]$. Then $J_{\pi_{c_0}} =  J_{\pi}/c_0^2$.

	By the van Trees inequality~\cite{gill1995applications}, for any estimator $T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})$ of $\varphi(t)$, the following inequalities hold
	\begin{equation}
	\label{bound: key_inequality}
	\begin{aligned}
	& \sup\limits_{t\in[-c_0,c_0]} \EE_{t} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - \varphi(t))^2 \geq \int^{c_0}_{-c_0} \EE_{t} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - \varphi(t))^2 \pi_{c_0}(t) dt  \\
	& \geq \frac{\big(\int^{c_0}_{-c_0} \varphi'(t)\pi_{c_0}(t)dt\big)^2}{\int^{c_0}_{-c_0} \mathcal{I}(t) \pi_{c_0}(t)dt + J_{\pi}/c_0^2} \geq \frac{\big(\int^{c_0}_{-c_0} \varphi'(t)\pi_{c_0}(t)dt\big)^2}{1+ J_{\pi}/c_0^2}.
	\end{aligned}
	\end{equation}
	The last inequality is due to the fact that when $\bfsym {\delta}}           \def\bDelta {\bfsym {\Delta} = \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)/\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)$, the Fisher information $\mathcal{I}(t) = \langle \bSigma^{-1} \bfsym {\delta}}           \def\bDelta {\bfsym {\Delta}, \bfsym {\delta}}           \def\bDelta {\bfsym {\Delta} \rangle = 1$.
	It remains to give a lower bound on $\big(\int^{c_0}_{-c_0} \varphi'(t)\pi_{c_0}(t)dt\big)^2$. Recall that $\varphi'(t) = \langle \bfsym {\delta}}           \def\bDelta {\bfsym {\Delta} ,  \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_t)\rangle$ and let
	\begin{align}
	& {\rm I}_0 := \int^{c_0}_{-c_0} \varphi'(0) \pi_{c_0}(t) dt = \int^{c_0}_{-c_0} \langle \bfsym {\delta}}           \def\bDelta {\bfsym {\Delta}, \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) \rangle \pi_{c_0}(t) dt = \langle \bfsym {\delta}}           \def\bDelta {\bfsym {\Delta}, \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\rangle \\
	& {\rm I}_1 := \int^{c_0}_{-c_0} (\varphi'(t) - \varphi'(0)) \pi_{c_0}(t) dt .
	\end{align}
	Then we have
	\begin{equation}
	\Big(\int^{c_0}_{-c_0} \varphi'(t)\pi_{c_0}(t)dt\Big)^2 = ({\rm I}_0 + {\rm I}_1)^2 \geq {\rm I}_0^2 - 2|{\rm I}_0||{\rm I}_1| = \sigma_{f,\bfsym {\xi}}^2 (\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) - 2\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) |{\rm I}_1|,
	\end{equation}
	where we used the assumption that $\bfsym {\delta}}           \def\bDelta {\bfsym {\Delta} = \bSigma \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)/\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)$. Now we need to bound $|{\rm I}_1|$. Note that
	\begin{equation}
	\begin{aligned}
	|{\rm I}_1| \leq |\varphi'(t) - \varphi'(0)| &=  |\langle \bfsym {\delta}}           \def\bDelta {\bfsym {\Delta} , \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_t) - \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\rangle | \leq \|\bfsym {\delta}}           \def\bDelta {\bfsym {\Delta} \| \|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_t) - \nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\| \\
	& \leq \frac{\|\bSigma\|_{op}^{1/2}\|\nabla f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\|}{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}   \|f\|_{C^s} c^{s-1} \|\bSigma\|_{op}^{(s-1)/2}  \\
	& \lesssim \frac{c^{s-1}\|\bSigma\|_{op}^{(s+1)/2} \|f\|^2_{C^s}}{\sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)}\\
	&\leq C_1^2 K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) c^{s-1}\|\bSigma\|_{op}^{(s-1)/2} \sigma_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)
	\end{aligned}
	\end{equation}
	As a result, we have
	\begin{equation}
	\label{bound: lower_numerator}
	\Big(\int^{c_0}_{-c_0} \varphi'(t)\pi_{c_0}(t)dt\Big)^2  \geq \sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) \Big( 1 -   2C_1^2 K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) c^{s-1} \|\bSigma\|_{op}^{(s-1)/2}   \Big).
	\end{equation}
	By plugging (\ref{bound: lower_numerator}) into (\ref{bound: key_inequality}), we get
	\begin{equation}
	\sup\limits_{t\in[-c_0,c_0]} \frac{\EE_{t} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - \varphi(t))^2 }{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) }  \geq \Big( \frac{1 -   2C^2_1 K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) c^{s-1} \|\bSigma\|_{op}^{(s-1)/2}}{ 1 + J_{\pi}/c_0^2 }\Big)
	\end{equation}
	Together with (\ref{bound: lower_switch1}) and (\ref{bound: lower_switch2}), we get
	\begin{equation}
	\begin{aligned}
	\inf_T  \sup\limits_{\|\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta} -\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0\|\leq c\|\bSigma\|_{op}^{1/2}} \frac{\EE_{\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}} (T(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - f(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}))^2}{\sigma^2_{f,\bfsym {\xi}}(\bfsym {\theta}}           \def\bTheta {\bfsym {\Theta})} &\geq \Big( \frac{1 -   2C_1^2 K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) c^{s-1} \|\bSigma\|_{op}^{(s-1)/2}}{(1+ 2C_1^2K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0) c^{s-1} \|\bSigma\|_{op}^{(s-1)/2})(1 + J_{\pi}/c_0^2)} \Big)  \\
	& \geq 1 - C_1^2K^2(f; \bSigma; \bfsym {\theta}}           \def\bTheta {\bfsym {\Theta}_0)\Big( \frac{J_{\pi}}{c^2 + J_{\pi}} + 4 c^{s-1} \|\bSigma\|_{op}^{(s-1)/2}\Big)
	\end{aligned}
	\end{equation}
	for some constant $C$.
\end{proof}

\subsection{Proof of Theorem \ref{theorem: adaptive}}
\begin{proof}
	We consider
	\begin{equation}
	\label{difference: g}
	\begin{aligned}
		\hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) & =  \frac{1}{(2\pi)^{d/2}} \Big(  \int_{\hat{\Omega}}  \mathcal{F} f^{\hat{N}}(\bfsym {\zeta})e^{\langle \hat{\bSigma} \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta}
		 -\int_{\Omega}  \mathcal{F} f^N(\bfsym {\zeta})e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta} \Big) \\
		 & =  \frac{1}{(2\pi)^{d/2}} \Big(  \int_{\Omega}  \mathcal{F} f(\bfsym {\zeta}) \big( e^{\langle (\hat{\bSigma}-\bSigma) \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}-1 \big) e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta}  \Big) \\
		 & + \frac{1}{(2\pi)^{d/2}}  \int_{(\hat{\Omega} -\Omega) \cup (\Omega - \hat{\Omega})} \mathcal{F} f^{\hat{N}}(\bfsym {\zeta})e^{\langle \hat{\bSigma} \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta}.
		\end{aligned}
	\end{equation}
	In the following, we will bound the two terms respectively. We denote by $\Delta: = e^{\langle (\hat{\bSigma}-\bSigma) \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}$.  By the concentration bound on the Gaussian covariance matrix \cite{koltchinskii2017}, for any $t>0$ we get with probability at least $1-e^{-t}$
	\begin{equation}
	\label{event: 1}
		\big|  \langle (\hat{\bSigma} -\bSigma)\bfsym {\zeta} , \bfsym {\zeta} \rangle \big| \leq \big\| \hat{\bSigma} -\bSigma \big\|_{op} \big\| \bfsym {\zeta} \big\|^2 \lesssim \frac{\|\bSigma_0\|_{op}}{n} \Big( \sqrt{\frac{\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma)}{n}} \bigvee \sqrt{\frac{t}{n}} \Big) \big\| \bfsym {\zeta} \big\|^2.
	\end{equation}
	We denote by ${\cal  E}} \def\cE{{\cal  E}_1$ as the event in (\ref{event: 1}). Conditionally on ${\cal  E}} \def\cE{{\cal  E}_1$,
	when $n$ is large enough, we have
	\begin{equation}
	\label{bound: part1}
	\begin{aligned}
		& \Big| \frac{1}{(2\pi)^{d/2}} \Big(  \int_{\Omega}  \mathcal{F} f(\bfsym {\zeta}) \big( e^{\langle (\hat{\bSigma}-\bSigma) \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}-1 \big) e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta}  \Big) \Big|  \\
		&\leq \frac{1}{(2\pi)^{d/2}}   \int_{\Omega}  \Big| \mathcal{F} f(\bfsym {\zeta}) \big( e^{\langle (\hat{\bSigma}-\bSigma) \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}-1 \big) e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} \Big| d\bfsym {\zeta}  \\
		& \leq \frac{e}{(2\pi)^{d/2}} \Big(  \int_{\Omega}  \Big| \mathcal{F} f(\bfsym {\zeta})\Big|^2 d\bfsym {\zeta}\Big)^{1/2} \Big( \int_{\Omega}  \big| \Delta-1 \big|^2 d\bfsym {\zeta} \Big)^{1/2}  \\
		&  \leq \frac{e}{(2\pi)^{d/2}}  \big\| f \big\|_{2}  \Big( \int_{\Omega}  \big| \Delta-1 \big|^2 d\bfsym {\zeta} \Big)^{1/2} \\	&  \leq \frac{e}{(2\pi)^{d/2}}  \big\| f \big\|_{\infty} {\rm Vol}(\Omega)* (n^{-(\alpha+1)/2} \vee  n^{-\alpha-1/2}\sqrt{t})\\
		& \lesssim \frac{e}{(2\pi)^{d/2}}  \big\| f \big\|_{B_{\infty,1}^s} {\rm Vol}(B(\Omega)) * (n^{-(\alpha+1)/2} \vee  n^{-\alpha-1/2}\sqrt{t})
		\end{aligned}
	\end{equation}
	where $B(\Omega)$ is the $d$-ball with radius $R=2^{N+1}$. The second inequality is due to H\"{o}lder's inequality, the third one is due to Plancherel's equality, and the forth one is due to the bound in (\ref{event: 1}).
	Given $\alpha\in (1/2,1)$, we have
	\begin{equation}
		{\rm Vol}(B(\Omega)) \asymp \frac{1}{\sqrt{\pi d}} \Big(\frac{2\pi e}{d} \Big)^{d/2} n^{(1-\alpha)d/2}.
	\end{equation}
	Since $d\geq \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0) = n^{\alpha}$. Then we get for all $t\geq 0$ and some $\epsilon>0$, with probability at least $1-e^{-t}$
	\begin{equation}
	\begin{aligned}
	       & \Big| \frac{1}{(2\pi)^{d/2}} \Big(  \int_{\Omega}  \mathcal{F} f(\bfsym {\zeta}) \big( e^{\langle (\hat{\bSigma}-\bSigma) \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}-1 \big) e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta}  \Big) \Big|   \\
	       & \lesssim n^{-\epsilon d} * (n^{-(\alpha+1)/2} \vee  n^{-\alpha-1/2}\sqrt{t}).
	       \end{aligned}
	\end{equation}
	Apparently, by taking $t=n^{\alpha}$ and $n$ is large enough such that $n^{2\alpha-1}> e$, we get with probability at least $1-e^{-n^{\alpha}}$
	\begin{equation}
	\begin{aligned}
	       & \Big| \frac{1}{(2\pi)^{d/2}} \Big(  \int_{\Omega}  \mathcal{F} f(\bfsym {\zeta}) \big( e^{\langle (\hat{\bSigma}-\bSigma) \bfsym {\zeta}, \bfsym {\zeta} \rangle/2}-1 \big) e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta}  \Big) \Big|
	       & \lesssim n^{-\epsilon d}n^{-1/2}.
	       \end{aligned}
	\end{equation}

	Now we switch to bound the second part on the right hand side of (\ref{difference: g}). Firstly, we consider the difference $|\hat{N}-N|$ and denote by $M:=(\hat{\Omega} -\Omega) \cup (\Omega - \hat{\Omega})$.
   	Recall that from (\ref{N}), we have
   	\begin{equation}
   	\label{difference: N}
   	\begin{aligned}
   		\big| \hat{N} - N\big| &= \big| 1/2* \log(n/{\rm tr}(\hat{\bSigma}_0))- 1/2* \log(n/{\rm tr}(\bSigma_0)) \big|
   		& = \log \frac{\sqrt{{\rm tr}(\bSigma_0)}}{\sqrt{{\rm tr}(\hat{\bSigma}_0)}}.
   		\end{aligned}
   	\end{equation}
   	Now we consider bounding $\sqrt{{\rm tr}(\bSigma_0)/{\rm tr}(\hat{\bSigma}_0)}$. It is easy to see that
   	\begin{equation}
   	\begin{aligned}
   		\sqrt{{\rm tr}(\hat{\bSigma}_0)}  &=  \sqrt{{\rm tr}(\sum_{j=1}^{n-1} \widetilde{\bfsym \beta}_j \otimes \widetilde{\bfsym \beta}_j)/(n-1)}
   		& = \frac{1}{\sqrt{n-1}} \sqrt{\sum_{j=1}^{n-1} \big\| \widetilde{\bfsym \beta}_j\big\|^2 }.
   		\end{aligned}
   	\end{equation}
   	Suppose that $\{\widetilde{\bfsym \beta}'_{j}\}_{j=1}^{n-1}$ is another independent identical copy of $\{\widetilde{\bfsym \beta}_{j}\}_{j=1}^{n-1}$. Then we have
   	\begin{equation}
   	\begin{aligned}
   		\Big| \sqrt{{\rm tr}(\hat{\bSigma}_0)}  -   \sqrt{{\rm tr}(\hat{\bSigma}_0')} \Big|
   		& =  \Big| \sqrt{ \frac{ {\rm tr}(\sum_{j=1}^{n-1} \widetilde{\bfsym \beta}_j \otimes \widetilde{\bfsym \beta}_j)}{n-1} } - \sqrt{ \frac{ {\rm tr}(\sum_{j=1}^{n-1} \widetilde{\bfsym \beta}_j' \otimes \widetilde{\bfsym \beta}_j')}{n-1} } \Big| \\
   		& \leq \frac{1}{n-1} \Big| \sqrt{\sum_{j=1}^{n-1} \big\| \widetilde{\bfsym \beta}_j\big\|^2 } - \sqrt{\sum_{j=1}^{n-1} \big\| \widetilde{\bfsym \beta}'_j\big\|^2 } \Big| \\
   		& \leq \frac{1}{n-1} \sqrt{\sum_{j=1}^{n-1} \big\| \widetilde{\bfsym \beta}_j - \widetilde{\bfsym \beta}_j'\big\|^2 }
   		\end{aligned}
   	\end{equation}
   	which shows that $\sqrt{{\rm tr}(\hat{\bSigma}_0)}$ is a Lipschitz function of $(\widetilde{\bfsym \beta}_1,...,\widetilde{\bfsym \beta}_{n-1})$. By Lemma \ref{Lemma:isoperimetric}, we get
   	for all $t\geq 1$, with probability at least $1-e^{-t}$
   	\begin{equation}
   		\Big| \sqrt{{\rm tr}(\hat{\bSigma}_0)}  -   \sqrt{{\rm tr}(\bSigma_0)} \Big| \lesssim  \big\|\bSigma_0\big\|_{op}^{1/2}\sqrt{ \frac{ t}{n}},
   	\end{equation}
   	together with (\ref{difference: N}), it implies that
   	\begin{equation}
   		\big| \hat{N} - N \big| =    \log  \sqrt{ \frac{{\rm tr}(\hat{\bSigma}_0)}{ {\rm tr}(\bSigma_0)  } }  \leq \log\Big( 1+ \sqrt{\frac{t}{n \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0)}} \Big) \leq \sqrt{\frac{t}{n \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0)}},
   	\end{equation}
   	where we used the inequality $\log(1+x)\leq x$ for all $x\geq 0$. Set $\eta(t):= \sqrt{t/(n\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0))}$ and we denote by event ${\cal  E}} \def\cE{{\cal  E}_2: = \{| \hat{N} - N | \leq \eta(t)\}$ and $M:= (\hat{\Omega} -\Omega) \cup (\Omega - \hat{\Omega})$. Then on event ${\cal  E}} \def\cE{{\cal  E}_1$ and ${\cal  E}} \def\cE{{\cal  E}_2$, similarly as in
   	(\ref{bound: part1}) we have
   	\begin{equation}
   	\label{bound: part2}
   	\begin{aligned}
   		& \frac{1}{(2\pi)^{d/2}}  \int_{(\hat{\Omega} -\Omega) \cup (\Omega - \hat{\Omega})} \mathcal{F} f(\bfsym {\zeta})e^{\langle \hat{\bSigma} \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta} \\
   		& \leq \frac{1}{(2\pi)^{d/2}}  \Big(\int_{M} \Big| \mathcal{F} (\bfsym {\zeta}) \Big|^2 d\bfsym {\zeta}\Big)^{1/2} \Big(\int_{M} e^{\langle (\hat{\bSigma}-\bSigma) \bfsym {\zeta}, \bfsym {\zeta} \rangle}  e^{\langle \bSigma \bfsym {\zeta}, \bfsym {\zeta} \rangle}d\bfsym {\zeta}\Big)^{1/2} \\
   		& \lesssim \frac{1}{(2\pi)^{d/2}} \big\| f \big\|_{B^s_{\infty,1}}  {\rm Vol}(M) \\
   		& \leq \frac{1}{(2\pi)^{d/2}} ({\rm Vol}(B_{\eta}^+(\Omega)) - {\rm Vol}(B_{\eta}^-(\Omega))) \\
   		& \lesssim \frac{1}{(2\pi)^{d/2}} \frac{1}{\sqrt{d\pi}} \Big( \frac{2\pi e}{d}\Big)^{d/2} ( 2^{(N+\eta(t))d} - 2^{(N-\eta(t))d}) \\
   		& \lesssim \frac{1}{\sqrt{d\pi} } \Big( \frac{n^{1-\alpha}}{d }\Big)^{d/2} (4e)^{d/2},
   		\end{aligned}
   	\end{equation}
   	where $B_{\eta}^+(\Omega) $ and $B_{\eta}^-(\Omega))$ denote the $d$-ball with radius $2^{N+\eta(t)}$ and $2^{N-\eta(t)}$ respectively. Clearly, $M\subset B_{\eta}^+(\Omega)-B_{\eta}^-(\Omega))$
   	Given $\alpha\in (1/2,1)$, and $d\geq \bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0) = n^{\alpha}$, we get with some $\epsilon'>0$ and for $n^{2\alpha-1}>4e$,
   	\begin{equation}
   		 \frac{1}{(2\pi)^{d/2}}  \int_{(\hat{\Omega} -\Omega) \cup (\Omega - \hat{\Omega})} \mathcal{F} f^{\hat{N}}(\bfsym {\zeta})e^{\langle \hat{\bSigma} \bfsym {\zeta}, \bfsym {\zeta} \rangle/2} e^{i\bfsym {\zeta} \cdot \bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}} d\bfsym {\zeta} \leq n^{-\epsilon'd}\times n^{-1/2}.
   	\end{equation}
   	Further, by taking $t:=\bfm r}   \def\bR{\bfm R}  \def\RR{\mathbb{R}(\bSigma_0) = n^{\alpha}$, $\varepsilon = \min\{ \epsilon, \epsilon'\}$, and applying the union bound, we get with probability at least $1-e^{-n^{\alpha}}$
   	\begin{equation}
   		 \big| \hat{g}(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X}) - g(\bfm x}   \def\bX{\bfm X}  \def\XX{\mathbb{X})\big| \lesssim n^{-\varepsilon d}\times n^{-1/2}.
   	\end{equation}
\end{proof}

\bibliographystyle{abbrv}