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{\sigma}{\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.

我们开发和分析了DASHA：一种新的非凸分布式优化问题方法，同时考虑了通信复杂度和理论oracle。我们的新方法改善了以前的最先进的方法，特别是在有限和期望形式的本地函数的情况下。新的方法发送压缩向量，并且永远不会同步节点，这使得它们对联邦学习更加实用。我们还将结果扩展到满足Polyak-Lojasiewicz条件的情况。在分类和深度学习模型的培训实验中，实践证实了我们的理论。

DASHA：分布式非凸优化，包含通信压缩，最优化 Oracle 复杂度，无须客户端同步