首个实现最优时间复杂度的异步SGD，解决多机计算差异难题
Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
- 提出环形调度机制，动态适应各节点计算速度差异
- 理论证明在任意异构计算下达到时间复杂度下界
- 适合大规模分布式训练场景，尤其当机器性能不均时
异步随机梯度下降（Asynchronous SGD）是分布式机器学习中并行训练的核心方法。然而，当工作节点计算时间存在任意异质性时，其性能会显著下降，导致时间复杂度非最优，且随着节点数量增加效率持续恶化。尽管已有多种异步SGD变体被提出，但最近的研究（Tyurin & Richtárik, NeurIPS 2023）指出，现有方法均未达到最优时间复杂度，文献中存在显著空白。本文提出Ringmaster ASGD，一种新型异步SGD方法，旨在克服这些局限性，并有效应对异步SGD的内在挑战。通过严格的理论分析，我们证明Ringmaster ASGD在任意异构且动态波动的节点计算时间下，能够实现最优时间复杂度。这使其成为首个在该类场景中达到理论时间复杂度下界的异步SGD方法。
原文摘要 · Abstract (English)
Asynchronous Stochastic Gradient Descent (Asynchronous SGD) is a cornerstone method for parallelizing learning in distributed machine learning. However, its performance suffers under arbitrarily heterogeneous computation times across workers, leading to suboptimal time complexity and inefficiency as the number of workers scales. While several Asynchronous SGD variants have been proposed, recent findings by Tyurin & Richtárik (NeurIPS 2023) reveal that none achieve optimal time complexity, leaving a significant gap in the literature. In this paper, we propose Ringmaster ASGD, a novel Asynchronous SGD method designed to address these limitations and tame the inherent challenges of Asynchronous SGD. We establish, through rigorous theoretical analysis, that Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous and dynamically fluctuating worker computation times. This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。