高效采样少数代理可带动整体收敛，打破性能瓶颈
Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD
- 分析统一分布式SGD中代理动态对收敛的影响
- 少数高效采样代理可超越多数中等策略代理
- 揭示采样策略与网络性能的非线性关系
分布式学习在异构代理间训练机器学习模型的同时保持数据隐私至关重要。本文对统一分布式SGD（UD-SGD）进行渐近分析，涵盖去中心化SGD、联邦学习中的本地SGD及通信间隔增大的场景。研究考察了i.i.d.采样、洗牌和马尔可夫采样等不同采样策略对收敛速度的影响，基于中心极限定理下代理动态对极限协方差矩阵的作用。结果不仅验证了线性加速和渐近网络无关性等既有理论，还从理论上和实验上表明，个别代理采用高效采样策略可显著提升整体收敛性能。仿真显示，少数使用高效采样策略的代理可实现或超过多数采用中等改进策略代理的性能，为传统聚焦最差代理的分析提供了新视角。
原文摘要 · Abstract (English)
Distributed learning is essential to train machine learning algorithms across heterogeneous agents while maintaining data privacy. We conduct an asymptotic analysis of Unified Distributed SGD (UD-SGD), exploring a variety of communication patterns, including decentralized SGD and local SGD within Federated Learning (FL), as well as the increasing communication interval in the FL setting. In this study, we assess how different sampling strategies, such as i.i.d. sampling, shuffling, and Markovian sampling, affect the convergence speed of UD-SGD by considering the impact of agent dynamics on the limiting covariance matrix as described in the Central Limit Theorem (CLT). Our findings not only support existing theories on linear speedup and asymptotic network independence, but also theoretically and empirically show how efficient sampling strategies employed by individual agents contribute to overall convergence in UD-SGD. Simulations reveal that a few agents using highly efficient sampling can achieve or surpass the performance of the majority employing moderately improved strategies, providing new insights beyond traditional analyses focusing on the worst-performing agent.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。