  For multi-class classification under class-conditional label noise, we prove
that the accuracy metric itself can be robust. We concretize this finding's
inspiration in two essential aspects: training and validation, with which we
address critical issues in learning with noisy labels. For training, we show
that maximizing training accuracy on sufficiently many noisy samples yields an
approximately optimal classifier. For validation, we prove that a noisy
validation set is reliable, addressing the critical demand of model selection
in scenarios like hyperparameter-tuning and early stopping. Previously, model
selection using noisy validation samples has not been theoretically justified.
We verify our theoretical results and additional claims with extensive
experiments. We show characterizations of models trained with noisy labels,
motivated by our theoretical results, and verify the utility of a noisy
validation set by showing the impressive performance of a framework termed
noisy best teacher and student (NTS). Our code is released.
