  We study the problem of learning nonparametric distributions in a finite
mixture, and establish tight bounds on the sample complexity for learning the
component distributions in such models. Namely, we are given i.i.d. samples
from a pdf $f$ where $$ f=w_1f_1+w_2f_2, \quad w_1+w_2=1, \quad w_1,w_2>0 $$
and we are interested in learning each component $f_i$. Without any assumptions
on $f_i$, this problem is ill-posed. In order to identify the components $f_i$,
we assume that each $f_i$ can be written as a convolution of a Gaussian and a
compactly supported density $\nu_i$ with $\text{supp}(\nu_1)\cap
\text{supp}(\nu_2)=\emptyset$.
  Our main result shows that $(\frac{1}{\varepsilon})^{\Omega(\log\log
\frac{1}{\varepsilon})}$ samples are required for estimating each $f_i$. The
proof relies on a quantitative Tauberian theorem that yields a fast rate of
approximation with Gaussians, which may be of independent interest. To show
this is tight, we also propose an algorithm that uses
$(\frac{1}{\varepsilon})^{O(\log\log \frac{1}{\varepsilon})}$ samples to
estimate each $f_i$. Unlike existing approaches to learning latent variable
models based on moment-matching and tensor methods, our proof instead involves
a delicate analysis of an ill-conditioned linear system via orthogonal
functions. Combining these bounds, we conclude that the optimal sample
complexity of this problem properly lies in between polynomial and exponential,
which is not common in learning theory.
