PaperlayerView exact revision on arXiv

Source-linked AI summary

Bad Global Minima Exist and SGD Can Reach Them

Shengchao Liu, Dimitris Papailiopoulos, Dimitris Achlioptas

arXiv:1906.02613v2cs.LGstat.ML

TL;DR

The paper examines why overparameterized neural networks trained by SGD generalize well and whether SGD’s implicit bias is sufficient to explain that behavior. It tests random-label pretraining and finds that regularization or data augmentation can prevent its detrimental effect on subsequent training with true labels.

  • Problem

    The paper asks whether SGD’s apparent tendency to find low-complexity models explains why overparameterized networks generalize despite being able to fit random labels.

    Source: §1 · pp. 1–2

  • Method

    The authors compare SGD after random-label pretraining with training that adds explicit regularization or data augmentation.

    Source: §1 · p. 2

  • Results

    Random-label pretraining can lead SGD to poorly generalizing models, whereas regularization or data augmentation lets it reach models that generalize well.

    Source: §1 · p. 2, §4 · p. 8

  • Takeaways & Limitations

    The results suggest that regularization affects training dynamics away from optima and helps make good models easier for SGD to find.

    Source: §1 · p. 2

Abstract

from arXiv · show

Several works have aimed to explain why overparameterized neural networks generalize well when trained by Stochastic Gradient Descent (SGD). The consensus explanation that has emerged credits the randomized nature of SGD for the bias of the training process towards low-complexity models and, thus, for implicit regularization. We take a careful look at this explanation in the context of image classification with common deep neural network architectures. We find that if we do not regularize \emph{explicitly}, then SGD can be easily made to converge to poorly-generalizing, high-complexity models: all it takes is to first train on a random labeling on the data, before switching to properly training with the correct labels. In contrast, we find that in the presence of explicit regularization, pretraining with random labels has no detrimental effect on SGD. We believe that our results give evidence that explicit regularization plays a far more important role in the success of overparameterized neural networks than what has been understood until now. Specifically, by penalizing complicated models independently of their fit to the data, regularization affects training dynamics also far away from optima, making simple models that fit the data well discoverable by local methods, such as SGD.

1 Introduction

The paper asks whether all global minima generalize equally well and whether SGD alone explains why it usually avoids poor solutions. It sketches how random-label pretraining can lead SGD to a complex, poorly generalizing solution, while regularization and data augmentation can help it escape.

1 Introduction

  • The study is motivated by the contrast between networks that can memorize random labels and the good generalization often achieved by overparameterized networks trained on true labels.Prior work showed that standard SGD can fit random labels in about as much time as correct labels.Source: §1 · p. 1
  • The paper asks whether global minima for true labels differ in generalization, noting that some global minima can generalize poorly.For randomly labeled data, the authors expect loss-minimizing models not to generalize.Source: §1 · p. 1
  • Because SGD’s choice among near-global minima matters for generalization, the authors ask whether it can be initialized to reach a bad minimum using only unlabeled training data.They argue that such initializations can reflect undesirable model characteristics that persist after training on true labels; regularization and data augmentation can encourage SGD to move away from them.Source: §1 · p. 2

A Sketch of the Phenomenon

  • In the toy example, random-label pretraining produces a complex, small-margin boundary that persists during true-label training, while data augmentation and regularization restore a max-margin boundary.The example uses a two-layer ReLU network trained on two well-separated Gaussian classes.Source: A Sketch of the Phenomenon · pp. 2–3
  • Across real-image experiments, random-label pretraining leads SGD to models that fit true labels but generalize poorly; regularization or data augmentation lets it reach models with good test performance.The experiments use VGG16, ResNet18, ResNet50, and DenseNet40 on CIFAR, CINIC10, and restricted ImageNet.Source: A Sketch of the Phenomenon · p. 3

2 Experimental Setup

The experiments compare standard SGD variants across several image datasets and architectures. The setup includes random and random-label-trained initializations, with training protocols and hyperparameters chosen for convergence and reproducibility.

Datasets and Architectures

  • Experiments use CIFAR10, CIFAR100, CINIC10, and resized Restricted ImageNet with VGG16, ResNet18, ResNet50, and DenseNet40.Resizing Restricted ImageNet to 32 × 32 lowers test accuracy from 96% to 87%.Source: §2 · p. 3

Training methods

  • Vanilla SGD omits data augmentation, ℓ2 regularization, and momentum; SOTA SGD includes all three.The augmentation uses random crops and flips.Source: §2 · p. 3

Initialization

  • Adversarial initialization starts from random weights and trains on an augmented dataset whose examples have uniformly random labels until the model reaches 100% accuracy.The algorithm can replicate examples and zero out a random subset of pixels before assigning random labels.Source: §2 · p. 3

Hyperparameters

  • The experiments use standard-practice decaying learning-rate schedules to isolate regularization and implicit-bias effects from learning-rate choices.The authors note that non-standard adaptive schedules or very large learning rates could potentially force vanilla SGD to escape bad initializers.Source: §2 · p. 4

3 Experimental Findings and Observed Phenomena

Across the tested architectures and datasets, random-label pretraining can leave vanilla SGD at a poorly generalizing solution despite perfect training fit, while regularization and data augmentation help it escape that initialization. The experiments examine training and test accuracy, distance traveled, the effect of replication and training heuristics, model-complexity proxies, and adversarial robustness.

3 Experimental Findings and Observed Phenomena

  • Vanilla SGD after random-label pretraining still reaches 100% training accuracy but can lose up to 40% test accuracy; SOTA SGD reaches nearly the same test accuracy from either initialization.Data augmentation, ℓ2 regularization, and momentum also help SGD move far from adversarial initializations, unlike vanilla SGD.Source: §3 · p. 4

3.1 Training Accuracy

  • Training accuracy reaches 100% in most settings regardless of initialization or training heuristics, and convergence speed is similar for random and adversarial initializations.DenseNet is an exception, reaching slightly less than 100% on some datasets.Source: §3.1 · pp. 4–5, Figure 2 · p. 5

3.2 Test accuracy

  • Test accuracy for adversarially initialized vanilla SGD flattens below random initialization despite both reaching 100% training accuracy, with degradation up to 40% on CIFAR100.The detrimental effect vanishes with data augmentation, momentum, and ℓ2 regularization.Source: Figure 3 · p. 5, §3.2 · p. 6

3.3 Distance Travelled during Training

  • Vanilla SGD travels about 0.2 from an adversarial initialization to a perfect fit, versus about 0.9 from a random initialization; SOTA SGD travels much farther from adversarial starts, often nearly an order of magnitude.Bad models also appear close to random initializers, while Table 1 reports mean model distances across five runs.Source: §3.3 · p. 6, Table 1 · p. 6

3.4 The Effect of the Replication Factor R on Test Accuracy

  • As the replication factor R increases, vanilla SGD test performance degrades, first rapidly and then more slowly, while SOTA SGD remains essentially unchanged.Generating the adversarial initializer takes time proportional to R because the enlarged dataset must be trained to full accuracy.Source: Figure 4 · p. 7, §3.4 · p. 7

3.5 The Effect of Different Training Heuristics

  • Each of data augmentation, ℓ2 regularization, and momentum alone largely helps SGD escape a bad initialization, while any tested pair makes test accuracy independent of initialization.Table 2 compares combinations on ResNet18 and CIFAR10.Source: §3.5 · p. 7, Table 2 · p. 7

3.6 Proxies for Model Complexity

  • Across three norms, SOTA SGD yields smaller norms regardless of initialization, while adversarially initialized vanilla SGD has larger norms than its random-initialization counterpart.The authors treat these norms as proxies for generalization and find that they track the observed test-performance pattern.Source: §3.6 · p. 7, Figure 5 · p. 8

3.7 Robustness to Adversarial Examples

  • Adversarially initialized vanilla SGD produces models more vulnerable to small perturbations, whereas SOTA SGD decision boundaries are less prone to attacks, potentially because of better margin.The robustness comparison uses FGSM on ResNet50.Source: §3.7 · p. 8, Figure 6 · p. 8

4 Conclusion

The paper examines whether SGD’s apparent preference for low-complexity minima is enough to explain generalization. It finds that random-label pretraining can lead SGD to poorly generalizing models, while regularization and momentum can help it escape that initialization.

4 Conclusion

  • The paper questions whether SGD’s apparent bias toward low-complexity minima alone explains why overparameterized networks generalize.Source: §4 · p. 8
  • Random-label pretraining can make SGD converge to perfectly training-fitting models with poor generalization, despite its bias toward simple models.The authors report that regularization, including data augmentation, and momentum can help SGD escape this effect and reach models that generalize well.Source: §4 · p. 8

Broader Impacts

The paper highlights regularization’s role in search dynamics, beyond stabilizing the selected model against training-sample fluctuations. It argues that penalizing complex models even when they fit poorly can make simple, well-fitting models more searchable by SGD, while leaving the mechanism open.

Broader Impacts

  • The paper frames regularization’s role as extending beyond stability of the chosen model with respect to training-sample fluctuations.Source: Broader Impacts · p. 8
  • Regularization can affect search dynamics by penalizing complex models even when they fit the data poorly.The authors argue this changes the optimization landscape and makes simple models that fit well more searchable by local methods such as SGD.Source: Broader Impacts · p. 9
  • The authors identify understanding regularization in search dynamics, including model discoverability, as an area for further research.Source: Broader Impacts · p. 9

A CIFAR10 Complete Results

The CIFAR10 appendix captions identify figures on training accuracy, test accuracy, adversarial attacks, and model complexity; the supplied passages do not state their results.

A CIFAR10 Complete Results

B CIFAR100 Complete Results

The CIFAR100 appendix captions identify figures on training accuracy, test accuracy, adversarial attacks, and model complexity; the supplied passages do not state their results.

B CIFAR100 Complete Results

C CINIC10 Complete Results

The CINIC10 results section presents figures for training- and test-accuracy convergence, FGSM, and model complexity.

D Restricted ImageNet Complete Results

The Restricted ImageNet results section presents figures for training- and test-accuracy convergence, FGSM, and model complexity.

Related papers

Loading 1906.02613v2…