Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910224054484992 |
|---|---|
| author | Guo, Luyao Alghunaim, Sulaiman A. Yuan, Kun Condat, Laurent Cao, Jinde |
| author_facet | Guo, Luyao Alghunaim, Sulaiman A. Yuan, Kun Condat, Laurent Cao, Jinde |
| contents | The ProxSkip algorithm for distributed optimization is gaining increasing attention due to its effectiveness in reducing communication. However, existing analyses of ProxSkip are limited to the strongly convex setting and fail to achieve linear speedup with respect to the number of nodes. Key questions regarding its behavior in the non-convex setting and the achievability of linear speedup remain open. In this paper, we revisit decentralized ProxSkip and answer these questions affirmatively. We provide a unified convergence analysis for stochastic non-convex, convex, and strongly convex problems, revealing how gradient noise, local updates, network connectivity, and data heterogeneity jointly determine the convergence behavior. To the best of our knowledge, this is the first analysis showing that decentralized ProxSkip achieves linear speedup in the number of nodes under stochastic gradients. Moreover, our results demonstrate that local updates can effectively reduce communication frequency and improve communication efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_07983 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization Guo, Luyao Alghunaim, Sulaiman A. Yuan, Kun Condat, Laurent Cao, Jinde Machine Learning Optimization and Control The ProxSkip algorithm for distributed optimization is gaining increasing attention due to its effectiveness in reducing communication. However, existing analyses of ProxSkip are limited to the strongly convex setting and fail to achieve linear speedup with respect to the number of nodes. Key questions regarding its behavior in the non-convex setting and the achievability of linear speedup remain open. In this paper, we revisit decentralized ProxSkip and answer these questions affirmatively. We provide a unified convergence analysis for stochastic non-convex, convex, and strongly convex problems, revealing how gradient noise, local updates, network connectivity, and data heterogeneity jointly determine the convergence behavior. To the best of our knowledge, this is the first analysis showing that decentralized ProxSkip achieves linear speedup in the number of nodes under stochastic gradients. Moreover, our results demonstrate that local updates can effectively reduce communication frequency and improve communication efficiency. |
| title | Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2310.07983 |