Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons

• Published in: IEEE transactions on information theory 2019-08, Vol.65 (8), p.4854-4874
• Main Authors: Shah, Nihar B., Balakrishnan, Sivaraman, Wainwright, Martin J.
• Format: Article
• Language: English
• Subjects: Adaptation models; adaptivity; Benchmark testing; Bernoulli probabilities; Data models; Estimation; Ground truth; Indexes; Least squares; negative result for least squares; Optimization; Pairwise comparisons; Stochastic processes; stochastic transitivity
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2019.2903249

We study methods for aggregating pairwise comparison data among a collection of n items with the goal of estimating the outcome probabilities for future comparisons. Working within a flexible model that only imposes a form of strong stochastic transitivity, we introduce an "adaptivity index" which compares the risk of our estimator to that of an oracle, over appropriate sub-models, where the oracle knows the specific sub-model in the ground truth. 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. First, we propose a three-step estimator termed count-randomize-least squares, and show that it has adaptivity index upper bounded by \sqrt {n} up to logarithmic factors. We then show that conditional on the planted clique hypothesis, 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.