提出Scaffold新分析框架，揭示其在随机梯度下可线性加速但存在固有偏差。
Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
- 构建全局参数与控制变量的马尔可夫链，证明其收敛性
- 在客户端数增加时实现近似线性加速，步长更高阶项影响显著
- 揭示算法存在不随客户端增加而衰减的高阶偏差，适合改进研究
本文为Scaffold算法提出一种新分析方法，该算法是处理联邦学习中数据异构性的主流方法。尽管其在确定性设置下（局部控制变量缓解客户端漂移）的收敛性已有充分研究，但随机梯度更新对其性能的影响仍不明确。为此，我们首先证明其全局参数与控制变量构成一个马尔可夫链，并在Wasserstein距离下收敛至平稳分布。基于此结果，我们证明Scaffold在客户端数量上达到近似线性加速，仅受步长的高阶项影响。然而，我们的分析也揭示，Scaffold仍存在类似FedAvg的高阶偏差，且不会随客户端数量增加而减少。这表明在随机联邦学习算法设计上仍有改进空间。
原文摘要 · Abstract (English)
This paper proposes a novel analysis for the Scaffold algorithm, a popular method for dealing with data heterogeneity in federated learning. While its convergence in deterministic settings--where local control variates mitigate client drift--is well established, the impact of stochastic gradient updates on its performance is less understood. To address this problem, we first show that its global parameters and control variates define a Markov chain that converges to a stationary distribution in the Wasserstein distance. Leveraging this result, we prove that Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size. Nevertheless, our analysis reveals that Scaffold retains a higher-order bias, similar to FedAvg, that does not decrease as the number of clients increases. This highlights opportunities for developing improved stochastic federated learning algorithms
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。