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).
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