In this paper, we study the performance of a large family of SGD variants in the smooth nonconvex regime. To this end, we propose a generic and flexible assumption capable of accurate modeling of the second moment of the stochastic gradient. Our assumption is satisfied by a large number of specific variants of SGD in the literature, including SGD with arbitrary sampling, SGD with compressed gradients, and a wide variety of variance-reduced SGD methods such as SVRG and SAGA. We provide a single convergence analysis for all methods that satisfy the proposed unified assumption, thereby offering a unified understanding of SGD variants in the nonconvex regime instead of relying on dedicated analyses of each variant. Moreover, our unified analysis is accurate enough to recover or improve upon the best-known convergence results of several classical methods, and also gives new convergence results for many new methods which arise as special cases. In the more general distributed/federated nonconvex optimization setup, we propose two new general algorithmic frameworks differing in whether direct gradient compression (DC) or compression of gradient differences (DIANA) is used. We show that all methods captured by these two frameworks also satisfy our unified assumption. Thus, our unified convergence analysis also captures a large variety of distributed methods utilizing compressed communication. Finally, we also provide a unified analysis for obtaining faster linear convergence rates in this nonconvex regime under the PL condition.

本文研究了SGD变体在平滑非凸情况下的表现，并提出了一种通用的假设模型来精确建模随机梯度的二阶矩，并给出了所有满足统一假设的方法的单一收敛分析。此外，作者提出了两种新的通用算法框架来处理分布式/联邦非凸优化问题，并说明这些方法均满足他们的统一假设，因此这个统一的收敛分析也包括了许多利用压缩通讯的分布式方法。最后，文章提供了一种在PL条件下获得更快线性收敛速度的统一分析。

用于非凸联邦优化的随机梯度方法的统一分析