Theory of Deep Learning III: explaining the non-overfitting puzzle

Abstract

A main puzzle of deep networks revolves around the absence of overfitting despite large overparametrization and despite the large capacity demonstrated by zero training error on randomly labeled data. In this note, we show that the dynamics associated to gradient descent minimization of nonlinear networks is topologically equivalent, near the asymptotically stable minima of the empirical error, to linear gradient system in a quadratic potential with a degenerate (for square loss) or almost degenerate (for logistic or crossentropy loss) Hessian. The proposition depends on the qualitative theory of dynamical systems and is supported by numerical results. Our main propositions extend to deep nonlinear networks two properties of gradient descent for linear networks, that have been recently established (1) to be key to their generalization properties: 1. Gradient descent enforces a form of implicit regularization controlled by the number of iterations, and asymptotically converges to the minimum norm solution for appropriate initial conditions of gradient descent. This implies that there is usually an optimum early stopping that avoids overfitting of the loss. This property, valid for the square loss and many other loss functions, is relevant especially for regression. 2. For classification, the asymptotic convergence to the minimum norm solution implies convergence to the maximum margin solution which guarantees good classification error for "low noise" datasets. This property holds for loss functions such as the logistic and cross-entropy loss independently of the initial conditions. The robustness to overparametrization has suggestive implications for the robustness of the architecture of deep convolutional networks with respect to the curse of dimensionality.

References in corpus (8)

• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• Train faster, generalize better: Stability of stochastic gradient descent
• Robustness and Regularization of Support Vector Machines
• Exploring Generalization in Deep Learning
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Optimal Rates for Multi-pass Stochastic Gradient Methods
• Theory II: Landscape of the Empirical Risk in Deep Learning
• Theory of Deep Learning IIb: Optimization Properties of SGD

Cited by in corpus (24)

• Bayesian Deep Convolutional Encoder-Decoder Networks for Surrogate Modeling and Uncertainty Quantification
• Shallow Neural Networks for Fluid Flow Reconstruction with Limited Sensors
• The Modern Mathematics of Deep Learning
• Predicting the Generalization Gap in Deep Networks with Margin Distributions
• Data augmentation instead of explicit regularization
• Gradient Starvation: A Learning Proclivity in Neural Networks
• Deep Gamblers: Learning to Abstain with Portfolio Theory
• On the Decision Boundary of Deep Neural Networks
• Bad Global Minima Exist and SGD Can Reach Them
• Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Gradient-Based Neural DAG Learning
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Generalization in Machine Learning via Analytical Learning Theory
• On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers
• DNN or k-NN: That is the Generalize vs. Memorize Question
• A deep learning theory for neural networks grounded in physics
• Machine learning approach to chance-constrained problems: An algorithm based on the stochastic gradient descent
• Noisy Recurrent Neural Networks
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• Understanding Dynamics of Nonlinear Representation Learning and Its Application
• An analytic theory of shallow networks dynamics for hinge loss classification
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• On the Stability and Generalization of Learning with Kernel Activation Functions