Introduction
In deep learning, the relationship between batch size ($b$) and training efficiency is a critical practical concern. Empirical evidence suggests that while increasing batch size initially reduces the number of training steps ($K$) proportionally, this benefit eventually diminishes. This paper provides a rigorous theoretical foundation for this "critical batch size" phenomenon by analyzing Stochastic First-order Oracle (SFO) complexity—the total number of gradient evaluations ($Kb$).
Methods: A Unified Framework
The author introduces a unified theoretical framework that encompasses a wide range of popular optimizers, including SGD, Momentum, AdaGrad, RMSProp, Adam, AMSGrad, and AdaBelief. This is achieved by defining a general algorithm where different optimizers are represented by specific preconditioner matrices ($H_k$).
By analyzing this unified structure, the paper derives upper and lower bounds for the number of steps $K$ as rational functions of the batch size $b$. This mathematical approach allows for a generalized proof of efficiency across diverse optimization strategies.
Theoretical Insights: The Critical Batch Size
The core contribution of this work is the mathematical proof that the SFO complexity function ($Kb$) is convex. As batch size increases, the number of steps $K$ decreases toward a constant floor ($K^*$), but the total computational cost $Kb$ eventually begins to rise after reaching a minimum point.
The "U-shaped" complexity curve identifies the critical batch size ($b_*$ and $b^*$) where training is most computationally efficient. Beyond this point, practitioners face diminishing returns where larger batches lead to higher total gradient evaluations without significantly reducing training time. The paper identifies that as batch size goes to infinity, the number of steps $K$ approaches a constant value, confirming why "infinite" batch sizes do not lead to "zero" steps.
Key Results and Empirical Validation
The theoretical findings were validated through experiments on the CIFAR-10 dataset using a ResNet-20 architecture:
- Adam's Efficiency: Adam exhibited a clear critical batch size at $2^{11}$ (2048), where SFO complexity was minimized.
- Comparison with SGD: Adaptive methods like Adam were found to exploit larger batch sizes more effectively than standard SGD or Momentum, which saw their total costs increase more rapidly with batch size.
- Validation of Empirical Laws: The mathematical bounds presented directly support the "Power Law" observations made in previous large-scale empirical studies by Google Brain and OpenAI.
Conclusion
This research bridges the gap between empirical observations of training dynamics and rigorous optimization theory. By proving the convexity of SFO complexity, it provides a mathematical tool for practitioners to identify the most efficient batch size for nonconvex optimization, balancing hardware utilization with total computational work. Future work may extend this to include hardware-specific constraints like communication overhead and memory bandwidth.
Summary updated