Markovian Compression: Looking to the Past Helps Accelerate the Future
stochastic optimization;distributed optimization;compressed communications;Markovian noise
Yes
No ethics review needed.
Please refer to the Weaknesses part.
I consider Markovian compressors to be a novel idea, but it is possible that I have missed some related literature. 

The proposed algorithm is easy to implement and fairly understandable, which might broaden its interest to general readers. 

The math looks correct to me, though I have not checked every detail.
This paper proposed a possible improvement of the random sparsification method in the context of distributed optimization, which is in turn a compression technique aimed at reducing the communication cost. Briefly speaking, random sparsification compresses the data by selecting a subset of coordinates uniformly at random and keeping only these selected coordinates of data. The key idea of the paper is that, instead of using i.i.d. selection of subset, it may help to select the subset with a Markov chain. In this way, more diversity is encouraged by setting a smaller probability to select those coordinates which was just selected in the previous few iterations.
My main concern is that the theoretical analysis does not seem to touch the real advantage of using a Markovian compressor. It appears that the paper resorted to stationarity analysis, but the stationary distribution of the Markov chain simply falls back to the standard random sparsification. It is thus unclear what is gained by a Markovian compressor. Although a better analysis could be challenging, as argued in the paper, the significance of the proposed algorithm would be greatly strengthened if more theoretical insights were provided.
Yes
No ethics review needed.
+ strange referencing in the text: I don't know if this is the standard ICLR referencing, but a lot of text space is lost due to the refs everywhere, that cut also the reading flow.
+ def 1: L-smooth -> L_i-smooth
+ Randm never defined
+ F_tau not defined in Theorem 2. Is this just a constant? That depends on what? 
+ what is "variance reduction" discussed in a whole paragraph?
+ what is the « information sent » axis in fig 1?
+ many linking words missing
Let me start by stating that I am not *at all* an expert in optimisation, even less in distributed setting. I will therefore not judge the novelty of the paper as I have no clue. 
Given this, I have found the paper interesting. The proposed idea is very natural and quite simple. The theoretical guarantees are strong and provide an clear view on convergence properties (I think).
The numerics are convincing.
The paper consider a generic distributed optimisation problem, and proposes a solution to the information bottleneck due to the necessary communication between computing nodes working in parallel. The solution is based on two stochastic compression operators that go beyond simple sparsifiers. Theoretical guarantees are provided on convergences rates in terms of distance to the minimum of the objective. The effect of momentum is also analysed. Numerical tests are then presented on distributed logistic regression and neural networks training.
I was disappointed by the quality of presentation. E.g., the text is sometimes quite cryptic and there are many linking words missing. Some definitions are missing too, and I had to guess a number of times what the authors meant. I recommend making an effort in presentation.
In spite I have found the problem in interesting in itself, it is not clear for me that ICLR is the right place to publish this paper. But the AC and authors probably know more about this than me, this is not a strong view.
Yes
No ethics review needed.
* In line 850, the notation is quite confusing for me. The left-hand side is a matrix and the right hand side sounds like a norm for me. Are there any typos here?
The paper present convergence bounds for the proposed compressors and distributed optimization approaches. There bounds can be valuable for analyzing similar optimization approaches.
This paper proposed two sparsification compressors for distributed optimization problems, where the communications between different devices are first compressed before transmission. Almost all previous compressors do not consider what have been transmitted during the previous iterations. While the paper proposed compressors that consider previous iterations in a Markovian fashion. The paper further proves convergence bounds for the proposed compressors. Some experimental results and numerical examples are presented to show that the proposed compressors result in performance improvements compared with previous approaches.
* The presentation of the proof part need to be improved. In its current form, the proof is difficult to follow. It is suggested that for each inequality, the author may provide a clue that which fact(s) has been used to get the inequality. It may also be helpful that the author provide more proof sketches. 
* It seems that the convergence bounds hold for any unbiased compressors or asymptotic unbiased compressors. Then, how the author justify that BanLast and KAWASAKI are near-optimal among all Markovian type compressors.
* For the experiment part, in my opinion, more experimental results are needed for justifying that the proposed compressors truly outperform the previous random compressors. It is recommend that more experiments with different types of neural networks and more numbers of devices. The distributed optimization approaches are interesting, typically when people want to train large models on massive datasets. So it would be interesting to see that the proposed compressors outperform other approaches on larger training jobs.
Yes
No ethics review needed.
There are various hyperparameters. Although some details on their tuning are provided in Appendix H, please describe the guiding principles in more detail.
The algorithm is simple and looks easy to implement. Convergence of the algorithm is guaranteed by proofs under several assumptions. Practical usefulness is shown experimentally.
This paper proposes a method for improving the performance of distributed optimization mitigating the communication bottleneck. The key idea is to use Markovian compressors in the vanilla Quantized Stochastic Gradient Descent (QSGD) algorithm. In addition, the momentum acceleration method is also used. The proof of convergence is provided and the usefulness of the proposed method is confirmed by experiments.
The key idea of "random sparsification" has already been proposed in the vanilla QSGD in an earlier paper. The contribution of this paper is to introduce Markovian randomness to it. The significance of the contribution is smaller than the prior work although the guarantee of its convergence may be non-trivial to prove.
@inproceedings{
anonymous2024markovian,
title={Markovian Compression: Looking to the Past Helps Accelerate the Future},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=H9oYYou34X},
note={under review}
}
This paper deals with distributed optimization problems that use compressed communication to achieve efficient performance and mitigate the 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. Intuitively, this should accelerate the convergence of optimization methods, as considering previous iterations seems more natural and robust. The compressors are implemented in the vanilla Quantized Stochastic Gradient Descent (QSGD) algorithm. To further improve efficiency and convergence rate, we apply the momentum acceleration method. We prove convergence results for our algorithms with Markovian compressors and show theoretically that the accelerated method converges faster than the basic version. The analysis covers non-convex, Polyak-Lojasiewicz (PL), and strongly convex cases. Experiments are conducted to demonstrate the applicability of the results to distributed data-parallel optimization problems. Practical results demonstrate the superiority of methods utilizing our compressors design over several existing optimization algorithms.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
stochastic optimization distributed optimization compressed communications Markovian noise
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/29ba5c4654aa3086d8e4febb32984cd0135b39fe.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Markovian Compression: Looking to the Past Helps Accelerate the Future
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission