  We address the problem of estimating the difference between two probability
densities. A naive approach is a two-step procedure of first estimating two
densities separately and then computing their difference. However, such a
two-step procedure does not necessarily work well because the first step is
performed without regard to the second step and thus a small error incurred in
the first stage can cause a big error in the second stage. In this paper, we
propose a single-shot procedure for directly estimating the density difference
without separately estimating two densities. We derive a non-parametric
finite-sample error bound for the proposed single-shot density-difference
estimator and show that it achieves the optimal convergence rate. The
usefulness of the proposed method is also demonstrated experimentally.
