Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
This work addresses the challenge of aggregating pairwise comparison data for applications like ranking or recommendation systems, providing theoretical insights into estimator adaptivity and computational limits.
The paper tackles the problem of estimating pairwise comparison probabilities under strong stochastic transitivity, introducing an adaptivity index to measure estimator performance relative to an oracle. It shows that the proposed Count-Randomize-Least squares estimator achieves an adaptivity index upper bounded by √n, while a regularized least squares estimator achieves poly-logarithmic adaptivity, revealing a √n gap between optimal and computationally achievable performance.
We study methods for aggregating pairwise comparison data in order to estimate outcome probabilities for future comparisons among a collection of n items. Working within a flexible framework that imposes only a form of strong stochastic transitivity (SST), we introduce an adaptivity index defined by the indifference sets of the pairwise comparison probabilities. In addition to measuring the usual worst-case risk of an estimator, this adaptivity index also captures the extent to which the estimator adapts to instance-specific difficulty relative to an oracle estimator. We prove three main results that involve this adaptivity index and different algorithms. First, we propose a three-step estimator termed Count-Randomize-Least squares (CRL), and show that it has adaptivity index upper bounded as $\sqrt{n}$ up to logarithmic factors. We then show that that conditional on the hardness of planted clique, no computationally efficient estimator can achieve an adaptivity index smaller than $\sqrt{n}$. Second, we show that a regularized least squares estimator can achieve a poly-logarithmic adaptivity index, thereby demonstrating a $\sqrt{n}$-gap between optimal and computationally achievable adaptivity. Finally, we prove that the standard least squares estimator, which is known to be optimally adaptive in several closely related problems, fails to adapt in the context of estimating pairwise probabilities.