Fast Computational Algorithms for Large-Scale Distance and Kernel-Based Independence Testing

• Activity Number: 336 - Nonparametric Test in Unusual Data Structure or of Independence
• Type: Contributed
• Date/Time: Wednesday, August 5, 2020 : 10:00 AM to 2:00 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Asmita Roy* and Shubhadeep Chakraborty and Xianyang Zhang
• Companies: Texas A&M university and Texas A&M University and Texas A&M University
• Keywords: Distance Covariance; Hilbert-Schmidt Independence Criterion; Hilbert Spaces; Isometric Embedding; Tests for independence

Abstract

Measuring and testing for independence is a fundamental problem in statistics. A direct implementation of Distance Covariance(dCov) and Hilbert-Schmidt Independence Criterion(HSIC),two widely popular distance and kernel-based dependence metrics has time and storage complexities of the order of O(n^2),where n is the sample size. This quadratic computational cost can be prohibitive in applications involving large-scale datasets. In this paper we propose two fast computational algorithms for large-scale distance and kernel-based tests for independence.To achieve a speed up of the computation of the canonical unbiased estimators of dCov and HSIC, we propose the use of stochastic approximation of the Euclidean distance and the Euclidean distance induced kernel via isometric embeddings into Hilbert spaces. Our proposed estimators have time and space complexities of the order of O(nN^2) and O(nN) where N< < n,thus achieving computational efficiency over the canonical estimators in case of large-scale datasets when N< ?n. We study the large sample properties of our estimators and the asymptotic power of the proposed tests. Numerical studies illustrate the efficiency of our proposed tests.