SIGNSGD WITH MAJORITY VOTE IS COMMUNICATION EFFICIENT AND FAULT TOLERANT
Training neural networks on large datasets can be accelerated by distributing the workload over a network of machines. As datasets grow ever larger, networks of hundreds or thousands of machines become economically viable. The time cost of communicating gradients limits the effectiveness of using such large machine counts, as may the increased chance of network faults. We explore a particularly simple algorithm for robust, communication-efficient learning-SIGNSGD. Workers transmit only the sign of their gradient vector to a server, and the overall update is decided by a majority vote. This algorithm uses 32× less communication per iteration than full-precision, distributed SGD. Under natural conditions verified by experiment, we prove that SIGNSGD converges in the large and mini-batch settings, establishing convergence for a parameter regime of ADAM as a byproduct. Aggregating sign gradients by majority vote means that no individual worker has too much power. We prove that unlike SGD, majority vote is robust when up to 50% of workers behave adversarially. The class of adversaries we consider includes as special cases those that invert or randomise their gradient estimate. On the practical side, we built our distributed training system in Pytorch. Benchmarking against the state of the art collective communications library (NCCL), our framework-with the parameter server housed entirely on one machine-led to a 25% reduction in time for training resnet50 on Imagenet when using 15 AWS p3.2xlarge machines.
The authors present a distributed implementation of signSGD with majority vote as aggregation. The result is a  communication efficient and byzantine robust distributed training method. This is an interesting and relevant problem. There are two parts in this paper: first the authors prove a convergence guarantee for signSGD, and then they prove that under a weak adversary attack signSGD will be robust to a constant fraction of adversarial nodes. The authors conclude with some limited experiments.
Overall, the idea of combining low-communication methods with byzantine resilience is quite interesting. That is, by limiting the domain of the gradients one expects that the power of an adversary would be limited too. The application of the majority vote on the gradients is an intuitive technique that can resolve weak adversarial attacks. Overall, I found the premise quite interesting.
There are several issues that if fixed this could be a great paper, however I am not sure if there is enough time between rebuttals to achieve this for this round of submissions. I will summarize these key issues below.
1) Although the authors claim that this is a communication efficient technique, signSGD (on its communication merit) is not compared with any state of the art communication efficient training algorithm, for example:
- 1Bit SGD [1]
- QSD [2]
- TernGrad [3]
- Deep Gradient compression [4]
I think it is important to include at least one of those algorithms in a comparison. Due to the lack of comparisons with state of the art it is hard to argue on the relative performance of signSGD.
2) Although the authors claim byzantine resilience, this is against a very weak type of adversary, eg one that only sends back the opposite sign of the local stochastic gradient. An omniscient adversary can craft attacks that are significantly more sophisticated, for which a simple majority vote would not work. Please see the results in [b1].
3) The authors although reference some limited literature on byzantine ML, they do not compare with other byzantine tolerant ML methods. For example check [eg, b1-b4] below. Again, due to the lack of comparisons with state of the art it is hard to argue on the relative performance of signSGD.
Overall, although the presented ideas are promising, a substantial revision is needed before this paper is accepted for publication. I think it is extremely important that an extensive comparison is carried out with respect to both communication efficient algorithms, and/or byzantine tolerant algorithms, since signSGD aims to be competitive with both of these lines of work. This is a paper that has potential, but is currently limited by its lack of appropriate comparisons.
[1] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/IS140694.pdf
[2] https://papers.nips.cc/paper/6768-qsgd-communication-efficient-sgd-via-gradient-quantization-and-encoding.pdf
[3] https://papers.nips.cc/paper/6749-terngrad-ternary-gradients-to-reduce-communication-in-distributed-deep-learning.pdf
[4] https://arxiv.org/pdf/1712.01887.pdf
[b1] https://arxiv.org/pdf/1802.07927.pdf
[b2] https://arxiv.org/pdf/1803.01498.pdf
[b3] https://dl.acm.org/citation.cfm?id=2933105
[b4] https://arxiv.org/pdf/1804.10140.pdf
[b5] https://arxiv.org/pdf/1802.10116.pdf
########################
I would like to commend the authors for making a significant effort in revising their manuscript. Specifically, I think adding the experiments for QSGD and Krum are an important addition. However, I still have a few major that in my opinion are significant:
- The experiments for QSGD are only carried for the 1-bit version of the algorithm. It has been well observed that this is by far the least well performing variant of QSGD. That is, 4 or 8 bit QSGD seems to be significantly more accurate for a given time budget. I think the goal of the experiments should not be to compare against other 1-bit algorithms (though to be precise, 1-bit QSGD is a ternary algorithm) , but against the fastest low-communication algorithm. As such, although the authors made an effort in adding more experiments, I am still not convinced that signSGD will be faster than 4 or 8 bit QSGD. I want to also acknowledge in this comment the fact that these experiments do take time, and are not easy to run, so I commend them again for this effort.
- My second comment relates to comparisons with state of the art algorithms in byzantine ML. The authors indeed did compare against Krum, however, as noted in my original review there are many works following Blanchard et al.  
For example as I noted https://arxiv.org/pdf/1802.07927.pdf (the Bulyan algorithm) shows that there exist significantly stronger defense mechanisms for byzantine attacks. I think it would have been a much stronger comparison to compare with Bulyan.
Overall, I think the paper has good content, and the authors significantly revised their paper according to the reviews. However, several more experiments are needed for convincing a potential reader of the main claims of the paper, i.e., that signSGD is a state of the art communication efficient and byzantine tolerant algorithm. 
I will increase my score from 5 to 6, and I will not oppose the paper being rejected or accepted. My personal opinion is that a resubmission for a future venue would yield a much stronger and more convincing paper assuming more extensive and thorough comparisons are added.