Robust reductions from ranking to classification

M.F. Balcan, N. Bansal, A. Beygelzimer, D. Coppersmith, J. Langford, G.B. Sorkin

    Research output: Contribution to journalArticleAcademicpeer-review

    36 Citations (Scopus)


    We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r. This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r bar right arrow nr where n is the number of elements.
    Original languageEnglish
    Pages (from-to)139-153
    JournalMachine Learning
    Issue number1-2
    Publication statusPublished - 2008

    Cite this

    Balcan, M. F., Bansal, N., Beygelzimer, A., Coppersmith, D., Langford, J., & Sorkin, G. B. (2008). Robust reductions from ranking to classification. Machine Learning, 72(1-2), 139-153.