An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
2015 (English)In: 2015 54th IEEE Conference on Decision and Control (CDC), IEEE , 2015, 1384-1389 p.Conference paper (Refereed)
Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities, or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting for the slower nodes to complete their work. We propose an asynchronous mini-batch algorithm for regularized stochastic optimization problems that eliminates idle waiting and allows workers to run at their maximal update rates. We show that the time necessary to compute an ϵ-optimal solution is asymptotically O(1/ϵ2), and the algorithm enjoys near-linear speedup if the number of workers is O(1/√ϵ). Theoretical results are confirmed in real implementations on a distributed computing infrastructure.
Place, publisher, year, edition, pages
IEEE , 2015. 1384-1389 p.
Optimization, Convex, Asynchronous optimization, Delay, Stochastic optimization
Engineering and Technology
IdentifiersURN: urn:nbn:se:kth:diva-183457DOI: 10.1109/CDC.2015.7402404ScopusID: 2-s2.0-84962032572ISBN: 978-1-4799-7884-7OAI: oai:DiVA.org:kth-183457DiVA: diva2:911486
QC 201603142016-03-122016-03-122016-03-14Bibliographically approved