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. Additionally, DSBA handles learning problems
like AUC-maximization which cannot be tackled efficiently in the decentralized
setting. Experiments on convex minimization and AUC-maximization validate the
efficiency of our method.

本研究提出了一种名为 DSBA 的随机算法，通过将分散的优化问题推广为单调算子求根问题来解决这一问题，具有线性收敛速度和只需稀疏通讯的优点，同时还能有效地处理像 AUC 最大化这样的学习问题。