Ranking vs Classification

When I began to blog, I feared that I will not have time to read and understand a lot of others' papers in any detail to have a pipeline of general results of interest to blog about with technical content, and that I would eventually end up talking about my own results disproportionately often. I continue to have this fear, and am glad when I get to blog about others' work.

There is an interesting recent result due to Ailon and Mohri. The authors reduce the problem of learning a ranking among objects to that of pairwise classification. The reduction is randomized, takes O(nlog n) calls, and the quality (formalized as regret) is no worse. The reduction is like quicksort and connotes the work of Ailon, Charikar and Newman for minimum feedback arcset for tournaments. This result improves earlier work that gave up a factor of 2 in quality and used O(n^2) pairwise classifications. The result is an example of interesting, foundational theory, and more reductions of this sort in machine learning will be of great interest.