PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding deep learning requires rethinking generalization

Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals

arXiv:1611.03530v2cs.LG

TL;DR

The paper asks why some highly overparameterized neural networks generalize well despite their capacity to memorize data. Through label and input randomization experiments, plus a finite-sample expressivity construction, it shows that standard networks can fit random labels and noise, challenging traditional explanations of generalization.

  • Problem

    The paper asks what distinguishes neural networks that generalize well from those that generalize poorly despite often having more parameters than training samples.

  • Method

    The authors compare training on true versus randomized labels and inputs across standard architectures, alongside a theoretical analysis of finite-sample expressivity.

  • Results

    Standard convolutional networks achieve 0 training error on random labels and random-pixel inputs, while increasing input noise steadily worsens generalization.

  • Takeaways & Limitations

    The findings challenge traditional model-complexity explanations and show that optimization can remain easy even when the resulting model does not generalize.

  • Takeaways & Limitations

    Minimum-norm intuition is not predictive of generalization performance, as the test error improves while the minimum-norm solution becomes larger.

Abstract

from arXiv · show

Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance. Conventional wisdom attributes small generalization error either to properties of the model family, or to the regularization techniques used during training. Through extensive systematic experiments, we show how these traditional approaches fail to explain why large neural networks generalize well in practice. Specifically, our experiments establish that state-of-the-art convolutional networks for image classification trained with stochastic gradient methods easily fit a random labeling of the training data. This phenomenon is qualitatively unaffected by explicit regularization, and occurs even if we replace the true images by completely unstructured random noise. We corroborate these experimental findings with a theoretical construction showing that simple depth two neural networks already have perfect finite sample expressivity as soon as the number of parameters exceeds the number of data points as it usually does in practice. We interpret our experimental findings by comparison with traditional models.

1 INTRODUCTION

The introduction challenges conventional explanations of neural-network generalization by showing that large networks can memorize randomized data while retaining the same architecture and training setup. It complements these experiments with results on regularization, finite-sample expressivity, and SGD’s implicit bias.

  • Motivation: Deep networks often have more parameters than training samples yet can achieve remarkably small training–test error differences.The introduction frames this mismatch as the central question of what distinguishes networks that generalize well from those that do not.
  • Randomization tests: Randomizing labels lets standard neural networks achieve 0 training error while test performance falls to random chance.The model, size, hyperparameters, and optimizer remain unchanged, so label randomization alone can sharply increase generalization error.
  • Randomization tests: Neural networks have enough effective capacity to memorize entire datasets, and optimization on random labels remains easy.Training time increases only by a small constant factor relative to training on true labels.
  • Randomization tests: Convolutional neural networks also fit completely unstructured random pixels with zero training error.Varying randomization from no noise to complete noise produces intermediate learning problems while preserving this fitting ability.
  • The role of explicit regularization: Explicit regularization, including weight decay, dropout, and data augmentation, can improve generalization but is neither necessary nor by itself sufficient.The introduction presents regularization as a tuning parameter that often improves final test error rather than as a complete explanation of generalization.
  • Finite sample expressivity: A two-layer ReLU network with p = 2n+d parameters can express any labeling of any sample of size n in d dimensions.This finite-sample construction shows that depth-2 networks of linear size can represent arbitrary training labels, unlike prior population-level function-space results.

2 EFFECTIVE CAPACITY OF NEURAL NETWORKS

This section tests neural-network capacity by training models on progressively randomized labels and inputs. The experiments show that tested networks can fit arbitrary training assignments, challenging traditional explanations of their generalization.

  • Experimental methodology: The randomization methodology compares training on true data with copies whose labels are replaced by random assignments, eliminating any instance-label relationship.The study also varies label corruption and randomizes inputs to examine the continuum from structured data to unstructured data.
  • Randomized data: Stochastic gradient descent fits random labels perfectly with unchanged hyperparameters, even after shuffling pixels or resampling each image from a Gaussian distribution.The networks tested remain able to fit despite the destruction of image structure and label-image relationships.
  • Experimental results: Alexnet and MLPs converge to zero training loss on CIFAR10, while ImageNet reaches 95.20% accuracy on a million random labels from 1000 categories.The ImageNet experiment used unchanged hyperparameters when switching from the original labels.
  • Experimental results: Networks fit every tested level of CIFAR10 label corruption perfectly, while convergence slows as corruption increases and test error equals generalization error because training error is zero.The corruption level ranges from 0, with no corruption, to 1, with completely random labels.
  • Implications for generalization: These randomization findings challenge traditional approaches that explain generalization through hypothesis-class complexity or training-algorithm properties.The discussion specifically connects perfect random-label fitting to Rademacher complexity and contrasts it with uniform stability.

3 THE ROLE OF REGULARIZATION

The experiments show that explicit and implicit regularizers can improve deep-network generalization but are unlikely to be its fundamental cause. Networks continue to generalize well after regularizers are removed, while remaining able to fit random labels under many regularization settings.

  • Explicit regularization: Even with dropout and weight decay, InceptionV3 fits random training labels extremely well, while AlexNet with weight decay fails to converge.On CIFAR10, Inception and MLPs also fit the random training set perfectly with weight decay enabled.
  • Explicit regularization: The study compares data augmentation, weight decay, and dropout across common architectures by toggling the regularizers used during training.Data augmentation applies domain-specific transformations; weight decay is an ℓ2 weight regularizer; dropout randomly masks layer outputs.
  • Explicit regularization: Turning off data augmentation and weight decay reduces performance, but all CIFAR10 models still generalize very well without these regularizers.The reported comparison covers Inception, AlexNet, and MLPs on CIFAR10.
  • Explicit regularization: 18% top-1 accuracy drop occurs when all regularizers are removed on ImageNet, yet Inception reaches 59.80% top-1 accuracy without regularization and 72.95% with data augmentation alone.Random guessing achieves 0.1% top-1 accuracy on ImageNet.
  • Implicit regularization: Batch normalization stabilizes training, but its generalization impact on CIFAR10 is only 3∼4% when explicit regularizers are disabled.Early stopping could potentially improve generalization, although the paper notes that rigorous evaluation would require an isolated test set.
  • Conclusion: Overall, properly tuned regularizers improve generalization, but their nonessential status is indicated by networks continuing to perform well after all regularizers are removed.The paper also reports Inception achieving 80.38% top-5 accuracy without regularization, versus 83.6% for the ILSVRC 2012 winner.

4 FINITE-SAMPLE EXPRESSIVITY

This section argues that finite-sample expressivity is more relevant than population-level expressivity for practice and shows that two-layer networks can represent any function on n samples once p > n.

  • Motivation: Finite-sample expressivity is more relevant in practice than population-level characterizations of functions represented over an entire domain.Transferring population-level results via uniform convergence would require samples polynomially large in input dimension and exponential in network depth.
  • Motivation: Uniform convergence bounds impose an unrealistic requirement: sample size must be polynomially large in input dimension and exponential in network depth.The paper therefore analyzes finite-sample expressivity directly instead of transferring population-level results.
  • Finite-sample expressivity: When the parameter count p exceeds the sample size n, simple two-layer neural networks can represent any function on every n-point input sample.The construction applies to samples in d dimensions and arbitrary functions from the sample to the real numbers.
  • Construction: The appendix discusses achieving width O(n/k) with depth k and provides bounds on construction weights through the smallest eigenvalue of matrix A.These bounds can yield reasonable bounds on the weight vector w.

5 IMPLICIT REGULARIZATION: AN APPEAL TO LINEAR MODELS

Linear models can fit arbitrary labels when d ≥ n, yet SGD selects a particular interpolating solution through the data span and kernel system. Exact fitting can generalize well, but minimum ℓ2 norm alone does not predict performance.

  • When d ≥ n, linear models can fit any labeling, raising whether such a rich unregularized model class can still generalize.
  • If X has rank n, infinitely many solutions to Xw = y achieve a global ERM minimum.
  • Starting from w0 = 0, SGD converges within the data span; interpolation then yields a unique kernel-system solution based only on data-point dot products.
  • The Gram-matrix system Kα = y can perfectly fit labels and is tractable on standard workstations when n is less than a hundred thousand.
  • 1.2% test error is achieved on MNIST without preprocessing by exactly fitting training labels with the kernel solution.The kernel matrix requires 30GB of memory, but the system is solved in under 3 minutes on a 24-core, 256 GB RAM workstation.
  • Minimum ℓ2 norm is not predictive of generalization: MNIST norm rises from approximately 220 to 390 with wavelet preprocessing while test error drops by a factor of 2.

6 CONCLUSION

The conclusion presents effective capacity as a framework for understanding successful neural networks, emphasizing that their large capacity can shatter and memorize training data. This challenges traditional complexity measures and leaves the precise notion of simplicity underlying their generalization unresolved.

  • 6 CONCLUSION: Successful neural network architectures have effective capacity large enough to shatter the training data.The experiments define and examine a notion of effective capacity for machine learning models.
  • 6 CONCLUSION: Consequently, these models are rich enough in principle to memorize the training data.
  • 6 CONCLUSION: This creates a conceptual challenge because traditional statistical learning measures of model complexity struggle to explain large neural networks’ generalization ability.
  • 6 CONCLUSION: The authors argue that no precise formal measure has yet been discovered under which these enormous models are simple.

A EXPERIMENTAL SETUP

The experiments use CIFAR10 and ImageNet with adapted convolutional and multilayer-perceptron architectures. Training relies on stochastic gradient methods under specified preprocessing, optimization, and randomized-data conditions.

  • Datasets: Experiments cover CIFAR10 and ImageNet, using 50,000 training and 10,000 validation images across 10 classes for CIFAR10, and 1,281,167 training and 50,000 validation images across 1000 classes for ImageNet.CIFAR10 inputs are 32x32 RGB images; ImageNet inputs are resized to 299x299 with 3 color channels.
  • Datasets: CIFAR10 preprocessing scales pixels to [0, 1], center-crops images to 28x28, and applies per-image whitening.Whitening subtracts each image’s mean and divides by its adjusted standard deviation using TensorFlow’s per_image_whitening function.
  • Architectures: CIFAR10 experiments test adapted small Inception and Alexnet models alongside standard MLPs with varying numbers of hidden layers.Small Alexnet uses two convolution–pooling–normalization modules, two fully connected layers with 384 and 192 hidden units, and a 10-way linear output layer.
  • Optimization: CIFAR10 models are trained with SGD momentum 0.9, learning rates of 0.1 or 0.01, and a 0.95 learning-rate decay factor per epoch.For randomized labels or pixels, networks are trained without weight decay, dropout, or other explicit regularization unless otherwise specified.
  • ImageNet setup: ImageNet experiments use Inception V3 with TensorFlow preprocessing and a pipeline supporting disabled augmentation and epoch-consistent random labels.The passage specifies that the ImageNet setup reuses TensorFlow’s data preprocessing and experimental configuration.

B DETAILED RESULTS ON IMAGENET

Table 2 reports Inception v3 performance on ImageNet under true and random labels, comparing training and test accuracy with regularization enabled or disabled. It also includes AlexNet’s reported top-5 accuracy as a reference and best test accuracy during training in parentheses.

  • B DETAILED RESULTS ON IMAGENET: Table 2 compares Inception v3 top-1 and top-5 training and test accuracy on ImageNet.The accuracies are reported as percentages.
  • B DETAILED RESULTS ON IMAGENET: The comparison covers both true labels and random labels, with various regularization settings turned on and off.This setup evaluates performance under multiple labeling and regularization conditions.
  • B DETAILED RESULTS ON IMAGENET: AlexNet’s originally reported top-5 accuracy on ILSVRC 2012 is included for reference.The table also places the best test accuracy during training in parentheses to indicate potential early-stopping gains.

C PROOF OF THEOREM 1

The proof constructs a depth-2 ReLU network that fits arbitrary targets on any n distinct sample points by reducing interpolation to an invertible lower-triangular linear system. It then trades width for depth, yielding networks of depth k, width O(n/k), and O(n + d) weights with the same finite-sample expressivity.

  • Depth-2 construction: The matrix A = [max{x_i − b_j, 0}]_ij is invertible because it is lower triangular with strictly positive diagonal entries.Its smallest eigenvalue is min_i x_i − b_i.
  • Depth-2 construction: The interpolating function c can be represented by a depth-2 network with ReLU activations.The proof defines c using weight vectors w, b ∈ R^n and a ∈ R^d.
  • Depth-2 construction: For n distinct sample points and arbitrary targets y ∈ R^n, the construction selects a and b so projected values interleave, then solves y = Aw for the output weights.The interleaving condition makes A full rank, enabling exact interpolation.
  • Width-depth tradeoff: For every k ≥ 2, a ReLU network can represent any function on n samples in d dimensions with depth k, width O(n/k), and O(n + d) weights.The width-for-depth construction uses a single output circuit and constant-size, constant-depth indicator functions.

D RESULTS OF IMPLICIT REGULARIZATION FOR LINEAR MODELS

This section reports Table 3’s small-benchmark test errors for linear models solved through a kernel equation. It also shows that preprocessing choices can significantly alter the resulting test error.

  • The experiments evaluate test error from solving the kernel equation (3) on small benchmarks.
  • Changing preprocessing can significantly change the resulting test error.
  • Table 3 reports experiment results for the linear models described in Section 5.

E FITTING RANDOM LABELS WITH EXPLICIT REGULARIZATION

The appendix tests whether explicit regularization prevents deep networks from fitting random labels. Across weight decay and data augmentation experiments, most models still overfit random labels, though augmentation requires longer convergence.

  • E FITTING RANDOM LABELS WITH EXPLICIT REGULARIZATION: Explicit regularizers did not produce a fundamental change in deep networks’ ability to fit random labels.The appendix directly investigates how explicit regularizers affect random-label fitting.
  • E FITTING RANDOM LABELS WITH EXPLICIT REGULARIZATION: All models except Alexnet fit random labels with their default weight-decay coefficients.These results were obtained on CIFAR10.
  • E FITTING RANDOM LABELS WITH EXPLICIT REGULARIZATION: Changing the default weight-decay factor from 0.95 to 0.999 and training longer led to overfitting random labels with Inception under random cropping and data augmentation.Data augmentation increases the training-set size, so convergence takes longer.
  • E FITTING RANDOM LABELS WITH EXPLICIT REGULARIZATION: With augmentation, training accuracy averages online mini-batch accuracy because a different randomly modified image appears in each epoch while labels remain consistent.Augmentation includes random left-right flipping and random rotation up to 25 degrees.
Loading 1611.03530v2…