  We present and analyze an algorithm for optimizing smooth and convex or
strongly convex objectives using minibatch stochastic gradient estimates. The
algorithm is optimal with respect to its dependence on both the minibatch size
and minimum expected loss simultaneously. This improves over the optimal method
of Lan (2012), which is insensitive to the minimum expected loss; over the
optimistic acceleration of Cotter et al. (2011), which has suboptimal
dependence on the minibatch size; and over the algorithm of Liu and Belkin
(2018), which is limited to least squares problems and is also similarly
suboptimal with respect to the minibatch size. Applied to interpolation
learning, the improvement over Cotter et al. and Liu and Belkin translates to a
linear, rather than square-root, parallelization speedup.
