Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
KTH, School of Electrical Engineering (EES), Automatic Control.
KTH, School of Electrical Engineering (EES), Automatic Control.ORCID iD: 0000-0003-1725-2901
KTH, School of Electrical Engineering (EES), Automatic Control.
2016 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, ISSN 0018-9286Article in journal (Refereed) Published
Abstract [en]

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/ √ 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 nearlinear speedup in the number of workers can be expected. Theoretical results are confirmed in real implementations on a distributed computing infrastructure.

Place, publisher, year, edition, pages
IEEE , 2016.
Keyword [en]
Optimization, Asynchronous, Delay, Convex, Nonsmooth
National Category
Engineering and Technology
Research subject
Electrical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-182598DOI: 10.1109/TAC.2016.2525015ISI: 000389891100003Scopus ID: 2-s2.0-85003890240OAI: oai:DiVA.org:kth-182598DiVA: diva2:904927
Note

QC 20160311

Available from: 2016-02-20 Created: 2016-02-20 Last updated: 2017-01-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Feyzmahdavian, Hamid RezaAytekin, ArdaJohansson, Mikael
By organisation
Automatic Control
In the same journal
IEEE Transactions on Automatic Control
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 59 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf