Sample-Efficient Learning of Mixtures
  We consider PAC learning of probability distributions (a.k.a. density
estimation), where we are given an i.i.d. sample generated from an unknown
target distribution, and want to output a distribution that is close to the
target in total variation distance. Let $\mathcal F$ be an arbitrary class of
probability distributions, and let $\mathcal{F}^k$ denote the class of
$k$-mixtures of elements of $\mathcal F$. Assuming the existence of a method
for learning $\mathcal F$ with sample complexity $m_{\mathcal{F}}(\epsilon)$,
we provide a method for learning $\mathcal F^k$ with sample complexity
$O({k\log k \cdot m_{\mathcal F}(\epsilon) }/{\epsilon^{2}})$. Our mixture
learning algorithm has the property that, if the $\mathcal F$-learner is
proper/agnostic, then the $\mathcal F^k$-learner would be proper/agnostic as
well.
This general result enables us to improve the best known sample complexity
upper bounds for a variety of important mixture classes. First, we show that
the class of mixtures of $k$ axis-aligned Gaussians in $\mathbb{R}^d$ is
PAC-learnable in the agnostic setting with $\widetilde{O}({kd}/{\epsilon ^ 4})$
samples, which is tight in $k$ and $d$ up to logarithmic factors. Second, we
show that the class of mixtures of $k$ Gaussians in $\mathbb{R}^d$ is
PAC-learnable in the agnostic setting with sample complexity
$\widetilde{O}({kd^2}/{\epsilon ^ 4})$, which improves the previous known
bounds of $\widetilde{O}({k^3d^2}/{\epsilon ^ 4})$ and
$\widetilde{O}(k^4d^4/\epsilon ^ 2)$ in its dependence on $k$ and $d$. Finally,
we show that the class of mixtures of $k$ log-concave distributions over
$\mathbb{R}^d$ is PAC-learnable using
$\widetilde{O}(d^{(d+5)/2}\epsilon^{-(d+9)/2}k)$ samples.
