Randomized incomplete U-statistics in high dimensions

DOI10.1214/18-AOS1773MaRDI QIDQ2284368zbMATH OpenFDO

Authors Xiaohui Chen, Kengo Kato

Publication date 15 January 2020

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.00771, https://projecteuclid.org/euclid.aos/1572487388

zbMATH Keywords

Bernoulli samplingbootstrapdivide and conquerGaussian approximationincomplete \(U\)-statisticsrandomized inferencesampling with replacement

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Approximations to statistical distributions (nonasymptotic) (62E17) Bootstrap, jackknife and other resampling methods (62F40) Hypothesis testing in multivariate analysis (62H15)

Abstract: This paper studies inference for the mean vector of a high-dimensional $U$-statistic. In the era of Big Data, the dimension $d$ of the $U$-statistic and the sample size $n$ of the observations tend to be both large, and the computation of the $U$-statistic is prohibitively demanding. Data-dependent inferential procedures such as the empirical bootstrap for $U$-statistics is even more computationally expensive. To overcome such computational bottleneck, incomplete $U$-statistics obtained by sampling fewer terms of the $U$-statistic are attractive alternatives. In this paper, we introduce randomized incomplete $U$-statistics with sparse weights whose computational cost can be made independent of the order of the $U$-statistic. We derive non-asymptotic Gaussian approximation error bounds for the randomized incomplete $U$-statistics in high dimensions, namely in cases where the dimension $d$ is possibly much larger than the sample size $n$, for both non-degenerate and degenerate kernels. In addition, we propose generic bootstrap methods for the incomplete $U$-statistics that are computationally much less-demanding than existing bootstrap methods, and establish finite sample validity of the proposed bootstrap methods. Our methods are illustrated on the application to nonparametric testing for the pairwise independence of a high-dimensional random vector under weaker assumptions than those appearing in the literature.

Review text

The authors consider the problem of statistical inference for the mean vector \(\mathbb{E}h(X_1,\ldots,X_r)\), based on independent and identically distributed data \(X_1,\ldots,X_n\) taking values in a measurable space \((S,\mathcal{S})\), and where \(h:S^r\mapsto\mathbb{R}^d\) is a fixed, symmetric function. Their aim is to develop tools for the setting where \(d\) is possibly much larger than \(n\), but where \(n\) is also large. In this setting, the commonly used \(U\)-statistic \[ \frac{1}{|I_{n,r}|}\sum_{(i_1,\ldots,i_r)\in I_{n,r}}h(X_{i_1},\ldots,X_{i_r})\,, \] where \(I_{n,r}\) is the set of all \(r\)-tuples in \(\{1,\ldots,n\}\), suffers from problems of computational scalability. As a solution to this, the authors propose two randomized incomplete \(U\)-statistics, where the average is taken over only a randomly chosen subset of \(I_{n,r}\), rather than over all elements of this set. The first of these uses Bernoulli sampling (or, equivalently, sampling without replacement), and the second uses sampling with replacement. Under some assumptions (such as some boundedness assumptions), Gaussian approximation results are established for these randomized incomplete \(U\)-statistics, with an explicit rate of convergence, in both the nondegenerate and degenerate cases. Since the limiting Gaussian distribution here has a covariance matrix depending on the unknown underlying distribution, fully data-dependent bootstrap techniques are developed which make these results applicable. The paper concludes with a simulation study investigating this framework in the setting of testing for pairwise independence of elements of a high-dimensional random vector using several well-known statistics from the literature.

Recommendations

• Approximating high-dimensional infinite-order \(U\)-statistics: statistical and computational guarantees
• scientific article; zbMATH DE number 5204610
• Asymptotically independent U-statistics in high-dimensional testing
• scientific article; zbMATH DE number 1959482
• High Dimensional Inference With Random Maximum A-Posteriori Perturbations
• Gaussian approximations for high-dimensional non-degenerate \(U\)-statistics via exchangeable pairs
• On U-statistics with random kernels
• Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
• scientific article; zbMATH DE number 3982169

Cites work

• A Class of Statistics with Asymptotically Normal Distribution
• A consistent test of independence based on a sign covariance related to Kendall's tau
• A Non-Parametric Test of Independence
• A Scalable Bootstrap for Massive Data
• Asymptotic distribution of symmetric statistics
• Asymptotic distributions for weighted U-statistics
• Asymptotic distributions of weighted \(U\)-statistics of degree 2
• Asymptotic normality of permutation statistics derived from weighted sums of bivariate functions
• Asymptotic Statistics
• Central limit theorems and bootstrap in high dimensions
• Consistency of the generalized bootstrap for degenerate \(U\)-statistics
• Distribution-free tests of independence in high dimensions
• Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates
• Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
• Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors
• Generalized bootstrap for studentized U-statistics: A rank statistic approach
• scientific article; zbMATH DE number 3850298 (Why is no real title available?)
• Incomplete Generalized U‐Statistics for Food Risk Assessment
• Jackknife multiplier bootstrap: finite sample approximations to the \(U\)-process supremum with applications
• Large-Sample Theory for the Bergsma-Dassios Sign Covariance
• Measuring and testing dependence by correlation of distances
• On the asymptotic behavior of weighted U-statistics
• On the bootstrap of \(U\) and \(V\) statistics
• On weighted U-statistics for stationary processes.
• Pairwise Independence of Jointly Dependent Variables
• Quantifying uncertainty in random forests via confidence intervals and hypothesis tests
• Random quadratic forms and the bootstrap for \(U\)-statistics
• Randomized incomplete \(U\)-statistics in high dimensions
• Reduced U-statistics and the Hodges-Lehmann estimator
• Scaling-up empirical risk minimization: optimization of incomplete U-statistics
• Some asymptotic theory for the bootstrap
• Some properties of incomplete U-statistics
• Testing independence in high dimensions with sums of rank correlations
• Testing mutual independence in high dimension via distance covariance
• The asymptotic distributions of incomplete U-statistics
• Weak convergence and empirical processes. With applications to statistics
• Weighted bootstrap for \(U\)-statistics

Cited in

(38)

• Direct regression modelling of high-order moments in big data
• Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
• Gaussian approximations for high-dimensional non-degenerate \(U\)-statistics via exchangeable pairs
• Improved central limit theorem and bootstrap approximations in high dimensions
• On the consistency of incomplete U-statistics under infinite second-order moments
• Stratified incomplete local simplex tests for curvature of nonparametric multiple regression
• Edgeworth expansions for network moments
• Rates of convergence for random forests via generalized U-statistics
• A robust bootstrap change point test for high-dimensional location parameter
• High-dimensional central limit theorems by Stein's method
• Approximating high-dimensional infinite-order \(U\)-statistics: statistical and computational guarantees
• Randomized incomplete \(U\)-statistics in high dimensions
• Inference from small and big data sets with error rates
• Fast surrogates of U-statistics
• Scaling-up empirical risk minimization: optimization of incomplete U-statistics
• Design based incomplete U-statistics
• High-dimensional central limit theorems for homogeneous sums
• Distributed inference for two‐sample U‐statistics in massive data analysis
• Inference for High-Dimensional Exchangeable Arrays
• Testing the martingale difference hypothesis in high dimension
• Central limit theorems for high dimensional dependent data
• On variance estimation of random forests with Infinite-order U-statistics
• Asymptotic distributions of a new type of design-based incomplete U-statistics
• Testing for practically significant dependencies in high dimensions via bootstrapping maxima of U-statistics
• Gaussian Approximation and Spatially Dependent Wild Bootstrap for High-Dimensional Spatial Data
• Berry-Esseen theorems for the asymptotic normality of incomplete U-statistics with Bernoulli sampling
• Goodness-of-fit tests for linear non-Gaussian structural equation models
• Statistical Inference for High-Dimensional Convoluted Rank Regression
• Statistical Inference for High-Dimensional Spectral Density Matrix
• U-Statistic Reduction: Higher-Order Accurate Risk Control and Statistical-Computational Trade-Off
• K-sample studentized tests: random lifter approach
• An exponential inequality for Hilbert-valued U-statistics of i.i.d. data
• Deviation and moment inequalities for Banach-valued U-statistics
• Bootstrapping networks with latent space structure
• Higher-Order Accurate Two-Sample Network Inference and Network Hashing
• Nonparametric estimation of conditional densities by generalized random forests
• High-dimensional bootstrap and asymptotic expansion
• Testing the equality of estimable parameters across many populations

This page was built for publication: Randomized incomplete \(U\)-statistics in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2284368)