从马尔可夫链视角分析去中心化SGD，揭示收敛机制与线性加速规律。
Tight Analysis of Decentralized SGD: A Markov Chain Perspective
- 将去中心化SGD迭代视为马尔可夫链，解析其收敛行为。
- 局部参数方差与客户端数量成反比，实现线性加速。
- 适用于研究分布式优化中的通信拓扑影响与异构性分析。
我们提出一种新型分析方法，将常步长的去中心化随机梯度下降（DSGD）算法迭代过程建模为马尔可夫链。证明了DSGD收敛至一个平稳分布，其偏差在首阶上可分解为两部分：一部分源于去中心化结构（随图谱间隙和客户端异构性增长），另一部分源于随机性。令人惊讶的是，局部参数的方差在首阶上与客户端数量成反比，无论网络拓扑如何，即使最终未对客户端迭代值进行平均也成立。基于此分析，我们得到了客户端局部迭代的非渐近收敛界，证实了DSGD在客户端数量上具有线性加速能力，且网络拓扑仅影响高阶项。
原文摘要 · Abstract (English)
We propose a novel analysis of the Decentralized Stochastic Gradient Descent (DSGD) algorithm with constant step size, interpreting the iterates of the algorithm as a Markov chain. We show that DSGD converges to a stationary distribution, with its bias, to first order, decomposable into two components: one due to decentralization (growing with the graph's spectral gap and clients' heterogeneity) and one due to stochasticity. Remarkably, the variance of local parameters is, at the first-order, inversely proportional to the number of clients, regardless of the network topology and even when clients' iterates are not averaged at the end. As a consequence of our analysis, we obtain non-asymptotic convergence bounds for clients' local iterates, confirming that DSGD has linear speed-up in the number of clients, and that the network topology only impacts higher-order terms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。