Online AUC maximization

• Main Authors: ZHAO, Peilin, HOI, Steven C. H., JIN, Rong, YANG, Tianbo
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2011
• Subjects: Computer Sciences; Databases and Information Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/2351; https://ink.library.smu.edu.sg/context/sis_research/article/3351/viewcontent/Online_AUC_Maximization.pdf
• Institution: Singapore Management University

Most studies of online learning measure the performance of a learner by classification accuracy, which is inappropriate for applications where the data are unevenly distributed among different classes. We address this limitation by developing online learning algorithm for maximizing Area Under the ROC curve (AUC), a metric that is widely used for measuring the classification performance for imbalanced data distributions. The key challenge of online AUC maximization is that it needs to optimize the pairwise loss between two instances from different classes. This is in contrast to the classical setup of online learning where the overall loss is a sum of losses over individual training examples. We address this challenge by exploiting the reservoir sampling technique, and present two algorithms for online AUC maximization with theoretic performance guarantee. Extensive experimental studies confirm the effectiveness and the efficiency of the proposed algorithms for maximizing AUC.