Abstract
Receiver Operating Characteristic (ROC) curves are useful for evaluation inbinary classification and changepoint detection, but difficult to use forlearning since the Area Under the Curve (AUC) is piecewise constant (gradientzero almost everywhere). Recently the Area Under Min (AUM) of false positiveand false negative rates has been proposed as a differentiable surrogate forAUC. In this paper we study the piecewise linear/constant nature of theAUM/AUC, and propose new efficient path-following algorithms for choosing thelearning rate which is optimal for each step of gradient descent (line search),when optimizing a linear model. Remarkably, our proposed line search algorithmhas the same log-linear asymptotic time complexity as gradient descent withconstant step size, but it computes a complete representation of the AUM/AUC asa function of step size. In our empirical study of binary classificationproblems, we verify that our proposed algorithm is fast and exact; inchangepoint detection problems we show that the proposed algorithm is just asaccurate as grid search, but faster.