Minibatch Random Reshuffling for Smooth Convex Optimization: Batch-Size Dependence, Finite-Population Variance, and Quadratic Growth
\(\)
Random Reshuffling (RR) is the default data-ordering strategy in practice, and it is almost always run with minibatches. The recent theory of Liu shows that single-sample RR dominates SGD in smooth convex optimization for every stepsize below \(2/\hat{L}\), but the role of the batch size has not been worked out. In this note we study minibatch RR with a fixed partition of the \(n\) components into \(m = n/b\) batches and a fresh random batch order in each epoch. We show that this method is exactly Shuffling SGD on \(m\) “batch components”, which lets us transfer the dominance theory of Liu while tracking how the batch size enters every constant. We obtain (i) an epoch-wise convergence rate for minibatch RR valid for all stepsizes \(\eta < 2/\hat{L}_P\), where \(\hat{L}_P \leq \min\{L, m\hat{L}\bar{\}}\) is the maximal smoothness of a batch; (ii) a proof that minibatch RR dominates minibatch SGD on the same batches; (iii) an exact finite-population variance identity showing that, for a uniformly random partition, the effective gradient variance at the optimum is \(\sigma^2_\star \frac{n-b}{b(n-1)}\) per batch; (iv) a precise accounting of what batching does and does not change per epoch: the optimization term is multiplied by \(b\hat{L}_P/\hat{L}\), the variance-driven terms change only by a factor \(\sqrt{(n-b)/(n-1)}\) (resp. its cube root form), and the stepsize regime in which RR strictly beats SGD is enlarged by a factor \(b\); and (v) a sample-complexity bound for functions with quadratic growth obtained by restarting minibatch RR. We also identify the setting that is not covered by our reduction, namely a fresh partition in every epoch, and state it as an open problem.