Density Estimation via Discrepancy Based Adaptive Sequential Partition
This work addresses density estimation for statistical modeling, offering a simple and efficient algorithm with theoretical guarantees, though it appears incremental as it builds on existing discrepancy concepts.
The authors tackled the problem of nonparametric density estimation from i.i.d. observations by proposing a method that uses discrepancy to adaptively partition the domain into a piecewise constant function, achieving a provable convergence rate and demonstrating efficiency in applications like k-means initialization.
Given $iid$ observations from an unknown absolute continuous distribution defined on some domain $Ω$, we propose a nonparametric method to learn a piecewise constant function to approximate the underlying probability density function. Our density estimate is a piecewise constant function defined on a binary partition of $Ω$. The key ingredient of the algorithm is to use discrepancy, a concept originates from Quasi Monte Carlo analysis, to control the partition process. The resulting algorithm is simple, efficient, and has a provable convergence rate. We empirically demonstrate its efficiency as a density estimation method. We present its applications on a wide range of tasks, including finding good initializations for k-means.