Minibatch and accelerated convex optimization with non-asymptotic convergence guarantees
Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
We extend the approximate-proximal point (aprox) family of model-based methods for solving stochastic convex optimization problems, including stochastic subgradient, proximal point, and bundle methods, to the minibatchand accelerated setting.To do so, we propose specific model-based algorithmsand an acceleration scheme for which we provide non-asymptotic convergence guarantees, which are order-optimal in all problem-dependent constants and provide linear speedup in minibatch size, while maintaining the desirable robustness traits (e.g.To stepsize) of the aprox family.We corroborate our theoretical results with empirical testing to demonstrate the gains accuratemodeling, acceleration, and minibatching provide.
