<p>Distributed optimization algorithms have emerged as a powerful approach for solving applied problems, including the training of machine learning models. To accommodate the diverse ways in which information can be stored across devices, it is essential that these methods are adaptable to a wide range of scenarios. At the highest level, two orthogonal regimes of data partitioning are distinguished: horizontal partitioning (sample-based division) and vertical partitioning (feature-based division). However, regardless of how information is distributed among workers, communication between them can become a critical bottleneck during parallel training, particularly in the case of high-dimensional and over-parameterized models. Therefore, it is crucial to enhance existing methods with strategies that minimize the amount of data transmitted during the optimization procedure while still achieving results of comparable quality. This paper introduces two accelerated algorithms that incorporate various compression techniques, operating under both horizontal and vertical partitioning regimes. By adapting the variance reduction mechanism from non-distributed stochastic methods, we achieve state-of-the-art asymptotic performance for the horizontal partitioning case. Additionally, we provide one of the first theoretical convergence guarantees for the vertical partitioning regime. In experiments, we demonstrate superior practical performance compared to other popular approaches that employ compression.</p>