Markovian Compression: Looking to the Past Helps Accelerate the Future

Andrey Veprikov, Vladimir Solodkin, Mikhail Rudakov, Petr Babkin, Aleksandr Beznosikov
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:6953-6998, 2026.

Abstract

This paper deals with distributed optimization problems that use compressed communication to achieve efficient performance and mitigate communication bottleneck. We propose a family of compression schemes in which operators transform vectors fed to their input according to a {Markov} chain, i.e. the stochasticity of the compressors depends on previous iterations. The compressors are implemented in the vanilla Quantized Stochastic Gradient Descent (QSGD) algorithm, and, to further improve the efficiency and convergence rate, in the momentum accelerated QSGD. We provide convergence results for our algorithms with Markovian compressors, the analysis covers non-convex, {Polyak-Lojasiewicz}, and strongly convex cases. To demonstrate the applicability of our approach to distributed data-parallel optimization problems, we conduct experiments on the {CIFAR-10} and GLUE datasets with the Resnet-18 and DeBERTaV3 models. Practical results show the superiority of methods that use our compressor design over existing schemes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-veprikov26a, title = {Markovian Compression: Looking to the Past Helps Accelerate the Future}, author = {Veprikov, Andrey and Solodkin, Vladimir and Rudakov, Mikhail and Babkin, Petr and Beznosikov, Aleksandr}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {6953--6998}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/veprikov26a/veprikov26a.pdf}, url = {https://proceedings.mlr.press/v337/veprikov26a.html}, abstract = {This paper deals with distributed optimization problems that use compressed communication to achieve efficient performance and mitigate communication bottleneck. We propose a family of compression schemes in which operators transform vectors fed to their input according to a {Markov} chain, i.e. the stochasticity of the compressors depends on previous iterations. The compressors are implemented in the vanilla Quantized Stochastic Gradient Descent (QSGD) algorithm, and, to further improve the efficiency and convergence rate, in the momentum accelerated QSGD. We provide convergence results for our algorithms with Markovian compressors, the analysis covers non-convex, {Polyak-Lojasiewicz}, and strongly convex cases. To demonstrate the applicability of our approach to distributed data-parallel optimization problems, we conduct experiments on the {CIFAR-10} and GLUE datasets with the Resnet-18 and DeBERTaV3 models. Practical results show the superiority of methods that use our compressor design over existing schemes.} }
Endnote
%0 Conference Paper %T Markovian Compression: Looking to the Past Helps Accelerate the Future %A Andrey Veprikov %A Vladimir Solodkin %A Mikhail Rudakov %A Petr Babkin %A Aleksandr Beznosikov %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-veprikov26a %I PMLR %P 6953--6998 %U https://proceedings.mlr.press/v337/veprikov26a.html %V 337 %X This paper deals with distributed optimization problems that use compressed communication to achieve efficient performance and mitigate communication bottleneck. We propose a family of compression schemes in which operators transform vectors fed to their input according to a {Markov} chain, i.e. the stochasticity of the compressors depends on previous iterations. The compressors are implemented in the vanilla Quantized Stochastic Gradient Descent (QSGD) algorithm, and, to further improve the efficiency and convergence rate, in the momentum accelerated QSGD. We provide convergence results for our algorithms with Markovian compressors, the analysis covers non-convex, {Polyak-Lojasiewicz}, and strongly convex cases. To demonstrate the applicability of our approach to distributed data-parallel optimization problems, we conduct experiments on the {CIFAR-10} and GLUE datasets with the Resnet-18 and DeBERTaV3 models. Practical results show the superiority of methods that use our compressor design over existing schemes.
APA
Veprikov, A., Solodkin, V., Rudakov, M., Babkin, P. & Beznosikov, A.. (2026). Markovian Compression: Looking to the Past Helps Accelerate the Future. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:6953-6998 Available from https://proceedings.mlr.press/v337/veprikov26a.html.

Related Material