Learning-to-Rank at the Speed of Sampling: Plackett-Luce Gradient Estimation With Minimal Computational Complexity

Abstract

Plackett-Luce gradient estimation enables the optimization of stochastic ranking models within feasible time constraints through sampling techniques. Unfortunately, the computational complexity of existing methods does not scale well with the length of the rankings, i.e. the ranking cutoff, nor with the item collection size. In this paper, we introduce the novel PL-Rank-3 algorithm that performs unbiased gradient estimation with a computational complexity comparable to the best sorting algorithms. As a result, our novel learning-to-rank method is applicable in any scenario where standard sorting is feasible in reasonable time. Our experimental results indicate large gains in the time required for optimization, without any loss in performance. For the field, our contribution could potentially allow state-of-the-art learning-to-rank methods to be applied to much larger scales than previously feasible.

arXiv commentSIGIR 2022

References in corpus (1)

• Evaluating Stochastic Rankings with Expected Exposure

Cited by in corpus (6)

• Information Retrieval: Recent Advances and Beyond
• Practical and Robust Safety Guarantees for Advanced Counterfactual Learning to Rank
• Meta Learning to Rank for Sparsely Supervised Queries
• Learning to Rank with Variable Result Presentation Lengths
• Exposure-Based Reinforcement Learning to Rank
• Estimating the Hessian Matrix of Ranking Objectives for Stochastic Learning to Rank with Gradient Boosted Trees