Sample complexity of population recovery
The problem of population recovery refers to estimating a distribution based on incomplete or corrupted samples. Consider a random poll of sample size $n$ conducted on a population of individuals, where each pollee is asked to answer $d$ binary questions. We consider one of the two polling impediments: \begin{itemize em in lossy population recovery, a pollee may skip each question with probability $\epsilon$; em in noisy population recovery, a pollee may lie on each question with probability $\epsilon$. \end{itemize Given $n$ lossy or noisy samples, the goal is to estimate the probabilities of all $2^d$ binary vectors simultaneously within accuracy $\delta$ with high probability. This paper settles the sample complexity of population recovery. For lossy model, the optimal sample complexity is $\tilde\Theta(\delta^{ -2\max\{\frac{\epsilon{1-\epsilon,1\)$, improving the state of the art by Moitra and Saks in several ways: a lower bound is established, the upper bound is improved and the result depends at most on the logarithm of the dimension. Surprisingly, the sample complexity undergoes a phase transition from parametric to nonparametric rate when $\epsilon$ exceeds $1/2$. For noisy population recovery, the sharp sample complexity turns out to be more sensitive to dimension and scales as $\exp(\Theta(d^{1/3 \log^{2/3(1/\delta)))$ except for the trivial cases of $\epsilon=0,1/2$ or $1$. For both models, our estimators simply compute the empirical mean of a certain function, which is found by pre-solving a linear program (LP). Curiously, the dual LP can be understood as Le Cam's method for lower-bounding the minimax risk, thus establishing the statistical optimality of the proposed estimators. The value of the LP is determined by complex-analytic methods.
main.tex
\begin{document}
\maketitle
\begin{abstract}
The problem of population recovery refers to estimating a distribution based on incomplete or corrupted samples.
Consider a random poll of sample size $n$ conducted on a population of individuals, where each pollee is asked to answer $d$ binary questions.
We consider one of the two polling impediments: 
\begin{itemize}
\item in lossy population recovery, a pollee may skip each question with probability $\epsilon$; 
\item in noisy population recovery, a pollee may lie on each question with probability $\epsilon$.
\end{itemize}
Given $n$ lossy or noisy samples, the goal is to estimate the probabilities of 
all $2^d$ binary vectors simultaneously within accuracy $\delta$ with high probability. 

This paper settles the sample complexity of population recovery.
For lossy model, the optimal sample complexity is $\tilde\Theta(\delta^{ -2\max\{\frac{\epsilon}{1-\epsilon},1\}})$,
improving the state of the art by Moitra and Saks in several ways: a lower bound is established, the upper bound is improved and the result depends at most on the logarithm of the dimension. Surprisingly, the sample complexity undergoes a phase transition from parametric to nonparametric rate when $\epsilon$ exceeds $1/2$. For noisy population recovery, the sharp sample complexity turns out to be more sensitive to dimension and scales as $\exp(\Theta(d^{1/3} \log^{2/3}(1/\delta)))$ except for the trivial cases of $\epsilon=0,1/2$ or $1$.

For both models, our estimators simply compute the empirical mean of a certain
function, which is found by pre-solving a linear program (LP). Curiously, the dual LP can be understood as Le Cam's method for lower-bounding the minimax risk, thus establishing the statistical optimality of the proposed estimators. The value of the LP is determined by complex-analytic methods.
\end{abstract}



\tableofcontents
%\newpage

\section{Introduction}
	\label{sec:intro}


\subsection{Formulation}
	\label{sec:formulation}




The problem of \emph{population recovery} refers to estimating an unknown distribution based on incomplete or corrupted samples.
Initially proposed by~\cite{DRWY12,WY12} in the context of learning DNFs with partial observations and further investigated in \cite{batman2013finding,MS13,LZ15,DST16}, this problem can also be viewed as a special instance of learning mixtures of discrete distributions in the framework of \cite{kearns1994learnability}.



The setting of \pop is the following:
Let $\cP_d$ be the set of all probability distributions over the hypercube
$\{0,1\}^d$. Let $P \in \cP_d$ be an unknown probability
distribution and $X \ed (X_1,X_2,\ldots X_d) \sim P$. Instead of
observing $X$, we observe its noisy version according to one of the two observation models:
\begin{itemize}
\item \textbf{Lossy population recovery}: For
  each $i$, $Y_i$ is obtained by passing $X_i$ independently through the 
	binary erasure channel with erasure probability $\epsilon$, 
	where 	$Y_i = X_i$ with probability $1-\epsilon$, and $Y_i = ?$,
  with probability $\epsilon$. 
  \item \textbf{Noisy population recovery}: 
    For each $i$, $Y_i$ is obtained by passing $X_i$ independently through the 
	binary symmetric channel with error probability $\epsilon$, 
	where		$Y_i = X_i$ with probability $1-\epsilon$, and $Y_i =
    1- X_i$, with probability $\epsilon$. 
\end{itemize}


Given independent noisy or lossy samples, the goal of \pop is to estimate the underlying distribution.  Specifically,
let $X^{(1)},\ldots,X^{(n)}$ be independently drawn from $P$ and we observe their noisy or lossy versions, denoted by
$Y^{(1)},\ldots,Y^{(n)}$, and aim to estimate the probabilities of all strings within $\delta$ simultaneously, i.e.,
$\|P-\hat P\|_\infty \leq \delta$ with high probability.\footnote{Equivalently, up to constant factors, we need to output
a set of strings $S \subset \{0,1\}^d$ and $\hat{P}_x$ for each $x \in S$, such that for all
$x \in S$, $|\hat{P}_x - P_x| \leq \delta$ and for all $x \notin S$, $P_x \leq \delta$. The point is that even when
dimension $d$ is large the list $S$ can be kept to a finite size of order ${1\over \delta}$.} In the absence of erasures
or errors, the problem is simply that of distribution estimation and the empirical distribution is near-optimal.  If the samples
are lossy or noisy, the distribution of each sample is a mixture of exponentially (in $d$) many product distributions
with mixing weights given by the input distribution $P$.  This problem is hence a special case of learning mixtures of discrete
product distributions introduced in \cite{kearns1994learnability} and more recently in
\cite{feldman2008learning,li2015learning}.


One of the key observations from \cite{DRWY12} is that both the sample and algorithmic complexity of estimating $P_x$ for all $x \in \{0,1\}^d$ is largely determined by those of estimating $P_x$ for a single $x$, which, without loss of generality, can be assumed to be the zero string.
This problem is referred to as \emph{individual recovery}.\footnote{This 
can be viewed as the combinatorial counterpart of estimating the density at a point, a well-studied problem in nonparametric statistics, where given $n$ iid samples drawn from a density $f$, the goal is to estimate $f(0)$ cf.~\cite{Tsybakov09}.}
Note that one can convert any estimator $\hat P_0$ to $\hat P_x$ by XOR-ing with $x$ the samples and applying the
estimator $\hat P_0$. 
However, naively applying union bound over all strings inflates both the time complexity and the error probability by a factor $2^d$, which is unacceptable.
The clever workaround in~\cite{DRWY12} is to leverage the special structure of Hamming space by recursively solving the
problem on lower-dimensional subspaces.
This argument is further explained in \prettyref{app:alg} along with an improved analysis. 
Specifically, given any estimator $\hat P_0$ using $n$ samples and time complexity $t$ such that $\Expect|\hat P_0 - P_0| \leq \delta$,
it can be converted to a distribution estimator $\hat P$ such that $\|\hat P-P\|_\infty \leq \delta$ with probability at least $1-\tau$ with 
$n \cdot \log \frac{d}{\delta \tau}$ samples and time complexity $t \cdot \frac{d}{\delta} \log \frac{d}{\delta \tau}$.
Therefore the problem of population recovery is equivalent, both statistically and algorithmically, to the problem of individual recovery.




%In light of the above reduction, it suffices to focus on individual recovery, with the goal of estimating $P_0$.
To understand the statistical fundamental limit of this problem, we consider the \emph{minimax risk}, defined as:
\begin{equation}
R^*(n, d) = \inf_{\hat{P_0}}\sup_P \Expect_P[(\widehat{P_0}
  - P_0)^2].
\label{eq:minimaxp0}
\end{equation}
To be consistent with the existing literature, the main results in this paper are phrased in terms of \emph{sample complexity}:
\begin{equation}
n^*(\delta,d) = \min\{n: R^*(n, d) \leq \delta^2\},
\label{eq:nstar}
\end{equation}
with subscript $\sfL$ or $\sfN$ denoting the lossy or noisy observation model. Up to constant factors, $n^*(\delta,d)$ is also the minimal sample size such that $P_0$ can be estimated within an additive error of $\delta$ with probability, say, $1/3$.
%By the usual split-sample-then-median method (see, e.g., \cite[Lemma 8]{acharya2017estimating}), $n^*(\delta,d) \cdot \log \frac{1}{\tau}$ suffices to boost the confidence to $1-\tau$. Using the algorithm of \cite{DRWY12} (see \prettyref{lem:irptorp} in  \prettyref{app:alg}), $n^*(\delta,d) \cdot \log \frac{d}{\delta \tau}$ samples suffices to estimate all probabilities within $\delta$ with probability $1-\tau$. 
The focus on this paper is to obtain sharp bounds on both $n^*_{\sfL}(d,\delta)$ and $n^*_{\sfN}(d,\delta)$ and computationally efficient estimators with provable optimality.
We make no assumption on the support size of the underlying distribution.





\subsection{Prior work}
	\label{sec:prior}

To review the existing results, we start with lossy \pop. Recall that $\epsilon$ is the erasure probability.
	A polynomial-time estimator is given in \cite{DRWY12} that succeeds  for $\epsilon \leq 0.635$, which was subsequently improved 
to 	$\epsilon \leq 1/\sqrt{2}$ by \cite{batman2013finding}.
The state of the art is \cite{MS13} who proposed a polynomial time algorithm that works for all $\epsilon < 1$, with sample complexity:
\begin{equation}
n^*_{\sfL}(d,\delta) \lesssim \pth{\frac{d}{\delta}}^{\frac{2}{1-\epsilon}\log\frac{2}{1-\epsilon}}.
\label{eq:ms13}
\end{equation}

It is worth noting that for the lossy model, most of the estimators for $P_0$ are of the following form:
\begin{equation}
\hat P_0 = \frac{1}{n} \sum_{i=1}^n g(w_i)
\label{eq:hatp}
\end{equation}
where $w_i=w(Y^{(i)})$ is the number of ones in the $i\Th$ sample $Y^{(i)}$.
Such an estimator is referred to as a \emph{linear estimator} since \prettyref{eq:hatp} can be equivalently written as a linear combination
$\hat P_0  = \frac{1}{n}\sum_{j=0}^d g(j) N_j$, where $N_j$ is the number of samples of Hamming weight $j$. Both \cite{MS13} and \cite{DST16} focus on efficient algorithms to construct the coefficient $g$.

The problem of noisy \pop was first studied by~\cite{WY12}. 
In contrast to the lossy model which imposes no assumption on the input, all provable results 
for the noisy model are obtained under a ``sparsity'' assumption, namely, the distribution $P$ has bounded support size $k$.
%The earlier result in \cite{kearns1994learnability} implies that $\exp(O(k))$ samples are sufficient. 
An algorithm for noisy recovery is proposed in \cite{WY12} with sample complexity $k^{\log k}$.
This was further improved by~\cite{LZ15} to $k^{\log \log k}$. Recently \cite{DST16} proposed a recovery algorithm with sample complexity that is polynomial in $(k/\delta)^{1/(1-2\epsilon)^4}$ and $d$, where $\epsilon$ is the probability to flip each bit.




Despite these exciting advances, several fundamental questions remain unanswered:
\begin{itemize}
\item Is it sufficient to restrict to the family of linear estimators of the form \prettyref{eq:hatp}? 
\item What is the optimal sample complexity of population recovery in terms of $\epsilon, d, \delta$? 
\item Estimators such as~\eqref{eq:hatp} only depend on the number of ones in the sample. For lossy \pop, in fact the number of ones and zeros in each sample together constitute a sufficient statistic (see \prettyref{rmk:type}) and a natural question arises: is the number of zeros in the samples almost uninformative for estimating $P_0$?
  \item For noisy \pop, is the assumption of bounded support size necessary for achieving polynomial (in $d$) sample complexity? 
  \end{itemize}
As summarized in the next two subsections, the main results in this paper settle all of these questions.  Specifically,
we find the optimal sample complexity and show that linear estimators~\eqref{eq:hatp} suffice to achieve it.
For lossy population recovery, the number of zeros indeed can be ignored. For the noisy model, without the bounded support assumption the sample complexity scales superpolynomially in the dimension.


\subsection{New results}
The main results of this paper provide sharp characterizations of the sample complexity for both lossy and noisy \pop, as well as computationally efficient estimators, 
shown optimal by minimax lower bounds.
We start from lossy recovery. 
The next result %significantly improves over \prettyref{eq:ms13} and 
determines the optimal sample complexity up to a $\mathrm{polylog}$ factor, which turns out to be \emph{dimension-free}.
\begin{theorem}[Lossy population recovery]
\label{thm:bec}
%For any estimator $\hat{p_0}$ that depends on the number of ones in $Y^{(1)},\ldots,Y^{(n)}$, we have
%\[
%\inf_{\hat{p_0}}\sup_p \Expect_P[(\widehat{p_0} - p_0)^2] = n^{ - \min\{\frac{1-\epsilon}{\epsilon},1\}} \mathrm{polylog}(n).
%\]
Assume $\delta<1/e$. There exist universal constants $c_1,c_2$ such that the following hold.
For the {low-erasure} regime of $\epsilon \leq 1/2$,
\begin{equation}
\frac{c_1}{\delta^2} \leq \sup_{d \in \naturals} n^*_{\mathsf{L}}(\delta,d) \leq \frac{1}{\delta^2}.
\label{eq:bec-low}
\end{equation}
For the {high-erasure} regime of $\epsilon > 1/2$,
\begin{equation}
c_2 \Big(e \delta \log \frac{1}{\delta}\Big)^{ -\frac{2\epsilon}{1-\epsilon}}
\leq
\sup_{d \in \naturals} n^*_{\mathsf{L}}(\delta,d) \leq \delta^{
  -\frac{2\epsilon}{1-\epsilon}}.
\label{eq:bec-high}
\end{equation}
Furthermore, for \prettyref{eq:bec-low} and \prettyref{eq:bec-high}, 
the supremum can be replaced by any $d \geq 1$ and $d \gtrsim \delta ^{ -\frac{2\epsilon}{1-\epsilon}} \polylog(\frac{1}{\delta})$, respectively.
%$E(\epsilon) = \frac{\log \frac{1+\epsilon}{\epsilon}}{\log \frac{1+\epsilon}{1-\epsilon}}$.
\end{theorem}

\begin{remark}[Elbow effects]
\label{rmk:elbow}
An important result in the statistics literature on nonparametric and high-dimensional functional estimation, the
\emph{elbow effect} refers to the phenomenon that there exists a critical regularity parameter (\eg, smoothness) below
which the rate of estimation is parametric $O(1/n)$ and above which, it becomes nonparametric (slower than $1/n$) in the
number of samples $n$. 
Taking a nonparametric view of the lossy population recovery problem by considering the input as binary sequence of infinite length, what we proved is the following characterization of the minimax estimation error:
\begin{equation}
%R^*(n, \infty) = 
\inf_{\hat{P_0}}\sup_P \Expect_P[(\widehat{P_0} - P_0)^2] = 
\begin{cases}
 \Theta(n^{-1}) &  0\leq \epsilon\leq \frac{1}{2} \\
n^{ - \frac{1-\epsilon}{\epsilon}} \polylog(n) &  \frac{1}{2} < \epsilon < 1 \\
\end{cases}
\label{eq:minimax-rate}
\end{equation}
%This type of behavior is known as \emph{elbow effect} in the rate of convergence in the nonparametric statistics literature.
which exhibits the following elbow phenomenon:
\begin{itemize}	
	\item In the \emph{low-erasure} regime of $\epsilon \leq 1/2$, it is possible to achieve the parametric rate of $1/n$ in any dimension. Clearly this is the best one can hope for even when $d=1$, in which case one wants to estimate the bias of a coin based on $n$ samples but unfortunately $\epsilon$-fraction of the samples are lost.
\item In the \emph{high-erasure} regime of $\epsilon > 1/2$, the infinite dimensionality of the problem kicks in and the optimal rate of convergence becomes nonparametric and strictly slower than $1/n$.
\end{itemize}
Since elbow effects are known for estimating non-linear (\eg, quadratic) functionals 
%in nonparametric regression, density estimation or estimation in high dimensions 
(see, e.g., \cite{INK87,cai2005nonquadratic,FRW15}), 
	it is somewhat surprising that it is also manifested in lossy \pop where the goal is to estimate a simple linear functional, namely, $P_0$.
	
	
The lossy population recovery problem should also be contrasted with classical statistical problems in the presence of \emph{missing data}, such as low-rank matrix completion and principle component analysis. In the latter case, it has been shown in \cite{Lounici14} that 
if an $\epsilon$ faction of the coordinates of each sample are randomly erased, this effectively degrades the sample size from $n$ to $n \epsilon^2$. 
For lossy \pop, \prettyref{thm:bec} shows there is a phase transition in the effect of missing observations: when more
than half of the data are erased ($\epsilon > 1/2$), 
 the rate of convergence are penalized and the effective sample size drops from $n$ to $n^{(1-\epsilon)/\epsilon}$.
\end{remark}






Next we turn to the noisy population recovery. Perhaps surprisingly, the sample complexity is no longer dimension-free and in fact grows with the dimension $d$ super-polynomially. The next result determines it up to a constant in the exponent.
%Fnd  the noisy population recovery, in Theorem~\ref{}, we show that

\begin{theorem}[Noisy population recovery]
\label{thm:bsc}
%For any estimator $\hat{p_0}$ that depends on the number of ones in $Y^{(1)},\ldots,Y^{(n)}$, we have
Let $\mu(\epsilon) \triangleq \frac{\epsilon(1-\epsilon)}{(1-2\epsilon)^2}$.
For all $d\geq 1$,
\[
\min\sth{
\exp(c_1 (1-2\epsilon)^2d), 
%\pth{\frac{d^4 \mu(\epsilon)}{\log^4 \frac{1}{\delta}} }^{1/3}
\exp\pth{c_1 \pth{d\mu(\epsilon) \log^2 \frac{1}{\delta}}^{1/3} }} \leq
  n^*_{\sfN}(\delta,d) \leq \exp\pth{ c_2 \pth{d\mu(\epsilon) \log^2 \frac{1}{\delta}}^{1/3} }.
\]
where $c_1,c_2$ are universal constants and the upper and lower bounds hold for all $\delta<1$ and all $\delta<1/3$, respectively.
\end{theorem}
\prettyref{thm:bsc} shows that to estimate $P_0$ within a constant accuracy $\delta$, the optimal sample size scales as 	
\[
 n^*_{\sfN}(\delta, d) = \exp\pth{
   \Theta\pth{\pth{\frac{\epsilon(1-\epsilon)}{(1-2\epsilon)^2}
     d \log^2\frac{1}{\delta}}^{1/3}} }.
\]
which is superpolynomial in the dimension.
This shows that the assumption made
by~\cite{kearns1994learnability,WY12} and subsequent work that the input distribution has bounded support size is in fact crucial for achieving polynomial sample complexity.
Indeed both algorithms in \cite{LZ15,DST16} are based on Fourier analysis of Boolean functions and exploit the sparsity of the distribution and they are not of the linear form \prettyref{eq:hatp}.

Finally, we mention that a subset of our results was
discovered independently by \cite{de2017sharp} using similar techniques.


\subsection{Technical contributions}

To describe our approach, we start from the constructive part. 
For both lossy and noisy \pop, we also focus on linear estimator \prettyref{eq:hatp}. 
Choosing the coefficient vector $g$ to minimize the worst-case mean squared error $\Expect (P_0-\hat P_0)^2$ leads to the following linear programming (LP):
\begin{equation}
\min_{g\in\reals^{d+1}}  \|\Phi^\top g-e_0\|_\infty + \frac{1}{\sqrt{n}} \|g\|_\infty,
\label{eq:LP-intro}
\end{equation}
where $e_0=(1,0,\ldots,0)^\top$ and $\Phi$ is a column stochastic matrix (probability transition kernel) that describes the conditional distribution of the output Hamming weight given the input weight.
%corresponds to the BEC (resp.~BSC) channel for lossy (resp.~noisy) population recovery problem. 
Here the first and second term in \prettyref{eq:LP-intro} correspond to the bias and standard deviation respectively. 
In fact, for lossy recovery the (unique) unbiased estimator is a linear one corresponding to $g= (\Phi^\top)^{-1} e_0$. 
When the erasure probability $\epsilon\leq \frac{1}{2}$, this vector has bounded entries and hence the variance is $O(\frac{1}{n})$. This has already been noticed in \cite[Sec.~6.2]{DRWY12}. However, 
when $\epsilon>\frac{1}{2}$, the variance of the unbiased estimator is exponentially large and the LP \prettyref{eq:LP-intro} aims to achieve the best bias-variance tradeoff.



Surprisingly, we show that the value of the above LP also produces a lower bound that applies to \emph{any} estimator. This is done by relating the dual program of \prettyref{eq:LP-intro} to Le Cam's two-point method for proving minimax lower bound \cite{Lecam86}.  \prettyref{sec:general} formalizes this argument and introduces a general framework of characterizing the minimax risk of estimating linear functionals of discrete distributions by means of linear programming.

The bulk of the paper is devoted to evaluating the LP \prettyref{eq:LP-intro} for the lossy (\prettyref{sec:bec}) and noisy model (\prettyref{sec:bsc}). The common theme is to recast the dual LP in the function space on the complex domain, consider its $H^\infty$-relaxation, and use tools from complex analysis to bound the value.
Similar
 proof technique was previously employed in \cite{MS13} to upper-bound the value of the dual LP in order to establish the sample complexity upper bound in \prettyref{eq:ms13}.
Here we tighten the analysis to obtain the optimal exponent and dimension-free result. Furthermore, we show that the dual LP not only provides an upper bound on the estimation error, it also gives minimax lower bound via the general result in \prettyref{sec:general} together with a refinement based on Hellinger distance.
To show the impossibility results we need to bound the value of the dual LP from below, which we do by demonstrating
an explicit solution that plays the role of the least favorable prior in the minimax lower bound.
%\prettyref{prop:mintv-bec} and \prettyref{prop:mintv-bsc} 
%Furthermore, to obtain matching lower bound for lossy recovery, we turn to 
%consider the dual, use complex analysis tools to bound.

Initially, we were rather surprised to have non-trivial complex-analytic methods such Hadamard three-lines theorem
emerge in this purely statistical problem. Realizing to have rediscovered portions of~\cite{MS13}, we were further surprised
when a new estimator for the trace reconstruction problem\footnote{This problem, in short, aims to
reconstruct a binary string based on its independent observations through a memoryless deletion channel.} was recently proposed by \cite{nazarov2016trace} and \cite{de2016optimal}, whose design crucially relied on complex-analytic methods. In fact, one of the key steps
of~\cite{nazarov2016trace} relies on the results from~\cite{borwein1997littlewood}, which we also use in \prettyref{sec:bsc} to obtain
sharp bounds for noisy \pop.


Finally, in ~\prettyref{sec:smooth} we propose an alternative linear estimator, which requires a slightly worse sample
complexity \[ \delta^{ -2\max\{\frac{3\epsilon - 1}{1-\epsilon},1\}}, \] having the exponent off by a factor of at most
$2$ in the worst case of $\epsilon \to 1$. The advantage of this estimator is that it is explicit and does not require
pre-solving a $d$-dimensional LP. The estimator is obtained by applying the \emph{smoothing}
technique introduced in \cite{OSW16} that averages a sequence of randomly truncated unbiased estimators to achieve good
bias-variance tradeoff.

	
\subsection{Notations}
	\label{sec:notations}


	Let $\Binom(n,p)$ denote the binomial distribution with parameters $n$ and $p$.
	For a pair of probability distributions $P$ and $Q$, 
	let $P \otimes Q$ and $P*Q$ denote their product distribution and convolution, respectively.
	Let 
	$\TV(P,Q) = \frac{1}{2}\int |\diff P-\diff Q|$, $H^2(P,Q)=\int (\sqrt{\diff P}-\sqrt{\diff Q})^2$ and $H(P,Q) =
	\sqrt{H^2(P,Q)}$ denote the total variation, squared  and non-squared Hellinger distance, respectively.	
	Throughout the paper, for any $\epsilon \in (0,1)$, let $\bar{\epsilon} \triangleq 1-\epsilon$.	
	For a family of parametric distribution $\{P_\theta: \theta\in\Theta\}$ and a prior $\pi$ on $\Theta$, with a
	slight abuse of notation we write $\Expect_{\theta\sim \pi}[P_\theta]$ to denote
	the mixture distribution $\int \pi(\diff \theta) P_\theta$. 
	For a holomorphic function $f(z)$ on the unit disk $D\subset\mathbb{C}$ we let $[z^k]f(z)$ denote the $k$-th
	coefficient of its Maclaurin series.
	

	
%\section{General theory}
\section{Estimating linear functionals and duality of Le Cam's method}
	\label{sec:general}
	
	%\subsection{Duality between upper bound and Le Cam's method}
	%\label{sec:dual}
	
        In this section, we relate the general problem of estimating linear
        functionals of distributions to the solution of a 
				\emph{minimal total variation} linear program. The latter corresponds to
        the optimization of a pair of distributions in Le Cam's
        two-point method and thus produces minimax lower bounds.
				Surprisingly, we also show that dual linear program
        produces an estimator, thereby explaining the general tightness
        of the two-point method.
\begin{theorem}
\label{thm:dual}
        Let $\Theta$ and $\calX$ be finite sets and $\{P_\theta:\theta \in
        \Theta\}$ be a collection of distributions on $\calX$.  Let $\pi$
        be a distribution (prior) on $\Theta$ and let $X_1,\ldots,X_n$ be iid samples from the mixture distribution\footnote{In
	other words, for
        each $i=1,\ldots,n$, $\theta_i$ is drawn iid from $\pi$ and $X_i \sim P_{\theta_i}$ independently.} $\sum_{\theta\in\Theta}
	\pi(\theta) P_\theta$.
        %The goal is to estimate a linear functional of $\pi$
				To estimate a linear functional of $\pi$
\[
F(\pi)\triangleq \iprod{\pi}{h} = \Expect_{\theta\sim\pi}{h(\theta)},
\]
define the minimax quadratic risk
\begin{equation}
R_n \triangleq \inf_{\hat F} \sup_{\pi} \Expect_\pi[(\hat F(X_1,\ldots,X_n)-F(\pi))^2].
\label{eq:minimax-F}
\end{equation}
Without loss of generality\footnote{This is because $R_n$ is unchanged if $h$ is replaced by $h-c \ones$ for any constant $c$. Note, however,
that the value of~\eqref{eq:LP-G} does change.} we assume that there exists $\theta_+$ and $\theta_-$ such that
$h(\theta_-)\le 0 \le h(\theta_+)$.
Then we have
\begin{equation}
{1\over 64}\delta\pth{\frac{1}{n}}^2 \leq R_n \leq \delta\pth{\frac{1}{\sqrt{n}}}^2,
\label{eq:dual}
\end{equation}
where $\delta(t)$ is given by the following linear program
\begin{equation}
\delta(t) \triangleq \max_{\Delta \in\mreals^\Theta} \{\iprod{\Delta}{h}: \|\Delta\|_1\leq 1, \|\Phi \Delta\|_1\leq t\}\,,
\label{eq:LP-G}
\end{equation}
where 
%$\Delta=\{\Delta_{\theta}, \theta \in\Theta\}$ is an element of $\mreals^\Theta$ 
$\Phi = (\Phi_{x,\theta})_{x\in \calX, \theta \in \Theta}$ is an $|\calX|\times |\Theta|$ column-stochastic matrix with
	$\Phi_{x,\theta} \eqdef P_\theta(x)$.
\end{theorem}
\begin{remark} 
\label{rmk:type}
Particularizing the above framework to the problem of population recovery, the subsequent two sections will be devoted to computing the LP value $\delta(t)$ for the lossy and noisy model, respectively. Below we specify the setting as a concrete example.
Since the probability of the zero vector is \emph{permutation-invariance}, it is sufficient\footnote{Indeed, for the worst-case formulation \prettyref{eq:minimaxp0}, the least favorable distribution $P$ is \emph{permutation-invariant}. Furthermore, if the input string $X$ has a permutation-invariant distribution, so is the distribution of the lossy or noisy observation $Y$, for which a sufficient statistic is its \emph{type}.}
 to consider permutation-invariant distributions and the relevant parameter is the Hamming weight of the input string, denoted by $\theta$, which is distributed according a distribution $\pi$ supported on the parameter space $\Theta=\{0,1,\ldots,d\}$. The goal, in turn, is to estimate $\iprod{\pi}{e_0} = \pi(0)$. Each sample is sufficiently summarized into their \emph{types}:
%parameter space $\Theta = \{0,\ldots,d\}$ in both, the linear functional to be estimated is given by $h=e_0$, while
\begin{itemize}
	\item For lossy population recovery: $\calX=\{0,\ldots,d\}^2$ and $X=(U,V)$, where $U$ and $V$ denote the 
	number of ones and zeros, respectively, in the output. More precisely, we have 
	\begin{equation}
	X|\theta \sim \Binom(\theta,\bar\epsilon)\otimes \Binom(d-\theta,\bar\epsilon).
	\label{eq:bec}
	\end{equation}
	
	\item For noisy population recovery: $\calX=\{0,\ldots,d\}$ where $X$ is the number of ones in output, and so the model is given by
	\begin{equation}
	X|\theta \sim \Binom(\theta,\bar\epsilon) * \Binom(d-\theta,\epsilon)
	\label{eq:bsc}
	\end{equation}
\end{itemize}
\end{remark}

\begin{remark}
\label{rmk:hellinger-preview}
As will be evident from the proof, the square-root gap in the LP characterization \prettyref{eq:dual} is due the usage
of the bound $\TV(P^{\otimes n}, Q^{\otimes n}) \leq n\TV(P,Q)$, which is often loose. 
To close this gap, we resort to the Hellinger distance and for lossy population recovery we show in \prettyref{sec:bec} that
\[
R_n = \delta\pth{\frac{1}{\sqrt{n}}}^2 \polylog(n).
\]	
For noisy population recovery, it turns out that $\delta(t)$ is exponentially small in $\polylog(\frac{1}{t})$ and hence
\prettyref{eq:dual} is sufficiently tight (see \prettyref{sec:bsc}).
\end{remark}


\begin{proof}[Proof of \prettyref{thm:dual}]
To prove the right-hand inequality in~\eqref{eq:dual} we consider the following estimator
\begin{equation}
\hat F(X_1,\ldots,X_n) = \frac{1}{n}\sum_{i=1}^n g(X_i)
\label{eq:hatF}
\end{equation}
for some $g\in\reals^\calX$. 
 Then
\[
\Expect_\pi[\hat F(X_1,\ldots,X_n)] = \sum_{\theta \in\Theta} \pi(\theta) \sum_{x \in \calX} g(x)P_\theta(x) = \pi^\top \Phi^\top g = \Iprod{\pi}{\Phi^\top g}
\]
and the bias is
\[
|\Expect_\pi[\hat F] - F(\pi)| \leq \|\pi\|_1\|\Phi^\top g-h\|_\infty = \|\Phi^\top g-h\|_\infty.
\]
For variance,
\[
\var_\pi(\hat F) = \frac{1}{n} \var_\pi(g(X)) \leq \frac{1}{n} \|g\|_\infty^2.
\]
This shows
\begin{equation}\label{eq:dy1}
	\sqrt{R_n} \le \sup_\pi \left(\EE_\pi [|\hat F - F(\pi)|^2]\right)^{1\over 2} \le \|\Phi^\top g-h\|_\infty +
\frac{1}{\sqrt{n}} \|g\|_\infty\,.
\end{equation}
We now optimize the right-hand side of~\eqref{eq:dy1} over all $g$ as follows:
	\begin{align}	
		& ~  \min_{g\in \mreals^\calX} \|\Phi^\top g - h\|_{\infty} + \frac{1}{\sqrt{n}} \|g\|_\infty
			\label{eq:dy2a}\\
	= & ~ \min_{g} \max_{\|y\|_1\leq 1,\|z\|_1\leq 1} \Iprod{y}{\Phi^\top g - h} + \frac{1}{\sqrt{n}} \Iprod{z}{g} 
			\label{eq:dy2}\\
	= & ~ \min_{g} \max_{\|y\|_1\leq 1,\|z\|_1\leq 1} \iprod{\Phi y + \frac{1}{\sqrt{n}} z }{g} - \iprod{y}{h} 
			\label{eq:dy3}\\
	= & ~  \max_{\|y\|_1\leq 1,\|z\|_1\leq 1} \min_{g } \iprod{\Phi y + \frac{1}{\sqrt{n}} z }{g} - \iprod{y}{h} 
			\label{eq:dy4}\\
	%= & ~  \max_{\substack{\|y\|_1\leq 1\\\|\Phi y\|_1\leq 1/\sqrt{n}}} - \iprod{y}{h} 
	= & ~  \max_{\|y\|_1\leq 1, \|\Phi y\|_1\leq 1/\sqrt{n}} \iprod{y}{h} = \delta\left({1\over \sqrt{n}}\right),
			\label{eq:dy5}
	\end{align}
where in~\eqref{eq:dy2a} we write $\min$ since the optimization can clearly be restricted to a suitably large
$\ell_\infty$-box, \eqref{eq:dy2} is by the dual representation of norms,~\eqref{eq:dy3} is by linearity,~\eqref{eq:dy4}
is by von Neumann's minimax theorem for bilinear functions, and~\eqref{eq:dy5} follows since the inner minimization
in~\eqref{eq:dy4} is $-\infty$ unless $\Phi y + \frac{1}{\sqrt{n}} z = 0$. In fact, the equality of \prettyref{eq:dy2a} and \prettyref{eq:dy5} also follows from the strong duality of finite-dimensional LP.

To prove the left-hand bound in~\eqref{eq:dual}, we first introduce an auxiliary linear program:
	\begin{equation}
	\tilde{\delta}(t) \triangleq \max_\Delta \{\iprod{\Delta}{h}: \|\Delta\|_1\leq 1, \iprod{\Delta}{\ones}=0,
	\|\Phi \Delta\|_1\leq t\}\,,
	\label{eq:LP-Gt}
	\end{equation}
where $\Phi$ and $\Delta$ are as in~\eqref{eq:LP-G}. 

We recall the basics of the Le Cam's two-point method~\cite{Lecam86}. If there exist two priors on $\Theta$, under which the distributions of the samples are not perfectly distinguishable, i.e., of a small total variation, then the separation in the functional values constitutes a lower bound that holds for all estimators.
Specifically, for estimating linear functionals under the quadratic risk, we have \cite{Lecam86}
\begin{equation}
R_n \geq \frac{1}{8}  \max_{\pi,\pi'} \iprod{\pi-\pi'}{h}^2 (1-\TV((\Phi \pi)^{\otimes n},(\Phi \pi')^{\otimes n}),
\label{eq:lc-tv}
\end{equation}
where $\pi,\pi'$ are probability vectors on $\Theta$.
 Since  $\TV((\Phi \pi)^{\otimes n},(\Phi \pi')^{\otimes n}) \leq n \TV(\Phi \pi,\Phi \pi')$, we have
\begin{equation}\label{eq:dy7}
R_n \geq \frac{1}{16} \pth{ \max_{\pi,\pi'}\sth{\iprod{\pi-\pi'}{h}: \TV(\Phi \pi,\Phi \pi') \leq \frac{1}{2n}} }^2.
\end{equation}
Now, we observe that 
\begin{equation}\label{eq:dy6}
	\max_{\pi,\pi'}\sth{\iprod{\pi-\pi'}{h}: \TV(\Phi \pi,\Phi \pi') \leq \frac{1}{2n}} = 2 \tilde \delta \left({1\over
2n}\right)\,.
\end{equation}
Indeed, the optimizer $\Delta$ in~\eqref{eq:LP-Gt} can clearly be chosen so that $\|\Delta\|_1=1$. Next, decompose $\Delta =
\Delta_+ - \Delta_-$, where $\Delta_{\pm}(x) \eqdef \max(\pm\Delta(x), 0)$. From $\iprod{\Delta}{1}=0$ we conclude
that $\pi=2\Delta_+$ and $\pi'=2\Delta_-$ are valid probability distributions on $\Theta$ and, furthermore,
$$ \TV(\Phi \pi, \Phi \pi') = \|\Phi \Delta\|_1,\quad \Iprod{\pi - \pi'}{h} = 2\iprod{\Delta}{h}\,.$$
For the reverse direction, simply take $\Delta = {1\over2}(\pi-\pi')$.

Overall, from~\eqref{eq:dy7}-\eqref{eq:dy6} we get
$$ R_n \geq {1\over 4} \tilde\delta\left({1\over 2n}\right)^2\,.$$
To complete the proof the lower-bound in~\eqref{eq:dual} we invoke property 2 (to convert to $\delta(t)$) and property 1 (with $\lambda = 1/2$) from the following lemma (proved in \prettyref{app:aux}).
\end{proof}



\begin{lemma}[Properties of $\delta(t)$ and $\tilde\delta(t)$]
\label{lmm:aux-dual}
\begin{enumerate}
	\item For any $\lambda \in [0,1]$ we have 
		$$ \delta(\lambda t) \ge \lambda \delta(t), \qquad \tilde \delta(\lambda t) \ge \lambda \tilde
		\delta(t)\,.$$
	\item Assuming that there exist $\theta_{\pm}$ such that $h(\theta_+)\ge0\ge h(\theta_-)$ we have 
		\begin{equation}\label{eq:deltas}
			\tilde\delta(t) \le \delta(t) \le 2 \tilde\delta(t)\,.
		\end{equation}		
	\item For any non-constant $h$, there exists $C=C(h)>0$ such that\footnote{This property is not used for establishing \prettyref{thm:dual}. We prove it because it implies that $1/n$ (parametric rate) is always a lower bound in~\eqref{eq:dual}.} 
		$$ \tilde \delta(t) \geq C(h) t.$$
\end{enumerate}
\end{lemma}


\begin{remark}
\label{rmk:highprob}	
	Although \prettyref{thm:dual} is in terms of the mean-square error, it is easy to obtain high-probability bound using standard concentration inequalities.
	Consider the estimator \prettyref{eq:hatF} with $g$ being the solution to the LP \prettyref{eq:LP-G} with $t=\frac{1}{\sqrt{n}}$. Since
	the bias satisfies $|\Expect[\hat F-F]| \leq  \delta(\frac{1}{\sqrt{n}})$ and the standard deviation is at most $\frac{1}{\sqrt{n}}\|g\|_\infty \leq  \delta(\frac{1}{\sqrt{n}})$, Hoeffding inequality implies the Gaussian concentration
	$\Prob[|\hat F-F| \geq t \delta(1/\sqrt{n})] \leq \exp(-c t^2)$ for all sufficiently large $t$ and some absolute constant $c$.
\end{remark}



\iffalse
\section{Statistical lower bound for lossy population recovery}
\begin{theorem}
%\label{thm:}
%For any estimator $\hat{p_0}$ that depends on the number of ones in $Y^{(1)},\ldots,Y^{(n)}$, we have
\[
\inf_{\hat{p_0}}\sup_P \Expect_P[(\widehat{p_0} - p_0)^2] \gtrsim n^{ - E(\epsilon)} \mathrm{polylog}(n),
\]
where $E(\epsilon) = \min\{\frac{1-\epsilon}{\epsilon},1\}$.
%$E(\epsilon) = \frac{\log \frac{1+\epsilon}{\epsilon}}{\log \frac{1+\epsilon}{1-\epsilon}}$.
\end{theorem}

%Todo: the above lower bound needs to be improved significantly.
%\begin{enumerate}
	%\item The current lower bound is proved for estimating $p_0$ based on observing the number of ones. In general, one could also use the number of zeros. 
	%\item The extra ``2'' in the lower bound comes from the usual $1/n$ versus $1/\sqrt{n}$ gap. The current argument relies on $\TV(P^{\otimes n}, Q^{\otimes n}) \leq n \TV(P,Q)$. This is usually loose. Instead one expects a quadratic behavior, for example, by showing that when we choose $\delta = \frac{1}{\sqrt{n}}$, $H^2\sim \TV^2 \sim D$, and the hypotheses are not testable.
%\end{enumerate}



We invoke Le Cam's two-point argument. The square of the following is a lower bound on the minimax MSE for estimating $p_0$ based on the number of ones:
\begin{align*}
\max & ~ p_0 - q_0	\nonumber \\
\text{s.t.} & ~ \left\| \pth{\sum_{j \geq 0} p_j \Binom(j,\bar{\epsilon})}^{\otimes n} -  \pth{\sum_{j \geq 0} q_j \Binom(j,\bar{\epsilon})}^{\otimes n} \right\|_1 \leq 0.5\\
& ~ p, q \in \calM(\integers_+)
\end{align*}
A relax scalar version is
\begin{align}
\max & ~ p_0 - q_0	\nonumber \\
\text{s.t.} & ~ \left\| \sum_{j \geq 0} (p_j-q_j) \Binom(j,\bar{\epsilon})\right\|_1 \leq \delta 	\\
& ~ p, q \in \calM(\integers_+) \label{eq:mintv_orig}
\end{align}
where $\delta \sim 1/n$. Equivalently,
\begin{align*}
\max & ~ x_0 \nonumber \\
\text{s.t.} & ~ \left\| \sum_{j \geq 0}	x_j \Binom(j,\bar{\epsilon})\right\|_1 \leq \delta\\
& ~ \|x\|_1 \leq 2\\
 & ~ \iprod{x}{\ones} = 0
\end{align*}
Let us consider the finite-dimensional version. Fix $d$ and consider the upper triangular matrix $\Phi \in \reals^{(d+1)\times (d+1)}$ given by
\[
\Phi_{ij} = 
\begin{cases}
\binom{j}{i} \bar{\epsilon}^i \epsilon^{j-i}  & i \leq j\\
 0 & i > j\\
\end{cases}
\]
Then our main problem is
\begin{equation}
\begin{aligned}
A_d(\delta) \triangleq
\max & ~ x_0 \\
\text{s.t.} & ~ \left\| \Phi x \right\|_1 \leq \delta\\
& ~ \|x\|_1 \leq 2\\
 & ~ \iprod{x}{\ones} = 0
\end{aligned}
\label{eq:main}
\end{equation}



The inverse of this matrix $B \triangleq \Phi^{-1}$, which is upper triangular as well, has a simple formula
\begin{equation}
B_{ij} = 
\begin{cases}
\binom{j}{i} \frac{(-\epsilon)^{j-i}}{\bar{\epsilon}^j }  & i \leq j\\
 0 & i > j\\
\end{cases}
\label{eq:phiinv}
\end{equation}
Let $B  = \Big[\begin{smallmatrix}b_0' \\ \vdots \\ b_d'\end{smallmatrix}\Big]$. 
We have the following observation about $B$:
\begin{enumerate}
	\item The first row is given by 
	$b_0 = [1, \frac{-\epsilon}{\bar{\epsilon}}, (\frac{-\epsilon}{\bar{\epsilon}})^2, \ldots, (\frac{-\epsilon}{\bar{\epsilon}})^d]$
	
	\item The sum of each column is equal to one, that is, $B' \ones = \ones$.	
\end{enumerate}
With the change of variable $y = \Phi x$, note that $\iprod{x}{\ones} = \iprod{y}{B'\ones} = \iprod{y}{\ones}$ and 
$x_0 = \iprod{y}{b_0}$. 
We can rewrite the main program \prettyref{eq:main} as
\begin{equation}
\begin{aligned}
A_d(\delta) = \max & ~ \iprod{y}{b_0} \\
\text{s.t.} & ~ \left\| y \right\|_1 \leq \delta\\
 & ~ \iprod{y}{\ones} = 0\\
& ~ \|By\|_1 \leq 2
\end{aligned}
\label{eq:mainy}
\end{equation}
Observe that $|\iprod{y}{b_0}| \leq \|y\|_1 \|b_0\|_\infty$
and
\[
\epsilon \leq \frac{1}{2}
\iff
\frac{\epsilon}{\bar{\epsilon}} \leq 1
\iff
\|b_0\|_\infty = 1,  \quad \forall d 
\]
Therefore we immediately have the following converse (upper bound) for $\epsilon \leq \frac{1}{2}$:
\[
A_d(\delta) \leq \delta, \quad \forall d.
\]


\begin{remark}[Superlinear lower bound]
%\label{rmk:}	
Here is a construction for ${\epsilon} > \frac{1}{2}$: Consider the program \prettyref{eq:mainy}.
Fix some constant $\alpha \in (0,1)$ and $\beta \in \reals$. Let $\tau > 0 $ (which will be proportional to $\delta$). 
Let $d$ be some large number (which will grows as $\log \frac{1}{\delta}$). 
Let
\[
y_i = \tau \begin{cases}
1+\beta  &  i=0\\
(-\alpha)^i & i \in [d]\\
\end{cases}
\]
that is,
$y = \tau (w + \beta e_0)$, where $w_i = (-\alpha)^i$. To fulfill $\iprod{y}{\ones}=0$, we need $\beta = - \iprod{w}{\ones} = \frac{(-\alpha)^{d+1}-1}{1+\alpha} \approx - \frac{1}{1+\alpha}$.
Furthermore,
\begin{itemize}
	\item $\|y\|_1 = \tau(|1+\beta| + \sum_{i=1}^d \alpha^i) =  \tau(\frac{(-\alpha)^{d+1}+\alpha}{1+\alpha} +  \frac{\alpha-\alpha^{d+1}}{1-\alpha} ) \approx \tau \frac{2 \alpha}{1-\alpha^2}$. So choosing  $\tau$ is a constant times $\delta$, namely, $\frac{1-\alpha^2}{2 \alpha} \delta$ satisfies $\|y\|_1 \leq \delta$.
	
	\item Since $By = \tau (B w + \beta B e_0)$ and $B e_0=e_0$, we have $\|By\|_1 \leq \tau \|Bw\|_1 + \tau |\beta|$. Since $\beta$ is a constant and $\tau = \Theta(\delta)$, for $\|By\|_1 \le 2$ it suffices to make sure that $\|Bw\|_1 \leq \frac{2}{\tau} = \Theta(\frac{1}{\delta})$. Note that 
	\[
	(Bw)_i = \sum_{j=i}^d B_{ij} w_j = 
	\sum_{j=i}^d \binom{j}{i} \frac{(-\epsilon)^{j-i}}{\bar{\epsilon}^j }  (-\alpha)^j
	=   \frac{1}{(-\epsilon)^{i}} \sum_{j=i}^d \binom{j}{i} \pth{\frac{\alpha \epsilon}{\bar{\epsilon}}}^j 
	\]
	Therefore
	\begin{align*}
	\|Bw\|_1
	= & ~ \sum_{i=0}^d |(Bw)_i| \\
	= & ~ \sum_{i=0}^d \frac{1}{\epsilon^{i}} \sum_{j=i}^d \binom{j}{i} \pth{\frac{\alpha \epsilon}{\bar{\epsilon}}}^j  = \sum_{j=0}^d \pth{\frac{\alpha \epsilon}{\bar{\epsilon}}}^j   \underbrace{\sum_{i=0}^j \binom{j}{i} \frac{1}{\epsilon^{i}}}_{(1+\frac{1}{\epsilon})^j} \\
= &~	\sum_{j=0}^d \pth{\frac{\alpha (1+ \epsilon)}{\bar{\epsilon}}}^j   \approx \pth{\frac{\alpha (1+ \epsilon)}{\bar{\epsilon}}}^d
	\end{align*}
So $\|By\|_1 \leq 2 $  is guaranteed by $\pth{\frac{\alpha (1+ \epsilon)}{\bar{\epsilon}}}^d \leq \frac{1}{\delta}$.

\item The objective is $\iprod{y}{b_0} = \tau \iprod{w}{b_0} + \Theta(\delta)$, where $\iprod{w}{b_0} = \sum_{i=0}^d \pth{\frac{\alpha  \epsilon}{\bar{\epsilon}}}^i \approx \pth{\frac{\alpha  \epsilon}{\bar{\epsilon}}}^d$, provided that $\alpha > \frac{\bar{\epsilon}}{\epsilon}$ .
\end{itemize}
	
So combining everything, the achievability we get in the end is
\[
\sup\sth{ \delta \pth{\frac{\alpha \epsilon}{\bar{\epsilon}}}^d: 
\pth{\frac{\alpha (1+ \epsilon)}{\bar{\epsilon}}}^d \leq \frac{1}{\delta}, \frac{\bar{\epsilon}}{\epsilon} < \alpha < 1}
= 
\delta^{E({\epsilon})}
\]
with 
\[
E({\epsilon}) = \frac{\log \frac{1+\epsilon}{\epsilon}}{\log \frac{1+\epsilon}{1-\epsilon}} < 1, \quad {\epsilon} \in (1/2,1],
\]
achieved by choosing $\alpha$ arbitrarily close to one. In fact, now I think about it, we probably can simply choose $y$ to be an alternating $\pm 1$, and the resulting achievable bound is $\delta^{E({\epsilon})} \frac{1}{\sqrt{\log \frac{1}{\delta}}}$ which is exact.
\end{remark}
\fi


\section{Lossy population recovery}
	\label{sec:bec}
	
	
Capitalizing on the general framework introduced in \prettyref{sec:general}, we prove the sample complexity bounds for lossy \pop announced in \prettyref{thm:bec}. 
The outline is the following:
\begin{enumerate}
	\item In \prettyref{sec:bec-horo} we obtain sharp bounds on the value of the LP \prettyref{eq:LP-G} in the infinite-dimensional case, with the restriction that the estimator is allowed to depend only on the number of ones in the erased samples (\prettyref{prop:mintv-bec}). In particular, the upper bound on the LP value leads to the sample complexity upper bound in \prettyref{thm:bec} for any dimension $d$.
	\item The lower bound is proved in \prettyref{sec:lp-bec} in two steps:
	(i) By resorting to the Hellinger distance, in \prettyref{lmm:bhel} we remove the square-root gap in the general \prettyref{thm:dual}. 
	(ii) Recall from \prettyref{rmk:type} that it is sufficient to consider estimators that are functions of the number of zeros and ones. To complete the proof, we show that the number of zeros provides negligible information for estimating the probability of the zero vector.	
	\end{enumerate}
	%\item The lower bound is proved in three steps:
	%\begin{enumerate}
		%\item We prove that the lower bound part of \prettyref{prop:mintv-bec} continues to hold in finite dimensions (\prettyref{lem:horo}).
		%The utility for truncation is two-fold: first, strong duality holds for finite-dimensional LP; second, the following Hellinger-based argument does not extend to infinite dimension.
	%\item By resorting to the Hellinger distance, in \prettyref{sec:lp-bec} we remove the square-root gap in the general \prettyref{thm:dual}.
	%\item Recall from \prettyref{rmk:type} that it is sufficient to consider estimators that are functions of the number of zeros and ones. To complete the proof of the lower bound of \prettyref{thm:bec}, we show that the number of zeros provides negligible information for estimating the probability of the zero vector.	
	%\end{enumerate}
	%\end{enumerate}
%\begin{enumerate}
	%\item In \prettyref{sec:bec-horo} we determine the value of the LP \prettyref{eq:LP-G} in the infinite-dimensional case ($d=\infty)$, where the estimator is restricted to be functions of the number of ones (\prettyref{prop:mintv-bec}). In particular, the upper bound on the LP value leads to the sample complexity upper bound in \prettyref{thm:bec} for any dimension $d$.
	%
	%\item To prove the lower bound of \prettyref{thm:bec}, 
	%\begin{enumerate}
		%\item We prove the lower bound part of \prettyref{prop:mintv-bsc} continues to hold in finite dimensions (\prettyref{lem:horo}).
		%The reason for truncation is two-fold (i) strong duality holds for finite-dimensional LP; (ii) the following Hellinger-based argument does not extend to infinite dimension.
		%\item By resorting to the Hellinger distance, we remove the square-root gap in the general result \prettyref{thm:dual}.
		%\item Recall from \prettyref{rmk:type} that it is sufficient to consider estimators that are functions of the number of zeros and ones in the erasured samples. To complete the proof of the lower bound of \prettyref{thm:bec}, 
%\end{enumerate}
%\end{enumerate}




%As a concrete example, we specialize the above framework to the problem of population recovery. First of all, note that the probability of the zero vector is invariant under permutation. This shows that for the worst-case formulation \prettyref{eq:minimaxp0}, the least favorable distribution $p$ is also \emph{permutation-invariant}. 
%Furthermore, if the input string $X$ has a permutation-invariant distribution, so is the distribution of the lossy or noisy observation $Y$, for which a sufficient statistic is its \emph{type}. Therefore, after factoring out the permutation, the relevant parameter is the Hamming weight of the input string, denoted by $\theta$, which is distributed according a distribution $\pi$ supported on the parameter space $\Theta=\{0,1,\ldots,d\}$. The goal, in turn, is to estimate $\iprod{\pi}{e_0} = \pi(0)$.
%Each sample is sufficiently summarized into their joint types, that is:
%\begin{itemize}
	%\item Lossy population recovery: $X=(U,V)$, where $U=\text{number of ones in the output}$ and $V= \text{number of zeros in the output}$. The model is given by
	%\begin{equation}
	%X|\theta \sim \Binom(\theta,\bar\epsilon)\otimes \Binom(d-\theta,\bar\epsilon).
	%\label{eq:bec}
	%\end{equation}
%
	%
	%\item Noisy population recovery: $X=\text{number of ones in output}$. The model is given by:
	%\begin{equation}
	%X|\theta \sim \Binom(\theta,\bar\epsilon) * \Binom(d-\theta,\epsilon)
	%\label{eq:bsc}
	%\end{equation}
	%
%\end{itemize}


\subsection{Solving the linear programming by $H^\infty$-relaxation}
\label{sec:bec-horo}

In this subsection we determine the value of the LP \prettyref{eq:LP-G} for lossy \pop where the estimator is restricted to be functions on the output Hamming weight. 
In view of \prettyref{eq:bec}, to apply \prettyref{thm:dual}, 
%For erasure probability $\epsilon$, 
here $\Phi$ is the transition matrix from the input to the output Hamming weight:
\begin{equation}
\Phi_{ij} = 
P(w(Y)=i |w(X)=j )=
\begin{cases}
\binom{j}{i} (1-\epsilon)^i \epsilon^{j-i}  & i \leq j\\
 0 & i > j\\
\end{cases}
\label{eq:Phi-bec}
\end{equation}
 and the linear functional corresponds to $h=e_0$. In other words, \prettyref{eq:LP-G} reduces to 
\begin{equation}
\delta(t) = \sup_\Delta \sth{\Delta_0: \|\Delta\|_1\leq 1, \left\|\sum_{j\geq 0} \Delta_j \mathrm{Bin}(j,1-\epsilon)\right\|_1\leq t}.
\label{eq:LP-G1}
\end{equation}


For notational convenience, let us define the following ``min-TV'' LP that is equivalent to~\eqref{eq:LP-G1}:
\begin{equation}
t(\delta) \eqdef \inf_\Delta\left\{\left\|\sum_{j\geq 0} \Delta_j \mathrm{Bin}(j,1-\epsilon)\right\|_1: \Delta_0 \ge \delta, \|\Delta\|_1 \le 1
\right\}\,.
\label{eq:mdelta}
\end{equation} 
Clearly we have $\delta(t(\delta))=\delta$. 
%and, thanks to \prettyref{thm:dual}, lower (resp.~upper) bounds on  $t(\delta)$ translate to upper (resp.~lower) bounds on the statistical estimation error.

\begin{prop} 
\label{prop:mintv-bec}
%We have
%$$ \lim_{\delta \to 0} {\log t(\delta)\over \log \delta} = \max\left({\epsilon \over 1-\epsilon}, 1\right)\,. $$
If $\epsilon \leq \frac{1}{2}$, then
\begin{equation}
\delta \leq t(\delta) \leq 2(1-\epsilon) \delta.
\label{eq:mintv-bec1}
\end{equation}
If $\epsilon > \frac{1}{2}$, then
\begin{equation}
\delta^{\frac{\epsilon}{1-\epsilon}}  \leq t(\delta) \leq 
\pth{e\delta \log \frac{1}{\delta} }^{\frac{\epsilon}{1-\epsilon}}
%\pth{\delta \log \frac{1}{\delta} }^{\frac{\epsilon}{1-\epsilon}} (1+o_{\delta\to0}(1))
\label{eq:mintv-bec2}
\end{equation}
where the right inequality holds provided that $\delta < 1/e$.
\end{prop}

\begin{remark}
\label{rmk:Ggamma-bec}	
Thanks to \prettyref{thm:dual}, the lower bound on $t(\delta)$ in \prettyref{prop:mintv-bec} immediately translates into the following upper bound on the MSE of estimating $P_0$ in any dimension:
\[
\sup_{d \geq 1} R^*(n,d) \leq \delta(1/\sqrt{n})^2 \leq n^{- \min\sth{\frac{1-\epsilon}{\epsilon},1}},
\]
without any hidden constants. 
%As mentioned in the beginning of this section, 
The upper bound on $t(\delta)$ require additional work to yield matching minimax lower bounds; this is done in \prettyref{sec:lp-bec}.
\end{remark}

\begin{proof}[Proof of \prettyref{prop:mintv-bec}]
Let $D$ be the open unit disk and $\bar D$ the closed unit disk on the complex plane. For analytic
functions on $D$ we introduce two norms:
	$$ \|f\|_{H^\infty(D)} \triangleq \sup_{z\in D} |f(z)|, \qquad \|f\|_{A} \triangleq \sum_{n\ge 0} |a_n|\,,$$
	where $a_n$ are the Taylor coefficients of $f(z) = \sum_n a_n z^n$. Functions with bounded $A$-norm form a space
	known as the Wiener algebra (under multiplication). It is clear that every $A$-function is also continuous on
	$\bar D$. Furthermore, by the maximal modulus principle,
	any function continuous on $\bar D$ and analytic on $D$ satisfies:
	\begin{equation}
	\|f\|_{H^\infty(D)} = \sup_{z \in \partial D} |f(z)|\,,
	\label{eq:maxmod}
	\end{equation}	
	and therefore:
		\begin{equation}\label{eq:bd1}
			\|f\|_{H^\infty} \le \|f\|_{A}\,.
\end{equation}		
	In general, there is no estimate in the opposite direction;\footnote{That is, the space $A$ is a strict subset of
	$H^\infty(D)$. This is easiest to see by noticing that all functions in $A$ are continuous on the unit
	circle, while $f(z) = {1\over (1-z)^i}$ is in $H^\infty$ but discontinuous on the unit circle. Another 
	example of a function in $H^\infty$ but not in $A$ is
	$f(z)=\exp({1+z\over 1-z})$, but it takes effort to show it is not in $A$. Also note that the linear
	functional $f \mapsto f(1)$ defined on polynomials is bounded in both $A$-norm and $H^\infty(D)$ norm.
	However, in $A$ it admits a unique extension to all of $A$, while in $H^\infty(D)$ there are different
	incompatible extensions (existence is from Hahn-Banach). }
	nevertheless, we can estimate the $A$-norm using the $H^\infty$-norm over a larger domain: Suppose $f\in H^\infty(rD)$ for $r>1$, then 
	\begin{equation}\label{eq:bd2}
		\|f\|_{A} \le \frac{r}{r-1} \|f\|_{H^\infty(rD)}\,.
	\end{equation}	
	Indeed, from Cauchy's integral formula we estimate coefficients $a_n$ as
		\begin{equation}
		 |a_n| \le r^{-n} \|f\|_{H^\infty(rD)}
		\label{eq:cauchy}
		\end{equation}
	and then sum over $n\ge0$ to get~\eqref{eq:bd2}.

	Now, to every sequence $\{\Delta_j: j\ge 0\}$ with finite $\ell_1$-norm, we associate a function in $A$ as
	$$ f(z) \eqdef \sum_{j\ge 0} \Delta_j z^j\,,$$
	which, in case when $\Delta$ is a probability distribution, corresponds its generating function.
	Note that the channel $\Phi$ maps the distribution of the input Hamming weight $w(X)$ into that of the output Hamming weight $w(Y)$ via a linear transformation.
	Equivalently, we can describe the action $\Phi$ on the function $f$ in terms how input generating functions are mapped to that of the output as follows:
\[
\Expect[z^{w(X)}] \overset{\Phi}{\mapsto}  \Expect[z^{w(Y)}]=\Expect[z^{\Binom(w(X),\bar\epsilon)}] = \Expect[(\epsilon z+ \bar\epsilon)^X]
\]
that is, $f(z) \mapsto f(\epsilon z+ \bar\epsilon)$. To this end, define the following operator, also denoted by $\Phi$, as
			\begin{equation}
			(\Phi f) (z) \eqdef f(\epsilon + \bar\epsilon z)\,,
			\label{eq:bec-op}
			\end{equation}
	which is known as a composition operator on a unit disk.\footnote{Despite the simple definition, characterizing properties of such
	operators is a rather difficult task cf.~\cite{cowen1988linear}.} Therefore, the channel maps $\Delta$ linearly into another $\ell_1$-sequence $\Delta' = \sum_j \Delta_j
	\mathrm{Bin}(j,\bar{\epsilon})$, which are exactly the coefficients of $\Phi f$.
		Indeed, $\Delta_j' = \sum_{k\geq j} \Delta_k \binom{k}{j} \bar\epsilon^j \epsilon^{k-j}$ and 
		\[
		\sum_{j \geq 0} \Delta_j' z^j = \sum_{k \geq 0} \Delta_k \sum_{j=0}^k \binom{k}{j} (\bar{\epsilon} z)^j \epsilon^{k-j} = \sum_{k \geq 0} \Delta_k (\bar{\epsilon} z+\epsilon)^k = (\Phi f)(z).
		\]
	Then, with the above identification, the LP \prettyref{eq:mdelta} can be recast as
	\begin{equation}\label{eq:mdef_2}
		t(\delta) = \inf \{\|\Phi f\|_{A}: \|f\|_{A} \le 1, f(0)\ge\delta\}\,.
\end{equation}	
	From \prettyref{eq:bec-op} an important observation is that $\Phi f$ restricts $f$ to a \textit{horodisk} 
	\begin{equation}\label{eq:br4}
		D_\tau  \eqdef \bar\tau+ \tau D = \{z \in \mathbb{C}: |z - \bar\tau| \leq \tau\}
\end{equation}	
which shrinks as $\tau$ decreases from 1 to 0 (see \prettyref{fig:horo}). Thus, $\|\Phi f\|_{H^\infty(D)} = \sup_{z\in D_{\bar{\epsilon}}} |f(z)|$.


\begin{figure}[ht]%
\centering
%\begin{tikzpicture}[scale=1,transform shape,node distance=1cm,auto,>=latex']
\begin{tikzpicture}[scale=2,font=\scriptsize,>=latex']
\draw[blue,thick] (0,0) circle (1);
\draw[red,thick] (1/2,0) circle (1/2);
\draw[thick] (1/3,0) circle (2/3);
\node at (0.8,0.95) {$D=D_1$};
\node at (-0.2,0.65) {$D_{2/3}$};
\node at (0.5,0.3) {$D_{1/2}$};
%\draw (0.15,0) arc (0:45:0.15);
%\draw[-open triangle 45] (0,0) -- (0.707,0.707);
%\draw[dotted] (0.707,0.707) -- (0.707,0) node[below] {$X$};
%\node at (0.2,0.1) {$\Theta$};
%\draw[->] ([shift=(30:1cm)]2,1) arc (30:60:1cm);
\draw[-latex] (-1.4,0) -- (1.4,0);
\draw[-latex] (0,-1.4) -- (0,1.4);
%\draw[blue,fill=blue]  (360/9*\ang:2) circle (0.05);
%\draw[-latex] (-2.2,0) -- (2.2,0) node[right] {$\text{Re}$};
%\draw[-latex] (0,-2.2) -- (0,2.2) node[right] {$\text{Im}$};
\end{tikzpicture}    
\caption{Horodisks.}%
\label{fig:horo}%
\end{figure}

In view of~\eqref{eq:bd1}, it is clear that $t(\delta)$ is lower bounded by
	\begin{equation}\label{eq:br3}
		t_1(\delta) \eqdef \inf \{\|\Phi f\|_{H^\infty(D)}: \|f\|_{H^\infty(D)} \le 1, f(0)\ge\delta\}\,,
	\end{equation}	
	Furthermore, if $\epsilon \leq 1/2$ then $0\in \bar D_{\bar{\epsilon}}$ and thus $t_1(\delta) \ge \delta$.
	This proves the lower bound in \prettyref{eq:mintv-bec1}. To show the upper bound, Take $f(z) = \delta(1-z)$, which is feasible since $f(0)=\delta$ and $\|f\|_{A} = 2 \delta < 1$. Clearly, $(\Phi f)(z) = \delta\bar{\epsilon}(1-z)$ which gives $t(\delta) \le 2 \bar{\epsilon} \delta$. 
	
	
	In the remainder of the proof we focus on the non-trivial case of $\epsilon > 1/2$.
	Note that the M\"obius transform $z \mapsto {z-1\over z+1}$ maps the right half-plane onto the $D$ so that: a) the imaginary axis gets mapped to the unit circle $\partial D$; b) the line $1 + i \mreals$ gets mapped to the horocircle $\partial D_{1/ 2}$ that
	passes through $0$; c) the line ${\epsilon\over \bar{\epsilon}} + i \mreals$ gets mapped to the horocircle $\partial D_{\bar{\epsilon}}$. Then by
	Hadamard's three-lines theorem (see, e.g., \cite[Theorem 12.3]{simon2011convexity}) we have that for any function $f \in H^\infty(D)$:
		\begin{equation}
		\sup_{z\in D_{1/2}} |f(z)| \le \left( \sup_{z\in D} |f(z)| \right)^{1-2\bar{\epsilon}\over \epsilon} 
							\left( \sup_{z\in D_{\bar{\epsilon}}} |f(z)| \right)^{\bar{\epsilon} \over \epsilon}\,.
		\label{eq:threehoro}
		\end{equation}							
	Since any feasible solution $f$ to \eqref{eq:br3} has $f(0) \ge \delta$ and $\|f\|_{H^\infty(D)} \leq 1$,  we conclude that 
		$$ t(\delta) \ge t_1(\delta) \ge \delta^{\epsilon\over \bar{\epsilon}}\,,$$
proving the lower bound in \prettyref{eq:mintv-bec2}. 

To show the upper bound, we demonstrate an explicit feasible solution for \prettyref{eq:mdef_2}. 
Choose $\alpha < 1$ such that 
\begin{equation}
\beta \triangleq \frac{\delta}{1-\alpha} \leq 1.
\label{eq:beta1}
\end{equation}
The main idea is to choose the function so that the comparison inequality \prettyref{eq:threehoro} is tight. To this end, recall that Hadamard three-lines theorem holds with equality for exponential function. 
This motivates us to consider the following mother function 
		$$ g(z) \eqdef \beta^{1+z\over 1-z}\,.$$
	Note that for any $\eta\in\reals$, for the horodisk $D_\eta$ defined in~\eqref{eq:br4}, 
	$z \mapsto \frac{1+z}{1-z}$ maps the horocircle $\partial D_\eta$ back to the straight line ${\bar{\eta}\over \eta} + i \reals$. Since $0 \leq \beta \leq 1$, 
		\begin{equation}
		%\sup_{z\in D_\eta} |g(z)| 
		\| g \|_{H^\infty(D_\eta)} 
		=  \beta^{\inf_{z\in \partial D_\eta} \text{Re}(\frac{1+z}{1-z})} 
		= \beta^{\bar \eta \over \eta}\,.
		\label{eq:gDeta}
		\end{equation}
			In particular, since $D=D_1$, by setting $\eta=1$ we get $\|g\|_{H^\infty(D)} = 1$.
	Next, for $\alpha \in (0,1)$ define the scaled function
		\begin{equation}
		f_\alpha(z) \eqdef (1-\alpha) g(\alpha z)\,,
		\label{eq:scale}
		\end{equation}		
		which is a feasible solution to \prettyref{eq:mdef_2}. Indeed, $f_\alpha(0) = (1-\alpha) g(0) = (1-\alpha)\beta = \delta$, by definition. 
	Furthermore, invoking the estimate~\eqref{eq:bd2} with $r=1/\alpha$, we have
		\begin{equation}
		\| f_\alpha \|_{A} \leq \frac{1}{1-\alpha} \| f_\alpha \|_{H^\infty(D/\alpha)} = \| g \|_{H^\infty(D)} = 1 \,.
		\label{eq:feas1}
		\end{equation}		
	%Since $\alpha D_{\bar{\epsilon}} \subset D_\eta$ (and also these two disks are concentric!), where $\eta = 1-\alpha\bar
	%\bar{\epsilon}$, we have again from~\eqref{eq:bd2}
	Setting $\eta = 1-\alpha {\epsilon}$ and $r = \frac{\eta}{\alpha\bar{\epsilon}} > 1$ since $\alpha < 1$, we have again from the reverse estimate~\eqref{eq:bd2}	
		\begin{equation}
		\| \Phi f_\alpha \|_{A} \leq \frac{1}{1-\frac{1}{r}} \| \Phi f_\alpha \|_{H^\infty(rD)}
		= \frac{1-\alpha}{1-\frac{1}{r}} \| g \|_{H^\infty(\alpha \epsilon+\alpha\bar{\epsilon} rD)}
		= (1-\alpha\epsilon) \| g \|_{H^\infty(D_\eta)}.
		%\overset{\prettyref{eq:gDeta}}{\le} (1-\alpha\epsilon) \beta^{\bar \eta \over 		\eta}\,.$$
		\label{eq:feas2}
		\end{equation}		
By		\prettyref{eq:gDeta} and let $\alpha=1-b$, we have
\begin{align}
\| \Phi f_\alpha \|_{A}
\leq & ~ (1-\alpha\epsilon) \beta^{\bar \eta \over 		\eta} = (1-\alpha \epsilon) \pth{\frac{\delta}{1-\alpha}}^{\frac{\alpha\epsilon}{1-\alpha\epsilon}} 
%\\
%\leq & ~ \exp\sth{\frac{\epsilon}{1-\epsilon} \log \frac{\delta}{b} \pth{1 - \frac{b}{1-(1-b)\epsilon}} }
\leq 	\exp\sth{\frac{\epsilon}{1-\epsilon} (1-b) \log \frac{\delta}{b} }\label{eq:feas3}
\end{align}
Choosing $b = \frac{1}{\log \frac{1}{\delta}}$ fulfills \prettyref{eq:beta1} and
yields the upper bound in \prettyref{eq:mintv-bec2}.
	%Now, we can not yet use $f_\alpha$ to upper bound $t(\delta)$, as redefined in~\eqref{eq:mdef_2}, because
	%$f_\alpha(1) \neq 0$. In fact we have:
		%$$ f_\alpha(1) = (1-\alpha) \delta^{1+\alpha \over 1-\alpha}\,.$$
	%Then it is clear that when $\alpha$ is sufficiently close to $1$ 
	%we have $f_\alpha(1) \ll \delta$ and $f_\alpha(1) \ll \delta^{\bar \eta
	%\over \eta}$, since as $\alpha \to 1$ we have ${\bar \eta\over \eta } \to {\epsilon \over \bar{\epsilon}}$. 
	%Furthermore, $f(0)=(1-\alpha)(\delta - \delta^{\frac{1+\alpha}{1-\alpha}})$.
	%Thus, we can set $f = f_\alpha - f_\alpha(1)$ in~\eqref{eq:mdef_2} and get
		%$$ t(\delta) \le C_\alpha \delta^{\bar \eta \over \eta}\,.$$
	%Finally, sending $\alpha \to 1$ finishes
	%the proof.
\end{proof}


\begin{remark}
\label{rmk:ms13}	We compare the proof techniques of the lower bound part of \prettyref{prop:mintv-bec} with that
of \cite{MS13}.  The sample complexity bound \prettyref{eq:ms13} is also obtained by bounding the value of the dual LP
from above via the $H^\infty$-norm relaxation. The suboptimality of the exponent
$\frac{1}{1-\epsilon}\log\frac{2}{1-\epsilon}$ in \prettyref{eq:ms13} seems to stem from the application of the Hadamard
three-circle theorem, which is applicable to three concentric circles centered at the origin. In comparison, the sharp
result in \prettyref{prop:mintv-bec} is obtained by comparing the value of any feasible $f$ on three horocircles (see
\prettyref{fig:horo}), which are images of three horizontal lines under the M\"obius transform and Hadamard three-lines
theorem is readily applicable yielding the optimal exponent $\frac{\epsilon}{1-\epsilon}$.  The upper bound part of
\prettyref{prop:mintv-bec} is new. %, obtained by choosing a near-optimal solution that is directly motivated by the
%equality case of Hadamard three-lines theorem.
\end{remark}




\apxonly{
The following is the truncated version of \prettyref{prop:mintv-bec}.
\begin{lemma}\label{lem:horo} 
Fix $\epsilon > {1\over 2}$. For $d \in \naturals$, define the finite-dimensional version of \prettyref{eq:mdelta}:
\begin{align}
 t(\delta,d) \eqdef
 & ~ \inf\left\{\left\|\sum_{j=0}^d \Delta_j \mathrm{Bin}(j,1-\epsilon)\right\|_1: \Delta\in\reals^{d+1}, \Delta_0 \ge \delta, \|\Delta\|_1 \le 1
\right\} \nonumber \\
= & ~ \inf \{\|\Phi f\|_{A}: \|f\|_{A} \le 1, f(0)\ge\delta, \deg f \leq d\}. \label{eq:mdelta-d}
\end{align}
Then for any $\delta < 1/e$, there exists $d_0\in\naturals$ such that 
\begin{equation}
d_0 \le \frac{1}{1-\epsilon}  \log^2 {1\over \delta}
\label{eq:d0}
\end{equation}
and
\begin{equation}
t(\delta/2,d_0) \leq \pth{e \delta \log \frac{1}{\delta} }^{\frac{\epsilon}{1-\epsilon}}
\label{eq:horo}
\end{equation}
%For every $\delta \le \delta_0(\epsilon)$ and $\alpha > \alpha_0(\epsilon)$
%there exists a degree-$d_0$ polynomial $f(z)$ such that a) $\|f\|_{H^\infty(D)} \le 1$, b) $f(1)=0$, c) $f(0) \ge
%{\delta \over 8}$ and 
	%\begin{equation}\label{eq:dbl1}
		%\sup_{z\in D} |f(\bar \epsilon z + \epsilon)| \le \delta^{E(\alpha \epsilon + \bar\alpha/2)}\,,
%\end{equation}	
	%where $E(\epsilon) = {\epsilon\over 1-\epsilon}$. Furthermore, we have
	%$$ d_0 \le C_\epsilon  {\log {1\over \delta}\over \log{1\over \alpha}} + {\log (1-\alpha)\over \log \alpha}\,.$$
\end{lemma}
\begin{proof}
Let $\beta = \delta/(1-\alpha)$ with $\alpha \in (0,1)$ to be specified.
	Let $g(z) = \beta^{1+z\over 1-z}$ as in the proof of \prettyref{prop:mintv-bec}, whose Taylor expansion is given by $g(z) = \sum_{n\ge 0} a_n z^n$ . 
		Let 	$\tilde g(z) = \sum_{0 \le n \le d_0} a_n z^n$. 
	The proof follows the same program as that of \prettyref{prop:mintv-bec}, with $\tilde g$ replacing $g$.
	 Similar to \prettyref{eq:scale}, define 
	\[
	\tilde f_\alpha(z) \eqdef \frac{1}{2} (1-\alpha) \tilde g(\alpha z).
	\]
	Then we have
	$\tilde f_\alpha(0)=\delta/2$, since $\tilde g(0) = g(0)=\beta$.
	%(a) $\tilde f_\alpha(0)=\delta/2$, since $\tilde g(0) = g(0)=\beta$;
	%(b) $\|\tilde f_\alpha\|_{A} = \|(1-\alpha) \tilde g(\alpha z)\|_{A}/2$;
	%(c) $\|\Phi \tilde f_\alpha\|_{A} \leq \|\tilde g\|_{H^\infty(D_\eta)}/2$ by \prettyref{eq:feas2}, where $\eta = 1-\alpha \epsilon$.
	Furthermore, by \prettyref{eq:gDeta}, $\| g\|_{H^\infty(D_\eta)}\leq \beta^{(1-\eta)/\eta}$  and  in particular $\|g\|_{H^\infty(D)} = 1$.
	By Cauchy's inequality \prettyref{eq:cauchy}, the Taylor series coefficients of $g$ satisfy $|a_n| \leq \|g\|_{H^\infty(D)} = 1$ and hence	
\begin{equation}\label{eq:dbl5}
			\|\tilde g(\alpha z) - g(\alpha z)\|_{A} \le {\alpha^{d_0+1}\over 1-\alpha} \eqdef \kappa\,.
\end{equation}		
	We later will choose $d_0$ so that $\kappa \le \beta^{(1-\eta)/\eta} \leq 1$. 
	Since $\|(1-\alpha) g(\alpha z)\|_A \leq \|g\|_{H^\infty(D)} = 1$ by \prettyref{eq:feas1}, we have 
	$\|\tilde f_\alpha\|_{A} \leq \|(1-\alpha) g(\alpha z)\|_{A}/2 + \|g(\alpha z) - \tilde g(\alpha z)\|_{A}/2 \leq 1$ 
	and hence $\tilde f_\alpha$ is a feasible solution for $t(\delta/2,d)$. 
	
	To bound the value of the objective function,
	note that $\|\Phi \tilde f_\alpha\|_{A} \leq \|\tilde g\|_{H^\infty(D_\eta)}/2$ by \prettyref{eq:feas2}, where $\eta = 1-\alpha \epsilon$.
	Since $D_\eta \subset D$ we have 
	$\|\tilde g\|_{H^\infty(D_\eta)} \leq \|\tilde g\|_{H^\infty(D_\eta)} + \|g-\tilde g\|_{H^\infty(D)} \leq \beta^{(1-\eta)/\eta} + \kappa \leq 2 \beta^{(1-\eta)/\eta}$
	and hence $\|\Phi \tilde f_\alpha\|_{A} \leq \beta^{(1-\eta)/\eta}$.
	Again, choose $\alpha = 1 - \frac{1}{\log(1/\delta)}$ gives the same upper bound as in \prettyref{eq:mintv-bec2}. 	
	The choice of $d_0$ in \prettyref{eq:d0} ensures
	\[
	\kappa=\frac{\alpha^{d_0+1}}{1-\alpha} \leq \beta^{(1-\eta)/\eta}=\pth{\frac{\delta}{1-\alpha}}^{\frac{\alpha \epsilon }{1-\alpha \epsilon }},
	\]
	in view of the fact that $\log\frac{1}{1-b}\geq b$ for $b\in(0,1)$ and $\log x < x$ for $x>0$. 
	 \nb{details: need 
	$d_0 + 1 \geq (\log \frac{1}{b} + \frac{\alpha \epsilon }{1-\alpha \epsilon } \log \frac{1}{\delta}) \frac{1}{\log \frac{1}{1-b}}$, where $b=1/\log(1/\delta)$.
	Then bound $\log\log$ by $\log$ and $\frac{\alpha \epsilon }{1-\alpha \epsilon }$ by $\frac{\epsilon }{1-\epsilon }$.}
\end{proof}
}



\iffalse
\nb{Since the argument in \prettyref{sec:lp-bec} does not work if the channel output is the pair of the numbers of zeros and ones, the following lemma will no longer be needed. Furthermore, the following lemma seems to lose more log factors than the Hellinger argument.}
\begin{lemma} Let $f$ be a degree $d_0$ polynomial such that $\|f\|_{H^\infty(D)} \le 1$ and $\max_{z\in D}|f(\bar\epsilon z +
\epsilon)| = \delta$. Then
	$$ L_\epsilon(f) \eqdef \inf_{d \ge d_0} \sup_{z_0, z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right| \le C_\epsilon \left(d_0^3  \log^2 {1\over
	\delta}\right) \cdot \delta\,.$$
	We also clearly have (by letting $z_0 \to 1$) 
	$$ L_\epsilon(f) \ge d_0^2 \delta\,.$$
\end{lemma}
\begin{proof} We will use the following property: For any $r>1$ and any degree-$d_0$ polynomial $p$ we have
\begin{equation}\label{eq:blg1}
		\max_{z\in D} |p(zr)| \le r^{d_0} d_0 \max_{z\in D} |p(z)|\,,
\end{equation}	
which follows from the Cauchy inequality $|[z^k] p(z)| \le \sup_{z\in D} |p(z)|$, that is, \prettyref{eq:cauchy} with $r=1$.


Let us denote $f(z) = \sum_{n\le d_0} a_n z^n$ and 
$$ M_d \eqdef \sup_{z_0, z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right| \,.$$

Fix some $\theta \in (0,1)$ (it will be very close to 1 in the end).  We will separate two cases: 

Case 1. If $\theta < |\bar \epsilon z_0 + \epsilon| \le 1$ then we first notice that disk described by the image of 
	$$ z_1 \mapsto { \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon} $$
	as $z_1$ ranges over $D$
	is contained inside the disk
	$$ z_1 \mapsto \bar \epsilon z_1 + \epsilon$$
	as $z_1$ ranges over ${1-\theta \epsilon\over 1-\epsilon} D$. Thus by~\eqref{eq:blg1} we get
	$$ \sup_{z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right| \le
		d^2 d_0 \left({1-\theta \epsilon\over 1-\epsilon}\right)^{d_0} \delta $$
	and in view of ${1-\theta \epsilon\over 1-\epsilon} \le \theta^{-{\epsilon\over \bar\epsilon}-1}$ we can
	continue as
	$$ \sup_{z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right|\le d^2 d_0 \theta^{-c d_0} \delta $$
	for some $c>1$. 

Case 2. If $|\bar\epsilon z_0 + \epsilon| \le \theta$ then we upper bound 
	$$ \sup_{z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right| \le
		d^2 \sup_{z_1 \in D} \sum_{n\le d_0} |a_n| \theta^{d-n} |\bar \epsilon z_1 + \epsilon|^n \le d^2 d_0
		\theta^{d-d_0} \|f\|_{H^\infty(D)} \le d^2 d_0 \theta^d \theta^{-cd_0}\,.$$
	where the last step is due to $c>1$.
	
	Thus, to summarize we get:
	$$ M_d \le 
		d^2 d_0 \theta^{-cd_0} \cdot \max \left\{\theta^d, \delta\right\}\,.$$
	Now choose $\theta$ and $d$ so that
\begin{align}  \theta^d &= \delta \\
	d &= d_0 \ln {1\over \delta} 
\end{align}
	Then we get $\theta^{-c d_0} = e^c$ and thus
		$$ M_d \le d_0^3  \left(\ln {1\over \delta}\right)^2 e^c \delta\,, $$
	as claimed.
\end{proof}
\fi


\subsection{Tight statistical lower bounds}
\label{sec:lp-bec}
Based on the general theory in \prettyref{thm:dual}, to prove the minimax lower bound announced in \prettyref{thm:bec}, there are two things to fix:
%(a) why it is sufficient to focus on the joint type (the number of $0$'s and $1$'s);
%(b) why the number of $1$ provides negligible information for estimating the parameter $p_0$;
%(c) how to fix the square-root gap in the general lower bound in \prettyref{thm:dual}.
\begin{enumerate}[(a)]
	%\item why it is sufficient to focus on the joint type (the number of $0$'s and $1$'s);
\item why numbers of $0$'s provides negligible information for estimating the probability of the zero vector;
%parameter $P_0$;
\item how to fix the square-root gap in the general lower bound in \prettyref{thm:dual}.
\end{enumerate}




%\subsection{Removing the square-root gap via Hellinger}
	%\label{sec:}

\
We start with the second task. Recall the relation between the total variation and the Hellinger distance \cite{Tsybakov09}
\begin{equation}
\frac{1}{2}H^2\le \TV \le H\sqrt{1-H^2/4}.
\label{eq:TVH}
\end{equation}
and the tensorization property of the Hellinger distance 
\[
H^2(P^{\otimes n}, Q^{\otimes n}) = 2 -2 (1- H^2(P,Q)/2)^n.
\]
Applying both to the original Le Cam's method  \prettyref{eq:lc-tv}, after simple algebra we get the following minimax
lower bound (still for estimators based on the number of ones only):
\begin{equation}
\sqrt{R_n} \ge {1\over 4} \max_{\pi,\pi'}\left\{\pi(0)-\pi'(0): H^2(\Phi \pi,\Phi \pi') \leq {1\over 2n} \right\}\,.
\label{eq:hellinger}
\end{equation}
for any constant $C$, where $\Phi$ is given in \prettyref{eq:Phi-bec}, i.e.
$\Phi \pi = \Expect_{\theta\sim \pi}[ \Binom(\theta,\bar\epsilon)]$.

It remains to show that for specific models, e.g., lossy \pop, we have the following locally quadratic-like behavior: 
given the optimal $\Delta$ to \prettyref{eq:mdelta}, one can find feasible $\pi$ and $\pi'$ for \prettyref{eq:hellinger} so that $\pi-\pi'\approx \Delta$ and 
%pair $\Phi \pi$ and $\PhiQ$ fulfills the lower bound
$H^2(\Phi \pi,\Phi \pi') \lesssim \TV(\Phi \pi,\Phi \pi')^2$, such that the lower bound in \prettyref{eq:TVH} is essentially tight.
 %\asymp \|\Phi (\pi-\pi')\|_1^2$.
This is done in the next lemma.
To construct the pair $\pi$ and $\pi'$, the main idea is to perturb a fixed distribution $\mu$ by $\pm \Delta$. In this case it turns out the center $\mu$ can be chosen to be a geometric distribution.
Furthermore, recall that the near-optimal solution used in \prettyref{prop:mintv-bec} deals with infinite sequence $\Delta$ in \prettyref{eq:mdelta},
 which, in the context of population recovery, corresponds to input strings of infinite length.\footnote{For the simple case of $\epsilon \leq 1/2$, the construction in \prettyref{prop:mintv-bec} is a degree-1 polynomial. This amounts to considering a single bit and using a pair of Bernoulli distributions to establish the optimality of the parametric rate $1/n$, which is standard.} 
It turns out that it suffices to consider $d = \Omega(\log^2\frac{1}{\delta})$.



\begin{lemma} 
\label{lmm:bhel}
Fix $\epsilon > {1\over 2}$.
For every $\delta < \frac{1}{2e}$, 
 %there exist $\delta_0(\epsilon)>0$ and a constant $C=C(\epsilon)>0$
%satisfying the following. For all $\delta < \delta_0$
there exists a pair of probability distributions $\pi$ and $\pi'$ on $\mathbb{Z}_+$ such that $|\pi(0) - \pi'(0)|\ge
\delta$ and
\begin{equation}\label{eq:bhel}
	H^2(\Phi \pi, \Phi\pi') \le C \pth{e\delta \log \frac{1}{\delta} }^{\frac{2\epsilon}{1-\epsilon}},
\end{equation}
where $C =4$.
Furthermore, if $C=36$, both distributions can be picked to be supported on $\{0,\ldots,
d\}$ provided that $d \geq \frac{2\epsilon}{1-\epsilon}\log^2\frac{1}{\delta}$.
\end{lemma}
\begin{proof} Let $g,\beta,\alpha,b,\eta,r$ be as in the proof of \prettyref{prop:mintv-bec}. 
In particular, $\alpha=1-\frac{1}{\log \frac{1}{\delta}}$, $\eta=1-\alpha\epsilon$, $\beta=\delta\log\frac{1}{\delta}$, and $r=\frac{1-\alpha\epsilon}{\alpha\bar\epsilon}$.
Set
$$ f(z) = \bar\alpha g(\alpha z) - \bar\alpha g(\alpha)\,.$$
Let $\Delta_k \eqdef [z^k] f(z)$.
Then $\Delta_0=\bar\alpha g(0)-\bar\alpha g(\alpha) = \delta - (\delta\log\frac{1}{\delta})^{2\log\frac{1}{\delta}-1}$
and $\Delta_k = \bar\alpha \alpha^k [z^k] f(z)$.
Since $\delta\leq 1/(2e)$ by assumption, we have
%Note that $g(\alpha) = \beta^{1+\alpha\over 1-\alpha} \le \beta^{\bar \eta\over \eta} \le {\delta\over2}$ (provided
%$\delta <\delta_0$) and, thus, we have
$$ \delta > \Delta_0 \ge {\delta\over 2}\,.$$
Furthermore, recall from the proof of \prettyref{prop:mintv-bec} that $\|g\|_{H^\infty(D)} = 1$
and thus
\begin{equation}\label{eq:bh1}
	|\Delta_k| \le \bar \alpha \alpha^k\,,\qquad k \ge 1\,.
\end{equation}
Consider the following geometric distribution $\mu$ on $\mathbb{Z}_+$:
$$ \mu(k) \eqdef \bar \alpha \alpha^k\,. $$
Define now $\pi$ and $\pi'$ via
$$ \pi(k) \eqdef \mu(k) + \Delta_k\,, \quad \pi'(k) \eqdef \mu(k) - \Delta_k\,.$$
Note that $\mu(0) = \bar\alpha = {1\over \log {1\over \delta}} \ge \delta > \Delta_0$, which implies $\pi(0)\ge 0$ and
$\pi'(0)\ge 0$. Furthermore, from~\eqref{eq:bh1} we get that $\pi(k),\pi'(k)\ge 0$ for all $k\in\mathbb{Z}_+$. Since
$f(1)=\sum_k \Delta_k = 0$ we conclude that $\pi$ and $\pi'$ are indeed probability distributions satisfying
$$ \pi(0) - \pi'(0) \ge \delta\,.$$
Next, notice that since $(\sqrt{1+r}-\sqrt{1-r})^2 \le 2r^2$ for all $r\in[0,1]$ we get
\begin{equation}\label{eq:bh4}
	H^2(\Phi\pi, \Phi\pi') = \sum_{k\ge 0} \left(
	\sqrt{\Phi\mu(k) + \Phi\Delta(k)} - \sqrt{\Phi\mu(k) - \Phi\Delta(k)}\right)^2  \le 2
		\sum_{k\ge 0} {\Phi\Delta(k)^2\over \Phi\mu(k)}\,.
\end{equation}		
Elementary calculation (e.g. from~\eqref{eq:bec-op} and $\sum_k z^k \mu(k) = {1-\alpha\over 1-\alpha z}$) shows that 
\begin{equation}\label{eq:bh2}
	\Phi\mu(k) = \left(1-{1\over r}\right) r^{-k}\,.
\end{equation}
We also know from the proof of \prettyref{prop:mintv-bec} and $g(\alpha) = \beta^{1+\alpha\over 1-\alpha} \le \beta^{\bar \eta\over \eta}$ that
\[\|\Phi f\|_{H^\infty(rD)} \le \bar \alpha \beta^{\bar \eta\over \eta} + \bar \alpha g(\alpha) \le 2 \bar
\alpha \beta^{\bar \eta\over \eta}\,.
\]
Therefore, from~\eqref{eq:cauchy} we get
\begin{equation}\label{eq:bh3}
	|\Phi\Delta(k)| = | [z^k] f(\bar\epsilon z + \epsilon) | \le2 \bar \alpha \beta^{\bar \eta\over \eta} r^{-k} \,.
\end{equation}
Plugging~\eqref{eq:bh2} and~\eqref{eq:bh3} into~\eqref{eq:bh4} we obtain as in~\eqref{eq:feas3}
\begin{equation}\label{eq:bh9}
	H^2(\Phi\pi, \Phi\pi') 
	\leq 4 \bar\alpha^2 \beta^{2\bar\eta/\eta} (1-1/r)^{-2} 
=	4 (1-\alpha \epsilon)^2 \beta^{2\bar\eta/\eta} 
	\le 4 \pth{e\delta \log \frac{1}{\delta} }^{\frac{2\epsilon}{1-\epsilon}}\,.
\end{equation}

To prove the second part, we replace $\pi,\pi'$ by their conditional version, denote by $\tilde \pi(k) = {\pi(k)\over \pi([0,d])}$ for $k\le d$ and similarly for $\tilde
\pi'$. 
Then 
\begin{equation}\label{eq:bh-tail}
\pi((d,\infty))+\pi'((d,\infty)) \le 2 \mu((d,\infty)) = 2 \sum_{k>d} \bar \alpha \alpha^k = 2\alpha^{d+1} \leq 2 \exp\pth{-\frac{d}{\log\frac{1}{\delta}}} \leq 2\delta^{2\epsilon\over 1-\epsilon},
\end{equation}
where the last inequality holds provided that $d \geq \frac{2\epsilon}{1-\epsilon}\log^2\frac{1}{\delta}$.
For Hellinger, 
\begin{align} H(\Phi\pi,\Phi\pi') &\ge H(\Phi\tilde \pi, \Phi \tilde \pi') -H(\Phi\pi, \Phi \tilde \pi) -
		H(\Phi\pi', \Phi \tilde \pi')\label{eq:bh5}\\
	&\ge H(\Phi\tilde \pi, \Phi \tilde \pi') -H(\pi, \tilde \pi) -
		H(\pi', \tilde \pi')\label{eq:bh6}\\
	&= H(\Phi\tilde \pi, \Phi \tilde \pi') - \sqrt{2-2\sqrt{\pi([0,d])}} - \sqrt{2-2\sqrt{\pi'([0,d])}}\
		\label{eq:bh7}\\
	&\ge H(\Phi\tilde \pi, \Phi \tilde \pi') - 4\delta^{\epsilon\over 1-\epsilon}\,,\label{eq:bh8}
\end{align}
where~\eqref{eq:bh5} is from the triangle inequality for Hellinger distance,~\eqref{eq:bh6} is from the data processing inequality for the
latter,~\eqref{eq:bh7} is explicit computation and finally in~\eqref{eq:bh8} 
we used \prettyref{eq:bh-tail} and
the fact that $\sqrt{2-2\sqrt{1-x}} \leq \sqrt{2x}$ for all $0\leq x \leq 1$.
In view of \prettyref{eq:bh9}, this completes the proof of \prettyref{eq:bhel} with $C=36$.
\end{proof}
	
	


\medskip

Finally, we put everything together.

\begin{proof}[Proof of Theorem~\ref{thm:bec}] The upper-bound on the sample complexity follows from
Theorem~\ref{thm:dual} and Proposition~\ref{prop:mintv-bec}. 

For the lower bound, we need to show that the number of zeros carries almost no information. 
This is done by dimension expansion. Indeed, set $d'\gg d$ and extend $\pi$ and $\pi'$ to distributions on
$\{0,\ldots,d'\}$ by zero-padding.
The intuition is that if the input vector contains at most $d$ ones, then the number of zeros of the output is
distributed approximately as $\Binom(d',\bar\epsilon)$, almost independent of the input. We make this idea precise next. 


Fix $\delta=4\delta'>0$, set $d ={2\epsilon\over
1-\epsilon} \log^2 {1\over \delta}$ and consider probability distributions
$\pi$ and $\pi'$ constructed in Lemma~\ref{lmm:bhel} with $H^2(\Phi \pi, \Phi \pi')\le h_1$, where
\begin{equation}\label{eq:bx1}
	h_1 = C \pth{e\delta \log \frac{1}{\delta} }^{\frac{2\epsilon}{1-\epsilon}}\,.
\end{equation}
Take $d'=\frac{16 \bar \epsilon d^2}{\epsilon h_1}$ and note that
according to Lemma \ref{lmm:bin} in \prettyref{app:aux} we have
\begin{equation}\label{eq:bx2}
	H^2(\Binom(d'-s,\bar\epsilon), \Binom(d',\bar\epsilon)) \leq \frac{4 \bar\epsilon d^2}{\epsilon d'}  = {h_1\over 4}\qquad \forall s\in\{0,\ldots,d\}\,.
\end{equation}
It suffices to show
\begin{equation}
	H^2( \Expect_{\theta\sim \pi}[ \Binom(\theta,\bar\epsilon)\otimes \Binom(d'-\theta,\bar\epsilon) ],
	\Expect_{\theta\sim \pi'}[ \Binom(\theta,\bar\epsilon)\otimes \Binom(d'-\theta,\bar\epsilon) ])	\le 4h_1\,,
\label{eq:hellinger-mix}
\end{equation}
Indeed, assuming~\eqref{eq:hellinger-mix} we can conclude from~\eqref{eq:hellinger} that 
	$$ n^*_{\mathsf{L}}(\delta',d') \ge {1\over 8 h_1}\,,$$
	which in view of~\eqref{eq:bx1} is precisely the statement of the theorem.
To show~\eqref{eq:hellinger-mix} consider the following chain:
\begin{align}
	& ~ H(\Expect_{\theta\sim \pi} [\Binom(\theta,\bar\epsilon) \otimes \Binom(d'-\theta,\bar\epsilon)], \Expect_{\theta\sim \pi'} [\Binom(\theta,\bar\epsilon) \otimes \Binom(d'-\theta,\bar\epsilon)])
	\nonumber \\
\leq & ~ H(\Expect_{\theta\sim \pi} [\Binom(\theta,\bar\epsilon)], \Expect_{\theta\sim \pi'}
[\Binom(\theta,\bar\epsilon)]) + \sqrt{h_1} \label{eq:bx3}\\
= & H(\Phi \pi, \Phi \pi') + \sqrt{h_1} \le 2\sqrt{h_1}
\end{align}
where~\eqref{eq:bx3} is an application of the following Lemma with $\tau=\sqrt{h_1}/2$.
\end{proof}

\begin{lemma}
\label{lmm:Hprod}	
	Suppose there exists $Q^*$ such that $H(Q^*,Q_\theta) \leq  \tau$ for any $\theta\in\Theta$. Then for any distributions $\pi$ and $\pi'$ on $\Theta$,
	\[
	H(\Expect_{\theta\sim \pi} [P_\theta \otimes Q_\theta],\Expect_{\theta\sim \pi'} [P_\theta \otimes Q_\theta]) \leq 
	H(\Expect_{\theta\sim \pi} P_\theta, \Expect_{\theta\sim \pi'} P_\theta) +	2\tau.
	%H(\int d\pi [P_\theta \otimes Q_\theta],\int d\pi' [P_\theta \otimes Q_\theta]) \leq 
	%H(\int d\pi P_\theta, \int d\pi' P_\theta) +	2\tau.
	\]
\end{lemma}
\begin{proof}
 	The triangle inequality yields
	\begin{align*}
		H(\Expect_{\theta\sim \pi} [P_\theta \otimes Q_\theta],\Expect_{\theta\sim \pi'} [P_\theta \otimes Q_\theta]) 
\leq & ~ 	H(\Expect_{\theta\sim \pi} [P_\theta \otimes Q^*],\Expect_{\theta\sim \pi'} [P_\theta \otimes Q^*]) \\
& ~ +	H(\Expect_{\theta\sim \pi} [P_\theta \otimes Q_\theta],\Expect_{\theta\sim \pi} [P_\theta \otimes Q^*]) \\
& ~ +	H(\Expect_{\theta\sim \pi'} [P_\theta \otimes Q_\theta],\Expect_{\theta\sim \pi'} [P_\theta \otimes Q^*]).
	\end{align*}
	Here 
	\[
	H(\Expect_{\theta\sim \pi} [P_\theta \otimes Q^*],\Expect_{\theta\sim \pi'} [P_\theta \otimes Q^*]) = H(\Expect_{\theta\sim \pi} [P_\theta] \otimes Q^*,\Expect_{\theta\sim \pi'} [P_\theta] \otimes Q^*) = H(\Expect_{\theta\sim \pi} [P_\theta],\Expect_{\theta\sim \pi'} [P_\theta])
	\]
	and, by convexity,
	$H(\Expect_{\theta\sim \pi} [P_\theta \otimes Q_\theta],\Expect_{\theta\sim \pi'} [P_\theta \otimes Q^*]) \leq \Expect_{\theta\sim \pi}H(Q_\theta,Q^*) \leq \tau$.
\end{proof}

\apxonly{
\subsection{Bounds for general estimators via analysis alone}

Among the two problems identified in the beginning of Section~\ref{sec:lp-bec} only the second one requires statistical tools (Hellinger distance).
Indeed, in this section we briefly outline a purely analytic resolution of the first problem.

Similarly to~\eqref{eq:mdef_2} we now define
$$ t_d(\delta) = \inf_{\Delta}  \quad \sum_{x_0,x_1} \left|\sum_{\ell=0}^d \Delta_\ell {\ell \choose x_1} {d-\ell \choose x_0} \bar
\epsilon^{x_1+x_0} \epsilon^{d-x_0-x_1}\right|\,,$$
where the conditions on $\{\Delta_\ell: \ell = 0,\ldots d\}$ are as before: $\Delta_0=\delta$, $\|\Delta\|_1\le 1$. Defining
$$ f(z) \eqdef \sum_{\ell} \Delta_\ell z^\ell\,,$$
we can rephrase the problem as
$$ t_d(\delta) = \min \{\|\tilde\Phi_d f\|_A: \|f\|_A \le 1, f(1)=0, f(0)=\delta\}\,,$$
where the operator $\tilde \Phi_d$ maps a univariate polynomial $f$ of degree $d$ to a bi-variate polynomial by
the rule
\begin{equation}\label{eq:phi2}
	(\tilde\Phi_d f)(z_0,z_1) \eqdef (\bar \epsilon z_0 + \epsilon)^d f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon
z_0 + \epsilon \right)\,,
\end{equation}
and $H^\infty$ and $A$-norms for bi-variate polynomials are defined as
\begin{align} \|\sum_{n_0,n_1} a_{n_0,n_1} z_0^{n_0} z_1^{n_1} \|_{A} &\eqdef \sum_{n_0,n_1} |a_{n_0,n_1}|\\
   \|g(z_0,z_1) \|_{H^\infty(D)} &\eqdef \sup_{z_0,z_1 \in D} |g(z_0,z_1)|
\end{align}

Bounding the value of $t_d(\delta)$ is done with the help of the following Lemma. Note that the $d_0$-degree polynomial
$f$ can be taken to be exactly the one constructed in the proof of Lemma~\ref{lem:horo}.

\nbr{YP needs to spell out the punchline of this result: (a) improve condition on $d$;  (b) cannot be combined with the Hellinger estimate so loses a factor of two in the exponent  }

\begin{lemma} Fix $\epsilon > 1/2$, then there exists a constant $C_\epsilon$ as follows. Let $f$ be a degree $d_0$
polynomial such that $\|f\|_{H^\infty(D)} \le 1$ and $\sup_{z\in D}|f(\bar\epsilon z +
\epsilon)| = \delta$. Then for $d = \lceil d_0 \log {1\over \delta} \rceil$ we have
	\begin{equation}\label{eq:beluga}
		\delta \le \|\tilde \Phi_d f\|_{A} \le C_\epsilon \cdot \delta  d_0^3  \log^2 {1\over
	\delta}\,.
\end{equation}	
\end{lemma}
\begin{proof} We will use the following relation between $A$ and $H^\infty$ norms:
\begin{equation}\label{eq:bld2}
	\|g\|_{H^\infty} \le \|g\|_A \le  d^2 \|g\|_{H^\infty}\,,
\end{equation}
for any degree-$d$ bivariate polynomial $g$.
For the lower bound in~\eqref{eq:beluga} we use first bound in~\eqref{eq:bld2} and simply lower-bound $H^\infty$ by taking $z_1\to1$. We proceed to the upper
bound.
Let us denote $f(z) = \sum_{n\le d_0} a_n z^n$ and 
$$ M_d \eqdef d^2 \|\tilde \Phi_d f\|_{H^\infty(D)}$$
By~\eqref{eq:bld2} we need to show an upper-bound on $M_d$ only.

We will use the following property: For any $r>1$ and any degree-$d_0$ polynomial $p$ we have
\begin{equation}\label{eq:blg1}
		\sup_{z\in D} |p(zr)| \le r^{d_0} d_0 \sup_{z\in D} |p(z)|\,,
\end{equation}	
which follows from an obvious $|[z^k] p(z)| \le \sup_{z\in D} |p(z)|$.

Fix some $\theta \in (0,1)$ (it will be taken close to 1).  We will compute $H^\infty(D)$-norm of $\tilde \Phi_d f$ by
fixing $z_0$ and maximizing over $z_1$. We separate two cases: 

Case 1. If $\theta < |\bar \epsilon z_0 + \epsilon| \le 1$ then we first notice that disk described by the image of 
	$$ z_1 \mapsto { \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon} $$
	as $z_1$ ranges over $D$
	is contained inside the disk
	$$ z_1 \mapsto \bar \epsilon z_1 + \epsilon$$
	as $z_1$ ranges over ${1-\theta \epsilon\over 1-\epsilon} D$ (\textbf{TODO:} Mistake! This is only true when
	$z_0$ is real, so need to show that $z_0$ real is the worst case!). Thus by~\eqref{eq:blg1} we get
	$$ \sup_{z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right| \le
		d^2 d_0 \left({1-\theta \epsilon\over 1-\epsilon}\right)^{d_0} \delta $$
	and in view of ${1-\theta \epsilon\over 1-\epsilon} \le \theta^{-{\epsilon\over \bar\epsilon}-1}$ we can
	continue as
	$$ \sup_{z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right|\le d^2 d_0 \theta^{-c d_0} \delta $$
	for some $c>1$. 

Case 2. If $|\bar\epsilon z_0 + \epsilon| \le \theta$ then we upper bound 
	$$ \sup_{z_1 \in D} d^2 \left|(\bar \epsilon z_0 + \epsilon)^d
	f\left( \bar \epsilon z_1 + \epsilon \over \bar \epsilon z_0 + \epsilon \right)\right| \le
		d^2 \sup_{z_1 \in D} \sum_{n\le d_0} |a_n| \theta^{d-n} |\bar \epsilon z_1 + \epsilon|^n \le d^2 d_0
		\theta^{d-d_0} \|f\|_{H^\infty(D)} \le d^2 d_0 \theta^d \theta^{-cd_0}\,.$$
	where the last step is due to $c>1$.
	
	Thus, to summarize we get:
	$$ M_d \le 
		d^2 d_0 \theta^{-cd_0} \cdot \max \left\{\theta^d, \delta\right\}\,.$$
	Now choose $d$ as in statement of Lemma and $\theta$ so that
$\theta^d = \delta$.
	Then we get $\theta^{-c d_0} = e^c$ and thus
		$$ M_d \le d_0^3  \left(\ln {1\over \delta}\right)^2 e^c \delta\,, $$
	as claimed.
\end{proof}
}

\section{Noisy population recovery}
\label{sec:bsc}


In this section we bound the value of the LP \prettyref{eq:LP-G} for noisy \pop.
As previously mentioned in \prettyref{rmk:hellinger-preview}, 
since in this case the sample complexity turns out to grow super-polynomially, 
the general result in \prettyref{thm:dual} suffices to produce
the sample complexity bound announced in \prettyref{thm:bsc}
and there is no need to consider refined Hellinger-based minimax lower bound as developed in \prettyref{sec:lp-bec} for lossy \pop.


We begin by specializing the LP in \prettyref{eq:LP-G} to the noisy \pop setting with error probability $\epsilon$, where the transition matrix $\Phi$
is given by \prettyref{eq:bsc} throughout this section.
Recall from \prettyref{eq:bsc} that conditioned on the input Hamming weight $w(X)=j$, the 
output Hamming  weight $w(Y)$ is distributed as the convolution $\Binom(j,\bar\epsilon) * \Binom(d-j,\epsilon)$.
Thus, similarly to \prettyref{eq:mdelta}, we consider the equivalent formulation:
\begin{equation}
t(\delta,d) \eqdef \min_{\Delta\in\reals^{d+1}} \left\{\left\|\sum_{j=0}^d \Delta_j \Binom(j,\bar\epsilon) * \Binom(d-j,\epsilon) \right\|_1: \Delta_0 \ge \delta, \|\Delta\|_1 \le 1
\right\}\,.
\label{eq:mdelta-bsc}
\end{equation}
Since we can always negate the observed bits, in the sequel we shall assume, without loss of generality, that
\[
\epsilon < 1/2.
\]


To recast \prettyref{eq:mdelta-bsc} as an optimization problem in terms of functions (polynomials), we note that the channel $\Phi$ maps the generating function of the input weight to that of the output as follows:
\[
\Expect[z^{w(X)}] \overset{\Phi}{\mapsto}  \Expect[z^{w(Y)}]=\Expect[z^{\Binom(w(X),\bar\epsilon) + \Binom(d-w(X),\epsilon)}] = \Expect[(\bar\epsilon z + \epsilon)^{w(X)} (\epsilon z + \bar\epsilon)^{d-w(X)}  ]
\]
that is,
\begin{equation}
f(z) \mapsto (\Phi f)(z) \triangleq f\pth{\frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}} (\epsilon z + \bar\epsilon)^d.
\label{eq:bsc-op}
\end{equation}
Thus, each degree-$d$ polynomial is mapped to another via
\[
\sum_{i=0}^d a_i z^i \mapsto \sum_{i=0}^d a_i (\bar\epsilon z + \epsilon)^i(\epsilon z + \bar\epsilon)^{d-i}.
\]
Therefore, using the $A$-norm introduced in \prettyref{sec:bec-horo}, we have:
\begin{equation}
t(\delta,  d) = \min \sth{\left\|f\pth{\frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}} (\epsilon z + \bar\epsilon)^d \right\|_{A}: f(0) \geq \delta,
 \|f\|_{A} \le 1, \deg f \le d}\,.
\label{eq:mdef_2-bsc}
\end{equation}

As usual, by choosing $f\equiv\delta$, we have the trivial bound
\begin{equation}
t(\delta,  d) \leq \delta.
\label{eq:m-trivial}
\end{equation}
The next proposition provides a sharp characterization:

\begin{prop} 
\label{prop:mintv-bsc}

Assume that $\epsilon < \frac{1}{2}$ and $d\geq 1$. Define
\begin{equation}
\mu(\epsilon) \triangleq \frac{\epsilon(1-\epsilon)}{(1-2\epsilon)^2}.
\label{eq:mu}
\end{equation}
There exist absolute constant $c,c'$ such that the following hold:
For all $\delta < 1$, 
\begin{equation}
t(\delta,d) \geq \exp\sth{-c   \pth{d \mu(\epsilon) \log^2 \frac{e}{\delta}}^{1/3} }.
%\label{eq:mintv-bsc1}
\label{eq:m-lb}
\end{equation}
For all $\delta < 1/3$, 
\begin{equation}
t(\delta,d) \leq 
%\exp\pth{- c \min \sth{d, \pth{d \log^2 \frac{1}{\delta}}^{1/3} }}.
\max\sth{
\exp(-(1-2\epsilon)^2d), 
%\pth{\frac{d^4 \mu(\epsilon)}{\log^4 \frac{1}{\delta}} }^{1/3}
\exp\pth{- c' \pth{d\mu(\epsilon) \log^2 \frac{1}{\delta}}^{1/3} }}.
\label{eq:m-ub}
\end{equation}
\end{prop}
Again, thanks to \prettyref{thm:dual}, \prettyref{eq:m-lb} and \prettyref{eq:m-ub} translate into the sample complexity lower and upper bound in \prettyref{thm:bsc}, respectively.
%\[
%\min\sth{
%\exp(c_1 (1-2\epsilon)^2d), 
%%\pth{\frac{d^4 \mu(\epsilon)}{\log^4 \frac{1}{\delta}} }^{1/3}
%\exp\pth{c_1 \pth{d\mu(\epsilon) \log^2 \frac{1}{\delta}}^{1/3} }} \leq
%n^*(\delta,d) \leq \exp\pth{ c_2 \pth{d\mu(\epsilon) \log^2 \frac{1}{\delta}}^{1/3} }.
%\]

The rest of this section is devoted to proving \prettyref{prop:mintv-bsc} using $H^\infty$-relaxations (\prettyref{sec:bsc-horo}), with upper and lower bound shown in \prettyref{sec:bsc-lb} and \prettyref{sec:bsc-ub}, respectively. 


\subsection{Two $H^\infty$-relaxations}
	\label{sec:bsc-horo}
	Compared to the analysis of lossy \pop, it turns out that the upper estimate \prettyref{eq:bd2} on $A$-norm using $H^\infty$-norm over a larger disk, which we relied on in \prettyref{sec:bec-horo} to deal with the composition operator \prettyref{eq:bec-op}, 
 is not useful for the more complicated operator \prettyref{eq:bsc-op} and more intricate analysis is thus required.
Specifically, we need to consider two $H^\infty$-relaxations of \prettyref{eq:mdef_2-bsc}, the latter of which retains the $A$-norm constraint:
\begin{align}
t_1(\delta, d) = & ~ \min \sth{\left\|f\pth{\frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}} (\epsilon z + \bar\epsilon)^d \right\|_{H^\infty(D)}: f(0) \geq \delta,
 \|f\|_{H^\infty(D)} \le 1, \deg f \le d}\,  \label{eq:m1}\\
t_2(\delta, d)= & ~ \min \sth{\left\|f\pth{\frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}} (\epsilon z + \bar\epsilon)^d \right\|_{H^\infty(D)}: f(0) \geq \delta,
 \|f\|_{A} \le 1, \deg f \le d}\,.	 \label{eq:m2}
\end{align}
Since 
$ \|p\|_{H^\infty(D)} \leq  \|p\|_{A}  \leq d \|p\|_{H^\infty(D)}$ for any degree-$d$ polynomials $p$, 
we have, in turn,
\begin{equation}
t_1(\delta, d) \le t(\delta,  d) \le  d t_2(\delta, d)\,.
\label{eq:mm1}
\end{equation}


Next we simplify \prettyref{eq:m1} and \prettyref{eq:m2} via a change of variable.
%since $f\pth{\frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}} (\epsilon z + \bar\epsilon)^d$ is a degree-$d$ polynomial, 
note that as long as $\epsilon \neq \frac{1}{2}$, 
the M\"obius transform $z \mapsto \frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}$ maps the unit circle to itself.
Therefore
\begin{align*}
\left\|f\pth{\frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}} (\epsilon z + \bar\epsilon)^d \right\|_{H^\infty(D)} 
\overset{\prettyref{eq:maxmod}}{=}  & ~  \sup_{z\in \partial D} 
\left|f\pth{\frac{\bar\epsilon z + \epsilon}{\epsilon z + \bar\epsilon}} (\epsilon z + \bar\epsilon)^d \right|
\\
= & ~ \sup_{w\in \partial D} 
\left|f(w)  h(w) \right| \overset{\prettyref{eq:maxmod}}{=} \|f h\|_{H^\infty(D)},
%=\left\|f(w)  \left(1-2\epsilon\over \bar\epsilon - \epsilon w\right)^d \right\|_{H^{\infty}(D)}
\end{align*}
where 
\[
h(w) \triangleq \left(1-2\epsilon\over \bar\epsilon - \epsilon w\right)^d
\]
is analytic on $\bar D$ since $\epsilon < 1/2$ by assumption. Hence \prettyref{eq:m1} and \prettyref{eq:m2} are equivalent to
%After reparametrization, we need to solve the following problem:
\begin{align}
t_1(\delta, d) = & ~  \min \sth{\left\|f h\right\|_{H^\infty(D)}: f(0) = \delta,
 \|f\|_{H^\infty(D)} \le 1, \deg f \le d}, \label{eq:m11}\\
t_2(\delta, d) = & ~  \min \sth{\left\|f h\right\|_{H^\infty(D)}: f(0) = \delta,
 \|f\|_{A} \le 1, \deg f \le d}. \label{eq:m22}
\end{align}

%An $H^\infty$-relaxation is
%$$ t_1(\delta, d) = \min \sth{\left\|f(w) \left(1-2\epsilon\over \bar\epsilon - \epsilon w\right)^d\right\|_{H^\infty (D)}: f(0) = \epsilon,
%\|f\|_{H^\infty(D)} \le 1, \deg f \le d}\,,$$
%where we have the usual bounds:
%$$ t_1(\epsilon, d) \le m(\epsilon, d) \le  t_1(\epsilon/d, d)\,.$$
%Note that if we know $m(\epsilon,d)$ we get, in terms of sample complexity $n^*(\epsilon,d)$ for recovering
%$p_0$ within $2\epsilon$:
%$$ {1\over n^*} \le m(\epsilon,d) \le {1\over \sqrt{n^*}}\,.$$





\subsection{Lower bound on $t_1$} 
\label{sec:bsc-lb}


\iffalse
Now regarding the $m_1$, we can immediately state a stupid lower bound (by evaluating at $w=0$):
$$ t_1(\epsilon,d) \ge \epsilon \left(1-2\epsilon\over 1-\epsilon\right)^d\,.$$
An by taking $f(w) = \epsilon \cdot (1-w)^v$ with $v=\log_2 {1\over \epsilon}$ we also have a polynomial (in $d$) upper bound:
$$ t_1(\epsilon,d) \le c d^{-c \ln{1\over \epsilon}}\,.$$
%$$ \sup_{w\in D} \left| \epsilon (w-1) \left(1-2\epsilon\over \bar\epsilon - \epsilon w\right)^d \right| $$
%is achieved at $w=e^{i\theta}$ with $\cos \theta = 1-{\over d}$. whenever $d\ge{1\over \epsilon \bar \epsilon}$. To show this, take $w=e^{i\theta}$ (since maximum as
%at the boundary), take log and differentiate. (\textbf{TODO}: YP will finish if needed).

Slight improvement of the lower bound comes from noticing that for any $f$ satisfying conditions in the definition of
$m_1$ we have (by Hadamard):
	$$ \|f\|_{H^\infty(D_\eta)} \ge \epsilon^{{1\over \eta} - 1}\,,$$
	where $D_\eta$ is a horodisk, cf.~\eqref{eq:br4}, and $\eta \in (0,1/2]$ is arbitrary. Since we also have
	$$ \min_{w \in D_\eta} \left| \left(1-2\epsilon\over \bar\epsilon - \epsilon w\right)^d\right| = \left(1\over
	1+{2\epsilon\over 1-2\epsilon}\eta\right)^d $$
	we get that for any $\eta \in (0,1/2]$:
	$$ t_1(\epsilon,d) \ge \epsilon^{{1\over \eta} - 1} \left(1\over
	1+{2\epsilon\over 1-2\epsilon}\eta\right)^d\,,$$
	In the regime of fixed $\epsilon$ and $d\to \infty$ we get after taking $\eta = c_\epsilon \sqrt{\ln {1\over \epsilon}
	\over d}$ the bound
	$$ t_1(\epsilon,d) \ge e^{-c_\epsilon \sqrt{d \ln {1\over \epsilon}} + c_\epsilon' \ln^{3\over2} {1\over
	\epsilon} + o(1/\sqrt{d})}\,.$$
	(e.g. $c_\epsilon = c_\epsilon' = 1$ when $\epsilon = {1\over 4}$).
\textbf{Better lower bound on $m_1$.} 
\fi


Rewriting $h(z)$ as $h(z) = \frac{1}{(1- c (z-1))^d}$, where $c\triangleq {\epsilon\over 1-2\epsilon}$, we have for all $\theta \in [-\pi,\pi]$,
\[
|h(e^{i\theta})| = (1 + 2c(1+c) (1-\cos \theta))^{-d/2} \geq (1 + c(1+c) \theta^2)^{-d/2} \geq e^{- \mu d \theta^2/2}
\]
where $\mu =\mu(\epsilon)$ is defined in \prettyref{eq:mu}.
%Notice that for some constant $c=c(\epsilon)$ and all $\theta \in (-\pi/100,\pi/100)$ we have
	%$$ \left|1-2\epsilon\over \bar\epsilon - \epsilon e^{i\theta}\right| \ge e^{-c \theta^2}\,.$$
Next, from~\cite[Corollary 3.2]{borwein1997littlewood} we conclude that for any feasible $f$ for \prettyref{eq:m11}, we have
$$ \sup_{\theta \in (-a/2,a/2)} |f(e^{i\theta})| \ge (\delta/e)^{c_1/a}\,, $$
where $c_1$ is an absolute constant. Thus, 
$$ \|fh\|_{H^\infty(D)} \geq  \sup_{\theta \in (-a/2,a/2)}  |f(e^{i\theta})| |h(e^{i\theta})|  \ge e^{- \mu d a^2/2 -
{c_1\over a} \log \frac{e}{\delta}}\,.$$
Setting $a = \left(2 c_1 \log \frac{e}{\delta} \over \mu d\right)^{1\over 3}$ we get the following non-asymptotic
bound:
$$ t_1(\delta,d) \ge \exp\sth{-c_2   \pth{\mu(\epsilon) d \log^2 \frac{e}{\delta}}^{1/3} }\,, $$
where $c_2$ is an absolute constant.
%This translates into an upper bound in terms of sample size: $\delta \leq \exp(- \Omega( \frac{\log^{2/3}n}{\mu(\epsilon) d^2} ))$.

\subsection{Upper bound on $t_2$} 
\label{sec:bsc-ub}
In view of \prettyref{eq:mm1}, we will show that for all $\epsilon<1/2$, $\delta \in(0,1/3)$  and all $d \in \naturals$ we have 
\begin{equation}
t(\delta,d) \leq 
%\exp\pth{- c \min \sth{d, \pth{d \log^2 \frac{1}{\delta}}^{1/3} }}.
\max\sth{
\exp(-(1-2\epsilon)^2d), 
\pth{\frac{d^4 \mu}{\log^4 \frac{1}{\delta}} }^{1/3}
\exp\sth{- c' \pth{d\mu \log^2 \frac{1}{\delta}}^{1/3} }}.
\label{eq:mintv-bsc1}
\end{equation}
for some absolute constant $c'$.


First consider $d \leq \frac{1}{(1-2\epsilon)^2} \log \frac{1}{\delta}$. By the trivial bound \prettyref{eq:m-trivial}, we have
\begin{equation}
t(\delta,d) \leq \exp(-(1-2\epsilon)^2d).
\label{eq:case1}
\end{equation}
In the sequel we shall assume that 
\begin{equation}
d \geq \frac{1}{(1-2\epsilon)^2} \log \frac{1}{\delta}.
\label{eq:r}
\end{equation}
 To construct a near optimal solution for \prettyref{eq:m22}, we modify the feasible solution previously used in the
 proof of \prettyref{prop:mintv-bec}.
Let 
%\[
%g(z) = (1-z) \delta^{1+z\over 1-z}, 
%\]
\begin{equation}\label{eq:g_bsc}
g(z) = (1-z)^2 \delta^{1+z\over 1-z}, 
\end{equation}
and $f(z) = g(\alpha z)$ with $\alpha \in (0,1)$ to be chosen.
Let $\tilde g$ be the degree-$d$ truncation of the Taylor expansion of $g(z) = \sum_n a_n z^n$, and $\tilde f(z) = \tilde g(\alpha z)$.
%We claim that $\tilde f$ is a feasible solution for \prettyref{eq:m22}.
%provided that $\beta = \frac{\delta}{1-\alpha} < 1$ and $\frac{\alpha^{d+1}}{1-\alpha} \leq 1$.
Note that $\tilde f(0)=\tilde g(0)=g(0)=\delta$. 
Next, instead of invoking \prettyref{eq:bd2} which estimates the $A$-norm by the $H^\infty$-norm over a bigger disk and turns out to be too loose here, 
the next lemma (proved in \prettyref{app:aux}) uses the $H^\infty$-norm of the derivative:
%here  we directly compute the $A$-norm via Laguerre polynomials and show the following:
\begin{lemma}
\label{lmm:gnorm}	
For any $\delta > 0$, 
	$\|g\|_{A} \leq A(\delta) \triangleq 4(\log \frac{1}{\delta}+3)$.
\end{lemma}
Therefore 
\[
\|\tilde f\|_{A} =\sum_{n=0}^d \alpha^n |a_n| \leq \sum_{n \geq 0} |a_n| = \|g\|_{A} \leq A(\delta).
\]
%and hence $\frac{\tilde f}{A(\delta)} $ is a feasible solution for $t_2(\delta/A(\delta),d)$ in \prettyref{eq:m22}.
By Cauchy's inequality \prettyref{eq:cauchy}, the Taylor series coefficients of $f$ satisfy $|a_n| \leq \|g\|_{H^\infty(D)} = 1$ and hence	
\begin{equation}\label{eq:dbl5x}
			\|\tilde f - f\|_{A} \le {\alpha^{d_0+1}\over 1-\alpha}\,.
\end{equation}		


Next we bound the objective function.
Rewriting $h(z)$ as $h(z) = \frac{1}{(1- c (z-1))^d}$, where $c\triangleq {\epsilon\over 1-2\epsilon}$, we recall that 
$$ \|h\|_{H^\infty(D)} = 1\,.$$
Thus, we have 
\begin{align}
\|\tilde f h\|_{H^\infty(D)} 
\leq & ~ \|f h\|_{H^\infty(D)} + \|(f-\tilde f) h\|_{H^\infty(D)} \nonumber \\
\overset{\eqref{eq:dbl5x}}{\leq} & ~ \|g(\alpha z) h(z)\|_{H^\infty(D)} +  {\alpha^{d+1}\over
1-\alpha} \nonumber \\
 \leq & ~ 4 \|\delta^{1+\alpha z\over 1-\alpha z} h(z)\|_{H^\infty(D)} +{\alpha^{d+1}\over
1-\alpha}, \label{eq:fh}
\end{align}
where in the last step we used $\|(1-\alpha z)^2\|_{H^\infty(D)} \leq 4$.
The first term is bounded by the following lemma (proved in \prettyref{app:aux}):
%$$ \|f h\|_{H^\infty(D)} \le \|g(\alpha z) h(z)\|_{H^\infty(D)} + \|\tilde g(\alpha z) - g(\alpha z)\|_{H^\infty(D)} $$



\begin{lemma}
\label{lmm:third} 
%For any $\delta,\alpha \in (0,1)$ and any $d$,
%$$ \|\delta^{1+\alpha z\over 1-\alpha z} h(z)\|_{H^\infty(D)} \leq \delta^{1-\alpha \over 1+\alpha}\,.$$
%Furthermore, 
If 
\begin{equation}
%d \ge {4(1-2\epsilon)\over \epsilon \bar\epsilon} (1-\alpha)^{-3} \ln {1\over \delta} ,
d \ge 2 \log \frac{1}{\delta} \max\sth{\frac{1}{\mu(1-\alpha)^3},  \frac{1}{1-\alpha}}
\label{eq:d1}
\end{equation}
where $\mu=\mu(\epsilon)$ is defined in \prettyref{eq:mu},
 then
\begin{equation}
\|\delta^{1+\alpha z\over 1-\alpha z} h(z)\|_{H^\infty(D)} = \delta^{1+\alpha \over 1-\alpha}\,.
\label{eq:third}
\end{equation}
 \end{lemma}
%\textbf{Remark:}
%In case the above condition (ensuring the maximizer is at $z=1$)  is violated, i.e., when $d \leq \log \frac{1}{\delta}$, 
%we can analyze the exact place of the maximum, the result is equivalent to simply use (i.e. take $z=-1$)
%$$ \|\delta^{1+\alpha z\over 1-\alpha z} h(z)\|_{H^\infty(D)} \leq \delta^{1-\alpha \over 1+\alpha}\,.$$
%The best $\alpha$ in this framework is to take $\alpha=0$, that is, let $f(z)=\delta$. This is then equivalent to simply apply the trivial bound \prettyref{eq:m-trivial}.



Finally, set
\begin{equation}
\alpha = 1-\pth{ \frac{2}{d \mu} \log \frac{1}{\delta}  }^{1/3},
\label{eq:alpha-bsc}
\end{equation}
which, in view of the assumption \prettyref{eq:r}, fulfills the condition \prettyref{eq:d1} in the \prettyref{lmm:third}. Combining \prettyref{eq:fh} and \prettyref{eq:third} yields
$ \|\tilde f h\|_{H^\infty(D)} \le \delta^{1+\alpha\over 1-\alpha} + {\alpha^{d+1}\over
1-\alpha}.
 %\le2e^{-c_3 \sqrt[3]{ d  \ln^{2} {1\over \delta}}}\,, 
$
%where in the last step we assumed that $d$ is large enough so that the first term is dominant.
Since $\alpha^d \leq \exp(-(1-\alpha) d)$, the assumption \prettyref{eq:r} together with \prettyref{eq:alpha-bsc} implies that $d \geq \log \frac{1}{\delta}$ and further $\alpha^d \leq \delta^{1 \over 1-\alpha}$. Hence
 \begin{equation}
\|\tilde f h\|_{H^\infty(D)} \leq \frac{1}{1-\alpha} \delta^{1 \over 1-\alpha} 
= \pth{\frac{d\mu}{2 \log \frac{1}{\delta}} }^{1/3}
\exp\sth{- \pth{\frac{d\mu}{2} \log^2 \frac{1}{\delta}}^{1/3} }.
 \label{eq:obj}
 \end{equation}



In summary, for any $\delta \in (0,1)$, we have constructed $\tilde f$ such that $\tilde f(0)=\delta$, $\|\tilde f\|_{A} \leq A(\delta) = 4(\log \frac{1}{\delta}+3)$ and 
$\|\tilde f h\|_{H^\infty(D)}$ is bounded by \prettyref{eq:obj}.
Rescaling by $A(\delta)$, we conclude there exists a universal constant $c_2$, such that for any $\delta'=\frac{\delta}{A(\delta)} \in (0,\frac{1}{3})$, 
\[
t_2(\delta',d) \leq c_2 \pth{\frac{d\mu}{\log^4 \frac{1}{\delta'}} }^{1/3}
\exp\sth{- c_2 \pth{d\mu \log^2 \frac{1}{\delta'}}^{1/3} },
\]
which, in view of \prettyref{eq:mm1}, yields \prettyref{eq:mintv-bsc1}.




\section{Smoothed estimators for lossy population recovery}
	\label{sec:smooth}
	
	
\newcommand{\gun}{g^{\textrm{u}}} \newcommand{\gsm}{g^{\textrm{s}}}

In this section, we construct an explicit estimator for lossy \pop that
is optimal up to a factor of $2$ in the exponent. We start from the 
unbiased estimator for $P_0$ and then modify it via the \emph{smoothing technique} proposed in
\cite{OSW16}.

Recall that for the linear estimator $g$ in \prettyref{eq:hatp}, its bias is bounded by $ \|\Phi^\top g-e_0\|_\infty$ and 
the standard deviation is at most $\frac{1}{\sqrt{n}} \|g\|_\infty$, 
where the matrix $\Phi$ is given by \prettyref{eq:Phi-bec} which is an upper triangular matrix with non-zero diagonals.
As mentioned in \prettyref{sec:intro}, the unique unbiased estimator is a linear estimator with coefficients $\gun = (\Phi^\top)^{-1} e_0$. Direct calculation shows that 
$\gun_j = (-\frac{\epsilon}{\bar\epsilon})^j$ for $j =0,1,\ldots,d$.\footnote{This can also be obtained from consider the inverse operator of \prettyref{eq:bec-op}, which is again a composition operator $(\Phi^{-1} f) (z) = f((z-\epsilon)/ \bar\epsilon )$.}
%Solving the above equation yields
%\[
%\gun_i = \left(-\frac{\epsilon}{\bar\epsilon}\right)^i, \quad i =0,1,\ldots,d.
%\]
%\begin{lemma}
%\label{lem:unbiased}
%Let $\gun$ be a vector such that $\gun_i = (-\epsilon/\bar\epsilon)^i$ for $i=0,\ldots,d$. Then 
%\[
%\Phi^\top \gun = e_0
%\]
%\end{lemma}
%
%For the lossy IRP, $\Phi$ is an upper triangular matrix with non-zero diagonal entries and hence is invertible. Thus
%the unique solution to $\Phi^\top g = e_0$ is given by
%\[
%\gun = (\Phi^\top)^{-1} e_0.
%\]
%%Note that the inverse matrix $\Phi^{-1}$ is upper triangular as well, which has a simple formula
%%\begin{equation}
%%B_{ij} = 
%%\begin{cases}
%%\binom{j}{i} \frac{(-\epsilon)^{j-i}}{\bar{\epsilon}^j }  & i \leq j\\
%% 0 & i > j\\
%%\end{cases}
%%\label{eq:phiinv}
%%\end{equation}
%%Using the inverse formula \prettyref{eq:phiinv}, we have the unique unbiased estimator 
%Solving the above equation yields
%\[
%\gun_i = \left(-\frac{\epsilon}{\bar\epsilon}\right)^i, \quad i =0,1,\ldots,d.
%\]
%and the unique unbiased estimator is given by
%\[
%\hat P_0^{\rm u} = 
%\sum_{j=0}^d \left(-\frac{\epsilon}{\bar\epsilon}\right)^j N_j
%%\frac{1}{n} \sum_{i=1}^n \left(-\frac{\epsilon}{\bar\epsilon}\right)^{w_i}
%\]


Note that $\|\gun\|_\infty = \max(1,
(\epsilon/\bar\epsilon)^{d+1})$. Hence, for $\epsilon \leq 1/2$, $\|\gun\|_\infty = 1$ and the unbiased estimator has a sample complexity at most
$\cO(\delta^{-2})$. For $\epsilon > 1/2$, the coefficients increase
exponentially in $d$ which results in high variance. To
alleviate this issue, we modify the estimator via the smoothing
technique proposed in \cite{OSW16}. 
The main idea of smoothing is to introduce an independent random integer $L$, 
truncate the unbiased estimator after the $L\Th$ term, and average the truncated estimators according to an appropriately chosen distribution that 
aims to balance the bias and variance.
Equivalently, this amounts to multiplying the coefficients of the unbiased estimator with a tail probability that modulates the exponential growth.
To this end, define the smoothed estimator $\hat P_0^{\rm u}$
as a linear estimator \prettyref{eq:hatp} with the coefficient $g$ given by
\[
\gsm_i \triangleq  \gun_i \cdot \Pr(L \geq i).
\]
The following theorem gives the sample complexity guarantee for Poisson smoothing.
%where $L$ is an independent random variable 
\begin{theorem}
\label{thm:linear}
Let $\epsilon > 1/2$.
Let $L$ be Poisson distributed with mean $\lambda = \frac{1-\epsilon}{3\epsilon-1} \log n$. Then
\[
\sup_{P\in\calP_d} \Expect_P[(\hat P_0^{\rm u}-P_0)^2] \leq 4 n^{-\frac{1-\epsilon}{3\epsilon-1}}.
\]
Therefore, the sample complexity of the smoothed estimator is at most $O\Big( \delta^{-\frac{2(3\epsilon-1)}{1-\epsilon}}\Big)$.
%There exists $\widehat{p_0}$, such that for any dimension $d$,
%\[
%\sup_P \Expect_P[(\widehat{p_0} - p_0)^2] \lesssim n^{ - \min\{\frac{1-\epsilon}{3\epsilon-1},1\}}.
%\]
%Furthermore, with probability $\geq 1 - \delta$,
%\[
%|p_0 - \hat{p}_0| \leq n^{ - 0.5 \cdot \min\{\frac{1-\epsilon}{3\epsilon-1},1\}} \cdot \sqrt{2} \log \frac{2}{\delta}.
%\]
\end{theorem}
\begin{proof}
We first bound the variance by the moment generating function of $L$. Observe that
%\begin{align}
%\|\gsm\|_\infty 
%&= \max_i |\gun_i | \cdot \Pr(L \geq i) \nonumber \\
%& = \max_i (\epsilon/\bar\epsilon)^i \cdot \Pr(L \geq i ) \nonumber \\
%& \leq \max_i \EE_L [(\epsilon/\bar\epsilon)^L] \nonumber \\
%& =e ^{\lambda\frac{2\epsilon-1}{1-\epsilon}},
%\label{eq:sm3}
%\end{align}
\begin{align}
\|\gsm\|_\infty 
= \max_i |\gun_i | \cdot \Pr(L \geq i)  = \max_i (\epsilon/\bar\epsilon)^i \cdot \Pr(L \geq i ) 
 \leq  \EE_L [(\epsilon/\bar\epsilon)^L]  =e ^{\lambda\frac{2\epsilon-1}{1-\epsilon}},
\label{eq:sm3}
\end{align}
where the inequality follows from the assumption that $\epsilon/\bar{\epsilon} > 1$.
To bound the bias term, note that 
$(\Phi^\top \gsm)_0 = 1$ and hence
\begin{equation}
\| \Phi^\top \gsm - e_0 \|_\infty \leq \max_{1 \leq j \leq d} |(\Phi^\top \gsm)_j|.
\label{eq:sm1}
\end{equation}
For any $j > 0$,
\begin{align}
(\Phi^\top \gsm)_j
 = \sum^d_{i=0} \Phi_{ij} \gsm_i 
 = \sum^j_{i=0} {j \choose i} \epsilon^j (-1)^i \Pr(L \geq i) \triangleq \epsilon^j f(j).
\label{eq:sm2}
\end{align}
Observe that
\begin{align}
f(j) 
& = \sum^j_{i=0} {j \choose i}(-1)^i \Pr(L \geq i) \nonumber \\
& = \sum^j_{i=0} \left({j-1 \choose i-1} + {j-1 \choose i}\right)(-1)^i \Pr(L \geq i) \nonumber \\
& = \sum^j_{i=0} {j-1 \choose i-1}(-1)^i \Pr(L \geq i) + \sum^j_{i=0} {j-1 \choose i}(-1)^i \Pr(L \geq i) \nonumber \\
& = \sum^{j-1}_{i=0} {j-1 \choose i}(-1)^{i+1} \Pr(L \geq i+1) + \sum^{j-1}_{i=0} {j-1 \choose i}(-1)^i \Pr(L \geq i) \nonumber \\
& = \sum^{j-1}_{i=0} {j-1 \choose i}(-1)^{i} \Pr(L =i). \nonumber
\end{align}
If $L \sim \text{Poi}(\lambda)$, then
\[
f(j) = \sum^{j-1}_{i=0} {j-1 \choose i}(-1)^{i} \Pr(L =i) = \sum^{j-1}_{i=0} {j-1 \choose i}
(-1)^i e^{-\lambda} \frac{\lambda^{i}}{i!} = e^{-\lambda}
L_{j-1}(\lambda),
\]
where $L_{k}(\lambda) = 	\sum_{i=0}^k \frac{(-\lambda)^i}{i!}  \binom{k}{i}$
 is the Laguerre polynomial of degree $k$.
Since $|L_k(\lambda)| \leq e^{\lambda/2}$ for all $k\geq 0$ cf.~\cite[22.14.12]{AS64}, we have $|f(j)|\leq e^{-\lambda/2}$ for all $j\geq 1$.
%Since $f(\infty) = 0$, 
%\[
%|f(\lambda)| \leq \int^\infty_{\lambda} e^{-x/2} dx  \leq 2 e^{-\lambda/2}.
%\]
Hence by \prettyref{eq:sm1} and \prettyref{eq:sm2},
\[
\|\Phi^\top \gsm - e_0 \|_\infty \leq e^{-\lambda/2}.
\]
Combining the above equation with
\prettyref{eq:sm3} yields
\[
%\sqrt{\Expect[(\hat P_0^{\rm u}-P_0)^2]}\leq
\|\Phi^\top \gsm - e_0 \|_\infty + \frac{\|\gsm\|_\infty}{\sqrt{n}}
\leq  e^{-\lambda/2} + \frac{e^{\lambda\frac{2\epsilon-1}{1-\epsilon}}}{\sqrt{n}}.
\]
The theorem follows by setting $\lambda = \frac{1-\epsilon}{3\epsilon-1} \log n$.
%Optimizing over $\lambda$ the following convergence rate which holds for all $\epsilon<1$:
%\[
%n^{ - \min\{\frac{1-\epsilon}{3\epsilon-1},1\}}.
%\]
\end{proof}
%Observe that the
%probability of observing $i$ $1$'s from a sequence of $w$ ones is
%\begin{equation}
%p_{w\to i} = \Phi_{iw}
%= P_{Y=1_i|X=1_w} 
%= {w \choose i} \epsilon^{w-i} (1-\epsilon)^{i}, \quad 0 \leq i \leq w,
%\label{eq:p0-BEC}
%\end{equation}
%that is, $\Binom(w,1-\epsilon)$.
%The following estimator is \emph{the} unbiased estimator for $p_0$ given $n$ samples $Y^{(1)},\ldots,Y^{(n)}$:
%\[
%\widehat{p_0} =\frac{1}{n} 
%\sum^n_{i=1}
%\left(-\frac{{\epsilon}}{1-\epsilon}\right)^{w(Y^{(i)})},
%\]
%where $w(x)$ denotes the number of ones of $x\in\{0,1,?\}^d$. 
%\begin{align*}
%\EE[\widehat{p_0}]
%& = \EE \left[ \left(-\frac{{\epsilon}}{1-\epsilon}\right)^{w(Y)}\right] \\
%& = \EE \left[ \EE \left[ \left(-\frac{{\epsilon}}{1-\epsilon}\right)^{w(Y)} \Bigg| w(X)\right] \right] \\
%& = \sum^d_{j=0} \Pr(w(X) = j)  \EE \left[ \left(-\frac{{\epsilon}}{1-\epsilon}\right)^{w(Y)} \Bigg| w(X)=j \right]   \\
%& = \sum^d_{j=0}p_j  \EE \left[ \left(-\frac{{\epsilon}}{1-\epsilon}\right)^{w(Y)} \Bigg | w(X) = j \right].
%\end{align*}
%For $j=0$,  
%\[
%\EE \left[ \left(-\frac{{\epsilon}}{1-\epsilon}\right)^{w(Y)} \Bigg| w(X) = 0 \right] = 1
%\]
%For $j \geq 1$, 
%% this is an unbiased
%estimator, as for every weight $w \neq 0$,
%\[
%\sum^j_{i=0} {j \choose i} \epsilon^{j-i} (1-\epsilon)^{i}
%\ \left(-\frac{{\epsilon}}{1-\epsilon}\right)^{i} = 0.
%\]
%Therefore $\widehat{p_0}$ is unbiased:
%\begin{equation}
%	\EE[\widehat{p_0}]
%=p_0.
%	\label{eq:unbiased}
%\end{equation}
%However, the variance blows up if $\frac{{\epsilon}}{1-\epsilon} >
%1$, and hence this method only works for $\epsilon \leq 1/2$. 
%I think this was Wigderson's contribution. \nbr{where is this from?}
%To deal with the high-erasure regime ($\epsilon>1/2$), we apply the following idea of smoothing:
%truncate the unbiased estimator at a random location and then average.  In particular, we choose the cutoff point to be Poisson with mean $\lambda$. This results in the following proposed estimator:
%\[
%\widetilde{p_0} = \frac{1}{n} \cdot 
%\sum^n_{i=1}
%\left(-\frac{{\epsilon}}{1-\epsilon}\right)^{w(Y_i)} \Pr(L \geq w(Y_i)),
%\]
%where $L$ is a Poisson random variable with mean $\lambda$. The
%highest co-efficient is
%\[
%\max_{w} \left(\frac{{\epsilon}}{1-\epsilon}\right)^{w} \Pr(L \geq w)
%\leq e^{-\lambda} \sum^\infty_{i=0} \frac{
%  \left(\lambda\frac{{\epsilon}}{1-\epsilon}\right)^{i} }{i!}  \leq
%ue^{\lambda\frac{2\epsilon-1}{1-\epsilon}},
%\]
%and thus is bounded for all $\epsilon < 1$. Therefore, the variance of the proposed
%estimator is bounded by 
%\[
%\Var( \widetilde{p_0}) \leq \frac{e^{2\lambda\frac{2\epsilon-1}{1-\epsilon}}}{n}.
%\]
%We now bound the bias. Observe that the bias corresponding to the weight $0$ is $0$.
%\[
%p_0e^{-\lambda}.
%\]
%The bias corresponding to any weight $w > 0$ is 
%\begin{align*}
 %p(w) \sum^w_{i=0} {w \choose i} \epsilon^{w-i} (1-\epsilon)^{i}
%\left(-\frac{{\epsilon}}{1-\epsilon}\right)^{i} \Pr(L \geq i) 
%& = p(w)
%\epsilon^w \sum^w_{i=0} {w \choose i}(-1)^i \Pr(L \geq i) \\
%& \leq p(w) \left \lvert
%\sum^w_{i=0} {w \choose i}(-1)^i \Pr(L \geq i)\right  \rvert.
%\end{align*}
%Let 
%\[
%f(w) = \sum^w_{i=0} {w \choose i}(-1)^i \Pr(L \geq i).
%\]
%Observe that
%\begin{align}
%f(w) 
%& = \sum^w_{i=0} {w \choose i}(-1)^i \Pr(L \geq i) \nonumber \\
%& = \sum^w_{i=0} \left({w-1 \choose i-1} + {w-1 \choose i}\right)(-1)^i \Pr(L \geq i) \nonumber \\
%& = \sum^w_{i=0} {w-1 \choose i-1}(-1)^i \Pr(L \geq i) + \sum^w_{i=0} {w-1 \choose i}(-1)^i \Pr(L \geq i) \nonumber \\
%& = \sum^{w-1}_{i=0} {w-1 \choose i}(-1)^{i+1} \Pr(L \geq i+1) + \sum^{w-1}_{i=0} {w-1 \choose i}(-1)^i \Pr(L \geq i) \nonumber \\
%& = \sum^{w-1}_{i=0} {w-1 \choose i}(-1)^{i} \Pr(L =i). 
%\end{align}
%Let
%\[
%f(\lambda) = \sum^w_{i=0} {w \choose i}(-1)^i \Pr(L >i) = \sum^w_{i=0}
%{w \choose i}(-1)^i \sum^\infty_{j=i+1}
%e^{-\lambda} \frac{\lambda^j}{j!}.
%\]
%Observe that 
%\begin{align*}
%f'(\lambda) & = \sum^w_{i=0} {w \choose
%i}(-1)^i \sum^\infty_{j=i+1} \left( -
%e^{-\lambda} \frac{\lambda^j}{j!} +
%e^{-\lambda} \frac{\lambda^{j-1}}{(j-1)!} \right) \\ & = -f(\lambda)
%+ \sum^w_{i=0} {w \choose i}(-1)^i \sum^\infty_{j=i}
%e^{-\lambda} \frac{\lambda^{j}}{j!} \\ & = -f(\lambda) + \sum^w_{i=0}
%{w \choose i}(-1)^i \sum^\infty_{j=i+1}
%e^{-\lambda} \frac{\lambda^{j}}{j!}  + \sum^w_{i=0} {w \choose i}
%(-1)^i e^{-\lambda} \frac{\lambda^{i}}{i!}\\ & = -f(\lambda) +
%f(\lambda) + \sum^w_{i=0} {w \choose i} (-1)^i
%e^{-\lambda} \frac{\lambda^{i}}{i!}\\ & = 
%\sum^w_{i=0} {w \choose i}
%(-1)^i e^{-\lambda} \frac{\lambda^{i}}{i!}\\ & = e^{-\lambda}
%L_w(\lambda).
%\end{align*}
%If $L \sim \text{Poi}(\lambda)$, then
%\[
%f(w) = \sum^{w-1}_{i=0} {w-1 \choose i}(-1)^{i} \Pr(L =i) = \sum^{w-1}_{i=0} {w-1 \choose i}
%(-1)^i e^{-\lambda} \frac{\lambda^{i}}{i!} = e^{-\lambda}
%L_{w-1}(\lambda).
%\]
%Hence by the bound on Laguerre polynomials, 
%\[
%|f(w)| \leq e^{-\lambda/2}.
%\]
%%Since $f(\infty) = 0$, 
%%\[
%|f(\lambda)| \leq \int^\infty_{\lambda} e^{-x/2} dx  \leq 2 e^{-\lambda/2}.
%\]
%Thus the bias of the proposed estimator is at most 
%\[
%(1-p_0) e^{-\lambda/2} \leq e^{-\lambda/2}.
%\]
%Hence, the variance increases as $\lambda$ and the bias decreases as $\lambda$. Hence MSE is 
%\[
%e^{-\lambda} + \frac{e^{2\lambda\frac{2\epsilon-1}{1-\epsilon}}}{n}.
%\]
%Optimizing over $\lambda$ the following convergence rate which holds for all $\epsilon<1$:
%\[
%n^{ - \min\{\frac{1-\epsilon}{3\epsilon-1},1\}}.
%\]
%The high concentrataion bound follows from McDiarmid's inequality. With probability $\geq 1 - 2\exp\left(-2n^{\min\{\frac{1-\epsilon}{3\epsilon-1},1\}}\epsilon^2 \right)$
%\[
%|p_0 - \hat{p}_0| \leq 2 \epsilon.
%\]
% PAC learning of DNFs follows from Dvir et al according to Moitra
%et al.
%\paragraph{Systematic way to obtain \emph{the} unbiased estimator}
%Suppose
%\[
%\hat{p_0} = g(w(Y)) = \sum_{i=0}^d g(i) \indc{w(Y)=i}.
%\]
%So we have $d+1$ variables. The goal is 
%\[
%\Expect_{w(Y)\sim \Binom(w,1-\epsilon)} g(w(Y)) = \indc{w=0},
%\]
%which gives
%\[
%\Phi' g = e_0
%\]
%so the unique solution is
%\[
%g = (\Phi^{-1})' e_0 = 0\Th \text{ row of $\Phi^{-1}$}
%\]

\appendix



\section{Converting individual recovery to population recovery}
\label{app:alg}


 %One naive approach is to use IRP to estimate $P_x$ for each $x\in
 %\{0,1\}^d$ and output the resulting vector as the global estimate of
 %probability distribution. Even ignoring the normalization issues, the
 %analysis of the $\ell_\infty$-risk of such an estimator requires
 %taking a union bound over $2^d$ events and does not result in any
 %reasonable performance bounds. The ingenious workaround
 %on~\cite{DRWY12} was to leverage the special structure of Hamming space, 
%namely that the spaces with different $d$ are embedded
 %in one another. 

In this appendix we describe the algorithm in \cite{DRWY12} that relates individual recovery to population recovery and converts any estimator for $P_0$ to a distribution estimator. The main ingredient is induction on the length $d$
and the observation that for any $x$, one can convert any estimator $\hat P_0$ for
$P_0$ to one for $P_x$:
\[
\wt P_x = \hat P_0(Y_1\oplus x, \ldots, Y_n\oplus x),
\]
which inherits the performance guarantee of $\hat P_0$ under both lossy and noisy model.

Let $xa$ denote the sequence obtained by concatenating sequences $x$
and $a$. Consider the following algorithm:
\begin{itemize}
\item Input $\delta$.
\item Initialize: $\cS_1 = \{0,1\}$.
\item For each $i$ from $2$ to $d$: 
\begin{itemize}
\item $\cS_i \leftarrow \cup_{x \in \cS_{i-1}} \{x0, x1\}$.
\item For each $x$ in $\cS_i$, compute the estimate $\wt P_x = \hat P_0(Y_1\oplus x, \ldots, Y_n\oplus x)$.  
	\item Let  $\cS_i \leftarrow \cS_i \setminus \{x: \wt P_x \leq 2\delta\}$.
	%If $ \hat P_x \leq 2\delta$, let   $\cS_i \leftarrow \cS_i \setminus \{x\}$.
%\item If $|\cS_i| \geq 1/\delta$, declare error and stop.
\end{itemize}
\item 
%Estimate $\cS_d$ for each $x \in \cS_d$ and output it.  
Assign $\hat P_x = \wt P_x$ for all $x \in \calS_d$ and $\hat P_x = 0$ otherwise.
\end{itemize}



The following lemma, applicable to both lossy and noisy recovery, improves the original guarantee in \cite{DRWY12} which depends on the support size of the distribution.
%It applies to both lossy and noisy \pop, since the only assumption is that each coordinate of the output vector is obtained by passing the corresponding bit of the input through the same channel.
%However, their analysis assumed that $k$ is known.  We show that 
 %their analysis can be extended  without any assumptions on $k$ and prove
 %that

 \begin{lemma}
   \label{lem:irptorp}
If there is an algorithm $\hat P_0$ that estimates $P_0$ to an
accuracy of $\delta$ using $n$ samples with probability at least $1-
\alpha$, then there is an algorithm that with probability $\geq 1 -
9d\alpha/(4\delta)$ satisfies,
\[
\max_{x \in \{0,1\}^d} |P_x - \hat{P}_x| \leq 4\delta.
\] 
The run time for the algorithm is $\cO(d/\delta \cdot (t+nd))$, where $t$
is the time it takes to compute $\hat P_0$.
\end{lemma}

\begin{remark}
\label{rmk:median}	
\prettyref{lem:irptorp} shows that the sample complexity of population recovery (estimating all probabilities) is within a logarithmic factor of that of individual recovery (estimating $\hat P_0$), namely, $n^*(d,\delta)$. To see this, consider an estimator $\hat P_0$ that achieves $\Expect(\hat P_0-P_0)^2 \leq \delta^2$ so that
$|\hat P_0-P_0| \leq 2 \delta$ with probability at least $1/4$. By the usual split-sample-then-median method,\footnote{That is, 
divide all the samples into $\log \frac{1}{\tau}$ batches, apply the same estimator to each batch and take the batchwise median.} $O(n^*(\delta,d) \cdot \log \frac{d}{\delta \tau})$ samples suffices to boost the probability of estimating $P_0$ within $\delta$ to $1- \frac{\delta\tau}{d}$, which, in view of \prettyref{lem:irptorp}, suffices to estimate all probabilities within $\delta$ with probability $1-\tau$. 		
\end{remark}


%\begin{lemma}
%%If there is an algorithm that estimates $P_x$ to an accuracy of
%%$\delta$ using $n$ samples with probability at least $1- \alpha$ for each $x$ of length at most $d$,
%If there is an algorithm $\hat P_0$ that estimates $P_0$ to an accuracy of
%$\delta$ using $n$ samples with probability at least $1- \alpha$, then the above algorithm with probability $\geq 1 -
%9d\alpha/(4\delta)$ satisfies,
%\[
%\max_{x \in \{0,1\}^d} |P_x - \hat{P}_x| \leq 4\delta.
%\] 
%The run time for the algorithm is $\cO(d/\delta \cdot (t+nd))$, where $t$
%is the time it takes to compute $\hat P_0$.
%\end{lemma}


\begin{proof}
We first show that with high probability all sequences with
probability $\geq 4 \delta$ remain in $\cS_d$.  Observe that if a
sequence $x$ has probability $\geq 4\delta$, then all of its 
prefixes also has probability $\geq 4\delta$. By definition, $\Pr(|P_x - \hat{P}_x|\geq 2\delta) \leq \alpha$.
Hence, the probability that $x$ is discarded is at most
$\alpha (d-1)$ by the union bound and the probability that any such
sequence is absent in $\calS_d$ is at most $(d-1)\alpha/(4\delta)$.

We now show by induction that $|\cS_d| \leq 1/\delta$ with probability $\geq 1 -
2(d-1)\alpha/\delta$.  Suppose $|\cS_{i-1}| \leq
1/\delta$ with probability $\geq 1- 2(i-2)\alpha/\delta$, which holds
for $i-1 = 1$. Then,
\begin{align*}
\Pr(\exists y \in \cS_i : {P}_y \leq \delta) 
&\leq \sum_{y \in \cup_{x \in \cS_{i-1}} \{x0, x1\}} \Pr(\hat{P}_y > 2\delta, P_y \leq \delta) \\
& \stackrel{(a)}{\leq}\sum_{y \in \cup_{x \in \cS_{i-1}} \{x0, x1\}} \alpha \\
&  = 2 \alpha |\cS_{i-1}| 
%& \leq 2 \alpha /\delta, 
\end{align*}
where $(a)$
follows from the assumption that $\Pr(|\hat P_y - P_y| \leq \delta) \geq 1- \alpha$ for all $y$.
%Conditioned on the set $\cS_{i-1}$, the probability
%that any subsequence with probability $\leq \delta$ remains in $\cS_i$
%is at most $\alpha$. Hence the probability that any element of the
%$\cS_i$s have an element with probability $\leq \delta$ is at most
%$\alpha |\cS_{i-1}| \leq 2\alpha/\delta$.
%\nbr{Then I don't understand this: before pruning, $|\calS_i|=2|\calS_i|$. Then the union bound reads 
%$2 \alpha |\cS_{i-1}|$ and will not work. }
 Hence, by the inductive hypothesis and the union bound, the probability that $|\cS_i|$ 
exceeds $ 1/\delta$ is at most $2(i-1)\alpha/\delta$.

Combing the above two results, we get that with probability $\leq 9(d-1)\alpha/(4\delta)$,
$\cS_d$ contains all symbols with probability $\geq 4\delta$ and
$|\cS_d| \leq 1/\delta$. 
%Let $\hat{P}_x$ denote the estimate of $P_x$ for $x \in \cS_d$. 
Conditioned on this event, with probability at least $1-\alpha/\delta$, $|P_x
-\hat{P}_x|\leq \delta$, for all $x \in \cS_d$.  Hence,
\begin{align*}
\max_{x \in \{0,1\}^d} |P_x -\hat{P}_x| & = \max \left(\max_{x \in
  S_d} |P_x -\hat{P}_x| , \max_{x \notin S_d} P_x \right)
	\leq \max \left(\max_{x \in S_d} |P_x -\hat{P}_x|, 4\delta
\right) \leq 4\delta.
\end{align*}
By the union bound the total error probability is $9(d-1)\alpha/(4\delta) + \alpha /\delta$. 
\end{proof}


\section{Proofs of auxiliary results}
\label{app:aux}




\begin{proof}[Proof of \prettyref{lmm:aux-dual}]
\begin{enumerate}
	\item Notice that maximizer $\Delta$ for $\delta(t)$ yields a feasible solution $\lambda \Delta$ in the program
for $\delta(\lambda t)$.

\item The first inequality of~\eqref{eq:deltas} is obvious. Now consider $\Delta$ is the maximizer for $\delta(t)$. Let
$\iprod{\Delta}{\ones} = \epsilon$. 
Since $\Phi$ is column-stochastic, we have $\Phi^\top \ones = \ones$ and thus
$$\iprod{\Delta}{\ones} = \iprod{\Phi \Delta}{\ones} \le\|\Phi\Delta\|_1 \|\ones\|_\infty \le t $$ 
and thus $|\epsilon|\le t$.
Then, let $\pi_\pm$ be distributions on $\Theta$ with
$\iprod{\pi_-}{h}\le 0 \le \iprod{\pi_+}{h}$ (their existence follows from that of $\theta_{\pm}$). Let
$\pi_0=\pi_-$ if $\epsilon>0$ and $\pi_0=\pi_+$ otherwise. Define
$$ \tilde\Delta \eqdef {1\over 2} \Delta - {\epsilon\over 2} \pi_0\,.$$
From $\|\pi_-\|_1 = 1$, $\|\Phi r\|_1 \le \|r\|_1$ and triangle inequality we have:
\begin{align*} \|\tilde \Delta\| &\le {1\over 2} + {|\epsilon|\over 2} \le 1\\
   \|\Phi\tilde \Delta\| &\le {1\over 2} \|\Phi \Delta\|_1 + {|\epsilon|\over 2} \le t\\
   \Iprod{\tilde \Delta}{\ones} &= {1\over 2} \iprod{\Delta}{\ones} - {\epsilon\over 2}=0\\
   \Iprod{\tilde \Delta}{h} &= {1\over 2} \iprod{\Delta}{h} - {\epsilon\over 2} \iprod{\pi_0}{h} \ge {1\over 2}
   \iprod{\Delta}{h}\,.
\end{align*}
Thus, we get that $\tilde \delta(t) \ge {1\over 2} \delta(t)$. 

\item
Let $z$ be such that $\iprod{z}{\ones}=0$ and $\|z\|_1\leq 1$ and set $\Delta=t z$. Then 
	$\|\Phi\Delta\|_1 \leq \|\Phi\|_{\ell_1\to\ell_1} \|\Delta\|_1 \leq t$.
	Choose $z$ to maximize $\iprod{z}{h}$ gives the desired result with $C(h) = {h_{\max}-h_{\min}\over 2}$, where 
$h_{\max} > h_{\min}$ are the maximal and minimal values of $h(\theta)$.
\end{enumerate}
\end{proof}



\begin{proof}[Proof of \prettyref{lmm:gnorm}]
	Recall the following upper bound on the $A$-norm in terms of the $H^\infty$-norm of the derivative, which is a simple consequence of Parseval's identity and the Cauchy-Schwartz inequality (see, e.g., \cite{Newman75}):
\begin{equation}
\|g\|_{A} \leq \|g\|_{H^\infty(D)} + 2 \|g'\|_{H^\infty(D)}.
\label{eq:newman}
\end{equation}
Recall that $\|\delta^{1+z\over 1-z}\|_{H^\infty(D)} = 1$. We have $\|g\|_{H^\infty(D)} \leq 4$.
Furthermore, $g'(z) = 2 \delta^{1+z\over 1-z} (\log \delta + z - 1)$. We have $\|g'\|_{H^\infty(D)} \leq 2 (\log \frac{1}{\delta}+2)$ and hence the lemma.
\end{proof}

\iffalse
\begin{proof}[Alternative proof of \prettyref{lmm:gnorm}]
Recall the generalized Laguerre polynomial $L_n^{(\nu)}(x)$ 
%$L_n^{(\nu)}(x) = \sum_{k=0}^n \binom{n+\nu}{n-k} \frac{(-x)^k}{k!} $ for $n\geq 2$, and $L_0^{(\nu)}(x) =1, L_1^{(\nu)}(x) =1+\nu-x$.
and its generating function \cite[8.975]{GR}:
\begin{equation}
\sum_{n \geq 0} z^n L_n^{(\nu)}(x) =  \frac{1}{(1-z)^{1+\nu}}  \exp\pth{\frac{zx}{z-1}} , \quad |z|< 1
\label{eq:LagGF}
\end{equation}
Since $g(z) = (1-z) \delta \delta^{\frac{2}{1-z}}$, its Taylor expansion $g(z) = \sum_{n \geq 0} a_n z^n$ is given by
\[
a_n = \delta L_n^{(-2)}(x), \quad x = 2 \log \frac{1}{\delta}
\]
and hence $\|g\|_{A} = \sum_{n\geq 0} |L_n^{(-2)}(x)|$.
Recall the classical bound of Szeg\"o (cf.~\cite[(7.6.10)]{orthogonal.poly}) on Laguerre polynomials: for $\nu \leq -\frac{1}{2}$, as $n\to\infty$,
\begin{equation}
|L_n^{(\nu)}(x)| = O(n^{\nu/2-1/4})
\label{eq:szego}
\end{equation}
uniformly in any compact interval of $[0,\infty)$.
Therefore $a_n = O(n^{-5/4})$ and hence $\|g\|_{A} \triangleq A(\delta)$ is finite.\footnote{In fact, recall Fej\'er's sharp asymptotics of Laguerre polynomials \cite[Theorem 8.22.1]{orthogonal.poly}: for fixed $\nu \in \reals$ as $n\to\infty$, $L_n^{(\nu)}(x) = \sqrt{\pi} e^{x/2} x^{-\nu/2-1/4} n^{\nu/2-1/4} \cos(2\sqrt{nx} - \pi(1/4+\nu/2)) + O(n^{\nu/2-3/4})$, where $x>0$ and the remainder is uniform in any compact interval of $(0,\infty)$. This suggests that 
$A(\delta) = O((\log \frac{1}{\delta})^{5/4})$.}


\nbr{Explicit bound: below we show $A(\delta) \leq O( \frac{1}{\delta})$, although the optimal bound might be $A(\delta) \leq \polylog(\frac{1}{\delta})$}

We show the following crude but non-asymptotic bound: 
for any $\nu \in \integers$, there exists $C=C(|\nu|)$ such that
\begin{equation}
|L_n^{(\nu)}(x)| \leq C(|\nu|) \frac{t(n+\frac{\nu}{2}+\frac{3}{4})}{n!} e^{x} x^{-\frac{\nu}{2}-\frac{1}{4}}
\label{eq:Lagcrude}
\end{equation}
provided that $n +\nu > -1$ and $n+\nu/2 > -3/4$. 

To this end, recall the following integral representation \cite[Theorem 5.4]{orthogonal.poly}
\[
e^{-x} x^{\nu/2} |L_n^{(\nu)}(x)| = \frac{1}{n!} \int_0^\infty e^{-t} t^{n+\nu/2} J_\nu(2\sqrt{tx}) dt
\]
provided that $n + \nu > -1$, where $J_\nu$ is the Bessel function of the first kind.
The magnitude of the Bessel function is bounded by (cf.~\cite[Theorem 7.31.2]{orthogonal.poly}): for any $\nu \geq 0$, there exists $c(\nu)$, such that
$|J_\nu(x)| \leq c(\nu) x^{-1/2}$ for all $x>0$.
Furthermore, for $\nu\in\integers$, $J_{-\nu}(x)=J_\nu(x) (-1)^\nu$.
Thus we have 
\[
e^{-x} x^{\nu/2} |L_n^{(\nu)}(x)| \leq \frac{c(|\nu|)}{n!} \int_0^\infty e^{-t} t^{n+\nu/2} (2\sqrt{tx})^{-1/2} dt = \frac{c(|\nu|)}{n!} (x/2)^{-1/4} t(n+\nu/2+3/4),
\]
which yields \prettyref{eq:Lagcrude}.

Finally, for $\nu=-2$ and all $n \geq 2$, \prettyref{eq:Lagcrude} gives
$|L_n^{(-2)}(x)| \leq C(2) \frac{t(n-\frac{1}{4})}{n!} e^{x} x^{\frac{3}{4}}$.
Since $\frac{t(n-\frac{1}{4})}{n!} = O(n^{-5/4})$, we have
$\|g\|_{A} = \delta \sum_{n\geq 0} |L_n^{(-2)}(2 \log \frac{1}{\delta})| \leq \frac{C}{\delta} $ for some universal constant $C$.
\end{proof}
\fi


\begin{remark}[Alternative proof of \prettyref{lmm:gnorm}]
\label{rmk:lag}	
	In fact with more refined analysis it is possible to choose
	\[
g(z) = (1-z) \delta^{1+z\over 1-z}
\]
as opposed to \prettyref{eq:g_bsc}.
Of course, in this case the bound \prettyref{eq:newman} based on derivatives fails.
Instead, we can express the Taylor expansion coefficients of $g$ in terms of Laguerre polynomials. 
	Recall the generalized Laguerre polynomial $L_n^{(\nu)}(x)$ 
%$L_n^{(\nu)}(x) = \sum_{k=0}^n \binom{n+\nu}{n-k} \frac{(-x)^k}{k!} $ for $n\geq 2$, and $L_0^{(\nu)}(x) =1, L_1^{(\nu)}(x) =1+\nu-x$.
and its generating function \cite[8.975]{GR}:
\[
\sum_{n \geq 0} z^n L_n^{(\nu)}(x) =  \frac{1}{(1-z)^{1+\nu}}  \exp\pth{\frac{zx}{z-1}} , \quad |z|< 1.
\]
Since $g(z) = (1-z) \delta \delta^{\frac{2}{1-z}}$, its Taylor expansion $g(z) = \sum_{n \geq 0} a_n z^n$ is given by
$a_n = \delta L_n^{(-2)}(x)$ with $x = 2 \log \frac{1}{\delta}$ 
and hence $\|g\|_{A} = \sum_{n\geq 0} |L_n^{(-2)}(x)|$.
Recall the classical bound of Szeg\"o (cf.~\cite[(7.6.10)]{orthogonal.poly}) on Laguerre polynomials: for $\nu \leq -\frac{1}{2}$, as $n\to\infty$,
$|L_n^{(\nu)}(x)| = O(n^{\nu/2-1/4})$
uniformly in any compact interval of $[0,\infty)$.
Therefore $a_n = O(n^{-5/4})$ and hence $\|g\|_{A}$ is finite.
Furthermore, recall Fej\'er's sharp asymptotics of Laguerre polynomials \cite[Theorem 8.22.1]{orthogonal.poly}: for fixed $\nu \in \reals$ as $n\to\infty$, $L_n^{(\nu)}(x) = \sqrt{\pi} e^{x/2} x^{-\nu/2-1/4} n^{\nu/2-1/4} \cos(2\sqrt{nx} - \pi(1/4+\nu/2)) + O(n^{\nu/2-3/4})$, where $x>0$ and the remainder is uniform in any compact interval of $(0,\infty)$. This suggests that 
$\|g\|_{A} = O((\log \frac{1}{\delta})^{5/4})$.



%We show the following crude but non-asymptotic bound: 
%for any $\nu \in \integers$, there exists $C=C(|\nu|)$ such that
%\begin{equation}
%|L_n^{(\nu)}(x)| \leq C(|\nu|) \frac{t(n+\frac{\nu}{2}+\frac{3}{4})}{n!} e^{x} x^{-\frac{\nu}{2}-\frac{1}{4}}
%\label{eq:Lagcrude}
%\end{equation}
%provided that $n +\nu > -1$ and $n+\nu/2 > -3/4$. 
%
%To this end, recall the following integral representation \cite[Theorem 5.4]{orthogonal.poly}
%\[
%e^{-x} x^{\nu/2} |L_n^{(\nu)}(x)| = \frac{1}{n!} \int_0^\infty e^{-t} t^{n+\nu/2} J_\nu(2\sqrt{tx}) dt
%\]
%provided that $n + \nu > -1$, where $J_\nu$ is the Bessel function of the first kind.
%The magnitude of the Bessel function is bounded by (cf.~\cite[Theorem 7.31.2]{orthogonal.poly}): for any $\nu \geq 0$, there exists $c(\nu)$, such that
%$|J_\nu(x)| \leq c(\nu) x^{-1/2}$ for all $x>0$.
%Furthermore, for $\nu\in\integers$, $J_{-\nu}(x)=J_\nu(x) (-1)^\nu$.
%Thus we have 
%\[
%e^{-x} x^{\nu/2} |L_n^{(\nu)}(x)| \leq \frac{c(|\nu|)}{n!} \int_0^\infty e^{-t} t^{n+\nu/2} (2\sqrt{tx})^{-1/2} dt = \frac{c(|\nu|)}{n!} (x/2)^{-1/4} t(n+\nu/2+3/4),
%\]
%which yields \prettyref{eq:Lagcrude}.
%
%Finally, for $\nu=-2$ and all $n \geq 2$, \prettyref{eq:Lagcrude} gives
%$|L_n^{(-2)}(x)| \leq C(2) \frac{t(n-\frac{1}{4})}{n!} e^{x} x^{\frac{3}{4}}$.
%Since $\frac{t(n-\frac{1}{4})}{n!} = O(n^{-5/4})$, we have
%$\|g\|_{A} = \delta \sum_{n\geq 0} |L_n^{(-2)}(2 \log \frac{1}{\delta})| \leq \frac{C}{\delta} $ for some universal constant $C$.


\end{remark}


\begin{proof}[Proof of \prettyref{lmm:third}]
	%Numerical evidence and quadratic Taylor expansion in $\theta$ for $z=e^{i\theta}$ around $\theta=0$.
Note that $ \|\delta^{1+\alpha z\over 1-\alpha z} h(z)\|_{H^\infty(D)} = \max_{|z|=1} \big|\delta^{1+\alpha z\over 1-\alpha z} \frac{1}{(1- c (z-1))^d}\big|$, where
\begin{align*}
\left| \frac{\delta^{1+\alpha e^{i\theta}\over 1-\alpha e^{i\theta}}}{(1- c (e^{i\theta}-1))^d}\right|
= & ~ \delta^{\text{Re}(\frac{1+\alpha e^{i\theta}}{1-\alpha e^{i\theta}})} |1- c (e^{i\theta}-1)|^{-d} \\
= & ~ 	\delta^{\frac{1-\alpha^2}{1-2\alpha \cos \theta + \alpha^2}} (1 + 2c(1+c) (1-\cos \theta))^{-d/2}
= e^{-F(1-\cos \theta)}
\end{align*}
where $F(t) \triangleq \frac{1-\alpha^2}{(1-\alpha)^2+2\alpha t} \log \frac{1}{\delta}  +\frac{d}{2}\log(1 + 2 t \mu)$ and $\mu=\mu(\epsilon)$ as defined in \prettyref{eq:mu} since $c=\frac{\epsilon}{1-2\epsilon}$ and 
$c(1+c)=\mu$.
The goal is to identify conditions so that the $H^\infty$-norm is achieved at  $\theta= 0$ ($z=1$).
Let $s = 2t \mu, A = \frac{d}{2(1-\alpha^2) \log \frac{1}{\delta}}, B =(1-\alpha)^2,C=\alpha/\mu$. Then $F(t) = (1-\alpha^2) \log \frac{1}{\delta}(A \log(1+s) + \frac{1}{B+Cs}) \triangleq \delta(s)$.
Straightforward calculation shows that 
$F'(t) \geq 0$ for $t\in[0,2]$ provided that
\[
A \geq \frac{C}{B^2},   \quad A \geq \frac{1}{2B},
\]
that is,
$d \geq \log \frac{1}{\delta} \max\{ \frac{\alpha(1-\alpha^2)}{\mu (1-\alpha)^4}, \frac{1-\alpha^2}{(1-\alpha)^2}\}$, which is ensured by \prettyref{eq:d1}.
Hence $\|\delta^{1+\alpha z\over 1-\alpha z} h(z)\|_{H^\infty(D)}=e^{-F(0)}$ as claimed.
\end{proof} 


Finally, the next result is used in \prettyref{sec:lp-bec}:
\begin{lemma}
\label{lmm:bin}	
	For any $d'\geq d \geq 1$ and $0\leq p<1$,
	$H^2(\Binom(d',p), \Binom(d'-d,p)) \leq \frac{4pd^2}{(1-p) d'}$. 
\end{lemma}
\begin{proof}[Proof of \prettyref{lmm:bin}]
	It suffices to show that for any $n\geq 1$, $H^2(\Binom(n,p),\Binom(n-1,p)) \leq \frac{p}{(1-p) n}$.	
	Indeed, since $H^2(P,Q) \leq \chi^2(P\|Q) = \int \frac{(dP)^2}{dQ} -1$, we have
	\[
	\chi^2(\Binom(n-1,p)\|\Binom(n,p)) = \Expect_{X \sim \Binom(n,p)}\Big[\Big(\frac{n-X}{n(1-p)}\Big)^2\indc{X < n} \Big] \leq \frac{p}{n(1-p)}.
		\]
	Then by the triangle inequality of the Hellinger distance, we have
	$H(\Binom(d',p), \Binom(d'-d,p)) \leq \sqrt{\frac{p}{1-p}} \sum_{n=d'-d+1}^{d'} \frac{1}{\sqrt{n}} \leq \sqrt{\frac{p}{1-p}} \int_{d'-d}^{d'} \frac{1}{\sqrt{x}}dx \leq \sqrt{\frac{p}{1-p}} \frac{2d}{\sqrt{d'}} $. 
\end{proof}

Polyanskiy17.tex
\documentclass[12pt]{colt2017}
\usepackage{enumerate}

%\usepackage[%dvips,
%            CJKbookmarks=true,
%            bookmarksnumbered=true,
%            bookmarksopen=true,
%                       bookmarks=true,
%            colorlinks=true,
%            citecolor=red,
%            linkcolor=blue,
%            anchorcolor=red,
%            urlcolor=blue
%            ]{hyperref}
%\usepackage{times}

%\usepackage[margin=1in]{geometry}  % set the margins to 1in on all sides%
\usepackage{url, color, xcolor}
\usepackage{amsmath,amssymb,amsfonts,bbm,graphicx,xspace}
\usepackage{tcolorbox}
\definecolor{myblue}{HTML}{0000FF}
\definecolor{myred}{HTML}{FF0000}
\definecolor{myorange}{HTML}{FFA500}
\definecolor{myyellow}{HTML}{FFFF00}
\definecolor{mycyan}{HTML}{00FFFF}
\definecolor{mygreen}{HTML}{008000}
\definecolor{mybrown}{HTML}{A52A2A}
\renewcommand{\Pr}{\Prob}
\newcommand{\polylog}{\mathsf{polylog}}
\newcommand{\pop}{population recovery\xspace}


\newcommand{\theertha}[1]{\textcolor{mygreen}{Theertha: #1}}
\newcommand{\sam}{n}
\newcommand{\alp}{k}
\newcommand{\mul}[1]{N_{#1}}
\newcommand{\muln}[1]{N^n_{#1}}
\newcommand{\multn}[1]{N^{tn}_{#1}}
\newcommand{\prev}[1]{{\varPhi_{#1}}}
\newcommand{\cpmx}[1]{{S(#1)}}
\newcommand{\cpm}{{S}}
\newcommand{\est}{E}
\newcommand{\poi}{\mathrm{poi}}
\newcommand{\indic}{\mathbbm{1}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Expect}{\mathbb{E}}
\newcommand{\MMSE}{\text{MMSE}}

%\newcommand{\news}[1]{\Delta({#1})}
%\newcommand{\newt}{\news{t}}
%\newcommand{\enews}[1]{\Delta^{E}({#1})}
%\newcommand{\FGT}{\mathrm{FGT}}
%\newcommand{\fnews}[1]{{\Delta}^{\FGT}({#1})}
%\newcommand{\hnews}[1]{{\Delta}^{{h}}({#1})}
%\newcommand{\etnews}[1]{{\Delta}^{ET}({#1})}
%\newcommand{\snews}[1]{{\Delta}^{S}({#1})}
%\newcommand{\tnews}[1]{{\Delta}^{T}({#1})}
%\newcommand{\enewt}{\enews{t}}
%\newcommand{\hnewt}{\hnews{t}}
%\newcommand{\snewt}{\snews{t}}
%\newcommand{\fnewt}{\fnews{t}}
%\newcommand{\fnewone}{\fnews{1}}
%\newcommand{\tnewt}{\tnews{t}}
%\newcommand{\etnewt}{\etnews{t}}
%\newcommand{\range}[2]{T^{#1}(#2)}
%\newcommand{\loss}{L}
%\newcommand{\lpe}{\loss^\est_p}
%\newcommand{\wclsss}[3]{\loss_*^{#1}(#2,#3)}
%\newcommand{\wclFGT}{\wclsss{\FGT}{n}{t}}
%\newcommand{\lossh}{\wclsss{h}{n}{t}}
\newcommand{\coeffs}[1]{h^{#1}}
\newcommand{\coeffET}{\coeffs{\rm ET}}
\newcommand{\coeffT}{\coeffs{T}}
%\newcommand{\coeffP}{\coeffs{P}}

\newcommand{\supp}{S}
\newcommand{\suppest}{\hat{\supp}}
\newcommand{\ed}{\stackrel{\mathrm{def}}{=}}

%\newcommand{\EE}{\mathop{\mathbb{E}}}
%\DeclareMathOperator*{\EE}{\mathbb{E}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\II}{\mathbb{I}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\Zplus}{\ZZ_{+}}

%\newcommand{\cO}{\mathcal{O}}
\newcommand{\cO}{O}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cE}{\mathcal{E}}


\newcommand{\tcO}{\tilde{\mathcal{O}}}

\newcommand{\partit}{\mathbb{P}}

\newcommand{\iid}{i.i.d.\xspace}
\newcommand{\ie}{i.e.\xspace}
\newcommand{\eg}{e.g.\xspace}


%%\newtheorem{Theorem}{Theorem}[section]
%\newtheorem{Theorem}{Theorem}
%% \newtheorem{Corollary}[Theorem]{Corollary}
%\newtheorem{Corollary}{Corollary}
%% \newtheorem{Lemma}[Theorem]{Lemma}
%\newtheorem{Lemma}{Lemma}
%%\newtheorem{Example}{Example}[section]
%\newtheorem{Example}[Theorem]{Example}
%
%%\theoremstyle{definition}
%%\newtheorem{definition}{Definition}
%%\newtheorem{example}{Example}
%\newtheorem{remark}{Remark}



%-----

\newcommand{\ignore}[1]{}%
\newcommand{\Xtn}{X^n}
\newcommand{\xtn}{x^n}
\newcommand{\xts}{x^*}
\newcommand{\Sym}{X}
\newcommand{\DeltaX}{\Delta_{\cX}}
\newcommand{\Deltak}{\Delta_k}
\newcommand{\realsp}{\RR_{\ge0}}
\newcommand{\upto}{,\ldots,}
\newcommand{\Sets}[1]{\left\{#1\right\}}
\newcommand{\sets}[1]{\{#1\}}
\newcommand{\Paren}[1]{\left(#1\right)}
\newcommand{\bE}{\EE}
\newcommand{\bEXnp}{\operatorname*{\bE}_{X^n\sim p^n}\;}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\cPkc}{\cP_k^{\text{const}}}

%Sets
\newcommand{\Sold}{S_{\text{old}}}
\newcommand{\Snew}{S_{\text{new}}}

%\renewcommand{\est}{q}
\newcommand{\cN}{{\cal N}}

%Loss
%\renewcommand{\loss}{r}
\newcommand{\rns}[1]{\loss_n(#1)}

%Regular loss
\newcommand{\rnqp}{\rns{q,p}}
\newcommand{\rnqP}{\rns{q,P}}
\newcommand{\rnqcP}{\rns{q,\cP}}
\newcommand{\rnqPp}{\rns{q,P'}}
\newcommand{\rncPp}{\rns{q,\cP'}}
\newcommand{\rncP}{\rns{\cP}}
\newcommand{\rnDk}{\rns{\Deltak}}

%Partition loss
\newcommand{\rnss}[2]{\loss_n^{#1}(#2)}
\newcommand{\rnPPs}[1]{\rnss{\PP}{#1}}
\newcommand{\rnPPqcP}{\rnPPs{q,\cP}}
\newcommand{\rnPPpqcP}{\rnss{\PP'}{q,\cP}}
\newcommand{\rnP}{\rns{P}}
\newcommand{\rnPp}{\rns{P'}}
\newcommand{\rnPPcP}{\rnPPs{\cP}}
\newcommand{\rnPPpcP}{\rnss{\PP'}{\cP}}
\newcommand{\rnqpp}{\rns{q,p'}}
\newcommand{\natest}{\cQ^{\text{nat}}}

\newcommand{\PPprm}{\PP_\sigma}

%Natural estimator loss
\newcommand{\rnNs}[1]{\loss_n^{\scriptscriptstyle\text{nat}}(#1)}
\newcommand{\rnNp}{\rnNs{\dist}}
\newcommand{\rnNss}[2]{\loss_n^{\scriptscriptstyle\text{nat}}(#1,#2)}
\newcommand{\rnNDk}{\rnNs{\Delta_k}}
\newcommand{\rnNqp}{\rnNs{\est,\dist}}



% wu
\newcommand{\Th}{^\mathrm{th}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\Prob}{\mathbb{P}}
\newcommand{\prob}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\pprob}[1]{\mathbb{P}[#1]}
\newcommand{\Binom}{\mathrm{Bin}}
\newcommand{\hyper}{\mathrm{Hyp}}

\newcommand{\pth}[1]{\left( #1 \right)}
\newcommand{\qth}[1]{\left[ #1 \right]}
\newcommand{\sth}[1]{\left\{ #1 \right\}}
\newcommand{\red}{\color{red}}
\newcommand{\blue}{\color{blue}}
\newcommand{\nb}[1]{{\sf\blue[#1]}}
\newcommand{\nbr}[1]{{\sf\red[#1]}}
\newcommand{\note}[1]{{\sf[#1]}}

\newcommand{\Sseen}{S_{\rm seen}}

\usepackage{prettyref}
% for prettyref
\newrefformat{eq}{(\ref{#1})}
\newrefformat{thm}{Theorem~\ref{#1}}
\newrefformat{th}{Theorem~\ref{#1}}
\newrefformat{chap}{Chapter~\ref{#1}}
\newrefformat{sec}{Section~\ref{#1}}
\newrefformat{algo}{Algorithm~\ref{#1}}
\newrefformat{fig}{Fig.~\ref{#1}}
\newrefformat{tab}{Table~\ref{#1}}
\newrefformat{rmk}{Remark~\ref{#1}}
\newrefformat{clm}{Claim~\ref{#1}}
\newrefformat{def}{Definition~\ref{#1}}
\newrefformat{cor}{Corollary~\ref{#1}}
\newrefformat{lmm}{Lemma~\ref{#1}}
\newrefformat{prop}{Proposition~\ref{#1}}
\newrefformat{pr}{Proposition~\ref{#1}}
\newrefformat{app}{Appendix~\ref{#1}}
\newrefformat{apx}{Appendix~\ref{#1}}
\newrefformat{ex}{Example~\ref{#1}}
\newrefformat{exer}{Exercise~\ref{#1}}
\newrefformat{soln}{Solution~\ref{#1}}

\newcommand{\sfN}{{\sf N}}
\newcommand{\sfL}{{\sf L}}


%% Data amplifier 

\newcommand{\lipf}{\ell_f}
\newcommand{\maxf}{\hat{f}}
\newcommand{\pf}{f(p)}
\newcommand{\empf}{E_f}
\newcommand{\propf}{H_f}
\newcommand{\perf}{L_f}
\newcommand{\smallf}{S_f}
\newcommand{\umax}{u_{\max}}

\newcommand{\psum}{p_{_S}}

\newcommand{\dTV}{d_{\rm TV}}

\newcommand{\Uno}{U_n(1)}
\newcommand{\Unin}{U_n(\infty)}
\newcommand{\Unnt}{U_n(nt)}
\newcommand{\UE}{U^{\scriptscriptstyle\rm E}}

\newcommand{\xn}{x^n}
\newcommand{\Xn}{X^n}
\newcommand{\Xnpm}{X^{n+m}}

\newcommand{\xnpom}{x_{n+1}^{n+m}}

\newcommand{\XNPOM}{X_{N+1}^{N+M}}
\newcommand{\Xnpom}{X_{n+1}^{n+m}}
\newcommand{\Xnpotn}{X_{n+1}^{n+tn}}

\newcommand{\xnp}{x^{n'}}

\newcommand{\Us}[1]{U^{\scriptscriptstyle\rm #1}}
\newcommand{\Usss}[3]{U^{\scriptscriptstyle\rm #1}(#2,#3)}

\newcommand{\UXnm}{\Usss{}{\Xn}{\Xnpom}} % \Unnp
\newcommand{\Uxnm}{\Usss{}{\xn}{\xnpom}} % \Unn
\newcommand{\UXntn}{\Usss{}{\Xn}{\Xnpotn}} % \Unnp

\newcommand{\UXNm}{\Usss{}{\NN}{\xnpom}} % \Unn

\newcommand{\UXNM}{\Usss{}{X^N}{\XNPOM}} % \Unn

\newcommand{\Uxnpm}{\Usss{}{\xnp}{m}} % \Unnp
\newcommand{\UXnpm}{\Usss{}{\xnp}{m}} % \Unnp

\newcommand{\UEXnm}{\Usss{E}{\Xn}{t}} % \UEnnp %% changed m to t

\newcommand{\UEXNm}{\Usss{E}{X^N}{t}} % \UEnnp  %5 changed m to t
\newcommand{\UExnm}{\Usss{E}{\xn}{m}} % \UEnnp
\newcommand{\UHXnm}{\Usss{H}{\Xn}{m}} % \UHnnp
\newcommand{\Uhxnm}{\Usss{h}{\xn}{m}}  % \Uhnnp

\newcommand{\UGT}{\Us{GT}} % \UGTnnp
\newcommand{\UGTXnm}{\Usss{GT}{\Xn}{m}} % \UGTnnp
\newcommand{\UGTxnm}{\Usss{GT}{\xn}{m}} % \UGTnnp
\newcommand{\UGTXnt}{\Usss{GT}{\Xn}{t}}
\newcommand{\UJxnm}{\Usss{J}{\xn}{m}} % \UETnnp
%\newcommand{\Uhnnp}{U_n^{\scriptscriptstyle\rm h}(m)}
%\newcommand{\Uhnnt}{U_n^{\scriptscriptstyle\rm h}(nt)}
\newcommand{\Uhnnt}{U_n^{\scriptscriptstyle h}(nt)}
\newcommand{\UGTnnt}{U_n^{\scriptscriptstyle\rm GT}(nt)}


%%% Shortened notation
\newcommand{\aUXnm}{U} % \Unnp
\newcommand{\aUxnm}{U} % \Unn

\newcommand{\aUXNm}{U}% \Unn

\newcommand{\aUXNM}{U } % \Unn

\newcommand{\aUxnpm}{\Usss{}{\xnp}{m}} % \Unnp
\newcommand{\aUXnpm}{\Usss{}{\xnp}{m}} % \Unnp

\newcommand{\aUEXnm}{\Us{E}} % \UEnnp

\newcommand{\aUEXNm}{\Us{E}} % \UEnnp
\newcommand{\aUExnm}{\Us{E}} % \UEnnp
\newcommand{\aUHXnm}{\Usss{H}{\Xn}{m}} % \UHnnp
\newcommand{\aUhxnm}{\Us{h}}  % \Uhnnp


\newcommand{\aUGT}{\Us{GT}} % \UGTnnp
\newcommand{\aUGTXnm}{\aUGT} % \UGTnnp
\newcommand{\aUGTxnm}{\aUGT} % \UGTnnp
\newcommand{\aUETXnm}{\Usss{ET}{\Xn}{m}}
\newcommand{\aUJxnm}{\Usss{J}{\xn}{m}} % \UETnnp
%\newcommand{\Uhnnp}{U_n^{\scriptscriptstyle\rm h}(m)}
%\newcommand{\Uhnnt}{U_n^{\scriptscriptstyle\rm h}(nt)}
\newcommand{\aUhnnt}{U_n^{\scriptscriptstyle h}(nt)}
\newcommand{\aUGTnnt}{U_n^{\scriptscriptstyle\rm GT}(nt)}

%\newcommand{\LE}{L^E(n,t)}
\newcommand{\LE}{\cE_{n,t}(U^{\scriptscriptstyle\rm E})}
%\newcommand{\LEnt}{L^E(n,t)}
\newcommand{\LEnt}{\cE_{n,t}(U^{\scriptscriptstyle\rm E})}
\newcommand{\LELnt}{\cE_{n,t}(U^{\scriptscriptstyle\rm L})}
\newcommand{\LElnt}{\cE_{n,t}(U^{\scriptscriptstyle \ell})}
\newcommand{\LEGTnt}{\cE_{n,t}(U^{\scriptscriptstyle \rm GT})}
%\newcommand{\LElnt}{L^{E^\ell}(n,t)}

\newcommand{\U}{U}
\newcommand{\Ut}{U}
\newcommand{\Up}{U}
\newcommand{\Uh}{U^{\scriptscriptstyle\rm h}}
\newcommand{\Uht}{U^{\scriptscriptstyle\rm h}}
\newcommand{\Ui}{U(\infty}
\newcommand{\Ug}{\hat{U}}
\newcommand{\Ugm}{\hat{U}}
\newcommand{\Ugnnt}{\hat{U}_n(nt)}
\newcommand{\Ugnm}{\hat{U}_n(m)}
\newcommand{\chckths}[1]{$\ll$#1$\gg$}
\newcommand{\binlmt}{k}
\newcommand{\mm}{m}
\newcommand{\LXnpm}{L^{\scriptscriptstyle\rm E}_{\Xn,p}(m)}
\newcommand{\Lxnpm}{L^{\scriptscriptstyle\rm E}_{\xn,p}(m)}
\newcommand{\LEnpm}{L^{\scriptscriptstyle\rm E}_{n,p}(m)}
\newcommand{\LEnm}{L^{\scriptscriptstyle\rm E}_{n}(m)}
\newcommand{\LJnm}{L^{\scriptscriptstyle\rm J}_{n}(m)}
\newcommand{\Lsnm}{L^*_n(m)}
\newcommand{\Lmtnpnp}{L_{n,p}^{m/2}(m)}
\newcommand{\Lmtnnp}{L_n^{m/2}(m)}
\newcommand{\MGnd}{M^{\scriptscriptstyle\rm GT}_n(\delta)}

\newcommand{\MEnd}{M^{\scriptscriptstyle\rm E}_n(\delta)}
\newcommand{\MJnd}{M^{\scriptscriptstyle\rm J}_n(\delta)}
\newcommand{\Msnd}{M^*_n(\delta)}
\newcommand{\Mmtnd}{M^{m/2}_n(\delta)}

\newcommand{\hJ}{h^{\scriptscriptstyle\rm J}}

\newcommand{\UET}{U^{\scriptscriptstyle\rm ET}}

\newcommand{\hET}{h^{\scriptscriptstyle\rm ET}}
\newcommand{\UJnnp}{U_n^{\scriptscriptstyle\rm J}(m)}
\newcommand{\UJ}{U^{\scriptscriptstyle\rm J}}
\newcommand{\UJt}{U^{\scriptscriptstyle\rm J}}
\newcommand{\UJp}{U^{\scriptscriptstyle\rm J}}
\newcommand{\Upoi}[1]{U^{\scriptscriptstyle\rm poi_{#1}}}
\newcommand{\Ubin}[2]{U^{\scriptscriptstyle\rm bin_{#1,#2}}}




\newcommand{\Urand}{U^{\scriptscriptstyle\rm \rand}}

\newcommand{\hrand}{h^{\scriptscriptstyle\rm \rand}}

\newcommand{\rand}{L}
\newcommand{\fixed}{\ell}
\newcommand{\diff}{\text{d}}
\newcommand{\bound}{B}

\newcommand{\hFGT}{h^{\scriptscriptstyle\rm GT}}

\newcommand{\DLt}{\xi_{\rand}(t)}
\ignore{
\newcommand{\Lpoinm}{L^{\scriptscriptstyle\rm  poi_r}_n(m)}
\newcommand{\LETnm}{L^{\textrm{ET}}_n(m)}
\newcommand{\LBnm}{L^{\scriptscriptstyle\rm Bin_{\binlmt,q}}_n(m)}
\newcommand{\MBnd}{M^{\scriptscriptstyle\rm Bin_{\binlmt,q}}_n(\delta)}
\newcommand{\Mpoirnd}{M^{\scriptscriptstyle\rm poi_{r}}_n(\delta)}
\newcommand{\Upoir}{\Upoi{r}}
\newcommand{\Ubinkq}{\Ubin{\binlmt}{q}}
}
\newcommand{\Lpoinm}{L^{\scriptscriptstyle\rm  P    }_n(m)}
\newcommand{\LETnm}{L^{\textrm{ET}}_n(m)}
\newcommand{\LBnm}{L^{\scriptscriptstyle\rm B}_n(m)}
\newcommand{\MBnd}{M^{\scriptscriptstyle\rm B} _n(\delta)}
\newcommand{\Mpoirnd}{M^{\scriptscriptstyle\rm P}_n(\delta)}
\newcommand{\Upoir}{U^{\scriptscriptstyle\rm P}}
\newcommand{\Ubinkq}{U^{\scriptscriptstyle\rm B}}

\newcommand{\UL}{U^{\scriptscriptstyle\rm L}}
\newcommand{\hypN}{R}
\newcommand{\hypn}{r}


%\newcommand{\USGT}{\Us{SGT}}

\newcommand{\ntotal}{n_{\text{total}}}
\newcommand{\hL}{h^{\scriptscriptstyle\rm L}}


\newcommand{\Bern}{\text{Bern}}



%\usepackage{amsmath,amsthm,amsfonts}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{coro}[theorem]{Corollary}
%\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prop}[theorem]{Proposition}

%\theoremstyle{definition}
%\newtheorem{definition}{Definition}
%\newtheorem{example}{Example}
%\newtheorem{remark}{Remark}

\renewcommand{\hat}{\widehat}
\newcommand{\wt}{\widetilde}


\newcommand{\calA}{{\mathcal{A}}}
\newcommand{\calB}{{\mathcal{B}}}
\newcommand{\calC}{{\mathcal{C}}}
\newcommand{\calD}{{\mathcal{D}}}
\newcommand{\calE}{{\mathcal{E}}}
\newcommand{\calF}{{\mathcal{F}}}
\newcommand{\calG}{{\mathcal{G}}}
\newcommand{\calH}{{\mathcal{H}}}
\newcommand{\calI}{{\mathcal{I}}}
\newcommand{\calJ}{{\mathcal{J}}}
\newcommand{\calK}{{\mathcal{K}}}
\newcommand{\calL}{{\mathcal{L}}}
\newcommand{\calM}{{\mathcal{M}}}
\newcommand{\calN}{{\mathcal{N}}}
\newcommand{\calO}{{\mathcal{O}}}
\newcommand{\calP}{{\mathcal{P}}}
\newcommand{\calQ}{{\mathcal{Q}}}
\newcommand{\calR}{{\mathcal{R}}}
\newcommand{\calS}{{\mathcal{S}}}
\newcommand{\calT}{{\mathcal{T}}}
\newcommand{\calU}{{\mathcal{U}}}
\newcommand{\calV}{{\mathcal{V}}}
\newcommand{\calW}{{\mathcal{W}}}
\newcommand{\calX}{{\mathcal{X}}}
\newcommand{\calY}{{\mathcal{Y}}}
\newcommand{\calZ}{{\mathcal{Z}}}

%% parenthesis
\newcommand{\bpth}[1]{\Bigg( #1 \Bigg)}
\newcommand{\bqth}[1]{\Bigg[ #1 \Bigg]}
\newcommand{\bsth}[1]{\Bigg\{ #1 \Bigg\}}
\newcommand{\xxx}{\textbf{xxx}\xspace}
\newcommand{\toprob}{{\xrightarrow{\Prob}}}
\newcommand{\tolp}[1]{{\xrightarrow{L^{#1}}}}
\newcommand{\toas}{{\xrightarrow{{\rm a.s.}}}}
\newcommand{\toae}{{\xrightarrow{{\rm a.e.}}}}
\newcommand{\todistr}{{\xrightarrow{{\rm D}}}}
\newcommand{\eqdistr}{{\stackrel{\rm D}{=}}}
\newcommand{\iiddistr}{{\stackrel{\text{\iid}}{\sim}}}
\newcommand{\var}{\mathsf{var}}
\newcommand\indep{\protect\mathpalette{\protect\independenT}{\perp}}
\def\independenT#1#2{\mathrel{\rlap{$#1#2$}\mkern2mu{#1#2}}}
\newcommand{\iprod}[2]{\left \langle #1, #2 \right\rangle}
\newcommand{\Iprod}[2]{\langle #1, #2 \rangle}
\newcommand{\indc}[1]{{\mathbf{1}_{\left\{{#1}\right\}}}}
\newcommand{\Indc}{\mathbf{1}}

\newcommand{\ones}{\mathbf{1}}
\newcommand{\identity}{\mathbf{I}}
\newcommand{\allones}{\mathbf{J}}
\newcommand{\bfP}{\mathbf{P}}

\newcommand{\TV}{\mathrm{TV}}

%% YP can not leave without these:
%\def\eqdef{\stackrel{\triangle}{=}}
\def\eqdef{\triangleq}
\newcommand{\mreals}{\ensuremath{\mathbb{R}}}
\newcommand{\mconst}{\ensuremath{\mathrm{const}}}
\def\EE{\mathbb{E}\,}
\def\PP{\mathbb{P}}




%%%%%%%%%%%%%%%%%%%%%%%%%% tikz %%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{tikz}
%\usepackage{signalflowdiagram}
\usetikzlibrary{matrix,arrows,calc,shapes,backgrounds}
\usetikzlibrary{shapes.callouts,decorations.text} 

%\usetikzlibrary{matrix.skeleton}

\usetikzlibrary{shapes.misc}

\tikzset{cross/.style={cross out, draw=black, minimum size=2*(#1-\pgflinewidth), inner sep=0pt, outer sep=0pt},
%default radius will be 1pt. 
cross/.default={1pt}}

\tikzstyle{int}=[draw, fill=blue!20, minimum size=2em]
\tikzstyle{dot}=[circle, draw, fill=blue!20, minimum size=2em]
\tikzstyle{dotred}=[circle, draw, fill=red!20, minimum size=2em]
\tikzstyle{init} = [pin edge={to-,thin,black}]
\tikzstyle{initred} = [pin edge={to-,thin,red}]
\tikzstyle{plan}=[draw, fill=blue!20, minimum size=2em, text width=5em, rounded corners,align=center]
\tikzstyle{planwide}=[draw, fill=blue!20, minimum size=2em, text width=8em, rounded corners,align=center]
%\newcommand{\tikzmark}[1]{\tikz[overlay,baseline,remember picture] \node[anchor=base] (#1) {};}
%\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture] \node (#1) {};}

%
%\def\firstcircle{(90:1.75cm) circle (2.5cm)}
%\def\secondcircle{(210:1.75cm) circle (2.5cm)}
%\def\thirdcircle{(330:1.75cm) circle (2.5cm)}


\usepackage{tikz-cd}
\newcommand{\colorball}[1]{\tikz{\draw[fill=#1,draw=#1] (0,0) circle (3.5pt);}}
\newcommand{\whiteball}{\tikz{\draw[draw=black] (0,0) circle (3.5pt);}}


\usepackage{pgfplots}
\usepackage{pgffor}

\pgfplotsset{
    standard/.style={
        axis x line=bottom,
        axis y line=middle,
				clip=false,
    enlargelimits=upper,
%        enlarge x limits=0.15,
%        enlarge y limits=0.15,
        every axis x label/.style={at={(current axis.right of origin)},anchor=west},
        every axis y label/.style={at={(current axis.above origin)},anchor=south}
    }
}
\pgfkeys{/pgfplots/scale/.style={
  x post scale=#1,
  y post scale=#1,
  z post scale=#1}
}


\pgfplotsset{soldot/.style={color=blue,only marks,mark=*}}
\pgfplotsset{holdot/.style={color=blue,fill=white,only marks,mark=*}}



%\pgfkeys{/pgfplots/axis labels at tip/.style={
    %xlabel style={at={(current axis.right of origin)}, xshift=1.5ex, anchor=center},
    %ylabel style={at={(current axis.above origin)}, yshift=1.5ex, anchor=center}}
%}

%%%%%%%%%%%%%%%%%%%%%%%%%% tikz %%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% CONDITIONAL COMPILATION TRICK %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% Usage: \ifmapx TEXT \fi 
%%%%%%%%%%%% The "TEXT" will only appear if *_apx.tex is compiled   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Ok, all this pain is to produce the name "xxx_apx" with characters
% of category 12, since this is what jobname expands to. What I used is the
% trick that \string\abc produces a sequence of tokens (\,a,b,c) all of category 12, 
% so I only need to kill the front \_12 which is what mkillslash macro doing.
%
%%%%%%%%%%%%
\newif\ifmapx
{\catcode`/=0 \catcode`\\=12/gdef/mkillslash\#1{#1}}
\edef\jobnametmp{\expandafter\string\csname horo_apx\endcsname}
\edef\jobnameapx{\expandafter\mkillslash\jobnametmp}
\edef\jobnameexpand{\jobname}
\ifx\jobnameexpand\jobnameapx
\mapxtrue
\else
\mapxfalse
\fi

\long\def\apxonly#1{\ifmapx{\color{blue}#1}\fi}


\title{Sample complexity of population recovery}

 \coltauthor{\Name{Yury Polyanskiy} \Email{yp@mit.edu}\\
 \addr Department of EECS, MIT, Cambridge, MA, USA
 \AND
 \Name{Ananda Theertha Suresh} \Email{theertha@google.com}\\
 \addr Google Research, New York, NY, USA
 \AND
 \Name{Yihong Wu} \Email{yihong.wu@yale.edu}\\
 \addr Department of Statistics and Data Science, Yale University, New Haven, CT, USA
 }





\input{main}

\section*{Acknowledgement}
The research was supported (in part) by the Center for Science of Information (CSoI),
an NSF Science and Technology Center, under grant agreement CCF-09-39370, 
ITS-1447879, CCF-1527105, NSF CAREER awards CCF-12-53205 and CCF-1651588.

%\bibliographystyle{alpha}
%\bibliography{strings,pop}
%\bibliography{IEEEabrv,strings,reports,wu_big}

\begin{thebibliography}{26}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Abramowitz and Stegun(1964)]{AS64}
M.~Abramowitz and I.~A. Stegun.
\newblock \emph{{Handbook of mathematical functions with formulas, graphs, and
  mathematical tables}}.
\newblock Wiley-Interscience, New York, NY, 1964.

\bibitem[Batman et~al.(2013)Batman, Impagliazzo, Murray, and
  Paturi]{batman2013finding}
Lucia Batman, Russell Impagliazzo, Cody Murray, and Ramamohan Paturi.
\newblock Finding heavy hitters from lossy or noisy data.
\newblock In \emph{Approximation, Randomization, and Combinatorial
  Optimization. Algorithms and Techniques}, pages 347--362. Springer, 2013.

\bibitem[Borwein and Erd\'elyi(1997)]{borwein1997littlewood}
Peter Borwein and Tam\'as Erd\'elyi.
\newblock Littlewood-type problems on subarcs of the unit circle.
\newblock \emph{Indiana University Mathematics Journal}, 46\penalty0
  (4):\penalty0 1323, 1997.

\bibitem[Cai and Low(2005)]{cai2005nonquadratic}
T~Tony Cai and Mark~G Low.
\newblock Nonquadratic estimators of a quadratic functional.
\newblock \emph{The Annals of Statistics}, pages 2930--2956, 2005.

\bibitem[Cowen(1988)]{cowen1988linear}
Carl~C Cowen.
\newblock Linear fractional composition operators on {$H^2$}.
\newblock \emph{Integral equations and operator theory}, 11\penalty0
  (2):\penalty0 151--160, 1988.

\bibitem[De et~al.(2016{\natexlab{a}})De, O'Donnell, and
  Servedio]{de2016optimal}
Anindya De, Ryan O'Donnell, and Rocco Servedio.
\newblock Optimal mean-based algorithms for trace reconstruction.
\newblock \emph{arXiv preprint arXiv:1612.03148}, 2016{\natexlab{a}}.

\bibitem[De et~al.(2016{\natexlab{b}})De, Saks, and Tang]{DST16}
Anindya De, Michael Saks, and Sijian Tang.
\newblock Noisy population recovery in polynomial time.
\newblock \emph{arXiv preprint arXiv:1602.07616}, 2016{\natexlab{b}}.

\bibitem[De et~al.(2017)De, O'Donnell, and Servedio]{de2017sharp}
Anindya De, Ryan O'Donnell, and Rocco Servedio.
\newblock Sharp bounds for population recovery.
\newblock \emph{arXiv preprint arXiv:1703.01474}, 2017.

\bibitem[Dvir et~al.(2012)Dvir, Rao, Wigderson, and Yehudayoff]{DRWY12}
Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff.
\newblock Restriction access.
\newblock In \emph{Proceedings of the 3rd Innovations in Theoretical Computer
  Science Conference}, pages 19--33. ACM, 2012.

\bibitem[Fan et~al.(2015)Fan, Rigollet, and Wang]{FRW15}
Jianqing Fan, Philippe Rigollet, and Weichen Wang.
\newblock Estimation of functionals of sparse covariance matrices.
\newblock \emph{The Annals of Statistics}, 43\penalty0 (6):\penalty0 2706,
  2015.

\bibitem[Feldman et~al.(2008)Feldman, O'Donnell, and
  Servedio]{feldman2008learning}
Jon Feldman, Ryan O'Donnell, and Rocco~A Servedio.
\newblock Learning mixtures of product distributions over discrete domains.
\newblock \emph{SIAM Journal on Computing}, 37\penalty0 (5):\penalty0
  1536--1564, 2008.

\bibitem[Gradshteyn and Ryzhik(2007)]{GR}
I.~S. Gradshteyn and I.~M. Ryzhik.
\newblock \emph{{Table of Integrals Series and Products}}.
\newblock Academic Press, New York, NY, seventh edition, 2007.

\bibitem[Ibragimov et~al.(1987)Ibragimov, Nemirovskii, and Khas'minskii]{INK87}
I.A. Ibragimov, A.S. Nemirovskii, and R.Z. Khas'minskii.
\newblock Some problems on nonparametric estimation in gaussian white noise.
\newblock \emph{Theory of Probability \& Its Applications}, 31\penalty0
  (3):\penalty0 391--406, 1987.

\bibitem[Kearns et~al.(1994)Kearns, Mansour, Ron, Rubinfeld, Schapire, and
  Sellie]{kearns1994learnability}
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert~E Schapire,
  and Linda Sellie.
\newblock On the learnability of discrete distributions.
\newblock In \emph{Proceedings of the twenty-sixth annual ACM symposium on
  Theory of computing}, pages 273--282. ACM, 1994.

\bibitem[Le~Cam(1986)]{Lecam86}
Lucien Le~Cam.
\newblock \emph{Asymptotic methods in statistical decision theory}.
\newblock Springer-Verlag, New York, NY, 1986.

\bibitem[Li et~al.(2015)Li, Rabani, Schulman, and Swamy]{li2015learning}
Jian Li, Yuval Rabani, Leonard~J Schulman, and Chaitanya Swamy.
\newblock Learning arbitrary statistical mixtures of discrete distributions.
\newblock In \emph{Proceedings of the Forty-Seventh Annual ACM on Symposium on
  Theory of Computing}, pages 743--752. ACM, 2015.

\bibitem[Lounici(2014)]{Lounici14}
Karim Lounici.
\newblock High-dimensional covariance matrix estimation with missing
  observations.
\newblock \emph{Bernoulli}, 20\penalty0 (3):\penalty0 1029--1058, 2014.

\bibitem[Lovett and Zhang(2015)]{LZ15}
Shachar Lovett and Jiapeng Zhang.
\newblock Improved noisy population recovery, and reverse {B}onami-{B}eckner
  inequality for sparse functions.
\newblock In \emph{Proceedings of the Forty-Seventh Annual ACM on Symposium on
  Theory of Computing}, pages 137--142. ACM, 2015.

\bibitem[Moitra and Saks(2013)]{MS13}
Ankur Moitra and Michael Saks.
\newblock A polynomial time algorithm for lossy population recovery.
\newblock In \emph{Foundations of Computer Science (FOCS), 2013 IEEE 54th
  Annual Symposium on}, pages 110--116. IEEE, 2013.

\bibitem[Nazarov and Peres(2016)]{nazarov2016trace}
F.~Nazarov and Y.~Peres.
\newblock Trace reconstruction with $\exp({O}(n^{1/3}))$ samples.
\newblock \emph{arXiv preprint arXiv:1612.03599}, 2016.

\bibitem[Newman(1975)]{Newman75}
DJ~Newman.
\newblock A simple proof of {W}iener’s $1/f$ theorem.
\newblock \emph{Proceedings of the American Mathematical Society}, 48\penalty0
  (1):\penalty0 264--265, 1975.

\bibitem[Orlitsky et~al.(2016)Orlitsky, Suresh, and Wu]{OSW16}
Alon Orlitsky, Ananda~Theertha Suresh, and Yihong Wu.
\newblock Optimal prediction of the number of unseen species.
\newblock \emph{Proceedings of the National Academy of Sciences (PNAS)},
  113\penalty0 (47):\penalty0 13283--13288, 2016.

\bibitem[Simon(2011)]{simon2011convexity}
Barry Simon.
\newblock \emph{Convexity: An analytic viewpoint}.
\newblock Cambridge University Press, 2011.

\bibitem[Szeg{\"o}(1975)]{orthogonal.poly}
G.~Szeg{\"o}.
\newblock \emph{{Orthogonal polynomials}}.
\newblock American Mathematical Society, Providence, RI, 4th edition, 1975.

\bibitem[Tsybakov(2009)]{Tsybakov09}
A.~B. Tsybakov.
\newblock \emph{Introduction to Nonparametric Estimation}.
\newblock Springer Verlag, New York, NY, 2009.

\bibitem[Wigderson and Yehudayoff(2012)]{WY12}
Avi Wigderson and Amir Yehudayoff.
\newblock Population recovery and partial identification.
\newblock In \emph{Foundations of Computer Science (FOCS), 2012 IEEE 53rd
  Annual Symposium on}, pages 390--399. IEEE, 2012.

\end{thebibliography}


\end{document}

1702.05574.extracted_bib
[Abramowitz and Stegun(1964)]{AS64 M.~Abramowitz and I.~A. Stegun. \newblock {Handbook of mathematical functions with formulas, graphs, and mathematical tables. \newblock Wiley-Interscience, New York, NY, 1964.
1702.05574.extracted_bib
[Batman et~al.(2013)Batman, Impagliazzo, Murray, and Paturi]{batman2013finding Lucia Batman, Russell Impagliazzo, Cody Murray, and Ramamohan Paturi. \newblock Finding heavy hitters from lossy or noisy data. \newblock In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 347--362. Springer, 2013.
1702.05574.extracted_bib
[Borwein and Erd\'elyi(1997)]{borwein1997littlewood Peter Borwein and Tam\'as Erd\'elyi. \newblock Littlewood-type problems on subarcs of the unit circle. \newblock Indiana University Mathematics Journal, 46\penalty0 (4):\penalty0 1323, 1997.
1702.05574.extracted_bib
[Cai and Low(2005)]{cai2005nonquadratic T~Tony Cai and Mark~G Low. \newblock Nonquadratic estimators of a quadratic functional. \newblock The Annals of Statistics, pages 2930--2956, 2005.
1702.05574.extracted_bib
[Cowen(1988)]{cowen1988linear Carl~C Cowen. \newblock Linear fractional composition operators on {$H^2$. \newblock Integral equations and operator theory, 11\penalty0 (2):\penalty0 151--160, 1988.
1702.05574.extracted_bib
[De et~al.(2016{\natexlab{a)De, O'Donnell, and Servedio]{de2016optimal Anindya De, Ryan O'Donnell, and Rocco Servedio. \newblock Optimal mean-based algorithms for trace reconstruction. \newblock arXiv preprint arXiv:1612.03148, 2016{\natexlab{a.
1702.05574.extracted_bib
[De et~al.(2016{\natexlab{b)De, Saks, and Tang]{DST16 Anindya De, Michael Saks, and Sijian Tang. \newblock Noisy population recovery in polynomial time. \newblock arXiv preprint arXiv:1602.07616, 2016{\natexlab{b.
1702.05574.extracted_bib
[De et~al.(2017)De, O'Donnell, and Servedio]{de2017sharp Anindya De, Ryan O'Donnell, and Rocco Servedio. \newblock Sharp bounds for population recovery. \newblock arXiv preprint arXiv:1703.01474, 2017.
1702.05574.extracted_bib
[Dvir et~al.(2012)Dvir, Rao, Wigderson, and Yehudayoff]{DRWY12 Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff. \newblock Restriction access. \newblock In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 19--33. ACM, 2012.
1702.05574.extracted_bib
[Fan et~al.(2015)Fan, Rigollet, and Wang]{FRW15 Jianqing Fan, Philippe Rigollet, and Weichen Wang. \newblock Estimation of functionals of sparse covariance matrices. \newblock The Annals of Statistics, 43\penalty0 (6):\penalty0 2706, 2015.
1702.05574.extracted_bib
[Feldman et~al.(2008)Feldman, O'Donnell, and Servedio]{feldman2008learning Jon Feldman, Ryan O'Donnell, and Rocco~A Servedio. \newblock Learning mixtures of product distributions over discrete domains. \newblock SIAM Journal on Computing, 37\penalty0 (5):\penalty0 1536--1564, 2008.
1702.05574.extracted_bib
[Gradshteyn and Ryzhik(2007)]{GR I.~S. Gradshteyn and I.~M. Ryzhik. \newblock {Table of Integrals Series and Products. \newblock Academic Press, New York, NY, seventh edition, 2007.
1702.05574.extracted_bib
[Ibragimov et~al.(1987)Ibragimov, Nemirovskii, and Khas'minskii]{INK87 I.A. Ibragimov, A.S. Nemirovskii, and R.Z. Khas'minskii. \newblock Some problems on nonparametric estimation in gaussian white noise. \newblock Theory of Probability \& Its Applications, 31\penalty0 (3):\penalty0 391--406, 1987.
1702.05574.extracted_bib
[Kearns et~al.(1994)Kearns, Mansour, Ron, Rubinfeld, Schapire, and Sellie]{kearns1994learnability Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert~E Schapire, and Linda Sellie. \newblock On the learnability of discrete distributions. \newblock In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 273--282. ACM, 1994.
1702.05574.extracted_bib
[Le~Cam(1986)]{Lecam86 Lucien Le~Cam. \newblock Asymptotic methods in statistical decision theory. \newblock Springer-Verlag, New York, NY, 1986.
1702.05574.extracted_bib
[Li et~al.(2015)Li, Rabani, Schulman, and Swamy]{li2015learning Jian Li, Yuval Rabani, Leonard~J Schulman, and Chaitanya Swamy. \newblock Learning arbitrary statistical mixtures of discrete distributions. \newblock In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 743--752. ACM, 2015.
1702.05574.extracted_bib
[Lounici(2014)]{Lounici14 Karim Lounici. \newblock High-dimensional covariance matrix estimation with missing observations. \newblock Bernoulli, 20\penalty0 (3):\penalty0 1029--1058, 2014.
1702.05574.extracted_bib
[Lovett and Zhang(2015)]{LZ15 Shachar Lovett and Jiapeng Zhang. \newblock Improved noisy population recovery, and reverse {Bonami-{Beckner inequality for sparse functions. \newblock In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 137--142. ACM, 2015.
1702.05574.extracted_bib
[Moitra and Saks(2013)]{MS13 Ankur Moitra and Michael Saks. \newblock A polynomial time algorithm for lossy population recovery. \newblock In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 110--116. IEEE, 2013.
1702.05574.extracted_bib
[Nazarov and Peres(2016)]{nazarov2016trace F.~Nazarov and Y.~Peres. \newblock Trace reconstruction with $\exp({O(n^{1/3))$ samples. \newblock arXiv preprint arXiv:1612.03599, 2016.
1702.05574.extracted_bib
[Newman(1975)]{Newman75 DJ~Newman. \newblock A simple proof of {Wiener’s $1/f$ theorem. \newblock Proceedings of the American Mathematical Society, 48\penalty0 (1):\penalty0 264--265, 1975.
1702.05574.extracted_bib
[Orlitsky et~al.(2016)Orlitsky, Suresh, and Wu]{OSW16 Alon Orlitsky, Ananda~Theertha Suresh, and Yihong Wu. \newblock Optimal prediction of the number of unseen species. \newblock Proceedings of the National Academy of Sciences (PNAS), 113\penalty0 (47):\penalty0 13283--13288, 2016.
1702.05574.extracted_bib
[Simon(2011)]{simon2011convexity Barry Simon. \newblock Convexity: An analytic viewpoint. \newblock Cambridge University Press, 2011.
1702.05574.extracted_bib
[Szeg{\"o(1975)]{orthogonal.poly G.~Szeg{\"o. \newblock {Orthogonal polynomials. \newblock American Mathematical Society, Providence, RI, 4th edition, 1975.
1702.05574.extracted_bib
[Tsybakov(2009)]{Tsybakov09 A.~B. Tsybakov. \newblock Introduction to Nonparametric Estimation. \newblock Springer Verlag, New York, NY, 2009.
1702.05574.extracted_bib
[Wigderson and Yehudayoff(2012)]{WY12 Avi Wigderson and Amir Yehudayoff. \newblock Population recovery and partial identification. \newblock In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 390--399. IEEE, 2012.