Abstract
We establish a new theoretical framework for learning under multi-class, instance-dependent label noise. At the heart of our framework is the concept of \emph{relative signal strength} (RSS), which is a point-wise measure of noisiness. Using relative signal strength, we establish matching upper and lower bounds for excess risk. Our theoretical findings reveal a surprising result: the extremely simple \emph{Noise Ignorant Empirical Risk Minimization (NI-ERM)} principle, which conducts empirical risk minimization as if no label noise exists, is minimax optimal. Finally, we translate these theoretical insights into practice: by using NI-ERM to fit a linear classifier on top of a self-supervised feature extractor, we achieve state-of-the-art performance on the CIFAR-N data challenge.