Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 
The authors examine several techniques that lead to low communication updates during distributed training in the context of Federated learning (FL). Under the setup of FL, it is assumed that training takes place over edge-device like compute nodes that have access to subsets of data (potentially of different size), and each node can potentially be of different computational power. Most importantly, in the FL setup, communication is the bottleneck. Eg a global model is to be trained by local updates that occur on mobile phones, and communication cost is high due to slow up-link.

The authors present techniques that are of similar flavor to quantized+sparsified updates. They distinguish theirs approaches into 1) structured updates and 2) sketched updates. For 1) they examine a low-rank version of distributed SGD where instead of communicating full-rank model updates, the updates are factored into two low rank components, and only one of them is optimized at each iteration, while the other can be randomly sampled.
They also examine random masking, eg a sparsification of the updates, that retains a random subset of the entries of the gradient update (eg by zero-ing out a random subset of elements). This latter technique is similar to randomized coordinate descent.

Under the theme of sketched updates, they examine quantized and sparsified updates with the property that in expectation they are identical to the true updates. The authors specifically examine random subsampling (which is the same as random masking, with different weights) and probabilistic quantization, where each element of a gradient update is randomly quantized to b bits. 

The major contribution of this paper is their experimental section, where the authors show the effects of training with structured, or sketched updates, in terms of reduced communication cost, and the effect on the training accuracy. They present experiments on several data sets, and observe that among all the techniques, random quantization can have a significant reduction of up to 32x in communication with minimal loss in accuracy.

My main concern about this paper is that although the presented techniques work well in practice, some of the algorithms tested are similar algorithms that have already been proven to work well in practice. For example, it is unclear how the performance of the presented quantization algorithms compares to say  QSGD [1] and Terngrad [2]. Although the authors cite QSGD, they do not directly compare against it in experiments.

As a matter of fact, one of the issues of the presented quantized techniques (the fact that random rotations might be needed when the dynamic range of elements is large, or when the updates are nearly sparse) is easily resolved by algorithms like QSGD and Terngrad that respect (and promote) sparsity in the updates. 

A more minor comment is that it is unclear that averaging is the right way to combine locally trained models for nonconvex problems. Recently, it has been shown that averaging can be suboptimal for nonconvex problems, eg a better averaging scheme can be used in place [3]. However, I would not worry too much about that issue, as the same techniques presented in this paper apply to any weighted linear averaging algorithm.

Another minor comment: The legends in the figures are tiny, and really hard to read.

Overall this paper examines interesting structured and randomized low communication updates for distributed FL, but lacks some important experimental comparisons.


[1] QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks https://arxiv.org/abs/1610.02132
[2] TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
https://arxiv.org/abs/1705.07878
[3] Parallel SGD: When does averaging help? 
https://arxiv.org/abs/1606.07365


review_title: The paper examines techniques to lower the communication of distributed model updates in a federated setup. The authors focus on low-rank, sparsified, and quantized updates. There are several interesting experiments, but comparisons with state-of-the-art quantization techniques are missing.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a new learning method, called federated learning, to train a centralized model while training data remains distributed over a large number of clients each with unreliable and relatively slow network connections. Experiments on both convolutional and recurrent networks are used for evaluation. 

The studied problem in this paper seems to be interesting, and with potential application in real settings like mobile phone-based learning. Furthermore, the paper is easy to read with good organization. 

However, there exist several major issues which are listed as follows:

Firstly, in federated learning, each client independently computes an update to the current model based on its local data, and then communicates this update to a central server where the client-side updates are aggregated to compute a new global model. This learning procedure is heuristic, and there is no theoretical guarantee about the correctness (convergence) of this learning procedure. The authors do not provide any analysis about what can be learned from this learning procedure. 

Secondly, both structured update and sketched update methods adopted by this paper are some standard techniques which have been widely used in existing works. Hence, the novelty of this paper is limited. 

Thirdly, experiments on larger datasets, such as ImageNet, will improve the convincingness. 

review_title: The studied problem seems to be interesting, but there exist several major issues in the paper.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes several client-server neural network gradient update strategies aimed at reducing uplink usage while maintaining prediction performance.  The main approaches fall into two categories: structured, where low-rank/sparse updates are learned, and sketched, where full updates are either sub-sampled or compressed before being sent to the central server.  Experiments are based on the federated averaging algorithm.  The work is valuable, but has room for improvement.

The paper is mainly an empirical comparison of several approaches, rather than from theoretically motivated algorithms.  This is not a criticism, however, it is difficult to see the reason for including the structured low-rank experiments in the paper (itAs a reader, I found it difficult to understand the actual procedures used.  For example, what is the difference between the random mask update and the subsampling update (why are there no random mask experiments after figure 1, even though they performed very well)?  How is the structured update "learned"?  It would be very helpful to include algorithms.

It seems like a good strategy is to subsample, perform Hadamard rotation, then quantise.    For quantization, it appears that the HD rotation is essential for CIFAR, but less important for the reddit data.  It would be interesting to understand when HD works and why,  and perhaps make the paper more focused on this winning strategy, rather than including the low-rank algo.  

If convenient, could the authors comment on a similarly motivated paper under review at iclr 2018:
VARIANCE-BASED GRADIENT COMPRESSION FOR EFFICIENT DISTRIBUTED DEEP LEARNING

pros:

- good use of intuition to guide algorithm choices
- good compression with little loss of accuracy on best strategy
- good problem for FA algorithm / well motivated
- 

cons:

- some experiment choices do not appear well motivated / inclusion is not best choice
- explanations of algos / lack of 'algorithms' adds to confusion

a useful reference:

Strom, Nikko. "Scalable distributed dnn training using commodity gpu cloud computing." Sixteenth Annual Conference of the International Speech Communication Association. 2015.


review_title: Reducing uplink communication in distributed setting: a strategy that works well, could use more clarity and insight.

Meta-review: The authors study the problem of reducing uplink communication costs in training a ML model where the training data is distributed over many clients.   The reviewers consider the problem interesting, but have concerns about the extent of the novelty of the approach.  As the reviewers and authors agree that the paper is an empirical study, and the authors agree that the novelty is in the problem studied and the combination of approaches used, a more thorough experimental analysis would
benefit the paper.
Decision: Reject