The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels

• URL: http://arxiv.org/abs/2403.07735v2
• Date: Mon, 14 Oct 2024 11:18:27 GMT
• Title: The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels
• Authors: Florian Kalinke, Zoltan Szabo,
• Abstract summary: 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)$.
• Score: 0.0
• License:
• Abstract: Kernel techniques are among the most influential approaches in data science and statistics. Under mild conditions, the reproducing kernel Hilbert space associated to a kernel is capable of encoding the independence of $M\ge 2$ random variables. Probably the most widespread independence measure relying on kernels is the so-called Hilbert-Schmidt independence criterion (HSIC; also referred to as distance covariance in the statistics literature). Despite various existing HSIC estimators designed since its introduction close to two decades ago, the fundamental question of the rate at which HSIC can be estimated is still open. In this work, we prove that the minimax optimal rate of HSIC estimation on $\mathbb R^d$ for Borel measures containing the Gaussians with continuous bounded translation-invariant characteristic kernels is $\mathcal O\!\left(n^{-1/2}\right)$. Specifically, our result implies the optimality in the minimax sense of many of the most-frequently used estimators (including the U-statistic, the V-statistic, and the Nystr\"om-based one) on $\mathbb R^d$.

Related papers

• 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. We show its $sqrtn$-consistency with a classical sub-Gaussian assumption, and demonstrate its applicability for goodness-of-fit testing on a suite of benchmarks.
  arXiv  Detail & Related papers  (2024-06-12T16:50:12Z)
• 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)
• Nystr\"om $M$-Hilbert-Schmidt Independence Criterion [0.0]
  Key features that make kernels ubiquitous are (i) the number of domains they have been designed for, (ii) the Hilbert structure of the function class associated to kernels, and (iii) their ability to represent probability distributions without loss of information. We propose an alternative Nystr"om-based HSIC estimator which handles the $Mge 2$ case, prove its consistency, and demonstrate its applicability.
  arXiv  Detail & Related papers  (2023-02-20T11:51:58Z)
• Kernelized Cumulants: Beyond Kernel Mean Embeddings [11.448622437140022]
  We extend cumulants to reproducing kernel Hilbert spaces (RKHS) using tools from tensor algebras. We argue that going beyond degree one has several advantages and can be achieved with the same computational complexity and minimal overhead.
  arXiv  Detail & Related papers  (2023-01-29T15:31:06Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• A Permutation-Free Kernel Independence Test [36.50719125230106]
  In nonparametric independence testing, we observe i.i.d. data $(X_i,Y_i)_i=1n$, where $X in mathcalX, Y in mathcalY$ lie in any general spaces. Modern test statistics such as the kernel Hilbert-Schmidt Independence Criterion (HSIC) and Distance Covariance (dCov) have intractable null distributions due to the degeneracy of the underlying U-statistics. This paper provides a simple but nontrivial modification of HSIC
  arXiv  Detail & Related papers  (2022-12-18T15:28:16Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  We propose a new, simplified high probability analysis of AdaGrad for smooth, non- probability problems. We present our analysis in a modular way and obtain a complementary $mathcal O (1 / TT)$ convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness.
  arXiv  Detail & Related papers  (2022-04-06T13:50:33Z)
• 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)
• 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)
• Taming Nonconvexity in Kernel Feature Selection---Favorable Properties of the Laplace Kernel [77.73399781313893]
  A challenge is to establish the objective function of kernel-based feature selection. The gradient-based algorithms available for non-global optimization are only able to guarantee convergence to local minima.
  arXiv  Detail & Related papers  (2021-06-17T11:05:48Z)

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.