Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents accelerated methods for communication-efficient learning applications. In particular, a loopless Katyusha strategy is introduced to attain the O(\sqrt{L/\mu}) rate for error-compensated methods using stochastic gradient information. These methods are called ECLK. In terms of theoretical iteration complexity and empirical experiments, ECLK is explicitly shown to be more communication efficient and to have a better rate than existing error compensation methods.
main_review: This paper is clearly written. The simulation results highlight the impact of algorithmic tuning parameters, and the superior performance of ECLK over non-accelerated error-compensated algorithms. However, there are some concerns presented below: 

* The authors claim that ECLK performs better than EC-LSVRG-DIAN but worse than ADIANA, in theoretical iteration complexity. However, to compare these complexities, Lyapunov functions associated with these methods are totally different. The Lyapunov function for ECLK is the summation of the Euclidean distance and the function difference, while the Lyapunov function for EC-LSVRG-DIANA and ADIANA is only the function difference. Therefore, comparing the complexities with different Lyapunov functions seems to weaken the authors' claim.
* Literature review related to this work is in Section F in the supplementary materials. This approach leads to weak discussions of error compensation in the introduction. This literature review in Section F should be included rather in the introduction. 
* This paper lacks the motivation on why Katyusha is used as the acceleration technique, instead of Nesterov's acceleration. It will be better if the authors also include literature review about this technique.
* One section in numerical experiments highlights that ECLK is comparable to ADIANA that uses non-compensated information for most cases in deterministic settings. This raises the question why the authors instead consider the extension of ADIANA for error-compensated methods. In addition, what happens in stochastic settings? Since Katyusha, unlike Nesterov's acceleration, guarantees the fast rate for the methods to solve stochastic optimization, ECLK may be expected to outperform ADIANA and error-compensated algorithms with Nesterov's acceleration. This will strengthen the authors' contributions. 
limitations_and_societal_impact: The contribution of this paper is primarily theoretical. Therefore, limitations and societal impacts are not applicable.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider accelerated training algorithms using gradient compression with error compensation. For this purpose, they incorporated gradient compression and error compensation in the Katyusha algorithm and developed ECKL. The algorithm quantizes both the SG and VR term and keeps track of the quantization error for error compensation in the next iteration.

The paper analyzed the convergence rate and iteration complexity of ECKL for the smooth convex functions and compared it with variants of DIANA both theoretically and via some simple simulations on logistic regression.
main_review: The idea and algorithm developed in the paper is interesting and can be potentially useful in distributed DNN training. However, one shortcoming of the paper is its analysis.The paper only considers the class of smooth convex functions. Although for theoretical analysis, the assumptions in the paper are common and ok, but for the simulations, it would be more interesting to see how the algorithm performs for more complex cost functions, even training a simple DNN on CIFAR10 could have demonstrated the performance of ECKL in more general setting.

Minor:
Finally, the writing and notations of the paper can be improved. Some notations are used without proper definition, and some parts are missing, e.g.,
* what is parameter $\mathcal{L}_1$?
* Algorithm 1, how $h_\tau^0$ is initialized?
* Alg. 1: $u_\tau^{k+1}$ is always set to 0 for $\tau=2,\ldots,n$, and only $u_1^k$ is changing and used. It seems that worker 1 acts as the controller to decide on updating $\omega^k$. In that sense, defining $u_\tau^k$ looks redundant and a single shared random variable $u^k$ would be enough.

____________________________
UPDATE:
Thanks for the answers and clarifications. I updated the my recommendation accordingly. Although not necessary and having simulations on convex problems suffices for the paper, I believe that showing the performance on some non-convex problems can really add to the value of the paper.
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed an error compensated based Katyusha method for finite-sum convex problems. The proposed method achieves the same asymptotic convergence rate as its full precision accelerated counterpart. Compared to another related work ADIANA, the proposed method can be applied to contractive compressor. 
main_review: The paper is clearly written and theoretically sound. However, I am not clear about the motivation of applying gradient compression to a finite-sum convex problems and what the real convex applications are that require gradient compression. Typically, the application requires gradient compression is the training of large deep neural networks, which is neither finite-sum nor convex. In addition, I have a few questions.

1. Theoretically, how do we select Q and Q_1 that minimizes the bound given a fixed communication budget?
2. What is the communication collective primitive used in the proposed algorithm? Since most of quantization and sparsification methods are incompatible with allreduce, it seems to me that it is all-to-all broadcast?
3. Since the proposed method obtains an accelerated rate that has better dependency on condition number, it is good to see the experimental results with varying condition numbers. 
4. The proposed method introduces a number of hyper-parameters. How do we choose them in practice?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces an error compensation variant of the loopless Katyusha, ECLK. Theoretical convergence analysis is given and accelerated linear convergence rate is obtained using contraction operators. Experimental study of ECLK is given on the logistic regression problem for binary classification.
main_review: The paper applys error compensation to accelerated gradient methods, and introduces error compensated loopless Katyusha method. Convergence analysis is given of ECLK with contraction operators, and compared to ADIANA with unbiased compressor. Experimental results are given for binary classification with ECLK with three contraction compressors, and compared with other methods in literature. 

The paper is clearly written and well organized.

**Update**: Thanks for the authors' response to the reviews. It helps with the clarification after reading the responses to all the reviewers.

limitations_and_societal_impact: The paper addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers communication efficient algorithms for SGD. In this model, there are $n$ total workers and each worker has a local smooth convex loss function $f_i$ on $R^d$. The objective is for a coordinator to find an approximate global minimum for an objective function that represents the average loss across all workers while minimizing communication between the workers and the coordinator. 

A common approach is for each worker to compute a sketch on their local batch of gradients that allows the coordinator to recover of the top $k$ gradients in magnitude, ideally improving the rate of convergence. However, the challenge with this approach is that the estimator formed by the coordinator using the sketches sent from the workers may not be an unbiased estimator of the overall gradient, which allows error to accumulate over multiple iterations. This paper introduces provable accelerated gradient-methods, in the sense of Nesterov momentum for contractive compressors, which are a general class of stochastic functions that form estimators of the gradient, including the top $k$ estimator. 
main_review: It seems the algorithm performs the usual uniform sampling technique to acquire a batch of gradients for each step. The algorithm then applies a contractive compressor in the standard way to improve communication efficiency over naive SGD. To address the bias incurred by the contractive compressor, the algorithm attempts to learn the added bias and subtract the bias incurred from the previous iterate before using a standard proximal operator to update the current iterate.

I believe existing approaches that achieve communication efficient SGD also use this framework to deal with error accumulation and feedback, e.g., FetchSGD [RPU+20] also achieves acceleration though it seems the convergence rate is better in this paper. What is the algorithmic novelty that allows the improved convergence rate? This should perhaps be clarified in the paper. 

Though the theoretical contributions of the paper seem very relevant to the machine learning and stochastic optimization communities, I think the exposition of the paper could be greatly improved in general. For example, I think discussion or comparison to related works or techniques are sometimes overlooked [IRU+19, RPU+20] or too brief [KRSJ19]. I also think the current text description does not give enough intuition for the main algorithm. 

[KRSJ19] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, Martin Jaggi: Error Feedback Fixes SignSGD and other Gradient Compression Schemes. ICML 2019: 3252-3261

[IRU+19] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, Raman Arora:
Communication-efficient Distributed SGD with Sketching. NeurIPS 2019: 13144-13154

[RPU+20] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, Raman Arora: FetchSGD: Communication-Efficient Federated Learning with Sketching. ICML 2020: 8253-8265
limitations_and_societal_impact: I do not think there are any limitations and potential negative societal impact of their work that the authors need to address.
review_title: null

Meta-review: Overall, this paper addresses an important open problem. It is well-written, and solid theoretical results are complemented by distinct advantages in simulation experiments.

Based on my own reading, and the comments of the reviewers, I recommend acceptance. 

There are some weak points that should be improved in the camera ready version.

The abstract and part of the introduction are a little bit misleading, referring to Nesterov’s acceleration (easily mistaken for Nesterov’s accelerated gradient method), while the algorithm later uses Katyusha (another acceleration technique).

The writing is a bit too dense, with little exposition on how the algorithm works and how it is related to previous work. In the response to the reviewers, you claim that this is not an issue and it does not matter if you put material in the main text or the appendix. I disagree. The main text should be complete and accessible to a broader audience than researchers in error-compensated training algorithms. I believe that parts of the related work from the appendix need to be moved into the main text and that you need to expand on how the algorithm works, and how its parameters are selected. In the response to the reviewers, you share such intuition and describe parameter tuning techniques. This knowledge should also make it into the main document.

Finally, I also believe that you can clarify in what environment you perform your experiments. I see the main contribution of this paper as mainly theoretical, but you do talk about “nodes” in your experiments, and “send” and “receive” in your algorithm. To me, it is perfectly fine if you have made the experiments in a Python/Matlab/C++… simulation where send and receive operations are instantaneous and error-free. But you should be clear with this in the paper.
Decision: Accept (Poster)