Direct Learning to Rank and Rerank.

Learning-to-rank techniques have proven to be extremely useful forprioritization problems, where we rank items in order of their estimatedprobabilities, and dedicate our limited resources to the top-ranked items. Thiswork exposes a serious problem with the state of learning-to-rank algorithms,which is that they are based on convex proxies that lead to poorapproximations. We then discuss the possibility of "exact" reranking algorithmsbased on mathematical programming. We prove that a relaxed version of the"exact" problem has the same optimal solution, and provide an empiricalanalysis.