# Nystr"om M-Hilbert-Schmidt Independence Criterion

arXiv: https://arxiv.org/abs/2302.09930 · HTML: https://mlsanity.com/paper/2302.09930/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 59 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 17 of 17)

- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [Kernels for sequentially ordered data](https://mlsanity.com/paper/1601.08169/) (2016)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [Fast Two-Sample Testing with Analytic Representations of Probability Measures](https://mlsanity.com/paper/1506.04725/) (2015)
- [Characteristic and Universal Tensor Product Kernels](https://mlsanity.com/paper/1708.08157/) (2017)
- [Kernel-based Tests for Joint Independence](https://mlsanity.com/paper/1603.00285/) (2016)
- [Large-Scale Kernel Methods for Independence Testing](https://mlsanity.com/paper/1606.07892/) (2016)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Kernel Partial Correlation Coefficient -- a Measure of Conditional Dependence](https://mlsanity.com/paper/2012.14804/) (2020)
- [Spectral Regularized Kernel Two-Sample Tests](https://mlsanity.com/paper/2212.09201/) (2022)
- [An Adaptive Test of Independence with Analytic Kernel Embeddings](https://mlsanity.com/paper/1610.04782/) (2016)
- [A Kernel Test for Three-Variable Interactions](https://mlsanity.com/paper/1306.2281/) (2013)
- [Distance Metrics for Measuring Joint Dependence with Application to Causal Inference](https://mlsanity.com/paper/1711.09179/) (2017)
- [On Distance and Kernel Measures of Conditional Independence](https://mlsanity.com/paper/1912.01103/) (2019)
- [Wind power predictions from nowcasts to 4-hour forecasts: a learning approach with variable selection](https://mlsanity.com/paper/2204.09362/) (2022)

## Built on by (most cited first, 5 of 5)

- [On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery](https://mlsanity.com/paper/2310.13553/) (2023)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels](https://mlsanity.com/paper/2403.07735/) (2024)
- [Informed Asymmetric Actor-Critic: Leveraging Privileged Signals Beyond Full-State Access](https://mlsanity.com/paper/2509.26000/) (2025)
- [Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD](https://mlsanity.com/paper/2607.24235/) (2026)

## Abstract (arXiv)

Kernel techniques are among the most popular and powerful approaches of data science. Among the 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 facilitating their statistical analysis, and (iii) their ability to represent probability distributions without loss of information. These properties give rise to the immense success of Hilbert-Schmidt independence criterion (HSIC) which is able to capture joint independence of random variables under mild conditions, and permits closed-form estimators with quadratic computational complexity (w.r.t. the sample size). In order to alleviate the quadratic computational bottleneck in large-scale applications, multiple HSIC approximations have been proposed, however these estimators are restricted to M=2 random variables, do not extend naturally to the M≥ 2 case, and lack theoretical guarantees. In this work, we propose an alternative Nystr"om-based HSIC estimator which handles the M≥ 2 case, prove its consistency, and demonstrate its applicability in multiple contexts, including synthetic examples, dependency testing of media annotations, and causal discovery.