An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums

arXiv1905.11394MaRDI QIDQ6319461

Author name not available (Why is that?)

Publication date: 27 May 2019

Abstract: Modern large-scale finite-sum optimization relies on two key aspects: distribution and stochastic updates. For smooth and strongly convex problems, existing decentralized algorithms are slower than modern accelerated variance-reduced stochastic algorithms when run on a single machine, and are therefore not efficient. Centralized algorithms are fast, but their scaling is limited by global aggregation steps that result in communication bottlenecks. In this work, we propose an efficient extbf{A}ccelerated extbf{D}ecentralized stochastic algorithm for extbf{F}inite extbf{S}ums named ADFS, which uses local stochastic proximal updates and randomized pairwise communications between nodes. On

n

machines, ADFS learns from

n m

samples in the same time it takes optimal algorithms to learn from

m

samples on one machine. This scaling holds until a critical network size is reached, which depends on communication delays, on the number of samples

m

, and on the network topology. We provide a theoretical analysis based on a novel augmented graph approach combined with a precise evaluation of synchronization times and an extension of the accelerated proximal coordinate gradient algorithm to arbitrary sampling. We illustrate the improvement of ADFS over state-of-the-art decentralized approaches with experiments.

Has companion code repository: https://github.com/HadrienHx/ADFS_NeurIPS

This page was built for publication: An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6319461)