Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers a distributed GD setting where multiple nodes need to jointly minimize the average of individual convex objectives by computing and communicating its compressed local gradients.  The proposed algorithm is shown to achieves an accelerated convergence rate with compressed gradient passing.
main_review: This paper is clearly written and well organized. The proven convergence with the proposed algorithm is faster than a few earlier works.

My major concern is the usefulness of the studied setting. Requiring each node to compute its gradient (instead of stochastic/sampled gradient) in a distributed optimization does not seem practical. The setting is much less challenging than the conventional distributed (compressed) SGD setting as considered in QSGD in [1].  So it is unfair to say the results in the current paper improve [1] as in table 1.  The order-wise faster convergence (compared to [1]) is not quite surprising to me under this distributed GD setting.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a novel distributed methods with acceleration and communication compression. Authors proof the convergence and show that it is faster than existing SOTA methods.
main_review: Positive: 
This method achieves bigO(1/T^2) convergence rate benefit from the acceleration technique.

Negative:
1. I do not think this method is suitable for traditional distributed optimization problems or federated optimization problems. In traditional distributed optimization problems, the data size and dimension are large. Calculating \nabla f_i(w) is slow and usually is worse than calculating a stochastic gradient, even when the model is convex. Furthermore, additional parameters h_t, \bar{x}_t and w_t will cost huge memory. In federated  learning, usually only few machines participate training in each communication round.

2. Authors should add experiments to compare CANITA with other distributed communication efficient optimization methods. I think a convex optimization experiment can be easily conduct on pytorch and tensorflow. 
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper propose a compressed and accelerated gradient method called CANITA for distributed optimization. 
It improves the the state-of-the-art result which is achieved by DIANA in smooth and convex problems.
The main contribution is the (near) optimal algorithm and its theoretical analysis.
main_review: Originality:

The paper considers a unexplored topic, how to fuse acceleration technique and unbiased compression operator organically. 
Though the algorithm (CANITA) is a combination accelerated ANITA method and compressed DIANA method, the analysis of the resulting algorithm has its own difficulty, i.e., how to analyze the error introduced by the compression operator while not ruining the delicate structure of acceleration for convex problems.
I think the analysis is new.

Quality:

The theoretical analysis is valid.
The author also provides a proof sketch to illustrate how to construct a potential function for convergence analysis.

Clarity:

The paper is well written and clear.

Significance:

The paper improves the state-of-the-art result of non-accelerated compressed algorithms.
I think the work might give insights on how to combine compression and acceleration optimally.


======================================================


I have read the author's response.
I think the author well answers my questions.
I keep my score.

limitations_and_societal_impact: Some questions:
1. Though CANITA has a theoretical superiority, it is still unclear how it performs empirically. I suggest the author could add some numerical experiments to investigate the empirical performance and its dependence on the hyper parameters. 
2. I am curious about why not provide the convergence rate of CANITA for strongly convex cases? ANITA could handle convex and strongly convex cases simultaneously. So I naturally expect CANITA could achieve it also. Comparing ANITA and CANITA, I find that the key is how to perform update rule (line 9). So why not use $x_{t+1}=\frac{1}{1+\mu \eta_{t}}\left(x_{t}+\mu \eta_{t} \underline{x}_{t}\right)-\frac{\eta_{t}}{\theta_{t}} \widetilde{\nabla}_{t}$ in the line 9 of CANITA? Does there exist some fundamental difficulties？
3. A typo: In line 148, I guess it should be $\theta_t = \frac{a_3}{t+a_4}$.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the compressed and accelerated gradient method for nonstrongly convex federated learning. State-of-the-art accelerated convergence rate is established.
main_review: Originality: This paper combines the accelerated ANITA in [16] and the compressed DIANA in [23]. I think it is a novel combination of two well-known techniques. It also extends the accelerated and compressed gradient method in [19] from strongly convex problems to nonstrongly convex ones. The convergence rate improvement over previous results is compared clearly.

Quality: The theory is technically solid. State-of-the-art convergence rate for nonstrongly convex problems is proved.

Clarity: This paper is written well. The proof is organized very clearly.

Significance: This paper studies acceleration and compression in federated learning. This is a significant topic. State-of-the-art convergence rate for nonstrongly convex problems is proved. The previous work on acceleration and compression all focus on strongly convex problems. I think the result is significant.

Major comment:

The experiment is missing. I suggest to include the numerical experiment in the final version. This paper proposes a new method, rather than reanalyzing a widely used method. So I think the numerical experiment is necessary.

Minor comment:

1. This paper studies the nonstrongly convex problems while [19] studied strongly convex ones. I am interested how fast CANITA converges for strongly convex problems by adoptting the proof techniques used in this paper. Is it faster than the one in [19]? The two rates in the last two lines of Table 1 looks different by letting $\kappa=\frac{L}{\epsilon}$ in the first one. I suggest to include the proof for strongly convex problmes in the supplementary material such that other researchers are likely to use the proof techniques in their work. For example,  the authors may organize the proof in a unified framework for both strongly convex and nonstrongly convex problems. 

2. I suggest to remove the proof of Lemma 6 to the supplementary material and inlcude the numurical experiment in page 8.

3. The proof of Theorem 1 in page 16 is redundant, because it is proved in page 9.

limitations_and_societal_impact: No limitation is discussed. I suggest to include the numerical expriment in the final version.
review_title: null

Meta-review: The review committee agreed that the paper is an interesting contribution and hence should be accepted for presentation at Neurips. However, there were some concerns regarding the practical relevance of the work. The authors mentioned in their response that they have run experiments on "logistic regression tasks". I strongly encourage the authors to include those simulations in the final version of the paper.


Decision: Accept (Poster)