The Minimax Lower Bound of Kernel Stein Discrepancy Estimation

• URL: http://arxiv.org/abs/2510.15058v1
• Date: Thu, 16 Oct 2025 18:16:05 GMT
• Title: The Minimax Lower Bound of Kernel Stein Discrepancy Estimation
• Authors: Jose Cribeiro-Ramallo, Agnideep Aich, Florian Kalinke, Ashit Baran Aich, Zoltán Szabó,
• Abstract summary: 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.
• Score: 3.7080682446788575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Copula-Stein Discrepancy: A Generator-Based Stein Operator for Archimedean Dependence [0.0]
  We introduce the Copula-Stein Discrepancy, a class of discrepancies tailored to the geometry of statistical dependence.<n>For the broad class of Archimedean copulas, this approach yields a closed-form Stein kernel derived from the scalar generator function.<n>The framework is extended to general non-Archimedean copulas, including elliptical and vine copulas.
  arXiv  Detail & Related papers  (2025-10-28T04:33:57Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)
• Nyström Kernel Stein Discrepancy [4.551160285910023]
  We propose a Nystr"om-based KSD acceleration -- with runtime $mathcal Oleft(mn+m3right)$ for $n$ samples and $mll n$ Nystr"om points.<n>We also show the $sqrt n$-consistency of the quadratic-time KSD estimator.
  arXiv  Detail & Related papers  (2024-06-12T16:50:12Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Kernel $ε$-Greedy for Multi-Armed Bandits with Covariates [5.115048067424624]
  We estimate the unknown mean reward functions using an online weighted kernel ridge regression estimator.<n>We show that for any choice of kernel and the corresponding RKHS, we achieve a sub-linear regret rate depending on the intrinsic dimensionality of the RKHS.
  arXiv  Detail & Related papers  (2023-06-29T22:48:34Z)
• Controlling Moments with Kernel Stein Discrepancies [74.82363458321939]
  Kernel Stein discrepancies (KSDs) measure the quality of a distributional approximation.<n>We first show that standard KSDs used for weak convergence control fail to control moment convergence.<n>We then provide sufficient conditions under which alternative diffusion KSDs control both moment and weak convergence.
  arXiv  Detail & Related papers  (2022-11-10T08:24:52Z)
• Kernel Stein Discrepancy Descent [16.47373844775953]
  Kernel Stein Discrepancy (KSD) has received much interest recently. We investigate the properties of its Wasserstein gradient flow to approximate a target probability distribution $pi$ on $mathbbRd$. This leads to a straightforwardly implementable, deterministic score-based method to sample from $pi$, named KSD Descent.
  arXiv  Detail & Related papers  (2021-05-20T19:05:23Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)

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.