Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model

Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E. Dahl, Christopher J. Shallue, Roger B. Grosse

Abstract

Increasing the batch size is a popular way to speed up neural network training, but beyond some critical batch size, larger batch sizes yield diminishing returns. In this work, we study how the critical batch size changes based on properties of the optimization algorithm, including acceleration and preconditioning, through two different lenses: large scale experiments, and analysis of a simple noisy quadratic model (NQM). We experimentally demonstrate that optimization algorithms that employ preconditioning, specifically Adam and K-FAC, result in much larger critical batch sizes than stochastic gradient descent with momentum. We also demonstrate that the NQM captures many of the essential features of real neural network training, despite being drastically simpler to work with. The NQM predicts our results with preconditioned optimizers, previous results with accelerated gradient descent, and other results around optimal learning rates and large batch training, making it a useful tool to generate testable predictions about neural network optimization.

Introduction

In deep learning, increasing the batch size is the primary mechanism for leveraging parallel hardware like GPUs and TPUs. Ideally, doubling the batch size should halve the number of training steps—a phenomenon known as "perfect scaling." However, every model eventually reaches a "critical batch size" where further increases yield diminishing returns. While previous research has extensively studied this effect for Stochastic Gradient Descent (SGD), this paper explores how more sophisticated algorithmic choices—such as momentum, preconditioning (Adam/K-FAC), and iterate averaging—influence this critical threshold.

The Noisy Quadratic Model (NQM)

To analyze these effects without the prohibitive cost of thousands of large-scale experiments, the researchers utilize the Noisy Quadratic Model (NQM). In this framework, the loss function is modeled as a convex quadratic, and gradients are subject to Gaussian noise. Despite its simplicity, the NQM allows for exact analytical solutions that describe how "risk" (error) evolves over time for various optimizers.

Risk decay in the NQM

The NQM captures the fundamental trade-off in optimization: the speed of convergence versus the steady-state noise. Preconditioning, for instance, speeds up convergence but can amplify noise, necessitating larger batch sizes to maintain stability.

Key Insights: Preconditioning and Scaling

A central finding of this work is that preconditioning acts as a "scaling extender." The NQM predicts, and empirical results confirm, that preconditioned optimizers like K-FAC and Adam possess significantly larger critical batch sizes than standard SGD. This allows for much higher levels of parallelization before hitting the wall of diminishing returns.

Scaling and LR schedules

As shown in Figure 4(a), increasing the preconditioning power (represented by 'pow') shifts the "elbow" of the steps-to-threshold curve to the right, indicating a larger critical batch size. Furthermore, the study confirms that for small batch sizes, the optimal learning rate scales linearly with the batch size, eventually saturating at the critical batch size—a behavior clearly visible in the optimized schedules of Figure 4(c).

Empirical Validation

The authors validated these theoretical predictions across several standard benchmarks, including MNIST, CIFAR-10 (using ResNet and VGG architectures), and the One Billion Word Benchmark (LM1B) using a Transformer model. In the Transformer experiments, K-FAC demonstrated superior scaling, maintaining near-perfect efficiency at batch sizes where SGD and Adam had already plateaued.

Limitations and Future Work

While the NQM is a powerful predictive tool, it relies on several simplifications. It assumes the Hessian and Noise Covariance can be co-diagonalized and focuses entirely on optimization speed rather than the "generalization gap" often observed with large-batch training. Additionally, as a local model, it does not capture the global dynamics of navigating complex, non-convex landscapes. Future research may explore using these insights to dynamically tune batch sizes and learning rates during training.

Summary updated

Abstract

Increasing the batch size is a popular way to speed up neural network training, but beyond some critical batch size, larger batch sizes yield diminishing returns. In this work, we study how the critical batch size changes based on properties of the optimization algorithm, including acceleration and preconditioning, through two different lenses: large scale experiments, and analysis of a simple noisy quadratic model (NQM). We experimentally demonstrate that optimization algorithms that employ preconditioning, specifically Adam and K-FAC, result in much larger critical batch sizes than stochastic gradient descent with momentum. We also demonstrate that the NQM captures many of the essential features of real neural network training, despite being drastically simpler to work with. The NQM predicts our results with preconditioned optimizers, previous results with accelerated gradient descent, and other results around optimal learning rates and large batch training, making it a useful tool to generate testable predictions about neural network optimization.
BibTeX
@inproceedings{zhang2019which,
  author = {Guodong Zhang and Lala Li and Zachary Nado and James Martens and Sushant Sachdeva and George E. Dahl and Christopher J. Shallue and Roger B. Grosse},
  title = {{Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=26ed3q-Dvq6},
}
Figure