Universal estimation of divergence for continuous distributions via data-dependent partitions

We present a universal estimator of the divergence D(P||Q) for two arbitrary continuous distributions P and Q satisfying certain regularity conditions. This algorithm, which observes i.i.d. samples from both P and Q, is based on the estimation of the Radon-Nikodym derivative ^ via a datadependent partition of the observation space. Strong convergence of this estimator is proved with an empirically equivalent segmentation of the space. This basic estimator is further improved by adaptive partitioning schemes and by bias correction. In the simulations, we compare our estimators with the plug-in estimator and estimators based on other partitioning approaches. Experimental results show that our methods achieve the best convergence performance in most of the tested cases.