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

By Tomaso A. Poggio, Kenji Kawaguchi, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix, Jack D. Hidary, Hrushikesh Narhar Mhaskar. 2017

138 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Scaling & Learning Theory

Citations in the corpus

Gradient-Based Neural DAG Learning (2019, methodology): “Second, to optimize (11), we use a stochastic gradient algorithm variant which is now known to have an implicit regularizing effect (Poggio et al., 2018).”
Three Factors Influencing Minima in SGD (2017, neutral): “This is a similar assumption to previous papers Mandt et al. (2017); Poggio & et al. (2018).”
Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization (2019, background): “…Goodfellow et al., 2014; Im et al., 2016; Wu et al., 2017; Liao & Poggio, 2017; Cooper, 2018; Novak et al., 2018), and to the implicit regularization properties of SGD (Brutzkus et al., 2017; Zhang et al., 2018a; Poggio et al., 2017), though a thorough theoretical understanding is not yet complete.”
To understand deep learning we need to understand kernel learning (2018, background): “There have been a number of recent efforts to understand generalization and overfitting in deep networks including (Bartlett et al., 2017; Liang et al., 2017; Poggio et al., 2018).”
On the Relation Between the Sharpest Directions of DNN Loss and the SGD Step Length (2018, background): “While understanding the generalization capability of DNNs remains an open challenge, it has been hypothesized that SGD acts as an implicit regularizer, limiting the complexity of the found solution (Poggio et al., 2017; Advani and Saxe, 2017; Wilson et al., 2017; Jastrzębski et al., 2017).”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, background): “The same phenomenon is referred to as implicit bias, implicit regularization, simplicity bias and spectral bias in several works [83, 75, 36, 74, 70, 53, 94, 10, 13, 35, 82, 66].”
Physics-informed neural networks with hard constraints for inverse design (2021, background): “This could be explained by the analysis that neural networks trained with gradient descent have an implicit regularization and tend to converge to smooth solutions [35, 43, 19].”
Optimization Models for Machine Learning: A Survey (2019, background): “Weight decay limits the growth of the weights, which makes the training via backpropagation faster, and has been shown to limit overfitting (See [178] for a discussion about overfitting in Neural Networks).”
Model complexity of deep learning: a survey (2021, background): “Expressive capacity of deep models is also known as representation capacity, expressive power, and complexity capacity [60, 86].”
The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, methodology): “In the n < p situation, if gradient descent is initialized at β = 0 then it will converge to the minimum-norm OLS solution (Zhang et al., 2017; Wilson et al., 2017) [see also Soudry et al. (2018) and Poggio et al. (2017) for the case of logistic loss].”