Interactive learning framework for various settings.
problem Various interactive learning settings.
method Adapted active learning algorithm for interactive structure discovery.
result Noise-tolerant algorithm with favorable query complexity.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,932 papers · 148 categories
Trend · papers per month
48 results for “top-k item identification”
Optimizes identifying top-k items from comparisons with minimal comparisons.
problem Finding the top-k items from pairwise comparisons with a fixed error rate.
method Developed an asymptotically optimal algorithm using primal-dual procedure and adaptive comparison allocation.
result Proves the algorithm is asymptotically optimal for top-k identification.
This paper explores the preference-based top- rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top- ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model…
We study the top- ranking problem where the goal is to recover the set of top- ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populat…
This paper is concerned with the problem of top- ranking from pairwise comparisons. Given a collection of items and a few pairwise comparisons across them, one wishes to identify the set of items that receive the highest ranks. To tackle this problem, we adopt the logistic parametric model --- the Bradley-Te…
We explore the top- rank aggregation problem. Suppose a collection of items is compared in pairs repeatedly, and we aim to recover a consistent ordering that focuses on the top- ranked items based on partially revealed preference information. We investigate the Bradley-Terry-Luce model in which one ranks items ac…
Proposes a method to infer ranking properties and top-K rankings with uncertainty quantification.
problem General uncertainty quantification in ranking problems.
method Combinatorial inference framework for the Bradley-Terry-Luce model, generalized to multiple testing.
result Minimax optimal method for inferring top-K rankings with FDR control.
A common problem in machine learning is to rank a set of n items based on pairwise comparisons. Here ranking refers to partitioning the items into sets of pre-specified sizes according to their scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defi…
Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top items from noisy pairwise comparisons. In our setting, we are non-actively given pairwise comparisons between each pair of items, where each comparison has noi…
Paper characterizes minimax regret rates for online ranking with top-k feedback.
problem Analyzing online ranking with partial feedback.
method Developed techniques from partial monitoring to characterize minimax regret rates.
result Full characterization of minimax regret rates for Precision@n.
Given an incomplete ratings data over a set of users and items, the preference completion problem aims to estimate a personalized total preference order over a subset of the items. In practical settings, a ranked list of top- items from the estimated preference order is recommended to the end user in the decreasing …
New methods provide stable ranking without assumptions on data distributions.
problem Stability issues in ranking problems with noisy data.
method Developed a stability framework and two ranking operators.
result Guaranteed stability without assumptions on data distributions.
We study the active learning problem of top- ranking from multi-wise comparisons under the popular multinomial logit model. Our goal is to identify the top- items with high probability by adaptively querying sets for comparisons and observing the noisy output of the most preferred item from each comparison. To ac…
We consider sequential or active ranking of a set of n items based on noisy pairwise comparisons. Items are ranked according to the probability that a given item beats a randomly chosen item, and ranking refers to partitioning the items into sets of pre-specified sizes according to their scores. This notion of ranking …
Online boosting for multilabel ranking with limited feedback.
problem Multilabel ranking with top-k feedback.
method Surrogate loss function and unbiased estimator for weak learners.
result Adapted full information multilabel ranking algorithms to top-k feedback setting with theoretical and experimental support.
We consider data in the form of pairwise comparisons of n items, with the goal of precisely identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We analyze the Copeland counting algorithm that ranks the items in order of the number of pairwise comparisons won, an…
JoVA combines two VAEs to learn user and item representations for better recommendation.
problem Collaborative filtering with implicit feedback.
method Joint Variational Autoencoders (JoVA) with a hinge-based pairwise loss function (JoVA-Hinge).
result JoVA-Hinge outperforms state-of-the-art methods in top-k recommendation.
This paper explores the adaptive (active) PAC (probably approximately correct) top- ranking (i.e., top- item selection) and total ranking problems from -wise () comparisons under the multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output of the most favored …
Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
Efficiently calculates PL model likelihood for partitioned preference data.
problem Computational infeasibility of calculating PL model likelihood for partitioned preference data.
method Random utility model formulation and efficient numerical integration approach.
result Proposed method outperforms existing LTR baselines and scales to real-world tasks.
Paper extends top-k Mallows model for better user preference analysis.
problem Capturing real-world user preferences focusing on a limited set of items.
method Generalized top-k Mallows model, novel sampling scheme, efficient algorithm, active learning.
result New tools for analysis and prediction in decision-making scenarios.
Industrial recommender systems deal with extremely large action spaces -- many millions of items to recommend. Moreover, they need to serve billions of users, who are unique at any point in time, making a complex user state space. Luckily, huge quantities of logged implicit feedback (e.g., user clicks, dwell time) are …
We consider PAC-learning a good item from -subsetwise feedback information sampled from a Plackett-Luce probability model, with instance-dependent sample complexity performance. In the setting where subsets of a fixed size can be tested and top-ranked feedback is made available to the learner, we give an algorithm w…
Zero-Shot Heterogeneous Transfer Learning from Recommender Systems to Cold-Start Search Retrievalcs.LG
Improves search performance by transferring knowledge from recommender system.
problem Cold start and feedback loop problems in search retrieval.
method Zero-Shot Heterogeneous Transfer Learning framework.
result Significant improvements in relevance and user interactions over production system.
Paper proposes PSIPS for identifying Pareto set with correlated objectives.
problem Identifying the best answer among items with multiple conflicting metrics.
method Posterior sampling in stopping and sampling rules for structure and correlation.
result PSIPS is asymptotically optimal and demonstrates good empirical performance.
Simple algorithms identify best items or full rankings from choice-based feedback.
problem Learning to identify the best item or full ranking from choice-based feedback.
method Nested Elimination (NE) and Nested Partition (NP) algorithms.
result NE is worst-case asymptotically optimal, NP is optimal up to a constant factor.
New deep learning model for matching sets of items, preserving exchangeability.
problem Matching two different sets of items while preserving exchangeability.
method Exchangeable deep neural networks architecture and efficient training framework.
result Significant improvements in fashion set recommendation and group re-identification.
New approaches estimate recommendation metrics using sampling.
problem Understanding and resolving the use of sampling for recommendation evaluation.
method MLE and ME principles for empirical rank distribution recovery.
result Advantages of new approaches for top-k metrics estimation.
Paper analyzes trade-offs in top-k classification accuracies and proposes a new loss function.
problem CE loss does not always optimize top-k prediction, especially with complex data.
method Introduces a novel top-k transition loss to improve top-k accuracy.
result Our loss function improves top-k accuracy, especially for k > 10.
Top-k Multiclass SVMstat.ML
Class ambiguity is typical in image classification problems with a large number of classes. When classes are difficult to discriminate, it makes sense to allow k guesses and evaluate classifiers based on the top-k error instead of the standard zero-one loss. We propose top-k multiclass SVM as a direct method to optimiz…
The top- error is often employed to evaluate performance for challenging classification tasks in computer vision as it is designed to compensate for ambiguity in ground truth labels. This practical success motivates our theoretical analysis of consistent top- classification. Surprisingly, it is not rigorously und…
The study analyzes group testing algorithms for identifying defective items with high confidence.
problem Identifying defective items from a population using group testing with high confidence.
method Formulated as a function learning problem using the PAC framework, analyzed three algorithms: column matching, combinatorial basis pursuit, and definite defectives.
result Derived bounds on the number of tests needed for approximate set identification, comparing with existing bounds and simulating performance.
New method reduces variance in estimating PL model expectations.
problem High variance in Monte Carlo estimates of PL model expectations.
method Combining Gumbel top-k trick with quasi-Monte Carlo sampling.
result More sample-efficient estimators of PL model expectations.
Paper introduces a new loss function for deep imbalanced classification.
problem Class ambiguity and imbalance in large datasets.
method Stochastic top-K hinge loss based on smoothed top-K operator.
result Our loss function significantly outperforms other baseline loss functions in imbalanced datasets.
Smoothed top-k operator improves model training efficiency.
problem Discontinuous top-k operation makes models untrainable end-to-end.
method SOFT top-k operator approximates top-k as EOT solution.
result Improved performance in k-nearest neighbors and beam search.
Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergencecs.LG
Proposes efficient stochastic algorithms for optimizing NDCG with provable convergence guarantees.
problem Efficient and provable stochastic methods for maximizing NDCG in deep learning models.
method Formulates novel compositional optimization problems, develops efficient stochastic algorithms with provable convergence guarantees, and proposes practical strategies.
result Stochastic algorithms with provable convergence guarantees for optimizing NDCG and its top- variant.
Paper introduces efficient top-k selection with differential privacy.
problem Efficiently selecting top-k elements with differential privacy.
method Oneshot Laplace mechanism, generalizing Report Noisy Max.
result Noise level of O(sqrt(k)/eps) for approximate differential privacy.
In order to push the performance on realistic computer vision tasks, the number of classes in modern benchmark datasets has significantly increased in recent years. This increase in the number of classes comes along with increased ambiguity between the class labels, raising the question if top-1 error is the right perf…
Unified model for prediction and deferral selects top-k entities efficiently.
problem Efficiently selecting top-k entities for deferral in machine learning.
method One-stage Top- Learning-to-Defer framework with a convex surrogate.
result Unified model achieves superior accuracy-cost trade-offs.
Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classificationcs.CV
Top-k error is currently a popular performance measure on large scale image classification benchmarks such as ImageNet and Places. Despite its wide acceptance, our understanding of this metric is limited as most of the previous research is focused on its special case, the top-1 error. In this work, we explore two direc…
Paper introduces MPES for top-k ranking BO with preferential observations.
problem Handling top-k ranking and tie/indifference observations in Bayesian optimization.
method Designs a surrogate model and introduces MPES acquisition function.
result MPES outperforms existing acquisition functions in handling preferential observations.
Study improves top-k set prediction with low cardinality.
problem Improving top-k set prediction accuracy with low cardinality.
method Introduces new target loss function and surrogate losses.
result Demonstrates effectiveness of cardinality-aware algorithms.
Top-k sparsification reduces deep learning communication costs.
problem Reducing communication overhead in distributed deep learning.
method Extensive experiments and theoretical analysis of Top-k sparsification.
result A tighter bound for Top-k operator derived, improving scaling efficiency.
Proposes differentiable and sparse top-k operators for neural networks.
problem Discontinuity of top-k operator makes it unsuitable for end-to-end training with backpropagation.
method Formulates top-k as a linear program over permutahedron, introduces p-norm regularization, and uses isotonic optimization.
result Successfully applied to neural network pruning, fine-tuning, and routing.
Work on making classifiers robust against adversarial attacks for top-k predictions.
problem Vulnerability of classifiers to adversarial perturbations, especially for top-k predictions.
method Randomized smoothing to turn any classifier into a robust one, using Gaussian noise.
result Derives a tight robustness in ℓ2 norm for top-k predictions, achieving 62.8% certified top-5 accuracy on ImageNet.
This paper compares average-K and top-K classification methods under ambiguity.
problem Choosing a single label in ambiguous cases leads to low precision.
method Formally characterizes ambiguity profiles and compares average-K and top-K classification methods.
result Average-K can achieve lower error rates than top-K in some ambiguous cases.
Top-two algorithm improved for best-k-arm selection.
problem Best-k-arm identification in multi-armed bandits.
method Information-directed selection based on dual variables.
result Top-two Thompson sampling with IDS is asymptotically optimal.
Proposes LML layer for multi-label predictions with k labels.
problem Efficient multi-label prediction with limited labels.
method Probabilistic multi-label modeling, efficient forward and backward passes.
result Improves top-k recall and accuracy in multi-label tasks.