Better Mini-Batch Algorithms via Accelerated Gradient Methods
Andrew Cotter, Ohad Shamir, Nathan Srebro et al. · 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.
Cited by 139 works. doi:10.48550/arxiv.1106.4574 Open-access PDF
Authors
References
- The Tradeoffs of Large-Scale Learning
- Smooth minimization of non-smooth functions
- Pegasos: primal estimated sub-gradient solver for SVM
- Robust Stochastic Approximation Approach to Stochastic Programming
- Mirror descent and nonlinear projected subgradient methods for convex optimization
- Primal-dual subgradient methods for convex problems
- SVM optimization
- A method for unconstrained convex minimization problem with the rate of convergence o(1/k^2)
- Dual Averaging Method for Regularized Stochastic Learning and Online Optimization
- Online Learning: Theory, Algorithms, and Applications