Robust reductions from ranking to classification

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    16 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 \mapsto nr$ where n is the number of elements.
    Original languageEnglish
    Title of host publicationLearning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings)
    EditorsN.H. Bshouty, C. Gentile
    Place of PublicationBerlin
    ISBN (Print)978-3-540-72925-9
    Publication statusPublished - 2007

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Robust reductions from ranking to classification'. Together they form a unique fingerprint.

    Cite this