证明了集中式分布式优化在通信开销下难以随节点数扩展,揭示了根本性瓶颈。
Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction
- 构造新最坏情况函数,建立基于随机和浓度的下界分析框架
- 即使同分布下,通信开销限制了性能随节点数的多对数级提升
- 适用于研究分布式优化可扩展性的研究人员,尤其关注通信瓶颈
我们研究经典联邦学习场景下的集中式分布式优化,$n$ 个工作者联合求解一个 $L$-光滑、$d$ 维非凸函数 $f$ 的 $ε$-驻点,仅能访问方差为 $\sigma^2$ 的无偏随机梯度。每个工作者计算梯度最多耗时 $h$ 秒,服务器到工作者和反向的通信延迟分别为 $\tau_s$ 和 $\tau_w$ 秒/坐标。尽管分布式 SGD 的方差相关运行时间项 $\frac{h \sigma^2 L \Delta}{n \varepsilon^2}$ 随 $n$ 改善,但一旦考虑服务器端通信 $\tau_s$,我们证明:使用无偏随机压缩器的方法无法同时将服务器端通信时间 $\tau_s d \frac{L \Delta}{\varepsilon}$ 和方差相关时间 $\frac{h \sigma^2 L \Delta}{\varepsilon^2}$ 优于 $n$ 的多对数级别地改善,即便在同分布(i.i.d.)假设下亦如此。为此,我们构造新的“最坏情况”函数并发展新下界框架,将分析归约为随机和的浓度问题,并给出相应浓度界。结果揭示了分布式优化在通信约束下的根本性可扩展性局限。
原文摘要 · Abstract (English)
We consider centralized distributed optimization in the classical federated learning setup, where $n$ workers jointly find an $\varepsilon$-stationary point of an $L$-smooth, $d$-dimensional nonconvex function $f$, having access only to unbiased stochastic gradients with variance $σ^2$. Each worker requires at most $h$ seconds to compute a stochastic gradient, and the communication times from the server to the workers and from the workers to the server are $τ_{s}$ and $τ_{w}$ seconds per coordinate, respectively. One of the main motivations for distributed optimization is to achieve scalability with respect to $n$. For instance, it is well known that the distributed version of SGD has a variance-dependent runtime term $\frac{h σ^2 L Δ}{n \varepsilon^2},$ which improves with the number of workers $n,$ where $Δ= f(x^0) - f^*,$ and $x^0 \in R^d$ is the starting point. Similarly, using unbiased sparsification compressors, it is possible to reduce both the variance-dependent runtime term and the communication runtime term. However, once we account for the communication from the server to the workers $τ_{s}$, we prove that it becomes infeasible to design a method using unbiased random sparsification compressors that scales both the server-side communication runtime term $τ_{s} d \frac{L Δ}{\varepsilon}$ and the variance-dependent runtime term $\frac{h σ^2 L Δ}{\varepsilon^2},$ better than poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution. To establish this result, we construct a new "worst-case" function and develop a new lower bound framework that reduces the analysis to the concentration of a random sum, for which we prove a concentration bound. These results reveal fundamental limitations in scaling distributed optimization, even under the homogeneous assumption.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。