# Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures

arXiv: https://arxiv.org/abs/2203.15150 · HTML: https://mlsanity.com/paper/2203.15150/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 79 references that are in the map.
- First posted on arXiv 28 Mar 2022.

## Builds on (most cited first, 25 of 25)

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Learning latent causal graphs via mixture oracles](https://mlsanity.com/paper/2106.15563/) (2021)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Tight bounds for learning a mixture of two gaussians](https://mlsanity.com/paper/1404.4997/) (2014)
- [Some Theoretical Insights into Wasserstein GANs](https://mlsanity.com/paper/2006.02682/) (2020)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression](https://mlsanity.com/paper/2006.02601/) (2020)
- [Spectral Experts for Estimating Mixtures of Linear Regressions](https://mlsanity.com/paper/1306.3729/) (2013)
- [Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses](https://mlsanity.com/paper/1902.03511/) (2019)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Sample-Optimal Density Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1506.00671/) (2015)
- [Identifiability of Nonparametric Mixture Models and Bayes Optimal Clustering](https://mlsanity.com/paper/1802.04397/) (2018)
- [A Population Background for Nonparametric Density-Based Clustering](https://mlsanity.com/paper/1408.1381/) (2014)
- [Source Identification for Mixtures of Product Distributions](https://mlsanity.com/paper/2012.14540/) (2020)
- [When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity](https://mlsanity.com/paper/1308.2853/) (2013)
- [Uniform Consistency in Nonparametric Mixture Models](https://mlsanity.com/paper/2108.14003/) (2021)
- [Learning Arbitrary Statistical Mixtures of Discrete Distributions](https://mlsanity.com/paper/1504.02526/) (2015)
- [Hadamard Extensions and the Identification of Mixtures of Product Distributions](https://mlsanity.com/paper/2101.11688/) (2021)
- [Sparse Solutions to Nonnegative Linear Systems and Applications](https://mlsanity.com/paper/1501.01689/) (2015)
- [High-Dimensional Non-Parametric Density Estimation in Mixed Smooth Sobolev Spaces](https://mlsanity.com/paper/2006.03696/) (2020)
- [Finite state space non parametric Hidden Markov Models are in general identifiable](https://mlsanity.com/paper/1306.4657/) (2013)
- [A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k](https://mlsanity.com/paper/1506.01367/) (2015)

## Built on by (most cited first, 3 of 3)

- [Sample Complexity Using Infinite Multiview Models](https://mlsanity.com/paper/2302.04292/) (2023)
- [Generalized Identifiability Bounds for Mixture Models with Grouped Samples](https://mlsanity.com/paper/2207.11164/) (2022)
- [Model-free Estimation of Latent Structure via Multiscale Nonparametric Maximum Likelihood](https://mlsanity.com/paper/2410.22248/) (2024)

## Abstract (arXiv)

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=w1f1+w2f2, quad w1+w2=1, quad w1,w2>0  and we are interested in learning each component fi. Without any assumptions on fi, this problem is ill-posed. In order to identify the components fi, we assume that each fi can be written as a convolution of a Gaussian and a compactly supported density nui with supp(nu1)cap supp(nu2)=emptyset. Our main result shows that (frac1varepsilon)^Omega(loglog frac1varepsilon) samples are required for estimating each fi. 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 (frac1varepsilon)^O(loglog frac1varepsilon) samples to estimate each fi. 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.