提出可调通信与计算的分布式优化方法,实现资源受限下的高效训练。
Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking
- 通过灵活设置每轮本地计算和通信次数,自适应不同系统条件。
- 在非凸场景下达到最优迭代与通信复杂度,逼近理论下界。
- 适合大规模分布式训练,尤其对通信资源受限的场景有显著优势。
本文研究非独立同分布数据下的分布式随机优化问题,关注通信与计算效率之间的权衡。提出FlexGT方法,通过灵活控制每轮的本地更新次数与邻居通信次数,实现对多样化系统资源条件的高效适应。基于统一收敛分析框架,推导出FlexGT在目标函数性质和可调参数依赖下的紧致通信与计算复杂度。进一步引入加速版本Acc-FlexGT,证明在已知图结构的前提下,能实现通信与计算的帕累托最优权衡。特别地,在非凸情形下,Acc-FlexGT达到迭代复杂度$ ilde{ ext{O}}ig((Lσ^2)/(nε^2) + L/(ε oot{4}{1-ρ_W})ig)$与通信复杂度$ ilde{ ext{O}}(L/(ε oot{4}{1-ρ_W}))$,匹配现有下界至对数因子;在强凸情形下,相比已有结果提升$ ilde{ ext{O}}(1/ oot{4}{ε})$倍,其中$ε$为目标精度,$n$为节点数,$L$为Lipschitz常数,$ρ_W$为图连通性,$σ$为随机梯度方差。数值实验验证了理论结果并展示了方法的有效性。
原文摘要 · Abstract (English)
This paper addresses distributed stochastic optimization problems under non-i.i.d. data, focusing on the inherent trade-offs between communication and computational efficiency. To this end, we propose FlexGT, a flexible snapshot gradient tracking method that enables tunable numbers of local updates and neighbor communications per round, thereby adapting efficiently to diverse system resource conditions. Leveraging a unified convergence analysis framework, we derive tight communication and computational complexity for FlexGT with explicit dependence on objective properties and certain tunable parameters. Moreover, we introduce an accelerated variant, termed Acc-FlexGT, and prove that, with prior knowledge of the graph, it achieves Pareto-optimal trade-offs between communication and computation. Particularly, in the nonconvex case, Acc-FlexGT achieves the optimal iteration complexity of $\tilde{\mathcal{O}}\left( \left( Lσ^2 \right) /\left( nε^2 \right) +L/\left( ε\sqrt{1-\sqrt{ρ_W}} \right) \right) $ and optimal communication complexity of $\tilde{\mathcal{O}}\left( L/\left( ε\sqrt{1-\sqrt{ρ_W}} \right) \right)$ for appropriately chosen numbers of local updates, matching existing lower bounds up to logarithmic factors. And, it improves the existing results for the strongly convex case by a factor of $\tilde{\mathcal{O}} \left( 1/\sqrtε \right)$, where $ε$ is the targeted accuracy, $n$ the number of nodes, $L$ the Lipschitz constant, $ρ_W$ the connectivity of the graph, and $σ$ the stochastic gradient variance. Numerical experiments corroborate the theoretical results and demonstrate the effectiveness of the proposed methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。