The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels
Florian Kalinke Zoltan Szabo
Kernel techniques are among the most influential approaches in data science
and statistics. Under mild conditions, the reproducing kernel Hilbert space
associated to a kernel is capable of encoding the independence of $M\ge 2$
random variables. Probably the most widespread independence measure relying on
kernels is the so-called Hilbert-Schmidt independence criterion (HSIC; also
referred to as distance covariance in the statistics literature). Despite
various existing HSIC estimators designed since its introduction close to two
decades ago, the fundamental question of the rate at which HSIC can be
estimated is still open. In this work, we prove that the minimax optimal rate
of HSIC estimation on $\mathbb R^d$ for Borel measures containing the Gaussians
with continuous bounded translation-invariant characteristic kernels is
$\mathcal O\!\left(n^{-1/2}\right)$. Specifically, our result implies the
optimality in the minimax sense of many of the most-frequently used estimators
(including the U-statistic, the V-statistic, and the Nystr\"om-based one) on
$\mathbb R^d$.