  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.
