Statistical and computational challenges in ranking

Alexandra Carpentier, Nicolas Verzelen · 2025

Read Statistical and computational challenges in ranking by Alexandra Carpentier, Nicolas Verzelen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-21111.txt.

Introduction

Alexandra Carpentier and Nicolas Verzelen survey a deceptively simple question: given many experts answering many questions, can we rank the experts by ability, and can we do it both optimally and quickly? In the crowdsourcing model, each expert's chance of correctness rises with ability, and the ability matrix is monotone once the experts are placed in their true, unknown order. Ranking is then estimation of that hidden permutation.

The survey's center of interest is the computational-statistical gap, the regime where the information exists but no fast algorithm is believed to recover it. Recent results surveyed here disprove such a gap for this ranking problem. The argument is built from a simpler sub-problem, detecting a hidden submatrix, whose lower bounds come from low-degree polynomial methods. Statisticians and platform designers alike learn when crowdsourced judgment can be sorted at full efficiency, and where the genuine limits lie.

Catalog record

CREATORAlexandra Carpentier, Nicolas Verzelen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-21111

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Statistical and computational challenges in ranking Thanks: A shorter version of this review paper is to be published in the proceedings of the ICM 2026. Alexandra Carpentier, Nicolas Verzelen Abstract We consider the problem of ranking n n experts according to their abilities, based on the correctness of their answers to d d questions. This is modeled by the so-called crowd-sourcing model, where the answer of expert i i on question k k is modeled by a random entry, parametrized by M i , k M_{i,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 M are available in the literature. We consider here the general isotonic crowd-sourcing model, where M M is assumed to be isotonic up to an unknown permutation π ∗ \pi^{*} of the experts - namely, M π ∗ − 1 ​ ( i ) , k ≥ M π ∗ − 1 ​ ( i + 1 ) , k M_{\pi^{*-1}(i),k}\geq M_{\pi^{*-1}(i+1),k} for any i ∈ [ n − 1 ] , k ∈ [ d ] i\in[n-1],k\in[d] . Then, ranking experts amounts to constructing an estimator of π ∗ \pi^{*} . 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 M is constrained to be of the form λ ​ 𝟏 ​ { S × T } \lambda\mathbf{1}\{S\times T\} where S ⊂ [ n ] , T ⊂ [ d ] S\subset[n],T\subset[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. 1 Introduction 1.1 Ranking problems. Ranking problems have received a lot of attention in the statistical, machine learning, and computer science literature. This includes a variety of practical situations ranging from ranking experts/workers in crowd-sourced data, ranking players in a tournament or equivalently sorting objects based on pairwise comparisons. To fix ideas, let us consider a problem where we have n experts (or workers) and d questions (or tasks). Given an expert i\in[n] and a question k\in[d] , the random variables Y_{i,k} stands for the validity of the response of expert i to question k . More specifically, we have Y_{i,k}=1 if expert i answers correctly to question k and Y_{i,k}=-1 otherwise. It is standard 1 1 1 There exist other parametrizations but those turn out to be equivalent. to assume that the Y_{i,k} ’s are independent and that there exists there exists an unknown matrix M\in[0,1]^{n\times d} such that \mathbb{P}_{M}[Y_{i,k}=1]=\frac{1+M_{i,k}}{2}\quad\quad\quad\quad\mathbb{P}_{M}[Y_{i,k}=-1]=\frac{1-M_{i,k}}{2}\kern 5.0pt, so that \mathbb{E}_{M}[Y_{i,k}]=1 . Here, the matrix M encodes the average performance of each expert on each question with M_{i,k}=0 when the expert does not answer the question better than random guess and M_{i,k}=1 the expert’s knowledge is perfect on that question. Depending on the problem at hand, the statistical may fully observe the matrix Y or observe a subset of its entries (partial observations). For tournament problems, we have n=d players (or objects) and (1+M_{i,k})/2 stands for the probability that player i wins against player k . Based on these noisy data, the general goal is to provide, based on the matrix Y , a full ranking of the experts or of the players. 1.1.1 Literature review. Originally, these problems have been tackled using parametric model for the matrix M . Notably for tournament problem, this includes the noisy sorting model [ 7 ] or Bradley-Luce-Terry model [ 6 ] . Still, it has been observed that these simple models are often unrealistic and do not tend to fit data well. This has spurred a recent stream of literature where strong parametric assumptions are replaced by non-parametric shape-constrained assumptions [ 54 , 55 , 56 , 57 , 44 , 43 , 39 , 26 , 4 , 52 , 49 , 50 , 28 ] . In what follows, a bounded matrix A\in[0,1]^{n\times d} is said to be isotonic if all its columns are non-increasing, that is A_{i,k}\geq A_{i+1,k} for any i\in[n-1] and k\in[d] . Besides, a matrix A is said to be bi-isotonic if both its rows and its columns are non-increasing. The most emblematic shape-constrained non-parametric models for ranking can be divided into three classes. • For tournament problems, the strong stochastically transitive (SST) model presumes that the square matrix M is, up to a common permutation \pi^{*} of the rows and of the columns, bi-isotonic and satisfies the skew symmetry condition M_{i,k}+M_{k,i}=1 . Optimal rates for estimation of the permutation \pi^{*} have been pinpointed in the earlier paper of Shah et al. [ 55 ] . However at that time there remained a large gap between these optimal rates and the best known performances of polynomial-time algorithms. Although this has been partially filled over the year, this has led to conjecture the existence of a statistical-computational gap [ 44 , 39 ] - namely, that no ranking algorithms was at the same time statistically optimal, and computationally efficient, i.e. polynomial time. See Subsection 1.3 , and also later in this paper, for a more precise explanation. • For crowdsourcing data, the counterpart of the SST model is the so-called bi-isotonic model, where the rectangular matrix M is bi-isotonic, up to an unknown permutation \pi^{*} of its rows and an unknown permutation \eta^{*} of its columns. From a modeling perspective, this presumes the existence of two unambiguously orderings \pi^{*} and \eta^{*} of the experts –from the best-one to the wort-one– and of the questions – from the simplest one to the most difficult one. This model turns out to be really similar to the SST model and the existence of a statistical-computational gap has also been conjectured [ 44 ] . See however [ 39 , 49 , 28 ] for two slight variations on this bi-isotonic setting where this conjecture has been disproved, and where polynomial-time and statistically optimal algorithms have been provided. • Finally and again for crowdsourcing data, another relevant model is the so-called isotonic model, where the rectangular matrix M is (only) isotonic, up to an unknown permutation \pi^{*} of its rows [ 26 ] . In this case, there is no structure in M along its columns, namely according to the questions, so that the isotonic model more flexible than the bi-isotonic and SST models. It is in fact the most general model under which an unambiguous ranking of the experts is well-defined. In this model as well, there was originally a gap between the (statistical) optimal rates, and the rate obtained by the (polynomial-time) algorithm in [ 26 ] so that again, a statistical-computational gap has been widely conjectured. Interestingly, this conjecture was proven false in this model [ 50 ] , and a polynomial-time and statistically

Read the complete text