The Role of Local Steps in Local SGD
The Role of Local Steps in Local SGD
复制标题
DOI：
10.1080/10556788.2023.2241151
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Tiancheng Qin;S. Etesami;César A. Uribe
中科院分区：
文献类型：
--
作者：
Tiancheng Qin;S. Etesami;César A. Uribe
我们考虑了分布式随机优化问题，其中$n$个智能体希望最小化一个由智能体局部函数之和所给出的全局函数，并且当智能体的局部函数定义在非I.I.D.上时，重点讨论了异质环境。数据集。我们研究了局部SGD方法，在该方法中，代理执行一系列局部随机梯度步骤，并偶尔与中心节点通信以改进其局部优化任务。分析了局部步长对局部SGD算法收敛速度和通信复杂度的影响。具体地说，我们不是假定所有通信轮次的局部步数是固定的，而是允许第$i个通信轮次期间的局部步数$H_i$是不同的和任意的数字。我们的主要贡献是刻画了在强凸、凸和非凸局部函数的不同设置下，局部SGD的收敛速度是$HI=1^R$的函数，其中$R$是通信轮数的总和。基于这一刻划，我们给出了序列H_i_{i=1}^R$使得局部SGD可以实现关于工人数目的线性加速的充分条件。此外，对于强凸局部函数，我们提出了一种新的局部步长递增的通信策略，优于已有的通信策略。另一方面，对于凸和非凸局部函数，我们认为固定局部步长是局部SGD的最佳通信策略，并恢复了最新的收敛速度结果。最后，我们通过大量的数值实验验证了我们的理论结果。
We consider the distributed stochastic optimization problem where $n$ agents want to minimize a global function given by the sum of agents' local functions, and focus on the heterogeneous setting when agents' local functions are defined over non-i.i.d. data sets. We study the Local SGD method, where agents perform a number of local stochastic gradient steps and occasionally communicate with a central node to improve their local optimization tasks. We analyze the effect of local steps on the convergence rate and the communication complexity of Local SGD. In particular, instead of assuming a fixed number of local steps across all communication rounds, we allow the number of local steps during the $i$-th communication round, $H_i$, to be different and arbitrary numbers. Our main contribution is to characterize the convergence rate of Local SGD as a function of $\{H_i\}_{i=1}^R$ under various settings of strongly convex, convex, and nonconvex local functions, where $R$ is the total number of communication rounds. Based on this characterization, we provide sufficient conditions on the sequence $\{H_i\}_{i=1}^R$ such that Local SGD can achieve linear speed-up with respect to the number of workers. Furthermore, we propose a new communication strategy with increasing local steps superior to existing communication strategies for strongly convex local functions. On the other hand, for convex and nonconvex local functions, we argue that fixed local steps are the best communication strategy for Local SGD and recover state-of-the-art convergence rate results. Finally, we justify our theoretical results through extensive numerical experiments.