In the presence of noisy or incorrect labels, neural networks have the\nundesirable tendency to memorize information about the noise. Standard\nregularization techniques such as dropout, weight decay or data augmentation\nsometimes help, but do not prevent this behavior. If one considers neural\nnetwork weights as random variables that depend on the data and stochasticity\nof training, the amount of memorized information can be quantified with the\nShannon mutual information between weights and the vector of all training\nlabels given inputs, $I(w ; \\mathbf{y} \\mid \\mathbf{x})$. We show that for any\ntraining algorithm, low values of this term correspond to reduction in\nmemorization of label-noise and better generalization bounds. To obtain these\nlow values, we propose training algorithms that employ an auxiliary network\nthat predicts gradients in the final layers of a classifier without accessing\nlabels. We illustrate the effectiveness of our approach on versions of MNIST,\nCIFAR-10, and CIFAR-100 corrupted with various noise models, and on a\nlarge-scale dataset Clothing1M that has noisy labels.\n