An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning

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