

A few remarks are in order.

From the result in the corollary above, it is easy to see that the optimal choice of batch size is \(m=\Theta (n)\) , and this in turn ensures an \(O\left(\frac{1}{n}\right)\)  rate of convergence for the stochastic gradient algorithm REF . With a biased derivative estimation scheme in a slightly different context, the authors in [1]} show that an increasing batch size is necessary for the error of gradient descent type algorithm to vanish. Finally, the \(O(1/n)\)  bound in Theorem REF , which is for a setting where gradient estimates are biased, matches the minimax complexity result for strongly convex optimization with a stochastic first order oracle, cf. [2]}.
