  There has been much interest in recent years in learning good classifiers
from data with noisy labels. Most work on learning from noisy labels has
focused on standard loss-based performance measures. However, many machine
learning problems require using non-decomposable performance measures which
cannot be expressed as the expectation or sum of a loss on individual examples;
these include for example the H-mean, Q-mean and G-mean in class imbalance
settings, and the Micro $F_1$ in information retrieval. In this paper, we
design algorithms to learn from noisy labels for two broad classes of
multiclass non-decomposable performance measures, namely, monotonic convex and
ratio-of-linear, which encompass all the above examples. Our work builds on the
Frank-Wolfe and Bisection based methods of Narasimhan et al. (2015). In both
cases, we develop noise-corrected versions of the algorithms under the widely
studied family of class-conditional noise models. We provide regret (excess
risk) bounds for our algorithms, establishing that even though they are trained
on noisy data, they are Bayes consistent in the sense that their performance
converges to the optimal performance w.r.t. the clean (non-noisy) distribution.
Our experiments demonstrate the effectiveness of our algorithms in handling
label noise.
