Minimax bounds for estimation of normal mixtures
Arlene K. H. Kim
This paper deals with minimax rates of convergence for estimation of density functions on the real line. The densities are assumed to be location mixtures of normals, a global regularity requirement that creates subtle difficulties for the application of standard minimax lower bound methods. Using novel Fourier and Hermite polynomial techniques, we determine the minimax optimal rate---slightly larger than the parametric rate---under squared error loss. For Hellinger loss, we provide a minimax lower bound using ideas modified from the squared error loss case. %Minimax rates of convergence for the problem of estimation in nonparametric models are often determined by strategically chosen submodels that capture the difficulty of the whole problem. The submodels are constructed to have separation properties, such as those required by Assouad's lemma, while still satisfying the constraints of the model. For the estimation of submodels, even more constraints are imported, which can make the calculation of minimax rates substantially more difficult. This paper illustrates the difficulty for a density estimation problem by means of a normal location mixture model, which actually has the same minimax rates as for a larger family of analytic densities. The analysis exploits a stability property of a two-parameter family of functions under convolution with the standard normal followed by Fourier transformation.
kyk_Mar28.tex
\documentclass{amsart}
\usepackage{hyperref}
\usepackage[active]{srcltx}

\usepackage{natbib}
%\usepackage[notcite, notref, color]{showkeys}
\usepackage[x11names,svgnames]{xcolor}
%\RequirePackage{amsthm,amsmath,natbib}

\definecolor{labelkey}{cmyk}{0.25,0.2,1,0}
\def\Hrule{\bigskip\hrule\bigskip}

\def\DBP{\bgroup\color{red}}
\def\eDBP{\egroup}
\def\xDBP{\bgroup\color{blue}}
%\newcommand{\beq}{\begin{equation}}  % expects a label
%\newcommand{\eeq}{\end{equation}}

\newcommand{\beqN}{\begin{equation*}}  %no label, same as $$ .... $$ except for alignment
\newcommand{\eeqN}{\end{equation*}}

\def\text#1{\hbox{\rm#1}}
\def\qt#1{\qquad\text{#1}}

 \textwidth=5.5in
%\setlength{\parindent}{0pt} \setlength{\parskip}{2ex}

\usepackage{amsthm,amsmath,amssymb}
\usepackage{bbm}
\usepackage{natbib}
\usepackage{verbatim}
\usepackage{epsfig}
\usepackage{graphicx} 
\usepackage{enumerate}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}{Remark}[section]
\newtheorem{example}[theorem]{Example}

\newcommand{\beq}{\begin{equation}}  % expects a label
\newcommand{\eeq}{\end{equation}}

\newcommand{\ben}{\begin{enumerate}}  % expects a label
\newcommand{\een}{\end{enumerate}}

\def\qt#1{\qquad\text{#1}}

%\newcommand {\ft} {{\mathcal{T}}}
%\newcommand {\sigma_m}{{C_3\sqrt{m}}}
\newcommand {\class}{{\mathcal{F}}}
\newcommand {\risk} {{\mathcal{R}}}
\newcommand {\comp} {\mathbb{C}}
\newcommand {\thetahat} {{\hat \theta}}
\newcommand {\sinc}{{\text{sinc}}}
\newcommand {\one}{{\mathbbm{1}}}

\newcommand {\leb}{{\frak m}}
\newcommand {\nl}{\newline}
\newcommand {\ul}{\underline}

\def\minner#1#2{{<#1,#2>_\leb}}
\def\mnorm#1{{\Vert#1\Vert_\leb}}

\def\phiinner#1#2{{<#1,#2>_\phi}}
\def\phinorm#1{{\Vert#1\Vert_\phi}}

%\newcommand {\AA} {{\mathcal A}}
\newcommand {\bb} {{\mathbb B}}
\newcommand {\CC} {{\mathcal C}}
\newcommand {\DD} {{\mathcal D}}
\newcommand {\ee} {{\mathbb E}}
\newcommand {\FF} {{\mathcal F}}
\newcommand {\GG} {{\mathcal G}}
%\newcommand {\gg} {{\mathbb G}}
\newcommand {\hh}{{\mathbb H}}

\newcommand {\KK} {{\mathcal K}}
\newcommand {\LL} {{\mathcal L}}
\newcommand {\MM} {{\mathcal M}}
\newcommand {\nn}{{\mathbb N}}

\newcommand {\OO}{{\mathcal O}}
\newcommand {\littleo}{ {\scriptstyle{\mathcal O}}}
\newcommand {\PP} {{\mathcal P}}
\newcommand {\pp} {{\mathbb P}}
\newcommand {\qq} {{\mathbb Q}}
\newcommand {\QQ} {{\mathcal Q}}
\newcommand {\rr} {{\mathbb R}}
%\newcommand {\SS} {{\mathcal S}}
\def\mathbi#1{\textbf{\em #1}}

\newcommand {\UU} {{\mathcal U}}
\newcommand {\vv} {{\mathbb V}}

\newcommand {\XX} {{\mathcal X}}
\newcommand {\zz} {{\mathbb Z}}

\newcommand {\up}{u}
\newcommand {\lo}{l}
\newcommand {\fourier}{{\mathcal{T}}}
\newcommand {\ft}{{\mathcal{F}}}
%\newcommand{\FT}[1]{\mathaccent{\u#1}}
\newcommand {\NL}{\nolimits}

\newcommand {\set}{{\mathcal{S}}}

\renewcommand \baselinestretch{1.4}


\let\FT=\ft
\begin{document}



\title[Minimax bounds for estimation of normal mixtures]{Minimax bounds for estimation of normal mixtures}%
\author{Arlene K. H. Kim}
\thanks{The research was supported in part by NSF Career Award DMS-0645676 and NSF FRG Grant DMS-0854975}
\address{
Statistical Laboratory\\
University of Cambridge\\
E-MAIL: A.Kim@statslab.cam.ac.uk
}
\date{\today}
\keywords{minimax lower bound, normal location mixture, Assouad's lemma, Hermite polynomials}

\begin{abstract}
This paper deals with minimax rates of convergence for estimation of density functions on the real line. The densities are assumed to be location mixtures of normals, a global regularity requirement that creates subtle difficulties for the application of standard minimax lower bound methods.
Using novel Fourier and Hermite polynomial techniques, we determine the minimax optimal rate---slightly larger than the parametric rate---under squared error loss.
For Hellinger loss, we provide a minimax lower bound using ideas modified from the squared error loss case.
%Minimax rates of convergence for the problem of estimation in nonparametric models are often determined by strategically chosen submodels that capture the difficulty of the whole problem. The submodels are constructed to have separation properties, such as those required by Assouad's lemma, while still satisfying the constraints of the model. For the estimation of submodels, even more constraints are imported, which can make the calculation of minimax rates substantially more difficult. This paper illustrates the difficulty for a density estimation problem by means of a normal location mixture model, which actually has the same minimax rates as for a larger family of analytic densities. The analysis exploits a stability property of a two-parameter family of functions under convolution with the standard normal followed by Fourier transformation.
\end{abstract}
\maketitle
\large
\section{Introduction} \label{intro}
This paper establishes the optimal minimax rate of convergence under squared error loss, for densities that are normal mixtures. The analysis reveals a subtle difficulty in the application of Assouad's Lemma to parameter spaces defined by indirect regularity conditions,  which complicate the usual construction of subsets of the parameter space indexed by `hyper-rectangles'.

More precisely, we consider independent observations from probability distributions~$P_f$ on the real line whose densities $f$ (with respect to Lebesgue measure on $\rr$) belong to the set of convolutions
\beqN
\FF = \left\{f: f(x)= \phi\star \Pi(x) = \int \phi(x-u) d\Pi(u), \Pi \in\PP(\rr) \right\}
\eeqN
where~$\phi$ denotes the standard normal N(0,1) density and~$\PP(\rr)$ denotes the set of all probability measures on the (Borel sigma-field of the) real line. 
Our main result gives an asymptotic minimax lower bound for the $L_2$ risk of estimators of $f \in \FF$.

\begin{theorem}\label{mainthm}
Let $X_1, \ldots, X_n$ be independent and identically distributed with density $f \in \FF$. 
Then there exists a positive constant~$c$ such that
\beqN
\sup_{f \in\FF}
\ee_{n,f} \int_{-\infty}^\infty\left(\hat f_n(x)-f(x)\right)^2dx
\ge c \cdot \log n \cdot \frac{1}{n\sqrt{\log n}}:=c\ell_n
%\qt{with $\ell_n =\dfrac{\sqrt{\log n}}{n}$}
\eeqN
for every estimator $\hat f_n = \hat f_n(X_1,\ldots, X_n)$.
\end{theorem}

Let $\FF_0$ denote the subset of $\FF$ consisting of those normal mixture densities whose mixing measure is absolutely continuous with respect to Lebesgue measure.
The proof of Theorem \ref{mainthm}, which is given in Section \ref{secoutline}, involves the construction of a finite subset of $\FF_0$, so the lower bound also holds when the supremum is taken over $f \in \FF_0$.
Perhaps the most interesting feature of this result is that the same rate has been obtained as an upper bound for the minimax risk with respect to squared error loss over much larger classes of functions.
For instance, \cite{ibragimov2001} defined the class $\FF^*$ consisting of those densities that can be extended to an entire function~$f^*$ on~$\mathbb{C}$ satisfying $\sup_{y \in \rr} e^{-y^2/2} \sup_{x \in \rr}|f^*(x+iy)| < \infty$.
%\begin{equation}\label{ibragimovset}
%\FF^* := \left\{ f \in \FF^{\text{\small{ent}}}:  \sup_{x} | f(x+iy)| \leq C\exp(|y|^2/2) \ \ \forall y \in \rr \right\},
%\end{equation}
%where $\FF^{\text{\small{ent}}}$ denotes the set of entire functions defined on $\mathbb{C}$ and $C$ is a cosntant.  
He proved the following:
\begin{theorem}[\cite{ibragimov2001}, Theorem 4.1]\label{ibragimovthm}
Let $X_1, \ldots, X_n$ be independent and identically distributed with density $f \in \FF^*$. 
Then there exists an estimator $\hat f_n = \hat f_n(X_1, \ldots, X_n)$ of $f$ such that
$$
\sup_{ f \in \FF^*} \ee_{n,f} \int_{-\infty}^\infty \left( \hat f_n(x)-f(x) \right)^2 dx = O(\ell_n).
$$
\end{theorem}
For the reader's convenience, in Section 3, we show that $\FF \subseteq \FF^*$ and summarize Ibragimov's proof.
%completeness, we provide a detailed proof of this result in Section 3.
Theorems \ref{mainthm} and \ref{ibragimovthm} together establish that the minimax optimal rate of estimation for squared $L_2$ loss is $\ell_n$ for any class of functions containing $\FF_0$ and contained in $\FF^*$.
In particular, this is the case for $\FF$.
%In particular, we show in Section 3 that $\FF \subseteq \FF^*$ so the minimax optimal rate of estimation over $\FF$ is $\ell_n$.
%As another example, \cite{efromovich2008} defined 
%$$
%\FF_1 = \FF_1(\gamma, Q) := \left\{ f: \frac{1}{\pi} \int_0^\infty | e^{\gamma t^2}h(t)|^2 dt \leq Q, \ h(t) = \int_{-\infty}^\infty f(x) e^{itx}dx  \right\}.
%$$
%We show in Section 3 that $\FF_0 \subseteq \FF_1$ provided $\gamma < 1/2$ and $Q>1/(2\sqrt{\pi(1-2\gamma)})$, so the minimax optimal rate of estimation over $\FF \cap \FF_1$ is $\ell_n$.
%This complements Theorem~5.2 in \cite{efromovich2008} who proved that the sharp minimax squared $L_2$ risk over $\FF_1$ is $\dfrac{\ell_n}{\pi\sqrt{2\gamma}}\{1+o(1)\}$.

While a minimax result under the $L_2$ loss presents the most successful case, this loss function is often criticized for giving too little weight to errors from the tails. 
As an alternative, we also consider the Hellinger loss.
Define a class of probability measures with sub-Gaussian tails,
$$
\PP_s(\rr) := \left\{ \Pi \in \PP(\rr): \exists \ C>0 \ \text{such that} \ \Pi(|u|>t) \leq C \exp(-t^2/C) \ \text{for all real} \ t\right\}.
$$
For the following class of normal location mixtures
$$
\FF_s := \left\{ f: f(x) = \phi \star \Pi (x)= \int \phi(x-u) d\Pi(u), \ \Pi \in \PP_s(\rr)  \right\},
$$ 
 \cite{ghosalvaart2001} provide a sieved maximum likelihood estimator whose convergence rate is $O((\log n)^2/n)$.
However, as they pointed out, the optimal rate for $\FF_s$ is still unknown.
% (to the best of my knowledge, there is no lower bound proof under the Hellinger loss) and here we provide one possible lower bound. 
Our technique gives a lower bound that lies within a logarithmic factor of Ghosal and van der Vaart's upper bound.

\begin{theorem}\label{mainthm2}
%Consider a class $\FF_s$ of normal location mixtures with mixing distributions having sub-Gaussian tails.
Let $X_1,\ldots,X_n$ be independent and identically distributed with density $f \in \FF_s$. Then there exists a positive constant~$c$ such that 
\beqN
\sup_{f \in \FF_s}
\ee_{n,f} \int_{-\infty}^\infty\left( \sqrt{\hat f_n(x)}- \sqrt{f(x)}\right)^2dx
\ge c \cdot \log n \cdot \frac{1}{n}
%\qt{with $\ell_n =\dfrac{\sqrt{\log n}}{n}$}
\eeqN
for every estimator $\hat f_n = \hat f_n(X_1, \ldots, X_n)$.
\end{theorem}
%It is interesting to note that even though $\FF_s$ is a subclass of $\FF$, the optimal minimax rate under Hellinger loss is slower than the optimal rate $\ell_n$ under $L_2$ loss.

%Not surprisingly, the proof use Fourier techniques
To prove Theorems 1.1 and 1.3, we use a variation on Assouad's Lemma (cf. \citealp[p.347]{vanassouad}).  
When specialized to  density estimation, the lemma can be cast into the following form. (Henceforth we omit the $\pm\infty$ terminals on the integrals when there is no ambiguity.) For completeness, we provide the proof in the appendix.

\begin{lemma}\label{assouadsim}
Let $\{ f_\alpha, \ \alpha \in  \{0,1\}^K\} \subseteq \FF$ where~$K$ is a finite index set of cardinality~$m$. Suppose $W$ is a nonnegative loss function for which there exists $\zeta>0$ such that, for all $g_1, g_2 \in \FF$, 
\beq\label{metricW}
\inf_{f \in \FF} W(f,g_1) + W(f,g_2) \geq \zeta W(g_1,g_2).
\eeq
Suppose also that for some constants~$c_0>0$ and~$1>c_1>0$, 
\beq
W(f_\alpha, f_\beta) \geq c_0 \epsilon^2 ||\alpha-\beta||_0 \ \ \text{for all} \ \ \alpha,  \beta \in \{0,1\}^K \label{cond1}
\eeq and
\beq \int  \frac{(f_\alpha-f_\beta)^2}{ f_\alpha} \leq \frac{c_1}{n}\ \ \text{if}\ \ ||\alpha-\beta||_0=1, \label{cond2}
\eeq
where $||\alpha-\beta||_0= \sum_{k \in K} \one\{ \alpha_k \neq \beta_k\}$, the Hamming distance.
Then, for every estimator $\hat f_n$ based on $n$ independent observations,
\beq\label{minimaxlower}
\sup_{f \in \FF} \ee_{n,f} W(\hat f_n, f) \geq \frac{c_0 \zeta}{4}(1-\sqrt{c_1}) m \epsilon^2.
%\qt{where $m = $ cardinality of~$K$},
\eeq
% with a constant $c = \frac{c_0}{8}(1-\sqrt{c_1})$. 
\end{lemma}
\begin{remark}
Assumption (\ref{cond2}) regarding the $\chi^2$ distance is merely a convenient way to show that the testing affinity, $||P_{f_\alpha}^n \wedge P_{f_\beta}^n||_1$, is at least~$1-\sqrt{c_1}$, where $P_{f}^n$ is a product probability measure under $f$ and $||P \wedge Q||_1$ is defined as $\int min(dP,dQ)$.
\end{remark}
\begin{remark}
To apply Lemma \ref{assouadsim}, we try to maximize $m\epsilon^2$ for the best possible lower bound. 
While we construct the finite density class satisfying the loss separation condition (\ref{cond1}), we need to restrict the size $\epsilon^2$ and $m$ so that two nearest densities should be reasonably close as in (\ref{cond2}), and so that the constructed densities are truly in the parameter space $\FF$. 
\end{remark}
For the proof in Section \ref{secoutline}, we construct~$f_\alpha$'s of the form
\beqN
f_\alpha(x) =f_0(x) + \epsilon \sum_{k\in K} \alpha_k \Delta_k(x), \ \ \alpha \in \{0,1\}^K
\eeqN
where $f_0$ is the normal density function with a zero mean (and variance specified later), where $K = \{1,3,\dots,2m-1\}$, and where $m$, $\epsilon >0$, and $\Delta_k$ could depend on~$n$.
The main difficulty lies in choosing the (signed) perturbations~$\Delta_k$ so that each~$f_\alpha$ is a normal location mixture. The natural way around this problem is to construct the Assouad hyper-rectangle in the space of mixing distributions,
\beqN
f_\alpha=\phi\star \Pi_\alpha
\qt{where }
\Pi_\alpha(u) = \Pi_0(u) + \epsilon \sum_{k\in K}\alpha_k V_k(u), \ \ \alpha \in \{0,1\}^K
\eeqN
where the signed measures~$V_k$ must be chosen so that each~$\Pi_\alpha$ is a probability measure. In contrast to the standard construction, the indirect form of $f_\alpha = \phi \star \Pi_\alpha$ leads to an embedding condition of the form
% Unfortunately, we then have only  indirect control over~$\Delta_k = \phi\star V_k$, which makes it difficult to achieve the two requirements of Lemma~\ref{assouadsim}.
%For example, for requirement~(2) it is desirable that the perturbations enjoy a ``near-orthogonality'' property:
\beq\label{nearortho}
W(\phi \star \Pi_\alpha, \phi\star \Pi_\beta) \geq \tau_n\sum_{k \in K} (\alpha_k-\beta_k)^2,
\eeq
for some $\tau_n$. 
The right side of (\ref{nearortho}) is expressed in terms of $\sum_{k\in K}(\alpha_k-\beta_k)^2$ instead of the Hamming distance, in order to emphasize the orthogonality relation.
If the convolution with the normal density were not present, such a property could be obtained by choosing the perturbations to be exactly orthogonal to each other, subject to various other regularity properties that define the parameter space. 
The smoothing effect of the convolution operation, however, makes it difficult to choose the $V_k$ to achieve such near-orthogonality.
 Nevertheless, we can achieve (\ref{nearortho}) by choosing the perturbations so that their Fourier transforms are orthogonal as elements in $L_2(\phi^2)$, the space of complex-valued functions $g$ such that $\int \phi(x)^2 |g(x)|^2 dx < \infty$ for the $L_2$ loss. Similarly, we achieve (\ref{nearortho}) under the Hellinger loss using the similar ideas under $L_2$ except that $\phi^2$ is replaced by a different weight function. %orthogonal perturbations are found by constructing suitable~$V_k$'s in Section \ref{secoutline}, which makes novel use of eigenfunction properties of operators defined by convolution followed by Fourier transformation.


\section{Proofs of the lower bounds}\label{secoutline}
First, we introduce some notation used in this section.
We let $\phi_{\sigma^2}$ be the normal density with mean zero and variance $\sigma^2$.
Following e.g. \citet[chap.~9]{rudin_real_complex}, we define the Fourier transform $\fourier$  by
\beqN
\fourier f(t) := \breve f(t) =\frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty  \exp(- i xt)  f(x)dx
\eeqN
 for $f \in \LL_1(\lambda)$ where $\lambda$ is Lebesgue measure, and then extend from $\LL_1 \cap \LL_2$ to $\LL_2$ by extending an isometry of $\LL_1 \cap \LL_2$ into $\LL_2$ to an isometry of $\LL_2$ onto $\LL_2$.

For both theorems, we construct the signed measures~$V_k$ to have (signed) densities~$v_k$ with respect to~$\lambda$:
\beq\label{formG}
\pi_\alpha(u) = \frac{d\Pi_\alpha}{d\lambda}(u)
= \pi_0(u)+ \epsilon \sum_{k\in K}\alpha_k v_k(u), \ \ \alpha \in \{0,1\}^K,
\eeq
where $\pi_0$ is the normal density with zero mean and each $v_k$ is a function for which~$\int v_k=0$ and
\beqN
\pi_0(u) +\epsilon \sum_{k\in K}\alpha_k v_k(u) \ge0
\qt{for all $u$}.
\eeqN
We then need to check the assumptions for Lemma~\ref{assouadsim}.

\subsection{Ideas in the proof of Theorem \ref{mainthm}}
Here we let $W(f,g) := ||f-g||_2^2 = \int (f-g)^2$, so (\ref{metricW}) is satisfied with $\zeta=1/2$.
The choice of the $v_k$'s is suggested by Fourier methods.
By  the Plancherel formula (and the fact that $\breve \phi=\phi$), recalling that $f_\alpha = \phi \star \Pi_\alpha$,
\begin{align*}
\frac{1}{2\pi}||f_\alpha-f_\beta||_2^2 &= \frac{1}{2\pi}|| \breve f_\alpha - \breve f_\beta||_2^2
= \epsilon^2 \int_{-\infty}^\infty \left|\sum_{k \in K}(\alpha_k-\beta_k)  \phi(t) \breve v_k (t) \right|^2 dt, 
\end{align*}
which lets us write the desired property (\ref{cond1}) of Lemma \ref{assouadsim} as
$$ %\beq\label{losscond}
 \int_{-\infty}^\infty \left|\sum_{k \in K}(\alpha_k-\beta_k)  \phi(t) \breve v_k (t) \right|^2 dt \geq \frac{c_0}{2\pi} \sum_{k \in K} (\alpha_k-\beta_k)^2, \ \text{$\forall$ $\alpha, \beta \in \{0,1\}^K$}.
$$ %\eeq
%where we use $||\alpha-\beta||_0 = \sum_{k \in K}(\alpha_k-\beta_k)^2$. 
We might achieve such an inequality by choosing the $v_k$'s to make the 
functions $\psi_k(t) := \phi(t)\breve v_k (t)$ orthogonal. Ignoring other requirements for the moment, we could even start from an orthonormal set~$\{\psi_k\}$ and then try to define~$v_k$ as the (inverse)
Fourier transform of $\psi_k(t)/\phi(t)$, provided that the ratio is square integrable. 
This heuristic succeeds if we start from the normalized orthogonal functions (see \citealp[chap.~9]{fourier_jackson}),
\beq\label{psi_k_choice}
\psi_k(t) =C i^{-k} \phi(t)^2 \frac{H_{k}(2t)}{\sqrt{k!}} 
= i^{-k} \sqrt{2\phi(2t)} \frac{H_{k}(2t)}{\sqrt{k!}}
\eeq
for $k\in K:= \{1,3,...,2m-1\}$,
where 
$C= \sqrt{2}(2\pi)^{3/4}$ is chosen so that~$C \phi(t)^2 = \sqrt{2\phi(2t)}$ 
and~$H_k(t)$ is the Hermite polynomial of order~$k$, 
the polynomial for which~$\phi(t)$ has $k^{th}$ derivative $(-1)^k H_k(t) \phi(t)$. 

\begin{remark}
$\{H_k, k=1,2,...\}$ is sometimes called the ``probabilists' Hermite Polynomials'' (denoted as `$He$' in \cite{table}), as opposed to the ``physicists' Hermite Polynomials'' $\mathbi{H}$. There is one-to-one relation between $H$ and $\mathbi{H}$, given by 
%where $\mathbi{H}$ is just written with a different scale,
$$
H_k(t)=2^{-k/2} \mathbi{H}_k \left(\frac{t}{\sqrt{2}}\right).
$$
\end{remark}
To calculate the Fourier inverse transform of $\psi_k(t)/\phi(t)$, we provide the following lemma.
\begin{lemma}\label{hermiteFT} For $b>a>0$,
\beq \fourier^{-1} \left[ \phi(a t) H_k(bt) \right](u)= Q_k \phi\left(\frac{u}{a}\right)H_k(b'u)
\eeq 
where $Q_k = \left(ic_{a,b} \right)^{k}/a$ with $c_{a,b} = \sqrt{b^2/a^2-1}$ and $b'= b/(a^2 c_{a,b})$.
\end{lemma} 
\begin{remark}
Lemma \ref{hermiteFT} illustrates a general form of the eigenvalue-eigenfunction relation for the Fourier transform of Hermite functions,
$$
\fourier [\phi(t) H_k(\sqrt{2}t)] (u) = (-i)^k \phi(u) H_k(\sqrt{2}u).
$$
(See (7.376) in \cite{table}, or for more details, see $\S 4.11$ in \cite{kawata}).
\end{remark}
We now formulate these arguments into a proof.
%\subsection{The loss condition (\ref{cond1}) in Lemma \ref{assouadsim}}
\begin{proof}[Proof of Theorem \ref{mainthm}]
By Lemma \ref{hermiteFT}, defining $\{\psi_k, k \in K\}$ as in (\ref{psi_k_choice}) leads to
\beq\label{G_k}
v_k(u) = C \sqrt{\frac{3^{k}}{k!}} \phi(u) H_{k} \left(\frac{2}{\sqrt{3}} u\right) \qt{for $k \in K$},
\eeq
because $\fourier^{-1}[\phi(t)H_k(2t)](u) =  i^k 3^{k/2}  \phi(u) H_{k}(2u/\sqrt{3})$.
By restricting to odd values of~$k$ we make the~$v_k$'s  real-valued and odd,  thereby ensuring that~$\int v_k d\lambda=0$ and $\int \pi_\alpha d\lambda=1$ for each~$\alpha$ in~$\{0,1\}^K$. 

In summary, the choice of~$v_k$ as in~(\ref{G_k}) gives
\begin{align}
\frac{1}{2\pi}||f_\alpha-f_\beta||_2^2 
&=\epsilon^2 \int_{-\infty}^\infty \left( \sum_{k \in K} (\alpha_k-\beta_k) \psi_k(t) \right)^2 dt 
=\epsilon^2 \sum_{k \in K} (\alpha_k-\beta_k)^2. 
\label{l2loss}
\end{align}
That is, the condition (\ref{cond1}) of Lemma \ref{assouadsim} is satisfied with $c_0=2\pi$.

We still need to check the condition (\ref{cond2}), and also show that~$\epsilon$ can be chosen small enough to make 
all the~$\pi_\alpha$'s nonnegative.
Actually, we first show that $\pi_\alpha \geq \pi_0/2 >0$ by choosing
%\subsection{Condition (\ref{cond2}) in Lemma \ref{assouadsim}}
%Considering the second condition in Lemma \ref{assouadsim}, we first show that the nonnegativity of $\pi_\alpha$ by choosing
\beq\label{halfg}
\epsilon \leq \frac{1}{16}3^{-m+1/2}m^{-3/2},
\eeq
and by choosing $\pi_0 = \phi_m$.
Secondly, we determine the largest size $m$ while the two densities $f_\alpha$ and $f_\beta$ are close in terms of the $\chi^2$ distance as $O(1/n)$ when there is only one different coordinate between $\alpha$ and $\beta$. 
%Recall that $G_\alpha(u) = G_0(u) + \epsilon \sum_{k \in K} \alpha_k G_k(u)$ defined in (\ref{G_alpha}). 

To control the denominator in (\ref{cond2}), we first show that $|v_k(u)| \leq C_k\sqrt{m} \pi_0(u)$ where $C_k = 8 \cdot 3^{k/2}$. 
By Cram$\acute{\text{e}}$r's inequality \cite[eqn. 8.954]{table}, 
\beq\label{cramer}
|H_k(u)| \leq \kappa \sqrt{k!} \exp(u^2/4) \ \ \text{with}\ \ \kappa \approx 1.086.
\eeq Applying this inequality to~(\ref{G_k}),
\begin{align} 
|v_k(u)| %&\leq C_k\phi(u) \exp\left( \frac{1}{3}u^2 \right)  \\
&\leq \kappa C3^{k/2}\frac{1}{\sqrt{2\pi}} \exp\left(-\frac{1}{6}u^2\right) \leq C_k \phi(u/\sqrt{3}) \label{bound1}\\
&\leq C_k\phi(u/\sqrt{m}) = C_k \sqrt{m} \pi_0(u). \label{bound2}
\end{align}
Using (\ref{bound2}), we have 
\begin{align*}
\pi_\alpha(u) = \pi_0(u) + \epsilon \sum_{k \in K} \alpha_k v_k(u)
&\geq \pi_0(u)- \epsilon \sum_{k \in K} C_k \sqrt{m} \pi_0(u)\\
&\geq \pi_0(u)\left[1- C_{2m-1} m^{3/2} \epsilon \right]\\
&=\pi_0(u)\left[1- 8 \cdot 3^{m-1/2}m^{3/2}\epsilon\right] \geq \frac{\pi_0(u)}{2}
\end{align*}
by the choice of~$\epsilon$ in (\ref{halfg}). 
%\beq\label{halfg}
%C_{2m-1} m^{3/2} = 8 \cdot 3^{m-1/2} m^{3/2} \leq \frac{1}{2\epsilon}.
%\eeq

Hence, under the condition (\ref{halfg}), $\phi \star \Pi_\alpha := f_{\alpha} \geq  f_0/2:= \phi \star \Pi_0/2$, which implies that the second condition in Lemma \ref{assouadsim} is rewritten as  $\int (f_\alpha-f_\beta)^2/f_0 \leq c_1/2n$ for $\alpha$ and $\beta$ having only one different coordinate. 
The denominator $f_0 = \phi \star \Pi_0$ is again normally distributed with mean zero and variance $1+m$ by the choice of $d\Pi_0/d\lambda:=\pi_0 = \phi_m$ density. 

For convenience, we let $\alpha_{1} \neq \beta_{1}$ (all the other cases work the same way). By splitting the integral into two regions $|x| \leq M\sqrt{m}$ and $|x| > M\sqrt{m}$ with a constant~$M^2 = 8\log 9$,
\begin{align*}
\int \frac{(f_{\alpha}-f_{\beta})^2}{f_{0}}&= \int_{|x| \leq M\sqrt{m}} \frac{(f_\alpha-f_\beta)^2}{f_0} + \epsilon^2 \int_{|x| > M\sqrt{m}} \frac{\left(\int\phi(x-u) v_{1}(u)d\lambda\right)^2 }{f_0}.
\end{align*}

For the first integral, the denominator is bounded below on the interval $\{|x| \leq M\sqrt{m}\}$, since 
$$f_0(x) \{ |x| \leq M\sqrt{m}\} > \exp(-M^2/2)/(2\sqrt{2\pi} \sqrt{m}) := 1/(C^\ast \sqrt{m})
$$ 
where $C^\ast := 2\sqrt{2\pi} \exp(M^2/2)$. Then, using the $\LL_2$ loss calculation from~(\ref{l2loss}), 
$$\int_{|x| \leq M\sqrt{m}} \frac{(f_{\alpha}(x)-f_{\beta}(x))^2}{f_{0}(x)} dx \leq C^\ast \sqrt{m} ||f_{\alpha}-f_{\beta}||_2^2 = 2\pi C^\ast\sqrt{m} \epsilon^2.$$
%where we upper bound the first term using the $\LL_2$ loss calculation after lower bounding the denominator.

For the second integral, recall that for any $k = 1,3,\ldots,2m-1$, we have 
$$
|v_{k}(u)| \leq C_{2m-1} \phi(u/\sqrt{3}) := C_{2m-1} \sigma_0 \phi_{\sigma_0^2}
$$ with $\sigma_0=\sqrt{3}$ as in~(\ref{bound1}). Using $C_{2m-1} := 8 \cdot 3^{m-1/2}$ and $\phi_{1+\sigma_0^2}(x) \leq \sqrt{m} \phi_{1+m}(x)$, with a notation $R(x) := \{|x|>M\sqrt{m}\}$, we bound the second integral:
	\begin{align*} 
 \epsilon^2 \int_{R(x)} \frac{\left(\int\phi(x-u) v_{1}(u)d\lambda\right)^2}{f_0(x)}dx 
	&\leq \epsilon^2C_{2m-1}^2 \sigma_0^2   \int_{R(x)} \frac{\left( \int \phi(x-u)\phi_{\sigma_0^2}(u)d\lambda\right)^2}{\phi_{1+m}(x)}dx\\
	&\leq  \sqrt{m}\epsilon^2 C_{2m-1}^2 \sigma_0^2   \int_{R(x)} \phi_{1+\sigma_0^2}(x) dx\\
	&=\left( \frac{64}{3} \sqrt{m} \epsilon^2\right) \left( 3^{2m}  \int_{R(x)} \phi_{1+\sigma_0^2}(x) dx\right)\\
        &\leq \frac{64}{3}\sqrt{m}\epsilon^2.
	\end{align*}
Here the last inequality is obtained by a Gaussian tail property with $\sqrt{m} \gg \sigma_0 := \sqrt{3}$, namely
$$
\int_{|x|>M\sqrt{m}} \phi_{1+\sigma_0^2}(x) dx\leq \exp\left(-\frac{1}{8} M^2m\right) =3^{-2m}
$$ since
$ M^2 = 8 \log 9$.

Combining these two upper bounds for the integral, we obtain
$$
\int \frac{(f_\alpha-f_\beta)^2}{f_0} \leq \sqrt{m} \epsilon^2 \left( 2\pi C^\ast + 64/3\right)= \frac{c_1}{2n}$$
as long as 
\beq\label{boundsigmam}
\sqrt{m} \epsilon^2 \leq \frac{1}{n}\frac{c_1}{ 2(2\pi C^\ast+64/3)}.\eeq
%where the first equality is followed by (\ref{halfg}).
% For further details, see Lemma \ref{chi2bound}.

As a consequence, the constructed mixing densities fulfil the two requirements in Assouad's lemma under conditions (\ref{halfg}) and (\ref{boundsigmam}), with 
%\begin{equation}\label{epsilonbound}
$$\epsilon^2 \leq \min\left(\frac{1}{16^2}3^{-2m+1}m^{-3}, \frac{1}{n\sqrt{m}} \frac{c_1}{2(2\pi C^\ast+64/3)} \right).
$$
%\end{equation}
  From Lemma \ref{assouadsim}, the lower bound is obtained as $c\epsilon^2 m$,
which is at most 
$$\min(3^{-2m}m^{-2}, \sqrt{m}/n)$$ up to a constant.
%\sigma_m^2\epsilon^2$ by (\ref{boundm}) with the choice of $m = O(\sigma_m^2)$, and a multiple of $(1/n) \sigma_m$ 
%by (\ref{boundsigmam}) with a choice of $1/\epsilon = O(\sqrt{n\sigma_m})$. 
To find the largest $m \epsilon^2$, by equating $3^{-2m}m^{-2} = \sqrt{m}/n$, we obtain $m$ and $\epsilon^2$ as $\log n$ and $1/(n\sqrt{\log n})$ respectively up to a constant, and hence the lower bound is obtained as $ \sqrt{\log  n}/n$ up to a constant.
\end{proof}

\subsection{Ideas in the proof of Theorem \ref{mainthm2}}
%We follow ideas used in the proof of \ref{mainthm}.
% the lower bound construction under the squared error loss.
Here we let $W(f,g) := ||\sqrt{f}-\sqrt{g}||_2^2 = \int (\sqrt{f}-\sqrt{g})^2$, so (\ref{metricW}) is satisfied with $\zeta = 1$.
%As we explain the choice of the perturbation functions in detail later, here we just provide main ideas.
First we relate the Hellinger distance and the $\chi^2$ distance.
That is, suppose we can show
$(1/2) \pi_0(u) \leq \pi_\varsigma(u) \leq (3/2) \pi_0(u)$ so that
$ (1/2)f_0(x) \leq f_\varsigma(x) \leq (3/2)f_0(x)$ for both $\varsigma=\alpha$ and $\varsigma = \beta$, by convolving with the standard normal density.
Then, using the upper bound for $f_\alpha$ and $f_\beta$, 
%for all $\alpha, \beta \in \{0,1\}^K$,
% we simplify the two conditions needed for Assouad's Lemma. Consider the following representations of the Hellinger loss,
\beq\label{uppertheta}
 \int \left( \sqrt{f_\alpha}-\sqrt{f_\beta}\right)^2
= \int \frac{(f_\alpha-f_\beta)^2}{(\sqrt{f_\alpha}+ \sqrt{f_\beta})^2}
\geq \frac{1}{6} \int \frac{(f_\alpha-f_\beta)^2}{f_0}. %\qt{for all $\alpha, \beta \in \{0,1\}^K$}.
\eeq

Similarly, the lower bound for $f_\alpha$ would give an upper bound for the testing condition
%By the lower bound for $\theta_\alpha \geq (1/2)\theta_0$,
\beq\label{lowertheta}
\int \frac{(f_\alpha-f_\beta)^2}{f_\alpha} \leq  2 \int \frac{(f_\alpha-f_\beta)^2}{f_0}.
 %, \qt{for $d(\alpha, \beta)=1$.}
\eeq
Thus it would be enough to work with the following quantity 
$$
\int \frac{(f_\alpha-f_\beta)^2}{f_0} = \int \left( \frac{f_\alpha}{\sqrt{f_0}} -\frac{f_\beta}{\sqrt{f_0}}\right)^2 = \epsilon^2
\int \left( \sum_{k \in K} (\alpha_k-\beta_k) \frac{\phi \star v_k}{\sqrt{f_0}}   \right)^2,
$$
where the second equality is given by (\ref{formG}).

At first glance, $\int (f_\alpha-f_\beta)^2/f_0$ does not look  amenable to Fourier techniques.
However, as Lemma \ref{absorb_g0} below shows, $\phi \star v_k/\sqrt{f_0}$ is expressed as convolution of a normal density (with a variance larger than $1$) with a certain choice of the perturbation function $v_k$ and base function $\pi_0 = \phi_{\sigma^2}$.

\begin{lemma}\label{absorb_g0}
Consider the perturbation functions 
$$v_k(u)= \frac{C_k}{\sqrt{k!}} \phi(\rho u) H_k(\gamma u), \ \ \rho^2 \geq \frac{1}{\sigma^2}+\frac{\gamma^2}{2},$$
where $C_k$ is a constant depending on $k$ and $\gamma>0$.
% $\rho$ satisfying the condition (\ref{cond_halfg_H}).
Then
\beq\label{tilde_convol}
\frac{[\phi \star v_k](x)}{\sqrt{\phi \star \phi_{\sigma^2}(x)}} 
%= \frac{\tilde C_k}{\sqrt{k!}}[\phi_{\tilde \sigma^2} \star \phi(\tilde \lambda u) H_k (\tilde \gamma u)](x) :
= \phi_{\tilde \sigma^2} \star \tilde v_k 
\eeq
where 
\beq\label{tilde_v_k}
\tilde v_k(u) :=\frac{\tilde C_k}{\sqrt{k!}} \phi(\tilde \rho u) H_k (\tilde \gamma u),
\eeq
with
\beq\label{tilde_def}
\tilde \sigma^2 = 1+ \frac{1}{2\sigma^2+1}, \ \tilde C_k = C_k  \frac{ (4\pi)^{1/4} }{\tilde \sigma } , \ \tilde \rho = \frac{\sqrt{\rho^2+1-\tilde \sigma^2}}{\tilde \sigma^2}, \ \tilde \gamma = \frac{\gamma}{\tilde \sigma^2}.
\eeq
\end{lemma}

By Lemma \ref{absorb_g0}, the denominator effect can be incorporated into the normal convolution.
Then we follow similar ideas used in the proof of Theorem \ref{mainthm}.


%The following Lemma \ref{lemma_halfg_H} provides convenient conditions for bounding the constructed mixing densities $\pi_\alpha(u)$.
%\begin{lemma}\label{lemma_halfg_H}
%Let $\pi_0(u)$ be the $N(0,1)$ density $\phi(u)$ and $v_k$ be as in (\ref{perturb_H}). 
%If 
%\beq\label{cond_halfg_H}
%\epsilon = \frac{1}{2\kappa mC_{2m-1}} \qt{with $\kappa \simeq 1.086$},
%\eeq
%then 
%\beq\notag %\label{bounds_g_alpha}
%\frac{1}{2}\pi_0(u) \leq \pi_\alpha(u) \leq \frac{3}{2}\pi_0(u) \qt{for all $u \in \rr, \ \alpha \in \{0,1\}^K$}.
%\eeq
%\end{lemma}



%Then, we shall calculate the quantity 
\begin{proof}[Proof of Theorem \ref{mainthm2}]
Again, the choice of $v_k$'s is suggested by Fourier methods.
For convenience, we let $\pi_0 = \phi$, so $f_0 = \phi_{2}$ and  $\sqrt{f_0} = 2 \pi^{1/4} \phi_{4}$. 
Assuming $\tilde v_k$ in (\ref{tilde_v_k}) are in $\LL_2$,
\begin{align*}
\fourier \left[\frac{f_\alpha}{\sqrt{f_0}}\right](t) 
&=\fourier \left[ \sqrt{f_0}\right](t) + \epsilon \sum_{k \in K} \alpha_k \fourier \left[ \frac{\phi \star v_k}{\sqrt{f_0}}\right](t) \\
&= \fourier [ \sqrt{f_0}](t) + \epsilon \sum_{k \in K} \alpha_k \fourier \phi_{\frac{4}{3}}(t) \fourier \tilde v_k (t)
\end{align*}
by Lemma \ref{absorb_g0}.

By the Plancherel formula,
\begin{align*}
\frac{1}{2\pi} \left\Vert\frac{f_\alpha}{\sqrt{f_0}} - \frac{f_\beta}{\sqrt{f_0}} \right\Vert_2 
%&= \frac{1}{2\pi} || \fourier \left[\frac{f_\alpha}{\sqrt{f_0}}\right]- \fourier \left[\frac{f_\beta}{\sqrt{f_0}}\right]||_2^2 \\
& = \epsilon^2 \int \left| \sum_{k \in K} (\alpha_k-\beta_k) \fourier \phi_{\frac{4}{3}}(t) \fourier [\tilde v_k] (t)  \right|^2 dt,
\end{align*}
which lets us write the condition (\ref{cond1}) in Assouad's Lemma \ref{assouadsim} as
$$
\int \left| \sum_{k \in K} (\alpha_k-\beta_k) \fourier [\phi_{\frac{4}{3}}](t) \fourier [\tilde v_k] (t)  \right|^2 dt \geq \frac{3c_0}{\pi} \sum_{k \in K}(\alpha_k-\beta_k)^2, \forall \alpha, \beta \in \{0,1\}^K,
$$
with $\delta =\pi c_0 \epsilon^2/3$ by (\ref{uppertheta}).
%Then if we can also show the testing condition, the lower bound is obtained as $m\delta \sim m\epsilon^2$ up to a constant.

Similar to the case for squared error loss, we might achieve even an equality with $c_0=\pi/3$ by choosing $\tilde v_k$'s to make the functions $\psi_k(t) := \fourier [\phi_{\frac{4}{3}}](t) \fourier 
[\tilde v_k] (t) $ orthonormal.
Ignoring other requirements, we also start from the same orthonormal set (\ref{psi_k_choice}),
%$$
%\psi_k(t) = i^{-k} \sqrt{2\phi(2t)} \frac{H_k(2t)}{\sqrt{k!}} \qt{for $k \in K:= \{1,3,...,2m-1\}$,}
%$$
 and then try to define $\tilde v_k$ as the inverse Fourier transform.

From the fact that
$$\fourier [\phi_{\frac{4}{3}}](t) = \frac{1}{\sqrt{2\pi}} \exp(-\frac{2}{3} t^2)
$$
and by definition of $\tilde v_k$ in (\ref{tilde_v_k}),
the requirement is that
%\begin{align*}
%\int \frac{(\theta_\alpha-\theta_\beta)^2}{\theta_0} &=\epsilon^2 \int \left( \sum\NL_{k \in K} h_k\frac{ \phi \star v_k }{\sqrt{\phi_{1+\sigma^2}}}\right)^2 \\
%&=\epsilon^2 \int \left( \sum\NL_{k \in K} \frac{h_k\tilde C_k}{\sqrt{k!}} [\phi_{\tilde \sigma^2} \star \phi(\tilde \lambda u) H_k(\tilde \gamma u)](x) \right)^2 dx \ \ \text{by Lemma \ref{absorb_g0}}\\
%&=\epsilon^2 \int \left( \sum\NL_{k \in \MM} \frac{h_k\tilde C_k}{\sqrt{2\pi k!}} \exp(-\frac{\tilde \sigma^2 t^2}{2}) \fourier [ \phi(\tilde \lambda u) H_k(\tilde \gamma u)](t) \right)^2 dt \ \ \text{by Plancherel}\\
%&:= \epsilon^2 \int \left( \sum\NL_{k \in \MM} (\alpha_k-\beta_k) \varphi_k(t) \right)^2 dt \qt{by defining $\varphi_k(t)$ correspondingly}.
%\end{align*}
%Following the strategy in Chapter \ref{L2chap}, we start with the orthonormal polynomials to prove the exact calculation.
%For instance, if we let
\beq\label{setting_ortho}
\psi_k(t) := \frac{\tilde C_k}{\sqrt{2\pi k!}} \exp(-\frac{2 t^2}{3}) \fourier [ \phi(\tilde \rho u) H_k(\tilde \gamma u)](t)
= 
i^{-k} \sqrt{2\phi(2t)} \frac{H_k(2t)}{\sqrt{k!}}.
\eeq
If we determine all the parameters to make (\ref{setting_ortho}) true, we have the desired property for the loss separation condition (\ref{cond1}), i.e. we have
\beq\label{hellingerL2}
\int \frac{(f_\alpha-f_\beta)^2}{f_0} =2\pi \epsilon^2 \sum_{k \in K} (\alpha_k-\beta_k)^2.
\eeq
%which leads to the choice of $\epsilon^2 \sim 1/n$ considering the $\chi^2$ testing condition.
We have to find $\tilde \rho$, $\tilde \gamma$ and $\tilde C_k$ so that (\ref{setting_ortho}) is satisfied. 
The solutions are derived below and given in (\ref{tilde_sol}).  
%and $\tilde C_k$ are found satisfying (\ref{setting_ortho}).

After some calculations, 
$$
\fourier [ \phi(\tilde \rho u) H_k(\tilde \gamma u)](t)
=
i^{-k} \frac{\sqrt{2}(2\pi)^{3/4}}{\tilde C_k} \phi\left( t\sqrt{\frac{2}{3}}\right) H_k(2t),
$$
which leads to
$$
\fourier^{-1} \left[ \phi\left(t\sqrt{\frac{2}{3}}\right) H_k(2t)\right](u)
=
i^{k}\frac{\tilde C_k}{\sqrt{2}(2\pi)^{3/4}} \phi(\tilde \rho u) H_k(\tilde \gamma u).
$$
% Recall Lemma \ref{hermiteFT}, i.e. for $b>a>0$,
% $$
% \fourier^{-1}[\phi(at)H_k(bt)](u) = \frac{(ic_{a,b})^k}{a} \phi(\frac{u}{a})H_k(\frac{bu}{a^2c_{a,b}}), \ \ c_{a,b} = \sqrt{\frac{b^2}{a^2}-1}.
% $$
Substituting $a=\sqrt{2/3}$ and $b=2$ into Lemma \ref{hermiteFT},
we have the following solutions,
\beq\label{tilde_sol}
%\tilde C_k = \frac{\sqrt{2}(2\pi)^{3/4}}{\sqrt{2-\tilde \sigma^2}} \left(\frac{2+\tilde \sigma^2}{2-\tilde \sigma^2}\right)^{k/2}, \tilde \rho = \frac{1}{\sqrt{2-\tilde \sigma^2}}, \ \tilde \gamma = \frac{2}{(2-\tilde \sigma^2)} \sqrt{\frac{2-\tilde \sigma^2}{2+\tilde \sigma^2}}
\tilde C_k = (2\pi)^{3/4}\sqrt{3}\sqrt{5^k}, \ \tilde \rho = \sqrt{\frac{3}{2}}, \ \tilde \gamma = \frac{3}{\sqrt{5}} .
\eeq

We need to ensure that the choice of $\sigma^2 =1$ satisfies the inequality $\rho^2 \geq \frac{1}{\sigma^2} + \frac{\gamma^2}{2}$ needed for the Lemma \ref{absorb_g0}.
%there exists $\tilde \sigma^2$ such that the first inequality in (\ref{cond_halfg_H}) is satisfied.
%Then we would guarantee that $g_\alpha$ satisfies the nonnegativity condition as well.
%In addition, the largest $m$ should be chosen to satisfy the second inequality in (\ref{cond_halfg_H}).
Comparing (\ref{tilde_def}) and (\ref{tilde_sol}), we obtain
%\beq\label{tilde_sol2}
$\rho^2 = 3$ and $\gamma = \frac{4}{\sqrt{5}}$, which satisfy the condition.
%\eeq
%The first inequality (\ref{cond_halfg_H}) can be written as
%\beq\label{cond2_halfg_H}
%\rho^2 = \frac{1}{1+2\sigma^2} + \frac{\tilde \sigma^4}{2-\tilde \sigma^2} 
%\geq \frac{1}{\sigma^2} +  \left( \frac{2}{2+\tilde \sigma^2}\right) \frac{\tilde \sigma^4}{2-\tilde \sigma^2}= \frac{1}{\sigma^2} + \frac{1}{2}\gamma^2,
%\eeq
%which is true for $\sigma^2$ not close to zero; large $\sigma^2$ means that $\tilde \sigma^2 := 1+ \dfrac{1}{1+2\sigma^2}$ is close to 1 so that the multiplication factor in the right side $2/(2+\tilde \sigma^2)$ makes the right side being smaller than the left side.
%(If $\sigma \rightarrow 0$, then the first term in the right side would dominate the left side.)
% the second term in the left side dominates other terms.
%For instance, with the choice of $\sigma^2 = 1$, we have
%$$\tilde \sigma^2 = \frac{4}{3}, \ \ \rho^2 = 3, \ \ \gamma^2 = \frac{16}{5} = 3.2,
%$$
%which satisfies the inequality (\ref{cond2_halfg_H}).
Also, $C_k$ is obtained as $C_k = (2^{5/4} \sqrt{\pi})\sqrt{5}^k$.
 %$C_k = (\pi/20)^{1/4} \sqrt{10/9} (29/9)^{k/2}$.

Therefore, this choice for the $\psi_k$'s leads to
\beq\label{choice2}
v_k(u) = 2^{5/4}\sqrt{\pi}\sqrt{\frac{5^k}{k!}} \phi (\sqrt{3} u) H_k \left( \frac{4}{\sqrt{5}} u\right) \qt{for $k \in K$}.
%v_k(u) = \left(\frac{\pi}{20}\right)^{1/4} \sqrt{\frac{10}{9}} \sqrt{\frac{(29/9)^k}{k!}} \phi( \sqrt{\frac{209}{171}}u) H_k( \frac{20}{9}\sqrt{\frac{19}{58}}).
\eeq
By restricting to odd values of $k$, we make the $v_k$'s real-valued and odd, thereby ensuring that $\int v_k d\lambda = 0$. 

Using exactly the same idea as in the previous section, if 
\beq\label{cond_halfg_H}
\epsilon \leq \frac{1}{2\kappa mC_{2m-1}} \qt{with $\kappa \simeq 1.086$},
\eeq
then 
\beq\notag %\label{bounds_g_alpha}
\frac{1}{2}\pi_0(u) \leq \pi_\alpha(u) \leq \frac{3}{2}\pi_0(u) \qt{for all $u \in \rr, \ \alpha \in \{0,1\}^K$}.
\eeq

Now the second testing condition can be treated straightforwardly.
Indeed, once we choose orthonormal functions $\{\psi_k, k \in K\}$, we obtain
$$\int \frac{(f_\alpha-f_\beta)^2}{f_\alpha} \leq \int 2\frac{(f_\alpha-f_\beta)^2}{f_0}= 4\pi \epsilon^2 \qt{for $||\alpha-\beta||_0=1$ by (\ref{lowertheta}) and (\ref{hellingerL2})}.
$$
%for $d(\alpha, \beta)=1$ by (\ref{hellingerL2}).
Thus it is enough to choose $\epsilon^2 < 1/(4\pi n)$.
With our choice $\epsilon = 1/(4\sqrt{n})$, the testing condition is satisfied.
% we need a condition like $c_2 < 1/(2\sqrt{\pi})$.
%Choose $c_2 = 1/4$.

From the lower bound $m\epsilon^2$, we want to choose $m$ as large as possible.
The condition in (\ref{cond_halfg_H}) restricts the size of $m$,
$$
2\kappa mC_{2m-1} <6m 5^m \leq 4\sqrt{n}.
$$
Thus, we have the upper bound for $m$,  
$$m \lesssim (1/(2\log 5)) \log n \simeq (0.31) \log n.$$

Finally, we check these constructed $\pi_\alpha$'s are inside of the parameter space $\PP_s(\rr)$
From the fact that $\pi_\alpha(u) \leq (3/2)\pi_0(u)$ for all $u \in \rr$ and $\alpha \in \{0,1\}^K$,
it is clear that $\pi_0$ is in the space $\PP_s(\rr)$ from the tail property of normal density.
%, i.e. we know that $\int_{|u|>t} \phi_{\sigma^2}(u)du \leq \exp(-\frac{t^2}{2\sigma^2})
%$.
%$ \exp(\frac{1}{2}t^2 \sigma^2 )= \exp(\frac{9}{2}t^2)$.
%This implies that 
%$$
%\int_{|u|>t} g_\alpha(u) du \leq \frac{3}{2} \exp\left(-\frac{1}{2} t^2\right) \qt{for all $\alpha$ and $t \in \rr$.}
%$$

Consequently, the lower bound is obtained as $\log n/n$ up to a constant.
\end{proof}
%\section{Lemmas for Section \ref{secoutline}}\label{secproof}
%
%\begin{remark}
%Lemma \ref{hermiteFT} is a general form of the eigenvalue eigenfunction relation of the Fourier transform. For instance, $a=1, b=\sqrt{2}$ gives the following fact $$\ft[\phi(t) H_k(\sqrt{2}t)] (u) =i^k \phi(u) H_k(\sqrt{2}u).$$ That is, eigenvalues of the Fourier transform are $i^k$.  (See (7.376) in \cite{table}, or for more details, see $\S 4.11$ in \cite{kawata}).
%\end{remark}

\section{Proof of the upper bound}\label{upperbound}
%As we discuss in Section \ref{intro}, we check the optimality of the rate from the lower bound under the $L_2$ loss. 
For the reader's convenience, we summarize the arguments for Theorem \ref{ibragimovthm}, following pages 365--369 by \cite{ibragimov2001}.
Before turning to that result, we first show that if $f = \phi \star \Pi \in \FF$, then $f$ can be extended to an entire function $f^*$. 
To see this, we let $f^*(x+iy) =\frac{1}{\sqrt{2\pi}} \int \exp\left(-(x+iy-u)^2)/2\right)d\Pi(u)$. Defining $a(x,y,u) \equiv y(u-x), \ b(x,y,u) \equiv-\frac{1}{2}\left\{(x-u)^2-y^2\right\}$, we write 
\begin{align*}
\sqrt{2\pi}f^*(x+iy)&=\int \left[ \left\{\cos a\left(x,y,u\right) + i \sin a\left( x,y,u\right)\right\} e^{b(x,y,u)} \right]d\Pi(u) \\
&= \int \left\{ \cos a\left(x,y,u\right)e^{b(x,y,u)} \right\} d\Pi(u) + i  \int \left\{\sin a\left(x,y,u\right)e^{b(x,y,u)}\right\} d\Pi(u) \\
&:= v(x,y) + iw(x,y).
\end{align*}
By differentiating under the integral (see Theorem 16.8 in \cite{billingsley}),
\begin{align*}
\frac{\partial v}{\partial x}  &=\int \left[ \left\{ y \sin a(x,y,u)+ (u-x)\cos a(x,y,u)\right\} e^{b(x,y,u)}\right] d\Pi(u) = \frac{\partial w}{\partial y}\\
\frac{\partial v}{\partial y}  &=
\int \left[\left\{ y\cos a(x,y,u)-(u-x)\sin a(x,y,u) \right\} e^{b(x,y,u)} \right] d\Pi(u)= -\frac{\partial w}{\partial x}.
\end{align*}
Also note that $\partial v/\partial x,\partial v/\partial y, \partial w/\partial x,$ and $\partial w/\partial y$ are continuous. Then by Cauchy--Riemann Theorem (see Theorem 1.5.8 in \cite{marsden1999}), $f^*$ is analytic.

Now it suffices to show that $f^*$ satisfies the growth condition. 
Indeed,
%\subsection{Entire function class}
%First, we show that $\FF \subseteq \FF^*$. Let $f \in \FF$.
\begin{align}
\sup_{x} \left|f^*(x+iy)\right| &= \sup_x \left| \frac{1}{\sqrt{2\pi}}\int \exp\left( -\frac{(x+iy-u)^2}{2}  \right) d\Pi(u)  \right|
\nonumber \\
&\leq \frac{1}{\sqrt{2\pi}} \sup_x\int  \left|  \exp\left( -\frac{(x+iy-u)^2}{2}  \right)  \right| d\Pi(u) \nonumber\\
%&=\frac{1}{\sqrt{2\pi}} \sup_x\int  \left| \exp \left( -\frac{(x-u)^2}{2}\right) \exp \left( \frac{y^2}{2} \right)   \right| d\Pi(u) \nonumber\\
&\leq \frac{1}{\sqrt{2\pi}} \exp \left( \frac{y^2}{2}\right) \sup_x \int d\Pi(u) =\frac{1}{\sqrt{2\pi}} \exp\left( \frac{y^2}{2}\right). \label{analyticcond}
\end{align}
Thus, $\FF \subseteq \FF^*$, which ensures that Ibragimov's estimation also gives the upper bound to match Theorem \ref{mainthm}. 

%We summarize the upper bound proof (on pages 365-369 in Ibragimov's paper).
\begin{proof}[Proof of Theorem \ref{ibragimovthm}]
Ibragimov used a \textit{sinc} kernel estimator,
$$ 
\hat f_n(x)= \frac{1}{nh} \sum_{j=1}^n \KK \left( \frac{X_j-x}{h}\right), \  \KK(u) = \frac{\sin (u)}{\pi u},
$$
with $h = 1/\sqrt{\log n}$.
%with observations $X_1,\ldots,X_n$ from a density $f = \phi \star \Pi$ where $d\Pi/d\lambda := \pi \in \LL_1$.
It is important for his method that the Fourier transform of $\KK$ is $\breve \KK(t) =\frac{1}{\sqrt{2\pi}} \one\{|t|\leq 1\}$ and also $\breve \KK^2(t) =\frac{1}{\sqrt{2\pi}} \frac{1}{\pi} \left(1-\frac{|t|}{2}\right)_{+}$ where $x_{+} = \max(x,0)$.

The expected mean integrated squared error (MISE) has the usual squared bias and variance decomposition.
As usual, the variance term is bounded by $(nh)^{-1} \int \KK^2(u)du$.
For the bias term, note that $\ee_{n,f} \hat f$ has the Fourier transform $\sqrt{2\pi} \breve f(t) \breve \KK(ht)$, so that
\begin{align*}
\text{bias}^2 := \int \left(\ee_{n,f}\hat f_n - f \right)^2 
&=  \int \left| \fourier [\ee_{n,f} \hat f_n](t) - \fourier [f](t)   \right|^2 dt \ \ \text{by Plancherel} \\
&= \int \left| \breve f(t) \right|^2 \left|\sqrt{2\pi} \breve \KK(ht) - 1 \right|^2 dt \\
&= \int_{|t| \geq 1/h} \left| \breve f(t) \right|^2 dt \ \ \text{by the form of} \ \breve \KK \\
&\leq 2 e^{-y/h} \int e^{-yt} \left|\breve f(t)\right|^2 dt \ \ \text{for } y>0 \\
&=2 e^{-y/h} \lim_{M \rightarrow \infty} \int e^{-yt} \left| \breve f(t) \right|^2 \left(1-\frac{|t|}{M} \right)_{+} dt.
\end{align*}
Write the last integral as
\begin{align*}
\int e^{-yt} \left| \breve f(t) \right|^2 \left( 1-\frac{|t|}{M} \right)_{+}dt &= \int \breve f(t) e^{-yt} \overline{\breve \vartheta(t)}dt = \int \breve f(t) e^{-yt}\breve \vartheta(-t) dt 
%&= \int \breve f(t) \breve \vartheta (t+iy) dt
\end{align*}
where $\breve \vartheta(t) =\breve f(t) \left(1-\frac{|t|}{M} \right)_{+}$ is the Fourier transform of the nonnegative function $\vartheta(x) = \frac{M\pi^2}{\sqrt{2\pi}} \int f(u) \KK^2\left(\frac{M}{2}(x-u) \right) du$.
Using $\vartheta(x+iy) = \frac{1}{\sqrt{2\pi}} \int e^{itx}e^{-yt}\breve \vartheta(t)dt$, we have $\int f(x) \vartheta(x+iy)dx = \int \breve f(t) e^{yt}\breve \vartheta(-t)dt$ by Parseval's theorem.
By changing the contour of the integration, $\int f(x+iy) \vartheta(x) dx = \int \breve f(t) e^{-yt}\breve \vartheta(-t)dt$. 
Combining these ideas, 
$$
\int \breve f(t) e^{-yt}\vartheta(-t)dt = \int f(x+iy) \vartheta(x)dx \leq \int \sup_x \left| f(x+iy) \right| \vartheta(x) dx \leq \frac{\exp(y^2/2)}{\sqrt{2\pi}},
$$ where the last inequality follows by (\ref{analyticcond}) together with $\int \vartheta(x)dx = \sqrt{2\pi}\breve \vartheta(0)=1$.
By taking $y = 1/h$, we obtain the upper bound as $\sqrt{\log  n}/n := \ell_n$ up to a constant.
%The right hand side is minimized by choosing $y=T$, so that
%$$
%\int \left(  \ee_{n,f} \hat f_n(x) - f(x) \right)^2 dx \leq \frac{2}{\sqrt{2\pi}}\exp\left(-\frac{T^2}{2}\right)= \frac{2}{\sqrt{2\pi}}\exp\left(-\frac{1}{2h^2}\right),
%$$
%where the last equality is by definition of $h = 1/T$.
%Thus the final upper bound is obtained as $1/(nh) + \exp(-1/(2h^2))$ up to a constant. 
%By choosing $h^2 \sim 1/\log n$, we have the upper bound as $\sqrt{\log n}/n := \ell_n$. 
\end{proof}
%\begin{remark}
% If we only consider a class of mixing densities which are square integrable with respect to $\lambda$, we obtain the same upper bound using a sinc kernel estimator with much shorter proof. 
%For the normal location mixture
%\end{remark}

%\subsection{Infinitely differentiable densities}
%In this subsection, we claim that $\FF_0 \subseteq \FF_1(\gamma, Q)$ when $\gamma<1/2$ and $Q>\sqrt{\pi/(1-2\gamma)}$.
%By using our definition of the Fourier transform, we can rewrite the condition for $\FF_1$ as $\int_{-\infty}^\infty \left| \exp(\gamma t^2) \breve f(-t) \right|^2 dt \leq Q$.
%From $\breve f(t) =\sqrt{2\pi} \phi(t) \breve \pi(t)$ for $f \in \FF_0$ and the fact \cite[Thm 9.6]{rudin_real_complex} that $||\breve \pi||_\infty \leq (1/\sqrt{2\pi})||\pi||_1 = 1/\sqrt{2\pi}$, with $\gamma<1/2$, we have
%$$
%\int_{-\infty}^\infty \left| \exp(\gamma t^2) \breve f(-t) \right|^2 \leq \frac{1}{2\pi} \int_{-\infty}^\infty \exp(-(1-2\gamma)t^2)dt =\frac{1}{ 2\sqrt{\pi(1-2\gamma)}}. 
%$$
%%as long as $\gamma < 1/2$.
%Thus, assuming a large constant $Q > 1/(2\sqrt{\pi(1-2\gamma)})$ with $\gamma<1/2$, $\FF_0 \subseteq \FF_1$.

% Now, in order to avoid the case where the constructed normal mixtures $\{f_\alpha, \alpha \in \{0,1\}^K\}$ is included in $\FF_1(\gamma,Q)$ with $\gamma \rightarrow 0$ (or $Q \rightarrow \infty$), we show that the constructed finite class of normal mixtures does not require too small $\gamma$. 
% %, we claim that $f_\alpha \in \FF_1$.
% By definition of $f_\alpha$,
% \begin{align*}
% \breve f_\alpha(-t) := \frac{1}{\sqrt{2\pi}}\int f_\alpha(x) e^{itx}dx &= \frac{1}{\sqrt{2\pi}} \int \left( \phi \star \left[ \phi_m + \epsilon \sum_{k \in K} \alpha_k v_k \right] \right) e^{itx} dx \\
% &= \frac{1}{\sqrt{2\pi}}\int \left[ \phi_{m+1}(x) + \epsilon \sum_{k \in K} \alpha_k ( \phi \star v_k) (x)\right]e^{itx}dx \\
% &= \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{m+1}{2}t^2\right) + \epsilon \sum_{k \in K} \alpha_k \phi(t) \breve v_k(-t)
% \end{align*}
% where $\phi(t) \breve v_k(-t) = i^{-k} \sqrt{2 \phi(2t)} H_k(-2t)/\sqrt{k!} = -\phi(t) \breve v_k(t)$ (from the odd property of $H_{k}$ with odd $k$) chosen as orthogonal functions in (\ref{psi_k_choice}).
% %Since it suffices to show $\int_{-\infty}^\infty \left| \exp(\gamma t^2) \breve f_\alpha(-t) \right|^2 dt \leq Q$ with some positive constants $\gamma$ and $Q$, 
% %For simplicity, we try with $\gamma =1/4$.
% %Using $\int |f+g|^2 \leq 2\int |f|^2 + 2\int |g|^2$,
% %Plugging this in the condition,
% Thus
% \begin{align*}
% \int \left| e^{\gamma t^2} \breve f_\alpha(t) \right|^2 dt &\leq \frac{1}{\pi} \int \left|\exp \left(-(\frac{m+1}{2}-\gamma)t^2 \right) \right|^2 dt + 2 m \epsilon^2 \int \left| \exp(\gamma t^2) \phi(t) \breve v_{2m+1}(t)  \right|^2 \\
% &=\sqrt{\frac{1}{\pi (m+1-2\gamma)}} + 2m\epsilon^2 \sqrt{\frac{2}{\pi}} \int   \exp(-2(1-\gamma)t^2) \frac{|H_{2m+1}(2t)|^2}{(2m+1)!}  dt \\
% &= \sqrt{\frac{1}{\pi (m+1-2\gamma)}}  + I.
% %&\leq 2\int_0^\infty \left| \exp\left( (\gamma t^2-\frac{m+1}{2})t^2 \right)\right|^2 + \left| m\exp(\gamma t^2) \phi(t) \breve v_k(t) \right|^2 dt
% \end{align*}
% To bound $I$, we use the following inequality \cite[eqn. 8.954]{table}
% $$
% |H_{2m+1}(t)| \leq 2^{-2m} \frac{(2m+1)!}{m!} \exp(t\sqrt{2m}).
% $$
% Using $(2m+1)!/(m!m!) \leq (2m+1)2^m$, we have
% \begin{align*}
% I \leq \sqrt{\frac{8}{\pi}} m\epsilon^2& 2^{-4m} \frac{(2m+1)!}{m!^2} \int \exp(-2(1-\gamma)t^2+(2\sqrt{2m})t) dt  \\
% &\leq \sqrt{\frac{8}{\pi}} m(2m+1)\epsilon^2 2^{-3m} \sqrt{\frac{\pi}{2(1-\gamma)}} \exp\left(\frac{m}{1-\gamma}\right) \\
% &\leq 2m(2m+1)(\frac{1}{16^2}3^{-2m+1}m^{-3}) 2^{-3m}\sqrt{\frac{1}{1-\gamma}}\exp\left(\frac{m}{1-\gamma}\right) \ \ \text{by  (\ref{halfg})}\\
% &\leq \frac{1}{16m}\sqrt{\frac{1}{1-\gamma}}\left(\frac{1}{72}\right)^m\exp\left(\frac{m}{1-\gamma}\right)
% \leq \frac{1}{16}\sqrt{\frac{1}{1-\gamma}}
% \end{align*}
% when we choose $\gamma \leq 1-1/\log(72) \sim 0.766$.
% %which can be bounded by some constant, say $Q-1$, when $\epsilon$ and $m$ satisfy the following condition $\log \epsilon+ 8m \leq 0$ by Stirling's approximation. 
% %By our choice of $m \sim \log n$ and $\epsilon \sim 1/(n \sqrt{\log n})$, the claim is proved.
% For instance, the condition is satisfied when $\gamma = 1/2$.

\section{Discussion} 
It has been claimed that the Fano's method is more general in a sense (see \citet[p. 428]{yu97lecam}).
Indeed, using Varshamov--Gilbert's lemma (e.g. Lemma 2.9 in \cite{tsybakov2009}), it is not very difficult to prove the same rate result for $\FF$ with a similar type of sub-parameter space using Fano's method.

However, Assouad's method seems more convenient in some cases.
For instance, before knowing how to construct the subspace, it would be extremely difficult to determine the right family of densities when there are only indirect regularity conditions as in this example.
Assouad's hyper-rectangle method indicates that the problem can be solved if we can show the orthogonality relations between the constructed densities.
These added regularity conditions can cause different difficulties, but we at least have some clues to handle these problems.

On the other hand, if we know metric entropy (good packing and covering number bounds) results beforehand, the optimal minimax rates can be obtained almost automatically with the predictive Bayes density estimator using the main theorems in \cite{yangbarron1999}.
It will be interesting to see if we can calculate a sharper metric entropy for $\FF$ or $\FF_s$ than the one that appeared in \cite{ghosalvaart2001}.

\section{Appendix}
\begin{proof}[Proof of Lemma \ref{assouadsim}]
Most of the proof is based on ideas borrowed from \cite{lecam73}, \cite{tsybakov2009},
 and some unpublished notes by David Pollard. Denote $A=\{0,1\}^K$ and for convenience denote $\ee_\alpha$ for $\ee_{f_\alpha}$ and $\pp_\alpha$ for $\pp_{f_\alpha}$ where $\pp_{f_\alpha} = P_{f_\alpha}^n$. For any density estimator $\hat f_n$ based on the observation $X_1,\ldots,X_n$, define an estimator
$$\hat \alpha = \arg\min_{\alpha \in A}  W(\hat f_n, f_\alpha ).$$
%Using the triangular inequality, $\int (T - \theta_\alpha)^2 + \int (T-\theta_\beta)^2 \geq \int (\theta_\alpha-\theta_\beta)^2$.
By restricting the parameter space and by the definition of $\hat \alpha$,
\begin{align*}
\sup_{f \in \FF} \ee_f W(\hat f_n, f) &\geq \max_{\alpha \in A} \ee_\alpha W (\hat f_n,f_\alpha) \\
&\geq\frac{1}{2}\max_{\alpha \in A} \ee_\alpha \left(W(\hat f_n,f_\alpha)+ W(\hat f_n,f_{\hat \alpha}) \right) \\
&\geq \frac{\zeta}{2} \max_{\alpha \in A} \ee_\alpha W (f_\alpha,f_{\hat\alpha})
\end{align*}
using the pseudo-distance property (\ref{metricW}).
Now, using the condition (\ref{cond1}) in the lemma followed by the simple fact that the supremum is bounded by the average, the last equation can be lower bounded by
%\begin{align*}
$$
\frac{c_0 \epsilon^2 \zeta}{2} \max_{\alpha \in A} \sum_{k=1}^m \ee_\alpha \one \{ \alpha_k \neq \hat \alpha_k \} \geq \frac{c_0 \epsilon^2 \zeta}{2} \frac{1}{2^m} \sum_{\alpha \in A} \sum_{k=1}^m \ee_\alpha \one \{\alpha_k \neq \hat \alpha_k\}. 
$$
%\end{align*}

Define 
$$
\bar \pp_{0,k}=\frac{1}{2^{m-1}} \sum_{\alpha \in A_{0,k}} \pp_\alpha, \ \  \bar \pp_{1,k}=\frac{1}{2^{m-1}} \sum_{\alpha \in A_{1,k}} \pp_\alpha, \ \ k=1,\ldots,m
$$
where $A_{i,k}=\{\alpha \in A: \alpha_k=i\}$ for $i=0,1$.


Since $\alpha_k, \hat \alpha_k\in \{0,1\}$, we have 
\begin{align*}
\frac{1}{2^m}\sum_{\alpha \in A} \sum_{k=1}^m \ee_\alpha \one \{ \alpha_k\neq \hat \alpha_k\} 
%&=\frac{1}{2^m}\sum_{k=1}^m \left( \sum_{\alpha \in A_{0,k}}\ee_\alpha (\hat \alpha_k-0)^2 
%+ \sum_{\alpha \in A_{1,k}} \ee_\alpha (\hat \alpha_k-1)^2 \right)\\
&=\frac{1}{2^m} \sum_{k=1}^m \left( \sum_{\alpha \in A_{0,k}} \pp_{\alpha} \one\{ \hat \alpha_k \neq 0\} + \sum_{\alpha \in A_{1,k}} \pp_{\alpha} \one \{\hat \alpha_k \neq 1\}  \right)\\
&= \frac{1}{2} \sum_{k=1}^m \left( \bar \pp_{0,k} \one \{\hat \alpha_k \neq 0\} + \bar \pp_{1,k} \one \{ \hat \alpha_k \neq 1\}   \right),
\end{align*}
which gives us the following lower bound
$$
\sup_{f \in \FF} \ee_{f} W (\hat f_n , f)
\geq
\frac{c_0 \epsilon^2 \zeta}{4} \sum_{k=1}^m||\bar \pp_{0,k} \wedge \bar \pp_{1,k} ||_1
$$
by $Ph+Q(1-h) \geq ||P \wedge Q||_1$ for $h \geq 0$ with $h=\mathbbm{1}\{\hat \alpha \neq 0\}$.

For $k=m$, each $\alpha$ in $A_{0,m}$ is of the form $(\gamma,0)$ with $\gamma \in D:= \{0,1\}^{m-1}$. Similarly, each $\alpha$ in $A_{1,m}$ is of the form $(\gamma,1)$ with $\gamma \in D$. Now
$$
||\bar \pp_{0,m} \wedge \bar \pp_{1,m} ||_1=\int \left(\frac{1}{2^{m-1}} \sum_{\gamma \in D} p_{\gamma,0} \right)
\wedge
 \left( \frac{1}{2^{m-1}} \sum_{\gamma \in D} p_{\gamma,1}\right) 
\geq \int \frac{1}{2^{m-1}} \sum_{\gamma \in D} (p_{\gamma,0} \wedge p_{\gamma,1}).
$$
Note that $(\gamma,0)$ and $(\gamma,1)$ have only one different coordinate. By similar calculations for other $k'$s, we obtain
$$
\sup_{f \in \FF} \ee_f W(\hat f_n, f) \geq \frac{c_0 \epsilon^2 \zeta}{4}m \min_{d(\alpha, \beta)=1} || \pp_\alpha \wedge \pp_\beta||_1.
$$

In general, it is difficult to calculate the testing affinity exactly. Fortunately, a convenient lower bound in terms of distances between marginals is available when $\pp_\alpha$ and $\pp_\beta$ are both product measures. For instance, when $\pp_\alpha = P_{\alpha}^n$ for i.i.d. case, we can bound this using the chi-squared distance $\chi^2$ by the following relation.
$$
(1-||\pp_\alpha \wedge \pp_\beta||_1)^2 \leq n \chi^2(P_\alpha, P_\beta) :=n \int \frac{(\theta_\alpha-\theta_\beta)^2}{\theta_\alpha}.
$$

Thus the condition (\ref{cond2}) in the lemma yields a lower bound for the maximum risk 
$$
\sup_{f \in \FF} \ee_f W(\hat f_n, f) \geq \frac{c_0\epsilon^2 \zeta}{4}m(1-\sqrt{c_1}).
$$
\end{proof}

See \citet[Lemma 2.7 on page 90]{tsybakov2009} or \citet[Lemma 1 on page 40]{lecam73} for the derivation of facts about relations between distances.

\begin{proof}[Proof of Lemma \ref{hermiteFT}]
For $b>a >0$, we have $$ \phi(at) \exp\left(btx- \frac{1}{2}x^2 \right) = \phi(at) \sum_{k=0}^\infty \frac{H_k(bt)}{k!}x^k.$$
Thus,
\begin{align*}
\fourier^{-1} \left[  \phi(at) \exp( bt x - \frac{1}{2}x^2 )  \right] (u) &= \int_{-\infty}^\infty \frac{\exp( i tu)}{2\pi}\exp\left(-\frac{a^2 t^2}{2} + bxt  - \frac{1}{2}x^2 \right)   dt \\
%&= \int \exp\left(-\frac{1}{2a^2}(\theta-a^2(bx+it) )^2 + \frac{1}{2a^2} \left( a^2(bx+it)\right)^2 - \frac{1}{2}x^2 \right)d\theta\\
&= \frac{1}{a\sqrt{2\pi}}\exp \left(\frac{(bx + i u)^2}{2a^2} - \frac{1}{2} x^2  \right) \\
&=\frac{1}{a} \phi\left(\frac{u}{a}\right) \exp\left( \frac{ bx u i}{a^2} - \frac{1}{2} \left(i x c_{a,b}\right)^2 \right)\\
&=\frac{1}{a}\phi\left(\frac{ u}{a}\right)\sum_{k=0}^\infty \frac{ H_k \left( b/(a^2 c_{a,b}) \ u  \right)}{k!} \left(i c_{a,b}\right)^{k} x^k. 
\end{align*}
The inverse Fourier transform of the right side is 
$$
\sum_{k=0}^\infty \fourier^{-1}\left[ \phi(at) \frac{H_k(b t)}{k!} \right] (u) x^k.
$$
By matching the coefficient for the $k^{th}$ power of $x$, $$\fourier^{-1} \left[ \phi(at) H_k(b t) \right](u) =\left(i c_{a,b}\right)^{k}\frac{1}{a}\phi\left(\frac{u}{a}\right) H_k \left( \frac{b}{a^2 c_{a,b}}\ u  \right) .$$ %Equivalently, $$\ft\left[ \left( \sqrt{a^2b^2-1} \right)^{-j} \exp(-\frac{\theta^2}{2a^2}) H_j(b\theta)\right](t) = a\sqrt{2\pi} \exp(-\frac{a^2t^2}{2}) H_j\left(  \frac{a^2b}{\sqrt{a^2b^2-1}}t \right) i^j,$$
which proves the claim.
\end{proof}

% \begin{proof}[Proof of Lemma \ref{lemma_halfg_H}]
% First, we bound the perturbations $v_k$ using Cramer's inequality for Hermite polynomials.
% \begin{align}
% \sum_{k\in K} |v_k(u)| &= \sum\NL_{k \in K} \frac{C_k}{\sqrt{k!}} \phi(\sqrt{3} u) |H_k(\frac{4}{\sqrt{5}}u)| \notag\\
% &\leq  \sum\NL_{k \in K}C_k \phi(\sqrt{3} u) \kappa \exp(\frac{4}{5} u^2) \qt{by (\ref{cramer})} \notag\\
% &=\frac{\kappa}{\sqrt{2\pi}} \exp\left(-\frac{1}{2} \frac{7}{5}u^2\right)  \sum\NL_{k \in K} C_k\notag\\
% &\leq \frac{\kappa mC_{2m-1}}{\sqrt{2\pi}} \exp\left(-\frac{1}{2} \frac{7}{5}u^2\right)  \ \ \text{by $C_k \leq C_{2m-1} \ \forall k \in K$}.  \label{boundv_k}
% \end{align}
% Using this upper bound (\ref{boundv_k}), we can lower bound $g_\alpha$. 
% %Let $\epsilon:= c_0/\sqrt{n}$.
% \begin{align*}
% \pi_\alpha(u) %&= g_0(u) + \epsilon \sum\NL_{k \in \MM} \alpha_k v_k(u) \\
% &\geq \pi_0(u) - \epsilon \sum\NL_{k \in K} |v_k(u)|\\
% &\geq \pi_0(u) - \frac{ \epsilon \kappa mC_{2m-1}}{\sqrt{2\pi}} \exp\left(-\frac{1}{2} \frac{7}{5}u^2\right)  \ \ \ \  \text{by (\ref{boundv_k})} \\
% &\geq \pi_0(u) - \frac{1}{2} \frac{1}{\sqrt{2\pi}} \exp(-\frac{u^2}{2}) \qt{by (\ref{cond_halfg_H})}\\
% &= \frac{1}{2}\pi_0(u).
% \end{align*}
% Similarly, we can upper bound $\pi_\alpha(u)$ by $\pi_0(u)+ \epsilon \sum\NL_{k\in K} |v_k(u)| \leq \dfrac{3}{2}\pi_0(u)$.
% \end{proof}


\begin{proof}[Proof of Lemma \ref{absorb_g0}]
%Main ideas are just completing the square and change of variables.
First note that $\phi \star \phi_{\sigma^2} = \phi_{1+\sigma^2}$.
We define $[\phi \star v_k(u)](x) = \int \phi(x-u)v_k(u)du$ and similarly $[\phi \star \phi(\rho u) H_k(\gamma u)](x) = \int \phi(x-u) \phi(\rho u) H_k(r u) du$.
By definition of $v_k$, we have
\begin{align*}
\frac{[\phi \star v_k(u)](x)}{\sqrt{\phi_{1+\sigma^2}(x)}} &= \frac{C_k}{\sqrt{k!}}\frac{[\phi \star \phi (\rho u) H_k(\gamma u)] (x)}{\sqrt{\phi_{1+\sigma^2}(x)}} \\
&=
\frac{C_k}{\sqrt{k!}} \int \frac{\frac{1}{\sqrt{2\pi}}\exp(-\frac{1}{2}(x-u)^2) \frac{1}{\sqrt{2\pi}} \exp(-\frac{1}{2}\rho^2 u^2) H_k(\gamma u)}{(2\pi (1+\sigma^2))^{-1/4} \exp(-\frac{1}{4} \frac{x^2}{1+\sigma^2})} du.
%&= \frac{C_k}{\sqrt{k!}} (1+\sigma^2)^{1/4} ({2\pi})^{-3/4}\int E_{\sigma, \rho}(x,u) H_k(\gamma u) du
\end{align*}
%where $E_{\sigma, \rho}(x,u)$ is the exponential factor.
Now, by completing the square,
\begin{align*}
\exp&\left(-\frac{1}{2}(x-u)^2\right)\exp\left(-\frac{1}{2}\rho^2 u^2\right) \exp\left(\frac{1}{4} \frac{x^2}{1+\sigma^2}\right)  \\&=\exp\left(\left(-\frac{1}{2}+\frac{1}{4(1+\sigma^2)}\right) x^2 + xu -\left(\frac{1}{2}+ \frac{1}{2}\rho^2\right)u^2 \right) \\
&= \exp\left( -\frac{1}{2\tilde \sigma^2}x^2+ xu  -\left(\frac{1}{2}+ \frac{1}{2}\rho^2\right)u^2\right) \qt{by def. of $\tilde \sigma^2$ in (\ref{tilde_def})} \\
&=\exp\left(-\frac{1}{2 \tilde \sigma^2} (x-\tilde u)^2 \right) \exp\left( -\frac{1}{2}(1+\rho^2-\tilde \sigma^2)\frac{\tilde u^2}{\tilde \sigma^4}\right) \qt{by $\tilde u := \tilde \sigma^2 u$}\\
&= (2\pi \tilde \sigma) \phi_{\tilde \sigma^2}(x-\tilde u) \phi \left( \frac{ \sqrt{1+\rho^2-\tilde \sigma^2}}{\tilde \sigma^2} \tilde u\right),
\end{align*}
where the positive value for $(1+\rho^2-\tilde \sigma^2)$ is guaranteed by the condition $\rho^2 \geq  1/\sigma^2+\gamma^2/2 >  1/(1+2\sigma^2) := 1-\tilde \sigma^2$.
%, which guarantees that the coefficient in the second exponential term is negative.
By change of variables,
%\begin{align*}
$$\frac{[\phi \star v_k(u)](x)}{\sqrt{\phi_{1+\sigma^2}(x)}} 
%&= 
%C_k C_\sigma \int \exp\left((-\frac{1}{2}+\frac{1}{4(1+\sigma^2)}) x^2 + xu -(\frac{1}{2}+ \frac{1}{2}\lambda^2)u^2 \right)H_k(\gamma u) du\\
%&=C_k C_\sigma \int \exp\left( -\frac{1}{2\tilde \sigma^2}x^2+ xu  -(\frac{1}{2}+ \frac{1}{2}\lambda^2)u^2\right) H_k(\gamma u) du\ \  \text{by def. of $\tilde \sigma^2$}\\
%&= C_k C_\sigma \int \exp(-\frac{1}{2 \tilde \sigma^2} (x-\tilde \sigma^2 u)^2 \exp\left( -\frac{1}{2}(1+\lambda^2-\tilde \sigma^2)u^2\right) H_k(\gamma u) du\\
= \left(\frac{C_k}{\sqrt{k!}} \frac{ [2\pi (1+\sigma^2)]^{1/4} }{\tilde \sigma } \right) \phi_{\tilde \sigma^2} \star \phi\left(\frac{ \sqrt{1+\rho^2-\tilde \sigma^2}}{\tilde \sigma^2} \tilde u\right) H_k \left( \frac{\gamma}{\tilde \sigma^2}\tilde u\right).
$$
%\end{align*}
%where $C_\sigma := \left(\dfrac{1+\sigma^2}{2\pi}\right)^{\frac{1}{4}}$, and the last two equalities are by completing the square and change of variables, respectively.
Using the definitions of each transformed variables (\ref{tilde_def}), the proof is complete.
\end{proof}

\textbf{Acknowledgements} \nl
This work is part of the author's PhD dissertation, written at Yale University.
The author is grateful to David Pollard, Harrison Zhou, and Richard J. Samworth for their comments and advice.
%\end{acknowledgements}

\bibliographystyle{chicago}      % mathematics and physical sciences
\bibliography{KYK}   % name your BibTeX data base

\end{document}
% end of file template.tex


kyk_Mar28.bbl
\def\noopsort#1{}
\begin{thebibliography}{}

\bibitem[\protect\citeauthoryear{Billingsley}{Billingsley}{1995}]{billingsley}
Billingsley, P. (1995).
\newblock {\em Probability and Measure\/} (3rd ed.).
\newblock Wiley.

\bibitem[\protect\citeauthoryear{Ghosal and van~der Vaart}{Ghosal and van~der
  Vaart}{2001}]{ghosalvaart2001}
Ghosal, S. and A.~W. van~der Vaart (2001).
\newblock Entropies and rates of convergence for maximum likelihood and {B}ayes
  estimation for mixtures of normal densities.
\newblock {\em Ann. Statist.\/}~{\em 29\/}(5), 1233--1263.

\bibitem[\protect\citeauthoryear{Gradshteyn and Ryzhik}{Gradshteyn and
  Ryzhik}{2007}]{table}
Gradshteyn, I.~S. and I.~M. Ryzhik (2007).
\newblock {\em Table of Integrals, Series, and Products\/} (7th ed.).
\newblock Academic Press.

\bibitem[\protect\citeauthoryear{Ibragimov}{Ibragimov}{2001}]{ibragimov2001}
Ibragimov, I. (2001).
\newblock Estimation of analytic functions.
\newblock In C.~K. M.~de Gunst and A.~van~der Vaart (Eds.), {\em State of the
  Art in Probability and Statistics}, Volume~36, pp.\  359--383. IMS,
  Beachwood, OH.

\bibitem[\protect\citeauthoryear{Jackson}{Jackson}{2004}]{fourier_jackson}
Jackson, D. (2004).
\newblock {\em Fourier Series and Orthogonal Polynomials}.
\newblock Dover publications.

\bibitem[\protect\citeauthoryear{Kawata}{Kawata}{1972}]{kawata}
Kawata, T. (1972).
\newblock {\em Fourier Analysis in Probability Theory}.
\newblock Academic Press.

\bibitem[\protect\citeauthoryear{Le~Cam}{Le~Cam}{1973}]{lecam73}
Le~Cam, L. (1973).
\newblock Convergence of estimates under dimensionality restrictions.
\newblock {\em Annals of Statistics\/}~{\em 1}, 38--53.

\bibitem[\protect\citeauthoryear{Marsden and Hoffman}{Marsden and
  Hoffman}{1999}]{marsden1999}
Marsden, J.~E. and M.~J. Hoffman (1999).
\newblock {\em {Basic Complex Analysis}\/} (2nd ed.).
\newblock New York: W. H. Freeman and Company.

\bibitem[\protect\citeauthoryear{Rudin}{Rudin}{1987}]{rudin_real_complex}
Rudin, W. (1987).
\newblock {\em Real and Complex Analysis\/} (Third ed.).
\newblock McGraw-Hill Book Co.

\bibitem[\protect\citeauthoryear{Tsybakov}{Tsybakov}{2009}]{tsybakov2009}
Tsybakov, A.~B. (2009).
\newblock {\em Introduction to Nonparametric Estimation}.
\newblock New York: Springer-Verlag.

\bibitem[\protect\citeauthoryear{Van~der Vaart}{Van~der
  Vaart}{1998}]{vanassouad}
Van~der Vaart, A. (1998).
\newblock {\em Asymptotic Statistics}.
\newblock Cambridge University Press.

\bibitem[\protect\citeauthoryear{Yang and Barron}{Yang and
  Barron}{1999}]{yangbarron1999}
Yang, Y. and A.~R. Barron (1999).
\newblock Information-theoretic determination of minimax rates of convergence.
\newblock {\em Annals of Statistics\/}~{\em 27}, 1564--1599.

\bibitem[\protect\citeauthoryear{Yu}{Yu}{1997}]{yu97lecam}
Yu, B. (1997).
\newblock Assouad, {F}ano, and {Le Cam}.
\newblock In D.~Pollard, E.~Torgersen, and G.~L. Yang (Eds.), {\em A
  Festschrift for Lucien Le~Cam}, pp.\  423--435. New York: Springer-Verlag.

\end{thebibliography}
