Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally
This resolves theoretical uncertainty about batch selection in gradient descent by showing most schedules don't harm generalization, benefiting ML practitioners who worry about batch schedule choices.
The paper establishes that for smooth Lipschitz-convex/nonconvex/strongly-convex loss functions, almost all mini-batch schedules (including deterministic and stochastic data-independent ones) achieve optimal generalization error, with matching upper and lower bounds showing they generalize as well as Stochastic Gradient Descent.
We establish matching upper and lower generalization error bounds for mini-batch Gradient Descent (GD) training with either deterministic or stochastic, data-independent, but otherwise arbitrary batch selection rules. We consider smooth Lipschitz-convex/nonconvex/strongly-convex loss functions, and show that classical upper bounds for Stochastic GD (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. Lastly, 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.