Worst-case versus average-case design for estimation from partial pairwise comparisons
From MaRDI portal
Publication:2196209
DOI10.1214/19-AOS1838zbMATH Open1452.62561arXiv1707.06217MaRDI QIDQ2196209FDOQ2196209
Authors: Ashwin Pananjady, Cheng Mao, Vidya Muthukumar, Martin J. Wainwright, Thomas A. Courtade 
Publication date: 28 August 2020
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: Pairwise comparison data arises in many domains, including tournament rankings, web search, and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items, we study the problem of estimating the underlying comparison probabilities under the assumption of strong stochastic transitivity (SST). We also consider the noisy sorting subclass of the SST model. We show that when the assignment of items to the topology is arbitrary, these permutation-based models, unlike their parametric counterparts, do not admit consistent estimation for most comparison topologies used in practice. We then demonstrate that consistent estimation is possible when the assignment of items to the topology is randomized, thus establishing a dichotomy between worst-case and average-case designs. We propose two estimators in the average-case setting and analyze their risk, showing that it depends on the comparison topology only through the degree sequence of the topology. The rates achieved by these estimators are shown to be optimal for a large class of graphs. Our results are corroborated by simulations on multiple comparison topologies.
Full work available at URL: https://arxiv.org/abs/1707.06217
Recommendations
- scientific article; zbMATH DE number 2172872
- Approximate and exact optimal designs for paired comparisons of partial profiles when there are two groups of factors
- On the choice of optimality criteria in comparing statistical designs
- Asymptotic relative efficiency of designs for factorial paired comparison experiments
- Comparing search and estimation performances of designs based on a compound criterion
- OPTIMAL DESIGNS FOR 2kPAIRED COMPARISON EXPERIMENTS
- Optimal designs for asymmetric linear paired comparisons with a profile strength constraint
- Optimal paired comparison designs for factorial and quadratic models
Statistical ranking and selection procedures (62F07) Matrix completion problems (15A83) Paired and multiple comparisons; multiple testing (62J15) Response surface designs (62K20) Lists of open problems (00A27)
Cites Work
- Probability models and statistical analyses for ranking data. Papers presented at the AMS-IMS-SIAM conference, Amherst, MA, USA, June 1990
- Title not available (Why is that?)
- Matrix estimation by universal singular value thresholding
- Emergence of Scaling in Random Networks
- Title not available (Why is that?)
- High-Dimensional Statistics
- Title not available (Why is that?)
- Binary choice probabilities: on the varieties of stochastic transitivity
- Models for paired comparison data: a review with emphasis on dependent data
- The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- A remark on the existence of finite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Aggregation and Social Choice: A Mean Voter Theorem
- Title not available (Why is that?)
- Noisy sorting without resampling
- Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
- Data-driven rank breaking for efficient rank aggregation
- Rank Centrality: Ranking from Pairwise Comparisons
- Competitive analysis of the top-K ranking problem
- Optimal rates of statistical seriation
- Estimation in Tournaments and Graphs Under Monotonicity Constraints
- Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
- Minimax Rates and Efficient Algorithms for Noisy Sorting
- Uncoupled isotonic regression via minimum Wasserstein deconvolution
Cited In (8)
- List's worst-average-case or WAC ratio
- Towards optimal estimation of bivariate isotonic matrices with unknown permutations
- Optimal permutation estimation in crowdsourcing problems
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- On the estimation of latent distances using graph distances
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Optimal full ranking from pairwise comparisons
- Estimation of Monge matrices
Uses Software
This page was built for publication: Worst-case versus average-case design for estimation from partial pairwise comparisons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196209)
