Abstract:

We consider the predictive problem of supervised ranking, where the task is to rank sets of candidate items returned in
response to queries. Although there exist statistical procedures that come with guarantees of consistency in this
setting, these procedures require that individuals provide a complete ranking of all items, which is rarely feasible in
practice. Instead, individuals routinely provide partial preference information, such as pairwise comparisons of items,
and more practical approaches to ranking have aimed at modeling this partial preference data directly. As we show,
however, such an approach has serious theoretical shortcomings. Indeed, we demonstrate that many commonly used surrogate losses for pairwise comparison data do not yield consistency; surprisingly, we show inconsistency even in low-noise settings. With these negative results as motivation, we present a new approach to supervised ranking based on aggregation of partial preferences and develop U-statistic-based empirical risk minimization procedures. We present an asymptotic analysis of these new procedures, showing that they yield consistency results that parallel those available for
classification. We complement our theoretical results with an experiment studying the new procedures in a large-scale
web-ranking task.

Joint work with Lester Mackey and Michael Jordan. 

Bio: John Duchi is a fifth-year PhD student in computer science at UC Berkeley, jointly supervised by Michael
Jordan and Martin Wainwright. John has also worked for several years on the research team at Google Research
and received the Bachelor's and Master's degrees from Stanford University. He is interested in large scale
statistical modeling and optimization, and has done work in distributed and stochastic optimization, ranking
algorithms, and graphical models.