Distributed Stochastic Momentum Tracking with Local Updates: Achieving Optimal Communication and Iteration Complexities
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909891405283328 |
|---|---|
| author | Huang, Kun Pu, Shi |
| author_facet | Huang, Kun Pu, Shi |
| contents | We propose Local Momentum Tracking (LMT), a novel distributed stochastic gradient method for solving distributed optimization problems over networks. To reduce communication overhead, LMT enables each agent to perform multiple local updates between consecutive communication rounds. Specifically, LMT integrates local updates with the momentum tracking strategy and the Loopless Chebyshev Acceleration (LCA) technique. We demonstrate that LMT achieves linear speedup with respect to the number of local updates as well as the number of agents for minimizing smooth objective functions with and without the Polyak-Łojasiewicz (PL) condition. Notably, with sufficiently many local updates $Q\geq Q^*$, LMT attains the optimal communication complexity. For a moderate number of local updates $Q\in[1,Q^*]$, LMT achieves the optimal iteration complexity. To our knowledge, LMT is the first distributed stochastic gradient method with local updates that enjoys such properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24155 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Stochastic Momentum Tracking with Local Updates: Achieving Optimal Communication and Iteration Complexities Huang, Kun Pu, Shi Optimization and Control Distributed, Parallel, and Cluster Computing We propose Local Momentum Tracking (LMT), a novel distributed stochastic gradient method for solving distributed optimization problems over networks. To reduce communication overhead, LMT enables each agent to perform multiple local updates between consecutive communication rounds. Specifically, LMT integrates local updates with the momentum tracking strategy and the Loopless Chebyshev Acceleration (LCA) technique. We demonstrate that LMT achieves linear speedup with respect to the number of local updates as well as the number of agents for minimizing smooth objective functions with and without the Polyak-Łojasiewicz (PL) condition. Notably, with sufficiently many local updates $Q\geq Q^*$, LMT attains the optimal communication complexity. For a moderate number of local updates $Q\in[1,Q^*]$, LMT achieves the optimal iteration complexity. To our knowledge, LMT is the first distributed stochastic gradient method with local updates that enjoys such properties. |
| title | Distributed Stochastic Momentum Tracking with Local Updates: Achieving Optimal Communication and Iteration Complexities |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2510.24155 |