Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures

Abstract

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 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 supp(_1) supp(_2)=. Our main result shows that (1)^( 1) 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 (1)^O( 1) 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.

Tasks

Reproductions