On Estimating L22 Divergence.

Akshay Krishnamurthy, Kirthevasan Kandasamy, Barnabás Póczos, Larry A. WassermanAISTATS 2015 · OpenReview

Abstract: We give a comprehensive theoretical characterization of a nonparametric estimator for the $L_2^2$ divergence between two continuous distributions. We first bound the rate of convergence of our estimator, proving its minimax optimality. Crucially, we demonstrate that for sufficiently smooth densities, the estimator achieves a parametric convergence rate, effectively bypassing the curse of dimensionality. Finally, we establish the asymptotic normality of the estimator, enabling the construction of principled confidence intervals.

Introduction

Quantifying the difference between probability distributions is a fundamental task in statistics and machine learning. While the Kullback-Leibler (KL) divergence is a standard choice, it possesses several drawbacks: it is asymmetric and can become infinite if the distributions do not share the same support. In contrast, the $L_2^2$ divergence—defined as $D(p, q) = \int (p(x) - q(x))^2 dx$—is symmetric, geometrically intuitive, and robust.

Despite these advantages, estimating $L_2^2$ divergence from finite samples is challenging, particularly in continuous settings. This work provides a theoretical "owner's manual" for a kernel-based nonparametric estimator, establishing its optimality and practical utility for statistical inference.

Methodology

The estimator is based on a kernel multi-sample U-statistic. The $L_2^2$ divergence can be expanded into three components: $\int p^2 + \int q^2 - 2\int pq$. The proposed method utilizes data splitting to ensure independence between the estimates of these terms.

The Role of Undersmoothing

A key technical insight of this work is the requirement for "undersmoothing." In standard density estimation, the bandwidth $h$ is chosen to balance bias and variance. However, when estimating a functional of the density (like an integral), the optimal strategy is to use a smaller bandwidth than usual. This reduces bias significantly; while it increases variance at the point-level, this variance is effectively averaged out during the integration process, leading to a more accurate global estimate.

Theoretical and Empirical Results

Convergence Rates and Dimensionality

The research identifies a "phase transition" in convergence rates based on the smoothness of the densities (denoted by $\beta$) and the dimension ($d$). If $\beta > d/4$, the estimator achieves the parametric rate of $n^{-1}$. This result is significant as it suggests that for smooth data, the estimator is as efficient as if the underlying parameters were known.

Relative error of the $L_2^2$ divergence estimator across different dimensions as a function of sample size.

As shown in the figure above, the relative error decreases consistently as the number of samples ($n$) increases. While higher dimensions ($d=5$) exhibit higher initial error, the downward trend confirms the estimator's consistency across varying complexities.

Statistical Inference: Confidence Intervals

Beyond point estimation, the authors prove that the estimator's error distribution is asymptotically Gaussian. This allows for the construction of valid confidence intervals. Empirical tests using Gaussian distributions—where the true divergence is analytically known—validate this theory.

Empirical success probability of 90% confidence intervals. As sample size increases, the probability approaches the nominal 0.9 level, though higher dimensions require more data to reach stability.

In low-dimensional cases ($d=1$), the success probability (the frequency with which the interval contains the true value) converges rapidly to the target 0.9. In higher dimensions, such as $d=5$, a larger sample size is required before the asymptotic behavior stabilizes, highlighting a practical limitation in the "small data" regime for high-dimensional problems.

Conclusion

This work provides the first comprehensive theoretical framework for $L_2^2$ divergence estimation. By proving minimax optimality and establishing asymptotic normality, the authors transition $L_2^2$ estimation from a heuristic tool to a rigorous method for statistical inference. Future work remains in developing data-driven bandwidth selection methods to further optimize performance in high-dimensional applications.

Summary updated

Abstract

We give a comprehensive theoretical characterization of a nonparametric estimator for the L_2^2 divergence between two continuous distributions. We first bound the rate of convergence of our estima...
BibTeX
@inproceedings{krishnamurthy2015estimating,
  author = {Akshay Krishnamurthy and Kirthevasan Kandasamy and Barnabás Póczos and Larry A. Wasserman},
  title = {{On Estimating L22 Divergence.}},
  booktitle = {AISTATS},
  year = {2015},
  url = {https://openreview.net/forum?id=7u6tvm3DSM6},
}
Figure