  Modern neural networks are typically trained in an over-parameterized regime
where the parameters of the model far exceed the size of the training data.
Such neural networks in principle have the capacity to (over)fit any set of
labels including pure noise. Despite this, somewhat paradoxically, neural
network models trained via first-order methods continue to predict well on yet
unseen test data. This paper takes a step towards demystifying this phenomena.
Under a rich dataset model, we show that gradient descent is provably robust to
noise/corruption on a constant fraction of the labels despite
overparameterization. In particular, we prove that: (i) In the first few
iterations where the updates are still in the vicinity of the initialization
gradient descent only fits to the correct labels essentially ignoring the noisy
labels. (ii) to start to overfit to the noisy labels network must stray rather
far from from the initialization which can only occur after many more
iterations. Together, these results show that gradient descent with early
stopping is provably robust to label noise and shed light on the empirical
robustness of deep networks as well as commonly adopted heuristics to prevent
overfitting.
