  Memorization in over-parameterized neural networks could severely hurt
generalization in the presence of mislabeled examples. However, mislabeled
examples are hard to avoid in extremely large datasets collected with weak
supervision. We address this problem by reasoning counterfactually about the
loss distribution of examples with uniform random labels had they were trained
with the real examples, and use this information to remove noisy examples from
the training set. First, we observe that examples with uniform random labels
have higher losses when trained with stochastic gradient descent under large
learning rates. Then, we propose to model the loss distribution of the
counterfactual examples using only the network parameters, which is able to
model such examples with remarkable success. Finally, we propose to remove
examples whose loss exceeds a certain quantile of the modeled loss
distribution. This leads to On-the-fly Data Denoising (ODD), a simple yet
effective algorithm that is robust to mislabeled examples, while introducing
almost zero computational overhead compared to standard training. ODD is able
to achieve state-of-the-art results on a wide range of datasets including
real-world ones such as WebVision and Clothing1M.
