PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tomaso Poggio, Kenji Kawaguchi, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix, Jack Hidary, Hrushikesh Mhaskar

arXiv:1801.00173v2cs.LG

TL;DR

Highly overparameterized deep networks can fit randomly labeled data, yet the paper asks why they show little overfitting on normally labeled data. It analyzes gradient-descent dynamics near minima and relates them to linear gradient systems. The paper concludes that overparameterization need not cause classification-error overfitting on suitable datasets.

  • Problem

    Highly overparameterized deep networks can fit randomly labeled data, raising the question of why they show little overfitting on normally labeled data.

    Source: §2 · p. 2

  • Method

    The paper uses ordinary differential equation theory to show that near a global flat minimum, deep-network gradient descent is qualitatively equivalent to a linear gradient system with a quadratic degenerate potential.

    Source: §1 · p. 2, §5 · p. 11

  • Results

    Overparameterization can yield loss overfit without classification-error overfit on suitable datasets, through gradient descent's implicit regularization and associated margin maximization.

    Source: §5 · pp. 11–12

  • Takeaways & Limitations

    The paper suggests that overparameterization does not necessarily lead to classification-error overfitting and relates deep local networks' approximation power to avoiding the curse of dimensionality for hierarchically local compositional functions.

    Source: §5 · p. 12

    Near a global minimum, the linear approximation does not guarantee that the null space remains unaffected by early gradient-descent steps, and the quadratic-loss solution is not strictly guaranteed to be minimum norm.

    Source: §6.2.1 · p. 16

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses why highly overparameterized deep networks generalize, extending insights from linear networks to deep networks. It studies gradient descent dynamics and argues that these properties help explain the apparent lack of overfitting.

1 Introduction

  • The paper frames generalization in highly overparameterized deep networks as the unresolved question, while representation power and empirical-loss optimization have more satisfactory answers.It positions its contribution as extending properties of linear networks to deep networks.Source: §1 · p. 2
  • The authors use classical ordinary differential equation theory to recast the generalization puzzle as properties of gradient optimization, while noting the work's physicist-level rather than mathematician-level rigor.They argue that this approach explains the puzzle without requiring a fundamental departure from classical learning theory.Source: §1 · p. 2
  • The analysis focuses on gradient descent for simplicity, with the authors expecting relevant results to extend to stochastic gradient descent.They note that on easier problems such as CIFAR, gradient descent can replace stochastic gradient descent given enough computational resources; on harder problems, stochastic gradient descent may converge faster and select global minima better.Source: §1 · p. 2
  • The simulations disable performance-enhancing practices such as data augmentation and weight decay to study basic network properties, while retaining batch normalization in CIFAR experiments.Some experiments also reduce network or training-set size, so performance is not state of the art; the paper uses cross-entropy for classification and square loss for regression.Source: §1 · p. 2
  • The paper uses polynomial approximations of ReLU networks, arguing that they retain deep-learning properties and that smooth activations can preserve the main properties.The stated implication is that ReLU activations can be replaced by smooth, non-positively-homogeneous activations without affecting those properties.Source: §1 · p. 2

2 Overfitting Puzzle

The paper distinguishes ordinary generalization from its central overfitting puzzle: highly overparameterized networks can fit randomly labeled data yet show little classification overfitting on normally labeled data. It cautions that parameter count alone is only a rough measure of overparameterization.

2 Overfitting Puzzle

  • Test error can decrease as training-set size increases even when training error is zero, and the paper distinguishes reported classification error from the cross-entropy loss minimized during training.The paper also describes generalization as convergence of training error to expected error as the number of examples tends to infinity.Source: §2 · p. 2
  • The central puzzle is that networks with many more parameters than data can fit randomly labeled data yet show little overfitting on normally labeled data.The same network's capacity is demonstrated by zero training error on randomly labeled data, while normally labeled data show no significant classification overfitting.Source: §2 · pp. 2–3
  • Figure 1 compares classification-error behavior on CIFAR subsets with normal labels and randomly scrambled labels.The network is a five-layer all-convolutional model with about 10,000 weights; it uses neither data augmentation nor regularization.Source: Figure 1 · p. 3
  • Parameter count alone cannot determine overparameterization; it is only a rough guideline.The paper distinguishes trivial from nontrivial parameterization.Source: §2 · p. 3

3 Linear Networks

The section presents linear-network results that motivate the paper's account of deep-network generalization: gradient descent implicitly regularizes solutions, and its limiting behavior connects minimum norm to classification margin. The qualifications differ by loss and data setting.

3 Linear Networks

  • Linear-network results motivate explaining lack of overfitting through the distinction between classification error and training loss, and through gradient descent's implicit regularization.The paper describes regularization as decreasing with iteration count, with the limiting minimum-norm solution also serving as a maximum-margin solution.Source: §3 · p. 3

3.1 Gradient descent methods yield implicit regularization

  • For square loss and appropriate initial conditions, gradient descent's implicit regularization is controlled by iteration count, and early stopping can avoid loss overfitting.As iterations increase, the implicit regularization parameter decreases; the limit is the minimum-norm solution, the pseudoinverse for square loss.Source: §3.1 · pp. 3–4

3.2 Implicit regularization yields margin maximization

  • Minimum-norm convergence yields maximum-margin classification with good error on low-noise data; with separable data, logistic and cross-entropy gradient descent converge to the max-margin solution from any starting point.For logistic and cross-entropy loss, this convergence is very slow—logarithmic in the convergence of the loss itself.Source: §3.2 · p. 4

Remarks

  • An alternative account links flat-minimum maximization under logistic loss to robust optimization and margin maximization, while cross-entropy is an upper bound for classification error.These are presented as remarks on the relationship between flatness, robust optimization, and classification error.Source: Remarks · p. 4

4 Deep networks at global minima are topologically equivalent to linear networks

Near stable zero-loss minima, deep-network gradient descent behaves like gradient flow in a locally quadratic, degenerate potential, making its dynamics comparable to those of a linear network. The paper uses this picture to interpret perturbation experiments and the different overfitting behavior of square and cross-entropy losses.

Qualitative properties of the dynamical system

  • The qualitative analysis linearizes gradient dynamics at stable equilibria using the loss Hessian, separating stable directions from zero-eigenvalue center directions.The center-manifold theorem says nearby solutions approach a solution in the center manifold exponentially fast; its non-instability is an assumption.Source: Qualitative properties of the… · pp. 4–5

The Hessian of deep networks

Proof sketch

  • For polynomial losses, the quadratic terms at the minimum occupy fewer than all parameter dimensions, and a flat minimum over a finite neighborhood would require the loss to be identically zero.The paper therefore rejects isotropically flat minima for polynomial losses.Source: Proof sketch · p. 6
  • Near each zero minimum found by GD or SGD, deep-network gradient descent is topologically equivalent to that of a linear network near a degenerate quadratic minimum.The proposition concerns stable minima of the empirical loss.Source: Proof sketch · p. 6

4.1 Testing the local structure of global minima

  • For cross-entropy, near-minimum valleys slope toward zero loss at infinite weight norm and become narrower to perturbations, unlike the flat valley of square loss.The paper reports that test loss can increase without perturbations as well as after them.Source: §4.1 · p. 7, §4.2 · pp. 9–10
  • Small perturbations near deep-network global minima produce behavior similar to linear degenerate regression, as numerical experiments predict.Repeated perturbations can leave training error unchanged while changing weights and increasing parameter norms and test error.Source: §4.1 · pp. 6–7

4.2 Resistance to overfitting in deep networks

  • For square loss, early stopping can reduce overfitting because fewer iterations leave smaller weights and may keep the solution closer to a minimum-norm solution.The paper also describes arbitrarily small weight decay as turning the flat valley into a gentle convex bowl.Source: §4.2 · p. 9
  • With separable data, cross-entropy gradient descent converges to a max-margin solution from any starting point, so classification error may avoid overfitting even when cross-entropy loss overfits.The paper summarizes the expected behavior as deep networks resembling linear models for regression and classification.Source: §4.2 · p. 10

5 Discussion

The discussion argues that deep-network gradient descent inherits linear-network properties near flat minima, helping explain why overfitting the loss need not mean overfitting classification error. The account remains qualitative: useful performance bounds, the effective norm, and why deep networks perform well remain open.

5 Discussion

  • Near global flat minima, deep-network gradient descent is qualitatively equivalent to a linear gradient system in a degenerate quadratic potential.The discussion uses this reduction to extend linear-network properties to deep networks under assumptions on empirical minimizers and datasets.Source: §5 · p. 11
  • Quantitative, useful performance bounds and the type of norm effectively optimized remain open problems.The paper also says it does not explain why deep networks perform as well as they do.Source: §5 · pp. 11–12
  • Overparametrized networks are described as yielding many global degenerate or flat minima, which SGD selects with high probability.The discussion presents this as part of the existing theoretical framework.Source: §5 · p. 12
  • Overparametrization can overfit loss without overfitting classification error on nice datasets, through implicit regularization and margin maximization.The discussion attributes the explanation to gradient-descent properties established for linear networks and extended to deep networks under certain assumptions.Source: §5 · pp. 11–12
  • Deep local networks can approximate hierarchically local compositional functions without the curse of dimensionality, unlike shallow networks.The discussion frames approximation power as the main difference between shallow and deep networks.Source: §5 · p. 12
  • Robust expected error under overparametrization suggests locally hierarchical architectures may not need to match the underlying function graph precisely.The discussion says relatively large overparametrization may not significantly affect predictive performance, potentially easing architecture design.Source: §5 · p. 12

6.1 Implicit/Iterative Regularization by GD and SGD for linear dynamical systems

This section describes implicit regularization in linear dynamical systems: the iteration dynamics control regularization, with convergence toward a minimum-norm expected-risk solution. The recalled results concern least-squares, linearly parameterized functions and include a dimension-independent claim.

6.1 Implicit/Iterative Regularization by GD and SGD for linear dynamical systems

  • Iteration dynamics implicitly regularize without explicit penalties or constraints, with regularization controlled by step size, iteration count, or both.The recalled results include convergence to minimum expected risk and to its minimum-norm minimizer.Source: §6.1 · p. 14
  • The results are dimension independent; the iteration description treats T as a stopping time and the training-point visitation sequence as stochastic in the classical choice.The passage describes stochastic visitation as induced by a uniform distribution over training points.Source: §6.1 · p. 14
  • The recalled minimum-norm convergence result assumes bounded inputs and outputs, η = 1/√n, T = n, least-squares loss, and linearly parameterized functions.The passages state convergence to the minimal-norm solution of expected risk under these conditions.Source: §6.1 · p. 14

6.2 Hessian of the loss for multilayer networks

This section examines how gradient descent selects minimum-norm solutions in overparameterized linear systems and networks, alongside Hessian degeneracy in overparameterized networks. For nonlinear multilayer networks, it describes degenerate Hessians at zero training error and, for ReLU, local null directions that preserve training outputs even as the associated matrix changes away from critical points.

6.2.1 No-hidden-layer linear systems

  • From zero initialization, gradient descent and stochastic gradient descent converge to the minimum-norm solution of the overparameterized linear system.The setup assumes d > n and a full-row-rank data matrix.Source: §6.2.1 · pp. 15–16
  • For separable data, logistic and cross-entropy loss guarantee a maximum-margin solution, while quadratic loss does not guarantee minimum norm in the nonlinear linearization.The passage also notes that norms remain bounded if the gradient is bounded.Source: §6.2.1 · p. 16

6.2.2 One-hidden layer linear networks

  • When d′ < N, the one-hidden-layer linear network has zero Hessian eigenvalues along weight directions that leave its output unchanged.Gradient descent does not add components in these degenerate directions.Source: §6.2.2 · p. 18
  • Overdetermined solutions have only trivial degeneracy, whereas underdetermined solutions may have nontrivial degeneracy that more data can avoid.Trivial degeneracy leaves the represented network unchanged; nontrivial degeneracy can yield different networks.Source: §6.2.2 · p. 18
  • With W2 ≠ 0 and initialization of W1 outside Null(X⊤), gradient descent and stochastic gradient descent find a minimum-norm solution.The result applies when the optimization converges to a solution.Source: §6.2.2 · pp. 19–20

6.2.3 One-hidden layer polynomial networks

  • For one-hidden-layer polynomial networks, the analysis considers n > d and derives gradient expressions using elementwise powers and Hadamard products.Source: §6.2.3 · p. 20

6.2.4 Nonlinear deep networks

  • For nonlinear one-hidden-layer networks, the first Hessian block has zero eigenvalues when dN > n·min(N, d′).The stated rank bound implies degeneracy in the output Jacobian product Hessian block.Source: §6.2.4 · p. 21
  • At any twice-differentiable zero-loss point, Theorem 3 guarantees a zero Hessian eigenvalue if some layer k satisfies NkNk−1 > n·min(Nk, ..., NH+1).The result applies to nonlinear networks with arbitrarily many hidden layers.Source: §6.2.4 · p. 22
  • At zero training error, the Hessian is the output-Jacobian Gram matrix, and a layer-block rank bound yields a zero eigenvalue under the stated width condition.The rank is at most n·min(Nk, ..., NH+1), so the block has a zero eigenvalue when NkNk−1 exceeds that bound.Source: §6.2.4 · p. 23
  • For ReLU, the identified null directions leave training outputs—and thus loss—unchanged locally, while gradient descent adds no null-space components; D nevertheless changes during training away from critical points.At a differentiable point, sufficiently small moves in these directions do not change the training outputs.Source: §6.2.4 · pp. 21, 23

6.3 For linear networks SGD selects flat minima which imply robust optimization which provides maximization of margin

The section links flat minima in linear networks to robust optimization and, for separable binary classification, to larger classification margins. It also relates robustness to weight perturbations to stability with respect to training examples.

6.3 For linear networks SGD selects flat minima which imply robust optimization which provides maximization of margin

  • Under the stated conjecture, SGDL—and approximately SGD—maximizes loss flatness in weight space.The robust-optimization interpretation is introduced as a conjecture under regularity assumptions on empirical minima.Source: §6.3 · p. 24

6.3.1 SGD converges to a large-margin classifier for linear functions

  • For separable data, the robust constraints yield the hard-margin SVM objective by maximizing margin under weight-perturbation robustness.The derivation assumes separability and bounds perturbations in the weights relative to their norm.Source: §6.3.1 · p. 24
  • For separable binary data, maximizing flatness is equivalent to maximizing robustness and classification margin.The section connects this result to SGD selecting flat minima and to a robust optimization formulation.Source: §6.3 · p. 24, §6.3.1 · p. 25

Remarks

  • Robust worst-case loss minimization is not classical SVM because its regularization term lies inside the hinge loss.The section says standard regularization is an upper bound for the robust minimum.Source: Remarks · p. 25
  • Depending on the loss and allowed perturbations, robust optimization can yield varied objectives that are not identical to standard regularization but usually contain a regularization term.For linear networks with linearly separable data, the section concludes that SGD provides a solution closely related to hinge-loss SVM.Source: Remarks · p. 25

6.3.2 Robustness wrt Weights and Robustness wrt Data

  • Flat minima in weight space indicate weight stability, which the section connects to stability with respect to training examples.The connection follows because the learned function depends on weights that themselves depend on the training set.Source: §6.3.2 · p. 25

6.4 Polynomial Networks

The section uses polynomial networks to study deep-network properties with analytic functions and polynomial tools. It reports that polynomial networks can approximate ReLU networks and show similar empirical behavior, including limited overfitting as parameter counts increase.

6.4 Polynomial Networks

  • Polynomial approximations make deep networks analytic, allowing polynomial tools such as the Bézout theorem to characterize loss minima.The paper also argues that ReLU-specific properties such as discontinuous derivatives and non-negative homogeneity do not play a significant role in the reported empirical approximation.Source: §6.4 · p. 26
  • A standard monomial parameterization uses N coefficients for a degree-at-most-k polynomial, while the stated one-hidden-layer network representation uses (d + 2)N weights.The deep polynomial network can represent the same polynomial, in principle, using the standard monomial parameterization.Source: §6.4 · p. 26, §6.4.2 · p. 27

6.4.1 Polynomial approximation of deep networks

  • On bounded intervals, univariate polynomials can approximate nonlinear activations and their derivatives to arbitrary accuracy.The text gives a weighted uniform approximation for derivatives when a smoothed ReLU is approximated by a polynomial.Source: §6.4.1 · p. 27, §6.4.2 · p. 27

6.4.2 Deep polynomial networks behave as deep networks

  • Polynomial and ReLU networks with the same architecture show very similar training and testing error in the reported experiments.The simulations replace ReLUs with degree-10 univariate polynomial approximations.Source: §6.4.2 · p. 27, Figure 9 · p. 28
  • Increasing parameter count does not induce overfitting in polynomial networks in terms of classification error, and their weights approach an asymptotic norm during training.The reported comparison uses polynomial networks trained on CIFAR.Source: §6.4.2 · p. 27

6.5 Additional experiments

The additional experiments compare overfitting behavior across linear feature-space models and deep networks under different losses and settings. They report that some test losses overfit even when classification error remains robust, while other settings show overfitting in test or classification error.

6.5 Additional experiments

  • Qualitative properties of deep networks under cross-entropy appear, as expected, under quadratic loss as well.The passage points to Figures 17 and 18 for this comparison.Source: §6.5 · p. 28, Figure 17 · p. 35, Figure 18 · p. 36
  • For an overparameterized linear feature-space model with degenerate Hessian, the minimum-norm solution eventually overfits the test error.The polynomial feature degree ranges from 1 to 300 in the Figure 13 experiment.Source: Figure 13 · p. 31
  • Without weight perturbations, Figure 14 reports some test-loss overfitting while classification remains robust to it.The text attributes the slight increase in test loss to cross-entropy risk and notes that the classification loss does not show overfitting there.Source: Figure 14 · p. 32
  • A separate linear feature-space experiment with 9 training points and degree-30 polynomial features reports overfitting in test error.The reported curves and weight norms average 30 full-gradient-descent repetitions.Source: Figure 15 · p. 33
  • In Figure 16’s nondegenerate quadratic convex case, the unperturbed left plot shows an inset indicating absence of overfitting, for a degree-4 feature polynomial, sine target frequency 4, and 9 training versus 100 test points.Training used full gradient descent with step size 0.2 for 250,000 iterations; plotted training and test errors average 30 repetitions. In the right plot, weights were perturbed every 4,000 iterations with Gaussian noise (mean 0, standard deviation 0.6), then gradient descent converged to zero training error after each perturbation.Source: Figure 16 · p. 34
  • With 2000 training examples and 188810 parameters, the CIFAR classification error overfits under gradient descent on square loss.Figure 18 reports the classification error for this setting.Source: Figure 18 · p. 36
Loading 1801.00173v2…