Worst-case versus average-case design for estimation from partial pairwise comparisons

DOI10.1214/19-AOS1838zbMath1452.62561arXiv1707.06217MaRDI QIDQ2196209

Thomas A. Courtade, Ashwin Pananjady, Martin J. Wainwright, Cheng Mao, Vidya Muthukumar

Publication date: 28 August 2020

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

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

zbMATH Keywords

pairwise comparisonsstrong stochastic transitivitystructured matrix completion

Mathematics Subject Classification ID

Statistical ranking and selection procedures (62F07) Response surface designs (62K20) Paired and multiple comparisons; multiple testing (62J15) Matrix completion problems (15A83) Lists of open problems (00A27)

Related Items (7)

Isotonic regression with unknown permutations: statistics, computation and adaptation ⋮ Optimal full ranking from pairwise comparisons ⋮ Optimal permutation estimation in crowdsourcing problems ⋮ Estimation of Monge matrices ⋮ Towards optimal estimation of bivariate isotonic matrices with unknown permutations ⋮ On the estimation of latent distances using graph distances ⋮ Spectral method and regularized MLE are both optimal for top-\(K\) ranking

Uses Software

• trueskill
• TrueSkill

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Models for paired comparison data: a review with emphasis on dependent data
• Probability models and statistical analyses for ranking data. Papers presented at the AMS-IMS-SIAM conference, Amherst, MA, USA, June 1990
• Binary choice probabilities: on the varieties of stochastic transitivity
• Optimal rates of statistical seriation
• Matrix estimation by universal singular value thresholding
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
• Emergence of Scaling in Random Networks
• A remark on the existence of finite graphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Aggregation and Social Choice: A Mean Voter Theorem
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Competitive analysis of the top-K ranking problem
• Minimax Rates and Efficient Algorithms for Noisy Sorting
• High-Dimensional Statistics
• Uncoupled isotonic regression via minimum Wasserstein deconvolution
• Estimation in Tournaments and Graphs Under Monotonicity Constraints
• Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
• Rank Centrality: Ranking from Pairwise Comparisons
• The Algebraic Combinatorial Approach for Low-Rank Matrix Completion

This page was built for publication: Worst-case versus average-case design for estimation from partial pairwise comparisons