Optimization Online


An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

Hamid Reza Feyzmahdavian(hamidrez***at***kth.se)
Arda Aytekin(aytekin***at***kth.se)
Mikael Johansson(mikaelj***at***kth.se)

Abstract: Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel 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 computations. In this paper, we propose an asynchronous mini-batch algorithm for regularized stochastic optimization problems with smooth loss functions that eliminates idle waiting and allows workers to run at their maximal update rates. We show that by suitably choosing the step-size values, the algorithm achieves a rate of the order O(1/sqrt{T}) for general convex regularization functions, and the rate O(1/T) for strongly convex regularization functions, where T is the number of iterations. In both cases, the impact of asynchrony on the convergence rate of our algorithm is asymptotically negligible, and a near-linear speedup in the number of workers can be expected. Theoretical results are confirmed in real implementations on a distributed computing infrastructure.

Keywords: Convex Optimization, Asynchronous algorithms, Composite minimization, Mini-batch, Stochastic optimization

Category 1: Convex and Nonsmooth Optimization

Category 2: Nonlinear Optimization

Citation: Department of Automatic Control, Royal Institute of Technology, KTH, 20150520-FAJ

Download: [PDF]

Entry Submitted: 05/28/2015
Entry Accepted: 05/28/2015
Entry Last Modified: 05/28/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society