Minimization of Stochastic First-order Oracle Complexity of Adaptive Methods for Nonconvex Optimization

Hideaki Iiduka

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$).

Table 1: Preconditioner definitions for various optimization methods within the unified framework.

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.

Figure 1: Theoretical relationship between batch size $b$, step count $K$ (left), and total SFO complexity $Kb$ (right).

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

Abstract

Numerical evaluations have definitively shown that, for deep learning optimizers such as stochastic gradient descent, momentum, and adaptive methods, the number of steps needed to train a deep neural network halves for each doubling of the batch size and that there is a region of diminishing returns beyond the critical batch size. In this paper, we determine the actual critical batch size by using the global minimizer of the stochastic first-order oracle (SFO) complexity of the optimizer. To prove the existence of the actual critical batch size, we set the lower and upper bounds of the SFO complexity and prove that there exist critical batch sizes in the sense of minimizing the lower and upper bounds. This proof implies that, if the SFO complexity fits the lower and upper bounds, then the existence of these critical batch sizes demonstrates the existence of the actual critical batch size. We also discuss the conditions needed for the SFO complexity to fit the lower and upper bounds and provide numerical results that support our theoretical results.
BibTeX
@misc{iiduka2021minimization,
  author = {Hideaki Iiduka},
  title = {{Minimization of Stochastic First-order Oracle Complexity of Adaptive Methods for Nonconvex Optimization}},
  year = {2021},
  eprint = {2112.07163},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.07163},
}
Figure