Thank you for your positive evaluation and acknowledging our contributions.

Weaknesses

1. I believe it important to compare LoCoDL with ADIANA when is at least 10 or 100 smaller than to see whether LoCoDL beats ADIANA in these scenarios.

2. It's recommended to conduct experiments on MNIST or larger datasets.

We have followed your suggestion and run additional experiments, please see the rebuttal to all reviewers for the results. This confirms that LoCoDL significantly outperforms ADIANA.

3. It is not easy to capture the intuition behind each algorithm line. It's recommended to give more detailed explanations on how the algorithm is developed.

Thank you for this constructive suggestion. We will make use of the extra page to better describe the steps of LoCoDL in Section 2.2.

Questions

1. Existing works widely use the error feedback mechanism from EF21 to remove the gradient dissimilarity bound condition. Does LoCoDL overcome this issue by the primal-dual format? Is the primal-dual format somehow equivalent to error feedback or has it been used by prior works for the same reason? I'm not questioning the novelty of the proposed algorithm but rather curious about the intuition behind.

This is an excellent and deep question. We can note the following.

1. In Condat et al. "EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization,"Neurips 2022, it is shown that the error feedback mechanism of EF21 and the variance-reduction technique of DIANA based on compressing the difference between gradients and control variates are essentially the same.
2. In Condat and Richtárik "RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates," ICLR 2023, it is shown that the control variates introduced in Scaffnew to correct for the client drift can be viewed as dual variables for the dualized consensus constraint $x_1=\cdots=x_n$.
3. Still, the two variance reduction techniques, EF21/DIANA/EF-BV on one hand, Scaffnew/RandProx on the other hand, are of different nature, as far as we can tell, and we are not aware of a primal-dual interpretation of the former.
4. Thus, the idea of compressing the difference between local model estimates $x_i$ and an anchor $y$, which are primal variables, is not related to the primal-dual view, which is used to analyze the overall algorithm, in particular how the random errors propagate between the primal and the dual variables.

2. Is it possible to extend LoCoDL to stochastic settings or generally convex settings?

Allowing for stochastic gradients with or without variance reduction instead of full and exact gradients does not seem to be difficult. But it is related to computation-efficiency, not communication-efficiency, and is worth a study in a full separate paper to investigate the different tradeoffs. We have not looked at the extension to the general convex setting. It is certainly possible to derive $O(1/t)$ rates without much difficulty. Obtaining convergence to a stationary point in the nonconvex setting would be more interesting, but our efforts so far have been unsuccessful.

3. $\mu$ may not be available for many objective functions. Should we tune it as a hyperparameter?

We study linear convergence rates when the functions are smooth and strongly convex. Indeed, the case $g=0$ requires transferring some amount of strong convexity from the $f_i$ to $g$, for which a lower bound on $\mu$ is needed. Underestimating this lower bound will slow down convergence. We note that the same idea of transferring strong convexity to get linearly converging algorithms has been used in other works, e.g. Grudzien et al. "Can 5th Generation Local Training Methods Support Client Sampling? Yes!" AISTATS 2023.

If we apply LoCoDL to the vanilla case where $g=0$, are there any difficulties in convergence analysis?

Without any change, if $g=0$, which is not strongly convex, there is no contraction applied to the variable $y$, so linear convergence will be lost.

Limitations

As stated in the conclusion part, the algorithm is limited to single-directional, deterministic setting without partial participation.

Deriving efficient algorithms with bidirectional compression is a hot and very challenging topic and our main priority. We believe the key idea introduced in LoCoDL of having the model estimate $y$ in addition to the local estimates $x_i$ will play a major role. Partial participation can be implemented in LoCoDL, but it will be more satisfactory to develop it in the setting of bidirectional compression.

Thank you for your positive evaluation and acknowledging our contributions.

Weaknesses

1. LoCoDL does not apply to NNs

This work is indeed mainly theoretical as we develop a new algorithmic framework combining the mechanisms of local training and compression, and validate it with proved acceleration in the strongly convex setting. For the nonconvex problem of training NNs, which poses specific challenges, the proof techniques are significantly different and we currently don't know how to analyze LoCoDL in this setting. More generally, the use of variance reduction to correct for client drift and compression error is an open and debated question, see for instance

"On the Ineffectiveness of Variance Reduced Optimization for Deep Learning" Neurips 2019

"On the effectiveness of partial variance reduction in federated learning with heterogeneous data", CVPR 2023

For the ultimate quest of training NNs in a distributed or federated way, we believe that our paper is a first milestone, whose original ideas could foster further research in the community about nonconvex settings.

2. LoCoDL possibly is less efficient for partial participation use cases (this part is unclear).

It is possible to allow for partial participation (PP) in LoCoDL. We did not focus on this, because there are several primal and dual variables, so a neat design would involve PP and bidirectional compression jointly. We leave such a difficult study for future work.

3. Strengthening the evaluation section is also advised.

We have run additional experiments, please see the rebuttal to all reviewers.

Questions

1. "are smooth, so their gradients will be called." This sentence is unclear.

We mean that for a smooth function, it is natural to use the gradient and not the proximity operator. We will reformulate this sentence.

2. “is slower than broadcasting the same message to an arbitrary number of clients.” Are there any real FL systems that employ broadcasting? Or do you mean sending the same message?

Yes, we just mean sending the same message in parallel to all clients. We will change the term broadcast.

3. The second part of the sentence should be softened or extended with real evidence that this is the case.

We have in mind federated learning (FL) with communication happening via the internet or mobile phone network. We will add references supporting the claim that uplink is more expensive than downlink communication.

4. "No other compressor can be used, which notably rules out any type of quantization." Why is this the case?

In CompressedScaffnew, the compressed vectors do not tend to zero. Therefore, for the algorithm to be variance reduced, the following property must hold: if the compressed vectors are all equal, then there is zero compression error. The only known mechanism satisfying this property is sparsification with the correlated rand-k compressors selecting elements according to a random permutation.

5. Is there a specific challenge in implementing permutation-based compressors?

Such compressors are correlated and select elements according to a random permutation. A first implementation is that all clients use pseudo-random generators that remain synchronized all the time. In case a client becomes inactive for any reason, synchronization may be lost. A second implementation would be that before compression, the server samples the permutation and sends information to all clients to identity it. This is not very challenging but is detrimental to robustness. The ability of LoCoDL to use independent compressors makes it more versatile for practical FL use cases.

6. Do you mean: our experiments indicate that...?

Yes, our experiments indicate that LoCoDL outperforms other algorithms. We will reformulate the sentence.

7. What is the communication complexity with partial participation (PP) (i.e., $\rho=1$)?

The communication complexity in number of rounds with $\rho=1$, $\omega_\mathrm{av}<1$, $\chi=1-\omega_\mathrm{av}$ and appropriate $p$ is $O\left(\left( \sqrt{\kappa/(1-\omega_\mathrm{av})(1+\omega)}+\omega/(1-\omega_\mathrm{av})\right)\log \epsilon^{-1}\right)$. With independent rand-k compressors with $k=\lceil 2d/n\rceil$, the complexity in number of reals is the same as in Table 2.So, up to some constants, we can indeed choose $\rho=1$ and get the same asymptotic complexity. If quantization is applied in addition to rand-k, we just have to be careful to keep $\omega_\mathrm{av}<1$.

8. It seems that some elements of LoCoDL have some similarities to DoCoFL. Can the authors shed light on this similarity?

Thank you for pointing out the nice paper on DoCoFL. We will cite it and consider it in our future work on bidirectional compression. Indeed, to efficiently compress models, it is natural to compress the difference between models and anchors, and the challenge is to come up with good anchors. The last model sent by the server to all clients is too old after several local GD steps and not a good anchor: linear convergence can be proved but there is no acceleration, so the benefits of local training are lost. In LoCoDL, the anchor is the variable $y$, which is updated in parallel to the local model estimates $x_i$. Thus, it is a dynamic anchor, in contrast to a static anchor that would be updated once in a while. This is key to obtain acceleration.

Limitations

The conclusions section discusses potential future extensions. Outlining the limitations clearly is advised. For example, is the PP use case relevant here?

We discuss venues for future work in the conclusion, such as bidirectional compression and PP. One can view it as a limitation that LoCoDL does not have these features yet.

1. compressing the error and feeding it back to the updates is a well-known technique to reduce the variance in distributed learning

Do you mean like in DIANA? We have discussed existing algorithms and techniques in the paper. The contribution is the combination of local training, like in the popular FedAvg algorithm, and compression. This way we obtain a double acceleration, with a complexity that depends on $\sqrt{\kappa}$ and $\sqrt{d}$ when $n$ is large.

You don't give any argument or reference to support your claim that our contribution is not valuable.

2. the experiments should include the accuracy versus iteration (or time).

Do you want to see the plots with the number of iterations in abscissa instead of the number of communicated bits? When communication is much more expensive than computation, which is precisely the point of local training in federated averaging, it is meaningless to measure the number of iterations. Our goal is to reduced the communication complexity, which is what we illustrate.

We have run additional experiments, please see the rebuttal to all reviewers