Statistical and computational challenges in ranking

• URL: http://arxiv.org/abs/2512.21111v1
• Date: Wed, 24 Dec 2025 11:18:06 GMT
• Title: Statistical and computational challenges in ranking
• Authors: Alexandra Carpentier, Nicolas Verzelen,
• Abstract summary: We consider the problem of ranking $n$ experts according to their abilities, based on the correctness of their answers to $d$ questions.<n>We investigate here the existence of statistically optimal and computationally efficient procedures for this problem.
• Score: 53.03724383992195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $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$ 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} \geq M_{π^{*-1}(i+1),k}$ for any $i\in [n-1], k \in [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 1\{S\times T\}$ where $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.

Related papers

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials [0.0]
  We investigate the model $Y=tfrac1sqrt1+sigma2(Pi_* X Q_* + sigma Z)<n>Consider the hypothesis testing problem of distinguishing this model from the case where $X$ and $Y$.<n>Results establish a smooth transition in the effectiveness of low-degree algorithms for this problem.
  arXiv  Detail & Related papers  (2025-04-04T00:32:38Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• A Spectral Approach to Item Response Theory [6.5268245109828005]
  We propose a emphnew item estimation algorithm for the Rasch model. The core of our algorithm is the computation of the stationary distribution of a Markov chain defined on an item-item graph. Experiments on synthetic and real-life datasets show that our algorithm is scalable, accurate, and competitive with the most commonly used methods in the literature.
  arXiv  Detail & Related papers  (2022-10-09T18:57:08Z)
• On the Multidimensional Random Subset Sum Problem [0.9007371440329465]
  In the Random Subset Sum Problem, given $n$ i.i.d. random variables $X_1,..., X_n$, we wish to approximate any point $z in [-1,1]$ as the sum of a subset $X_i_1(z),..., X_i_s(z)$ of them, up to error $varepsilon cdot. We prove that, in $d$ dimensions, $n = O(d3log frac 1varepsilon cdot
  arXiv  Detail & Related papers  (2022-07-28T08:10:43Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices. We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
  arXiv  Detail & Related papers  (2020-11-21T01:33:15Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  We consider the question of learning $Q$-function in a sample efficient manner for reinforcement learning with continuous state and action spaces. We develop a simple, iterative learning algorithm that finds $epsilon$-Schmidt $Q$-function with sample complexity of $widetildeO(frac1epsilonmax(d1), d_2)+2)$ when the optimal $Q$-function has low rank $r$ and the factor $$ is below a certain threshold.
  arXiv  Detail & Related papers  (2020-06-11T00:55:35Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.