Design based incomplete U-statistics

DOI10.5705/SS.202019.0098MaRDI QIDQ5155202zbMATH OpenOpenAlexFDO

Authors Xiangshun Kong, Wei Zheng

Publication date 6 October 2021

Published in STATISTICA SINICA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.04348

zbMATH Keywords

asymptotically efficientbalanced incomplete block design (BIBD)big datadesign of experimentsubsampling

Mathematics Subject Classification ID

Point estimation (62F10) Asymptotic properties of parametric estimators (62F12) Statistical block designs (62K10) Statistical aspects of big data and data science (62R07)

Abstract: U-statistics are widely used in fields such as economics, machine learning, and statistics. However, while they enjoy desirable statistical properties, they have an obvious drawback in that the computation becomes impractical as the data size $n$ increases. Specifically, the number of combinations, say $m$, that a U-statistic of order $d$ has to evaluate is $O(n^d)$. Many efforts have been made to approximate the original U-statistic using a small subset of combinations since Blom (1976), who referred to such an approximation as an incomplete U-statistic. To the best of our knowledge, all existing methods require $m$ to grow at least faster than $n$, albeit more slowly than $n^d$, in order for the corresponding incomplete U-statistic to be asymptotically efficient in terms of the mean squared error. In this paper, we introduce a new type of incomplete U-statistic that can be asymptotically efficient, even when $m$ grows more slowly than $n$. In some cases, $m$ is only required to grow faster than $sqrtn$. Our theoretical and empirical results both show significant improvements in the statistical efficiency of the new incomplete U-statistic.

Recommendations

• Randomized incomplete \(U\)-statistics in high dimensions
• Incomplete generalized L-statistics
• Scaling-up empirical risk minimization: optimization of incomplete U-statistics
• Incomplete U -statistics of permanent design
• Fast surrogates of U-statistics

Cites work

• A Class of Statistics with Asymptotically Normal Distribution
• Almost sure convergence of generalized U-statistics
• An invariance principle for reduced U-statistics
• Consistency and Unbiasedness of Certain Nonparametric Tests
• Consistency of the generalized bootstrap for degenerate \(U\)-statistics
• Fast surrogates of U-statistics
• Generalized bootstrap for studentized U-statistics: A rank statistic approach
• scientific article; zbMATH DE number 3850298 (Why is no real title available?)
• scientific article; zbMATH DE number 3928085 (Why is no real title available?)
• scientific article; zbMATH DE number 47948 (Why is no real title available?)
• scientific article; zbMATH DE number 775913 (Why is no real title available?)
• scientific article; zbMATH DE number 3352656 (Why is no real title available?)
• Incomplete U -statistics of permanent design
• Mathematical Statistics
• Minimum variance rectangular designs for U-statistics.
• On Incomplete U-Statistics Having Minimum Variance
• On the Asymptotic Distribution of Differentiable Statistical Functions
• Orthogonal Array-Based Latin Hypercubes
• ORTHOGONAL EXPANSIONS AND U-STATISTICS
• Random quadratic forms and the bootstrap for \(U\)-statistics
• Randomized incomplete \(U\)-statistics in high dimensions
• Reduced U-statistics and the Hodges-Lehmann estimator
• Some asymptotic theory for the bootstrap
• Some properties of incomplete U-statistics
• Strong orthogonal arrays and associated Latin hypercubes for computer experiments
• Testing for Stochastic Monotonicity
• Variance estimation of a general u-statistic with appllication to cross-validation
• Weak convergence of generalized U-statistics

Cited in

(12)

• Incomplete generalized L-statistics
• Product-form estimators: exploiting independence to scale up Monte Carlo
• Edgeworth expansions for network moments
• Approximating high-dimensional infinite-order \(U\)-statistics: statistical and computational guarantees
• Fast surrogates of U-statistics
• U-statistics for some nonparametric incomplete data models with side information
• Scaling-up empirical risk minimization: optimization of incomplete U-statistics
• Incomplete U -statistics of permanent design
• U-statistics with conditional kernels for incomplete data models
• The divide-and-conquer sequential Monte Carlo algorithm: theoretical properties and limit theorems
• Asymptotic distributions of a new type of design-based incomplete U-statistics
• U-Statistic Reduction: Higher-Order Accurate Risk Control and Statistical-Computational Trade-Off

This page was built for publication: Design based incomplete U-statistics

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