  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.
