Scalable Decentralized Learning with Teleportation

We thank the reviewer for your comments.

Even though the distinction of TELEPORTATION from client sampling has been discussed, it still looks to me a follow-up variant in this category (McMahan 2017) [...] "completely alleviate the convergence rate degradation" is not that interesting any more.

We believe that the similarity between TELEPORTATION and client sampling does not mean that our paper is less novel. Mitigating the degradation caused by large $n$ is an essential topic in decentralized learning, and our paper successfully proposed a method to solve this degradation.

Scaling decentralized learning to a large number of nodes is a challenging and important research topic, since the convergence rate of DSGD degrades when $n$ is significantly large. Existing papers have attempted to alleviate this problem by proposing topologies with a large spectral gap [1,2,3]. However, no existing work can completely eliminate the convergence rate degradation caused by large $n$ (see Table 2 in Sec. D). It has been an open question of how to eliminate this degradation completely.

In this study, we solved this issue by activating only the appropriate number of nodes instead of designing a graph with a large spectral gap. Then, we found that TELEPORTATION can completely eliminate this degradation without sacrificing the linear speedup property $\mathcal{O}(1 / \sqrt{n T})$. We believe that it is surprising that such a simple idea can totally alleviate this degradation.

As the reviewer mentioned, client sampling is widely studied in the federated learning literature to reduce the communication costs between the central server and nodes. However, it is novel to use the idea of activating only a few nodes to mitigate the degradation caused by large $n$ in decentralized learning, and it is not trivial that this idea can totally eliminate the degradation caused by $n$. We believe that the fact that the proposed method is similar to client sampling does not diminish our contribution.

What are the Base-2 graph and what do you mean by superiority of this graph?

Base-2 Graph is a topology that is proposed to alleviate the convergence rate degradation caused by large $n$, and it can achieve a reasonable balance between the convergence rate and communication efficiency. [1] demonstrated that Base-2 Graph enables DSGD to more successfully reconcile accuracy and communication efficiency than the other existing topologies in their experiments. Thus, we compared TELEPORTATION and DSGD with Base-2 Graph in our experiments.

Reference

[1] Takezawa et. al., Beyond Exponential Graph: Communication-efficient Topologies for Decentralized Learning via Finite-time Convergence, In NeurIPS 2023

[2] Ying et. al., Exponential Graph is Provably Efficient for Decentralized Deep Training, In NeurIPS 2021

[3] Ding et. al., . DSGD-CECA: Decentralized SGD with Communication-optimal Exact Consensus Algorithm, In ICML 2023

I appreciate the contributions of the paper; however, I feel that the presentation may overstate the significance of the results. The analysis by Koloskova et al. establishes a connection between the convergence rate and parameters $p$ and $n$, showing that the required convergence time decreases as $n$ increases and increases as $p$ decreases. In scenarios where $p$ depends on $𝑛$, as seen in all the cases presented in Table 2 of this paper, their bounds have the claimed degradation in terms of $n$.

In the context where $p$ depends on $n$, denoted here as $p_n$, the primary contribution of the present paper is to replace $p_n$ in Koloskova et al.'s bounds with $p_k$. The authors then claim to have completely removed the degradation with respect to $n$. However, this claim appears to be somewhat overstated for the following reasons:

1. Dependency of $p_k$ on $n$: While $p_k$ is introduced as distinct from $p_n$, it is not entirely independent of $n$. For instance, in lines 277-282 regarding the Exp. Graph, $k$ is defined as $\max (1,n, \dots )$. Consequently, $p_k$ inherits a dependency on $n$ through $k$.
2. Addition of a new parameter: Even if $p_k$ does not depend on $n$, the introduction of $p_k$ adds an additional parameter to the analysis.. Improvements of this nature could also be achieved using other techniques (e.g. client activation, graph sparsification) that similarly parameterize $p$ with a variable independent of $n$.
3. Limited impact in certain cases: The paper does not demonstrate any improvement in cases where the spectral gap does not scale with $n$.

We thank the reviewer for clarifying the concerns.

We suspect the reviewer feels that our claim that TELEPORTATION can "completely" mitigate the degradation caused by $n$ is overstated. For example, we could remove this statement and modify this statement to be more accurate by claiming that “the convergence rate of TELEPORTATION consistently improves convergence rate as $n$ increases.”

Would this modification address the reviewer's concerns? If the reviewer's concerns are still unresolved, please let us know. We will gladly address your concerns.

See below for more detailed comments.

While $p_k$ is introduced as distinct from, it is not entirely independent of $n$. For instance, in lines 277-282 regarding the Exp. Graph, $p_k$ is defined as $\max (1, n, \dots)$. Consequently, $p_k$ inherits a dependency on $n$ through $k$.

We agree with the reviewer that $p_k$ is not entirely independent of $n$ since the choice of $k$ depends on $n$. However, the dependence of $n$ is no longer harmful in TELEPORTATION, as shown in Theorem 2, where the convergence rate of TELEPORTATION consistently improves as $n$ increases. For this reason, we claimed that TELEPORTATION can completely eliminate the convergence rate degradation caused by large $n$ in the current manuscript, but if the reviewer feels that this claim is an overstatement, we would be happy to revise it as mentioned above.

Even if $p_k$ does not depend on $n$, the introduction of $p_k$ adds an additional parameter to the analysis.. Improvements of this nature could also be achieved using other techniques (e.g. client activation, graph sparsification) that similarly parameterize $p$ with a variable independent of $n$.

As the reviewer mentioned, we need to make $p$ independent of $n$ to alleviate the convergence rate degradation caused by large $n$.

However, we would like to emphasize again that no existing paper has succeeded in eliminating the degradation associated with large $n$ (see Table 2 in Sec. D), and our paper is the first to propose a decentralized learning method whose convergence rate can consistently improve as $n$ increases.

The reviewer mentioned that other techniques might achieve results similar to TELEPORTATION, but we believe the possibility of unpublished alternative methods does not diminish our contribution.

The paper does not demonstrate any improvement in cases where the spectral gap does not scale with $n$.

In decentralized learning, it is essential to reconcile the communication efficiency and convergence rate, e.g., $p_n$. As we discussed in our paper, no existing paper has succeeded in proposing a topology that has a spectral gap that does not decrease as $n$ increases without sacrificing the communication efficiency (see Table 2 in Sec. D). TELEPORTATION is the first method that can eliminate the convergence rate degradation caused by large $n$ without sacrificing the communication efficiency.

We thank the reviewer for our comments.

I am unsure why decentralized learning methods should necessarily converge more slowly as the number of nodes increases [...]

We would like to briefly explain why the convergence rate of DSGD can be degraded as $n$ is substantially large.

DSGD satisfies the following:

$

\bar{\mathbf{x}}^{(t+1)} = \bar{\mathbf{x}}^{(t)} - \frac{\eta}{n} \sum_{i=1}^n \nabla F_i (\mathbf{x}_i ; \xi_i^{(t)}),

$

where $\bar{\mathbf{x}} \coloneqq \frac{1}{n} \sum_{i=1}^n \mathbf{x}_i$ (see the proof of Lemma 11 in [1]). $\nabla F_i$ is calculated at different parameters $\mathbf{x}_i$, and the convergence rate degrades when $\mathbf{x}_i$ is far from $\bar{\mathbf{x}}$. In decentralized learning, each node communicates with a few nodes for communication efficiency. For instance, if we use a ring as the underlying topology, each node communicates with two neighboring nodes. Thus, $\mathbf{x}_i$ comes to be far from $\bar{\mathbf{x}}$ as $n$ increases, and the convergence rate of DSGD degrades when $n$ is substantially large.

The following table summarizes the convergence rate of DSGD with various topologies. For all topology, $n$ appears in the numerator in the convergence rate, and the rate degrades when $n$ is substantially large. We show this table in Sec. D.

The discussion in lines 140-148 seems to rely on the upper bound from Proposition 1. However, this argument feels weak, as the tightness of the upper bound is never discussed. [...] Is there any way to demonstrate that the bound is tight? [...]

Thank you for the comment. [1] analyzed the lower bound of the convergence rate of SGD and showed that it is inevitable that the convergence rate of DSGD degrades when $n$ is substantially large. We will add the following discussion in the revised manuscript.

Specifically, Theorem 3 in [1] shows the lower bound of the convergence rate of DSGD when $f_i$ is $\mu$-strongly convex and $L$-smooth with $\mu = L=1$ and $\sigma=0$. Under these assumptions, [1] showed that it requires

$

\tilde{\Omega} (\frac{\zeta (1-p_n)}{\sqrt{\epsilon} p_n})

$

iterations to converge to accuracy $\epsilon$. See Theorem 3 in [1] for the precise statement. Thus, the convergence rate of DSGD must depend on $p_n$, and it is inevitable that the convergence rate of DSGD degrades when $n$ is substantially large since $p_n$ reaches zero as $n$ increases.

It appears that the theoretical improvement primarily stems from the dependence on $p_n$. Could the authors clarify the source of this improvement? Is it driven by a more refined analysis, or is it due to a novel aspect of the algorithm itself? [...]

As we mentioned above, it is inevitable that the convergence rate of DSGD degrades when $n$ is substantially large. Thus, the property that TELEPORTATION can alleviate the degradation caused by large $n$ is not obtained by the refined analysis but by its methodology.

We would like to briefly explain why TELEPORTATION can alleviate this degradation in the following.

The convergence rate of DSGD degrades when $n$ is substantially large since $\mathbf{x}_i$ comes to be far from $\bar{\mathbf{x}}$ due to the sparse communication characteristic. To prevent $\mathbf{x}_i$ from being far from $\bar{\mathbf{x}}$, TELEPORTATION activates only $k$ nodes. If we use a small $k$, the gossip averaging is performed on a small topology, and the convergence rate does not depend on $p_n$, as shown in Theorem 1. Comparing Proposition 1 and Theorem 1, the second and third terms in the convergence rate in Theorem 1 are better since $p_k \geq p_n$, but the first term is worse. Finally, by carefully tuning $k$, we can balance these terms, obtaining the statement of Theorem 2, and TELEPORTATION can totally alleviate the degradation caused by large $n$.

The proposed hyperparameter-tuning method for selecting the number of active nodes adds another layer of complexity to the method. However, the impact of this additional tuning on overall training time and resource consumption is not fully explored. [...]

We will add the following discussion in the revised manuscript.

By comparing with DSGD, TELEPORTATION has an additional hyperparameter $k$. However, thanks to Algorithm 2, its hyperparameter-tuning requires only $2T$ iteration in total, which is not very expensive.

From the viewpoint of the convergence rate, TELEPORTATION is superior to DSGD, even considering the cost of hyperparameter-tuning with Algorithm 2 since the cost of hyperparameter-tuning with Algorithm 2 is constant, which is negligible compared to the degradation of the convergence rate of DSGD caused by large $n$.

From an experimental viewpoint, TELEPORTATION can be superior to DSGD in the heterogeneous case. Figure 3 shows that TELEPORTATION can train the neural network more stably than DSGD in the heterogeneous case. Thus, even considering the cost of hyperparameter-tuning with Algorithm 2, TELEPORTATION can be superior to DSGD. In the homogeneous case, DSGD and TELEPORTATION achieved comparable performance in Figure 3. Thus, in the homogeneous case, DSGD is superior to TELEPORTATION.

The assumption that any two nodes can communicate directly (as mentioned in the abstract and discussions) is overly idealized. [...]

As the reviewer mentioned, there are cases, such as wireless networks, where there are pairs of nodes that cannot communicate. However, there are also many settings where this condition is satisfied. For example, in a data center or in a setting where nodes are connected to the Internet, any two nodes can exchange parameters. TELEPORTATION can be used in these cases to scale decentralized learning to a large number of nodes.

Furthermore, we would like to emphasize that even in this setting, it is not trivial to eliminate the convergence rate degradation caused by large $n$. In this setting, many existing papers have also tried to alleviate this degradation by designing a topology with a large spectral gap [2-4], while none of the existing papers can completely eliminate this degradation (see the discussion in Section 2.2). TELEPORTATION is the first decentralized learning method that can completely alleviate the degradation caused by large $n$.

It is a limitation that TELEPORTATION can only work when any two nodes can communicate. However, we believe that our work has achieved the important steps for scaling decentralized learning to a large number of nodes in the general case where there are pairs of nodes that cannot communicate.

Reference

[1] Koloskova et. al., A Unified Theory of Decentralized SGD with Changing Topology and Local Updates, In ICML 2019

[2] Takezawa et. al., Beyond Exponential Graph: Communication-efficient Topologies for Decentralized Learning via Finite-time Convergence, In NeurIPS 2023

[3] Ying et. al., Exponential Graph is Provably Efficient for Decentralized Deep Training, In NeurIPS 2021

[4] Ding et. al., . DSGD-CECA: Decentralized SGD with Communication-optimal Exact Consensus Algorithm, In ICML 2023

We thank the reviewer for your constructive feedback.

In line 268, $k$ can be simplified as [...]

Thank you for the suggestion. We have not revised the statement of our theorems in the main paper yet because revising the theorem would complicate my response to your other comments. We will revise it as you suggested in the camera-ready version.

About the experiments: [...]

We are currently conducting these experiments, but we do not have enough time left to show you the results in this rebuttal period. We promise to add these experiments in the camera-ready version.

About the proof of Lemma 9 [...]

To derive the statement of Lemma 9, further expansion of the equations is necessary.

• When $k = \lceil (A^3 / B^6)^{1/7} \rceil \leq \min \\{ \lceil (A / C^2)^{1/5} \rceil, n \\}$, we get

$

\sqrt{\frac{A}{k}} = \mathcal{O} (A^{\frac{2}{7}} B^{\frac{3}{7}}), \quad B k^{\frac{2}{3}} = \mathcal{O} (A^{\frac{2}{7}} B^{\frac{3}{7}}), \quad C k^2 \leq \mathcal{O} (A^{\frac{2}{5}} C^{\frac{1}{5}}).

$

In the last inequality, we use $k \leq \lceil (A / C^2)^{1/5} \rceil$. Note that we need to use $k \leq \lceil (A / C^2)^{1/5} \rceil$ instead of $k = \lceil (A^3 / B^6)^{1/7} \rceil$ to get the statement of Lemma 9. Then, using the above inequalities, we get the following convergence rate:

$

\mathcal{O} \left( A^{\frac{2}{7}} B^{\frac{3}{7}} + A^{\frac{2}{5}} C^{\frac{1}{5}} \right).

$

• When $k = \lceil (A/C^2)^{1/5} \rceil \leq \min \\{ \lceil (A^3 / B^6)^{1/7} \rceil, n \\}$, we get

$

\sqrt{\frac{A}{k}} = \mathcal{O} (A^{\frac{2}{5}} C^{\frac{1}{5}}), \quad B k^{\frac{2}{3}} \leq \mathcal{O} (A^{\frac{2}{7}} B^{\frac{3}{7}}), \quad C k^2 = \mathcal{O} (A^{\frac{2}{5}} C^{\frac{1}{5}}).

$

Note that we use $k \leq \lceil (A^3 / B^6)^{1/7} \rceil$ to obtain $B k^{2/3} \leq \mathcal{O} (A^{2/7} B^{3/7})$. Then, using the above inequalities, we get the following convergence rate:

$

\mathcal{O} \left( A^{\frac{2}{7}} B^{\frac{3}{7}} + A^{\frac{2}{5}} C^{\frac{1}{5}} \right).

$

• When $k=n \leq \min \\{ \lceil (A^3 / B^6)^{1/7} \rceil, \lceil (A/C^2)^{1/5} \rceil \\}$, we get

$

\sqrt{\frac{L r_0 (\sigma^2 + (1 - \frac{k-1}{n-1})\zeta^2)}{k T}} = \sqrt{\frac{L r_0 \sigma^2}{n T}}, \quad B k^{\frac{2}{3}} \leq \mathcal{O} (A^{\frac{2}{7}} B^{\frac{3}{7}}), \quad C k^2 \leq \mathcal{O} (A^{\frac{2}{5}} C^{\frac{1}{5}}),

$

where we use $k \leq \lceil (A^3 / B^6)^{1/7} \rceil$ and $k \leq \lceil (A/C^2)^{1/5} \rceil$. Then, we get the following rate:

$

\mathcal{O} \left(\sqrt{\frac{L r_0 \sigma^2}{n T}} + A^{\frac{2}{7}} B^{\frac{3}{7}} + A^{\frac{2}{5}} C^{\frac{1}{5}} \right).

$

By summarizing the above inequalities, we obtain the statement of Lemma 9. We have clarified the explanation above in the revised manuscript, with the revisions highlighted in blue.

[...] I expect that the proposed algorithm to only achieve the linear speedup of $\mathcal{O}(1 / \sqrt{kT})$.

If we carefully tune $k$, the convergence rate of TELEPORTATION can be $\mathcal{O}(\frac{1}{\sqrt{n T}})$ as shown in Theorem 2.

Here, we intuitively explain why setting $k$ as in Theorem 2 achieves the linear speedup $\mathcal{O}(\frac{1}{\sqrt{n T}})$. See the proof in Lemma 9 and the above response for the precise discussion.

• When $T$ is small, the second and third terms $\mathcal{O}((\frac{(1- p_k)}{T^2 p_k})^{1/3} + \frac{1}{T p_k})$ dominate the convergence rate in Theorem 1. In this case, we would like to use a small $k$.
• When $T$ is large, the first term $\mathcal{O}(\frac{1}{\sqrt{k T}})$ dominates the convergence rate in Theorem 1. In this case, we would like to set $k=n$.

Thus, if we carefully set $k$ so that $k$ increases to $n$ as $T$ increases, we can balance $\mathcal{O}(\frac{1}{\sqrt{k T}})$ and $\mathcal{O}((\frac{(1- p_k)}{T^2 p_k})^{1/3} + \frac{1}{T p_k})$. Then, TELEPORTATION can achieve the linear speedup $\mathcal{O}(\frac{1}{\sqrt{nT}})$ and can totally eliminate the degradation caused by large $n$.

Also, by the above equivalence, the proposed algorithm is only serving as a new implementation of DSGD on large graph without data heterogeneity [...]

We respectfully disagree with this reviewer's comment that TELEPORTATION is equivalent to DSGD in the homogeneous case. Even in the homogeneous case, DSGD suffers from a degradation in convergence rate when $n$ is substantially large because stochastic gradient noise causes the parameters held by each node to drift away. Activating only an appropriate number of nodes in TELEPORTATION is critical to mitigating this issue in both homogeneous and heterogeneous cases.

Specifically, TELEPORTATION with ring and DSGD achieve the following convergence rate when $\zeta=0$, respectively:

$

&**TELEPORTATION**: \\;\\; \mathcal{O} \left( \sqrt{\frac{L r_0 \sigma^2}{n T}} + \left( \frac{L r_0 \sigma^{\frac{3}{2}}}{T }\right)^\frac{4}{7} + \left( \frac{L r_0 \sigma^\frac{4}{3}}{T} \right)^\frac{3}{5} + \frac{L r_0}{T} \right), \\\\
&**DSGD**: \\;\\; \mathcal{O} \left( \sqrt{\frac{L r_0 \sigma^2}{n T}} + \left( \frac{L^2 r_0^2 \sigma^2 (1 - p_n)}{T^2 p_n} \right)^\frac{1}{3} + \frac{L r_0}{T p_n} \right).

$

The convergence rate of DSGD degrades when $n$ is substantially large, while the convergence rate of TELEPORTATION is consistently improved as $n$ increases. Our experiments in Figure 2 can also show the superiority of TELEPORTATION, demonstrating that TELEPORTATION can converge faster than DSGD in both homogeneous and heterogeneous cases.

I suggest the authors to consider along this argument and compare with DSGD in the main text in terms of such equivalence.

Thank you for your suggestion. We will clarify this point in the revised manuscript.

I suggest the authors to expand the experiment section with larger scale experiments such as larger dataset and larger number of nodes $n > 100$.

Since there is not enough time left until the end of the rebuttal, we cannot show the results with a larger number of nodes in this rebuttal period. We will add the results with a larger number of nodes in the camera-ready version.

We thank the reviewer again for carefully reviewing our theorem and response. We promise to include our discussion in the camera-ready version and revise the paper to make our methods more intuitive to the reader.

We thank the reviewer for your positive feedback.

How are the consensus weights $\mathbf{W}$ chosen, and how is it assumed that the randomly activated nodes at any iteration know these weights?

We explain how the sampling of active nodes can be implemented in more detail.

All nodes communicate before starting the training and have the same seed value, as we mentioned in line 215. Then, we sample the active nodes $V_\text{active}$ and assign $\\{1, 2, \cdots, k \\}$ to variables $\\{ \\text{token\\_id}_i \\}$ by using this seed value for each iteration in line 3 in Algorithm 1. Since all nodes have the same seed value, all nodes can know which nodes are active and can obtain the same variables \\{ \text{token\\_id}_i \\} without communicating with other nodes. Using these variables, active nodes exchange parameters with their neighbors and compute the weighted average in lines 11-12 in Algorithm 1.

Would it help if the nodes were sampled taking some other criteria in mind, such as activating nodes that are more likely to have an edge between them?

In our current proposed method, we assume that the active nodes are sampled uniformly. In the federated learning literature, many client sampling strategies have been proposed, as we summarized in Sec. 4. Thus, there might be a better scheme for selecting active nodes than random sampling. However, the primary objective of our work is to address the convergence rate degradation associated with large $n$ and to make decentralized learning scalable to a large number of nodes. We have shown that random sampling of active nodes successfully achieves this goal. We believe that proposing a better node sampling scheme is beyond the scope of our paper, and we leave it for future research.

More generally, how do the authors expect the sampling to be implemented in practice in a fully decentralized topology? More generally, can the authors highlight a practical application scenario?

Sampling of the active nodes can be performed in a decentralized manner. See our first response for more details.

The paper would benefit with some explicit discussion on the dependence of the node-selection strategy, and/or the required number of active nodes on the network topology? For instance, it seems like if the network is sparse, perhaps more nodes need to be activated at every iteration?

In Theorem 2, we show the optimal number of active nodes when we use a ring and exponential graph as a topology to connect active nodes. An exponential graph has a larger spectral gap than a ring. Comparing the results with a ring and an exponential graph, more nodes are activated when we use an exponential graph. This is because the parameters that each node has are more likely to drift away when the number of active nodes increases when a ring is used than when an exponential graph is used.

See the above response for the discussion of the node-selection strategy.