Learning to Rank With Bregman Divergences and Monotone Retargeting

Sreangsu Acharyya, Oluwasanmi Koyejo, Joydeep Ghosh
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:13-22, 2012.

Abstract

This paper introduces a novel approach for learning to rank (LETOR) based on the notion of monotone retargeting. It involves minimizing a divergence between all monotonic increasing transformations of the training scores and a parameterized prediction function. The minimization is both over the transformations as well as over the parameters. It is applied to Bregman divergences, a large class of "distance like" functions that were recently shown to be the unique class that is statistically consistent with the normalized discounted gain (NDCG) criterion [19]. The algorithm uses alternating projection style updates, in which one set of simultaneous projections can be computed independent of the Bregman divergence and the other reduces to parameter estimation of a generalized linear model. This results in easily implemented, efficiently parallelizable algorithm for the LETOR task that enjoys global optimum guarantees under mild conditions. We present empirical results on benchmark datasets showing that this approach can outperform the state of the art NDCG consistent techniques.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-acharyya12a, title = {Learning to Rank With Bregman Divergences and Monotone Retargeting}, author = {Acharyya, Sreangsu and Koyejo, Oluwasanmi and Ghosh, Joydeep}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {13--22}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/acharyya12a/acharyya12a.pdf}, url = {https://proceedings.mlr.press/r10/acharyya12a.html}, abstract = {This paper introduces a novel approach for learning to rank (LETOR) based on the notion of monotone retargeting. It involves minimizing a divergence between all monotonic increasing transformations of the training scores and a parameterized prediction function. The minimization is both over the transformations as well as over the parameters. It is applied to Bregman divergences, a large class of "distance like" functions that were recently shown to be the unique class that is statistically consistent with the normalized discounted gain (NDCG) criterion [19]. The algorithm uses alternating projection style updates, in which one set of simultaneous projections can be computed independent of the Bregman divergence and the other reduces to parameter estimation of a generalized linear model. This results in easily implemented, efficiently parallelizable algorithm for the LETOR task that enjoys global optimum guarantees under mild conditions. We present empirical results on benchmark datasets showing that this approach can outperform the state of the art NDCG consistent techniques.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Learning to Rank With Bregman Divergences and Monotone Retargeting %A Sreangsu Acharyya %A Oluwasanmi Koyejo %A Joydeep Ghosh %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-acharyya12a %I PMLR %P 13--22 %U https://proceedings.mlr.press/r10/acharyya12a.html %V R10 %X This paper introduces a novel approach for learning to rank (LETOR) based on the notion of monotone retargeting. It involves minimizing a divergence between all monotonic increasing transformations of the training scores and a parameterized prediction function. The minimization is both over the transformations as well as over the parameters. It is applied to Bregman divergences, a large class of "distance like" functions that were recently shown to be the unique class that is statistically consistent with the normalized discounted gain (NDCG) criterion [19]. The algorithm uses alternating projection style updates, in which one set of simultaneous projections can be computed independent of the Bregman divergence and the other reduces to parameter estimation of a generalized linear model. This results in easily implemented, efficiently parallelizable algorithm for the LETOR task that enjoys global optimum guarantees under mild conditions. We present empirical results on benchmark datasets showing that this approach can outperform the state of the art NDCG consistent techniques. %Z Reissued by PMLR on 04 October 2026.
APA
Acharyya, S., Koyejo, O. & Ghosh, J.. (2012). Learning to Rank With Bregman Divergences and Monotone Retargeting. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:13-22 Available from https://proceedings.mlr.press/r10/acharyya12a.html. Reissued by PMLR on 04 October 2026.

Related Material