We study the MARINA method of Gorbunov et al (2021) -- the current state-of-the-art distributed non-convex optimization method in terms of theoretical communication complexity. Theoretical superiority of this method can be largely attributed to two sources: the use of a carefully engineered biased stochastic gradient estimator, which leads to a reduction in the number of communication rounds, and the reliance on {\em independent} stochastic communication compression operators, which leads to a reduction in the number of transmitted bits within each communication round. In this paper we i) extend the theory of MARINA to support a much wider class of potentially {\em correlated} compressors, extending the reach of the method beyond the classical independent compressors setting, ii) show that a new quantity, for which we coin the name {\em Hessian variance}, allows us to significantly refine the original analysis of MARINA without any additional assumptions, and iii) identify a special class of correlated compressors based on the idea of {\em random permutations}, for which we coin the term Perm$K$, the use of which leads to $O(\sqrt{n})$ (resp. $O(1 + d/\sqrt{n})$) improvement in the theoretical communication complexity of MARINA in the low Hessian variance regime when $d\geq n$ (resp. $d \leq n$), where $n$ is the number of workers and $d$ is the number of parameters describing the model we are learning. We corroborate our theoretical results with carefully engineered synthetic experiments with minimizing the average of nonconvex quadratics, and on autoencoder training with the MNIST dataset.
翻译:我们研究了Gorbunov等人(2021年)的MARINA方法,这是目前最先进的非Convex优化法,在理论通信复杂度方面,该方法的理论优势主要可归因于两个来源:使用精心设计的偏向性随机梯度估测器,这导致通信轮数的减少,以及依赖“独立”的通信压缩操作器,这导致每轮通信中传输的比特数量减少。在本文中,我们扩展了MARINA理论,以支持范围更广得多的潜在 $ em相关值的压缩器,将这种方法的覆盖范围扩大到经典独立压缩器设置之外,二)表明,新数量(我们为此命名为 em Hesian 差异值),使我们能够在不附加任何假设的情况下大大改进对MARINA的原始分析,以及基于“随机”概念,我们用“美元”和“美元(美元)的数学”的模型来记录“美元”和“美元(美元)的数学”数据。