An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums

Understand

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.