Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

Understand

Recently, the decentralized optimization problem is attracting growing attention.

• Most existing methods are deterministic with high per-iteration cost and have a convergence rate quadratically depending on the problem condition number.
• Besides, the dense communication is necessary to ensure the convergence even if the dataset is sparse.
• In this paper, we generalize the decentralized optimization problem to a monotone operator root finding problem, and propose a stochastic algorithm named DSBA that (i) converges geometrically with a rate linearly depending on the problem condition number, and (ii) can be implemented using sparse communication only.