Density Estimation via Discrepancy Based Adaptive Sequential Partition
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 also show how it can be utilized to find good initializations for k-means.
The authors propose an adaptive partitioning method to fit a piecewise constant density estimate. They bound the integration error and get standard Monte Carlo bounds (O(1/\sqrt{n})) for their method. The method (or a variant---I am not quite sure) is tested on a set of synthetic data and a k-means initialization task.
Novelty: there are a fair number of adaptive partitioning density estimation methods in existence that the authors omit (Darbellay and Vajda, 1999; Petralia, Vogelstein, and Dunson, 2013; etc). Some of these are designed for high dimensions, some function in lower dimensions. In general, this space is fairly well studied but there is room for serious theoretical analysis. A much stronger result than the standard Monte Carlo integration rates would be something like rates in Hellinger or Lp distance, which are generally not dimension-free. These rates and associated traits (adaptivity to intrinsic dimension, shape constraints, etc) are generally much more predictive of how a method performs in the wild than simple MC integration rates.  Impact: this method relies on star discrepancy to make partition selections and bound the error. However, this metric is generally impractical as it requires a supremum over all d-dimensional sub-rectangles, which is computationally burdensome. The authors suggest a work around, but this destroys their rate guarantees. This method would be quite slow in its original form and not theoretically supported in its modified form.  Clarity: I had some trouble following this paper. Aside from some random typos, some of the ideas were not well explained. For instance, what is the intuition behind using gaps? How does the scaling step relate? Additionally, I found a few of the experimental numbers puzzling. KDE computations were quite slow, while computations with this method were quite fast. Given the general simplicity of a KDE and the complexity of star discrepancy, I would expect those numbers to be reversed. There must be some aspect of the implementation that is not well explained.