PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization in Deep Networks: The Role of Distance from Initialization

Vaishnavh Nagarajan, J. Zico Kolter

arXiv:1901.01672v2cs.LGcs.AIstat.ML

TL;DR

The paper asks why SGD-trained deep networks can generalize without error worsening as parameter count grows. It studies effective capacity conditioned on a given initialization, using distance from initialization as a candidate measure. Experiments find this distance is mostly width-independent, while the paper leaves open whether it suffices to explain generalization.

  • Problem

    The paper asks why SGD training can yield generalization error independent of network parameter count, despite overparameterized networks’ ability to fit random labels and real data.

    Source: §1 · p. 1, §3 · p. 2

  • Method

    The paper defines effective capacity for a distribution, fixed initialization, and algorithm, and investigates distance from initialization through experiments and theoretical arguments.

    Source: §1 · p. 1, §3 · p. 2

  • Results

    Distance from initialization mostly remains constant or decreases with width, but grows with training-set size and label noise in the reported experiments.

    Source: §4 · p. 3

  • Takeaways & Limitations

    The paper argues that understanding deep-network capacity requires conditioning on initialization, and its experiments suggest distance moved by training has a key role.

    Source: §7 · p. 4

    It remains open whether distance regularization alone can yield a width-independent learning-theoretic complexity or explain generalization.

    Source: §5 · p. 3, §7 · p. 5

Abstract

from arXiv · show

Why does training deep neural networks using stochastic gradient descent (SGD) result in a generalization error that does not worsen with the number of parameters in the network? To answer this question, we advocate a notion of effective model capacity that is dependent on {\em a given random initialization of the network} and not just the training algorithm and the data distribution. We provide empirical evidences that demonstrate that the model capacity of SGD-trained deep networks is in fact restricted through implicit regularization of {\em the $\ell_2$ distance from the initialization}. We also provide theoretical arguments that further highlight the need for initialization-dependent notions of model capacity. We leave as open questions how and why distance from initialization is regularized, and whether it is sufficient to explain generalization.

1 Introduction

The ability of overparameterized networks to fit random labels yet achieve low test error on real data challenges the conventional expressivity–generalization tradeoff. The paper examines SGD’s implicit regularization, focusing on distance from a fixed initialization and initialization-dependent model capacity.

  • Overparameterized networks can fit completely random labels while also achieving low test error on real-world data, challenging the conventional expressivity–generalization tradeoff.Source: §1 · p. 1
  • Understanding this phenomenon requires examining model capacity together with SGD, including whether SGD implicitly restricts the parameter configurations it finds.Source: §1 · p. 1
  • The paper studies capacity after fixing network initialization and investigates whether SGD regularizes distance from initialization, alongside theoretical arguments for initialization-dependent capacity.Source: §1 · p. 1

2 Notations

The paper specifies a feed-forward network and the conventions used to describe its layers, parameters, activations, and norms. It assumes ReLU activations and Xavier-initialized weights with zero biases.

  • The model is a depth-d feed-forward network with H hidden units per layer, mapping inputs from R^n through layer weights W and biases B.Source: §2 · p. 2
  • The output layer is single-output, with W_d a column matrix and b_d a scalar; the text also introduces notation for each layer’s pre-activation output.Source: §2 · p. 2
  • The analysis assumes ReLU activations, Xavier-initialized weights, and zero-initialized biases.Source: §2 · p. 2
  • The notation distinguishes Frobenius, spectral, and vector ℓ2 norms, and uses tildes on asymptotic bounds to suppress logarithmic factors.Source: §2 · p. 2

3 Problem Formulation

The paper defines effective capacity for a distribution, initialization, and algorithm, aiming to explain generalization that does not grow with network width. It focuses on distance from initialization as a candidate capacity measure and relates that choice to SGD’s implicit regularization.

  • Effective capacity is defined for a distribution, a fixed initialization, and a training algorithm as the set of parameter configurations reached with high probability after zero-loss training on m samples.Source: §3 · p. 2
  • The paper argues that effective capacity should depend on initialization because this notion incorporates network symmetries and is more refined than notions independent of initialization.Source: §3 · p. 2
  • The target is a learning-theoretic characterization of this capacity with complexity independent of width H, rather than a global norm quantity independent of initialization.Source: §3 · p. 2
  • The paper focuses on the Frobenius distance of the weights and biases from initialization, a quantity previously used in a PAC-Bayesian bound by Dziugaite and Roy [2017].Source: §3 · p. 2
  • Figure 1 reports that distance is width-independent or decreases, and grows with label noise in a five-layer MNIST experiment trained to a margin of at least 10 on 99% of data.Source: Figure 1 · p. 3

4 Experiments

Experiments on MNIST and CIFAR-10 examine how distance from initialization varies with network width, training-set size, and label noise. The distance is mostly width-independent but grows with training-set size and label noise.

  • The experiments use four-hidden-layer networks on CIFAR-10 and MNIST, varying width and training-set size with real and corrupted labels.Source: §4 · p. 3
  • Distance from initialization mostly remains constant or decreases as width H grows, with only slight logarithmic growth sometimes at very large widths.Source: §4 · p. 3
  • Distance grows with label noise, and that increase is more pronounced at larger sample sizes; the paper connects this to greater distances needed for stronger memorization.Source: §4 · p. 3
  • Even when width-independent, distance grows with training-set size, typically at rates between m^0.25 and m^0.4 without label noise; growth is more prominent for smaller widths or noisier labels.Source: §4 · p. 3

5 Complexity of linear networks within fixed distance from initialization

The section tests whether restricting networks to a fixed distance from initialization can yield width-independent complexity. Linear networks provide a positive result, while the cited PAC-Bayesian substitution still leaves width dependence.

5 Complexity of linear networks within fixed distance from initialization

  • Replacing distance from the origin with distance from initialization tightens the PAC-Bayesian bound by a factor of H, but the bound still depends on width.The authors describe extending the observation to a width-independent generalization bound as non-trivial.Source: §5 · p. 3
  • Linear networks are examined first because width-dependent complexity there would leave little hope for width-independent complexity with nonlinearities.The section presents the linear case as a first test of the usefulness of distance regularization.Source: §5 · pp. 3–4
  • For linear networks, the Rademacher complexity of hypotheses within distance r of initialization is shown to be width-independent.The proof uses the high-probability width-independent spectral norms of Xavier-initialized weight matrices.Source: §5 · pp. 3–4

6 Why initialization-independent norms may not explain generalization

The section argues that norms measured from the origin may not explain width-independent generalization because random initializations move farther from the origin as width grows. It also finds that controlling distance from initialization controls a spectral-norm product, making that product less useful as an explanation.

6 Why initialization-independent norms may not explain generalization

  • The untrained network has width-independent generalization error, yet its ℓ2 norm increases with width for large H.This contrast motivates the concern that origin-based norm measures may fail to explain generalization.Source: §6 · p. 4
  • The studied product of ℓ2 norms increases with width for large H, while the known Rademacher-complexity bound grows with its norm bound.The passage links this growth to why the measure could not explain width-independent generalization.Source: §6 · p. 4
  • Origin-based norm measures may miss relevant structure because random initializations and the origin lie farther apart as width increases.The authors caution that SGD need not move solutions close to the origin for wider initializations.Source: §6 · p. 4
  • The spectral-norm measure also grows with H at random initialization, since the random matrices' spectral norms are approximately constant.The authors report growth of order ˜Ω(H^(d−1)) for the measure.Source: §6 · p. 4
  • If distance from initialization is regularized to an H-independent value, the product of spectral norms is also H-independent, making it less useful for explaining generalization.The remaining question is whether distance regularization suffices for width-independent generalization, which would extend the linear-network result to nonlinear networks.Source: §6 · p. 4

7 Conclusion

The conclusion argues that explaining deep-network generalization requires effective capacity tied to a given random initialization, and identifies unresolved questions about distance regularization and its sufficiency. The appendices provide supporting Gaussian-matrix bounds and proof steps connecting complexity control to generalization.

7 Conclusion

  • The authors leave open why training regularizes distance from initialization, whether that distance can be bounded independently of hidden width H, and whether it alone explains generalization.They also ask whether distance-regularized nonlinear networks admit an H-independent complexity bound or occupy a smaller subspace within an H-independent-radius ball.Source: §7 · pp. 4–5

A Useful Lemmas

  • Xavier initialization yields high-probability spectral-norm bounds for weight matrices, which support the appendix's network analyses.The appendix also states Gaussian and Rademacher-vector facts used in its bounds.Source: A Useful Lemmas · pp. 5–6

B Proofs

  • An H-independent complexity bound gives uniform convergence over the effective-capacity set; because the algorithm's output lies in that set, the proof obtains a generalization bound.The argument combines the two probability bounds using a union bound.Source: B Proofs · pp. 6–7

B.1 Proofs from Section 5

For linear networks, the appendix proves an H-independent Rademacher-complexity bound for hypotheses within distance r of a random initialization. The proof uses high-probability spectral-norm bounds for Xavier-initialized weights and recursively removes network parameters layer by layer.

B.1 Proofs from Section 5

  • Theorem 5.1 bounds the Rademacher complexity of linear-network hypotheses within ℓ2 distance r of initialization.The stated proof target is a complexity bound independent of hidden width H.Source: §B.1 · p. 7
  • With high probability, Xavier-initialized weight matrices have spectral norms ˜Θ(1) for layers k > 1 and ˜Θ(√n) for the first layer.These bounds are the key initialization property used in the proof.Source: §B.1 · p. 7
  • The proof removes parameters layer by layer using recursive bounds, with a linear factor d accounting for bias contributions.It also applies the Khintchine-Kahane inequality during the recursion.Source: §B.1 · pp. 7–8

B.2 Proofs from Section 6

The appendix shows that an untrained random initialization can have width-independent generalization error even while its ℓ2 norm grows with hidden width. It also argues that distance-from-initialization regularization is more powerful than spectral-norm regularization for explaining width-independent generalization.

B.2 Proofs from Section 6

  • The section states that regularizing distance from initialization is more powerful than regularizing spectral norms for explaining generalization independent of hidden width H.The proof relates each layer's spectral norm to its initialization norm plus its distance from initialization.Source: §B.2 · pp. 8–9

C Some H-independent bounds for ReLU networks

For ReLU networks under the stated Xavier initialization, the appendix develops bounds on network outputs and parameter gradients that depend on distance from initialization rather than hidden width. It also derives a width-independent bound on initial squared error loss.

C Some H-independent bounds for ReLU networks

D Experiments

The appendix reports experiments on real and corrupted MNIST and CIFAR-10 labels, varying network width, training-set size, and label noise. Its experiments use four-hidden-layer networks, with different loss targets and training conditions across settings.

D Experiments

  • The experiments use four-hidden-layer networks trained with batch-size-64 SGD; appendix plots use squared error, while main-paper plots use cross-entropy.Appendix experiments use CIFAR-10 and MNIST with a squared-error loss between one-hot labels and network outputs.Source: D Experiments · p. 10
  • Some experiments stop near 10% of initial loss rather than near-zero loss; the authors still observe non-increasing or decreasing generalization error with increasing width.The noisy-label experiments are among those trained only to around 10% of original loss.Source: D Experiments · p. 11

D.1 Real data

  • Generalization error on real data only decreases or remains constant as hidden-unit count H increases across the three MNIST and CIFAR-10 settings.Experiment A uses MNIST with learning rate 0.01 and momentum 0.9 until loss is below 0.001; B uses CIFAR-10 with learning rate 0.5 until loss is below 0.02; C uses MNIST with learning rate 1.Source: §D.1 · p. 11, Figure 2 · p. 11, Figure 3 · p. 12
  • The real-data experiments vary H and training-sample count m, and plot both generalization error and distance from initialization against those quantities.The plots use logarithmic X axes; some also use logarithmic Y axes.Source: §D.1 · p. 11

D.2 Noisy Labels

  • Completely random labels are tested on MNIST and CIFAR-10, with SGD training stopped when loss reaches 0.1.The learning rates are 0.01 for MNIST and 0.001 for CIFAR-10.Source: §D.2 · p. 11

D.3 Partially Noisy Labels

  • Partially corrupted labels are tested on two MNIST classes, varying the corrupted-point proportion and measuring distance moved from initialization.Training uses learning rate 0.01 until loss reaches 0.1.Source: §D.3 · p. 12

Related papers

Loading 1901.01672v2…