John Duchi and Lester Mackey and Michael Jordan

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2010-56

May 9, 2010

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-56.pdf

We present a theoretical analysis of supervised ranking, providing necessary and sufficient conditions for the asymptotic consistency of algorithms based on minimizing a surrogate loss function. We show that many commonly used surrogate losses are inconsistent; surprisingly, we show inconsistency even in low-noise settings. We present a new value-regularized linear loss, establish its consistency under reasonable assumptions on noise, and show that it outperforms conventional ranking losses in a collaborative filtering experiment.

---

BibTeX citation:

@techreport{Duchi:EECS-2010-56,
    Author= {Duchi, John and Mackey, Lester and Jordan, Michael},
    Title= {On the Consistency of Ranking Algorithms},
    Year= {2010},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-56.html},
    Number= {UCB/EECS-2010-56},
    Abstract= {We present a theoretical analysis of supervised ranking, providing necessary and sufficient conditions for the asymptotic consistency of algorithms based on minimizing a surrogate loss function.  We show that many commonly used surrogate losses are inconsistent; surprisingly, we show inconsistency even in low-noise settings.  We present a new value-regularized linear loss, establish its consistency under reasonable assumptions on noise, and show that it outperforms conventional ranking losses in a collaborative filtering experiment.},
}

EndNote citation:

%0 Report
%A Duchi, John 
%A Mackey, Lester 
%A Jordan, Michael 
%T On the Consistency of Ranking Algorithms
%I EECS Department, University of California, Berkeley
%D 2010
%8 May 9
%@ UCB/EECS-2010-56
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-56.html
%F Duchi:EECS-2010-56