Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers the problem of minimizing the finite-sum of smooth and strongly convex functions in decentralized time-varying networks. The authors establish the first lower bounds on the number of decentralized communication rounds and the number of local computations required to find an approximate solution. They also designed two optimal algorithms that attain these lower bounds. Experiment results of the proposed methods are also presented.
main_review: Originality: The obtained result of lower bound is new, though its proof appears to be a straightforward extension of that in Scaman et al. (2017). The multi-concensus procedure is new to the best of my knowledge. 

Quality: The paper is technically sound. All the claims are equipped with solid proof. The technical results are correct.

Clarity: The paper is well written and organized. 

Significance: I have some concerns on the significance and potential impact of this paper. First, the authors claim that the obtained lower bound is for time-varying networks, but I cannot see how the time-varying property plays a role in the main theorems. Also, what is the lower bound for time-invariant networks? In general, we are expecting the lower bound for time-varying networks to be larger than the lower bound for time-invariant networks, and we are interested in how the time-varying property affects the bound. Second, it is interesting to see that multi-consensus leads to optimal local computation rounds. However, it might be only of theoretical interest because it significantly increases the communication rounds (although the bound on communication rounds remains the same). Since in practice the communication cost is usually the bottleneck, the practical impact of multi-consensus strategy is rather limited. 
limitations_and_societal_impact: There are no foreseeable negative societal impact of this work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the decentralized optimization ove time-varying networks. Lower bounds for smooth and strongly convex problems are proved at the first time and optimal algorithms that attain these lower bounds are provided.
main_review: Originality: This paper establishes the first lower bounds for decentralized optimization over time-varying networks. The task is more challenging than the case of fixed network. I think it is a novel contribution. Optimal algorithms are provided which attain these lower bounds. The presented method ADOM+ is a novel extention of the one in Kovalev 2020. 

Quality: The theory is technically solid. Both lower bounds and upper bounds are provided. This is a complete work. The authors discuss both the strengths and weaknesses of the proposed methods.

Clarity: This paper is written well.

Significance: Decentralized optimization over time-varying networks is an important task in signal processing, automatic control, and federated learning. This paper provides the state-of-the-art results to this task. I think the contributions are important.

Comments:

1. The third assumption on line 102 means that the elements of each column of W(q) sum to 0, which is equivalent to the assumption that I-W(q) is column stochastic. What about the rows? We often assume the double stochastic mixing matrices for undirected graphs, and column (or row) stochastic ones for directed graphs. I suggest the authors to check it carefully whether the row stochastic assumption is really avoided.
 
2. The presented ADOM+ algorithm is not implementable because step 5 dependes on $y^{k+1}$, which is computed in step 8, whle step 8 dependes on $x^{k+1}$, which is computed in step 5. This is a little problem and can be easily addressed. However, I suggest to give a detailed explanation after the presentation of the algorithm.

3. In the experiment, the authors only test the performance of ADOM+ with multi-consensus. According to my experience, the multi-consensus are not working in practice. I suggest to compare ADOM+ with multi-consensus, ADOM+ without multi-consensus, Acc-GT with multi-consensus, and Acc-GT without multi-consensus in the final version. This is not a compulsion in the rebuttal because the time is limited to redo the experiment.

4. Both the ADOM+ algorithm and its analysis are complex. I have read the proof, but I cannot get the ideas. I suggest to provide more intuitions and explanations of the proofs.
limitations_and_societal_impact: This paper discusses the limitations in Section 5.3. I am interested in whether the primal-dual framework can be applied to nonstrongly convex problems. This may be another limination.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work studies the problem of smooth and strongly convex decentralized optimization problems in time-varying networks and it is relevant to the conference. The paper provides both lower bound and optimal algorithms for decentralized optimization that combines several existing works, then apply them in time-varying networks. The paper prove its algorithm is optimal, in sense of the computation and communication complexity. There are some light experiments associated with the paper, thus the practical performance of the approach is somehow validated.
main_review: The main contribution of this paper is to offer both lower bound and rate optimal algorithms for smooth and strongly convex decentralized optimization problems in time-varying networks. The problem is well-motivated and the writing is clear. There are some light simulation results thus the proposed algorithm seems work from both the theory and simulations perspective.

Decentralized distributed optimization in the strongly convex and smooth regime is relatively well studied. In particular, [1] established lower decentralized communication and local computation complexities for solving this problem, and proposed an optimal algorithm called MSDA in the case when an access to the dual oracle is assumed. Under a primal oracle, current state of the art includes the near-optimal algorithms [2], and a recently proposed optimal algorithm OPAPC [3]. The main contribution of this work is an extension of above works into time-varying networks. Thus the obtained lower bound is not surprise. Build up on that, the authors further introduce a rate optimal algorithm which match the rate of lower bound and the results are validated by light simulations. However, the simulation is based on logistic regression which is way too simple in current deep learning era. I don't see any points of an experiments using only 100 data points per node. 

In short, the paper is technically sound and the developments are clear. The derived algorithm and rates seems to be a useful contribution to the literature on decentralized composite convex optimization, showing a modest improvement over the state of the art. ​However, the paper is still a combine-then-twist work based on top of several existing works and could be strengthened by demonstrating more significant results instead of incremental. It could be accepted if there is room, but should not warrant a strong accept due to the lack of novelty and experiments.

[1] Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. (2017). Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference on machine learning, pages 3027–3036. PMLR.

[2] Dvinskikh, D. and Gasnikov, A. (2019). Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems. arXiv preprint arXiv:1904.09015.

[3] Kovalev, D., Salim, A., and Richtárik, P. (2020). Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33.

---
after thoroughly and carefully read the paper and response after rebuttal, the best I can do is to keep my score unchanged (if not lower it). Basically, the response said nothing, and the paper is a trivial combination work with only limited experimental results.
limitations_and_societal_impact: Have the authors adequately addressed the limitations and potential negative societal impact of their work? 
Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies a decentralized optimization problem. There is a set of nodes that collectively want to find the minimum of an objective function that is the sum of local costs. The nodes can communicate on underlying communication graph.  The authors study the trade-off communication v.s. precision. They show a lower bound on the quality of a solution that can be attained given a certain communication budget. They then provide two algorithms that attain this lower bound.

main_review: I must say that I have very limited knowledge on this topic so my review has to be taken with a grain of salt. Yet, I find the paper not easy to read in the many technical part. For instance, I am not sure to understand exactly what is the matrix $W(q)$ defined in section 2.4 and what are the implication of Equation (3) -> in section 5.1, it is written "as discussed in Section 2.4, a decentralized communication round can be represented by a multiplication by [...] W(q)". I would have appreciated more details there. On the other hand, I believe that some part can be shorten (what is the interest of Figure 1? Would not it be better to merge Theorem 2 and 3 into one?)

The lower bound (Theorem 1) seem to be the main contribution of the paper. The authors could comment on the impact of choosing $d=+\infty$ here?  Would it change anything?

The algorithmic part is harder to understand for me. For instance, is it obvious that the multi-consensus algorithm falls into the category of algorithms used in the lower bound of Theorem 1? Also, the contribution with respect to ADOM (Kovalev et al 2021) is unclear.

Finally, the results presented in the paper looks promising but lack details. For instance: what is shown on the y-axis of Figure 2?

**Rebuttal** 
After reading the rebuttal, I am not convinced that the new version will be more accessible.

limitations_and_societal_impact: To be more accessible to a non-expert like me, the assumption behind the communication model and the contribution with respect to related work could be better explained.
review_title: null

Meta-review: The paper presents a significant contribution to distributed optimization over time-varying networks. In particular it establishes a lower-bound on complexity  by identifying a specific pattern of time-varying networks, and proposes two schemes (one, ADOM+, requiring access to dual gradients, and another one avoiding the need to access such dual gradients) that are proven to match this lower bound. This thus gives a rather complete treatment of the problem of distributed convex optimization for time-varying networks as those considered in the paper. 
While the paper's analysis is made for specific assumptions (eg on the type of time varying networks) and the lower bound is of a worst-case nature, the authors clarified these points, and proposed to develop discussions of these and other points in the final version which should put the paper in a correct perspective. 
Decision: Accept (Poster)