Asymptotic Normality of the Median Heuristic

Garreau Damien

Published 2017-07-23Version 1

The median heuristic is a popular tool to set the bandwidth of radial basis function kernels. While its empirical performances make it a safe choice under most circumstances, there is little theoretical understanding of why this is the case. For large sample size, we show in this article that the median heuristic behaves approximately as the median of a distribution that we describe completely in the setting of kernel two-sample test and kernel change-point detection. More precisely, we show that the median heuristic is asymptotically normal around this value. We illustrate these findings when the underlying distributions are multivariate Gaussian distributions.