Better Mini-Batch Algorithms via Accelerated Gradient Methods
  Mini-batch algorithms have been proposed as a way to speed-up stochastic convex optimization problems. We study how such algorithms can be improved using accelerated gradient methods. We provide a novel analysis, which shows how standard gradient methods may sometimes be insufficient to obtain a significant speed-up and propose a novel accelerated gradient algorithm, which deals with this deficiency, enjoys a uniformly superior guarantee and works well in practice. 
Andrew Cotter, Ohad Shamir, Nathan Srebro, Karthik Sridharan
cs.LG