  Over-parameterized deep neural networks trained by simple first-order methods
are known to be able to fit any labeling of data. Such over-fitting ability
hinders generalization when mislabeled training examples are present. On the
other hand, simple regularization methods like early-stopping can often achieve
highly nontrivial performance on clean test data in these scenarios, a
phenomenon not theoretically understood. This paper proposes and analyzes two
simple and intuitive regularization methods: (i) regularization by the distance
between the network parameters to initialization, and (ii) adding a trainable
auxiliary variable to the network output for each training example.
Theoretically, we prove that gradient descent training with either of these two
methods leads to a generalization guarantee on the clean data distribution
despite being trained using noisy labels. Our generalization analysis relies on
the connection between wide neural network and neural tangent kernel (NTK). The
generalization bound is independent of the network size, and is comparable to
the bound one can get when there is no label noise. Experimental results verify
the effectiveness of these methods on noisily labeled datasets.
