<tt>AdaBatchGrad</tt> : combining adaptive batch size and adaptive step size

Abstract 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 nonconvergence 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 convex case in $O(LR^{2}/\varepsilon )$ iterations, analogous to standard gradient descent, and in nonconvex case—in $O(L\varDelta /\varepsilon ^{2})$ iterations. For inexact tests it achieves convergence in convex case in $O(\max \lbrace LR^{2}/\varepsilon , \sigma ^{2} R^{2}/\varepsilon ^{2} \rbrace )$ iterations, and in nonconvex case—in $O(\max \{ L \varDelta / \varepsilon ^{2}, L \varDelta \sigma ^{2} / \varepsilon ^{4} \})$ 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.