Optimal permutation estimation in crowdsourcing problems

DOI10.1214/23-AOS2271MaRDI QIDQ6136577zbMATH OpenFDO

Authors Emmanuel Pilliat, Alexandra Carpentier, Nicolas Verzelen

Publication date 31 August 2023

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

Full work available at URL https://arxiv.org/abs/2211.04092, https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-3/Optimal-Permutation-Estimation-in-CrowdSourcing-problems/10.1214/23-AOS2271.full

zbMATH Keywords

bi-isotonic matricesrankingsub-Gaussian noise

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20)

Abstract: Motivated by crowd-sourcing applications, we consider a model where we have partial observations from a bivariate isotonic n x d matrix with an unknown permutation $pi$ * acting on its rows. Focusing on the twin problems of recovering the permutation $pi$ * and estimating the unknown matrix, we introduce a polynomial-time procedure achieving the minimax risk for these two problems, this for all possible values of n, d, and all possible sampling efforts. Along the way, we establish that, in some regimes, recovering the unknown permutation $pi$ * is considerably simpler than estimating the matrix.

Recommendations

• A Permutation-Based Model for Crowd Labeling: Optimal Estimation and Robustness
• Optimal Inference in Crowdsourced Classification via Belief Propagation
• Task design in complex crowdsourcing experiments: item assignment optimization
• Efficient crowdsourcing of unknown experts using multi-armed bandits
• Optimal stopping and worker selection in crowdsourcing: an adaptive sequential probability ratio test framework
• Spectral methods meet EM: a provably optimal algorithm for crowdsourcing
• Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
• On computing an optimal permutation of ranks for multiselection
• Bandit-based task assignment for heterogeneous crowdsourcing

Cites work

• A Permutation-Based Model for Crowd Labeling: Optimal Estimation and Robustness
• Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
• Estimation in Tournaments and Graphs Under Monotonicity Constraints
• Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
• Heteroskedastic PCA: algorithm, optimality, and applications
• High-dimensional statistics. A non-asymptotic viewpoint
• scientific article; zbMATH DE number 3073477 (Why is no real title available?)
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Matrix estimation by universal singular value thresholding
• Minimax rates and efficient algorithms for noisy sorting
• Minimax rates in sparse, high-dimensional change point detection
• Noisy sorting without resampling
• On matrix estimation under monotonicity constraints
• Optimal full ranking from pairwise comparisons
• Optimal multiple change-point detection for high-dimensional data
• Optimal rates of statistical seriation
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
• Towards optimal estimation of bivariate isotonic matrices with unknown permutations
• Worst-case versus average-case design for estimation from partial pairwise comparisons

Cited in

(4)

• Task design in complex crowdsourcing experiments: item assignment optimization
• Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems
• Seriation of Tœplitz and latent position matrices: optimal rates and computational trade-offs

This page was built for publication: Optimal permutation estimation in crowdsourcing problems

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