Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more
It provides a general recipe for Hellinger distance estimation that enables fast algorithms for important density classes, addressing a gap in existing theory.
The paper extends the minimum-distance estimator approach from total variation to Hellinger distance for density estimation, yielding near-linear time algorithms for univariate mixtures of log-concave densities and mixtures of Gaussians with near-optimal sample complexity.
We study the task of density estimation, where we hope to accurately estimate a probability density from $n$ samples. A textbook method for density estimation in total variation distance is the minimum-distance estimator approach, where we conclude both the algorithm and the analysis merely from bounding the VC dimension of a particular concept class (the so-called Yatracos class). While this technique has originally yielded sharp guarantees primarily for total variation distance, in this work we extend the minimum-distance estimator approach for learning within Hellinger distance. Our main observation is that we may produce an analogous recipe for Hellinger (where we only require bounding the VC dimension of a related concept class) by drawing connections to recent results yielding reverse data processing inequalities. This recipe is flexible enough to accommodate fast algorithms originally designed for total variation distance; by modifying the approach of Acharya et al. (2017) we conclude the first near-linear time algorithm for learning classes including univariate mixtures of log-concave densities and mixtures of Gaussians (with arbitrary variances), with near-optimal sample complexity.