Abstract
We propose a metric for evaluating the generalization ability of deep neural networks trained with mini-batch gradient descent. Our metric, called gradient disparity, is the \(\ell _2\) norm distance between the gradient vectors of two mini-batches drawn from the training set. It is derived from a probabilistic upper bound on the difference between the classification errors over a given mini-batch, when the network is trained on this mini-batch and when the network is trained on another mini-batch of points sampled from the same dataset. We empirically show that gradient disparity is a very promising early-stopping criterion (i) when data is limited, as it uses all the samples for training and (ii) when available data has noisy labels, as it signals overfitting better than the validation data. Furthermore, we show in a wide range of experimental settings that gradient disparity is strongly related to the generalization error between the training and test sets, and that it is also very informative about the level of label noise.
Keywords
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsNotes
- 1.
We have also studied networks trained with the mean square error in Appendix E.3 of the full version [12], and we observe that there is a strong positive correlation between the test error/loss and gradient disparity for this choice of the surrogate loss function as well (see Fig. 11 of the full version [12]).
- 2.
- 3.
See for example Fig. 14 (left column) in the full version [12] where the validation loss fails to estimate the test loss, but where GD (Fig. 14 (middle left column)) does signal overfitting correctly.
References
Prechelt, L.: Early stopping - but when? In: Orr, G.B., Müller, K.-R. (eds.) Neural Networks: Tricks of the Trade. LNCS, vol. 1524, pp. 55–69. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49430-8_3
Yao, Y., Rosasco, L., Caponnetto, A.: On early stopping in gradient descent learning. Constr. Approximation 26(2), 289–315 (2007)
Gu, J., et al.: Recent advances in convolutional neural networks. Pattern Recogn. 77, 354–377 (2018)
Roh, Y., Heo, G., Whang, S.E.: A survey on data collection for machine learning: a big data-ai integration perspective. IEEE Transactions on Knowledge and Data Engineering (2019)
Ipeirotis, P.G., Provost, F., Wang, J.: Quality management on amazon mechanical turk. In: Proceedings of the ACM SIGKDD Workshop on Human Computation, pp. 64–67 (2010)
Frénay, B., Verleysen, M.: Classification in the presence of label noise: a survey. IEEE Trans. Neural Netw. Learn. Syst. 25(5), 845–869 (2013)
Zhang, C., Bengio, S., Hardt, M., Recht, B., Vinyals, O.: Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 (2016)
McAllester, D.A.: Pac-bayesian model averaging. In: Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pp. 164–170 (1999)
McAllester, D.A.: Some pac-bayesian theorems. Mach. Learn. 37(3), 355–363 (1999)
McAllester, D.: Simplified PAC-Bayesian margin bounds. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT-Kernel 2003. LNCS (LNAI), vol. 2777, pp. 203–215. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45167-9_16
Bien, N., et al.: Deep-learning-assisted diagnosis for knee magnetic resonance imaging: development and retrospective validation of mrnet. PLoS Med. 15(11), e1002699 (2018)
Forouzesh, M., Thiran, P.: Disparity between batches as a signal for early stopping. arXiv preprint arXiv:2107.06665 (2021)
Chatterjee, S.: Coherent gradients: an approach to understanding generalization in gradient descent-based optimization. In: International Conference on Learning Representations (2020). https://openreview.net/forum?id=ryeFY0EFwS
He, H., Su, W.: The local elasticity of neural networks. In: International Conference on Learning Representations (2020). https://openreview.net/forum?id=HJxMYANtPH
Deng, Z., He, H., Su, W.J.: Toward better generalization bounds with locally elastic stability. arXiv preprint arXiv:2010.13988 (2020)
Dziugaite, G.K., Roy, D.M.: Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008 (2017)
Neyshabur, B., Bhojanapalli, S., McAllester, D., Srebro, N.: Exploring generalization in deep learning. In: Advances in Neural Information Processing Systems, pp. 5947–5956 (2017)
Nagarajan, V., Kolter, J.Z.: Uniform convergence may be unable to explain generalization in deep learning. In: Advances in Neural Information Processing Systems, pp. 11611–11622 (2019)
Chatterji, N., Neyshabur, B., Sedghi, H.: The intriguing role of module criticality in the generalization of deep networks. In: International Conference on Learning Representations (2020). https://openreview.net/forum?id=S1e4jkSKvB
Sankararaman, K.A., De, S., Xu, Z., Huang, W.R., Goldstein, T.: The impact of neural network overparameterization on gradient confusion and stochastic gradient descent. arXiv preprint arXiv:1904.06963 (2019)
Riemer, M., et al.: Learning to learn without forgetting by maximizing transfer and minimizing interference. arXiv preprint arXiv:1810.11910 (2018)
Liu, V., Yao, H., White, M.: Toward understanding catastrophic interference in value-based reinforcement learning. Optimization Foundations for Reinforcement Learning Workshop at NeurIPS (2019)
Bengio, E., Pineau, J., Precup, D.: Interference and generalization in temporal difference learning. arXiv preprint arXiv:2003.06350 (2020)
Yin, D., Pananjady, A., Lam, M., Papailiopoulos, D., Ramchandran, K., Bartlett, P.: Gradient diversity: a key ingredient for scalable distributed learning. arXiv preprint arXiv:1706.05699 (2017)
Fort, S., Nowak, P.K., Jastrzebski, S., Narayanan, S.: Stiffness: A new perspective on generalization in neural networks. arXiv preprint arXiv:1901.09491 (2019)
Fu, J., Liu, P., Zhang, Q., Huang, X.: Rethinking generalization of neural models: A named entity recognition case study. arXiv preprint arXiv:2001.03844 (2020)
Mehta, H., Cutkosky, A., Neyshabur, B.: Extreme memorization via scale of initialization. arXiv preprint arXiv:2008.13363 (2020)
Negrea, J., Haghifam, M., Dziugaite, G.K., Khisti, A., Roy, D.M.: Information-theoretic generalization bounds for sgld via data-dependent estimates. In: Advances in Neural Information Processing Systems, pp. 11013–11023 (2019)
Haghifam, M., Negrea, J., Khisti, A., Roy, D.M., Dziugaite, G.K.: Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. arXiv preprint arXiv:2004.12983 (2020)
Qian, X., Klabjan, D.: The impact of the mini-batch size on the variance of gradients in stochastic gradient descent. arXiv preprint arXiv:2004.13146 (2020)
Jastrzebski, S., et al.: The break-even point on optimization trajectories of deep neural networks. arXiv preprint arXiv:2002.09572 (2020)
Liu, J., Bai, Y., Jiang, G., Chen, T., Wang, H.: Understanding why neural networks generalize well through gsnr of parameters. In: International Conference on Learning Representations (2020). https://openreview.net/forum?id=HyevIJStwH
Mahsereci, M., Balles, L., Lassner, C., Hennig, P.: Early stopping without a validation set. arXiv preprint arXiv:1703.09580 (2017)
Liu, Y., Starzyk, J.A., Zhu, Z.: Optimized approximation algorithm in neural networks without overfitting. IEEE Trans. Neural Netw. 19(6), 983–995 (2008)
Piotrowski, A.P., Napiorkowski, J.J.: A comparison of methods to avoid overfitting in neural networks training in the case of catchment runoff modelling. J. Hydrol. 476, 97–111 (2013)
Zhang, X., Wu, D., Xiong, H., Dai, B.: Optimization variance: Exploring generalization properties of dnns (2021). https://openreview.net/forum?id=ZAfeFYKUek5
Dziugaite, G.K., Hsu, K., Gharbieh, W., Roy, D.M.: On the role of data in pac-bayes bounds. arXiv preprint arXiv:2006.10929 (2020)
Neyshabur, B., Bhojanapalli, S., Srebro, N.: A pac-bayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564 (2017)
Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.: Dropout: a simple way to prevent neural networks from overfitting. J. Mach. Learn. Res. 15(1), 1929–1958 (2014)
Bellido, I., Fiesler, E.: Do backpropagation trained neural networks have normal weight distributions? In: Gielen, S., Kappen, B. (eds.) ICANN 1993, pp. 772–775. Springer, London (1993). https://doi.org/10.1007/978-1-4471-2063-6_214
Stone, M.: Cross-validatory choice and assessment of statistical predictions. J. R. Stat. Soc. Ser. B (Methodol.) 36(2), 111–133 (1974)
Bengio, Y., Grandvalet, Y.: No unbiased estimator of the variance of k-fold cross-validation. J. Mach. Learn. Res. 5(9), 1089–1105 (2004)
Li, M., Soltanolkotabi, M., Oymak, S.: Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. In: International Conference on Artificial Intelligence and Statistics, pp. 4313–4324. PMLR (2020)
Song, H., Kim, M., Park, D., Lee, J.G.: Prestopping: How does early stopping help generalization against label noise? (2020). https://openreview.net/forum?id=BklSwn4tDH
Xia, X., et al.: Robust early-learning: hindering the memorization of noisy labels. In: International Conference on Learning Representations (2021). https://openreview.net/forum?id=Eql5b1_hTE4
Heckel, R., Yilmaz, F.F.: Early stopping in deep networks: Double descent and how to eliminate it. arXiv preprint arXiv:2007.10099 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Forouzesh, M., Thiran, P. (2021). Disparity Between Batches as a Signal for Early Stopping. In: Oliver, N., Pérez-Cruz, F., Kramer, S., Read, J., Lozano, J.A. (eds) Machine Learning and Knowledge Discovery in Databases. Research Track. ECML PKDD 2021. Lecture Notes in Computer Science(), vol 12976. Springer, Cham. https://doi.org/10.1007/978-3-030-86520-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-86520-7_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86519-1
Online ISBN: 978-3-030-86520-7
eBook Packages: Computer ScienceComputer Science (R0)