TL;DR
This paper tackles the problem of accurately estimating the variance of the Maximum Mean Discrepancy (MMD) statistic, a crucial tool for comparing probability distributions. The authors present a novel, truly unbiased estimator for the MMD variance, which is computationally efficient and corrects biases found in previous methods. This advancement is vital for reliable statistical inference and hypothesis testing in various machine learning applications.
What Problem Does This Paper Address?
The Maximum Mean Discrepancy (MMD) is a powerful kernel-based distance metric used to quantify the difference between two probability distributions. It's widely applied in areas like two-sample testing, domain adaptation, and generative model evaluation. A key challenge in using MMD for statistical inference (e.g., hypothesis testing) is accurately estimating its variance. Previous attempts to derive unbiased variance estimators, notably by Bounliphone et al. (2016), introduced biases by dropping lower-order terms, which can be problematic, especially for smaller sample sizes. This paper aims to provide a theoretically sound and practically useful unbiased estimator for the variance of the MMD statistic, and also for the variance of the difference between two MMD statistics.
Methods
The core of this paper lies in the rigorous application of U-statistic theory. The authors extend and correct previous work by deriving expressions for the variance of the MMD estimator. They meticulously analyze the first-order ($\xi_1$) and second-order ($\xi_2$) terms that constitute the variance.
Key methodological contributions include:
- Derivation of Variance Expressions: The paper provides detailed derivations of the population-level variance expressions for both the squared MMD estimator and the difference between two correlated squared MMD estimators. This is achieved by carefully expanding the U-statistic structure and utilizing properties of kernel functions and mean embeddings.
- Unbiased Estimator Construction: Building upon the derived variance expressions, the authors construct unbiased estimators for these population quantities. This involves carefully estimating terms that represent expectations of inner products in Reproducing Kernel Hilbert Spaces (RKHS) and variances of kernel functions.
- Addressing Bias in Previous Work: The paper explicitly points out and corrects biases present in prior estimators, particularly those that simplify by dropping terms. They demonstrate that these simplifications, while seemingly reducing complexity, lead to biased results.
- Computational Efficiency: A significant aspect is that the proposed unbiased estimators do not incur additional computational cost compared to the biased estimators, making them practical for real-world applications.
Datasets
Not discussed in the paper. The paper focuses on theoretical derivations and does not present empirical evaluations on specific datasets.
Key Insights and Ideas
- The Importance of Lower-Order Terms: A crucial insight is that dropping lower-order terms in variance estimation, while tempting for simplification, introduces bias. The paper emphasizes that these terms are essential for achieving true unbiasedness.
- U-Statistics as the Foundation: The paper leverages the well-established theory of U-statistics to systematically derive and analyze the variance of the MMD estimator. This theoretical framework provides a robust basis for their findings.
- Unbiasedness for Difference of MMDs: The work extends beyond estimating the variance of a single MMD to also providing an unbiased estimator for the variance of the difference between two MMDs. This is particularly useful for comparing different MMD-based models or tests.
- Computational Cost is Not a Barrier: The paper highlights that achieving unbiasedness doesn't necessitate a significant increase in computational complexity, making the proposed estimators practical for use.
Key Results
The paper's primary results are the explicit formulas for unbiased estimators of:
- The variance of the squared MMD estimator: This is presented in Equation (3) and further simplified in Equation (5).
- The variance of the difference between two correlated squared MMD estimators: This is presented in Equation (6).
These estimators are derived to be unbiased for the true population variance, correcting the biases found in earlier methods. The paper also provides detailed expressions for the intermediate terms (like $\xi_1$ and $\xi_2$) that constitute these variances, which are themselves of theoretical interest.
Limitations and Future Work
- Computational Complexity for Large Datasets: While the paper states the estimators do not add computational cost relative to evaluating the MMD itself, the derived estimators still involve sums over pairs of samples, leading to $O(n^2)$ complexity for estimating the variance. This can be prohibitive for very large datasets.
- Biased Estimator Performance: The paper briefly mentions Liu et al. (2020)'s simpler biased estimator, noting it can sometimes perform better in practice. The theoretical justification for this empirical observation is not fully explored within this paper.
- Practical Implementation Details: While the theoretical derivations are thorough, the paper could benefit from more discussion on practical implementation challenges and potential optimizations for large-scale scenarios.
Future work could involve developing more computationally efficient estimators for very large sample sizes, perhaps by exploring approximations or randomized techniques. Further investigation into the performance trade-offs between the proposed unbiased estimators and simpler biased ones in various practical settings would also be valuable.
Summary updated