EGRank: An exponentiated gradient algorithm for sparse learning-to-rank

This paper focuses on the problem of sparse learning-to-rank, where the learned ranking models usually have very few non-zero coefficients. An exponential gradient algorithm is proposed to learn sparse models for learning-to-rank, which can be formulated as a convex optimization problem with the l(1) constraint. Our proposed algorithm has a competitive theoretical worst-case performance guarantee, that is, we can obtain an epsilon-accurate solution after O(1/epsilon) iterations. An early stopping criterion based on Fenchel duality is proposed to make the algorithm be more efficient in practice. Extensive experiments are conducted on some benchmark datasets. The results demonstrate that a sparse ranking model can significantly improve the accuracy of ranking prediction compared to dense models, and the proposed algorithm shows stable and competitive performance compared to several state-of-the-art baseline algorithms. (C) 2018 Elsevier Inc. All rights reserved.