Don't Compress Gradients in Random Reshuffling: Compress Gradient Differences

On the main hypothesis that reducing the compression variance brings improvement, it is yet unclear whether this is also a necessary condition. The paper does provide a convergence result for Q-RR that does not improve over Q-SGD; but what would be preferable is a lower bound that shows how Q-RR can not improve over Q-SGD in a worst-case example. This is currently missing to complete the picture. While the experimental result presented in the main text also support the hypothesis, there are some caveats (see next point).

As the reviewer fairly notices, we provide only upper convergence bounds: according to them Q-RR is not better than QSGD, and DIANA-RR has a better worst-case guarantee than both methods and the original DIANA. Deriving algorithmic dependent lower-bounds for Q-RR is indeed an interesting research question that would complement our work and support the hypothesis. Nevertheless, our experiments also support our hypothesis, as the reviewer noticed. Therefore, the importance of deriving such a lower bound is minor. Moreover, this might require a lot of work deserving another paper since we are not aware of any algorithmic-dependent lower bounds in the literature on distributed optimization with compression.

The results for CIFAR10 in the main text suggest that Q-RR is on par with Q-SGD. However, in the appendix it becomes clear that this experiment refers to only training the last layer (see Fig. 12). When training the whole network (Fig. 10), the results suggest that Q-RR is actually much better than Q-SGD, and the gap is roughly equal to DIANA vs. DIANA-RR. The main text does not mention this, so this result is hard to find if it's only presented in the appendix. I would ask the authors to clarify this part in the main text - in particular, because this result weakens one of the hypotheses that the DIANA technique is necessary to get improvements (at least for nonconvex problems, like the ResNet example is). If I missed something important here, please let me know - I am happy to discuss details.

Although we do not have formal proof explaining this phenomenon, we conjecture that this can be related to the significant over-parameterization occurring during the training of a large model on a relatively small dataset. That is, the model can almost perfectly fit the training data on all clients, leading to the decrease of the heterogeneity parameter $\zeta_\ast$. In this case, there is no need for shifts since the variance coming from compression naturally goes to zero, and the complexities of QSGD and DIANA match (see Table 1). In this situation, Q-RR performs better than QSGD since the compression does not spoil the convergence of RR. Therefore, DIANA-type shifts are not always necessary to get improvements. Nevertheless, we conjecture that they are necessary when the datasets are larger and more complex (since in this case the models do not perfectly fit the data).

The logistic regression examples show a clearer picture, but only three datasets are tested, and all of them are very low-dimensional (). I would suggest to add more high-dimensional datasets, or other deep learning experiments to have more insight whether there is a difference between Q-SGD and Q-RR.

We agree with the reviewer that the additional experiments are important and would strengthen the paper. We will do our best to include them in the final version. However, we also would like to emphasize that our work is primarily theoretical, and the experiments are mainly needed to illustrate and support our theoretical findings.

All theoretical results only apply to strongly convex, smooth functions. While this is a standard framework for optimization analysis, it is very far from most modern machine learning applications, thus restricting the applicability of the results for such nonconvex, nonsmooth problems.

We agree that many practically important problems are non-convex. However, the main goal of our paper was to understand how to combine RR and unbiased compression properly. This research question is not related to the convexity of the problem, and it was natural for us to investigate it in the strongly convex case first. Moreover, in many cases, convex optimization serves as inspiration for methods that work well even for non-convex problems. For example, the well-known Adam uses a momentum trick. However, we know that momentum does not theoretically improve convergence in non-convex cases.. Moreover, momentum was initially proposed by Boris Polyak to accelerate the convergence rate for GD in a convex setup (more specifically, for strongly convex quadratics). Next, very successful optimizers for DL proposed recently, such as D-Adaptation [1], Prodigy [2], and Schedule-Free SGD [3], were designed and analyzed for convex problems only. Nevertheless, they work well in the training of neural networks. To sum up, we want to say the initial step in the direction considered by us is natural.

[1] Defazio & Mishchenko. Learning-Rate-Free Learning by D-Adaptation. ICML 2023

[2] Mishchenko & Defazio. Prodigy: An expeditiously adaptive parameter-free learner. ICML 2024

[3] Defazio et al. The Road Less Scheduled. arXiv preprint arXiv:2405.15682

wait... I'm just curious and a little bit confused: why exactly are you using FP64 for training? If all the calculation is in FP64, then it is not surprising that the computational demands are significant. However, this kind of setting is very uncommon in academia. Even for lower level hardwares such as consumer-level GPUs like RTX3080/4080, FP32 or FP16 are commonly used. I've been in academia and I also have experience in limited budgets, but I haven't heard any commonly used hardware (in both CPU and GPU) that doesn't support FP32.

And honestly, from my own experience, even using pure CPU (yes my lab is very poor) to train resnet-18 on cifar-10, it only takes 1-2 minutes for each epoch. So from my point of view, the common reason why people do not scale resnet18@cifar10 to 100 clients is that the computation is too fast and scaling up beyond 10 clients is meaningless. And I'm pretty sure that vgg@cifar100 is feasible in academia.

Dear Reviewer,

Thank you for your insightful comments.

We opted for FP64 (IEEE 754) due to its superior numerical stability compared to FP32, FP16, and BFloat16. Our primary intention in using FP64 was to address potential numerical instabilities that can arise with FP32. While FP32 and FP16 are commonly used for inference tasks, the choice of precision for training depends on the specific requirements of the task. In certain cases, FP32 may be sufficient, but for others, FP64 is necessary to ensure stability.

The performance gain from switching from FP64 to FP32 can indeed vary based on the GPU model. For instance, the NVIDIA A100 40GB GPU used in our experiments offers approximately a two-fold increase in computational throughput with FP32 compared to FP64. In contrast, GPUs such as the RTX 3080 that you referred to may exhibit a more substantial difference, with potential speedups of up to 64 times. The choice of precision is influenced by the specific architecture of the GPU, and these characteristics can differ across various GPU models and updates.

In our simulation involving 10 clients sharing a common dataset, we ran 2000 rounds/epochs for fine-tuning. Based on your estimate of 2 minutes per epoch, the total computation time would be approximately 66 hours per run (2 minutes/epoch × 2000 epochs = 66 hours). Taking into account the grid search with 18 preset learning rates, 5 sets of decay parameters, and 4 algorithms, the total estimated computation time would be around 23,760 hours (66 hours × 18 × 5 × 4). We recognize that this represents a substantial amount of time.

Our simulation infrastructure was designed to maximize computational efficiency, and we would be pleased to provide additional details about the actual simulation time in the camera-ready version of the paper.

Additionally, we understand there may have been some misunderstanding regarding the feasibility of comparing multiple algorithms. To clarify, conducting a comprehensive comparison involving four algorithms with an extensive grid of hyperparameters is particularly challenging for models larger than ResNet-18 on CIFAR10. To cover 23,760 hours of training would indeed require approximately 40 GPUs running continuously for about 25 days. Nonetheless, we have conducted numerous experiments to ensure a thorough and fair comparison, as illustrated in Figure 13 on page 24.

Thank you once again for your valuable feedback. We hope this clarification addresses your concerns.

From a technical perspective, my main concern is that I am unsure how challenging it is to realise random reshuffling in practice.

RR is a well-known technique exploited in many applications: for ML training, for SGD, Monte Carlo methods, etc. For example, in many ML frameworks, such as TensorFlow or Pytorch, random reshuffling of the training dataset is performed at the beginning of each epoch to ensure that the models do not learn the order of training data.

The specific implementation and initialization of random reshuffling depend on the programming language, library, or framework being used. Most modern data processing and machine learning libraries provide built-in functions for random reshuffling, making it easy to integrate into various workflows.

As I understand, using the authors' algorithms does not allow the server to start the next training epoch before every client sends updates for the current epoch. This sounds like a severe limitation, as in the worst case, some of the clients might drop out (e.g. due to connectivity issues) and never send any updates, causing the training loop to get stuck. Could the authors please comment on this?

Partial Participation and asynchronous setting are important aspects of distributed optimization. However, we believe that one paper cannot cover all possible aspects of the field. Otherwise, each paper would be several hundreds of pages. In this work, we focus on data sampling but not client sampling. We can extend our results to the partial participation setting but we believe that it will be more complicated for readers to understand the results. We believe that for the sake of readability, the paper should be focused on one or two particular ideas, and the questions that we address (how to combine RR, unbiased compression, and, optionally, local steps) are challenging and interesting on their own.

The other issue with the paper is the writing needs to be improved significantly. While the introduction section is well-written, it is three pages long, which means there is not enough space to expose the large amount of content that the authors wish to include at the level of formality they want to use. Concretely, the paper goes from a high-level discussion in the introduction section to being immensely technical in section two, with many new quantities and notations introduced without explaining what they represent. For example, what is the interpretation of the shuffling radius, or the quantity in Eq (6)? However, even more importantly, the methods the authors base their work on, namely DIANA and NASTYA, are not explained; the reader only has the pseudocode given in Algorithms 2-4 to work with. The best illustration of this is the disconnect between the paper title and its contents: there is no explicit mention of compressing gradient differences in the main text. I believe the authors' use of DIANA inspires the title, but I am not fully sure. Furthermore, the pseudocodes in Algorithms 1-4 are ambiguous, as the authors mix what happens on the client's side and on the server's side. I suggest the authors break up the code into two parts, one demonstrating the server-side operations and one showing the clients' side.

We thank the reviewer for the suggestions. If our paper gets accepted, we will have an extra page to add more clarifications to the main text. We also can shorten the introduction. We believe these adjustments can be easily done.

I find Eq (1) and similar equations combining definitions with statements very confusing; please separate the two.

Eq (1) is the standard finite sum formulation of the optimization objective, see (Mishchenko et al., 2019; Stich, 2020; Haddadpour et al., 2021).

As defined, assumption (1) doesn't make sense; the expectations have no meaning as $\mathcal{Q}$ is not stochastic; please make the meaning precise.

We consider only the case when $\mathcal{Q}$ is a random operator, e.g., see (Horvath et al., 2019). This assumption is satisfied for many compression operators, e.g., for random sparsification and quantization.

The symbol $n$ denoting the batch size is technically undefined; it should be included in the chain of equalities on line 34.

Thank you for noting this; we will add $n$ to the sentence as advised.

Table 1 is difficult to interpret, and it is unclear to me what value it brings to the paper. I would either move it to the appendix or cut it altogether and use the space to address my main concern, which I outlined above.

Table 1 is very important, and it summarizes our main theoretical results. We will address your concerns without removing the table.

Over what is the expectation in Def 2.1?

The expectation is taken with respect to data permutation, which is the essential part of the random reshuffling method.

Figures 2 and 3 should be renamed to Figures 1a and 1b, respectively.

Thank you for the suggestion. We will update the paper accordingly.

Merge the two panels in Figure 4

We believe that it makes the plot more complicated. On the first one you can observe the performance of QSGD and Q-RR and how it is similar. On the second, it is clear that DIANA-RR works better than DIANA. To compare Q-RR and DIANA-RR it is enough to compare the obtained accuracy.

Algorithm 1, steps 2 and 3, $x^0_{t,m}$: the symbol $m$ is undefined

We will make such an adjustment.

Thank you for your response!

To address the issue related to the full participation case, we have provided theoretical results specifically for the Partial Participation setting. In this context, we analyze the scenario where only a subset of clients, with cardinality $C$, is sampled. We have included theoretical results for the Q-NASTYA and DIANA-NASTYA methods in this setting.

Furthermore, we plan to present similar theoretical results for the Q-RR and DIANA-RR methods in the camera-ready version of the paper. This additional analysis will provide a more comprehensive view of our methods' performance under various participation scenarios. Please review the theoretical results provided below, starting with the Q-NASTYA method in the Partial Participation setting. We hope these results clarify our approach and address the concerns raised.

Theorem 1. Let step sizes $\eta, \gamma$ satisfy the following equations $\eta=\frac{1}{16 L_{\max }\left(1+\frac{\omega}{C}\right)}, \quad \gamma=\frac{1}{5 n L_{\max }}$

Under the Assumptions 1, 2, 3 it holds

\mathbb{E}\left[\left\Vert x_T-x^{\star}\right\Vert^2\right] \leq & \left(1-\frac{\eta \mu}{2}\right)^T\left\Vert x_0-x^{\star}\right\Vert^2+\frac{9}{2}\frac{\gamma^2 n L_{\max }}{\mu}\left(\frac{1}{M} \sum_{m=1}^M \sigma_{\star, m}^2+n \sigma_{\star}^2\right) +8 \frac{\eta}{\mu}\left(\frac{\omega}{C} \sigma_{\star}^2+\frac{M-C}{C \max (M-1,1)} \sigma_{\star}^2\right) \end{aligned}$$ where $$\sigma_{\star}^2=\frac{1}{M} \sum_{m=1}^M\left\Vert\nabla f_m\left(x^{\star}\right)\right\Vert^2, \quad \sigma_{\star, m}^2=\frac{1}{n}\left\Vert\nabla f_m^i\left(x^{\star}\right)\right\Vert^2.$$ As we can see, there is an additional error term proportional to $ \frac{M-C}{C \max (M-1,1)} $ that arises due to client sampling in the partial participation setting. Note that when $ C=M $ (all clients are participating), this error term vanishes, allowing us to recover the previous result for the full participation case. This shows the consistency of our theoretical framework across different participation scenarios. We start from Lemma F.1: **Lemma F.1. (updated)** Let Assumptions 1, 2, 3 hold. Then, for all $t \geq 0$ the iterates produced by Q-NASTYA satisfy $$\mathbb{E}\_{\mathcal{Q}, S\_t}\left[\left\Vert g\_t\right\Vert^2\right] \leq \frac{2 L_{\max }^2\left(1+\frac{\omega}{C}\right)}{M n} \sum_{m=1}^M \sum_{i=0}^{n-1}\left\Vert x_{t, m}^i-x_t\right\Vert^2 +8 L_{\max }\left(1+\frac{\omega}{C}\right)\left(f\left(x_t\right)-f\left(x^{\star}\right)\right) +4\left(\frac{\omega}{C}+\frac{M-C}{C \max \{M-1,1\}}\right) \sigma_{\star}^2$$ where $\mathbb{E}\_{\mathcal{Q}, S\_t}$ is expectation w.r.t. $\mathcal{Q}, S\_t$ and $ \sigma_{\star}^2=\frac{1}{M} \sum_{m=1}^M\left\Vert \nabla f_m\left(x^{\star}\right)\right\Vert^2. $ **Proof**: Using $\mathbb{E}\left[\Vert \xi\Vert^2\right]=\mathbb{E}\left[\Vert\xi-\mathbb{E}[\xi]\Vert^2\right]+\Vert\mathbb{E} \xi\Vert^2$, we obtain $ \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert g\_t\right\Vert^2\right]= & \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert\frac{1}{C} \sum\_{m \in S_t}\left(\mathcal{Q}\left(\frac{1}{n} \sum\_{i=0}^{n-1} \nabla f_m^{\pi\_m^i}\left(x\_{t, m}^i\right)\right)-\frac{1}{n} \sum\_{i=0}^{n-1} \nabla f_m^{\pi\_m^i}\left(x\_{t, m}^i\right)\right)+\frac{1}{C n} \sum\_{m \in S_t}\sum\_{i=0}^{n-1} \nabla f_m^{\pi\_m^i}\left(x\_{t, m}^i\right)\right\Vert^2\right] \\\\ =&\frac{1}{C^2} \mathbb{E}\_{\mathcal{Q}}\Vert\sum\_{m \in S\_t}(\underbrace{\mathcal{Q}\left(\frac{1}{n} \sum\_{i=0}^{n-1} \nabla f\_m^{\pi\_m^i}\left(x\_{t, m}^i\right)\right)-\frac{1}{n} \sum\_{i=0}^{n-1}\nabla f\_m^{\pi\_m^i}\left(x\_{t, m}^i\right)}_{=\xi\_m}\Vert^2] \\\\ &+\left\Vert \frac{1}{C n} \sum\_{m \in S_t}\sum\_{i=0}^{n-1} \nabla f\_m^{\pi_m^i}\left(x\_{t, m}^i\right)\right\Vert^2 \\\\ =&\frac{1}{C^2} \mathbb{E}\_{\mathcal{Q}}\left[\sum\_{m \in S_t}\left\Vert \xi\_m\right\Vert^2+\sum\_{m, l \in S_t: m \neq l} 2\left\langle\xi\_m,\xi\_l\right\rangle\right]+\left\Vert\frac{1}{C n} \sum\_{m \in S\_t}\sum\_{i=0}^{n-1} \nabla f\_m^{\pi\_m^i}\left(x\_{t, m}^i\right)\right\Vert^2. $ Using independence between $\xi_m$ and $\xi_l$ for different $m, l$ and Using (2), (3), we get $ \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert g\_t\right\Vert^2\right]= & \frac{1}{C^2} \sum\_{m \in S\_t} \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert \mathcal{Q}\left(\frac{1}{n} \sum\_{i=0}^{n-1} \nabla f\_m^{\pi\_m^i}\left(x\_{t, m}^i\right)\right)-\frac{1}{n} \sum\_{i=0}^{n-1} \nabla f\_m^{\pi\_m^i}\left(x\_{t, m}^i\right)\right\Vert^2\right] \\\\ &+\left\Vert\frac{1}{C n} \sum_{m \in S_t} \sum_{i=0}^{n-1} \nabla f_m^{\pi_m^i}\left(x_{t, m}^i\right)\right\Vert^2 \\\\ \leq & \frac{\omega}{C^2} \sum_{m \in S_t}\left\Vert\frac{1}{n} \sum_{i=0}^{n-1} \nabla f_m^{\pi_m^i}\left(x_{t, m}^i\right)\right\Vert^2+\left\Vert\frac{1}{C n} \sum_{m \in S_t} \sum_{i=0}^{n-1} \nabla f_m^{\pi_m^i}\left(x_{t, m}^i\right)\right\Vert^2. $

Dear Reviewer,

Please note that we provided theoretical results not only for Q-NASTYA in the partial participation regime but also for DIANA-NASTYA in the same setting. Similar to the full participation case, this approach allows us to reduce compression variance in Q-NASTYA, which may be the dominant factor. Even without this technique, Q-NASTYA in the partial participation case remains beneficial if the compression is minimal. However, when variance reduction for compression is applied, DIANA-NASTYA in the partial participation setting becomes particularly advantageous.

Let step sizes $\eta, \gamma$ satisfy the following equations $\eta= \min \left( \frac{1}{80 L_{\max }\left(1+\frac{\omega}{C}\right)}, \frac{C}{\mu(1+\omega)M}\right), \quad \gamma=\frac{1}{5 n L_{\max }}$

Under the Assumptions 1, 2, 3 it holds $\mathbb{E}\left[\Psi_T\right] \leq\left(1-\frac{\eta \mu}{2}\right)^T \mathbb{E}\left[\Psi_0\right]+\frac{3 \gamma^2 n^2 L_{\max }^2}{\mu}\left(\frac{1}{M} \sum_{m=1}^M \sigma_{\star, m}^2+n \sigma_{\star}^2\right)+\frac{2 \eta(M-C)}{\mu C \max(1,M-1)} \sigma_{\star}^2.$

Note that we eliminate the variance term proportional to $\omega$: $8 \frac{\eta}{\mu}\frac{\omega}{C} \sigma^2_\star$. In the Partial Participation regime, we have a variance term proportional to $\frac{(M - C)}{C \max(1, M - 1)}$, which equals zero if $C = M$. This term decreases as $\mathcal{O}\left(\frac{1}{C}\right)$, so we achieve the expected linear speedup.

We start from STEP 1: we need to estimate inner product. By $\hat{g}\_t=\frac{1}{C} \sum\_{m \in S_t} \hat{g}\_{t, m}$, we have

$$\begin{aligned} -\mathbb{E}\_t\left[\left\langle\frac{1}{C} \sum\_{m \in S\_t} \hat{g}\_{t, m}, x\_t-x^{\star}\right\rangle\right]= & -\left\langle\frac{1}{C} \mathbb{E}\_t\left[\sum\_{m \in S\_t} \hat{g}\_{t, m}\right], x_t-x^{\star}\right\rangle \\\\ = & -\left\langle\frac{1}{M} \sum\_{m=1}^M \mathbb{E}\_t\left[\hat{g}\_{t, m}\right], x_t-x_{\star}\right\rangle \\\\ = & -\frac{1}{M} \sum_{m=1}^M\left\langle g_{t, m}, x_t-x^{\star}\right\rangle \\\\ = & -\frac{1}{M} \sum_{m=1}^M\left\langle g_{t, m}-h_m^{\star}, x_t-x^{\star}\right\rangle \\\\ \leq & -\frac{\mu}{4}\left\Vert x_t-x^{\star}\right\Vert^2-\frac{1}{2}\left(f\left(x_t\right)-f\left(x^{\star}\right)\right)-\frac{1}{M n} \sum_{m=1}^M \sum_{i=0}^{n-1} D_{f_m^{\pi_m^i}}\left(x^{\star}, x_{t, m}^i\right) \\\\ & +\frac{L_{\max }}{2 M n} \sum_{m=1}^M \sum_{i=0}^{n-1}\left\Vert x_t-x_{t, m}^i\right\Vert^2. \end{aligned}$$

STEP 2: STEP 2: We need to bound $\mathbb{E}\left\Vert\hat{g}\_t\right\Vert^2$. By $\hat{g}\_t=\frac{1}{C} \sum\_{m \in S_t} \hat{g}\_{t, m}$, we have

$$\begin{aligned} \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert \hat{g}\_t\right\Vert^2\right]= & \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert \frac{1}{C} \sum\_{m \in S\_t}\left(h_{t, m}+\mathcal{Q}\left(g\_{t, m}-h\_{t, m}\right)-g\_{t, m}+g\_{t, m}\right)\right\Vert^2\right] \\\\ = & \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert \frac{1}{C} \sum_{m \in S_t}\left(h_{t, m}+\mathcal{Q}\left(g_{t, m}-h_{t, m}\right)-g_{t, m}\right)\right\Vert^2\right]+\left\Vert \frac{1}{C} \sum_{m \in S_t} g_{t, m}\right\Vert^2 \\\\ = & \frac{1}{C^2} \sum_{m \in S_t} \mathbb{E}\_{\mathcal{Q}}\left[\left\Vert h_{t, m}+\mathcal{Q}\left(g_{t, m}-h_{t, m}\right)\right\Vert^2\right]+\left\Vert \frac{1}{C} \sum_{m \in S_t} g_{t, m}\right\Vert^2 \\\\ \leq & \frac{\omega}{C^2} \sum_{m \in S_t}\left\Vert g_{t, m}-h_{t, m}\right\Vert^2+\left\Vert \frac{1}{C} \sum_{m \in S_t} g_{t, m}\right\Vert^2 \\\\ \leq & \frac{2 \omega}{C^2} \sum_{m \in S_t}\left\Vert g_{t, m}-\nabla f_m\left(x_t\right)\right\Vert^2+\frac{2 \omega}{C^2} \sum_{m \in S_t}\left\Vert \nabla f_m\left(x_t\right)-h_{t, m}\right\Vert^2 \\\\ & +2\left\Vert\frac{1}{C} \sum_{m \in S_t} g_{t, m}-h_m^{\star}\right\Vert^2+2\left\Vert\frac{1}{C} \sum_{m \in S_t} h_m^{\star}\right\Vert^2 \end{aligned}$$

We will continue in the next parts.

We thank the reviewer for the detailed feedback and a very positive evaluation of our work.

While the experiments conducted are thorough, they are limited to certain types of tasks (logistic regression and ResNet-18 on CIFAR-10). The generalizability of the results to other models and datasets is not fully explored, which could limit the broader applicability of the findings.

Thank you for your comment! We will try to do additional experiments on other datasets and models.

Q-NASTYA and DIANA-NASTYA algorithms are too dependent on hyperparameters, which requires additional computation and management, affecting the practical application and deployment of the algorithms, especially in large-scale distributed environments.

When tuning parameters (e.g. step size), could you try a more efficient way of tuning the parameters to increase the scalability of the algorithm? Whether there are plans to develop automated methods for tuning parameters to reduce the complexity of manual tuning and increase the feasibility of the algorithm in practical applications?

Thank you for your comment! We agree that dependence on hyperparameters is a limitation of our methods (though many methods in the field have the same similar limitation). We will think about adaptive versions of the proposed methods (and incorporation of recently proposed adaptive methods such as D-Adaptation, Prodigy, and Schedule-Free SGD). We leave it for future work. Regarding the tuning of parameters for our methods in practice, the standard schemes for tuning the stepsizes (e.g., search at the logarithmic scale) should work well.

Due to the increased implementation complexity of the algorithms proposed by DIANA-RR et al. are there any performance evaluations in practical applications, especially how well they perform in large-scale distributed systems?

We will do our best to run the methods with a larger number of workers. Then, we can measure the efficiency of the methods in terms of the number of communicated bits to achieve convergence w.r.t. different metrics (top-1 accuracy, train loss, gradient norm).

The algorithm in this work relies on many parameters, but lacks corresponding experimental proofs. For example, DIANA-RR uses multiple shift vectors (n of them), while DIANA uses only 1 shift vector, and there are no experimental results showing the effect of different number of shift vectors on the performance. There are no detailed experimental results showing the effect of different compression levels on the performance of the algorithm at different compression levels. etc.

We agree with the reviewer that all of these experiments are important and would strengthen the paper. We will do our best to include them in the final version. In particular, we conducted the experiment with a $1$ local shift for DIANA-RR and attached the results to the general rebuttal message. Our results indicate that the usage of multiple shifts is important for DIANA-RR, since otherwise, the method does not work better than DIANA.

Regarding the experiments with different compression levels, we expect that the behaviour will be expected: the less we compress, the better all methods converge, and the less the impact of shifts is.

However, we also would like to emphasize that our work is primarily theoretical, and the experiments are mainly needed to illustrate and support our theoretical findings.

... including Q-RR and its variants Q-NASTYA, which compress gradient differences in the scenario of data random shuffling.

Just to clarify, Q-NASTYA is not a variant with compressed gradient differences. The variants that utilize compressed gradient differences are DIANA-RR and DIANA-NASTYA, as they are based on the DIANA technique, which specifically compresses gradient differences.

The algorithm of EF21 also looks very similar to DIANA-RR. I think DIANA-RR is basically a combination of DIANA and EF21. Unfortunately, I lost track of the huge number of variants of DIANA, so I'm not exactly sure whether the variant of DIANA + EF21 has already existed somewhere.

Regardless of DIANA itself, what exactly is the difference between the "compress gradient differences" proposed in this paper and the algorithm of EF21?

From these comments, we see that you have some questions related to DIANA, EF21, and our DIANA-RR. We explain the main features of those methods and emphasize the differences between them.

DIANA. The DIANA method was proposed by [Mishchenko et al, 2019] as a fix to the QDGD (quantized distributed gradient descent) leading to linear convergence to the exact solution in a strongly convex case compared to QDGD. As you can see, for QSGD, there is a neighbourhood term corresponding to data heterogeneity in the complexity (see Table 1). The same phenomena have a place for QDGD. This is why DIANA can be seen as a variance reduction technique for unbiased compression. Next, DIANA is designed for unbiased compression operators (see Assumption 1); this is crucial for the analysis. The third property of DIANA, which can be inferred from the complexity results, is that the convergence rate improves when $M$ increases. In other words, the neighbourhood terms decrease with the increase in the number of clients $M$.

EF21. EF21 is an improved version of a well-known error feedback technique [Seide et al., 2014]. EF21 works for the wider class of compressors called biassed compressors. However, the convergence rate does not improve when $M$ is large. Also the gradient estimator in EF21 is biassed, which brings another challenge for convergence analysis. Moreover, a naive combination of EF21 with SGD requires to use of large batchsizes; see [1].

DIANA-RR. This new algorithm combines the DIANA technique and sampling without replacement (a.k.a. RR). However, the combination is not straightforward (we do not simply plug in RR estimator in DIANA) and requires several modifications: first of all, we do not wait until each client goes through the whole dataset to send information at the end of each epoch. Instead of this, we construct the algorithm to send a compressed gradient from clients to the server on each step of the epoch, and we make a gradient step on the server. To set up such an approach correctly, we set for each client their own set of shift- vectors $h^i_{t,m}$, which differs from the original DIANA method.

As one can see from the above explanation, DIANA, DIANA-RR, and EF21 are completely different methods, and DIANA-RR is not a combination of DIANA and EF21, as the reviewer claims.

[1] Fatkhulin et al. Momentum provably improves error feedback! NeurIPS 2024.

The idea of compressing gradient differences is actually not very novel. EF21 [1] proposed compressing gradient differences a long time ago.

We do not claim that we are the first who propose usage gradient differences to improve the performance of FL algorithms with communication compression. It was proposed in the DIANA paper, which is much older than EF21. One of the main messages of our work is that the naive approach of a combination of RR and gradient compression (i.e., Q-RR) has no improvements over vanilla QSGD. Therefore, we combine two techniques – RR and DIANA – to improve Q-RR, but the combination is not trivial, as we explain above.

Since EF21 already uses compression of gradient differences, I think EF21 is a better baseline than QSGD. However, EF21 is not included in the experiments.

As we mentioned earlier, EF21 is a method designed for biased compression, which is not the focus of our current work. In this paper, we concentrate on unbiased compression techniques. We plan to explore biased compression in future research.

Could EF21 also be included in the experiments as a baseline?

Since we do not consider biased compression in this paper, we do not see a clear reason why we should add EF21 to the comparison. Our work is primarily theoretical, and the main goal of our experiments is to illustrate and support our theoretical findings. Thus, experiments with EF21 would be completely unrelated.