Nondeterminism and Instability in Neural Network Optimization

Cecilia Summers, Michael J. DinneenICML 2021

Introduction

If you’ve ever trained a deep learning model, observed a 0.2% accuracy gain, and wondered, "Is my new architecture actually better, or did I just get a lucky seed?"—you’ve encountered the pervasive problem of nondeterminism.

Neural network training is notoriously unstable. This run-to-run variability makes research expensive, requiring multiple runs to prove statistical significance, and severely harms reproducibility. While random weight initialization is a well-known culprit, other "hidden" sources of randomness exist: data shuffling orders, stochastic data augmentation, and even the way low-level hardware libraries like cuDNN handle floating-point operations.

Remarkably, this instability is so extreme that changing a single bit of a single weight at initialization—a difference of roughly $10^{-11}$—causes as much final model variability as re-initializing the entire network from scratch. This paper reveals that all sources of randomness trigger the same underlying instability and explores how to mitigate this "jitter" for free using clever ensembling techniques.

Isolating the Chaos: Methods and Metrics

To understand the fundamental mechanisms driving this uncertainty, the authors developed a rigorous experimental protocol to isolate and compare different sources of nondeterminism. They held all factors constant while varying exactly one (e.g., keeping the weight initialization seed identical but varying the data shuffling seed).

Instead of relying solely on top-line accuracy, they measured "model diversity" using three key metrics:

  1. Pairwise Disagreement: How often two independently trained models disagree on specific test examples.
  2. Centered Kernel Alignment (CKA): A state-of-the-art method to compare the internal representations and hidden layers of two networks.
  3. Ensemble Gain: The accuracy improvement observed when averaging the predictions of two models.

The study evaluated these metrics across a broad range of tasks, including image classification (CIFAR-10, MNIST, ImageNet using architectures like ResNet and VGG) and language modeling (Penn Treebank using QRNNs).

Key Insights: The Butterfly Effect in Deep Learning

The Equivalence of Randomness

Surprisingly, every source of nondeterminism produces nearly the exact same amount of final model variability and diversity. Whether it is a complete weight re-initialization, a different data shuffle, or a tiny floating-point difference from a low-level library like cuDNN, the resulting variance in accuracy and pairwise disagreement remains remarkably consistent.

Equivalence of nondeterminism sources

Extreme Instability and the "Single Bit" Test

In a striking experiment, the authors trained a baseline model and then trained a second model where they changed only one bit in the least-significant digit of a single weight in the first layer (a change within machine precision, $\sim 10^{-11}$).

The result? On CIFAR-10, a full random initialization led to an accuracy standard deviation (SD) of 0.23%. Changing just one bit led to an SD of 0.21%. The tiny perturbation cascaded through the network, proving that neural network optimization is a highly chaotic system. Furthermore, this instability is tied to network depth: while absent in simple linear models, adding just one hidden layer increases instability by a factor of 10,000.

Timing is Everything (or Isn't)

One might assume that randomness only dictates the final model if introduced at the very start of training, when the loss landscape is steepest. However, the authors found that even if training is kept perfectly deterministic for the first 50 or 100 epochs, introducing randomness later still results in high final variability.

Accuracy SD vs Epoch

Free Mitigation and Future Directions

If nondeterminism is an unavoidable feature of deep learning optimization, how can practitioners cope without multiplying their compute budgets?

The authors tested "Accelerated Ensembling" (using Snapshot Ensembles with cyclic learning rates to save multiple checkpoints during a single run) combined with Test-Time Augmentation (TTA). By averaging predictions over these checkpoints and augmented test images, they successfully reduced run-to-run variability by up to 61% without requiring any additional training time.

Limitations and Future Work: While the paper comprehensively covers CNNs and RNNs, it does not explicitly test massive Transformer architectures (like GPT or ViT), though the fundamental instability likely generalizes. Furthermore, while the paper provides robust empirical proof of this chaos, a stronger theoretical understanding of why the loss landscape behaves this way remains an open question. Finally, extending this analysis to Reinforcement Learning—where random seeds are notoriously influential—represents a highly promising area for future research.

Summary updated

BibTeX
@inproceedings{summers2021nondeterminism,
  author = {Cecilia Summers and Michael J. Dinneen},
  title = {{Nondeterminism and Instability in Neural Network Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
}
Figure