Abstract

We consider the problem of classification in the presence of label noise. In the analysis of classification problems it is typically assumed that the train and test distributions are one and the same. In practice, however, it is often the case that the labels in the training data have been corrupted with some unknown probability. We shall focus on classification with class conditional label noise in which the labels observed by the learner have been corrupted with some unknown probability which is determined by the true class label.

In order to obtain finite sample rates, previous approaches to classification with unknown class conditional label noise have required that the regression function attains its extrema uniformly on sets of positive measure. We consider this problem in the setting of non-compact metric spaces, where the regression function need not attain its extrema.

In this setting we determine the minimax optimal learning rates (up to logarithmic factors). The rate displays interesting threshold behaviour: When the regression function approaches its extrema at a sufficient rate, the optimal learning rates are of the same order as those obtained in the label-noise free setting. If the regression function approaches its extrema more gradually then classification performance necessarily degrades. In addition, we present an algorithm which attains these rates without prior knowledge of either the distributional parameters or the local density.