Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes the minimax lower bounds for estimating kernel discrepancies, specifically maximum mean discrepancy (MMD), Hilbert-Schmidt independence criterion (HSIC), and kernel Stein discrepancy (KSD), demonstrating that the optimal convergence rate remains $n^{-1/2}$ even in general topological spaces with unbounded kernels. The findings extend the understanding of kernel discrepancy estimation beyond traditional finite-dimensional settings, providing a comprehensive framework for assessing the performance of these estimators. By proving that these rates also apply to mean embedding and centered cross-covariance operator estimation, the authors resolve longstanding questions regarding optimality in this domain.
Minimax lower bounds for kernel discrepancy estimators hold firm at $n^{-1/2}$ even in unbounded spaces, reshaping our understanding of their optimality.
Over the past 20 years, kernel discrepancies have been leveraged as a highly powerful tool for quantifying the disagreement of distributions, with numerous successful applications in two-sample, goodness-of-fit, and independence testing, among others. Their fastest estimators are known to converge at a parametric rate---$n^{-1/2}$---under mild conditions. While this rate is known to be minimax optimal on $\mathbb R^d$ under strict assumptions with bounded kernels, little is known about its optimality beyond the finite-dimensional Euclidean setting with unbounded kernels. In this work, we prove that the minimax lower bound of estimation of the most popular kernel discrepancies (maximum mean discrepancy, Hilbert-Schmidt independence criterion and kernel Stein discrepancy; MMD, HSIC, KSD) is $n^{-1/2}$ on general topological spaces, and under mild assumptions on the kernel; the same rates are shown (as corollaries) to hold for the estimation of the mean embedding and the centered cross-covariance operator. Our results settle the question of optimal estimation of these kernel discrepancies.