Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: This paper proposes to use population algorithms as a mechanism for implementing distributed training of deep neural networks. The paper makes some claims about the relationship to previous work on (asynchronous) gossip algorithms that appear to be incorrect. In fact, the proposed PopSGD algorithm is very closely related to other methods in the literature, including AD-PSGD (Lian et al. 2017b) and SGP (Assran et al. 2018). I recommend it be rejected due to lack of novelty and missing connections to much related work.

The introduction (page 3) mentions that the "matrix characterization is not possible in the population model." Here the "matrix characterization" refers to the typical approach in which gossip algorithms (synchronous or asynchronous) are formulated and analyzed. I'd appreciate if the authors could elaborate on this claim. In the study of gossip algorithms, the organization of time into "global rounds" is purely for the sake of analysis; a global, synchronized clock is not required to implement these methods. In fact, the description of the setup appears to be very similar to the asynchronous time model described used to analyze "randomized gossip algorithms" (see the well-cited paper by Boyd, Ghosh, Prabhakar, and Shah). In the PopSGD case, the choice is simply to allow the complete graph (i.e., any agent can interact with any other agent) rather than restricting interactions of a given agent to be among a subset of the other agents (i.e., its neighbors).

Let me elaborate on the ways in which PopSGD is similar to AD-PSGD and SGP. PopSGD involves interactions between randomly drawn pairs of agents. The AD-PSGD algorithm of Lian et al. (2017b) also performs updates between pairs of agents drawn randomly at every step. The definition of the PopSGD interaction in (1.1) (or equivalently Alg 1) implies that when agents i and j interact, neither i nor j can interact with another agent until the current interaction completes. The main difference appears to be that in Lian et al. (2017b) agents are organized into a bipartite graph where $n/2$ nodes are "active" and initiate interactions with one of the other $n/2$ "passive" nodes (drawn randomly). This is done for practical reasons - to avoid deadlocks.

I also believe that PopSGD can be viewed as a particular instance of the overlap-SGP algorithm proposed in Assran et al. (2018). Overlap-SGP, the way it is described, makes use of one-directional interactions (agent i may receive and incorporate information from agent j without the reverse happening simultaneously). This was also introduced for practical reasons. It is possible for multiple interactions to happen simultaneously, and the pattern of iteractions may vary over time. There is nothing in the analysis, however, that prevents one from restricting to symmetric interactions, in which case one could recover the symmetric updates of PopSGD. To compensate for one-directional interactions, Overlap-SGP tracks an additional variable (the weight, or denominator). However, in the case where interactions are always symmetric as in PopSGD, the corresponding update matrices will always be doubly-stochastic, and in this case the weights are always equal to 1. Thus PopSGD really is identical to Overlap-SGP in this special restricted case where interactions are always pair-wise and symmetric. Moreover, Assran et al. (2018) prove that Overlap-SGP achieves a linear speedup in the smooth non-convex setting.

The experiments don't provide any comparison with other related methods, and the discussion in the introduction isn't sufficient to convince me that there are significant differences between these methods. In the experiments, I also wanted to ask about the mult constant. If it is really possible to achieve linear scaling, wouldn't one hope to be able to get away with mult=1?

The decreasing learning rate schedule used in the description and analysis of PopSGD seems very restrictive. Specifically, in the training of deep neural networks it is common to use much different learning rate schedules. Is it fundamentally not possible to do so with PopSGD-type models, or is it just a limitation of the current analysis approach (specifically for convex functions)? What learning rate scheme was used in the experiments?

Finally, the introduction (p3) emphasizes that it is the population gradient perspective, and the connection to load-balancing processes, which enable one to achieve linear scaling. I disagree with this statement. While I do agree that convexity alone is not sufficient, the key assumption made here (as well as in other work, such as that of Lian et al.), is that all agents draw gradients from the same distribution; i.e., that all agents have access to independent and identically distributed stochastic gradient oracles. In fact, this is stronger than the assumptions made in Lian et al. (2017a and 2017b), and Assran et al. (2018), where it is only assumed that the gradient oracles at each agent are similar, but not necessarily identical.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper considers scaling distributed stochastic gradient descent to large number of nodes.  Paper proposes novel asynchronous variant to decentralized SGD, called PopSGD. It models asynchrony with the population model. Paper theoretically analyzes the proposed method and shows that in the convex case PopSGD has a linear speedup in the number of nodes compared to the sequential training on one node. However, in the non-convex setting, the PopSGD rate doesn’t have a linear speedup. The paper also provides experimental evaluation of PopSGD where they scale PopSGD up to 1000 of nodes in the convex optimization; and also apply PopSGD to neural network training on ImageNet.

My score is weak reject. The major reason is that it is not clear how does this work theoretically and experimentally compares to the previous asynchronous variants of decentralized SGD (Lian et al. (2017b) AD-PSGD and Assran et al. (2018) SGP) or to the centralized SGD (parallel mini-batch SGD) baseline; and what are the benefits of the proposed method. 

Concerns that should be addressed: 

1. No theoretical and experimental comparison with the baselines (see above).

2. Extension to the non-convex case: there is no linear speedup in the number of nodes n. Does this mean that it is better to use Centralized SGD (which has speedup in the number of nodes)? The comparison should be made explicit. 


3. The paper is a bit too long (10 pages) and contains some repetitions. Consider to shorten a bit. (e.g. procedure of splitting data between nodes was described twice on page 2 and 4; proof overview on page 6 could be merged with two steps on page 7)


4. The procedure how to sample nodes uniformly was not discussed in the paper. Moreover, it is also not clear why \Theta(n) updates could be done in parallel. When intersection happens, many nodes would have to wait for the previously selected pairs to finish computation.  


5. Why are the local learning rates required? When scheduler samples the nodes uniformly it can also transmit them the global time count.


6. In the description of data distribution (page 2, paragraph 4-5, page 4, last paragraph): what if there is more samples than available nodes? do the nodes exchange samples or only gradients? Is it possible to have part of the full dataset on every node without sharing it with anyone? 


7. Page 3, line 3: Lian et al. (2017b) and Assran et al. (SGP) also showed that they don’t require global synchronization. 


8. Page 4, line 2: The AD-PSGD rate does have a linear speedup in the number of workers n, so the claim should be corrected. 


9. Page 7: all lemmas and theorems hold only for the global stepsize \eta_t. Would it also hold with local stepsizes \eta_t^i? 


10. Extensions for arbitrary graphs: would it be possible to have one theorem for all possible graphs and see how graph parameters (e.g. spectral gap or others) influence the convergence rate? 


11. Experiments: I didn’t understand the definition of mult constant and what does it control. Re-phrase this paragraph. 

Minor comments: 
- page 1, last line of the paragraph 2: “parameter obtained by node i at time t“ -> “stoch. gradient obtained by node i at time t“? 
- page 2, line 4: “variants(e.g.” -> “variants (e.g.”
- Usually \mu is used for strong convexity parameter. 
- page 3, paragraph 2, “we emphasize that convexity is not enough…” the purpose of this sentence is unclear, what is enough then or why is that important to know? 
- page 3, related work: Nedic at al. Nedic et al. (2017) -> Nedic et al. (2017). The same for the other citation. 
- page 3, related work: PP model is not defined. 
- How can PP model result in a multigraph? If two samples pairs have the same nodes, then they need to be processed sequentially, so it can be modeled with two graphs for different time steps. 
- Population protocol model (page 4): “states store real numbers” -> can they store vectors instead? 
page 5, estimating time and the learning rate section: what happens if the V^i is equal to V_j? Who updates its value? 
- Figure 1(a) was not discussed at all in the text. 
- Page 6, Notation and preliminaries: why it is required that T = O(poly n) is not explained.

review_title: Official Blind Review #3

Meta-review: This manuscript studies scaling distributed stochastic gradient descent to a large number of nodes. Specifically, it proposes to use algorithms based on population analysis (relevant for large numbers of distributed nodes) to implement distributed training of deep neural networks. 

In reviews and discussions, the reviewers and AC note missing or inadequate comparisons to previous work on asynchronous SGD, and possible lack of novelty compared to previous work. The reviewers also mentioned the incomplete empirical comparison to closely related work. On the writing, reviewers mentioned that the conciseness of the manuscript could be improved.

Decision: Reject