Better Mini-Batch Algorithms via Accelerated Gradient Methods
Andrew Cotter, Ohad Shamir, Nati Srebro, Karthik Sridharan · arXiv (Cornell University) · 2011
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.