Minimax Bounds on Stochastic Batched Convex Optimization

We study the stochastic batched convex optimization problem, in which we use many parallel observations to optimize a convex function given limited rounds of interaction. In each of M rounds, an algorithm may query for information at n points, and after issuing all n queries, it receives unbiased noisy function and/or (sub)gradient evaluations at the n points. After M such rounds, the algorithm must output an estimator. We provide lower and upper bounds on the performance of such batched convex optimization algorithms in zeroth and first-order settings for Lipschitz convex and smooth strongly convex functions. Our rates of convergence (nearly) achieve the fully sequential rate once M = O(d log log n), where d is the problem dimension, but the rates may exponentially degrade as the dimension d increases, in distinction from fully sequential settings.