Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality

• URL: http://arxiv.org/abs/2304.06821v1
• Date: Thu, 13 Apr 2023 21:14:30 GMT
• Title: Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality
• Authors: Yanxi Chen
• Abstract summary: This technical report studies the problem of ranking from pairwise comparisons in the classical Bradley-Terry-Luce (BTL) model. We show that, with sufficiently many samples, maximum likelihood estimation (MLE) achieves an entrywise estimation error matching the Cram'er-Rao lower bound. We explore divide-and-conquer algorithms that can provably achieve similar guarantees even in the regime with the sparsest samples.
• Score: 3.1219977244201056
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This technical report studies the problem of ranking from pairwise comparisons in the classical Bradley-Terry-Luce (BTL) model, with a focus on score estimation. For general graphs, we show that, with sufficiently many samples, maximum likelihood estimation (MLE) achieves an entrywise estimation error matching the Cram\'er-Rao lower bound, which can be stated in terms of effective resistances; the key to our analysis is a connection between statistical estimation and iterative optimization by preconditioned gradient descent. We are also particularly interested in graphs with locality, where only nearby items can be connected by edges; our analysis identifies conditions under which locality does not hurt, i.e. comparing the scores between a pair of items that are far apart in the graph is nearly as easy as comparing a pair of nearby items. We further explore divide-and-conquer algorithms that can provably achieve similar guarantees even in the regime with the sparsest samples, while enjoying certain computational advantages. Numerical results validate our theory and confirm the efficacy of the proposed algorithms.

Related papers

• Spectral Ranking Inferences based on General Multiway Comparisons [7.222667862159246]
  We show that a two-step spectral method can achieve the same vanilla efficiency as the Maximum Likelihood Estor. It is noteworthy that this is the first time effective two-sample rank testing methods have been proposed.
  arXiv  Detail & Related papers  (2023-08-05T16:31:32Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
  We derive novel, general upper bounds on the $ell_infty$ estimation error of the Bradley-Terry-Luce model. We demonstrate that the derived bounds perform well and in some cases are sharper compared to known results.
  arXiv  Detail & Related papers  (2021-10-20T23:46:35Z)
• Task Affinity with Maximum Bipartite Matching in Few-Shot Learning [28.5184196829547]
  We propose an asymmetric affinity score for representing the complexity of utilizing the knowledge of one task for learning another one. In particular, using this score, we find relevant training data labels to the test data and leverage the discovered relevant data for episodically fine-tuning a few-shot model.
  arXiv  Detail & Related papers  (2021-10-05T23:15:55Z)
• Optimal detection of the feature matching map in presence of noise and outliers [0.0]
  We consider the problem of finding the matching map between two sets of $d$ dimensional vectors from noisy observations. The matching map is then an injection, which can be consistently estimated only if the vectors of the second set are well separated.
  arXiv  Detail & Related papers  (2021-06-13T17:08:29Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Active Sampling for Pairwise Comparisons via Approximate Message Passing and Information Gain Maximization [5.771869590520189]
  We propose ASAP, an active sampling algorithm based on approximate message passing and expected information gain. We show that ASAP offers the highest accuracy of inferred scores compared to the existing methods.
  arXiv  Detail & Related papers  (2020-04-12T20:48:10Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

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.