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 decentralized
communications between nodes. On $n$ machines, ADFS minimizes the objective
function with $nm$ samples in the same time it takes optimal algorithms to
optimize 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 give a lower bound of
complexity to show that ADFS is optimal among decentralized algorithms. To
derive ADFS, we first develop an extension of the accelerated proximal
coordinate gradient algorithm to arbitrary sampling. Then, we apply this
coordinate descent algorithm to a well-chosen dual problem based on an
augmented graph approach, leading to the general ADFS algorithm. We illustrate
the improvement of ADFS over state-of-the-art decentralized approaches with
experiments.

本文提出了一种名为 ADFS 的高效分布式算法，利用局部碰撞更新和节点之间的分布式通信，在单机上运行时比现代加速随机算法要慢，但在 n 个机器上最小化目标函数与在一个机器上 m 个样本的最优算法相同的时间内完成。我们证明了 ADFS 是分散化算法中最佳的，并通过实验证明了 ADFS 相对于现有方法的改进。