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 article discusses network structure for decentralized consensus and optimization. The authors propose EquiTopo, a family of network structures with $O(1)$ consensus rates, i.e., network-independent rates. For both directed and undirected topologies, the authors present static network structures with degrees $O(\ln n)$ and propose counterpart dynamic (time-varying) networks to relax connection degrees to $O(1)$. Lastly, the authors apply their proposed network topologies to decentralized stochastic gradient descent as well as decentralized stochastic gradient tracking algorithms and provide a comparison of the number of rounds required for convergence.
strengths_and_weaknesses: Strengths:
- A novel result is presented for network design in decentralized optimization problems where the consensus rate is independent of the size of the network.
- By reducing the connection degree from $O(\ln n)$ to $O(1)$, constant communication can be achieved per iteration.

Weakness:
- As shown in Theorem 5 and Theorem 6, the convergence rate improvement for DSGD and DSGT only occurs in transient terms.
questions: - Which of the following terms in the convergence rate describes transient iterations (Trans. Iters.)? This needs to be clarified in the description.
It is often necessary to use push-sum algorithms (gradient-push algorithms) for directed networks (static or dynamic). There are, however, no differences between the algorithms proposed for directed and undirected networks in this study. Does this only apply to the network design (EquiTopo) proposed here? In that case, please elaborate in the manuscript.
- Do the theoretical results for DSGD and DSGT presented (Theorem 5 and Theorem 6) represent new results? If not, it is best to present them as propositions and to properly cite the seminal work.
limitations: We have limited control over the network design in decentralized optimization, which is the main limitation of this work. The authors of this paper have pointed out that their work is primarily concerned with defining the communication structure on a central machine with multiple GPUs, i.e., high-throughput scenarios with the capability of making arbitrary connections between entities. However, this challenges robustness extensions where entities may fail to communicate synchronously.
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 proposes a new family of topologies which has a constant degree and a network-size-independent consensus rate and can be used to accelerate decentralized optimization and learning algorithms. 
strengths_and_weaknesses: The paper has a very novel idea. The paper is well written. The results are very interesting. 

The only concern is whether it is feasible to design topologies in this way in real world applications. 
questions: I expect in real applications, the communication topologies are given or constrained.  Does the topology design require each pair of nodes are allowed to communicate?  Is there any examples in which such a topology design is feasible? 
limitations: NA
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: This work  introduces new families of graph topologies having (almost) constant degree and network size independent mixing rates. This has the advantage that each node needs to exchange information with relatively few neighbors while achieving fast mixing rates. The authors propose directed and undirected version of static graphs with desired properties and then propose dynamic graphs for which the degree of each agent is always 1. As expected, the price to pay for this is a degradation in the mixing rate. Finally, the authors incorporate the families of graph topologies into distributed optimization schemes and analyze the graphs impact on the algorithms' performances. 
strengths_and_weaknesses: The main weakness lies in the comparison with  the Erd\H{o}s-R'{e}nyi (ER) random graph. While in Table 1 it is stated that ER graphs yield a consensus rate of $1-\Theta(1/\ln(n)),$ this result seems to have been  improved in the literature.  See for instance Proposition 5 in 

```Network Topology and Communication–Computation Tradeoffs in Decentralized Optimization'' by A. Nedich, et. al., in IEEE Proceedings 2018, 

where it is established that if $p = (1+a)\ln (n)$ one achieves a solution $\varepsilon$ away from consensus in time $\mathcal{O}(\log(\varepsilon^{-1}))$, implying that the rate is invariant with respect to the network size (this is done for undirected graphs). Note that ER random graphs have the additional advantage of guaranteeing that the consensus time will scale as stated above, with a probability $p$ that goes to $1$ as $n \to \infty$. This is in contrast with the families D-EquiStatic and U-EquiStatic  which can be generated algorithmically using Algorithm 3 in Appendix A with the understanding that one can generate a graph with the desired properties with probability $p,$ where $p$ does not improve (go to 1)   as $n$ increases.  

On the other hand, the main strength of the paper lies in the use of the structure of the families D-EquiStatic and U-EquiStatic to build the classes OD-EquiDyn and OU-EquiDyn wherein  all agents are connected via a time-varying graph whose each instance has  degree 1. This naturally leads to a loss in the consensus rate, which is still related to the consensus rate of the ``base''  graph of the D-EquiStatic or U-EquiStatic family.   

That said, given the discussion in the previous paragraph, I would request the authors to highlight the shortcomings of having each agent randomize transmissions to one of its neighbors over a ``base'' ER graph.
questions: I would like the authors to provide some clarification on the topic discussed on the first paragraph in ``Strengths and Weaknesses.'' above.  
limitations: see above
review_title: null

Meta-review: metareview: This paper introduces a framework for communication scheduling in fully connected networks, in order to improve the convergence rate of decentralized learning algorithms (specifically, the mixing rate of the underlying consensus process). Both broadcast/convergecast (one-to-many, many-to-one) and directed/undirected communication is considered. I believe that this is a useful addition to the toolset for decentralized optimization on fully connected networks and therefore recommend acceptance. A limitation not raised by the reviewers appears to be the lack of an efficient method for constructing the graph, as it appears that Algorithm 3 essentially performs a random search that could take a long time to converge if rho is selected close to its limit (or that would not converge if rho was chosen too aggressively). 
confidence: Less certain
Decision: Accept