mlsanityData to 7 Oct 2026

Statistical and computational challenges in ranking

arXiv 2512.21111 ↗First posted 24 Dec 2025math.ST stat.ML stat.THcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider the problem of ranking n experts according to their abilities, based on the correctness of their answers to d questions. This is modeled by the so-called crowd-sourcing model, where the answer of expert i on question k is modeled by a random entry, parametrized by Mi,k which is increasing linearly with the expected quality of the answer. To enable the unambiguous ranking of the experts by ability, several assumptions on M are available in the literature. We consider here the general isotonic crowd-sourcing model, where M is assumed to be isotonic up to an unknown permutation π^* of the experts - namely, M_π*-1(i),k ≥ M_π*-1(i+1),k for any i∈ [n-1], k ∈ [d]. Then, ranking experts amounts to constructing an estimator of π^*. In particular, we investigate here the existence of statistically optimal and computationally efficient procedures and we describe recent results that disprove the existence of computational-statistical gaps for this problem. To provide insights on the key ideas, we start by discussing simpler and yet related sub-problems, namely sub-matrix detection and estimation. This corresponds to specific instances of the ranking problem where the matrix M is constrained to be of the form λ mathbf 1S× T where Ssubset [n], Tsubset [d]. This model has been extensively studied. We provide an overview of the results and proof techniques for this problem with a particular emphasis on the computational lower bounds based on low-degree polynomial methods. Then, we build upon this instrumental sub-problem to discuss existing results and algorithmic ideas for the general ranking problem.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 42 of its 64 references that are in the map. First posted on arXiv 24 Dec 2025.

Builds on

42 of 64 references.

References · 42

  1. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  2. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  3. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  4. 2015Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependencecited by 59
  5. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  6. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  7. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  8. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  9. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
  10. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  11. 2015Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issuescited by 32
  12. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
30 more
  1. 2014Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatricescited by 29
  2. 2014Computational Lower Bounds for Community Detection on Random Graphscited by 21
  3. 2015Information Limits for Recovering a Hidden Communitycited by 18
  4. 2017Minimax Rates and Efficient Algorithms for Noisy Sortingcited by 15
  5. 2019Universality of Computational Lower Bounds for Submatrix Detectioncited by 13
  6. 2015Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrixcited by 12
  7. 2016A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustnesscited by 12
  8. 2018Uncoupled isotonic regression via minimum Wasserstein deconvolutioncited by 12
  9. 2025Computational Complexity of Statistics: New Insights from Low-Degree Polynomialscited by 12
  10. 2013Community Detection in Sparse Random Networkscited by 11
  11. 2016Optimal Rates of Statistical Seriationcited by 10
  12. 2019Optimal Permutation Recovery in Permuted Monotone Matrix Modelcited by 10
  13. 2015Finding One Community in a Sparse Graphcited by 8
  14. 2024Tensor cumulants for statistical inference on invariant distributionscited by 8
  15. 2023Is Planted Coloring Easier than Planted Clique?cited by 7
  16. 2025Sharp Phase Transitions in Estimation with Low-Degree Polynomialscited by 7
  17. 2016Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisonscited by 6
  18. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  19. 2023Active Ranking of Experts Based on their Performances in Many Taskscited by 6
  20. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  21. 2025Low-degree lower bounds via almost orthonormal basescited by 5
  22. 2015Submatrix localization via message passingcited by 4
  23. 2018Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutationscited by 4
  24. 2023Detection-Recovery Gap for Planted Dense Cyclescited by 4
  25. 2025Stochastic block models with many communities and the Kesten--Stigum boundcited by 4
  26. 2025Computational lower bounds in latent models: clustering, sparse-clustering, biclusteringcited by 4
  27. 2018Breaking the 1/√n Barrier: Faster Rates for Permutation-based Models in Polynomial Timecited by 3
  28. 2024Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraphcited by 2
  29. 2024Optimal level set estimation for non-parametric tournament and crowdsourcing problemscited by 1
  30. 2025Optimal community detection in dense bipartite graphscited by 1

Built on by

Not cited yet.