Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper revisits non-convex stochastic decentralized optimization and extends existing convergence analysis with special weight matrices to establish an optimal convergence rate with general weight matrices. The algorithms proposed has a convergence rate that matches DeTAG's rate but avoids gradient tracking and saves half of the communication overheads per step.
strengths_and_weaknesses: The paper studies decentralized optimization algorithm over general communication weight matrix, but the weight matrix has to be fixed over time, so it does not seem to apply to decentralized algorithms where the communication pattern is different in different steps.

When the matrix is fixed, the paper proves the optimal convergence rate for nonconvex objectives (where the lower bound and upper bound match). Also an algorithm MG-DSGD is proposed to achieve that optimal convergence rate while being simpler and less communication costy than existing algorithms such as DeTAG.
questions: Is it possible for a time-varying communication pattern to improve the convergence? It will be nice to include the discussion if some conclusions can be drawn.
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors investigate the optimal convergence rate for smooth and nonconvex decentralized stochastic optimization. Specifically, given function class F_L, oracle class O_{\sigma^2}, and weight matrix class W_{n,\beta}, the authors establish a tight lower bound for any \beta within (0,cos(\pi/n)). An algorithm based on multiple-step gossip is also proposed.

Post-rebuttal update: I have raised the score from 5 to 7.


strengths_and_weaknesses: Strengths:
1. A tight lower bound for any \beta within (0,cos(\pi/n)).
2. An algorithm that matches the lower bound.

Weaknesses:
1. For the optimal rate of decentralized stochastic optimization algorithms, readers should be interested in the following question: “Given a network topology, what are the best algorithm and its rate?” In [33], the optimal rate is in the sense of “given a line network of n nodes, finding an optimal algorithm with the best weight matrix (and hence \beta).” It is limited to the line topology, but consistent to our intuition. In this paper, the optimal rate is in the sense of “given a network of n nodes, finding the worst topology and corresponding weight matrix whose connectivity measure is \beta, and finding an optimal algorithm.” This is a little bit confusing because in most cases we do not prefer the worst weight matrix. Please clarify.
2. Related to the above comment. From the very beginning the authors mention that “this paper revisits non-convex stochastic decentralized optimization and establishes an optimal convergence rate with general weight matrices.” Weight matrix design should be a part of algorithm development. I cannot fully understand the necessity of finding the worst weight matrix.
3. In the problem setup the authors talk about the zero-respecting policy, but do not mention it in the proof.
4. “Surprisingly, we find in MG-DSGD that the multiple gossip technique can significantly reduce the influence of data heterogeneity, and the gradient tracking step can be saved to achieve the convergence optimality.” Why?
5. Mistakes: The degree of a 10-node complete graph is 9, not 10. In Line 3 of Algorithm 2, z_i^{(r)} should be z_j^{(r)}.
6. For these reasons, I recommend “borderline accept” and would like to see further clarifications from the authors.

questions: 1. For the optimal rate of decentralized stochastic optimization algorithms, readers should be interested in the following question: “Given a network topology, what are the best algorithm and its rate?” In [33], the optimal rate is in the sense of “given a line network of n nodes, finding an optimal algorithm with the best weight matrix (and hence \beta).” It is limited to the line topology, but consistent to our intuition. In this paper, the optimal rate is in the sense of “given a network of n nodes, finding the worst topology and corresponding weight matrix whose connectivity measure is \beta, and finding an optimal algorithm.” This is a little bit confusing because in most cases we do not prefer the worst weight matrix. Please clarify.
2. “Surprisingly, we find in MG-DSGD that the multiple gossip technique can significantly reduce the influence of data heterogeneity, and the gradient tracking step can be saved to achieve the convergence optimality.” Why?

limitations: N/A.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers decentralized stochastic non-convex optimization problems. The main innovation is the new structure of the connection graph, which can be used to revisiting the lower bounds. In a supplement, the authors apply this graph structure to obtain lower estimates in the non-convex case. Finally, the authors present an algorithm based on FastGossipAverage which achieves lower bounds.  
strengths_and_weaknesses: **Strengths:**

1) The new ring-based graph structure is interesting to me. Previous methods of deriving lower bounds consist in that we fix $\beta$ (in the literature it is also $\chi$), on the basis of this $\beta$ a connection graph (typically a path) with some number of vertices $n$ is constructed. The new graph structure allows to fix not only $\beta$ but also $n$. This can be important. 

2) The rest of the results, including lower bounds for non-convex problems (in the general case and in the PL case), the algorithm that achieves these lower bounds, and the experiments, complement the paper well.

3) The article is quite well written and easy to follow. The literature review is satisfactorily done. 

**Weaknesses:**

1) It is a pity that the new graph construction works only for $\beta \in [0; \cos \pi/n]$.

2) Unfortunately, the rest of the results of the work, except for the construction of the graph are not particularly interesting. Most of them are obvious and represent a simple combination of existing works. Read more below.

3) Lower bounds in the general non-convex case can be obtained by simply replacing the graph in the available results in the literature.

4) Lower bounds in the PL case are actually made for the strongly convex case, and this also can be done by simply replacing the graph in the available results. I also do not like that in the main paper the estimates in the PL case does not show the dependence on the factor $L/\mu$. It replaces by $C$. Most likely this is due to the fact that in the lower bounds $C = \sqrt{L/\mu}$, and in the upper estimates $C = L/\mu$. This spoils the optimality of the algorithm, and perhaps the authors want to hide it.

5) The algorithm, which is set as optimal, is simply an analysis of SGD with inexactness + gossip consensus. Such results are obvious and do not cause much interest.

**Conclusion:**

In this paper the interesting thing is the construction of the new graph, with which one can get more accurate lower bounds. The rest of the facts (including experimental ones) complement the paper and make it more solid, but for me are minor in comparison with the new graph. I am hesitant to decide on acceptance and would like to discuss with fellow reviewers and AС their impressions of the paper. I put a borderline reject, but I'm ready to easily change it after discussion.
questions: The question is about experiments. It is rather rhetorical and I am just interested in your opinion here. 

I sometimes have to work with the learning problems on decentralized architectures. Despite the fact that I have a quite good theoretical experience in gossip protocol, we never use it (neither with single step, nor with multi steps). It's easier to use tricky all-reduce procedures. For me gossip protocol is about simpler tasks and simpler computing devices (not powerful GPU), for example about signal processing and transmission. 

What do you think about it?
limitations: No potential negative societal impact
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper study optimal convergence rates in  decentralized nonconvex (smooth) optimization and develops algorithms to achieve such lower complexity bounds up to log factor. More specifically the key contributions are:

(i) Establishing optimal convergence rates for smooth, non convex stochastic optimization for  mesh networks compliant with gossip matrices whose connectivity measure is not $\cos(\pi/n)$, where $n$ is the number of agents. Example of such graphs are grids, hypercubes, toruses, etc. Previous literature considered lower complexity bound only for linear graphs. 
The authors established lower complexity bounds for ring-lattice graphs, for connective values within $[0,cos(\pi/n)]$; for large $n$ the interval spans [0,1].  A key enabler of such new results is a tight relationship between the connectivity of the graph and its diameter, a fact that was established before for linear graphs (meaning connectivity values equal to $\cos(\pi/n)$). 

(ii) By modifying properly the distributed SGD algorithm, the authors provide a solution method that achieve lower complexity bounds. Differently from the existing method, DeTAC, still achieving lower complexity bounds, the proposed algorithm does not require gradient tracking and hence save one communication (O(d)) per iteration. 

(iii) The authors extend the results above  to the case of nonconvex functions satisfying the PL condition.
strengths_and_weaknesses: Strengths:
 The paper advances the state of the art on SDGD-like algorithms for smooth, nonconvex problems. The authors identified a gap in the literature (the lower complexity bound were established for a restricted class of gossip matrices and associated graphs) and provide a solution to it. The overall presentation is good and the paper is easy to read. The comparison with the state of the art is satisfactory (to my knowledge). 

Weaknesses: 
On the technical side, it is not very clear which new technique has been developed in the proofs to derive some of the results. For instance, once the connection between the connectivity and the diameter of ring-lattice graphs is established, it seems that the proof of Th.2 follows the same path of that in [38]. Same comment apply to the convergence analysis of DSGD; except of a suitable choice of the learning rate, I see a fairly standard proof. Since the proposed MG-DSGD has the same structure of the vanilla DSGD (with a different gossip matrix and a gradient accumulation), same comment applies to its proof of convergence. I do not find the proof under PL particularly more difficult than under strong convexity, the functional relationship between the optimality gap and gradient steps is basically the same.

I would not consider MG-DSGD a new algorithm: it is the DSGD with multiple consensus steps (accelerated) and batch gradients. Both features have been extensively used in the literature.  What is unclear is why the acceleration via multiple round of consensus copes with the data heterogeneity and allows one to get ride of the gradient tracking, which is notoriously known to be beneficial under data heterogeneity. 

 
questions: Is the proof of lower complexity bounds in Th. 2 significantly different from [38], once the connection between the connectivity and the diameter of ring-lattice graphs is established?

The convergence proof of DSGD has been already established in the literature , e.g. in [12, 25]. I think it would be useful if the authors can elaborate in the paper (and in their reply) on the key difference in their analysis, which lead to slightly different results. What was the key enabler for that?

Do the author have some intuition why MG-DSGD can deal with data heterogeneity's efficient as gradient tracking methods? It would be good to provide some inside substantiated by some technical reasoning.  

I would write the upper bounds making explicitly the dependence on L and b, to be consistent with the presentation of complexity bound in the literature. Is the dependence on these parameters of the same order of that in the literature?

I would change the merit function using to measure stationarity: the current one does not capture consensus errors. I would include a consensus error term rather than considering only the gradient along the average. The average is representative of the local iterates only when the consensus error is sufficiently small. It is true however that the consensus error decays faster than the optimization one, but still I would consider a more comprehensive merit function to measure performance of the algorithm. 
limitations: See my comments above under weaknesses.
review_title: null

Meta-review: metareview: This paper presents some new results on near-optimum algorithms for distributed optimization, nearly matching lower bounds. Most of the reviewers are positive about the contributions of this work. However, one issue that came up is the assumption of bounded gradient dissimilarity, which is essentially a gap between upper and lower bounds. While I am recommending to accept this paper, I believe this gap should be more prominently discussed in the abstract and introduction. 


confidence: Less certain
Decision: Accept