  Modern neural networks have the capacity to overfit noisy labels frequently
found in real-world datasets. Although great progress has been made, existing
techniques are limited in providing theoretical guarantees for the performance
of the neural networks trained with noisy labels. Here we propose a novel
approach with strong theoretical guarantees for robust training of deep
networks trained with noisy labels. The key idea behind our method is to select
weighted subsets (coresets) of clean data points that provide an approximately
low-rank Jacobian matrix. We then prove that gradient descent applied to the
subsets do not overfit the noisy labels. Our extensive experiments corroborate
our theory and demonstrate that deep networks trained on our subsets achieve a
significantly superior performance compared to state-of-the art, e.g., 6%
increase in accuracy on CIFAR-10 with 80% noisy labels, and 7% increase in
accuracy on mini Webvision.
