Online Ranking: Discrete Choice, Spearman Correlation and Other Feedback
Given a set $V$ of $n$ objects, an online ranking system outputs at each time step a full ranking of the set, observes a feedback of some form and suffers a loss. We study the setting in which the (adversarial) feedback is an element in $V$, and the loss is the position (0th, 1st, 2nd...) of the item in the outputted ranking. More generally, we study a setting in which the feedback is a subset $U$ of at most $k$ elements in $V$, and the loss is the sum of the positions of those elements. We present an algorithm of expected regret $O(n^{3/2}\sqrt{Tk})$ over a time horizon of $T$ steps with respect to the best single ranking in hindsight. This improves previous algorithms and analyses either by a factor of either $\Omega(\sqrt{k})$, a factor of $\Omega(\sqrt{\log n})$ or by improving running time from quadratic to $O(n\log n)$ per round. We also prove a matching lower bound. Our techniques also imply an improved regret bound for online rank aggregation over the Spearman correlation measure, and to other more complex ranking loss functions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Question Difficulty Ranking for Multiple-Choice Reading Comprehension
Multiple-choice (MC) tests are an efficient method to assess English learners. It is useful for test creators to rank candidate MC questions by difficulty during exam curation. Typically, the difficulty is determined by …
Multiple-choiceReading ComprehensionStandardization of Weighted Ranking Correlation Coefficients
A relevant problem in statistics is defining the correlation of two rankings of a list of items. Kendall's tau and Spearman's rho are two well established correlation coefficients, characterized by a symmetric form that …
Investigating Non-Transitivity in LLM-as-a-Judge
Automatic evaluation methods based on large language models (LLMs) are emerging as the standard tool for assessing the instruction-following abilities of LLM-based agents. The most common method in this paradigm, pairwis…
ChatbotComputational EfficiencyInstruction FollowingMultivariate Spearman's rho for aggregating ranks using copulas
We study the problem of rank aggregation: given a set of ranked lists, we want to form a consensus ranking. Furthermore, we consider the case of extreme lists: i.e., only the rank of the best or worst elements are known.…
Learning-To-RankSequential estimation of Spearman rank correlation using Hermite series estimators
In this article we describe a new Hermite series based sequential estimator for the Spearman rank correlation coefficient and provide algorithms applicable in both the stationary and non-stationary settings. To treat the…
ClusteringData Summarizationfeature selectionSequential Correlation Estimation