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.
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.
Paper proposes Spectral MLE for reliable top-K ranking from pairwise comparisons.
problem Aggregating preferences to identify top-K ranked items from comparisons.
method Proposes Spectral MLE, a nearly linear-time ranking scheme.
result Spectral MLE achieves perfect top-K item identification with minimal sample complexity.
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.
The paper proposes methods to identify and sample from mixtures of Mallows models for top-k rankings.
problem Identifying and sampling from mixtures of Mallows models for top-k rankings in a heterogeneous population.
method Efficient sampling algorithms and identifiability proofs for both components of the mixture.
result The identifiability and learnability of the Mallows components' parameters in the mixture.
Study top-K ranking with adversarial crowdsourced data, identifying top-K items reliably.
problem Recovering top-K ranked items from partially revealed preferences in an adversarial setting.
method Characterizes minimax limit on sample size for reliable identification, extends to unknown population size.
result Establishes fundamental limits on sample size for top-K recovery in adversarial crowdsourced data.
Optimally ranks top-K items from pairwise comparisons.
problem Aggregating rankings from pairwise comparisons to focus on top-K items.
method Bradley-Terry-Luce model, spectral method.
result Spectral method achieves optimality in sample size for top-K ranking.
The paper addresses calibration in label ranking, a structured prediction task.
problem Calibration in label ranking is not well understood and often poorly calibrated.
method Formalized calibration for label ranking, developed a hierarchy of notions, and empirically evaluated models.
result Popular label ranking models are often poorly calibrated, with differences between sub-ranking and top-k metrics.
New algorithm identifies top-k items with minimal comparisons.
problem Active learning of top-k rankings from noisy comparisons.
method Designs an instance-optimal algorithm without item score info.
result Achieves nearly instance optimal performance with matching lower bound.
New algorithm for top-K ranking with linear time and competitive ratio of sqrt(n).
problem Identifying top K items from noisy pairwise comparisons.
method Linear time algorithm with competitive ratio of sqrt(n) under strong stochastic transitivity model.
result Tight competitive ratio of sqrt(n) for top-K ranking problem.
A new algorithm improves top-k recommendation accuracy by considering item payoffs uncertainty.
problem Suboptimal performance in top-k recommendation rankings due to varying item payoffs. method Proposes a risk-seeking utility function for ranking items based on estimated preference scores.
result Risk-seeking ranking yields the best performance in top-k recommendations. RAMPART ranks top-k features more accurately than existing methods.
problem Accurate ranking of important features in machine learning.
method Adaptive sequential halving strategy combined with ensembling techniques.
result RAMPART achieves the correct top-k ranking with high probability.
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.
Optimizes ranking of top-k players from partial comparison data.
problem Identifying the top-k players from incomplete pairwise comparisons.
method Maximum Likelihood Estimator (MLE) and Spectral Method.
result MLE achieves optimal partial and exact recovery, while Spectral Method is sub-optimal.
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.
The paper studies ranking algorithms from pairwise and listwise comparisons, deriving lower bounds and optimal algorithms.
problem Designing efficient ranking algorithms from pairwise and listwise comparisons.
method Deriving lower bounds and proposing optimal algorithms for top-k and total ranking problems.
result The proposed algorithms match the derived lower bounds and are optimal up to a logarithmic factor.
Spectral method and regularized MLE are both optimal for top-K ranking from pairwise comparisons.
problem Identifying the top-K ranked items from pairwise comparisons.
method Adopting the Bradley-Terry-Luce model, the spectral method, and regularized MLE are used to estimate item scores and rank them.
result The spectral method and regularized MLE are minimax optimal in terms of sample complexity for top-K ranking.
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.
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.
A robust ranking algorithm outperforms previous methods in efficiency and guarantees.
problem Ranking items from pairwise comparisons with robustness and efficiency.
method Copeland counting algorithm for precise ranking or top k items.
result The Copeland algorithm is optimal up to constant factors and robust to various conditions.
Low-rank framework for task-specific LLM ranking from sparse comparisons.
problem Challenges in reliable task-specific ranking of LLMs under sparse, imbalanced comparisons.
method Low-rank modeling of task-by-model ability matrix, max-norm accurate estimator, task-wise top-K recovery guarantees, uncertainty quantification framework.
result Improves sample efficiency and produces tighter, better-calibrated ranking certificates.
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.
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.
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.
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.
New statistical models for predicting ranked preferences from partial orders.
problem Statistical models overlook information in list length.
method Composite and augmented ranking models for joint modeling of partial orders and list lengths.
result Augmented ranking models best predict both length and preferences.
Top-k multiclass SVM optimizes for top-k error in ambiguous image classification.
problem Ambiguity in large-class image classification problems.
method Proposes a generalization of multiclass SVM to optimize for top-k error using a tight convex upper bound and efficient projection onto the top-k simplex.
result Consistent improvements in top-k accuracy compared to baselines on five datasets.
The paper analyzes top-k classification and proposes consistent loss functions.
problem Understanding consistency of top-k classification in challenging tasks.
method Theoretical analysis, defining top-k calibration, proposing new loss functions.
result Proposes a new consistent hinge loss and a top-k calibrated convex loss.
Distributions over rankings are used to model data in various settings such as preference analysis and political elections. The factorial size of the space of rankings, however, typically forces one to make structural assumptions, such as smoothness, sparsity, or probabilistic independence about these underlying distri…
A method for rank verification in multivariate Gaussian data, improving on existing approaches.
problem Determining the top K means in multivariate Gaussian data with any covariance structure. method Selective inference tools to generalize the two-sided difference-of-means test for any K and covariance structure. result The method provides a generalization for rank verification in multivariate Gaussian data with any covariance structure.
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.
The paper tackles learning true rankings from noisy, incomplete data.
problem Learning true rankings from incomplete and noisy data.
method Introduces a selective Mallows model for noisy rankings and derives upper and lower bounds on sample complexity.
result Strong asymptotically tight bounds on sample complexity for learning complete rankings and top-k rankings.
Paper evaluates and introduces new top-k loss functions for improved performance.
problem Increased ambiguity in modern datasets affects performance measures.
method Comparison and evaluation of multiclass methods, introduction of new top-k loss functions.
result Softmax loss performs well across all k, new top-k losses improve performance.
CIT and CIF improve feature selection for downstream prediction.
problem Feature selection bias in machine learning models.
method Conditional inference trees and forests with Bonferroni correction.
result CIF ranks top 3 among 18 regression methods and top 4 among 17 classification methods.
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.
Study explores loss functions for multiclass, top-k, and multilabel classification.
problem Understanding and optimizing loss functions for multiclass, top-k, and multilabel classification.
method In-depth analysis of multiclass top-k methods, optimization of loss functions, and development of efficient training algorithms.
result Softmax and smooth multiclass SVM are competitive in top-k error across all k.
We efficiently find top k eigenvectors in streaming PCA with global convergence.
problem Finding top k eigenvectors in streaming PCA with limited space.
method Developed global convergence for Oja's algorithm and a faster variant Oja++.
result Achieved global convergence rate matching information theoretic lower bound.
New algorithm improves ad targeting for personalized online services.
problem Personalizing online services for improved user experience and revenue.
method Label ranking approach for non-linear, large-scale prediction of user interests.
result The proposed algorithm outperforms existing solutions in rank loss and top-K retrieval.
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-k Learning-to-Defer framework with a convex surrogate. result Unified model achieves superior accuracy-cost trade-offs.
A framework for quantifying uncertainty in feature importance values.
problem Stable interpretation of feature importance values in machine learning models.
method A novel method based on pairwise comparisons of feature importance values to produce confidence intervals for feature ranks.
result The method produces simultaneous confidence intervals for feature ranks, enabling selection of top-k important features.
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-K variant. 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.
Algorithm learns latent simplex from perturbed points in input-sparsity time.
problem Learning a latent k-vertex simplex from noisy data. method Input-sparsity time algorithm using low-rank approximation and adaptive selection.
result Algorithm achieves O(extrmnnz(A)) time complexity, avoiding k⋅extrmnnz(A). 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.
An algorithm finds approximate rankings from pairwise comparisons with near-optimal comparisons.
problem Ranking items based on pairwise comparisons with minimal comparisons.
method Active ranking algorithm that decides comparisons based on confidence intervals.
result The algorithm succeeds in recovering approximate rankings with near-optimal comparisons.