Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: A major bottleneck in large-scale distributed deep learning is the communication bottleneck. The computational cost of the majority of existing compression algorithms to reduce the communication cost is too high. The authors proposed a new distributed optimization algorithm, Binary SGD-Momentum which 1- compresses the updates of the model's parameters at each worker, instead of the gradients commonly done in most other distributed DL methods, and 2-stochastically quantizes the values to +1 or -1. To aggregate the binary quantized values, they devise hierarchical 1-bit All-Reduce to take advantage of the 1-bit quantized values, and inter-node/intra-node communications. Finally, they theoretically analyzed their algorithm and evaluated it performance using numerous experiments.

strength_and_weaknesses: **Strengths:**

The authors have considered all aspects of distributed DL in developing their algorithm, such as computational cost, communication, and aggregation. This paper is among the few works that have considered compressing model updates instead of the SGs, and the simulation results show that the training with Bin-SGDM is consistently faster (or at least as fast as) uncompressed optimizers (even with high-speed intra-node connections among multiple GPUs).

**Weaknesses:**

In some parts, the paper is hard to read and the intent of the authors of some sentences/paragraphs are not clear. Moreover, some notations are not defined, and the reader has to search the appendix for the definition of some of the concepts. Moreover, the theoretical analysis seems to be flawed at some points.

1. There is a disparity between algorithm 1 and BinSGDM equation (4). Algorithm 1, line 7, keeps the maximum of $b_t^{(i)}$ and uses it to compute the parameter update. The authors do not explain or motivate this seemingly critical point in distributed BinSGDM, and it is not clear whether equation 4 or Alg. 1 is used for simulations. Practically, since the magnitude of SGs are usually larger at the first few training epochs, using the maximum value ($b_t^{(i)}$) is similar to scaling the SGs with a large constant value to map them to [-1, 1]. In other words, after few epochs, Alg. 1 applies (almost) fixed scaling factors to the computed SGs before binarizing them.
2. Theorem 1, what are the constants $\rho$ and $I$? Also, $z_1$ should be defined in the theorem.
3. The analysis and proofs in the appendix either have some flaws or unclear:
- Equation 10, note that although $g_t=\frac{1}{n}\sum_i g_t^{(i)}$, but $|g_t| \neq \frac{1}{n}\sum_i |g_t^{(i)}|$. Hence, the RHS equation is incorrect. I am not sure how this affects the validity of the proofs.
- Equation 34, the reason for 3rd and 4th inequalities are not clear.

clarity,_quality,_novelty_and_reproducibility: The algorithm is clearly presented (except the confusion between equation 4 and Alg. 1), and well-motivated, especially, the connection to the existing sign-SGD and Adam.
Moreover, all aspects of the experiments (HW, used software and libraries, architecture of the models, hyper-parameters, datasets, ...) are clearly stated with enough details.
However, as mentioned in the weaknesses, some parts of the paper are hard to understand or contain seemingly contradicting statements (e.g., first few sentences of Appendix B- Discussion). The writing of the paper needs some improvements.

summary_of_the_review: The paper has presented an interesting and somehow novel compression algorithm for the distributed DL.The authors have provided both theoretical analysis and to some extent complete simulation results.
I believe that the paper needs some minor improvements, such as double-checking the proofs of theorems and fixing some mistakes,
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors proposed a new quantized distributed stochastic gradient algorithm which resembles Adam.

They prove the new algorithm BinSGDM bears the same convergence rate as Adam, and BinSGDM is more communication efficient than Adam. They also compare the new algorithm with other algorithms, including ADAMW, 1-bit Adam and SGDM to show that the BinSGDM implementation is more performant than other algorithms' implementations.
strength_and_weaknesses: There are four key contributions listed by the authors

1. The first algorithm that quantizes the entire update of an adaptive optimizer (which seems to me that it translates to less quantization steps) and does not need warm-up.
  - This one looks novel and simplifies the usage of this algorithm.
2. BinSGDM has the same convergence rate as the full-precision Adam
  -  This one is based on strong assumptions such as the gradients are bounded by a constant, and it doesn't say much since the convergence rate is also the same as SGD's 1/\sqrt{T} rate. A simple quantized SGD can achieve the same rate.
3. Hierarchical 1-bit All-Reduce
  - This is a standard system implementation, basically it treats a node as a single worker in distributed training. Already implemented in frameworks such as DDP, Horovod, Bagua, etc.
4. First work to be consistently faster than DDP
  - This is highly dependent on the system implementation and computer network. And also not true, Existing works like Bagua and HiPress already show significant speedup over DDP

Therefore the novelty seems to be 1, but since the algorithm is completely different from the traditional Adam (the second-moment stat is also replaced by first-moment of the gradient absolute value), more comprehensive experiments are needed to confirm the uncompressed version of the algorithm matches the convergence of Adam on most tasks.

Also since the paper claims to have speedup in real-world settings, it should use more practical settings for experiments. Most people don't use A100-80G GPUs with only 10Gbps ethernet connection.
clarity,_quality,_novelty_and_reproducibility: The paper is well written and easy to understand. The algorithm looks novel.
summary_of_the_review: The algorithm looks novel, but there remains some work to justify the effectiveness of the algorithm.

1. The experiments need to be done in more realistic settings (for example A100 with RDMA connections)
2. Since the algorithm is based on a different update rule than the original Adam, to justify the new algorithm is as good as Adam (as one of the key contributions states) more comprehensive experiments are needed to confirm the uncompressed version of the algorithm matches the convergence of Adam on most tasks.

Also some claims need to be adjusted according to the "Strength And Weaknesses" section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to quantize ( two values)  the updates of the adam optimizer. The approach leverages the bounded nature of adam updates to design a unbiased quantization scheme - it uses the value of the update to define a bernoulli distribution (+1, -1). They show improvements in speed in several experiments. 

Some questions /  comments, 
1. What is \mathcal{M} on page two . It is not defined. 
2. what does "random gradient of f" mean? Also i believe g_t is a vector . so what is g_t / |g_t|  .. Do you mean elementwise division?
3. Page 4, "Adam do not have this appealing property" can you explain this point further. The point you are making claims that adam does not converge at local minimas but keeps oscillating. 
4. Theorem 1 
      a. statement about "spectral norm of b_i" is bounded. Are we assuming b_i to be a matrix?
5. lot of grammatical errors in the paper. like neede, Lagre, "cost become a bottleneck",  "be friendly to efficient primitive communication primitives" and a lot more.
strength_and_weaknesses: Strength:
1. novel quantization scheme which is easy to implement 
2. Provable convergence as update is same in expectation
3. strong empirical results


Weakness
1. writing needs a lot of work - see some confusions / point outs above

clarity,_quality,_novelty_and_reproducibility: The clarity of the paper is hampered a bit as the paper is riddled with writing issues. See above
summary_of_the_review: The paper seems to be making a novel contribution.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Communication bottleneck is a major bottleneck in large-scale distributed deep learning. The authors propose a new distributed optimization algorithm, Binary SGD-Momentum, which compresses the updates of the model's parameters at each worker. To aggregate the binary quantized values, they devise a hierarchical 1-bit All-Reduce protocol to take advantage of the 1-bit quantized values and inter-node/intra-node communications. They theoretically analyze their algorithm and evaluate its performance numerically.

Weaknesses:

1. The authors claim: "All the existing communication-efficiency optimizers are built upon gradient compression. In contrast, to the best of our knowledge, we are the first to directly quantize the entire model update, which will streamline the quantization." The authors are not aware of an entire subfield of methods (worth tens to hundreds of papers) which quantize model updates. Examples of such methods: DIANA (the first method that achieved this), EF21 (does this for biased compressors such as top-k), MARINA (currently the theoretical SOTA in the nonconvex regime) - and many follow up works. These works show that compressing model updates is theoretically superior to compressing models. This is an important omission.

2. Assumption 4 on (deterministically) bounded stochastic gradients is highly problematic and is not justified.

3. The rate in Theorem 1 does not make sense. One of the reasons is: Theorem 1 assumes that the sequence $( b_t^{(i)} )_j$ is bounded below by some $\rho >0$ throughout the iterations. However, this is not proved, so it may not be true. Even if it is true, it is not clear how small $\rho$ can be. The bound in (6) depends inversely in $\rho$, and becomes vacuous for small values of $\rho$.

4. The writing seems hurried, with many grammatical and stylistic issues.

These are examples of several important issues with the paper; some of them being fatal. The reviewers noticed more issues than this. Some reviewers had a borderline positive view of the paper, but I did not see sufficient reasoning and explanation in these reviews that would be convincing. 

The experimental part of the paper seems to be the key highlight. 

I recommend the authors to remove the theoretical part and focus on the empirical results, or to make a realistic and critical assessment of the results and assumptions, so that the reader would not be mislead but enlightened. 

Unfortunately, I cannot recommend the paper for acceptance in its current form.
justification_for_why_not_higher_score: Fatal issues with the theory and assumptions.
Decision: Reject