Distributed mirror descent for stochastic learning over rate-limited networks

Matthew Nokleby, Waheed U. Bajwa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We present and analyze two algorithms - termed distributed stochastic approximation mirror descent (D-SAMD) and accelerated distributed stochastic approximation mirror descent (AD-SAMD) - for distributed, stochastic optimization from high-rate data streams over rate-limited networks. Devices contend with fast streaming rates by mini-batching samples in the data stream, and they collaborate via distributed consensus to compute variance-reduced averages of distributed subgradients. This induces a trade-off: Mini-batching slows down the effective streaming rate, but may also slow down convergence. We present two theoretical contributions that characterize this trade-off: (i) bounds on the convergence rates of D-SAMD and AD-SAMD, and (ii) sufficient conditions for order-optimum convergence of D-SAMD and AD-SAMD, in terms of the network size/topology and the ratio of the data streaming and communication rates. We find that AD-SAMD achieves order-optimum convergence in a larger regime than D-SAMD. We demonstrate the effectiveness of the proposed algorithms using numerical experiments.

Original languageEnglish (US)
Title of host publication2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-5
Number of pages5
ISBN (Electronic)9781538612514
DOIs
StatePublished - Mar 9 2018
Event7th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017 - Curacao
Duration: Dec 10 2017Dec 13 2017

Publication series

Name2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017
Volume2017-December

Conference

Conference7th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017
CityCuracao
Period12/10/1712/13/17

ASJC Scopus subject areas

  • Signal Processing
  • Control and Optimization
  • Instrumentation

Fingerprint

Dive into the research topics of 'Distributed mirror descent for stochastic learning over rate-limited networks'. Together they form a unique fingerprint.

Cite this