Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a randomized compress-to-integer operator with a shared scaling factor for use in data communication in distributed SGD.  The resulting algorithm is provably convergent, matches the behavior of SGD up to constant factors, and works well with the all-reduce primitive.  The authors claim three main contributions: the IntSGD algorithm itself, the analysis of convergence rates, and the IntDIANA variant for heterogeneous data distributions (though this is only discussed in the appendices).
main_review: The paper is clearly written, and the experiments show that the convergence issues with the nearest competitor (HeuristicSGD) are not just theoretical.  The main contribution really does seem to be the theoretical analysis of the convergence behavior.  The timing results show a 10-15% improvement over uncompressed distributed SGD (the all-reduce version); not a bad improvement, but not enormous, either.  The point remains that the proposed method requires only all-reduce communication (unlike many competitors) and does not require error feedback (unlike PowerSGD), and so does have a number of advantages over recently-published competitors.

I would have appreciated a little discussion of any shortcomings of the method, or next steps for future work.

Also, though I appreciated the experimental results, having a little more about the IntDIANA results in the body text (as opposed to the appendix) would have been more consistent with the claim that this is a main contribution of the paper.

Minor issues: 

- "By combing (5) and (3)" -> "By combining (5) and (3)"

- "image classifcation" -> "image classification"

- I do not understand the red-blue color coding in some of the equations.

- In the experiments, are the data types float32 (for computation + SGD communication) and int8 for the intSGD communication?  This seems likely based on the communication timing, but it's hard to be sure.
summary_of_the_review: The proposed algorithm represents an improvement in theory over the nearest competitor (the Heuristic IntSGD algorithm), requires only all-reduce style communication, and does not require error feedback.  Though the performance improvements in experiments were not enormous, there certainly were improvements.  I'd like to see the paper in ICLR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: QSGD with compression results addable
main_review: PAPER SUMMARY: This paper presents a new compression algorithm for distributed machine learning, the algorithm is similar to QSGD, but uses a global scaling factor that is known to all parties. This adds additional benefits that the compressed results on each worker are addable.

NOVELTY & SIGNIFICANCE: Having compression results directly addable is a very useful property to support broader range of applications and improve the system performance.
The algorithm itself seems to be a simple trick based on QSGD (and indeed), but this simple trick seems to be quite effective. There are existing work on this topic (such as heuristic-SGD that was referenced in this paper). This paper adds theoretical analysis and better scaling factor choice.

TECHNICAL SOUNDNESS: The proof should be easy just following existing QSGD theoretical analysis with minor modifications. The only concern would be if the magnitude on different party varies a lot, there will be much larger compression error for the parties with smaller magnitude. But this shouldn't affect the (asymptotic) convergence rate.

OTHERS Experiments look fine.

summary_of_the_review: This paper proposes a new compression algorithm for distributed deep learning where the compression results are addable). There are existing work on this topic, and the main contributions of this paper are providing theoretical analysis and giving better scaling factor choice.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a quantized parallel SGD where the gradient coordinates are rounded after scaling: $Q_\alpha(g) = $ round$(\alpha g )/\alpha.$ The scaling factor $\alpha$ determines the quantization error: higher the $\alpha$, lower the quantization error. The authors propose a clever $\alpha$ shared across workers. Such sharing of $\alpha$ allows for in-network aggregation of gradient updates using programmable switches. It also allows for an all-reduce model of parallel SGD which can be much more efficient than the all-gather model. A previous version Heuristic IntSGD uses a scaling factor that is more intuitive (uses all available bits binning the known range), but interestingly its accuracy is suboptimal on some tasks. Other integer rounding methods such as QSGD use a scale $\alpha$ that is not the same across workers and hence it does not allow the all-reduce primitive.


main_review: The authors find a clever scaling factor that makes the convergence proof work. In the experiments, they show that their method works best on one task, but not as well as PowerSGD on another task.

* Can this approach be extended to popular optimization methods such as Adam?
* In Table 2, it will be useful to have the results for Heuristic SGD as well. How does Heuristic SGD perform without the factor $n$ in the denominator of the scaling factor? That will reduce the quantization error, at the cost of removing the protection against overflow. There is no guard against overflow in IntSGD as well.

Minor:
* In Algorithm 1, line 6, is $\| x^k - x^{k-1} \|^2$ a scalar? Is $r_0 = 0 \in R^d$? That would mean all the entries of $r_k$ are equal at any iteration $k$. Looking at Algorithm 2 in the appendix clarifies this, but the authors should explain this in the main text.
* Page 6: What is the linear speedup with respect to?
* After Assumption 1, the authors claim they show several choices of scaling factors $\alpha$. But they show only one choice (the other choice in the supplement is a special case of the first choice) Please adjust the claim accordingly.
* In Tables 1, 2, why are the communication latencies so different for IntSGD(Determ) and IntSGD (Random)? The discrepancies are too high be explained with the standard deviations reported.
* Please run through a spell-checker to fix the few typos.

summary_of_the_review: The scaling factor proposed by the authors helps them show convergence of their quantized SGD. Empirically, the authors were able to show that their method beats competitors only one task out of the two considered.
review_title: null

Meta-review: This paper proposes a theoretically sound and practically effective method to compress quantized gradients and reduce communication in distributed optimization. The method is interesting and worth publication.
Decision: Accept (Spotlight)