The Minimax Lower Bound of Kernel Stein Discrepancy Estimation

AI summary

Overview

• Research area: Statistical machine learning / learning theory — specifically minimax estimation theory for kernel Stein discrepancies (KSDs), a family of goodness-of-fit measures built from Stein operators and reproducing kernel Hilbert spaces (RKHSs).
• Technical level: Advanced. The paper is a pure theory contribution (stat.ML), requiring familiarity with RKHSs, Stein operators, integral probability metrics, and minimax lower-bound techniques such as Le Cam's two-point method.
• Scope in one sentence: The paper proves that the minimax lower bound for estimating kernel Stein discrepancy is n^{-1/2}, thereby showing that existing KSD estimators — the V-statistic and the Nyström-based estimators — are rate-optimal.

What This Paper Is About

KSDs are widely used to measure how well a sampling distribution matches a known target distribution, and every KSD estimator whose convergence rate was previously known achieves √n-convergence. The open question was whether this rate is fundamental or whether some cleverer estimator could do better. This paper answers that question by proving matching lower bounds: no estimator, in the minimax sense, can beat n^{-1/2}, so the known √n rates are optimal.

Key Contributions

1. The authors establish the minimax lower bound n^{-1/2} for KSD estimation on ℝ^d using the Langevin-Stein operator, for continuous, bounded, translation-invariant, characteristic base kernels, with explicit constants given for the Gaussian base kernel.
2. For the Gaussian base kernel, the explicit constant indicates that the difficulty of KSD estimation may increase exponentially with the dimensionality d.
3. Using a different proof strategy based on local perturbations, the authors obtain the same n^{-1/2} lower bound for KSD estimation on general domains (general topological spaces) under integrability conditions that relax the usual kernel-boundedness assumptions.
4. Together, these results settle the optimality of existing KSD estimators, whose rates were previously only known as upper bounds.

Main Findings

• Minimax lower bound on ℝ^d: For Langevin-Stein KSD with continuous, bounded, translation-invariant characteristic base kernels, the minimax lower bound of KSD estimation is n^{-1/2}. An explicit constant is provided for the Gaussian base kernel.
• Dimensional dependence: The explicit Gaussian-kernel constant suggests that the difficulty of KSD estimation may increase exponentially with the dimension d — the paper describes this as a possibility indicated by the constant, not a separate theorem.
• Minimax lower bound on general domains: Via a local-perturbation proof strategy, the same n^{-1/2} bound holds for KSD on general domains, under integrability conditions that relax the standard boundedness assumptions.
• Existing estimators are rate-optimal: The V-statistic KSD estimator (Chwialkowski et al., 2016), with runtime complexity O(n^2), achieves |KSD_V − KSD| = O_{P^n}(n^{-1/2}) under a sub-Gaussian assumption on the Stein feature map (Kalinke et al., 2025). The Nyström-KSD estimator (Kalinke et al., 2025), with runtime complexity O(mn + m^3), achieves |KSD_N − KSD| = O_{P^n ⊗ Λ^m}(n^{-1/2}) given sub-Gaussianity of the Stein feature map, appropriate spectral decay of its centered covariance operator, and a lower bound on m. The new lower bounds show neither can be improved in rate.
• Why prior lower bounds did not apply: Existing minimax lower bounds for MMD (Tolstikhin et al., 2016), the mean embedding (Tolstikhin et al., 2017), covariance operators (Zhou et al., 2019), and HSIC (Kalinke and Szabó, 2024) all assume the kernel to be bounded and rely on Le Cam's two-point method. Boundedness practically never holds in the KSD setting. The paper closes this gap.
• No empirical results: The paper reports no experiments, datasets, or benchmarks; it is purely theoretical.

Methodology in Plain English

The paper first sets up two versions of KSD: the Langevin-Stein KSD on ℝ^d, where the Stein operator is built from the gradient of the log-density of the target p_0, and an abstract KSD on a general topological space defined through a Hilbert-space-valued map Ψ_{P_0} whose mean under the target vanishes. Both formulations express KSD as the RKHS norm of an expectation, which is the object to be estimated from n i.i.d. samples. The authors then define the minimax risk as the worst-case expected absolute difference between an estimator and the true KSD value, as in Equation (37) of the paper. To prove that the rate cannot be better than n^{-1/2}, the first result constructs a pair of hard distributions and uses Le Cam's two-point method — but adapted, because the usual bounded-kernel argument fails here. The second result takes a different route entirely: instead of two-point Le Cam arguments, it applies local perturbations of the target distribution, which allows the proof to work on general domains and under weaker integrability assumptions than boundedness of the kernel. Detailed proofs are deferred to the appendix.

Why This Matters

• Impact on research: It closes a gap in the theory of goodness-of-fit testing and kernel methods by supplying the missing minimax lower bounds for KSD, analogous to earlier lower bounds established for MMD, mean embeddings, covariance operators, and HSIC. It also introduces proof techniques — particularly the local-perturbation strategy — that may be reusable for other kernel-based quantities whose kernels are unbounded.
• Real-world applications (drawn from the application areas the paper cites for KSD):
  • Model validation and model comparison, where KSD checks whether a fitted model matches data.
  • Learning variational models, including variational inference procedures built on KSD objectives.
  • Statistical testing of goodness-of-fit, where KSD-based tests decide whether a sample matches a target.
  • Distribution compression, where KSD is used as a quality criterion for summarizing a large sample.
  • Additional cited domains include model explainability, discrete spaces, Riemannian manifolds, Hilbert spaces, point processes, and graph data.
• Industry relevance: Because KSD is agnostic to the normalization constant of the sampling distribution — a constant that is often intractable in applications — it is attractive for large-scale probabilistic modeling. Knowing that n^{-1/2} is the best achievable rate tells practitioners that no further algorithmic cleverness will asymptotically beat the existing V-statistic and Nyström estimators, and that the Nyström estimator's cheaper O(mn + m^3) runtime is therefore the sensible choice for large samples.

Future Directions

• The paper's explicit Gaussian-kernel constant indicates a possible exponential growth of difficulty with dimension d; establishing whether this is tight, and how it interacts with the optimal rate, is a natural next question.
• The general-domain result rests on integrability conditions that relax boundedness; identifying precisely which KSD settings (Riemannian manifolds, Hilbert spaces, discrete spaces, point processes, graph data) satisfy those conditions remains to be worked out.
• KSDs defined via the Pettis integral are explicitly excluded from this paper (Remark 1), leaving the minimax question open for that formulation.
• Extending the local-perturbation proof strategy to other unbounded-kernel minimax problems — MMD with unbounded kernels, mean embeddings, covariance operators, HSIC — is an obvious follow-up, since the existing bounds for those quantities assume bounded kernels.
• The paper notes that the same n^{-1/2} rate (up to logarithmic factors) appears in distribution compression with KSD (Li et al., 2024); whether the lower bound transfers exactly to that setting is not reported.

Target Audience

Researchers and graduate students in statistical machine learning and learning theory who work on kernel methods, Stein operators, goodness-of-fit testing, or minimax estimation. It is also relevant to theoretically inclined practitioners who rely on KSDs for model validation, variational inference, or distribution compression and want to know whether the √n rate of current estimators is a fundamental limit or an artifact of existing algorithms.

Authors’ abstract

Kernel Stein discrepancies (KSDs) have emerged as a powerful tool for quantifying goodness-of-fit over the last decade, featuring numerous successful applications. To the best of our knowledge, all existing KSD estimators with known rate achieve $\sqrt n$-convergence. In this work, we present two complementary results (with different proof strategies), establishing that the minimax lower bound of KSD estimation is $n^{-1/2}$ and settling the optimality of these estimators. Our first result focuses on KSD estimation on $\mathbb R^d$ with the Langevin-Stein operator; our explicit constant for the Gaussian kernel indicates that the difficulty of KSD estimation may increase exponentially with the dimensionality $d$. Our second result settles the minimax lower bound for KSD estimation on general domains.