Venue: NeurIPS 2022 Conference

Reviews:

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: This paper deeply investigated the role of topology in decentralized learning. Instead of the commonly adopted spectral gap in the literature, it proposed the "effective number of neighbors" concept and further revealed that the benefits of "good" topology are enabling larger learning rates so that it speeds up optimizations. The paper provides a sound proof of the convex case and observed similar behavior in deep learning.
strengths_and_weaknesses: Originality: The role of the topology can influence the step-size choice in decentralized learning is not a surprisingly new observation, but this is the first time I saw a well-quantified way to describe it and show it in rigorous proof.
Quality & Clarity: The presentation is clear and well organized. I can follow the logic and proof easily. The proof looks sound to me.
Significance: The work is a theoretical explanation work, which can be quite useful. However, the conclusion and the proof technique seem to rely on several strict assumptions. Not sure how easy to extend this framework to more general or complicated settings.

questions: 1.  The D-SGD update adopted the uncommonly used probability update rule, i.e. execute the local gradient update with some probability and gossip communication with the rest case. It makes the analysis simplified since the expectation of Lyapunov becomes the convex combination of two steps independently instead of coupling them together. What about the case that one local gradient always followed by one gossip communication? How to modify the proof framework to cover this case?

2. Can we rewrite $M = (1-r)\sum_{k=1}^\infty\gamma^{k-1}W^{2k}$ into the form $M = (1-\gamma) W^{2}(I-\gamma W^2)^{-1}$ (assuming the inverse exists), since it looks closer to toy example Eq. (3). Also, personally feel the Definition I (effective number of neighbors) in the appendix is better moved to the main context so that the reader is easier to understand what the intuition of effective neighbors means.

3. The toy example use an isotropic quadratic function $\mathbb{E} \frac{1}{2}(d^Tx)^2 = \frac{1}{2}\\|x\\|^2$, which has a special property that the gradient noise at the optimal point $w^\star$ vanish so that the linear speedup is established. It is more common to use Least-Mean-Square as the toy example, which is closer to the later theorem form. 
limitations: The nice detailed analysis is based on homogenous data and all workers shared the same loss function. I don't think heterogonous data or different minimizer cases should be covered by the theorem in this paper. But it will be nice to use some experiments to show the sensitivity of the conclusion when that assumption is not valid.
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: In this paper, the authors showed that decentralized learning allows a larger learning rate compared to centralized learning, which can accelerate the training process. The effective number of neighbors is defined in the paper which measures the ratio of the asymptotic variance of the iterations. As a main result, the authors provided the theorem about the larges learning rate that gives the best convergence guarantees based on the local neighborhood size. The authors also provided the results of the experiment based on the CIFAR10 dataset. 
strengths_and_weaknesses: Strengths:
(1) Equations are written in a clear and reader-friendly way.
(2) Visualizations are useful to convey the authors' main idea.
(3) Paper is well-written and easy to follow.

Weaknesses:
(1) The related work section should discuss more related works.
(2) Although the theory of this paper is solid, it would be better to give some theoretical direction for the non-convex problems. Since data-parallel optimization is widely used in deep learning regimes rather than strongly convex problems.
questions: (1) Same as the second point in weaknesses, is there any theoretical direction for the non-convex problems. It's maybe hard to get the same results as the convex case, but there is possible to get some upper bound or lower bound for the learning rate.
(2) In the theory part, the authors use randomized D-SGD defined in equations (4). However, in practice, the standard D-SGD is used widely, which will average the parameters of neighbors and update the parameters every step without probability. It would be better to extend the current theory to the standard D-SGD.
(3) For disconnected cases, it is more reasonable to look at batch size = batch size of decentralized case * num of workers rather than use the same batch size as the decentralized case. In the current setting, the larger stepsize mainly comes from a larger batch size compared to the decentralized case. If we use batch size * num of workers, would these results still hold?
limitations: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
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: The paper analyzes the D-SGD algorithm where workers (nodes) in a graph collaboratively perform stochastic gradient descent of an objective function. While the existing convergence rates of D-SGD mostly depend on the spectral gap of the adjacency matrix (assuming small learning rate), this paper suggests an alternative analysis based on the "effective number of neighbors," which is defined through specific random walks on the communication graph.

In Section 3, the authors define the notion of effective number of neighbors $n_W(\gamma)$, which is roughly the variance reduction rate of random walks (with decay $\gamma$) on the graph $W$ compared to $W = I$. They derive a convergence rate depending on $n_W$, not the spectral gap of $W$, on a quadratic toy problem. They also extend this result to strongly convex functions. This analysis can explain the convergence of D-SGD even when the spectral gap is zero.

Finally, they verify their theory by training VGG-11 on CIFAR-10. They argue that $n_W$ is better aligned with empirical training performance than the spectral gap.
strengths_and_weaknesses: Strengths
- The paper captured a weakness of current theories on D-SGD and provided an improved explanation on its convergence. Now, their theory can explain the convergence when the spectral gap is zero and also better align with empirical performance of neural networks trained with D-SGD.
- The paper introduced an interesting random walk model on a graph as a proxy for the training dynamics of D-SGD. Based on this, they define a novel concept of $n_W$, which is a key in their analysis.
- The paper performed exhaustive experiments on various types of graph (including time-varying topology) to confirm the theory.

Weaknesses
- I believe the writing of the paper can be much improved. There were notations (e.g. $\zeta$, $\bar{\mathbf{P}}$) that are used before defined, so I had to go between the main text and appendix back and forth. 
- In line 149, the paper is giving the rate in terms of $n_W$, which is not yet defined. I think it is logically better to move the result after Section 3.2 (after $n_W$ is defined).
- There were many typos and some of them slowed down my reading significantly.

Typos
- line 193, page 6: $\zeta = d + 2$ instead of $\zeta = d + 1$
- displayed equation below line 471, page 17: $\gamma^{\frac{k - 1}{2}}$ instead of $\gamma^{\frac{k}{2}}$ (think about $\mathbf{z}^{(1)}$)
- displayed equation below line 473, page 17: $\gamma^{k - 1}$ instead of $\gamma^k$ (same reason)
- line 476, page 17: assumptions of "Lemma" 2
- proof of Lemma 4, page 18: Missing subscript of $\mathbf{b}^{(t)}$. Result is correct, but the proof has a wrong scaling. The second line leads to $\gamma (1 - r) \mathbf{b}_{ni + j}^{(t)} + (1 - r)^t$ -- should be fixed.
- line 501, page 18: the inequality is in the wrong direction. Should be $\mathbf{b}^{(t + 1)} \geq ...$.
- line 521, page 19: $\nabla h(x)$
- Figure 13, page 27: the figure and caption say different $\gamma$
questions: - Could you provide a high-level motivation for introducing the decay $\gamma$? I understand a parameter is technically needed to fit the random walk model, but is there a good interpretation of it?
- Is it possible to compare the maximum learning rate in Theorem I with learning rate in other literatures?
- How exactly are the $\gamma$'s in the experiment chosen? From Figure 2, it seems that the ordering of $n_W$ of different graphs depends a lot on $\gamma$. Can you also show what happens to Figure 5&6 if we use different $\gamma$? Are those results still true?
- Is it possible to relax Assumption B (IV)? The toy problem of Section 3 does not satisfy it since the spectrum of $\mathbf{d} \mathbf{d}^\top$ can be arbitrary for $\mathbf{d} \sim \mathcal{N}^d(0, 1)$. Maybe some sort of average case definition is needed (just like Definition C)?



limitations: The authors have well addressed the limitations of their work.
review_title: null

Meta-review: metareview: The paper studies decentralized optimization and considers all machines work on the data that follow the same distribution. Most of the reviewers think the paper is interesting. I recommend an acceptance. 
confidence: Less certain
Decision: Accept