Minimax Limits of Adaptive Averaging and Batching in SGD

Averaging SGD checkpoints can improve on the last iterate, while larger batches reduce gradient noise but consume more samples. We ask how much these choices can improve the worst-case guarantee under prescribed learning rates and the fixed SGD update rule. To characterize these limits, we study convex quadratics with curvature at most $L$ and additive IID noise, using convex averages with the same averaging weights in every coordinate. We prove that, for fixed batch sizes, choosing averaging weights from the observed trajectory has the same minimax value as fixing them optimally before training. For joint averaging and batching, integer batch sizes may also adapt to training feedback, with a total sample budget and a maximum batch size per update enforced on every run. The minimax value then equals that of the best randomized plan specifying all batch sizes and averaging weights before training, independently of the instance and samples. These randomized plans can strictly improve on deterministic plans. Both equalities hold for any positive learning-rate sequence, with the worst case taken over all finite dimensions. For inverse-root rates ${\gamma }_t=c/\sqrt{t+1}$, $0<c\le 1/(2L)$, we further prove that the optimal additional risk above the exact noiseless minimax value for the same rates is $\Theta (C^{-1/2}{T}^{-3/4}+\log (T)/T)$, with $T$ updates, $qT$ samples, and maximum batch size $C\ge q$. Here $q>1$ is a fixed integer, and initialization and noise budgets are fixed, positive, and finite. We conclude that these exact values provide benchmarks for comparing learning-rate sequences and bounding the improvement available beyond feasible averaging and batching plans.