Large-scale kernel methods for independence testing

By Qinyi Zhang, Sarah Filippi, Arthur Gretton, Dino Sejdinovic. 2016

144 citations recorded by the source corpus.

Representations of probability measures in reproducing kernel Hilbert spaces provide a flexible framework for fully nonparametric hypothesis tests of independence, which can capture any type of departure from independence, including nonlinear associations and multivariate interactions. However, these approaches come with an at least quadratic computational cost in the number of observations, which can be prohibitive in many applications. Arguably, it is exactly in such large-scale datasets that capturing any type of dependence is of interest, so striking a favourable trade-off between computational efficiency and test performance for kernel independence tests would have a direct impact on their applicability in practice. In this contribution, we provide an extensive study of the use of large-scale kernel approximations in the context of independence testing, contrasting block-based, Nyström and random Fourier feature approaches. Through a variety of synthetic data experiments, it is demonstrated that our large-scale methods give comparable performance with existing methods while using significantly less computation time and memory.

Subfields: Artificial Intelligence, Civil and Structural Engineering, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Civil and Structural Engineering

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Differentiable Causal Discovery from Interventional Data (2020, background): “For example, KCI-test scales in O(n(3)) [43] and HSIC in O(n(2)) [51].”
A New Coefficient of Correlation (2019, background): “ch as the maximal correlation coecient [5, 12, 18, 30], various coecients based on joint cumulative distribution functions and ranks [3, 4, 7{9, 15, 19, 27, 29, 32, 33, 43{46], kernel-based methods [13, 14, 28, 37, 48], information theoretic coecients [21, 23, 31], coecients based on copulas [24, 36”
Approximate Kernel-Based Conditional Independence Tests for Fast Non-Parametric Causal Discovery (2017, methodology): “We will use a strategy that has already been successfully adopted in the context of unconditional dependence testing in doing so [12, 13].”
Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences (2018, methodology): “ncies between random variable variables. Since it also can be calculated in a simple way using kernels, it has found a wide range of applications including independence testing [Gretton et al., 2008, Zhang et al., 2018], variable selection [Song et al., 2012, Yamada et al., 2014], post selection inf”
Nonparametric independence testing via mutual information (2017, background): “One drawback of the kernel paradigm here is the computational complexity, though Jitkrittum, Szab´o and Gretton (2016) and Zhang et al. (2017) have recently attempted to address this issue.”
Hybrid Random Features (2021, methodology): “(1) These two are prominent examples of functions used in the so-called kernel methods (Gretton et al., 2005; Zhang et al., 2018) and beyond, i.e. in softmax-sampling (Blanc & Rendle, 2018).”
A fast algorithm for computing distance correlation (2018, background): “However, the use of these approximations leads to a reduction in power (Zhang et al., 2018).”