Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD

Jul 2026 · Papers

arXiv (preprint)

We studied the minimax lower bound of the most popular kernel discrepancies: MMD, HSIC and KSD. While results for MMD and HSIC already exists, they are limited to $\mathbb R^d$, while interest for these discrepancies extends far-beyond the Euclidean case. We found that the fastest estimation one can give for the MMD and HSIC is $\mathcal O(n^{1/2}+m^{1/2})$ and $\mathcal O(n^{1/2})$, respectively---these results extend our previous work where we obtained minimax lowerbounds for the KSD.

Cite

@TECHREPORT{cribeiro26kernel,
  AUTHOR =       {Jose Cribeiro-Ramallo and Florian Kalinke and Zolt{\'a}n Szab{\'o}},
  TITLE =        {Minimax Lower Bounds of Kernel Discrepancy Estimation: {MMD}, {HSIC}, {KSD}},
  YEAR =         {2026},
  note =         {(\url{https://arxiv.org/abs/2607.24235})},
}