分析异步联邦学习的性能权衡,提出可量化收敛速度与能耗的理论框架。
Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach
- 构建随机队列网络模型,联合建模客户端计算、通信延迟。
- 推导出更新吞吐量及收敛时间的闭式表达,揭示梯度延迟与速度的权衡。
- 提出优化策略,在EMNIST上减少29%~46%收敛时间、36%~49%能耗。
同步联邦学习因慢速节点问题扩展性差。异步算法通过及时处理更新提升吞吐量,但引入梯度延迟和对快速客户端的偏差。尽管如AsyncSGD和Generalized AsyncSGD等算法通过客户端任务队列缓解偏差,现有分析多忽略底层队列动态,缺乏更新吞吐量与梯度延迟的闭式刻画。为此,本文为Generalized AsyncSGD构建随机队列网络框架,联合建模客户端与服务器的随机计算时间、上行与下行通信延迟。基于乘积形式网络理论,推导出更新吞吐量的闭式表达,以及通信轮次复杂度和达到ε-平稳点所需期望墙钟时间的上界。结果明确刻画了梯度延迟与墙钟收敛速度之间的权衡。进一步扩展框架以量化随机时序下的能耗,揭示收敛速度与能效间的额外权衡。基于此分析,提出基于梯度的路由与并发联合优化策略。EMNIST实验显示,相比AsyncSGD,收敛时间降低29%–46%,能耗减少36%–49%。
原文摘要 · Abstract (English)
Synchronous federated learning scales poorly due to the straggler effect. Asynchronous algorithms increase the update throughput by processing updates upon arrival, but they introduce two fundamental challenges: gradient staleness, which degrades convergence, and bias toward faster clients under heterogeneous data distributions. Although algorithms such as AsyncSGD and Generalized AsyncSGD mitigate this bias via client-side task queues, most existing analyses neglect the underlying queueing dynamics and lack closed-form characterizations of the update throughput and gradient staleness. To close this gap, we develop a stochastic queueing-network framework for Generalized AsyncSGD that jointly models random computation times at the clients and the central server, as well as random uplink and downlink communication delays. Leveraging product-form network theory, we derive a closed-form expression for the update throughput, alongside closed-form upper bounds for both the communication round complexity and the expected wall-clock time required to reach an $ε$-stationary point. These results formally characterize the trade-off between gradient staleness and wall-clock convergence speed. We further extend the framework to quantify energy consumption under stochastic timing, revealing an additional trade-off between convergence speed and energy efficiency. Building on these analytical results, we propose gradient-based optimization strategies to jointly optimize routing and concurrency. Experiments on EMNIST demonstrate reductions of 29%--46% in convergence time and 36%--49% in energy consumption compared to AsyncSGD.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。