MEMR: A Margin Equipped Monotone Retargeting Framework for Ranking

Abstract

We bring to bear the tools of convexity, mar-gins and the newly proposed technique of monotone retargeting upon the task of learn-ing permutations from examples. This leads to novel and efficient algorithms with guaran-teed prediction performance in the online set-ting and on global optimality and the rate of convergence in the batch setting. Monotone retargeting efficiently optimizes over all pos-sible monotone transformations as well as the finite dimensional parameters of the model. As a result we obtain an effective algorithm to learn transitive relationships over items. It captures the inherent combinatorial char-acteristics of the output space yet it has a computational burden not much more than that of a generalized linear model. 1