Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures
This provides fundamental limits for learning latent variable models in statistics and machine learning, with implications for mixture modeling, but it is incremental as it builds on prior work in nonparametric mixtures.
The paper tackles the problem of learning nonparametric component distributions in a two-component mixture model, establishing that the sample complexity for estimating each component is tight at (1/ε)^(Θ(log log 1/ε)), which lies between polynomial and exponential rates.
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 $ν_i$ with $\text{supp}(ν_1)\cap \text{supp}(ν_2)=\emptyset$. Our main result shows that $(\frac{1}{\varepsilon})^{Ω(\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.