Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity

Summary

The paper studied distributed asynchronous SGD with heterogeneous communication and computation times for non-convex stochastic optimization problems. In particular, the paper proposed a new algorithm called Shadowheart SGD and analyzed his time complexity. The time complexity is proven to be optimal in the famly of centralized methods with compressed communication by providing a lower bound. This time complexity is also shown to be better than those in the literature.

Strengths

1. The paper considered a general scenario of distributed/federated learning by considering asynchronous SGD, arbitrary computation and communication time, and unbiased compression. 2. The paper proposed a new and non-trivial algorithm called Shadowheart SGD, which is optimal in terms of time complexity. 3. The paper introduced equilibrium time, which is a key parameter to characterize the number of computations and communications in Shadowheart SGD. 4. The the paper also proposed Adaptive Showheart SGD, which does not require the knowledge of equilibrium time, the communication and the computation times.

Weaknesses

1. The paper was not well written and is very hard to read. It reads like a summary of the results that are in the appendix. In addition, the intuitive explanations are very few and many notations were not well explained. 2. The paper considered only IID data distribution. This almost rules out the application of the algorithm in federated learning. The results are nice contributions to the existing results but it seems minor. 3. It lacks experimental results. All the experiments use either logistic regression with MNIST dataset or quadratic optimization and multiplicative noise. Since the paper proposed a new algorithm, i believe the experiments need to be much more extensive.

Questions

1. In page 3, why $D_v$ is a distribution on $\mathbb{S}_{\xi}$?

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The paper only focuses on the IID dataset.

Summary

The paper proposes a method (Shadowheart SGD) for centralized asynchronous optimization with compression. The lower complexity bounds are proposed, as well. It is shown that Shadowheart SGD achieves the lower bounds, meaning that the method is optimal.

Strengths

The main strength is the development of an optimal method. The paper contribution is outlined and clearly presented. The proposed method is compared to others in several regimes of communication delays, showing how Shadowheart SGD can outperform its counterparts.

Weaknesses

Personally, I did not understand the discussion of equilibrium time well. I understand that it comes from the analysis; also the examples are illustrative. But still, can equilibrium time have some interpretation like mixing time or first hit time in Markov chains? Or maybe it is possible to interpret equilibrium time using some random process, like the authors do in [1]. Also citation of MARINA on line 76, page 3 is missing. [1] Vogels, T., Hendrikx, H., & Jaggi, M. (2022). Beyond spectral gap: The role of the topology in decentralized learning. Advances in Neural Information Processing Systems, 35, 15039-15050.

Questions

See question on equilibrium time above.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

The paper is mostly theoretical and does not have negative societal impact.

Summary

This paper considers distributed and centralized smooth non-convex optimization when workers have different computation and communication speeds. These different speeds on the workers (and even possibly the server) characterize the problem's device heterogeneity. The authors provide a new algorithm that uses unbiased compression and, more importantly, assigns a time budget for each communication round to optimize for total time complexity. This time budget is calculated based on the speeds of different workers and is the main contribution of this paper. Adapting classic lower bounds for distributed zero-respecting algorithms, and using RandK compression algorithm, the authors show their algorithm is optimal. The authors also offer extensions, such as an adaptive variant of their algorithm, and consider the setting when server communication requires some time.

Strengths

The paper is well written, and a reader not familiar with the literature gets to a very good understanding of the current literature in the area after reading the first few sections of the paper. The results are also presented in a transparent, easy to understand, and mathematically sound manner. The studied problem is a fundamental problem in distributed optimization, and underlies several more complicated seeming problems in Federated learning. The authors attempt at showing optimality of their procedure at least for RandK also provides context on any scope for improvement in the current result. Finally, the authors consider several important extreme limits as well as baselines, making clear comparisons with them. Overall, it is a good paper with only some flaws that can be corrected using remarks and small additional comments, that can be accommodated in the camera ready version. I support accepting the paper, and am happy to further increase my score based on author rebuttal and discussion.

Weaknesses

I have the following comments in a decreasing order of importance: 1. I am not sure if the lower bound actually holds for all unbiased compression schemes. For instance, if the unbiased compression scheme is to add random noise to the gradient vector before arbitrarily picking a direction to communicate, then it woun't be distributed zero-respecting. Ofcourse, with randK this does not happen because if it picks a co-ordinate it wouldn't make it non-zero if it isn't already. This is an important subtlety and should be incorporated in the discussion, but either removing the above compression scheme I mentioned through an additional constraint in the definition of distributed zero-respecting algorithms (with compression), or state that the lower bound is only for randK compression operator. Otherwise, it is not accurate to say the proposed method is optimal. 2. In the introduction while specifying the scope of the problem, it would also be useful to discuss the issue of bit communication complexity somewhere. It is true that in some settings, the communication time complexity only depends on the total number of communications, but in more optimized channel communication the bit complixty is an important factor as well, and for instance in the general setup $\tau_i$ should be a function of $K$ for say randK compressor. I ofcourse don't expect the authors to solve all problems in a single problem, but discussing this would make the survey more exhaustive in my opinion. 3. The authors should comment on when (12) is a reasonable approximation, even if the calculations are not exact. 4. Small typos: line 112 should be "is not negligible", line 134 should have $t/2$ instead of $t$, unless the authors are using some interlacing idea to compute and communicate simultaneously, in line 217 it should be "it is left",

Questions

1. Do the authors have thoughts on statistical heterogeneity can be considered in this setting? I am concerned that the current algorithm might heavily bias the final output towards the databases of agents that are pretty quick. 2. Do the authors have thoughts on the second weakness I raised above? In particular, it is an open question to obtain algorithms with optimal round and bit communication complexity, and understanding the regime with non-trivial bit complexity can help make progress towards that setting.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Nothing big, but please see my comments above in the weaknesses.

Summary

The paper presents a novel method for non-convex stochastic optimization in an asynchronous centralized distributed setup, focusing on improving time complexity in heterogeneous environments. Additionally, the authors demonstrate that the proposed method achieves theoretically optimal time complexity under compression.

Strengths

1. **Novel Method**: The introduction of Shadowheart SGD guarantees finding an $\varepsilon$-stationary point with optimal time complexity in heterogeneous environments. 2. **Theoretical Contributions**: The paper provides rigorous proofs showing that Shadowheart SGD has better or equal time complexity compared to existing centralized methods. 3. **Optimal Time Complexity**: The time complexity analysis shows that Shadowheart SGD can be significantly better than previous methods in many regimes.

Weaknesses

1. The definition and calculation of equilibrium time are complex and not very intuitive. The implicit nature of this definition might make practical implementation and understanding challenging. 2. While the proposed method improves time complexity, the paper does not fully discuss the impact on final convergence and loss in real-world scenarios with limited training datasets. Additionally, the experiments only compare the loss of different SGD methods under the same wall time, but it would be insightful to know if Shadowheart SGD maintains lower loss when comparing the number of training samples.

Questions

1. Can the process of calculating equilibrium time be simplified or made more intuitive? Are there any practical algorithms or tools recommended for this calculation? 2. Similar to Weakness 2. Regarding the impact on convergence and loss in scenarios with limited training datasets, how does Shadowheart SGD perform when comparing the loss against the number of training samples?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Answer to Authors

Dear Authors, Thank you for the reply. I decided to maintain my score.