Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper extends the idea of hierarchical local SGD by extending the top hierarchy level to decentralized communication. The multi-level local SGD is achieved by the edge devices (performing all-reduce per \tau local edge steps in terms of the corresponding hub) and hubs (gossip averaging per q local hub steps with the neighboring hubs).

### pros
* the paper considers a probabilistic form of the local edge update, making the whole system formulation more realistic.
* A convergence analysis is given for the provided system formulation.

### cons
1. the formulated problem can be seen as a decentralized optimization problem with specifically designed time-varying communication topology and local edge update steps. It is better to compare the derived rate with the existing rate (e.g. in [1]) for the case of $p_i=1$, otherwise, it is unclear the tightness of the derived rate.
2. the claim 'if the gradient of F has a large Lipschitz constant, the step size in the algorithm is large' looks strange to me; normally we have stepsize <= 1/L.
3. the motivation example of the system is formed by edges devices and data-center hubs. however, in both theoretical analysis and numerical results, only the iid data case is been investigated. It somehow contrasts motivation.
4. the numerical evaluation setup might be unfair. 
    1. the evaluated decentralized communication over the hubs is unclear to me and why it is a manually generated graph with $\zeta=0.74$.
    2. only the learning curves w.r.t. update step k are visualized. due to the extra gossip averaging steps over hubs, the current observations (i.e. improved convergence speed over local SGD) are reasonable but it is hard to identify the exact benefits of the proposed algorithm. is it possible to use a communication model to simulate some important metrics, e.g. time-to-target-loss? is it possible to include the numerical results of hierarchical local SGD e.g. in Lin et al (i.e. All-reduce is performed for hubs) as an extra baseline?
5. The provided numerical results are limited to the toy problems and may not be sufficient to justify the effectiveness of the proposed algorithm, due to the existing large amount of local SGD work (either empirical or theoretical).

### reference
1. A Unified Theory of Decentralized SGD with Changing Topology and Local Updates, ICML 2020.
review_title: initial review

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper extends (Wang & Joshi, 2018) and proposes MLL-SGD for training models in hierarchic networks, where the network consists multiple sub-networks, and each sub-network contains multiple workers. In the level of sub-networks, models can be averaged. In the level of workers, the local copies of models can be averaged within a sub-network; however, workers cannot communicate directly with those from a different sub-networks. In such setting, MLL-SGD is proved to enjoy certain convergence property.


# Pros
Hierarchic networks are a common object in practice, but current SGD algorithms fail to cover it due to the hierarchic communication restrictions. Though MLL-SGD itself is a quite naïve extension of existing local SGD methods for handling hierarchic networks, the convergence theory is not a trivial work. I think this paper can serve as a ground work for developing more efficient algorithms for training models in hierarchic networks.


# Cons
- Theorem 1 only considers constant step size and shows a (at least) constant upper bound for MLL-SGD. A theorem that involves decreasing step size and a upper bound that decreasing to zero can be more favorable.

- Eq. (2) and (3). Though here the authors claim they take a probabilistic approach, but actually they treat $tau^(i)$ as constants, where they should be random variables. Can you explain what would be a counterpart of Theorem 1 if $tau^(i)$ are random variables?

- The proof mainly follows (Wang & Joshi, 2018) and the technical contribution is limited. With that being said, I appreciate the formal theory for MLL-SGD in the setting of hierarchic networks.

- Weak experiments. It can be great if there are some experiments that involve training models in real hierarchic networks.


In sum, I think this work is OK but not very significant. 

review_title: This paper proposes MLL-SGD for training models in hierarchic networks

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposed a multi level SGD algorithm, where workers are assigned to different groups, and each group averages local workers' model. 

The idea is a natural extension on existing SGD algorithms (and should be beneficial in heterogeneous networks). The proof should not be hard based on existing asynchronous/decentralized SGD proof. My concern about this paper is that it seems to me the algorithm has a similar motivation with grouping SGD:

W. Jiang et al., "A Novel Stochastic Gradient Descent Algorithm Based on Grouping over Heterogeneous Cluster Systems for Distributed Deep Learning," 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID), Larnaca, Cyprus, 2019, pp. 391-398, doi: 10.1109/CCGRID.2019.00053.

which is a straightforward extension of AllReduce SGD. I suggesting also comparing with it in the experiments. My first thought is that this paper should be faster than grouping-SGD when the network between hubs is not good (and that benefit comes from the fact that communication between hubs in this paper is decentralized).

The hub in this paper does not seem necessary to me also, since it is used to average all local workers' model. Why not just do an AllReduce on all local workers and have one of the worker responsible for averaging with other groups? That should be easier to implement and more efficient.
review_title: Unsure about how this compares to grouping SGD

final_score: rating: 7: Good paper, accept
review_content: ## Summary
This paper proposes a new variant of local SGD algorithm to make it be more realistic. In particular, (1) it allows workers to perform different number of local steps, depending on their computational resources; (2) workers are organized in a multi-level structure. Workers connected to one central hub can synchronize frequently and hubs are communicated in an infrequent and decentralized manor.

The authors provide convergence analysis under non-convex, iid data partition settings, and conduct preliminary experiments to validate their theoretical findings.

## Pros
1. This paper is easy to follow and very well-written.
2. It makes a non-trivial extension of (Wang & Joshi, 2018). By introducing probability of taking local updates, the framework allows different workers to take different local steps within a given time interval. This is a realistic setting typically ignored by related literature.
3. The analysis of the proposed algorithm is not trivial. It is nice to see how the authors model the complex algorithm in a simple way, although the formulation is roughly the same as (Wang & Joshi 2018).

## Cons
1. It seems that the results of MTL-SGD cannot recover local SGD? In particular, the additional error terms (the last two terms in (13)) increase with $q^2 \tau^2$. However, in local SGD, the additional error terms increases linearly with $\tau$, as shown in (Wang & Joshi, 2018). I didn't find any discussions on this discrepancy.
2. The experimental results are too limited. Especially, it is hard to see the advantages of MTL-SGD over other two baselines. I encourage the authors to redefine the x-axis in experiments to time slots. Within one time slot, each worker has a probability $p_i$ to perform one local step. In local SGD, in order to finish one round of $\tau$ local updates, the time slots required for one worker is $\tau/p_i$, and hence, the time slots used for one round is $\max_i \tau/p_i$. However, in MTL-SGD, the time slots used per round can be exactly $\tau$ by allowing workers to have different number of local steps. By doing this, MTL-SGD might have much faster convergence than local SGD, in terms of loss versus time slots.

## Post-rebuttal
I've read the authors' response and other reviewers' comments. The response and the updated version clarify my concerns. So I slightly increase my score.
review_title: Solid theoretical analysis but limited empirical validations

Meta-review: The paper studies a hierarchical or multi-level version of local SGD, extending earlier work by (Wang & Joshi, 2018), (Lin et al, 2018) and  (Jiang et al. 2019) among others. It gives novel convergence rates in relevant settings, such as by allowing different workers to take different numbers of local steps within a given time interval. The current analysis is restricted to the IID data case, but still insightful, and might serve as a useful building block for follow-up research in the future.
Smaller concerns remained that the presented multi-level results cannot exactly recover local SGD as a special case. Nevertheless the consensus remained that the overall contributions and relevance of the paper remain above the bar. In the discussion phase, several concerns were clarified and additional deep learning experiments have been added to the paper, which is appreciated.
Decision: Accept (Poster)