An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums

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 \textbf{A}ccelerated \textbf{D}ecentralized stochastic algorithm for \textbf{F}inite \textbf{S}ums named ADFS, which uses local stochastic proximal updates and randomized pairwise communications between nodes. On $n$ machines, ADFS learns from $nm$ 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.

Code available in source files. arXiv admin note: substantial text overlap with arXiv:1901.09865

References in corpus (8)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Revisiting Distributed Synchronous SGD
• Don't Use Large Mini-Batches, Use Local SGD
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• D${}^2$: Decentralized Training over Decentralized Data
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Communication trade-offs for synchronized distributed SGD with large step size

Cited by in corpus (11)

• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction
• Explicit Regularization of Stochastic Gradient Methods through Duality
• Decentralized Learning with Lazy and Approximate Dual Gradients
• Heavy-Tail Phenomenon in Decentralized SGD
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
• Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method
• ${\text{A}}^2{\text{CiD}}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning