An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
This provides a more efficient optimization method for machine learning practitioners, though it appears incremental as it builds on existing stochastic optimization frameworks.
The paper tackles the problem of optimizing smooth convex objectives using minibatch stochastic gradients, achieving an algorithm that is optimal in dependence on both minibatch size and minimum expected loss, improving over prior methods with suboptimal dependencies.
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.