Query: U statistics

title: Gaussian and bootstrap approximations for high dimensional U statistics and their applications
abstract: This paper studies the Gaussian and bootstrap approximations for the probabilities of a non degenerate U statistic belonging to the hyperrectangles in \mathbb{R}^d$ when the dimension $d$ is large. A two step Gaussian approximation procedure that does not impose structural assumptions on the data distribution is proposed. Subject to mild moment conditions on the kernel, we establish the explicit rate of convergence uniformly in the class of all hyperrectangles in \mathbb{R}^d$ that decays polynomially in sample size for a high dimensional scaling limit, where the dimension can be much larger than the sample size. We also provide computable approximation methods for the quantiles of the maxima of centered U statistics. Specifically, we provide a unified perspective for the empirical bootstrap, the randomly reweighted bootstrap, and the Gaussian multiplier bootstrap with the jackknife estimator of covariance matrix as randomly reweighted quadratic forms and we establish their validity. We show that all three methods are inferentially first order equivalent for high dimensional U statistics in the sense that they achieve the same uniform rate of convergence over all $d$ dimensional hyperrectangles. In particular, they are asymptotically valid when the dimension $d$ can be as large as $O(e^{n^c} for some constant $c \in (0,1/7) (Full abstract can be found in the paper.

title: Robust modifications of U statistics and applications to covariance estimation problems
abstract: Let $Y$ be a $d$ dimensional random vector with unknown mean \mu$ and covariance matrix \Sigma$ This paper is motivated by the problem of designing an estimator of \Sigma$ that admits tight deviation bounds in the operator norm under minimal assumptions on the underlying distribution, such as existence of only 4th moments of the coordinates of $Y$ To address this problem, we propose robust modifications of the operator valued U statistics, obtain non asymptotic guarantees for their performance, and demonstrate the implications of these results to the covariance estimation problem under various structural assumptions.

title: Asymptotically independent U statistics in high dimensional testing
abstract: Many high dimensional hypothesis tests aim to globally examine marginal or low dimensional features of a high dimensional joint distribution, such as testing of mean vectors, covariance matrices and regression coefficients. This paper constructs a family of U statistics as unbiased estimators of the \ell_p$ norms of those features. We show that under the null hypothesis, the U statistics of different finite orders are asymptotically independent and normally distributed. Moreover, they are also asymptotically independent with the maximum type test statistic, whose limiting distribution is an extreme value distribution. Based on the asymptotic independence property, we propose an adaptive testing procedure which combines $p$ values computed from the U statistics of different orders. We further establish power analysis results and show that the proposed adaptive procedure maintains high power against various alternatives.

title: Quantitative CLTs for symmetric $U$ statistics using contractions
abstract: We consider sequences of symmetric $U$ statistics, not necessarily Hoeffding degenerate, both in a one and multi dimensional setting, and prove quantitative central limit theorems (CLTs) based on the use of \it contraction operators} Our results represent an explicit counterpart to analogous criteria that are available for sequences of random variables living on the Gaussian, Poisson or Rademacher chaoses, and are perfectly tailored for geometric applications. As a demonstration of this fact, we develop explicit bounds for subgraph counting in generalised random graphs on Euclidean spaces; special attention is devoted to the so called `dense parameter regime' for uniformly distributed points, for which we deduce CLTs that are new even in their qualitative statement, and that substantially extend classical findings by Jammalamadaka and Janson (1986) and Bhattacharaya and Ghosh (1992)

title: Multisample adjusted U statistics that account for confounding covariates.
abstract: Multisample U statistics encompass a wide class of test statistics that allow the comparison of 2 or more distributions. U statistics are especially powerful because they can be applied to both numeric and nonnumeric data, eg, ordinal and categorical data where a pairwise similarity or distance like measure between categories is available. However, when comparing the distribution of a variable across 2 or more groups, observed differences may be due to confounding covariates. For example, in a case control study, the distribution of exposure in cases may differ from that in controls entirely because of variables that are related to both exposure and case status and are distributed differently among case and control participants. We propose to use individually reweighted data (ie, using the stratification score for retrospective data or the propensity score for prospective data) to construct adjusted U statistics that can test the equality of distributions across 2 (or more) groups in the presence of confounding covariates. Asymptotic normality of our adjusted U statistics is established and a closed form expression of their asymptotic variance is presented. The utility of our approach is demonstrated through simulation studies, as well as in an analysis of data from a case control study conducted among African Americans, comparing whether the similarity in haplotypes (ie, sets of adjacent genetic loci inherited from the same parent) occurring in a case and a control participant differs from the similarity in haplotypes occurring in 2 control participants.

title: Renewal theory for asymmetric U statistics
abstract: We extend a functional limit theorem for symmetric U statistics [Miller and Sen, 1972] to asymmetric U statistics, and use this to show some renewal theory results for asymmetric U statistics.

title: Theory Of U Statistics
abstract: Thank you for downloading theory of u statistics. As you may know, people have search hundreds times for their chosen books like this theory of u statistics, but end up in harmful downloads. Rather than enjoying a good book with a cup of tea in the afternoon, instead they juggled with some malicious virus inside their computer. theory of u statistics is available in our book collection an online access to it is set as public so you can get it instantly. Our books collection spans in multiple locations, allowing you to get the most less latency time to download any of our books like this one. Merely said, the theory of u statistics is universally compatible with any devices to read.

title: Randomized incomplete $U$ statistics in high dimensions
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.

title: Scaling up Empirical Risk Minimization: Optimization of Incomplete $U$ statistics
abstract: In a wide range of statistical learning problems such as ranking, clustering or metric learning among others, the risk is accurately estimated by $U$ statistics of degree $d\geq 1$ i.e. functionals of the training data with low variance that take the form of averages over $k$ tuples. From a computational perspective, the calculation of such statistics is highly expensive even for a moderate sample size $n$ as it requires averaging $O(n^d) terms. This makes learning procedures relying on the optimization of such data functionals hardly feasible in practice. It is the major goal of this paper to show that, strikingly, such empirical risks can be replaced by drastically computationally simpler Monte Carlo estimates based on $O(n) terms only, usually referred to as incomplete $U$ statistics, without damaging the $O_{\mathbb{P}(1/\sqrt{n} learning rate of Empirical Risk Minimization (ERM) procedures. For this purpose, we establish uniform deviation results describing the error made when approximating a $U$ process by its incomplete version under appropriate complexity assumptions. Extensions to model selection, fast rate situations and various sampling techniques are also considered, as well as an application to stochastic gradient descent for ERM. Finally, numerical examples are displayed in order to provide strong empirical evidence that the approach we promote largely surpasses more naive subsampling techniques.

title: Asymptotic distribution of AUC, NRIs, and IDI based on theory of U statistics.
abstract: The change in area under the curve (AUC) the integrated discrimination improvement (IDI) and net reclassification index (NRI) are commonly used measures of risk prediction model performance. Some authors have reported good validity of associated methods of estimating their standard errors (SE) and construction of confidence intervals, whereas others have questioned their performance. To address these issues, we unite the AUC, IDI, and three versions of the NRI under the umbrella of the U statistics family. We rigorously show that the asymptotic behavior of AUC, NRIs, and IDI fits the asymptotic distribution theory developed for U statistics. We prove that the AUC, NRIs, and IDI are asymptotically normal, unless they compare nested models under the null hypothesis. In the latter case, asymptotic normality and existing SE estimates cannot be applied to AUC, NRIs, or IDI. In the former case, SE formulas proposed in the literature are equivalent to SE formulas obtained from U statistics theory if we ignore adjustment for estimated parameters. We use Sukhatme Randles deWet condition to determine when adjustment for estimated parameters is necessary. We show that adjustment is not necessary for SEs of the AUC and two versions of the NRI when added predictor variables are significant and normally distributed. The SEs of the IDI and three category NRI should always be adjusted for estimated parameters. These results allow us to define when existing formulas for SE estimates can be used and when resampling methods such as the bootstrap should be used instead when comparing nested models. We also use the U statistic theory to develop a new SE estimate of AUC.