Distributed learning is essential for training large-scale deep models. Asynchronous SGD (ASGD) and its variants are commonly used distributed learning methods, particularly in scenarios where the computing capabilities of workers in the cluster are heterogeneous. Momentum has been acknowledged for its benefits in both optimization and generalization in deep model training. However, existing works have found that naively incorporating momentum into ASGD can impede the convergence. In this paper, we propose a novel method called ordered momentum (OrMo) for ASGD. In OrMo, momentum is incorporated into ASGD by organizing the gradients in order based on their iteration indexes. We theoretically prove the convergence of OrMo with both constant and delay-adaptive learning rates for non-convex problems. To the best of our knowledge, this is the first work to establish the convergence analysis of ASGD with momentum without dependence on the maximum delay. Empirical results demonstrate that OrMo can achieve better convergence performance compared with ASGD and other asynchronous methods with momentum.
Paper
Similar papers
Peer review
Summary
In distributed learning environments, asynchronous SGD (ASGD) and its variants are often used to deal with computing nodes with uneven computing power. Momentum methods are beneficial for both optimization and generalization in deep model training, but directly applying momentum to ASGD may hinder its convergence. The paper proposes the OrMo method to integrate momentum into ASGD by sorting gradients based on iteration index. The paper provides a theoretical proof of the convergence of OrMo on non-convex problems.
Strengths
1. A new asynchronous stochastic gradient descent optimization method (OrMo) is proposed, and a theoretical proof of convergence on non-convex problems is provided, which is the first time that it does not rely on the bounded delay assumption. 2. Experiments show the advantages of the OrMo method in convergence performance. 3. The paper provides detailed algorithm implementation details and open access links to the experimental code, which enhances the reproducibility. 4. The experiment setting is clear, and the wall-clock time shows that the OrMo outperforms baseline methods significantly.
Weaknesses
1. Although experimental validation was performed on the CIFAR dataset, the generalization ability of the OrMo method may need to be further tested in more types of datasets and different application scenarios. 2. The paper does not discuss in detail the computational resource requirements of the OrMo method on data and models of different scales. Specifically, the ordered momentum need to be cached on the server, the extra storage costs should be considerred. 3. The proposed re-ordering method inherently is like the staleness control. The difference is that the OrMo proposes using the exponentioal term on \beta to control the staleness of the incoming gradients.
Questions
Figure 3 shows that the curve is very unstable. So, on which epoch, the model is used as the final model for testing?
Rating
5
Confidence
3
Soundness
2
Presentation
3
Contribution
3
Limitations
N/A
Thanks for explanations
Thanks for the efforts and explanations. As illustrated by authors, > In penalty function methods, gradients with larger delays are given smaller weights when updating the parameter. In OrMo, gradients with larger delays are given smaller weights when updating the momentum, but larger weights when updating the parameter. Thus, the main differences between the penalty and the OrMo is the updating object, i.e., parameter v.s. momentum. Inherently, the core idea is similar, as adjusting the weights according to the staleness. In light of this, I think the claim that the OrMo is not a staleness-control method is not appropriate. Maybe authors should reconsider this claim. Nevertheless, I appreciate the idea of integrating momentum into ASGD by sorting gradients based on iteration index. Thus, I'd like to keep the positive score.
We greatly appreciate the insightful follow-up comments, which helps us rethink about our work. We agree that OrMo can be considered as another type of staleness-control methods since the weights in OrMo are depended on the staleness. We will add the discussion in the final version and sincerely thank you for your support of our work.
Summary
This paper proposed a new ordered momentum for asynchronous SGD based on the delayed update characteristic of asynchronous training, which weights the momentum according to the actual iteration index. The authors proved the convergence of the algorithm both theoretically and experimentally.
Strengths
* This paper proposes a new momentum algorithm for ASGD and proves that the algorithm is convergent. * Experiments are conducted in this paper to verify the effectiveness of the OrMo algorithm.
Weaknesses
* This paper studies asynchronous training algorithms but does not explore the effect of asynchronous delays on convergence. * The theoretical results in this paper are limited by the number of distributed workers $K$, i.e., the algorithm does not scale well to large-scale distributed training systems.
Questions
1. The theoretical results in this paper do not contain asynchronous delay information and fail to reveal the effect of asynchronous delay on the convergence of the algorithm. This may be due to rough gradient upper bounds that obscure the delay gradient information. However, the reviewer believes that analyzing the effect of asynchronous delay is essential in a work that studies ASGD algorithms. Also, the experimental section did not test the empirical effect of different delays on the algorithm. 2. Theorem 1 shows that the convergence of the algorithm is linearly dependent on the number of distributed workers $K$, which implies that the algorithm will fail to converge when $K$ is large. In light of this theoretical result, can't the algorithm proposed in this paper be applied to large-scale distributed training systems? 3. The algorithm design and theoretical analysis in this paper relies on a fixed constant learning rate. Can this be extended to adaptive learning rates or decreasing learning rates that are more common in practice? 4. The result of Lemma 4 in the main text is inconsistent with the proof in the Appendix.
Rating
5
Confidence
4
Soundness
3
Presentation
2
Contribution
3
Limitations
Please refer to Weaknesses and Questions.
Summary
The paper introduces Ordered Momentum (OrMo), a novel method enhancing the performance of ASGD by systematically incorporating momentum based on the iteration indexes of gradients. The authors provide theoretical proofs demonstrating the convergence of OrMo for non-convex problems, marking an advancement as this is purportedly the first such convergence analysis for ASGD with momentum that does not rely on the bounded delay assumption. Empirical results further validate that OrMo outperforms standard ASGD and other asynchronous variants with momentum in terms of convergence rates.
Strengths
1. The proposed OrMo algorithm addresses the common problem of momentum integration in asynchronous settings, which is often associated with convergence issues. 2. The paper provides a convergence analysis of OrMo in non-convex settings without the need for a bounded delay assumption.
Weaknesses
1. The writing and presentation of the paper seems to require substantial improvement. Especially for Section 3, it is hard to fully follow the algorithmic and theoretical details, making it laborious to check the correctness. 2. The paper considers only scenarios with homogeneous data distributions, where the workers access to a shared dataset $\mathcal{D}$. 3. Assumption 1 includes a bounded gradient assumption, which is rather demanding. 4. The experiment setup does not quite match the theoretical analysis. In the experiment, the learning rate is multiplied by a factor after a specific number of epochs, while Theorem 1 is based on a constant learning rate. There also lacks discussion on how the multiplication factors and the intervals are tuned.
Questions
1. What is the impact of the size of the waiting set $\mathcal{C}$? How to choose the size of $\mathcal{C}$? 2. What are the key insights that the convergence can be guaranteed without bounded delay? 3. What is the complexity and cost in terms of the ordering of gradients?
Rating
3
Confidence
2
Soundness
2
Presentation
1
Contribution
2
Limitations
The authors have partially addressed the limitations.
Summary
This paper introduces OrMo, a novel method to weight stale gradients received on the server in asynchronous SGD with momentum. The algorithm is based on the idea of organizing the sequence of gradients received on the server into "buckets" to approximate standard minibatch SGD with momentum. The method is shown to converge under arbitrary (possibly unbounded) delays, with experiments on CIFAR-10 and CIFAR-100 validating the strength of OrMo compared to some baseline.
Strengths
* **Convergence without bounded delay assumption:** Convergence is proved without relying on the bounded delay assumption, extending recent analysis of ASGD [[Mishchenko et al., 2022]](https://arxiv.org/pdf/2206.07638 ), [[Koloskova et al., 2022]](https://arxiv.org/pdf/2206.08307 ) to ASGD with momentum. * **Clear explanation of the "momentum as a sum of weighted buckets" idea:** Time is spent to clearly lay down the ideas of "buckets" and re-writing the momentum updates so that OrMo comes naturally, which is helped by Fig.1 \& 2. * **Promising experimental results:** Compared to naive implementation (e.g., plain ASGD with momentum) and some chosen baselines, OrMo is shown to perform better in practice, especially in cases where the workers speed is heterogeneous.
Weaknesses
* **Lack of discussion between OrMo and its approximation of standard synchronous SGD with momentum:** While the idea of OrMo may seem natural when we visualize standard momentum as a "sum of weighted buckets of gradients", the update performed by OrMo simply *approximate* synchronous momentum. Indeed, as the parameters hosted on the server are updated at each stochastic gradient in the asynchronous setting, the *points* $w_t$ on which the gradients are computed all differ even inside a given "bucket", which is not the case for synchronous SGDm. Yet, this is not discussed. * **Standard baselines are lacking in the experiments:** In Table 1\&2, and in Fig. 3\& 4, a comparison *(for reference only)* to synchronous SGDm could be interesting to have (to see whether or not there is still a gap to fill with synchronous methods in terms of "performance per iteration"). Moreover, it seems that the baselines "tuning the momentum value" for asynchronous SGD with momentum described in [[Zhang and Mitliagkas, 2018]]( https://arxiv.org/pdf/1706.03471 ) and [[Mitliagkas et al., 2016]]( https://arxiv.org/pdf/1605.09774 ) are lacking. Finally, we can see OrMo as a method to penalize stale gradients received by the server, using some sort of "exponential weight". Empirically, there have been other "penalty functions" that have been tried in Asynchronous Federated Learning, such as the ones described Part 5.2 of [[Xie et al., 2020]]( https://www.opt-ml.org/papers/2020/paper_28.pdf ). Have you compared OrMo to them?
Questions
* In Theorem 1, the quantities $L,G$ do not appear in the convergence rate (contrary to what is displayed in Theorem 2 of [[Mishchenko et al., 2022]](https://arxiv.org/pdf/2206.07638 ) ). Is it normal? * Fig.5: As the Parameter Server is known to become a bottleneck for communications at scale, how does OrMo fair compared to synchronous SGDm at larger scale than $K=16$? (for instance, $K=64$)
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
2
Limitations
.
Thanks for responses
I have two follow-up comments: - 1. Why do you train ViT on CIFAR-10, instead of ResNet? The ResNet 18 trained with SGD momentum can obtain round 94% test accuracy, which should be the most standard baseline to compare optimizers with SGD momentum. - 2. While the derivation of how to adjust the momentum is complex, the core of it is still like staleness control and a penalty function.
We sincerely thank you for your timely response. We would like to answer the questions point by point as follows: 1. In the maintext of our submission, we have presented the empirical results of training a ResNet20 model on the CIFAR-10 dataset. More experimental results about ResNet20 are given in the response to Reviewer NjVh. Meanwhile, we promise to add the experimental results of training a Vision Transformer model on CIFAR-10 in our initial responses. The number of workers is set as $32$. The additional experiments are finished now. We would like to present the results below. Each experiment is repeated 3 times. |Test Accuracy | (hom.) | (het.) | | -------|--------|---------| |ASGD | 56.09\% $\pm$ 0.41\% | 56.33\% $\pm$ 0.56\% | |naive ASGDm | 55.66\% $\pm$ 0.15\% | 55.74\% $\pm$ 0.35\% | |shifted momentum | 57.43\% $\pm$ 0.28\% | 57.39\% $\pm$ 0.47\% | |SMEGA$^2$ | 60.54\% $\pm$ 0.05\% | 60.66\% $\pm$ 0.12\% | |OrMo | **61.21\% $\pm$ 0.17\%** | **61.30\% $\pm$ 0.11\%** | We have also tested the performance of the OrMo method on the ResNet18 model, as you mentioned, over the past three days. Compared to the above Vision Transformer model which has about $0.5$ million parameters, ResNet18 has $10$ million parameters. OrMo achieves around 94% test accuracy on the ResNet18 model, as shown in the table below. Please note that while shifted momentum performs well in terms of final test accuracy, it converges more slowly than OrMo. Specifically, OrMo requires approximately 30 epochs to reach 85% test accuracy, whereas shifted momentum requires 60 epochs. Due to format constraints in the discussion period, we are unable to include figures in this response. We will provide more details (e.g., training curve figures) in the final version. These additional results are consistent with those in the main text and further support the conclusions of our work. |Test Accuracy | (hom.) | (het.) | | -------|--------|---------| |ASGD | 91.45\% | 91.52\% | |naive ASGDm | 93.74\% | 93.10\% | |shifted momentum | 94.02\% | 94.20\% | |SMEGA$^2$ | 93.72\% | 93.36\% | |OrMo | **94.32\%** | **94.26\%** | 2. We sincerely thank you for the valuable comment, which makes us rethink about our method. We have provided a discussion about the differences between OrMo and existing penalty function methods in the general response, and we will add the discussion in the final version. Meanwhile, we would like to briefly summarize the differences between OrMo and existing methods that use a penalty function below. + For penalty function methods, the key insight is to reduce the contribution of gradients with larger delays to the parameter update. For OrMo, the key insight lies in tracking the sequences $\hat{\bf w}_t$ and $\hat{\bf u}_t$ defined in Subsection 3.3, which are updated in a manner similar to SSGDm. + In penalty function methods, gradients with larger delays are given smaller weights when updating the parameter. In OrMo, gradients with larger delays are given smaller weights when updating the momentum, but larger weights when updating the parameter. Both theoretical derivations and empirical ablation studies highlight the importance of giving larger weights to gradients with larger delays when updating the parameter For more details, please refer to our general responses. Thank you again for letting us know your remaining concerns. We are always willing to answer any further questions.
Thanks to the authors for their responses. I currently have no further questions.
Thank you for the response. We are grateful for your support of our work.
comparison to existing results
How is the theoretical convergence rate in this paper comparable to existing results such as vanilla asynchronous SGD: Asynchronous parallel stochastic gradient for nonconvex optimization. momentum asynchronous SGD: 1-bit Adam: Communication Efficient Large-Scale Training with Adam’s Convergence Speed
Dear Area Chair, We greatly appreciate your valuable time on our submission and the insightful comments, which make us rethink our method. We would like to briefly summarize the theoretical results in our work and then compare our results with those in existing works [1][2]. **Theoretical results in our work:** In our submission, we propose an asynchronous momentum method called OrMo and give a theoretical analysis of the convergence rate of OrMo without relying on the maximum delay of the gradients. In Theorem $1$ of our submission, OrMo has the following convergence rate: $$ \frac{1}{T}\sum_{t=1}^T \mathbb{E}\\|\nabla F({\bf w}_t)\\|^2\leq \mathcal{O} (\frac{\sigma}{\sqrt{T}}+ \frac{K^{\frac{2}{3}}}{T^{\frac{2}{3}}} + \frac{K}{T}), $$ where $T$ is the number of iterations and $K$ is the number of workers. Below, we will make a comparison between the theoretical convergence rate of OrMo and those of the existing works in [1][2]. **Comparison with [1]:** [1] provides a theoretical analysis for vanilla asynchronous SGD (ASGD). As shown in Theorem $1$ and Corollary $2$ in [1], for smooth non-convex problems, ASGD has a convergence rate of $\frac{1}{T}\sum\_{t=1}^T \mathbb{E}\\|\nabla F({\bf w}\_t)\\|^2\leq \mathcal{O} (\frac{\sigma}{\sqrt{T}})$ when $T \geq \Omega(\tau_{max}^2)$. For OrMo, the same convergence rate can be achieved when $T \geq \Omega(K^4)$. Although the convergence rate are the same, our analysis is based on weaker assumptions since we do not assume a bounded delay. To the best of our knowledge, this is the first work to establish the convergence analysis of ASGD with momentum without relying on the bounded delay assumption. **Comparison with [2]:** [2] proposes 1-bit Adam, which is a communication efficient momentum SGD algorithm pre-conditioned with Adam optimizer. As shown in Theorem $1$ and Corollary $1$ in [2], 1-bit Adam has the following convergence rate: $$ \frac{1}{\tilde{T}}\sum_{t=1}^{\tilde{T}} \mathbb{E}\\|\nabla F({\bf w}_t)\\|^2\leq \mathcal{O} (\frac{\sigma}{\sqrt{K\tilde{T}}}+ \frac{1}{\tilde{T}^{\frac{2}{3}}} + \frac{1}{\tilde{T}}), $$ where $K$ is the number of workers and $\tilde{T}$ is the number of iteration. We notice that the server in 1-bit Adam needs to aggregate the information from all the $K$ workers at each iteration and every worker executes a gradient computation for each iteration. For fair comparison, we can rewrite the convergence rate of 1-bit Adam in terms of the number of gradient computations as $\mathcal{O} (\frac{\sigma}{\sqrt{C}}+ \frac{K^{\frac{2}{3}}}{C^{\frac{2}{3}}} + \frac{K}{C})$, where $C$ is the number of gradient computations and $C = K \tilde{T}$. At each iteration of OrMo, the server only needs one stochastic gradient. Thus, the convergence rate of OrMo in terms of the number of gradient computations is $\mathcal{O} (\frac{\sigma}{\sqrt{C}}+ \frac{K^{\frac{2}{3}}}{C^{\frac{2}{3}}} + \frac{K}{C})$. We can find that OrMo and 1-bit Adam have the same convergence rate in terms of gradient computations. Meanwhile, we would like to clarify that although the two methods have the same convergence rate, the application scenarios of 1-bit Adam and OrMo are quite different. The communication compression technique in 1-bit Adam can greatly reduce the communication cost while the asynchronous updating technique in OrMo is mainly to reduce the synchronization overhead when the computing capabilities of workers are heterogeneous. Additionally, combining OrMo with the communication compression technique used 1-bit Adam can reduce its communication overhead, which can be considered in future work. --- We sincerely thank you again for the valuable comments, which greatly help us improve our work. We promise that the discussion and the references [1][2] will be added in the final version. [1] Lian et al., Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization. NeurIPS 2015. [2] Tang et al., 1-bit Adam: Communication Efficient Large-Scale Training with Adam’s Convergence Speed. ICML 2021.
I thank the authors for their rebuttals, and their thorough discussion of the points I raised. I hope the authors will include these additional experimental results, the more "standard" presentation of convergence results, as well as the discussions (especially the one about the difference with penalty function methods which I found particularly instructive) in their final version of the paper. Given that my concerns were answered, I raise my score.
We greatly appreciate the insightful comments, which help us rethink our work. The additional results, the more "standard" presentation of convergence results, and the discussions will be included in the final version of the paper, as we promised. Thank you deeply for the support of our work.
I thank the authors for the response. The paper integrates momentum into ASGD. Compared to vanilla ASGD [1], this paper requires stronger assumption, while not improving the convergence rate. I am inclined to change my score to 4. As I have not carefully checked the technical details of the analysis, my confidence remains limited. [1] Mishchenko el al., Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays, NeurIPS 2022.
We sincerely thank the reviewer for the willingness to increase the rating and the follow-up comments. Meanwhile, we would like to address the remaining concern below. **Q: The paper integrates momentum into ASGD. Compared to vanilla ASGD [1], this paper requires stronger assumption, while not improving the convergence rate.** + We would like to first clarify that momentum is widely used in distributed machine learning and has a good performance in many practical applications. There are several existing works that integrate momentum into ASGD [2][3][4]. However, as far as we know, there is almost no convergence analysis of these methods in existing works. In view of this challenge, we introduce the ordered momentum to ASGD and present the method OrMo, which is theoretically proven to be convergent and empirically performs better than existing methods. + Although the analysis of ASGD for adaptive learning rates in [1] does not require the bounded gradient assumption, the analysis of ASGD for constant learning rates in [1] is based on the bounded gradient assumption. Therefore, the analyses in our work and in [1] for constant learning rates are under the same assumptions ($L$-Lipschitz smoothness, lower-bounded objective, and bounded gradient). + As presented in Remark 6 at the end of Section 3, OrMo can also be used with adaptive learning rates. We have discussed this point in the general response, and will further explore it in future work. Given the reasons above, we carefully think that there are adequate theoretical contributions in our work. We hope that our response can address the reviewer's concern. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work based on our response. [1] Mishchenko el al., Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays, NeurIPS 2022. [2] Giladi et al., At stability’s edge: How to adjust hyperparameters to preserve minima selection in asynchronous training of neural networks?, ICLR 2020. [3] Cohen et al., SMEGA2: distributed asynchronous deep neural network training with a single momentum buffer, ICPP 2022. [4] Mitliagkas et al., Asynchrony begets momentum, with an application to deep learning. In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 2016.
Decision
Accept (poster)