Adaptive Weighting Push-SUM for Decentralized Optimization with Statistical Diversity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929621821292544 |
|---|---|
| author | Zhou, Yiming Cheng, Yifei Xu, Linli Chen, Enhong |
| author_facet | Zhou, Yiming Cheng, Yifei Xu, Linli Chen, Enhong |
| contents | Statistical diversity is a property of data distribution and can hinder the optimization of a decentralized network. However, the theoretical limitations of the Push-SUM protocol reduce the performance in handling the statistical diversity of optimization algorithms based on it. In this paper, we theoretically and empirically mitigate the negative impact of statistical diversity on decentralized optimization using the Push-SUM protocol. Specifically, we propose the Adaptive Weighting Push-SUM protocol, a theoretical generalization of the original Push-SUM protocol where the latter is a special case of the former. Our theoretical analysis shows that, with sufficient communication, the upper bound on the consensus distance for the new protocol reduces to $O(1/N)$, whereas it remains at $O(1)$ for the Push-SUM protocol. We adopt SGD and Momentum SGD on the new protocol and prove that the convergence rate of these two algorithms to statistical diversity is $O(N/T)$ on the new protocol, while it is $O(Nd/T)$ on the Push-SUM protocol, where $d$ is the parameter size of the training model. To address statistical diversity in practical applications of the new protocol, we develop the Moreau weighting method for its generalized weight matrix definition. This method, derived from the Moreau envelope, is an approximate optimization of the distance penalty of the Moreau envelope. We verify that the Adaptive Weighting Push-SUM protocol is practically more efficient than the Push-SUM protocol via deep learning experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_07252 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Adaptive Weighting Push-SUM for Decentralized Optimization with Statistical Diversity Zhou, Yiming Cheng, Yifei Xu, Linli Chen, Enhong Distributed, Parallel, and Cluster Computing Statistical diversity is a property of data distribution and can hinder the optimization of a decentralized network. However, the theoretical limitations of the Push-SUM protocol reduce the performance in handling the statistical diversity of optimization algorithms based on it. In this paper, we theoretically and empirically mitigate the negative impact of statistical diversity on decentralized optimization using the Push-SUM protocol. Specifically, we propose the Adaptive Weighting Push-SUM protocol, a theoretical generalization of the original Push-SUM protocol where the latter is a special case of the former. Our theoretical analysis shows that, with sufficient communication, the upper bound on the consensus distance for the new protocol reduces to $O(1/N)$, whereas it remains at $O(1)$ for the Push-SUM protocol. We adopt SGD and Momentum SGD on the new protocol and prove that the convergence rate of these two algorithms to statistical diversity is $O(N/T)$ on the new protocol, while it is $O(Nd/T)$ on the Push-SUM protocol, where $d$ is the parameter size of the training model. To address statistical diversity in practical applications of the new protocol, we develop the Moreau weighting method for its generalized weight matrix definition. This method, derived from the Moreau envelope, is an approximate optimization of the distance penalty of the Moreau envelope. We verify that the Adaptive Weighting Push-SUM protocol is practically more efficient than the Push-SUM protocol via deep learning experiments. |
| title | Adaptive Weighting Push-SUM for Decentralized Optimization with Statistical Diversity |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2412.07252 |