Research map / Learning theory and algorithms / Kernels and regression theory
The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves a minimax lower bound of order n^{-1/2} for estimating HSIC with continuous bounded translation-invariant characteristic kernels on R^d via Le Cam's method, showing existing U-, V- and Nyström HSIC estimators are minimax optimal.
Problem
The minimax optimal rate of estimating the Hilbert-Schmidt independence criterion (HSIC) on R^d was open; known estimators achieve O_P(n^{-1/2}) but it was unknown whether faster rates are possible.
Approach
Construct Gaussian adversarial pairs differing only in one cross-correlation rho_n = n^{-1/2}, which keeps KL bounded while HSIC differs by order n^{-1/2}; for translation-invariant kernels use the spectral (characteristic function) representation of MMD to lower bound the HSIC gap.
Key results
- Minimax lower bound of order n^{-1/2} for HSIC estimation on R^d with Gaussian kernels, with explicit constant c = gamma/(2(2gamma+1)^{d/4+1}), probability at least (1-sqrt(5/8))/2.
- Extends the lower bound to continuous bounded translation-invariant characteristic kernels (Theorem part ii), so U-, V- and Nyström HSIC estimators are minimax optimal.
- Corollary: the same n^{-1/2} lower bound holds for estimating the centered cross-covariance operator in RKHS norm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Establish a minimax lower bound for HSIC under continuous bounded translation-invariant characteristic kernels | HSIC estimation on R^d · HSIC on R^d | estimation error rate: O(n^{-1/2}) | Helped |
| Use a U-statistic estimator | HSIC estimation · HSIC on R^d with continuous bounded translation-invariant characteristic kernels | estimation error rate: O_P(n^{-1/2}) | Helped |
| Use a V-statistic estimator | HSIC estimation · HSIC on R^d with continuous bounded translation-invariant characteristic kernels | estimation error rate: O_P(n^{-1/2}) | Helped |
| Use Nyström approximation under appropriate eigenspectrum decay | HSIC estimation · HSIC on R^d with continuous bounded translation-invariant characteristic kernels | estimation error rate: O_P(n^{-1/2}) | Helped |
| Establish the lower bound for cross-covariance operator estimation | Cross-covariance operator estimation · Cross-covariance operator | estimation error rate: c/√n | Helped |
Surprising findings
- Lower bounds for MMD estimation from prior work do not transfer to HSIC because their product-structured adversarial pairs yield zero HSIC gap.
Limitations
- Result is a lower bound only for the stated Gaussian/translation-invariant setting on R^d; not extended to other domains or kernel classes in the text.
- Explicit constant only given for Gaussian kernels; for general translation-invariant kernels the constant c is non-explicit.
Experimental setup
Baselines: U-statistic HSIC estimator V-statistic HSIC estimator Nyström HSIC estimator
Builds on: Le Cam's method Hilbert-Schmidt independence criterion maximum mean discrepancy Bochner's theorem
Closest papers by meaning
- Statistical Insights into HSIC in High Dimensions (NeurIPS 2023 · similarity 0.88)
- Statistical and Geometrical properties of the Kernel Kullback-Leibler divergence (NeurIPS 2024 · similarity 0.85)
- Regularized least squares learning with heavy-tailed noise is minimax optimal (NeurIPS 2025 · similarity 0.84)
- Flat Minima in Linear Estimation and an Extended Gauss Markov Theorem (ICLR 2024 · similarity 0.83)
- On the Consistency of Kernel Methods with Dependent Observations (ICML 2024 · similarity 0.83)
- K$^2$IE: Kernel Method-based Kernel Intensity Estimators for Inhomogeneous Poisson Processes (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.