AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Size
Petr Ostroukhov Aigerim Zhumabayeva Chulu Xiang Alexander Gasnikov Martin Takáč Dmitry Kamzolov
This paper presents a novel adaptation of the Stochastic Gradient Descent
(SGD), termed AdaBatchGrad. This modification seamlessly integrates an adaptive
step size with an adjustable batch size. An increase in batch size and a
decrease in step size are well-known techniques to tighten the area of
convergence of SGD and decrease its variance. A range of studies by R. Byrd and
J. Nocedal introduced various testing techniques to assess the quality of
mini-batch gradient approximations and choose the appropriate batch sizes at
every step. Methods that utilized exact tests were observed to converge within
$O(LR^2/\varepsilon)$ iterations. Conversely, inexact test implementations
sometimes resulted in non-convergence and erratic performance. To address these
challenges, AdaBatchGrad incorporates both adaptive batch and step sizes,
enhancing the method's robustness and stability. For exact tests, our approach
converges in $O(LR^2/\varepsilon)$ iterations, analogous to standard gradient
descent. For inexact tests, it achieves convergence in $O(\max\lbrace
LR^2/\varepsilon, \sigma^2 R^2/\varepsilon^2 \rbrace )$ iterations. This makes
AdaBatchGrad markedly more robust and computationally efficient relative to
prevailing methods. To substantiate the efficacy of our method, we
experimentally show, how the introduction of adaptive step size and adaptive
batch size gradually improves the performance of regular SGD. The results imply
that AdaBatchGrad surpasses alternative methods, especially when applied to
inexact tests.