`

Timezone: »

 
Poster
An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
Blake Woodworth · Nathan Srebro

Thu Dec 09 12:30 AM -- 02:00 AM (PST) @ None #None

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, which is insensitive to the minimum expected loss; over the optimistic acceleration of Cotter et al., which has suboptimal dependence on the minibatch size; and over the algorithm of Liu and Belkin, which is limited to least squares problems and is also similarly suboptimal. Applied to interpolation learning, the improvement over Cotter et al.~and Liu and Belkin translates to a linear, rather than square-root, parallelization speedup.

Author Information

Blake Woodworth (TTIC)
Nathan Srebro (University of Toronto)

More from the Same Authors