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

• URL: http://arxiv.org/abs/2607.24235v1
• Date: Mon, 27 Jul 2026 10:13:26 GMT
• Title: Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD
• Abstract summary: We prove that the minimax lower bound of estimation of the most popular kernel discrepancies is $n-1/2$ on general topological spaces.<n>Our results settle the question of optimal estimation of these kernel discrepancies.
• Score: 4.345882429229813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Minimax Estimation of Kernel Stein Discrepancy: Trace versus Hilbert-Schmidt Scales [0.8883733362171032]
  Stein Discrepancy (KSD) compares a sample to a fixed target distribution known only through its score.<n>We study the estimation of $operatornameKSD(P_0,P)$ from $n$ independent observations.
  arXiv  Detail & Related papers  (2026-07-03T14:22:58Z)
• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element.<n>Our main result bounds the regret by $widetildeObig(sqrtT, d_*(),log|X|big)$, where $d_*()$ is a widely-adopted notion of effective dimension.
  arXiv  Detail & Related papers  (2026-05-26T06:10:24Z)
• The Minimax Lower Bound of Kernel Stein Discrepancy Estimation [3.7080682446788575]
  We show that the minimax lower bound of KSD estimation is $n-1/2$ and settling the optimality of these estimators.<n>Our first result focuses on KSD estimation on $mathbb Rd$ with the Langevin-Stein operator.<n>Our second result settles the minimax lower bound for KSD estimation on general domains.
  arXiv  Detail & Related papers  (2025-10-16T18:16:05Z)
• Kernel Quantile Embeddings and Associated Probability Metrics [12.484632369259659]
  We introduce the notion of kernel quantile embeddings (KQEs)<n>We use KQEs to construct a family of distances that: (i) are probability metrics under weaker kernel conditions than MMD; (ii) recover a kernelised form of the sliced Wasserstein distance; and (iii) can be efficiently estimated with near-linear cost.
  arXiv  Detail & Related papers  (2025-05-26T18:27:17Z)
• The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels [0.0]
  We prove that the minimax optimal rate of HSIC estimation on $mathbb Rd$ for Borel measures containing the Gaussians with continuous bounded translation-invariant characteristic kernels is $mathcal O!left(n-1/2right)$.
  arXiv  Detail & Related papers  (2024-03-12T15:13:21Z)
• Targeted Separation and Convergence with Kernel Discrepancies [61.973643031360254]
  kernel-based discrepancy measures are required to (i) separate a target P from other probability measures or (ii) control weak convergence to P.<n>In this article we derive new sufficient and necessary conditions to ensure (i) and (ii)<n>For MMDs on separable metric spaces, we characterize those kernels that separate Bochner embeddable measures and introduce simple conditions for separating all measures with unbounded kernels.
  arXiv  Detail & Related papers  (2022-09-26T16:41:16Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  We propose an efficient approximation procedure based on the Nystr"om method. It yields sufficient conditions on the subsample size to obtain the standard $n-1/2$ rate. We discuss applications of this result for the approximation of the maximum mean discrepancy and quadrature rules.
  arXiv  Detail & Related papers  (2022-01-31T08:26:06Z)
• Kernel Two-Sample Tests in High Dimension: Interplay Between Moment Discrepancy and Dimension-and-Sample Orders [1.9303929635966661]
  We study the behavior of kernel two-sample tests when the dimension and sample sizes both diverge to infinity. We establish the central limit theorem (CLT) under both the null hypothesis and the local and fixed alternatives. The new non-null CLT results allow us to perform exact power analysis, which reveals a delicate interplay between the moment discrepancy that can be detected.
  arXiv  Detail & Related papers  (2021-12-31T23:12:44Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.