Concentration inequalities for two-sample rank processes with application to bipartite ranking

DOI10.1214/21-EJS1907zbMATH Open1471.62356arXiv2104.02943OpenAlexW3202421026MaRDI QIDQ2233587FDOQ2233587

Authors: Stephan Clémençon, Myrto Limnios, Nicolas Vayatis 

Publication date: 11 October 2021

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: The ROC curve is the gold standard for measuring the performance of a test/scoring statistic regarding its capacity to discriminate between two statistical populations in a wide variety of applications, ranging from anomaly detection in signal processing to information retrieval, through medical diagnosis. Most practical performance measures used in scoring/ranking applications such as the AUC, the local AUC, the p-norm push, the DCG and others, can be viewed as summaries of the ROC curve. In this paper, the fact that most of these empirical criteria can be expressed as two-sample linear rank statistics is highlighted and concentration inequalities for collections of such random variables, referred to as two-sample rank processes here, are proved, when indexed by VC classes of scoring functions. Based on these nonasymptotic bounds, the generalization capacity of empirical maximizers of a wide class of ranking performance criteria is next investigated from a theoretical perspective. It is also supported by empirical evidence through convincing numerical experiments.

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

Recommendations

• Applications of concentration inequalities for statistical scoring and ranking problems
• Generalization bounds for the area under the ROC curve
• Adaptive estimation of the optimal ROC curve and a bipartite ranking algorithm
• Generalization performance of bipartite ranking algorithms with convex losses
• Bipartite ranking: a risk-theoretic perspective

zbMATH Keywords

concentration inequalitiesempirical risk minimizationgeneralization boundsstatistical learning theorybipartite rankingtwo-sample linear rank statisticsrank process

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Inequalities; stochastic orderings (60E15) Empirical decision procedures; empirical Bayes procedures (62C12) Nonparametric inference (62G99)

Cites Work

• Weak convergence and empirical processes. With applications to statistics
• Approximation Theorems of Mathematical Statistics
• Asymptotic Statistics
• Rates of strong uniform consistency for multivariate kernel density estimators. (Vitesse de convergence uniforme presque sûre pour des estimateurs à noyaux de densités multivariées)
• Title not available (Why is that?)
• U-processes: Rates of convergence
• A Class of Statistics with Asymptotically Normal Distribution
• An estimate on the supremum of a nice class of stochastic integrals and U-statistics
• Title not available (Why is that?)
• A statistical view of clustering performance through the theory of \(U\)-processes
• Title not available (Why is that?)
• Asymptotic Normality of Simple Linear Rank Statistics Under Alternatives
• Sharper bounds for Gaussian and empirical processes
• A distribution-free theory of nonparametric regression
• Weighted uniform consistency of kernel density estimators.
• Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ranking and empirical minimization of \(U\)-statistics
• Some limit theorems for empirical processes (with discussion)
• Generalization bounds for the area under the ROC curve
• Theory of Classification: a Survey of Some Recent Advances
• Some New Estimates for Distribution Functions
• Ranking data with ordinal labels: optimality and pairwise aggregation
• Tree-Based Ranking Methods
• Overlaying classifiers: A practical approach to optimal scoring
• Ranking the best instances
• Bipartite ranking: a risk-theoretic perspective
• Asymptotically Most Powerful Rank-Order Tests
• Ranking with a P-Norm Push
• The performance of kernel density functions in kernel distribution function estimation
• A central limit theorem for two-sample U-processes
• Subset Ranking Using Regression
• The treerank tournament algorithm for multipartite ranking

Cited In (4)

• Applications of concentration inequalities for statistical scoring and ranking problems
• Adaptive estimation of the optimal ROC curve and a bipartite ranking algorithm
• Ranking the best instances
• Generalization bounds for the area under the ROC curve

This page was built for publication: Concentration inequalities for two-sample rank processes with application to bipartite ranking

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