  Distributed optimization algorithms have emerged as a superior approaches for
solving machine learning problems. To accommodate the diverse ways in which
data can be stored across devices, these methods must be adaptable to a wide
range of situations. As a result, two orthogonal regimes of distributed
algorithms are distinguished: horizontal and vertical. During parallel
training, communication between nodes can become a critical bottleneck,
particularly for high-dimensional and over-parameterized models. Therefore, it
is crucial to enhance current methods with strategies that minimize the amount
of data transmitted during training while still achieving a model of similar
quality. This paper introduces two accelerated algorithms with various
compressors, working in the regime of horizontal and vertical data division. By
utilizing a momentum and variance reduction technique from the Katyusha
algorithm, we were able to achieve acceleration and demonstrate one of the best
asymptotics for the horizontal case. Additionally, we provide one of the first
theoretical convergence guarantees for the vertical regime. Our experiments
involved several compressor operators, including RandK and PermK, and we were
able to demonstrate superior practical performance compared to other popular
approaches.
