Large sample analysis of the median heuristic

Garreau Damien, Wittawat Jitkrittum, Motonobu KanagawaarXiv 2017 · DOI · arXiv

Abstract

In kernel methods, the median heuristic is a standard approach for selecting the bandwidth of Radial Basis Function (RBF) kernels. Despite its widespread empirical use, theoretical justification for its performance has remained limited. This paper provides a rigorous large-sample analysis of the median heuristic, specifically within the framework of kernel two-sample testing. We establish the asymptotic normality of the bandwidth estimator and evaluate its efficiency using the Approximate Bahadur Slope (ABS). Our findings reveal that while the median heuristic is remarkably effective for detecting mean shifts, it can be suboptimal for detecting changes in variance. We also identify a "two bumps" phenomenon in the distribution of pairwise distances that explains the heuristic's behavior in well-separated distributions.

Introduction

The performance of kernel-based algorithms, such as Support Vector Machines (SVMs) and Kernel Principal Component Analysis (KPCA), is highly sensitive to the choice of kernel bandwidth. For the Gaussian RBF kernel, $k(x, y) = \exp(-\|x-y\|^2 / \gamma)$, the bandwidth $\gamma$ determines the scale at which data points are compared. A common practice is the median heuristic: setting the bandwidth to the median of all pairwise distances between data points. While this rule of thumb is robust in practice, its theoretical properties as the sample size $n \to \infty$ have not been fully explored. This study focuses on the kernel two-sample test, where the goal is to determine if two samples $X$ and $Y$ originate from the same distribution.

Theoretical Framework

We treat the median heuristic as a statistical estimator $H_n$ and analyze its convergence. The empirical distribution of pairwise distances is modeled using $U$-statistics. For the two-sample case involving distributions $P$ and $Q$, we derive a Central Limit Theorem (CLT) for non-identically distributed triangular arrays of $U$-statistics.

We prove that $\sqrt{n}(H_n - m) \xrightarrow{\mathcal{L}} \mathcal{N}(0, \frac{\sigma^2}{F'(m)^2})$, where $m$ is the theoretical median of the mixture distribution. This result ensures that the bandwidth selected by the heuristic stabilizes as the number of samples increases. To assess the quality of this selection, we employ the Approximate Bahadur Slope (ABS), which quantifies the rate at which the test's $p$-value decreases with $n$.

Empirical Analysis and the "Two Bumps" Phenomenon

We investigate the heuristic's behavior using synthetic Gaussian datasets representing two primary scenarios: mean shifts (differences in location) and variance shifts (differences in scale).

A key observation is the "two bumps" phenomenon in the distribution of pairwise distances. When two distributions are sufficiently separated, the histogram of squared distances $\|X_{n,i} - X_{n,j}\|^2$ exhibits two distinct modes. The first mode corresponds to "intra-distances" (distances between points within the same distribution), while the second corresponds to "inter-distances" (distances between points from different distributions).

The "two bumps" phenomenon: The left plot shows the separation of intra- and inter-distances in a well-separated case, while the right plot shows a single mode where distributions overlap.

This separation is crucial because the median heuristic typically selects a value within the first bump (the intra-distances). This makes the choice "safe" for representing the internal scale of the data but potentially conservative for detecting the gap between distributions.

Key Results

Our analysis reveals a "remarkable coincidence" in the mean shift scenario: the bandwidth chosen by the median heuristic is nearly identical to the bandwidth that maximizes the power of the quadratic-time Maximum Mean Discrepancy (MMD) test. In this case, the heuristic is near-optimal.

However, in the variance shift scenario, the median heuristic performs less effectively. It tends to select a bandwidth significantly larger than the one that would maximize test power. This discrepancy is further confirmed by the ABS, which shows a significant performance gap between the median heuristic and power-optimized bandwidths for scale-based differences. The median's conservative nature, driven by its focus on intra-sample distances, limits its sensitivity to variance-based changes compared to specialized power-maximization strategies.

Conclusion

This work provides the first theoretical foundation for the median heuristic in kernel two-sample testing. While the heuristic is a reliable and often near-optimal choice for detecting mean shifts, practitioners should be cautious when applying it to problems where differences are primarily in variance. Future work will extend this analysis to supervised learning tasks and explore the heuristic's performance when sample sizes are highly imbalanced.

Summary updated

Abstract

In kernel methods, the median heuristic has been widely used as a way of setting the bandwidth of RBF kernels. While its empirical performances make it a safe choice under many circumstances, there is little theoretical understanding of why this is the case. Our aim in this paper is to advance our understanding of the median heuristic by focusing on the setting of kernel two-sample test. We collect new findings that may be of interest for both theoreticians and practitioners. In theory, we provide a convergence analysis that shows the asymptotic normality of the bandwidth chosen by the median heuristic in the setting of kernel two-sample test. Systematic empirical investigations are also conducted in simple settings, comparing the performances based on the bandwidths chosen by the median heuristic and those by the maximization of test power.
BibTeX
@misc{damien2017large,
  author = {Garreau Damien and Wittawat Jitkrittum and Motonobu Kanagawa},
  title = {{Large sample analysis of the median heuristic}},
  year = {2017},
  eprint = {1707.07269},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.07269},
}
Figure