Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work studies the problem of decentralized nonconvex optimization problems and it is relevant to the conference. The paper provides convergence analysis for an existing and well-studied algorithm -- stochastic gradient tracking algorithms, without providing any improvements. The paper prove its algorithm the same convergence compared to existing works. There are some light and limited experiments associated with the paper, but only limited to quadratic case.
main_review: The main contribution of the paper is the offering of convergence analysis for an existing and well-studied algorithm -- stochastic gradient tracking algorithms for decentralized nonconvex optimization. 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.

The gradient tracking algorithm for decentralized nonconvex optimization is well-studied by [1], and the linear speed up rate is also well-explored by many scholars [2]. The main contribution of this work is a combination of above works into a new paper, without any convergence rate improvement [both at $\sigma / \sqrt{nT}$]. Also, the simulation is based on simple quadratic functions only, which is way too simple in current deep learning era and further weaken the work significance.

In short, the derived algorithm and rates seems to be correct. However, the paper is still a combine-then-twist work based on top of several existing works and show no improvement compared to existing works. The paper could be strengthened by demonstrating more significant results instead of incremental.  

[1] P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016.

[2] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. "$ D^ 2$: Decentralized training over decentralized data." In International Conference on Machine Learning, pp. 4848-4856. PMLR, 2018.

============================================
After response period: I have carefully and thoroughly read the article and all responses and discussions. As many other reviewers also mentioned, this work is trivial and includes many typos and flaws. I keep my score unchanged.
limitations_and_societal_impact: Please provide discussion on the limitations and potential negative societal impact of the work per NeurIPS' request.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the gradient tracking method for decentralized optimization. While it is widely used, its convergence rate is not optimal compared with some other methods. This paper provides a tighter analysis for nonstrongly convex problems, strongly convex problems, and nonconvex problems. Faster convergence rates are proved in this paper.
main_review: Originality: This paper studies a widely used method and gives improved convergence rates analysis. The analysis framework follows [15]. However, a few crucial differences remain due to the specification of GT, and moreover, improved convergence rates are proved. To my best knowledge, all the previous conplexities depend on $\frac{1}{p^2}$, while this paper improves it to $\frac{1}{pc}$, and $c$ can be controled in practice, such as $c=1$ when we set $W$ to be $\frac{I+W}{2}$. So I think the analysis in this paper is novel.

Quality: The theory is technically solid. This is a complete work. However, I think more details of the proof should be provideded in the final version.

Clarity: I think this paper should be written more carefully in the final version.

Significance: I think the results in this paper are important. It provides a new way to analyze GT, and faster convergence rates are proved than previous work.

Comments:

1. The authors claim that they improve over all known results on line 41. I suggest to cite "Sulaiman A. Alghunaim, Ernest K. Ryu, Kun Yuan, and Ali H.Sayed. Decentralized proximal gradient algorithms with linear covnergence rates. IEEE trans. on automatic control", which proved the $O( ( \frac{L}{\mu} + \frac{1}{p^2} )log\frac{1}{\epsilon} )$ complexity for strongly convex problems. As a comparison, this paper only proves the $O( \frac{L}{\mu p} log\frac{1}{\epsilon} )$ one ($\sigma=0$ and $c=1$ in (7)), which is slower when $\frac{L}{\mu} > \frac{1}{p}$.

2. The GT algorithm on line 112 does not lead to steps 3 and 5 in Algorithm 1. I suggest to write W on the left hand side.

3. What is $\eta_t$ in step 3 of Algorithm 1? The stepsize is $\gamma$ in the input description.

4. The authors claim that their results can be used to time-varying graphs on line 172. I am not sure whether it is correct because there are some challenges, such as the non-symmetry of $W_{l,\tau}$ (thus, no eigenvalue decomposition exists), which is defined in Assumption 4 in [15].  Can the convergence rates still be improved over time-varying graphs? Consider (7) for example, I am interested whether the $O( \frac{\sigma^2}{\mu n T} + \frac{L\sigma^2\tau}{\mu^2 p c^2 T^2} + \frac{LR_0\tau}{pc}\exp(-\frac{\mu pcT}{L}) )$ complexity can be proved, where  $\tau$ is the parameter in Assumption 4 in [15].

5. What is $\widetilde W$ on line 189? Is should be defiend in Section 5, rather than in Supp. A.

6. What is $0<a11$ on line 555?

7. How the inequality below line 571 comes? I think more details should be provided, rather than checking the proofs in [15].



limitations_and_societal_impact: I suggest to compare with "Sulaiman A. Alghunaim, Ernest K. Ryu, Kun Yuan, and Ali H.Sayed. Decentralized proximal gradient algorithms with linear covnergence rates. IEEE trans. on automatic control", and discuss the complexity comparisons.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper studies  the gradient tracking (GT) algorithm for stochastic distributed optimization problems over undirected, static graphs; nonconvex, strongly convex and weakly convex local objective functions are considered. The claimed contribution is a new line of analysis unlocking tighter (asymptotic) convergence rates than those already developed in the literature. The impact of some network parameters on the convergence rate is also discussed, and validated via some (albeit limited)  numerical results. 
main_review: The paper is overall well written (I found only minor typos); statement are rigorous and clear. 

On the technical side, I think that the major differences from existing proofs (in particular those in [15]) are twofold:
1. Eq.  (11) and Lemma 5 open the way to establish contraction of the error dynamics; this approach is new to my knowledge, and is of general interest. 
2. A thither analysis of the tracking error with respect to [15] is provided, which allows the authors to remove in the final error bound the dependence of data dissimilarity 
However, the rest of the analysis is fairly standard and does not add much to the classical roadmap followed to study such distributed algorithms. Overall the technical contribution is a bit limited. 

When it comes to the new rate bounds, I have some comments which deflect from authors' assessments.

1. A key motivation provided by the authors to study GT methods is the potential heterogeneity of data across the agents. But if this is the case, the assumption that all the functions f_i have the same strong convexity constant \mu and Liptschitz gradient constant L is quite restrictive. On the other hand, if such constants are different for each agent (which in my opinion is more compatible  with data heterogeneity) , then the convergence results would read in terms of L=\max_i L and \mu=\min_i \mu_i. If so, the claimed bound are no longer tight, as claimed by the authors. For instance, the following papers (although in the deterministic setting) provide tighter bounds for the strongly convex case (Table 1):

Haishan Ye,  Ziang Zhou,  Luo Luo, Tong Zhang, "Decentralized Accelerated Proximal Gradient Descent," NeurIPS 2020
(the non acceleration comes as special case, note the dependence of the rate on the global condition number)

Ying Sun, Amir Daneshmand, Gesualdo Scutari, Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation," arXiv:1905.02637

including other non GT schemes, e.g., 

H Li and Z Lin "Revisiting extra for smooth distributed optimization," - SIAM Journal on Optimization, 2020 

I think that a much stronger contribution would be developing the analysis under different \mu_i and L_i, still showing dependence of the rates on the parameters \mu and L of the average loss F. However, it is not clear to me that the current analysis extend to this more general case. 

2. The comparison in the table can be improved. I do not think that all the rate bounds therein refers to the "same" optimality measure. Speaking of which, I think that characterizing the optimality of the average of the iterates does not capture directly the consensus error. I find more suitable a merit function in terms of the local agents' variables rather than just the average (which does not provide any info about the distance of the local copies from the solution). I encourage the authors to redo the analysis incorporating explicitly in the optimality matrix the consensus error. 

3. The authors may want to compare their result with those in 

K Yuan, S A. Alghunaim, B Ying and A H. Sayed "On the Influence of Bias-Correction on DistributedStochastic Optimization," IEEE Trans. Signal Processing, 2020

The exact diffusion scheme there is another form of gradient correction. 

4. Simulations are limited. I would have expected a comparison of the GT with other distributed method employing some form of gradient correction to check whether these methods exhibit different behaviors in practice. This would also validate the tightness of the rate results. 


Some typos: 
------------------

1. line 113: Hence *and*

2. line 141: Section 4.1, *and .*


limitations_and_societal_impact: Some limitation in the algorithmic analysis and results are already mentioned in points 1 and 2 and 4 of my review above. I do not see other limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes Gradient Tracking, a very common decentralized optimization algorithm, in the stochastic setting. The authors first introduce the standard gradient tracking algorithms, along with the assumptions they use to analyze it. Then, they provide convergence results in 3 main settings: non-convex, strongly-convex and weakly-convex. In each case, the leading order term matches the rates of centralized mini-batch SGD, meaning that the methods are fast (at least when this term dominates). It is argued that many interesting extensions naturally fit in this framework and could be adapted without too much efforts.

Then, a proof sketch is given, and highlights the importance of studying the consensus difference X_t - \bar{X_t}, where \bar{X_t} is the average over all nodes, instead of studying just X_t. The other key ingredient is that a simple recursion, can be written with the consensus difference on both GT variables. Although the operator J involved in this recursion is not contractive at each step (spectral radius greater than 1), J^i with i large enough is contractive (spectral radius smaller than 1/2), which allows to prove convergence of the recursion.

Then, the rates obtained for Gradient Tracking are compared with rates previously obtained in the literature, and they compare favorably overall. Finally, some toy experiments are given to analyze the impact of the graph-dependent constants c and p that were introduced and that appear in the higher order terms. These experiments seem to confirm the theoretical rates. 
main_review: The paper is globally clear and well-written, and state of the art is reviewed well. The results are significant since they show that gradient tracking, a very standard approach for linearly converging decentralized learning, achieves good rates in the stochastic setting as well. 

Reference [14] achieves similar results with a simple decentralized SGD algorithm. Yet, I believe that this work is interesting because compared to [14], this paper gets rid of a "data-heterogeneity" term. This is quite important and I believe it is precisely due to using gradient tracking (or any other method that would converge to the true global minimizer without stochasticity, which is not the case of D-SGD). 

Time varying and local updates extensions: does it really only requires slight adaptations of the proof? If so, I believe this could significantly strengthen the results in the paper and should be included. 

I believe that p should be explained more in details, since it is non-standard. In particular, it would be helpful to discuss its relationship with the spectral gap of the graph: I would say from Eq (3) that it is always bigger, but of the same order of magnitude since the max of the eigenvalues should be very close to 1, but it would be good to state this explicitly. Similarly, examples on some standard graphs (ring, grid) could be given. It would also be good to do the same for parameter c, although this is partially done in Section 6.1 (but it could be useful to have it earlier). 

About Section 4.2: This seems to confirm the fact that p and delta are not so different actually. Indeed, in this case, gradient tracking converges similarly to standard (synchronous) gossip, but with delta replaced by p. Section 4.2 may be condensed into a remark to make room for more discussions on p and c. 

Experimental evaluation of the dependence on p and c is a good idea. I believe that linear scaling in 1/p is quite natural (if it is closely related with the spectral gap). For the c^2 term, the range of parameters considered is a bit narrow, but since it is 1/c^2 I understand it is hard to considered much wider choices of parameters.   
limitations_and_societal_impact: No foreseeable societal impact
review_title: null

Meta-review: This paper studies gradient tracking for stochastic decentralized learning. Their new analysis provides improved convergence rates for strongly convex functions. In particular the dependence on p (which is essentially the spectral gap) is changed to pc^2, which is always better since c>p. Moreover, as noted in the paper, c can be controlled and therefore can provide better guarantees in practice as well. This is a clean observation, and perhaps of broader interest if (11) and Lemma 5 can be used to prove contraction in other problems. 

With multiple rounds of communications a reviewer has noted that better rakes in terms of k_g can be obtained. It would be good to include that remark, and in particular emphasize that this paper does not consider multiple rounds of communication. The authors' claim about the analysis extending to time varying graphs and local updates easily are disappointing. Primarily because it is not true as one of the reviewer points out (which the authors agree to), and partly because this is a sloppiness where I am not sure if the authors even analyzed it themselves before putting this claim in the paper. At a latter point someone may think about obviousness of these things when they are unable to extend the results. 
Decision: Accept (Poster)