Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper suggests a gradient averaging strategy for distributed adaptive optimization. Gradient compression is used for reducing the communication costs in transmission of gradients, and the tool of error feedback is used for correcting bias injected by the compression step. Convergence analysis results demonstrates that the proposed strategy has a linear speedup as the number of workers increases while the same convergence rate as standard AMSGrad. The experimental results on real-world datasets successfully validate the theoretical results.
main_review: Strengths
- The topic considering communication efficiency for adaptive distributed optimization is of timeliness and importance.
- Theoretical results look promising and the numeral results efficiently supports the validity of the theoretical results in practice.
- The paper is well-organized and contains the introduction of related studies with a fairly enough coverage. 

Weaknesses:
Minor comments
- Is there any systematic ways to choose the parameters $\beta_1, \beta_2, \epsilon$ in the proposed algorithm (Algorithm 2)?
- Page 4, "In Section 4 & 5" --> "In Sections 4 and 5"
- How do we define the "data heterogeneity" in page 2? Does this mean different $\chi_i$ on each local node? It would be better if the authors could clearly state this.
- Page 6, "under Assumption 1 to Assumption 4" --> "under Assumptions 1 to 4"

summary_of_the_review: Overall, I believe that this paper could be a meaningful add to the theories behind the distributed optimization. Numerical results also look solid enough to support the theoretical results.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new distributed optimization framework-COMP-AMS-based on gradient averaging and compression with convergence guarantee. In particular, theoretical discussions have shown that the proposed algorithm shares the same convergence rate as AMSGrad with linear speedup effect. Numerical experiments on several real-world data sets have demonstrated the proposed method can significantly reduce the communication costs while reaching comparable performance with full-precision AMSGrad.
main_review: Major strengths are listed as follows:
(1) The paper is easy to follow and provides sufficient background on compressed gradients and adaptive optimization. Comparisons with two related works are important and clear. 
(2) The proposed error-feedback strategy is interesting in the distributed optimization scenario. 
(3) Empirical results on some benchmark data sets are supportive and convincing. 

In addition, there are several minor issues that the authors could address to improve the clarity and quality of the paper:
1. In Sec 2.2, it seems there is no problem description for Algorithm 1, which may cause confusion for first-time readers. The paragraph in the beginning of Sec 3 could be moved here or even before Sec 2.2. Also, the parameter space could be explained or detailed with an example. 
2. In Sec 2.2., "different learning rate"->"different learning rates", "element-wisely"->"elementwise", "previous gradient magnitude"->"previous gradient magnitudes".
3. In Definition 2, $sign(x_{\mathcal{B}_1})$ is not defined. 
4. In Theorem 1, "Under Algorithm 1 to Algorithm 4" -> "Under Algorithms 1-4".
summary_of_the_review: Overall, the proposed work is important and interesting, and the paper deserves publication. The compressed gradient averaging technique with error feedback and its related convergence discussions could shed lights on other related works.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose the COMP-AMS algorithm for a distributed optimization framework. The algorithm is based on gradient averaging and adaptive algorithms. The application of gradient compression helps to reduce the communication complexity, and the tool of error feedback is used for the bias correction. The authors study the convergence rate of the proposed algorithm. The theoretical results are justified by the numerical experiments.
main_review: Strength:
The authors extend the adaptive optimization framework to distributed approach with a compressed gradient averaging. The convergence analysis implies a linear speedup in terms of the number of workers, and shows that in the single-machine case, it can achieve the same convergence rate as the standard full-gradient SGD. The paper is well-written and easy to follow.

Weakness:
I have some concerns as follows.
1. The authors do not assume the finite-sum of $f_i(\theta)$ to be convex, then how to avoid converging to a local optimal? 
2. If data heterogeneity exists for local workers, is it possible that the local gradient may drag others back when taking the gradient averaging in the central server?
3. In Algorithm 2, how to determine parameters $\beta_1, \beta_2$ and $k$? Is it possible that $k$ differs for different local workers?
4. In the algorithm, when applying EF technique to reduce the bias, each local worker still needs extra storage for the error term $e_t$, which is the same dimension as the local gradient. Why such an approach can be efficient in terms of the memory space when training large-scale learners?
5. In the experiments, how many workers are considered? Since data samples are randomly assigned to the workers, it can be regarded as the non-data heterogeneous case, it could be better if the authors can add the results for cases with data heterogeneity, e.g., workers with different sample sizes/ different class distributions.
6. There seem to be some typos. For example, in algorithm 1, line 8, I suppose the numerator should be $m_t$ instead of $\theta_t$; in theorem 1, corollary 1 and 2, what is $C_2$ in the denominator of the constrain for $\eta$? 


summary_of_the_review: I believe the paper has its value in extending the adaptive optimization framework to distributed approach with compressed gradient averaging. I mainly have concerns about the assumption on convexity and the impact on the performance brought by data heterogeneity.
review_title: null

Meta-review: The paper considers the setting of distributed optimization and proposes an adaptive gradient averaging and compression scheme to reduce the communication cost. The proposed scheme is shown to achieve the same convergence rate as full-gradient AMSGrad algorithm, but due to the reduced cost, it exhibits linear speedup as the number of workers grows.

The reviews appreciated the clear presentation of the results, technical soundness, and convincing numerical experiments. The paper is a solid contribution to distributed optimization. Thus, I recommend acceptance.
Decision: Accept (Poster)