Revisiting 1-peer exponential graph for enhancing decentralized learning efficiency

First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.

[W1] The optimal rate for any $n$ has been achieved in for example [1]. [1] Ding et al. DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm, 2023.

As you suggested, a missing reference [1] will be cited in the revised version. We believe that our study offers advantages by proposing graphs that maximally leverage distributed computing resources capable of supporting multi-peer communication with $k \geq 2$.

[W2] The extension from 1-peer exponential graph to $k$-peer is quite straightforward.

We believe that Section 3, which extends from 1-peer exponential graph to $k$-peer exponential graph, plays a crucial role in establishing the connection between the expected spectral gap and the Discrete Fourier Transform (DFT). While, as you pointed out, the extension from the 1-peer to be $k$-peer exponential graph may not represent a major novelty on its own, its importance lies in enabling a novel analysis of the expected spectral gap through the DFT of the employed filters, specifically, the Moving Average Filters (MAFs) that underlie the $k$-peer exponential graph.

Building on this foundation, Section 4 extends this idea by incorporating Steerable Null Filters (SNFs) alongside MAFs, leading to the formulation of the proposed null-cascade graph. In this context, the $k$-peer exponential graph serves as a critical conceptual and technical milestone towards the development of the null-cascade graph.

[W3] [Q2] Adding more intuition and explanation about MAF and SNF would be helpful.

While the application of DFT to the filters (e.g., MAFs and SNFs) is standard practice in the signal processing community, it may be unfamiliar to many researchers in the machine learning field. Therefore, we will include more intuitive explanations of MAFs and SNFs, along with their frequency characteristics, in the Appendix of the revised version.

[W4] The authors only discussed spectral gap of the null-cascade graph.

See Table 3 in Appendix D, which presents the convergence rates of DSGD with various graphs, including our proposed graphs: the $k$-peer exponential graph and the null-cascade graph. These convergence rates can be derived by substituting the expected spectral gap $p$ and the periodic interval $\tau$ into the convergence expression of DSGD given in Theorem 1. Due to space constraints, we have omitted these details from the main paper.

[Q1] In [26], it should be O(1) instead of o(1).

Thank you for pointing this out. This will be modified in the revised version.

First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.

[W1] Unclear role of commutativity.

- Can asynchronous training be supported in these topologies?

Under synchronized communication among $n$ nodes, the mixing matrices can be applied in an arbitrary order, as long as the corresponding graphs satisfy the commutativity of mixing matrices specified in Definition 4.

- How does commutativity specifically help decentralized training?

We agree this is an important question. Given your insightful comment, we reconsider the benefit of commutativity of mixing matrices in decentralized learning, and a possible idea which may mitigate your concern is summarized as follows:

First, we would like to emphasize that reducing the discrepancy between the global model $\bar{x}^{(r)}$ and local models $x_{i}^{(r)}$, specifically, minimizing $\sum_{i=1}^{n} \| \bar{x}^{(r)} - x_{i}^{(r)} \|$ is crucial for improving the convergence rate of decentralized learning algorithms. This quantity explicitly appears in the convergence rate of DSGD, as stated in Theorem 1 (see proof in [12]). Ensuring the commutativity of the mixing matrices within graphs would help reduce this discrepancy.

To illustrate this, we reformulate the update rules of DSGD recursively, as follows:

$X^{(r+1)} = X^{(r)} W^{(r)} - \eta \nabla F(X^{(r)}; \xi^{(r)}) W^{(r)}$

$= X^{(r-1)} W^{(r-1)} W^{(r)} - \eta \{ \nabla F(X^{(r-1)}; \xi^{(r-1)}) W^{(r-1)} W^{(r)} + \nabla F(X^{(r)}; \xi^{(r)}) W^{(r)} \}$

$\vdots$

$= X^{(0)} W^{(0)} \cdots W^{(r)} - \eta \{ \nabla F(X^{(0)}; \xi^{(0)}) W^{(0)} \cdots W^{(r)} + \cdots + \nabla F(X^{(r)}; \xi^{(r)}) W^{(r)} \}$

$= X^{(0)} \prod_{s=0}^{r} W^{(s)} - \eta \sum_{s_{1}=0}^{r} \{ \nabla F(X^{(s_{1})}; \xi^{(s_{1})}) \prod_{s_{2}=s_{1}}^{r} W^{(s_{2})} \}.$

Next, we investigate the property of $\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})}$ for finite-time convergent graph with periodic interval $\tau$.

[Case 1: Commutativity of mixing matrices is satisfied]

When commutativity of mixing matrices is satisfied, $W^{(\rho(0))} W^{(\rho(1))} \cdots W^{(\rho(\tau-1))} = \frac{1}{n} 1 1^{T}$ for any permutation $\rho$. The product $\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})}$ can be categorized into two cases:

(Case 1a) When $s_{1} \leq r - \tau + 1$, $\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} = \frac{1}{n} 1 1^{T}$.

(Case 1b) When $s_{1} \geq r - \tau + 2$, $\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} \neq \frac{1}{n} 1 1^{T}$.

These results indicate that no discrepancy among $n$ nodes can occur for terms with index $s_{1} \in [0, r - \tau + 1]$ (in Case 1a). In contrast, discrepancy among $n$ nodes can occur for terms with index $s_{1} \in [r - \tau + 2, r ]$ (in Case 1b), which leads to degradation in the convergence rate.

[Case 2: Commutativity of mixing matrices is NOT satisfied]

When we denote $\mod (r, \tau) = \phi$, the product $\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})}$ can be categorized into two cases:

(Case 2a) When $s_{1} \leq r - \tau - \phi + 1$, $\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} = \frac{1}{n} 1 1^{T}$.

(Case 2b) When $s_{1} \geq r - \tau - \phi + 2$, $\prod_{s_{2} = s_{1}}^{r} W^{(s_{2})} \neq \frac{1}{n} 1 1^{T}$.

These results indicate that no discrepancy among $n$ nodes can occur for terms with index $s_{1} \in [0, r - \tau - \phi + 1]$ (in case 2a). In contrast, discrepancy among $n$ nodes can occur for terms with index $s_{1} \in [r - \tau - \phi + 2, r ]$ (in case 2b), which leads to degradation in the convergence rate.

Comparing these two cases, the components that contribute to discrepancies among the $n$ nodes tend to be more significant when $\mod (r, \tau) = \phi$ is non-zero. Although this difference may be small and therefore difficult to observe empirically, we have theoretically demonstrated the advantage of using commutative mixing matrices. To reflect this discussion, we will revise the sentence in the Introduction regarding commutativity and add an Appendix section to explain the potential benefits of commutativity as discussed above.

[W2] Can a filter be designed that directly zeros out undesired frequencies without cascading many filters?

When a large value of $k$ is available, undesired frequencies can be effectively nullified without the need to cascade many filters. For instance, in the extreme case of $k = n - 1$, all non-zero frequencies can be eliminated; however, this corresponds to the complete graph, where each node is connected to all other nodes.

We highlight a fundamental trade-off between the number of nullified frequencies and the value of $k$. In practical network settings, only a relatively small $k$ (i.e., $k \ll n$) is typically feasible. Under such constraints, it is impossible to nullify undesired frequencies without cascading multiple filters.

[W3] In dynamically changing networks where nodes may leave, join, or lose connectivity, the designed structures may no longer satisfy the required properties. Is this correct?

Yes, our problem setting is to construct dynamical graphs given $(n, k)$; namely, dynamically-changing $(n, k)$ scenarios are out of scope.

[W4] Discussion of implementation or runtime cost of Algorithms 3 and 4.

First, we assume that our graph is constructed at the initialization step of decentralized learning. Since we do not consider dynamically changing networks, as you pointed out in [W3], we believe that computational cost would not pose a serious issue.

Second, we emphasize that the runtime cost of Algorithms 1-4 is negligible for many $(n, k)$-configurations. Algorithms 1-3 are straightforward to implement and incur negligible runtime overhead. Algorithm 4, which is used to select the roots $q$, expansions $m$, and communication orders $c$ for computing SNFs, may be complex to implement and may introduce noticeable runtime costs. This potential complexity stems from the fact that combinations of $(q, m, c)$ are not uniquely determined, requiring a greedy search to identify suitable candidates. While we have not exhaustively evaluated the runtime cost for all possible $(n, k)$-configurations, we confirm that for those configurations tested in our experiments (as reported in Section 5 and Appendix F), the runtime costs were negligible. To further address this concern, we will include runtime measurements for the $(n,k)$-configurations used in our experiments and will release the corresponding source code upon the publication of this paper.

[W5] Missing period in paragraph title.

As you suggested, we separate the paragraph title from the body using period in the revised version.

I have read your rebuttal and have decided to keep my rating since my score is already 5 (accept). Good luck!

First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.

[W1] Why do we need to design a new complex dynamic graph?

When the maximum degree $k$ (maximum number of each node connections) is restricted to be a small value $(k \ll n)$, static graphs cannot achieve a spectral gap $p$ such that $1/p$ in Theorem 1 is not large. In Table 3 of Appendix D, we present the convergence rates of DSGD using various graphs, including several static graphs such as ring, torus, and exponential graphs. These results are obtained by substituting the following spectral gap into the convergence rate for DGSD given in Theorem 1:

Ring: $p = O(1 / n^2), k = 2, \tau=1$,

Torus: $p = O(1 / n), k = 4, \tau=1$,

Exponential: $p = O(1 / \log_{2} n), k = \lceil \log_{2}(n) \rceil, \tau=1$.

Among these static graphs, the spectral gap can be improved using the exponential graph; however, it requires $k = \lceil \log_{2}(n) \rceil$ connections. Therefore, it is infeasible when $k$ is restricted to be a small value relative to $n$ (i.e., $k \ll n$).

To address this limitation, dynamic graphs have been explored for communication-efficient decentralized learning. Notable examples include the 1-peer exponential graph, base-(k+1) graph, and EquiTopo graphs.

[W2] Discuss disadvantages of the proposed null-cascade in practical implementation.

We emphasize that Algorithms 1-3 are not difficult to implement. However, as you pointed out, Algorithm 4--which is used to select roots $q$, expansions $m$, and communication orders $c$ to compute SNFs may be complex. This complexity arises because combinations of $(q, m, c)$ are not uniquely determined, requiring a greedy search to identify suitable candidates. To mitigate your concern, we will include a discussion of this limitation in the null-cascade graph implementations, and we will release the organized source code upon publication of this paper.

[W3], [Q4] Verify the efficiency of the proposed null-cascade graph on larger networks.

To address your concern, we conducted additional evaluations using a relatively large network size. While you suggest testing at an even larger scale (e.g., $n > 1000$), such an experiment exceeds the limits of our available computing resources. As a compromise, we selected $(n, k) = (75, 2)$. The evaluation setting follows the same CIFAR-10 classification task with heterogeneous data allocation ($\alpha = 0.1$) as in Section 5.2 (Test 2).

[CIFAR-10 classification ($\alpha=0.1$) with $(n, k) = (75, 2)$]

Even with a relatively large network ($n = 75$), the highest test accuracy was achieved using our proposed null-cascade graph. This indicates that the experimental trend remains consistent with the results reported in the original paper.

We will include additional experimental results using relatively large $n$ in the revised version, along with consensus rate investigations similar to those shown in Section 5.1 (Test 1).

[W4] This paper's theoretical complexity creates barriers to comprehension.

We apologize if parts of our paper were difficult to follow. Balancing accessibility with theoretical completeness within the space constraints has indeed been challenging. We would like to respectfully highlight that other reviewers found the writing to be clear.

[W5] Introducing examples for the practical applications.

A promising application involves decentralized learning of machine learning models, such as deep learning models, across data center networks. As modern data centers are geographically distributed across multiple regions, aggregating all data to a single site is often impractical due to regulatory, privacy, or legal constraints. Therefore, effectively leveraging both the distributed computational resources and the locally stored data at these sites is essential.

Given the operational overheads associated with, e.g., parameter tuning and algorithm implementation, the simplest decentralized learning algorithm, DSGD, is frequently adopted in real-world distributed computing environments. When deploying DSGD over data center networks, one can select a communication graph to perform partial averaging of local models. In this regard, the communication graphs we propose offer significant advantages in terms of both communication efficiency and the test accuracy of the resulting models.

[Q1] What is the advantage of the 1-peer exponential graph?

When the maximum degree $k$ is constrained (e.g., to reduce communication overhead), the spectral gap of a static graph can only be improved up to a certain point. In contrast, allowing dynamically changing connections between nodes opens up the possibility of increasing the spectral gap in expectation.

Motivated by this aim, prior works have explored dynamic graphs, such as 1-peer exponential graph, base-(k+1) graph, and EquiTopo graph. In our work, we further investigate more advanced dynamic graphs, including $k$-peer exp. graph and null-cascade graph.

[Q2] Is constructing such networks time-consuming in practical applications?

[Q3] Do we need to run Algorithm 1 at each iteration?

The communication graph is constructed based on $(n,k)$ at the initialization step, prior to the start of model training, that is, Algorithm 1 does NOT need to run at each iteration. This is identified in line 2 of Algorithm 6 in Appendix F. While, as you rightly pointed out, constructing such networks can be time-consuming, this is required only once at initialization. We suspect this may not have been fully apparent, and we will clarify it in the revised version.

First of all, we sincerely appreciate your insightful comments. We will carefully incorporate your feedback to improve the quality of this paper.

[W1] Empirical evaluations on relatively small networks $(n \leq 30)$.

To address your concern, we additionally conducted evaluations using a relatively large network size (e.g., $n = 75$). The evaluation setting follows the same CIFAR-10 classification task with heterogeneous data allocation ($\alpha = 0.1$) as in Section 5.2 (Test 2).

[CIFAR-10 classification ($\alpha=0.1$) with $(n, k) = (75, 2)$]

Even with a relatively large network ($n = 75$), the highest test accuracy was achieved using our proposed null-cascade graph. This indicates that the experimental trend remains consistent with the results reported in the original paper.

We will include additional experimental results using relatively large $n$ in the revised version, along with consensus rate investigations similar to those shown in Sec. 5.1 (Test 1).

[W2] Limited motivation and benefits of extending from 1-peer exponential graph to k-peer graph.

We may be misunderstanding your question, but if high-throughput distributed computing resources capable of supporting fast $k$-peer communication are available, then increasing the number of connections (with a reasonably large $k$) can enable communication-efficient decentralized training of models. Thanks to your question, we realized that our motivation for designing graphs extended to $k$-peer communication may not have been clearly conveyed. In the revised version of the Introduction, we would like to improve the explanation to make this point clearer.

[W3] Only showing the results based on communication rounds or iterations is inadequate.

Thank you for pointing this out. First, we would like to clarify the limitations of our computing resources: our computational setup consists of eight GPUs in a single server without NVLink connectivity. Due to these constraints, we are required to simulate multiple nodes' updates on a single GPU. For example, when $n=30$, updates from $3$ or $4$ nodes are processed on each GPU. As a result, it is difficult to accurately and fairly evaluate the impact of communication overheads. Moreover, these overheads become particularly significant when the number of neighbors $k$ is large. We kindly ask you to take our computational resource limitations into consideration. We believe that our proposed graphs are well-suited for deployment on more advanced computing infrastructures that offer high throughput and/or native support for simultaneous multicasting.

For this reason, we conducted comparisons with baseline graphs that have the same maximum degree $k$, including the base-$(k+1)$ graph, static random graph, and dynamic random graph (i.e., $(k+1)$-pertite random match graph). We will revise the future work section in Appendix H to reflect this discussion.

[Q1] In the simulation, why choosing k=2?

Although we present experimental results with $k=2$ in the main paper, we also provided additional experimental results for $k \in \{ 3, 4 \}$ in Appendix F (see Table 5 and Figure 33). Our proposed graphs are not limited to the case of $k=2$. If an additional page is available, we will include these extended results in the revised version.

[Q2] Application examples.

A promising application involves decentralized learning of machine learning models, such as deep learning models, across data center networks. As modern data centers are geographically distributed across multiple regions, aggregating all data to a single site is often impractical due to regulatory, privacy, or legal constraints. Therefore, effectively leveraging both the distributed computational resources and the locally stored data at these sites is essential.

Given the operational overheads associated with, e.g., parameter tuning and algorithm implementation, the simplest decentralized learning algorithm, DSGD, is frequently adopted in real-world distributed computing environments. When deploying DSGD over data center networks, one can select a communication graph to perform partial averaging of local models. In this regard, the communication graphs we propose offer significant advantages in terms of both communication efficiency and the test accuracy of the resulting models.