The Sample Complexity of Best-$k$ Items Selection from Pairwise Comparisons

• URL: http://arxiv.org/abs/2007.03133v2
• Date: Thu, 29 Jul 2021 19:41:20 GMT
• Title: The Sample Complexity of Best-$k$ Items Selection from Pairwise Comparisons
• Authors: Wenbo Ren, Jia Liu, Ness B. Shroff
• Abstract summary: We study the sample complexity (aka number of comparisons) bounds for the active best-$k$ items selection from pairwise comparisons. At any time, the learner can adaptively choose a pair of items to compare according to past observations. We propose two algorithms based on our PAC best items selection algorithms.
• Score: 33.66975831989357
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the sample complexity (aka number of comparisons) bounds for the active best-$k$ items selection from pairwise comparisons. From a given set of items, the learner can make pairwise comparisons on every pair of items, and each comparison returns an independent noisy result about the preferred item. At any time, the learner can adaptively choose a pair of items to compare according to past observations (i.e., active learning). The learner's goal is to find the (approximately) best-$k$ items with a given confidence, while trying to use as few comparisons as possible. In this paper, we study two problems: (i) finding the probably approximately correct (PAC) best-$k$ items and (ii) finding the exact best-$k$ items, both under strong stochastic transitivity and stochastic triangle inequality. For PAC best-$k$ items selection, we first show a lower bound and then propose an algorithm whose sample complexity upper bound matches the lower bound up to a constant factor. For the exact best-$k$ items selection, we first prove a worst-instance lower bound. We then propose two algorithms based on our PAC best items selection algorithms: one works for $k=1$ and is sample complexity optimal up to a loglog factor, and the other works for all values of $k$ and is sample complexity optimal up to a log factor.

Related papers

• Active Preference Learning for Ordering Items In- and Out-of-sample [7.0774164818430565]
  actively sampling item pairs can reduce the number of annotations necessary for learning an accurate ordering. Many algorithms ignore shared structure between items. It is also common to disregard how noise in comparisons varies between item pairs.
  arXiv  Detail & Related papers  (2024-05-05T21:44:03Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  We consider the sign-function-based comparison feedback model and analyze the convergence rates with batched and multiway comparisons. Our work is the first to study the problem of convex optimization with multiway preferences and analyze the optimal convergence rates.
  arXiv  Detail & Related papers  (2023-12-19T01:52:13Z)
• 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)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  We investigate the sample complexity of learning the optimal arm for multi-task bandit problems. Arms consist of two components: one that is shared across tasks (that we call representation) and one that is task-specific (that we call predictor) We devise an algorithm OSRL-SC whose sample complexity approaches the lower bound, and scales at most as $H(Glog(delta_G)+ Xlog(delta_H))$, with $X,G,H$ being, respectively, the number of tasks, representations and predictors.
  arXiv  Detail & Related papers  (2022-11-28T08:40:12Z)
• 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)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  In rank aggregation problems, users exhibit various accuracy levels when comparing pairs of items. We propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons. We prove that our algorithm can return the true ranking of items with high probability.
  arXiv  Detail & Related papers  (2021-10-08T13:51:55Z)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  Given a kernel function and a subset size $k$, our goal is to sample $k$ out of $n$ items with probability proportional to the determinant of the kernel matrix induced by the subset (a.k.a. $k$-DPP) Existing $k$-DPP sampling algorithms require an expensive preprocessing step which involves multiple passes over all $n$ items, making it infeasible for large datasets. We develop an algorithm which adaptively builds a sufficiently large uniform sample of data that is then used to efficiently generate a smaller set of $k$ items.
  arXiv  Detail & Related papers  (2020-06-30T16:40:44Z)
• 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)
• Best-item Learning in Random Utility Models with Subset Choices [40.17224226373741]
  We consider the problem of PAC learning the most valuable item from a pool of $n$ items using sequential, adaptively chosen plays of subsets of $k$ items. We identify a new property of such a RUM, termed the minimum advantage, that helps in characterizing the complexity of separating pairs of items. We give a learning algorithm for general RUMs, based on pairwise relative counts of items and hierarchical elimination, along with a new PAC sample complexity guarantee.
  arXiv  Detail & Related papers  (2020-02-19T03:57:16Z)

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.