Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work investigated a very interesting topic about generalization in decentralized deep learning. The authors identify the consensus distance as the key factor that affects the generalization performance of decentralized training. In general, the paper is well written and there are several interesting observations and discoveries involved regarding the generalization performance of decentralized learning. But the quality and significance of the work seem not very high.

1. There is no clear link between the theory part and the numerical results. (Th1 is based on previous work.) The other results, e.g., remark 2, proposition 3, and lemma 4 cannot claim how the consensus distance affects the generalization error. All the statements are based on the observations in terms of consensus distance shown in eq4. I can only agree that the distance is related to the generalization error.

2. Also, Th1 quantified the convergence rate for SGD, while in the numerical results the authors used accelerated SGD and adam. 

3. How did the critical distance be calculated? For example, what are L and sigma approximated?

4. From the numerical results, the authors at least claim two points of linking the critical consensus distance and the performance: i) the critical distance is important to the initial training phase; ii) a non-negligible consensus distance can improve the generalization performance. There is no convincing explanation that the critical distance contributes to the generalization. Also, there is no clear definition of either the initial training phase or middle phase, since the learning rate is chosen by the authors so that it might not reflect the true convergence phases. (especially in this case a warm-up scheme was used). In all, the discussion about the relation between the general error and critical distance is vague.

5. Except for the ring case, the generalization error of the most decentralized learning results might be worse than the centralization learning within 0.5%, which seems not that significant. Comparing the linear speed up benefited from the decentralized training, is this loss significant?  

In summary, I don’t think the theory part is very strong in this paper, and the relation between the critical distance and the generalization error needs to be further justified. 


review_title: Comments on the effect of consensus in decentralized deep learning

final_score: rating: 7: Good paper, accept
review_content: Summary:

This paper studies the problem of decentralized training where several computing units are used simultaneously to process the data, and computing units are assumed to be connected over a network. The main focus is to better understand the role of consensus, or lack there of, into the generalization abilities of decentralized training. The authors describe an upper bound for dissimilarity of local variables that guarantees the performance of decentralized training is as good as centralized one. Moreover, some heuristic guidelines are proposed to control consensus during training process. Some numerical evidence is also provided.

Reasons for score:

I believe the paper is well written and the results are useful for the literature. There are a couple of issues that need to be addressed. Moreover some context item that need to be elaborated more carefully.

Some items that need to be elaborated.

1. The main argument of the paper sees to be that generalization might be affected by decentralized training, as initially pointed out by Table 1.  However, at some point there is a conceptual leap and the discussion transforms into analyzing convergence rates. Although there is a connection between rates and generalization, one is not equivalent to the other. The provided analysis is done on rates, I do not think one can translate that into generalization so straightforward.

2. The authors claim to analyze the problem theoretically. However, wha seems to be the main result is left as Remark 2. I believe  Remark 2 is a statement that needs to proven, as represents the main issues addressed in the paper, namely, how consensus affects convergence rates.

3. The authors mention that the analysis is made on non-momentum algorithm, but experiments are made with the momentum version. This is an issue, as the translation of the obtained results into the momentum method needs to be proven. How are the authors sure that momentum does not play a role into the dependency on consensus?

4.  One main concept seems to be that \phi_t does not change too fast. This is left for the appendix. Such a main concept needs to be spelled out in the main text.

5. Is there a cite for Lemma 4?,  there seems to be studied in the literature before.

6. I read Remark 2 as the main result rather than Proposition 3.

7. I value the experimental results,  they are rather informative and complete.





review_title: An initial step towards understanding decentralized training

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors consider the decentralized optimization problem and explain the generalization gap using the consensus distance. They show that when the consensus distance does not grow too large, the performance of centralized training can be reached and sometimes surpassed. The conducted experiments are extensive and the delivered message is pretty clear -- Critical consensus distance exists in the initial training phase and ensures good optimization and generalization, while a non-negligible consensus distance at middle phases can improve generalization over centralized training.

On the theory side, the main contribution is Remark 2 and proposition 3, but why remark 2 relates to generalization are unclear (it only shows the convergence rate), neither does proposition 3 (it only shows the consensus distance). How do we relate the convergence rate differences with the generalization capability is unclear. So I would say the abstract is a bit overclaiming, the authors better tune down their claims to practical only, without any theoretical guarantees -- "We identify the changing consensus distance between devices as a key parameter to explain the gap between centralized and decentralized training. We show that when the consensus distance does not grow too large, the performance of centralized training can be reached and sometimes surpassed."  

On the literature side, besides the gossip-based decentralized methods, there are also many primal-dual based decentralized optimization methods [1,2]. In those methods, there will be no mixing matrix and hard to run multiple mixing steps, the authors better also comment on those and discuss how the proposed findings can help these works. 

Overall speaking, I feel the motivation and message delivering is clear, though I am afraid that the main contribution falls into the practical findings (they are also important though) instead of the theoretical guarantees -- there is a mismatch between theory and implementations. 

[1] Mingyi Hong, Davood Hajinezhad, and Ming-Min Zhao. "Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks." International Conference on Machine Learning. 2017.
[2] Haoran Sun and Mingyi Hong. "Distributed non-convex first-order optimization and information processing: Lower complexity bounds and rate optimal algorithms." IEEE Transactions on Signal Processing 67.22 (2019): 5912-5928.

------
update after rebuttal

After reading the author's response, the authors stated that they indeed identify the optimization difficulty and consensus distance in theory, while only empirically justify its generalization on training performance. As also pointed out by reviewers 1 and 3, the gap between the convergence rate/consensus distance and the generalization capability still exists, causing the mismatch between the theory and the simulations. But at the same time, the work can also serve as an initial good start and raises good points for the literature. I will keep my score unchanged.


review_title: Great topic but need more thoughtful discussions

final_score: rating: 7: Good paper, accept
review_content: This paper studies decentralized gradient methods for training deep networks. It focuses on the so-called "critical consensus distance" and how disagreement during different stages of training ultimately effects optimization (training loss) and learning (generalization error). Theory is provided for the case of synchronous symmetric averaging methods, and the paper is complemented with detailed experiments on CIFAR and tiny-ImageNet.

This is a nice contribution to the growing literature on decentralized training for deep neural networks. The connection between consensus distance and performance has previously been studied to a limited extent in various settings, so the contribution of this work is somewhat incremental. However, this paper makes the connection somewhat more rigorous through the theoretical developments in Section 3, and it provides a more detailed empirical investigation than previous work. I expect the results to be useful to those working on decentralized training and am supportive of accepting it.

I have a few suggestions and comments, about which I look forward to hearing from the authors.
1. You mention that consensus distance has previously been investigated to some extent (e.g., Fig 2 in Assran et al. 2019). Are there connections between consensus distance and other quantities that have been considered in the literature to relate training to performance (e.g., gradient diversity as in Yin et al. 2017, or the closely related gain ratio in Johnson et al., 2020). Similarly, is there a connection to stochastic weight averaging (Izmailov et al. 2018) and it's parallel version (Gupta et al., 2020)?
2. It is not clear if there are specific aspects of the tasks considered that are important for the findings to hold. CIFAR-10 and ImageNet-32 are both relatively small datasets. Is it possible that in the centralized setting, ResNet-20 is overfitting, and the error from decentralized SGD has a regularizing effect, leading to better generalization? It would be interesting to perform further experiments to explore if this is the case. 
3. It would also be interesting to know if the results similarly carry over to the standard (higher-resolution) ImageNet training and models (e.g., ResNet-50), to know if the phenomena observed are relevant to large-scale training. While I appreciate that CIFAR and ImageNet-32 experiments are useful for quick experimentation, and running experiments on the standard ImageNet task are much more computationally expensive, CIFAR and ImageNet-32 are not very reflective of tasks where one would normally use distributed or decentralized training, since one can easily train a model on them using a single GPU in a reasonable amount of time (~1 hour).
4. Regarding the experiments in Table 5 (longer training), why focus on prolonging training in phase 1? I would expect that extending later phases would potentially allow to overcome issues due to large consensus distances in phase 1. Did you explore this?
5. The analysis focuses on symmetric (push-pull) mixing. Do you expect the same trends to carry over to push-only methods such as those considered in Assran et al., 2019?
6. Nowadays, the half-cosine learning rate schedule is also commonly used for CV tasks (He et al. 2018). How do you expect this to affect CCD and the analysis leading to Remark 2?
7. How does using more gossip iterations impact the practical utility of these methods? In particular, standard implementations of all_reduce only require that each node communicate 2 copies of the parameters per iteration. Now that we need to potentially perform multiple rounds of gossip between each optimizer update, are decentralized methods still attractive for reducing overall training time? On a related note, Tsianos and Rabbat (2014) also proposed to use multiple rounds of gossip to essentially reduce the CCD for convex problems, and show that it can lead to overall less communication overhead to reach a desired level of accuracy. Is it possible to show something similar in this setting?

Additional references mentioned:
* Gupta, Serrano, DeCoste, "Stochastic weight averaging in parallel: Large-batch training that generalizes well," ICLR 2020 and arxiv:2001.02312
* He, Zhang, Zhang, Zhang, Xie, and Li, "Bag of tricks for image classification with convolutional neural networks," CVPR 2019 and arxiv:1812.01187
* Izmailov, Podoprikhin, Garipov, Vetrov, and Wilson, "Averaging weights leads to wider optima and better generalization," arxiv:1803.05407
* Johnson, Agrawal, Gu, and Guestrin, "AdaScale SGD: A user-friendly algorithm for distributed training" ICML 2020 and arxiv:2007.05105
* Tsianos and Rabbat, "Efficient distributed online prediction and stochastic optimization with approximate distributed averaging" IEEE Trans Signal and Information Procesing over Networks 2016 and arxiv:1403.0603
* Yin, Pananjady, Lam, Papailiopoulos, Ramchandran, and Bartlett, "Gradient diversity: A key ingredient for scalable distributed learning," AISTATS 2018 and arxiv: 1706.05699

review_title: Useful contributions on decentralized methods for training deep network, if somewhat incremental

Meta-review: The authors study the problem of (insufficient) generalization in gossip-type decentralized deep learning. Specifically, they establish an upper bound on the square of the consensus parameter distance, which the authors identify as a key quantity that influences both optimization and generalization. This upper bound (called the critical consensus distance) can be monitored and controlled during the training process via (e.g.) learning rate scheduling and tweaking the amount of gossip. A series of empirical results on decentralized image classification and neural machine translation are presented in support of this observation.

Initial reviews were mixed. While all reviewers liked the approach, concerns were raised about the novelty of the results, the lack of theoretical depth, and the mismatch between theory and experiments. Overall, the idea of tracking consensus distance to control generalization seems to be a practically useful concept.  During the discussion phase the authors were been able to (convincingly, in the area chair's view) respond to a subset of the criticisms. 

Unfortunately, concerns remained regarding the mismatch between the theoretical and empirical results, and in the end the paper fell just short of making the cut. 

The authors are encouraged to carefully consider the reviewers' concerns while preparing a future revision.
Decision: Reject