Select without Fear: Almost All Minibatch Schedules Generalize Optimally

Source abstract

Abstract. We establish matching upper and lower generalization error bounds for minibatch gradient descent (GD) training with either deterministic or stochastic, data-independent, but otherwise arbitrary batch selection rules, including stochastic GD (SGD) with random reshuffling, SGD with single shuffling, and incremental gradient methods. We consider smooth Lipschitz-convex/nonconvex/strongly convex loss functions and show that classical upper bounds for SGD also hold verbatim for such arbitrary nonadaptive batch schedules, including all deterministic ones. Further, for convex and strongly convex losses we prove matching lower bounds directly on the generalization error uniform over the aforementioned class of batch schedules, showing that all such batch schedules generalize optimally. Last, for smooth (non-Lipschitz) nonconvex losses, we show that full-batch (deterministic) GD is essentially optimal, among all possible batch schedules within the considered class, including all stochastic ones.