Lagrangian Inference for Ranking Problems

• URL: http://arxiv.org/abs/2110.00151v1
• Date: Fri, 1 Oct 2021 01:16:25 GMT
• Title: Lagrangian Inference for Ranking Problems
• Authors: Yue Liu, Ethan X. Fang, Junwei Lu
• Abstract summary: We consider the widely adopted Bradley-Terry-Luce (BTL) model, where each item is assigned a positive preference score that determines the Bernoulli distributions of pairwise comparisons' outcomes. Our proposed method aims to infer general ranking properties of the BTL model. We generalize our framework to multiple testing problems where we control the false discovery rate (FDR) and apply the method to infer the top-$K$ ranked items.
• Score: 18.70913621061314
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel combinatorial inference framework to conduct general uncertainty quantification in ranking problems. We consider the widely adopted Bradley-Terry-Luce (BTL) model, where each item is assigned a positive preference score that determines the Bernoulli distributions of pairwise comparisons' outcomes. Our proposed method aims to infer general ranking properties of the BTL model. The general ranking properties include the "local" properties such as if an item is preferred over another and the "global" properties such as if an item is among the top $K$-ranked items. We further generalize our inferential framework to multiple testing problems where we control the false discovery rate (FDR), and apply the method to infer the top-$K$ ranked items. We also derive the information-theoretic lower bound to justify the minimax optimality of the proposed method. We conduct extensive numerical studies using both synthetic and real datasets to back up our theory.

Related papers

• Reward Modeling with Ordinal Feedback: Wisdom of the Crowd [9.034189257088762]
  Learning a reward model (RM) from human preferences has been an important component in aligning large language models. We propose a framework for learning RMs under ordinal feedback. We prove the statistical benefits of ordinal feedback in terms of reducing the Rademacher complexity.
  arXiv  Detail & Related papers  (2024-11-19T20:17:04Z)
• Reward-Augmented Data Enhances Direct Preference Alignment of LLMs [56.24431208419858]
  We introduce reward-conditioned Large Language Models (LLMs) that learn from the entire spectrum of response quality within the dataset. We propose an effective yet simple data relabeling method that conditions the preference pairs on quality scores to construct a reward-augmented dataset.
  arXiv  Detail & Related papers  (2024-10-10T16:01:51Z)
• Covariate Assisted Entity Ranking with Sparse Intrinsic Scores [3.2839905453386162]
  We introduce novel model identification conditions and examine the regularized penalized Maximum Likelihood Estimator statistical rates. We also apply our method to the goodness-of-fit test for models with no latent intrinsic scores.
  arXiv  Detail & Related papers  (2024-07-09T19:58:54Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Combinatorial Inference on the Optimal Assortment in Multinomial Logit Models [14.689897325621672]
  Decision-makers may only be interested in testing whether a given property holds true for the optimal assortment. This paper proposes a novel inferential framework for testing such properties.
  arXiv  Detail & Related papers  (2023-01-28T17:09:50Z)
• Uncertainty Quantification of MLE for Entity Ranking with Covariates [3.2839905453386162]
  This paper concerns with statistical estimation and inference for the ranking problems based on pairwise comparisons. We propose a novel model, Co-Assisted Ranking Estimation (CARE) model, that extends the well-known Bradley-Terry-Luce (BTL) model. We derive the maximum likelihood estimator of $alpha_i*_i=1n$ and $beta*$ under a sparse comparison graph. We validate our theoretical results through large-scale numerical studies and an application to the mutual fund stock holding dataset.
  arXiv  Detail & Related papers  (2022-12-20T02:28:27Z)
• Ranking Inferences Based on the Top Choice of Multiway Comparisons [2.468314282946207]
  This paper considers ranking inference of $n$ items based on the observed data on the top choice among $M$ randomly selected items at each trial. It is a useful modification of the Plackett-Luce model for $M$-way ranking with only the top choice observed and is an extension of the celebrated Bradley-Terry-Luce model that corresponds to $M=2$.
  arXiv  Detail & Related papers  (2022-11-22T02:34:52Z)
• Relational Proxies: Emergent Relationships as Fine-Grained Discriminators [52.17542855760418]
  We propose a novel approach that leverages information between the global and local part of an object for encoding its label. We design Proxies based on our theoretical findings and evaluate it on seven challenging fine-grained benchmark datasets. We also experimentally validate our theory and obtain consistent results across multiple benchmarks.
  arXiv  Detail & Related papers  (2022-10-05T11:08:04Z)
• Recommendation Systems with Distribution-Free Reliability Guarantees [83.80644194980042]
  We show how to return a set of items rigorously guaranteed to contain mostly good items. Our procedure endows any ranking model with rigorous finite-sample control of the false discovery rate. We evaluate our methods on the Yahoo! Learning to Rank and MSMarco datasets.
  arXiv  Detail & Related papers  (2022-07-04T17:49:25Z)
• 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)
• Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking Fairness and Algorithm Utility [54.179859639868646]
  Bipartite ranking aims to learn a scoring function that ranks positive individuals higher than negative ones from labeled data. There have been rising concerns on whether the learned scoring function can cause systematic disparity across different protected groups. We propose a model post-processing framework for balancing them in the bipartite ranking scenario.
  arXiv  Detail & Related papers  (2020-06-15T10:08:39Z)

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.