On the equivalence of different adaptive batch size selection strategies for stochastic gradient descent methods

In this study, we demonstrate that the norm test and inner product/orthogonality test presented in citeBol18 are equivalent in terms of the convergence rates associated with Stochastic Gradient Descent (SGD) methods if ε2=θ2+nu2 with specific choices of θ and nu. Here, ε controls the relative statistical error of the norm of the gradient while θ and nu control the relative statistical error of the gradient in the direction of the gradient and in the direction orthogonal to the gradient, respectively. Furthermore, we demonstrate that the inner product/orthogonality test can be as inexpensive as the norm test in the best case scenario if θ and nu are optimally selected, but the inner product/orthogonality test will never be more computationally affordable than the norm test if ε2=θ2+nu2. Finally, we present two stochastic optimization problems to illustrate our results.