On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization

Thank you for the positive evaluation of our work! Let us respond to the weaknesses:

Although the algorithms are interpretable, they may be challenging to implement in practical systems.

We agree that our algorithms seem too lengthy, but the goal was to provide a very detailed listing to ensure that the algorithms can be implemented correctly and without challenges. We tried to give as many details as possible.

There is limited experimental validation of the proposed methods.

The main target of the paper was to obtain the fundamental limits of decentralized optimization. Thus, we focused our attention on theoretical results and lower bounds, which we believe are important to understand the nature of decentralized optimization. In Section I, we run our algorithms to test our theory and ensure that the dependencies that appear in theory are reflected in practice. Moreover, we prepared extra experiments with logistic regression and a neural network that the reviewer can find in the global rebuttal response, which we will add to the camera-ready version.

Thank you for your review! We now respond to the weaknesses:

1. This is also somewhat related to the strengths part. While the paper keeps referring to and comparing against some previous works...

Before we answer this comment, note that our new methods are optimal (up to log factor) for all possible parameters $h_i, \tau_{i \to j}, ...$, so if we want to show that some other method is worse, it is enough to show in one (practical) scenario (take $\tau_{i \to j} = 0$ for instance). Returning back to the comment, we totally agree that most of the previous methods designed their methods for a different setting, Gossip-type communication, but it does not mean that we can not compare the previous methods with our new methods. For instance, we consider Asynchronous SGD in the Gossip framework (Even et al 2024) in the scenario when the communication is free or negligible (Section 5.4). This scenario is equivalent to the setting when the Gossip matrix $w_{ij}$ is non-zero for all $i \neq j$ (in one step, one worker can send a vector to all other workers because communication is free). We explain that even in this scenario, when Asynchronous SGD is allowed for free to send one vector to other workers, it is worse than our method. We did similar work with other methods and showed that they are strongly worse (Sections 5.4, B.4, and C.7).

In fact, our setting is more general than the Gossip communication. Indeed, recall that in the Gossip communication, a worker is allowed to get vectors $\{x_j\}$ from other workers through the operation $\sum_{j=1}^n w_{ij} x_j,$ where $w_{ij}$ either zero or not zero. This is equivalent to our setting for the case when the communication time $\rho_{ij} = \infty$ when $w_{ij}$ is zero, and $\rho_{ij} = 1$ if $w_{ij}$ is not zero, and worker $i$ sums the received vectors. But our setting is richer since we allow different communication and computation times, and allow workers to do with vectors whatever they like (not only to sum). We should probably add this paragraph to the paper. Thank you for the good comment!

Finally, the Gossip framework codes the communication graph through the matrix $W = [w_{ij}]$. We propose to code graphs through the times $\rho_{i \to j}$ ($\tau_{i \to j}$). Our approach is closer to real scenarios because, as we explained previously, it includes the Gossip framework.

2. The second point is also somewhat related. I appreciate it that the authors takes computation and communication times into consideration...

In the previous comment, we explained that our time complexity framework is more general. As a consequence, it includes more realistic scenarios than the Gossip framework, for instance. We argue that the time complexity metric is one of the most natural metrics for parallel setting, unlike the iteration complexity metric. Our assumptions are generic and only assume that communication and computation take time, so it is not clear where we overfitted our methods. Of course, it is possible to add other time restrictions to take this setup closer to reality, but our work can be a starting point.

3. Fragile SGD requires a pivot worker which is, in some sense, at the center of the graph, to coordinate the updates...

Fragile SGD and Amelie SGD were designed to show that our lower bounds are tight (up to log factor). We do not deny the possibility of designing methods without pivot workers and spanning trees. However, any other method without these algorithmic components will not beat these methods due to the lower bounds. The fact that the methods distinguish one pivot worker does not contradict the decentralized setting. We agree that Fragile SGD and Amelie SGD, in some sense, mimic the centralized setup, but we are totally allowed to do it. Note that we can design similar methods in the Gossip setting, taking one pivot worker that aggregates all vectors from other workers using $W$ through several steps: in the first step, the pivot worker aggregates vectors from the neighbors $\sum_{j=1}^n w_{ij} x_j,$ in the second step, it aggregates the vector from the neighbors of the neighbors $\sum_{j=1}^n w_{ij} w_{jk} x_k,$ where $w_{jk} x_k$ is calculated in the first step in worker $j,$ and so on. This way, we can aggregate all information in one worker.

Thank you for your time and review. In the following responses, we address the raised problems. In particular, we prepared extra experiments to support our theoretical results, which the reviewer can find in the global rebuttal's PDF. We also have experiments in Section I of the paper. Let us respond to the weaknesses and questions:

I believe it is crucial to provide empirical results to demonstrate the effectiveness of the proposed method from two key aspects:..

Could you provide empirical results for the proposed methods?

In Section I of our paper, we have already conducted experiments with quadratic optimization problems and showed that our theoretical results align with numerical computations. Nevertheless, we have run extra experiments to support our results in the submission. Please consider our results in the pdf we submitted in the global rebuttal. There, we consider experiments with logistic regression and a neural network and show that our new method has the best convergence rate and accuracy in different settings. We will add highlights of the experiments to the extra page of the camera-ready version of the paper.

We believe that we have addressed all concerns raised by the reviewer by conducting extra experiments, and hope that the reviewer will reconsider the score.

I think the proposed methods heavily relies on the pivot worker, which represents a different concept of convergence dependency compared to the spectral gap. ...

Could you provide more discussion about the relationship between the pivot worker and the server?

We agree that our Fragile SGD and Amelie SGD, in some sense, mimic a centralized algorithm. But note that the goal of the paper is to find fundamental time limits of the decentralized optimization in the homogeneous and heterogeneous setup. The standard way to accomplish this goal is to prove a lower bound (Theorem 7) and find a method that attains this lower bound (Fragile SGD, Corollary 1). We have the freedom to design an optimal method in any way as long as this method satisfies the setup's constraints. We designed Fragile SGD and Amelies SGD, valid methods in the decentralized setup. One can design a method without pivot workers and spanning trees, but any other method will never get a time complexity better than our new methods due to the lower bounds.

Let us give a comment on the statement "... the pivot worker possesses significantly greater computation and communication capabilities ..." This is not always true. For instance, consider the example from Section 6. In this example, almost all workers have the same computation and communication capabilities, but we chose the middle worker due to its relative position to other workers. At the same time, all workers are equally loaded with communications and computations. They all calculate stochastic gradients, send and receive the same amount of vectors per second (except the the first and the last worker since they have only one edge). The pivot worker runs an extra process, Process 0, that only aggregates vectors in $g^k.$ However, the aggregation is a negligible operation compared to stochastic gradient computations.

Thank you for your time! Let us address the weaknesses:

First, one of the two algorithms mentioned in the abstract is relegated entirely to the appendix, which is inappropriate for the paper’s structure.

We agree. However, all algorithms, theorems, and discussions that are relegated to the appendix do not give, conceptually and significantly, new information and algorithmic insights. We tried to showcase the most important ideas in the main part. In the camera-ready version, having an extra page, we will provide more important details from the appendix.

Second, the experimental results are also exclusively placed in the appendix, which does not conform to standard layout.

The main goal of this paper is to provide fundamental and theoretical limits of the decentralized setup. We tried to focus on theoretical questions in the main part. For instance, we believe adding details about our lower bounds is more important than experiments. Having said that, we will add experiment highlights on the extra page. Moreover, we prepared extra experiments with logistic regression and a neural network that the reviewer can find in the global rebuttal response, which we will add to the camera-ready version.

Finally, Section 6(Example: line or circle), which serves as the conclusion, fails to provide an effective summary of the entire paper and instead functions more as the concluding part of the theoretical analysis.

Following many previous conference papers published at NeurIPS, the role of the conclusion section plays the Contributions section (Section 3). This section gives a comprehensive overview of the paper. Section 6(Example: line or circle) is not a conclusion. It provides an example with clearer formulas and intuition. We can add a conclusion section instead of Section 6, but it will sacrifice an important example illustrating our new time complexities.

In practical applications, we often cannot choose which node serves as the central node and are instead constrained by existing conditions. In such scenarios, will the proposed algorithm still maintain its current advantages?

We answer this question in Section 5.3. Let us clarify it here. In general, one can choose any pivot worker and spanning trees, and the methods will converge (Theorem 5) with the time complexity (10) from the paper. But to get the best possible convergence time, one should use the rule from Corollary 1. Then we can guarantee the time complexity (11) from the paper, which is optimal (up to log factor). Comparing (10) and (11), one can see the difference is only in $\mu_{i \to j}$ and $\tau_{i \to j},$ which have the relation $\tau_{i \to j} \leq \mu_{i \to j}.$ The term $\mu_{i \to j}$ depends on how we choose a pivot worker and spanning trees in the algorithm. See also the discussion in Lines 181-183, 209-214.

In order to find optimal spanning trees and an optimal pivot worker using the rule from Corollary 1, one has to know $\tau_{i \to j}$ and $h_i.$ In practice, one can run a load testing program that estimates $\tau_{i \to j}$ and $h_i.$ Then, one can substitute these estimations to the formulas to find optimal spanning trees and an optimal pivot worker.

We believe that all the weaknesses pointed out by the reviewer can be addressed with an additional page in the camera-ready version of the paper. We hope that we have responded to all questions and weaknesses. If you have more questions, then please let us know.