On Top-$k$ Selection from $m$-wise Partial Rankings via Borda Counting
- URL: http://arxiv.org/abs/2204.05742v1
- Date: Mon, 11 Apr 2022 16:31:37 GMT
- Title: On Top-$k$ Selection from $m$-wise Partial Rankings via Borda Counting
- Authors: Wenjing Chen, Ruida Zhou, Chao Tian, Cong Shen
- Abstract summary: We analyze the performance of the Borda counting algorithm in a non-parametric model.
We show that if $Delta_k$ is greater than certain value, then the top-$k$ items selected by the algorithm is almost surely accurate.
- Score: 23.290889341552898
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the performance of the Borda counting algorithm in a
non-parametric model. The algorithm needs to utilize probabilistic rankings of
the items within $m$-sized subsets to accurately determine which items are the
overall top-$k$ items in a total of $n$ items. The Borda counting algorithm
simply counts the cumulative scores for each item from these partial ranking
observations. This generalizes a previous work of a similar nature by Shah et
al. using probabilistic pairwise comparison data. The performance of the Borda
counting algorithm critically depends on the associated score separation
$\Delta_k$ between the $k$-th item and the $(k+1)$-th item. Specifically, we
show that if $\Delta_k$ is greater than certain value, then the top-$k$ items
selected by the algorithm is asymptotically accurate almost surely; if
$\Delta_k$ is below certain value, then the result will be inaccurate with a
constant probability. In the special case of $m=2$, i.e., pairwise comparison,
the resultant bound is tighter than that given by Shah et al., leading to a
reduced gap between the error probability upper and lower bounds. These results
are further extended to the approximate top-$k$ selection setting. Numerical
experiments demonstrate the effectiveness and accuracy of the Borda counting
algorithm, compared with the spectral MLE-based algorithm, particularly when
the data does not necessarily follow an assumed parametric model.
Related papers
- Top-$K$ ranking with a monotone adversary [19.871049853222132]
We consider the scenario where a comparison graph is randomly generated and the adversary is allowed to add arbitrary edges.
The statistician's goal is then to accurately identify the top-$K$ preferred items based on pairwise comparisons.
The main contribution of this paper is to develop a weighted maximum likelihood estimator (MLE) that achieves near-optimal sample complexity.
arXiv Detail & Related papers (2024-02-12T06:57:34Z) - Sorting with Predictions [1.7042264000899532]
We explore the fundamental problem of sorting through the lens of learning-augmented algorithms.
We design new and simple algorithms using only $O(sum_i log eta_i)$ exact comparisons.
We prove that the comparison complexity is theoretically optimal with respect to the examined error measures.
arXiv Detail & Related papers (2023-11-01T18:00:03Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem.
We show that all used solvers perform very badly on a large majority of the instances.
We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
arXiv Detail & Related papers (2023-06-29T14:57:56Z) - 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) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
We develop a novel, conceptually simpler technique for list-decodable sparse mean estimation.
In particular, for distributions with "certifiably bounded" $t-th moments in $k$-sparse directions, our algorithm achieves error of $(1/alpha)O (1/t)$ with sample complexity $m = (klog(n))O(t)/alpha(mnt)$.
For the special case of Gaussian inliers, our algorithm achieves the optimal error guarantee of $Theta (sqrtlog
arXiv Detail & Related papers (2022-06-10T17:38:18Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset.
We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
arXiv Detail & Related papers (2021-06-16T03:34:14Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints.
For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
arXiv Detail & Related papers (2021-01-20T04:29:18Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
We study the fundamental task of list-decodable mean estimation in high dimensions.
Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset.
A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
arXiv Detail & Related papers (2020-11-19T17:21:37Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized.
This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
arXiv Detail & Related papers (2020-04-16T19:16:38Z) - 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.