论文标题
DASHA：通过通信压缩，最佳Oracle复杂性，没有客户端同步的分布式非Convex优化
DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization
论文作者
论文摘要
我们开发和分析Dasha：非凸出分布式优化问题的新方法。当节点的局部函数具有有限的和期望形式时，我们的新方法Dasha-page和dasha-sync-MVR提高了Gorbunov等人先前最先进的方法Marina的理论甲骨文和通信复杂性。 （2020）。特别是，要达到epsilon安置点，并以随机的刺激器randk为例，我们的方法计算了最佳梯度$ \ Mathcal {o} \ left（\ frac {\ frac {\ sqrt {m} {m}}}} $ \ MATHCAL {O} \ left（\fracσ{\ varepsilon^{3/2} n} \ right）$分别在有限含量和期望表案例中，同时保持SOTA通信复杂性$ \ MATHCAL {O} {O} {O} \ sqrt {n}} \ right）$。此外，与Marina不同，新方法Dasha，Dasha-page和Dasha-Mvr仅发送压缩向量，并且从不同步节点，这使它们在联合学习方面更加实用。当功能满足Polyak-lojasiewicz条件时，我们将结果扩展到了情况。最后，我们的理论在实践中得到了证实：我们看到非凸形分类和深度学习模型培训的实验有了显着改善。
We develop and analyze DASHA: a new family of methods for nonconvex distributed optimization problems. When the local functions at the nodes have a finite-sum or an expectation form, our new methods, DASHA-PAGE and DASHA-SYNC-MVR, improve the theoretical oracle and communication complexity of the previous state-of-the-art method MARINA by Gorbunov et al. (2020). In particular, to achieve an epsilon-stationary point, and considering the random sparsifier RandK as an example, our methods compute the optimal number of gradients $\mathcal{O}\left(\frac{\sqrt{m}}{\varepsilon\sqrt{n}}\right)$ and $\mathcal{O}\left(\fracσ{\varepsilon^{3/2}n}\right)$ in finite-sum and expectation form cases, respectively, while maintaining the SOTA communication complexity $\mathcal{O}\left(\frac{d}{\varepsilon \sqrt{n}}\right)$. Furthermore, unlike MARINA, the new methods DASHA, DASHA-PAGE and DASHA-MVR send compressed vectors only and never synchronize the nodes, which makes them more practical for federated learning. We extend our results to the case when the functions satisfy the Polyak-Lojasiewicz condition. Finally, our theory is corroborated in practice: we see a significant improvement in experiments with nonconvex classification and training of deep learning models.
